lca-0.3.1: O(log n) persistent online lowest common ancestor search 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 # Methodsfmap :: (a -> b) -> Path a -> Path b #(<\$) :: a -> Path b -> Path a # Source # Methodsfold :: Monoid m => Path m -> m #foldMap :: Monoid m => (a -> m) -> Path a -> m #foldr :: (a -> b -> b) -> b -> Path a -> b #foldr' :: (a -> b -> b) -> b -> Path a -> b #foldl :: (b -> a -> b) -> b -> Path a -> b #foldl' :: (b -> a -> b) -> b -> Path a -> b #foldr1 :: (a -> a -> a) -> Path a -> a #foldl1 :: (a -> a -> a) -> Path a -> a #toList :: Path a -> [a] #null :: Path a -> Bool #length :: Path a -> Int #elem :: Eq a => a -> Path a -> Bool #maximum :: Ord a => Path a -> a #minimum :: Ord a => Path a -> a #sum :: Num a => Path a -> a #product :: Num a => Path a -> a # Source # Methodstraverse :: Applicative f => (a -> f b) -> Path a -> f (Path b) #sequenceA :: Applicative f => Path (f a) -> f (Path a) #mapM :: Monad m => (a -> m b) -> Path a -> m (Path b) #sequence :: Monad m => Path (m a) -> m (Path a) # Read a => Read (Path a) Source # MethodsreadsPrec :: Int -> ReadS (Path a) #readList :: ReadS [Path a] # Show a => Show (Path a) Source # MethodsshowsPrec :: Int -> Path a -> ShowS #show :: Path a -> String #showList :: [Path a] -> ShowS #

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