lca-0.3: O(log n) persistent on-line lowest common ancestor calculation without preprocessing

Data.LCA.Online

Description

Provides online calculation of the the lowest common ancestor in O(log h) by compressing the spine of a `Path` using a skew-binary random access list.

This library implements the technique described in my talk

http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search

to improve the known asymptotic bounds on both online lowest common ancestor search

http://en.wikipedia.org/wiki/Lowest_common_ancestor

and the online level ancestor problem:

http://en.wikipedia.org/wiki/Level_ancestor_problem

Algorithms used here assume that the key values chosen for `k` are globally unique.

Synopsis

# Documentation

data Path a Source

Compressed paths using skew binary random access lists

Instances

 Source Source Source Read a => Read (Path a) Source Show a => Show (Path a) Source

lca :: Path a -> Path b -> Path a Source

O(log h) Compute the lowest common ancestor of two paths.

The `empty` `Path`

cons :: Int -> a -> Path a -> Path a Source

O(1) Invariant: most operations assume that the keys `k` are globally unique

Extend the `Path` with a new node ID and value.

uncons :: Path a -> Maybe (Int, a, Path a) Source

O(1) Extract the node ID and value from the newest node on the `Path`.

view :: Path a -> View Path a Source

O(1) Extract the node ID and value from the newest node on the `Path`, slightly faster than `uncons`.

null :: Foldable t => forall a. t a -> Bool

Test whether the structure is empty. The default implementation is optimized for structures that are similar to cons-lists, because there is no general way to do better.

length :: Foldable t => forall a. t a -> Int

Returns the size/length of a finite structure as an `Int`. The default implementation is optimized for structures that are similar to cons-lists, because there is no general way to do better.

isAncestorOf :: Path a -> Path b -> Bool Source

O(log h) `xs isAncestorOf ys` holds when `xs` is a prefix starting at the root of `Path` `ys`.

keep :: Int -> Path a -> Path a Source

O(log (h - k)) to `keep k` elements of `Path` of `length` `h`

This solves the online version of the "level ancestor problem" with no preprocessing in O(log h) time, improving known complexity bounds.

http://en.wikipedia.org/wiki/Level_ancestor_problem

drop :: Int -> Path a -> Path a Source

O(log k) to `drop k` elements from a `Path`

traverseWithKey :: Applicative f => (Int -> a -> f b) -> Path a -> f (Path b) Source

Traverse a `Path` with access to the node IDs.

toList :: Path a -> [(Int, a)] Source

Convert a `Path` to a list of `(ID, value)` pairs.

fromList :: [(Int, a)] -> Path a Source

Build a `Path` from a list of `(ID, value)` pairs.

(~=) :: Path a -> Path b -> Bool infix 4 Source

O(1) Compare to see if two trees have the same leaf key