-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | O(log n) persistent on-line lowest common ancestor calculation without preprocessing -- -- This package provides a reference implementation of my skew binary -- random access algorithm for performing an online lowest common -- ancestor search (and online level ancestor search) in logarithmic time -- without preprocessing. This improves the previous known asymptotic -- bound for both of these problems from O(h) to O(log h), -- where h is the height of the tree. Mostly importantly this -- bound is completely independent of the width or overall size of the -- tree, enabling you to calculate lowest common ancestors in a -- distributed fashion with good locality. -- -- While offline algorithms exist for both of these algorithms -- that that provide O(1) query time, they all require at least -- O(n) preprocessing, where n is the size of the entire -- tree, and so are less suitable for LCA search in areas such as -- revision control where the tree is constantly updated, or distributed -- computing where the tree may be too large to fit in any one computer's -- memory. -- -- Slides are available from -- -- -- http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search @package lca @version 0.3 module Data.LCA.View -- | Provides a consistent View for peeling off the bottom node of a -- path. data View f a Root :: View f a Node :: {-# UNPACK #-} !Int -> a -> (f a) -> View f a instance (GHC.Show.Show a, GHC.Show.Show (f a)) => GHC.Show.Show (Data.LCA.View.View f a) instance (GHC.Read.Read a, GHC.Read.Read (f a)) => GHC.Read.Read (Data.LCA.View.View f a) instance (GHC.Classes.Ord a, GHC.Classes.Ord (f a)) => GHC.Classes.Ord (Data.LCA.View.View f a) instance (GHC.Classes.Eq a, GHC.Classes.Eq (f a)) => GHC.Classes.Eq (Data.LCA.View.View f a) instance GHC.Base.Functor f => GHC.Base.Functor (Data.LCA.View.View f) instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Data.LCA.View.View f) instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Data.LCA.View.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. -- -- This library implements the technique described in my talk -- -- -- http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search -- -- to improve the known asymptotic bounds on both online lowest common -- ancestor search -- -- http://en.wikipedia.org/wiki/Lowest_common_ancestor -- -- and the online level ancestor problem: -- -- http://en.wikipedia.org/wiki/Level_ancestor_problem -- -- Algorithms used here assume that the key values chosen for k -- are globally unique. -- -- This version provides access to a monoidal "summary" of the elided -- path for many operations. module Data.LCA.Online.Monoidal -- | A compressed Path as a skew binary random access list data Path a -- | Convert a Path to a list of (ID, value) pairs. toList :: Path a -> [(Int, a)] -- | Build a Path from a list of (ID, value) pairs. fromList :: Monoid a => [(Int, a)] -> Path a -- | O(n) Re-annotate a Path full of monoidal values using a -- different Monoid. map :: Monoid b => (a -> b) -> Path a -> Path b -- | O(n) Re-annotate a Path full of monoidal values/ -- -- Unlike map, 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 -- | O(n) Re-annotate a Path full of monoidal values with -- access to the key. mapWithKey :: Monoid b => (Int -> a -> b) -> Path a -> Path b -- | Traverse a Path yielding a new monoidal annotation. traverse :: (Applicative f, Monoid b) => (a -> f b) -> Path a -> f (Path b) -- | Traverse a Path with access to the node IDs. 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 -- -- Extend the Path with a new node ID and value. cons :: Monoid a => Int -> a -> Path a -> Path a -- | O(1) Extract the node ID and value from the newest node on the -- Path. uncons :: Monoid a => Path a -> Maybe (Int, a, Path a) -- | O(1) Extract the node ID and value from the newest node on the -- Path, slightly faster than uncons. view :: Monoid a => Path a -> View Path a -- | Test whether the structure is empty. The default implementation is -- optimized for structures that are similar to cons-lists, because there -- is no general way to do better. null :: Foldable t => forall a. t a -> Bool -- | Returns the size/length of a finite structure as an Int. The -- default implementation is optimized for structures that are similar to -- cons-lists, because there is no general way to do better. length :: Foldable t => forall a. t a -> Int -- | Extract a monoidal summary of a Path. measure :: Monoid a => Path a -> a -- | O(log h) xs `isAncestorOf' ys holds when -- xs is a prefix starting at the root of path ys. isAncestorOf :: Monoid b => Path a -> Path b -> Bool -- | O(log (h - k)) to keep k elements of -- Path of length h -- -- This solves the online version of the "level ancestor problem" with no -- preprocessing in O(log h) time, improving known complexity -- bounds. -- -- http://en.wikipedia.org/wiki/Level_ancestor_problem keep :: Monoid a => Int -> Path a -> Path a -- | O(log (h - k)) to keep k elements of Path of -- length h, and provide a monoidal summary of the -- dropped elements using a supplied monoid homomorphism. mkeep :: (Monoid a, Monoid b) => (a -> b) -> Int -> Path a -> (b, 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 using a suplied -- monoid homomorphism mdrop :: (Monoid a, Monoid b) => (a -> b) -> Int -> Path a -> (b, 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 using the supplied -- monoid homomorphisms. mlca :: (Monoid a, Monoid b, Monoid c, Monoid d) => (a -> c) -> (b -> d) -> Path a -> Path b -> (c, Path a, d, Path b) instance GHC.Read.Read a => GHC.Read.Read (Data.LCA.Online.Monoidal.Path a) instance GHC.Show.Show a => GHC.Show.Show (Data.LCA.Online.Monoidal.Path a) instance GHC.Read.Read a => GHC.Read.Read (Data.LCA.Online.Monoidal.Tree a) instance GHC.Show.Show a => GHC.Show.Show (Data.LCA.Online.Monoidal.Tree a) instance Data.Foldable.Foldable Data.LCA.Online.Monoidal.Tree instance Data.Foldable.Foldable Data.LCA.Online.Monoidal.Path -- | Naive online calculation of the the lowest common ancestor in -- O(h) module Data.LCA.Online.Naive -- | An uncompressed Path with memoized length. data Path a -- | The empty Path empty :: Path a -- | O(1) Invariant: most operations assume that the keys k -- are globally unique -- -- Extend the path with a new node ID and value. cons :: Int -> a -> Path a -> Path a -- | O(1) Extract the node ID and value from the newest node on the -- Path. uncons :: Path a -> Maybe (Int, a, Path a) -- | O(1) Extract the node ID and value from the newest node on the -- Path, slightly faster than uncons. view :: Path a -> View Path a -- | Test whether the structure is empty. The default implementation is -- optimized for structures that are similar to cons-lists, because there -- is no general way to do better. null :: Foldable t => forall a. t a -> Bool -- | Returns the size/length of a finite structure as an Int. The -- default implementation is optimized for structures that are similar to -- cons-lists, because there is no general way to do better. length :: Foldable t => forall a. t a -> Int -- | O(h) xs isAncestorOf ys holds when xs -- is a prefix starting at the root of Path ys. isAncestorOf :: Path a -> Path b -> Bool -- | O(h) Compute the lowest common ancestor of two paths lca :: Path a -> Path b -> Path a -- | O(h - k) to keep k elements of Path of -- length h keep :: Int -> Path a -> Path a -- | O(k) to drop k elements from a Path drop :: Int -> Path a -> Path a -- | Traverse a Path with access to the node IDs. traverseWithKey :: Applicative f => (Int -> a -> f b) -> Path a -> f (Path b) -- | Convert a Path to a list of (ID, value) pairs. toList :: Path a -> [(Int, a)] -- | Build a Path from a list of (ID, value) pairs. fromList :: [(Int, a)] -> Path a -- | O(1) Compare to see if two trees have the same leaf key (~=) :: Path a -> Path b -> Bool instance GHC.Read.Read a => GHC.Read.Read (Data.LCA.Online.Naive.Path a) instance GHC.Show.Show a => GHC.Show.Show (Data.LCA.Online.Naive.Path a) instance GHC.Base.Functor Data.LCA.Online.Naive.Path instance Data.Foldable.Foldable Data.LCA.Online.Naive.Path instance Data.Traversable.Traversable Data.LCA.Online.Naive.Path -- | Provides online calculation of the the lowest common ancestor in -- O(log h) by compressing the spine of a Path using a -- skew-binary random access list. -- -- This library implements the technique described in my talk -- -- -- http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search -- -- to improve the known asymptotic bounds on both online lowest common -- ancestor search -- -- http://en.wikipedia.org/wiki/Lowest_common_ancestor -- -- and the online level ancestor problem: -- -- http://en.wikipedia.org/wiki/Level_ancestor_problem -- -- 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 of two paths. 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 -- -- Extend the Path with a new node ID and value. cons :: Int -> a -> Path a -> Path a -- | O(1) Extract the node ID and value from the newest node on the -- Path. uncons :: Path a -> Maybe (Int, a, Path a) -- | O(1) Extract the node ID and value from the newest node on the -- Path, slightly faster than uncons. view :: Path a -> View Path a -- | Test whether the structure is empty. The default implementation is -- optimized for structures that are similar to cons-lists, because there -- is no general way to do better. null :: Foldable t => forall a. t a -> Bool -- | Returns the size/length of a finite structure as an Int. The -- default implementation is optimized for structures that are similar to -- cons-lists, because there is no general way to do better. length :: Foldable t => forall a. t 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 length h -- -- This solves the online version of the "level ancestor problem" with no -- preprocessing in O(log h) time, improving known complexity -- bounds. -- -- http://en.wikipedia.org/wiki/Level_ancestor_problem keep :: Int -> Path a -> Path a -- | O(log k) to drop k elements from a Path drop :: Int -> Path a -> Path a -- | Traverse a Path with access to the node IDs. traverseWithKey :: Applicative f => (Int -> a -> f b) -> Path a -> f (Path b) -- | Convert a Path to a list of (ID, value) pairs. toList :: Path a -> [(Int, a)] -- | Build a Path from a list of (ID, value) pairs. fromList :: [(Int, a)] -> Path a -- | O(1) Compare to see if two trees have the same leaf key (~=) :: Path a -> Path b -> Bool instance GHC.Read.Read a => GHC.Read.Read (Data.LCA.Online.Path a) instance GHC.Show.Show a => GHC.Show.Show (Data.LCA.Online.Path a) instance GHC.Read.Read a => GHC.Read.Read (Data.LCA.Online.Tree a) instance GHC.Show.Show a => GHC.Show.Show (Data.LCA.Online.Tree a) instance GHC.Base.Functor Data.LCA.Online.Tree instance Data.Foldable.Foldable Data.LCA.Online.Tree instance Data.Traversable.Traversable Data.LCA.Online.Tree instance GHC.Base.Functor Data.LCA.Online.Path instance Data.Foldable.Foldable Data.LCA.Online.Path instance Data.Traversable.Traversable Data.LCA.Online.Path