Data.LCA.Online.Naive

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

Documentation

data Path k a

Instances

Functor (Path k)

Foldable (Path k)

Traversable (Path k)

(Read k, Read a) => Read (Path k a)

(Show k, Show a) => Show (Path k a)

empty :: Path k a

The empty path

cons :: k -> a -> Path k a -> Path k a

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

null :: Path k a -> Bool

O(1)

length :: Path k a -> Int

O(1)

isAncestorOf :: Eq k => Path k a -> Path k b -> Bool

lca :: Eq k => Path k a -> Path k b -> Path k a

O(h) Compute the lowest common ancestor

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

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

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

O(k) to drop k elements from a path

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

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

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

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

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