-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | O(log n) online lowest common ancestor calculation
--
-- O(log n) online lowest common ancestor calculation
@package lca
@version 0.1.0.1
-- | Naive online calculation of the the lowest common ancestor in
-- O(h)
module Data.LCA.Online.Naive
data Path k a
-- | The empty path
empty :: Path k a
-- | O(1) Invariant: most operations assume that the keys k
-- are globally unique
cons :: k -> a -> Path k a -> Path k a
-- | O(1)
null :: Path k a -> Bool
-- | O(1)
length :: Path k a -> Int
isAncestorOf :: Eq k => Path k a -> Path k b -> Bool
-- | O(h) Compute the lowest common ancestor
lca :: Eq k => Path k a -> Path k b -> Path k a
-- | O(h - k) to keep k elements of path of height
-- h
keep :: Int -> Path k a -> Path k a
-- | O(k) to drop k elements from a path
drop :: Int -> Path k a -> Path k a
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
-- | O(1) Compare to see if two trees have the same leaf key
(~=) :: Eq k => Path k a -> Path k b -> Bool
instance (Show k, Show a) => Show (Path k a)
instance (Read k, Read a) => Read (Path k a)
instance Traversable (Path k)
instance Foldable (Path k)
instance Functor (Path k)
-- | 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.
module Data.LCA.Online
-- | Compressed paths using skew binary random access lists
data Path k a
-- | The empty path
empty :: Path k a
-- | O(1) Invariant: most operations assume that the keys k
-- are globally unique
cons :: k -> a -> Path k a -> Path k a
-- | O(1)
null :: Path k a -> Bool
-- | O(1)
length :: Path k a -> Int
isAncestorOf :: Eq k => Path k a -> Path k b -> Bool
-- | O(log h) Compute the lowest common ancestor
lca :: Eq k => Path k a -> Path k b -> Path k a
-- | O(log (h - k)) to keep k elements of path of height
-- h
keep :: Int -> Path k a -> Path k a
-- | O(log k) to drop k elements from a path
drop :: Int -> Path k a -> Path k a
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
-- | O(1) Compare to see if two trees have the same leaf key
(~=) :: Eq k => Path k a -> Path k b -> Bool
instance (Show k, Show a) => Show (Tree k a)
instance (Read k, Read a) => Read (Tree k a)
instance (Show k, Show a) => Show (Path k a)
instance (Read k, Read a) => Read (Path k a)
instance Traversable (Tree k)
instance Foldable (Tree k)
instance Functor (Tree k)
instance Traversable (Path k)
instance Foldable (Path k)
instance Functor (Path k)