Data.LCA.Online.Naive

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

Documentation

data Path a

Instances

Functor Path

Foldable Path

Traversable Path

Read a => Read (Path a)

Show a => Show (Path a)

empty :: Path a

The empty path

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

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

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

view :: Path a -> View Path a

null :: Path a -> Bool

O(1)

length :: Path a -> Int

O(1)

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

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

O(h) Compute the lowest common ancestor

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

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

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

O(k) to drop k elements from a path

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

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

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

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

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