lca-0.2.1: O(log n) persistent on-line lowest common ancestor calculation without preprocessing with optional monoidal annotations

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

Data.LCA.Online.Monoidal

Description

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

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

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

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

fromList :: Monoid a => [(Int, a)] -> Path aSource

map :: (Monoid a, Monoid b) => (a -> b) -> Path a -> Path bSource

mapHom :: (a -> b) -> Path a -> Path bSource

mapHom f assumes that f is a monoid homomorphism, that is to say, you must ensure

 f a `mappend` f b = f (a `mappend` b)
 f mempty = mempty

mapWithKey :: (Monoid a, Monoid b) => (Int -> a -> b) -> Path a -> Path bSource

traverse :: (Applicative f, Monoid b) => (a -> f b) -> Path a -> f (Path b)Source

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

empty :: Path aSource

The empty path

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

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

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

view :: Monoid a => Path a -> View Path aSource

null :: Path a -> BoolSource

O(1)

length :: Path a -> IntSource

O(1)

measure :: Monoid a => Path a -> aSource

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

O(log (h - k)) to keep k elements of path of height h

mkeep :: Monoid a => Int -> Path a -> (a, Path a)Source

O(log (h - k)) to keep k elements of path of height h, and provide a monoidal summary of the dropped elements

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

O(log k) to drop k elements from a path

mdrop :: Monoid a => Int -> Path a -> (a, Path a)Source

O(log k) to drop k elements from a path and provide a monoidal summary of the dropped elements

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

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

lca :: (Monoid a, Monoid b) => Path a -> Path b -> Path aSource

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

mlca :: (Monoid a, Monoid b) => Path a -> Path b -> (a, Path a, b, Path b)Source

O(log h) Compute the lowest common ancestor of two paths along with a monoidal summary of their respective tails.