-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | O(log n) persistent on-line lowest common ancestor calculation without preprocessing with optional monoidal annotations -- -- O(log n) persistent on-line lowest common ancestor calculation without -- preprocessing with optional monoidal annotations @package lca @version 0.2 module Data.LCA.View data View f a Root :: View f a Node :: {-# UNPACK #-} !Int -> a -> (f a) -> View f a instance (Eq a, Eq (f a)) => Eq (View f a) instance (Ord a, Ord (f a)) => Ord (View f a) instance (Read a, Read (f a)) => Read (View f a) instance (Show a, Show (f a)) => Show (View f a) instance Traversable f => Traversable (View f) instance Foldable f => Foldable (View f) instance Functor f => Functor (View f) -- | 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.Monoidal -- | Compressed paths using skew binary random access lists data Path a toList :: Path a -> [(Int, a)] fromList :: Monoid a => [(Int, a)] -> Path a map :: (Monoid a, Monoid b) => (a -> b) -> Path a -> Path b -- | 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
--
mapHom :: (a -> b) -> Path a -> Path b mapWithKey :: (Monoid a, Monoid b) => (Int -> a -> b) -> Path a -> Path b traverse :: (Applicative f, Monoid b) => (a -> f b) -> Path a -> f (Path b) traverseWithKey :: (Applicative f, Monoid b) => (Int -> a -> f b) -> Path a -> f (Path b) -- | The empty path empty :: Path a -- | O(1) Invariant: most operations assume that the keys k -- are globally unique cons :: Monoid a => Int -> a -> Path a -> Path a uncons :: Monoid a => Path a -> Maybe (Int, a, Path a) view :: Monoid a => Path a -> View Path a -- | O(1) null :: Path a -> Bool -- | O(1) length :: Path a -> Int measure :: Monoid a => Path a -> a isAncestorOf :: Monoid b => Path a -> Path b -> Bool -- | O(log (h - k)) to keep k elements of path of height -- h keep :: Monoid a => Int -> Path a -> Path a -- | O(log (h - k)) to keep k elements of path of height -- h, and provide a monoidal summary of the dropped elements mkeep :: Monoid a => Int -> Path a -> (a, Path a) -- | O(log k) to drop k elements from a path drop :: Monoid a => Int -> Path a -> Path a -- | O(log k) to drop k elements from a path and provide a -- monoidal summary of the dropped elements mdrop :: Monoid a => Int -> Path a -> (a, Path a) -- | O(1) Compare to see if two trees have the same leaf key (~=) :: Path a -> Path b -> Bool -- | O(log h) Compute the lowest common ancestor of two paths lca :: (Monoid a, Monoid b) => Path a -> Path b -> Path a -- | O(log h) Compute the lowest common ancestor of two paths along -- with a monoidal summary of their respective tails. mlca :: (Monoid a, Monoid b) => Path a -> Path b -> (a, Path a, b, Path b) instance Show a => Show (Tree a) instance Read a => Read (Tree a) instance Show a => Show (Path a) instance Read a => Read (Path a) instance Foldable Path instance Foldable Tree -- | Naive online calculation of the the lowest common ancestor in -- O(h) module Data.LCA.Online.Naive data Path a -- | The empty path empty :: Path a -- | O(1) Invariant: most operations assume that the keys k -- are globally unique cons :: Int -> a -> Path a -> Path a uncons :: Path a -> Maybe (Int, a, Path a) view :: Path a -> View Path a -- | O(1) null :: Path a -> Bool -- | O(1) length :: Path a -> Int isAncestorOf :: Path a -> Path b -> Bool -- | O(h) Compute the lowest common ancestor lca :: Path a -> Path b -> Path a -- | O(h - k) to keep k elements of path of height -- h keep :: Int -> Path a -> Path a -- | O(k) to drop k elements from a path drop :: Int -> Path a -> Path a traverseWithKey :: Applicative f => (Int -> a -> f b) -> Path a -> f (Path b) toList :: Path a -> [(Int, a)] fromList :: [(Int, a)] -> Path a -- | O(1) Compare to see if two trees have the same leaf key (~=) :: Path a -> Path b -> Bool instance Show a => Show (Path a) instance Read a => Read (Path a) instance Traversable Path instance Foldable Path instance Functor Path -- | 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 a -- | O(log h) Compute the lowest common ancestor lca :: Path a -> Path b -> Path a -- | The empty path empty :: Path a -- | O(1) Invariant: most operations assume that the keys k -- are globally unique cons :: Int -> a -> Path a -> Path a -- | O(1) uncons :: Path a -> Maybe (Int, a, Path a) -- | O(1) view :: Path a -> View Path a -- | O(1) null :: Path a -> Bool -- | O(1) length :: Path a -> Int -- | O(log h) xs isAncestorOf ys holds when -- xs is a prefix starting at the root of path ys. isAncestorOf :: Path a -> Path b -> Bool -- | O(log (h - k)) to keep k elements of path of height -- h keep :: Int -> Path a -> Path a -- | O(log k) to drop k elements from a path drop :: Int -> Path a -> Path a traverseWithKey :: Applicative f => (Int -> a -> f b) -> Path a -> f (Path b) toList :: Path a -> [(Int, a)] fromList :: [(Int, a)] -> Path a -- | O(1) Compare to see if two trees have the same leaf key (~=) :: Path a -> Path b -> Bool instance Show a => Show (Tree a) instance Read a => Read (Tree a) instance Show a => Show (Path a) instance Read a => Read (Path a) instance Traversable Path instance Foldable Path instance Functor Path instance Traversable Tree instance Foldable Tree instance Functor Tree