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

Portabilityportable
Stabilityexperimental
MaintainerEdward Kmett <ekmett@gmail.com>
Safe HaskellSafe-Inferred

Data.LCA.Online.Naive

Description

Naive online calculation of the the lowest common ancestor in O(h)

Synopsis

Documentation

data Path a Source

An uncompressed Path with memoized length.

Instances

empty :: Path aSource

The empty Path

cons :: Int -> a -> Path a -> Path aSource

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 aSource

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

null :: Path a -> BoolSource

O(1) Returns True iff the Path is empty.

length :: Path a -> IntSource

O(1) Determine the length of a Path.

isAncestorOf :: Path a -> Path b -> BoolSource

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

lca :: Path a -> Path b -> Path aSource

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

keep :: Int -> Path a -> Path aSource

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

drop :: Int -> Path a -> Path aSource

O(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 aSource

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

(~=) :: Path a -> Path b -> BoolSource

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