-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | O(log n) persistent online lowest common ancestor search without preprocessing
--   
--   This package provides a reference implementation of my skew binary
--   random access algorithm for performing an <i>online</i> 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 <i>O(h)</i> to <i>O(log h)</i>,
--   where <i>h</i> 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 <i>offline</i> algorithms exist for both of these algorithms
--   that that provide <i>O(1)</i> query time, they all require at least
--   <i>O(n)</i> preprocessing, where <i>n</i> 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
--   
--   
--   <a>http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search</a>
@package lca
@version 0.3.1


module Data.LCA.View

-- | Provides a consistent <a>View</a> 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)


-- | Naive online calculation of the the lowest common ancestor in
--   <i>O(h)</i>
module Data.LCA.Online.Naive

-- | An uncompressed <a>Path</a> with memoized length.
data Path a

-- | The empty <a>Path</a>
empty :: Path a

-- | <i>O(1)</i> Invariant: most operations assume that the keys <tt>k</tt>
--   are globally unique
--   
--   Extend the path with a new node ID and value.
cons :: Int -> a -> Path a -> Path a

-- | <i>O(1)</i> Extract the node ID and value from the newest node on the
--   <a>Path</a>.
uncons :: Path a -> Maybe (Int, a, Path a)

-- | <i>O(1)</i> Extract the node ID and value from the newest node on the
--   <a>Path</a>, slightly faster than <a>uncons</a>.
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 => t a -> Bool

-- | Returns the size/length of a finite structure as an <a>Int</a>. 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 => t a -> Int

-- | <i>O(h)</i> <tt>xs <a>isAncestorOf</a> ys</tt> holds when <tt>xs</tt>
--   is a prefix starting at the root of <a>Path</a> <tt>ys</tt>.
isAncestorOf :: Path a -> Path b -> Bool

-- | <i>O(h)</i> Compute the lowest common ancestor of two paths
lca :: Path a -> Path b -> Path a

-- | <i>O(h - k)</i> to <tt><a>keep</a> k</tt> elements of <a>Path</a> of
--   <a>length</a> <tt>h</tt>
keep :: Int -> Path a -> Path a

-- | <i>O(k)</i> to <tt><a>drop</a> k</tt> elements from a <a>Path</a>
drop :: Int -> Path a -> Path a

-- | Traverse a <a>Path</a> with access to the node IDs.
traverseWithKey :: Applicative f => (Int -> a -> f b) -> Path a -> f (Path b)

-- | Convert a <a>Path</a> to a list of <tt>(ID, value)</tt> pairs.
toList :: Path a -> [(Int, a)]

-- | Build a <a>Path</a> from a list of <tt>(ID, value)</tt> pairs.
fromList :: [(Int, a)] -> Path a

-- | <i>O(1)</i> Compare to see if two trees have the same leaf key
(~=) :: Path a -> Path b -> Bool
infix 4 ~=
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
--   <i>O(log h)</i> by compressing the spine of the paths using a
--   skew-binary random access list.
--   
--   This library implements the technique described in my talk
--   
--   
--   <a>http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search</a>
--   
--   to improve the known asymptotic bounds on both online lowest common
--   ancestor search
--   
--   <a>http://en.wikipedia.org/wiki/Lowest_common_ancestor</a>
--   
--   and the online level ancestor problem:
--   
--   <a>http://en.wikipedia.org/wiki/Level_ancestor_problem</a>
--   
--   Algorithms used here assume that the key values chosen for <tt>k</tt>
--   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 <a>Path</a> as a skew binary random access list
data Path a

-- | Convert a <a>Path</a> to a list of <tt>(ID, value)</tt> pairs.
toList :: Path a -> [(Int, a)]

-- | Build a <a>Path</a> from a list of <tt>(ID, value)</tt> pairs.
fromList :: Monoid a => [(Int, a)] -> Path a

-- | <i>O(n)</i> Re-annotate a <a>Path</a> full of monoidal values using a
--   different <a>Monoid</a>.
map :: Monoid b => (a -> b) -> Path a -> Path b

-- | <i>O(n)</i> Re-annotate a <a>Path</a> full of monoidal values/
--   
--   Unlike <a>map</a>, <tt><a>mapHom</a> f</tt> assumes that <tt>f</tt> is
--   a <a>Monoid</a> homomorphism, that is to say you must ensure
--   
--   <pre>
--   f a `<tt>mappend'</tt> f b = f (a `<tt>mappend'</tt> b)
--   f <a>mempty</a> = <a>mempty</a>
--   </pre>
mapHom :: (a -> b) -> Path a -> Path b

-- | <i>O(n)</i> Re-annotate a <a>Path</a> full of monoidal values with
--   access to the key.
mapWithKey :: Monoid b => (Int -> a -> b) -> Path a -> Path b

-- | Traverse a <a>Path</a> yielding a new monoidal annotation.
traverse :: (Applicative f, Monoid b) => (a -> f b) -> Path a -> f (Path b)

-- | Traverse a <a>Path</a> with access to the node IDs.
traverseWithKey :: (Applicative f, Monoid b) => (Int -> a -> f b) -> Path a -> f (Path b)

-- | The empty <a>Path</a>
empty :: Path a

-- | <i>O(1)</i> Invariant: most operations assume that the keys <tt>k</tt>
--   are globally unique
--   
--   Extend the <a>Path</a> with a new node ID and value.
cons :: Monoid a => Int -> a -> Path a -> Path a

-- | <i>O(1)</i> Extract the node ID and value from the newest node on the
--   <a>Path</a>.
uncons :: Monoid a => Path a -> Maybe (Int, a, Path a)

-- | <i>O(1)</i> Extract the node ID and value from the newest node on the
--   <a>Path</a>, slightly faster than <a>uncons</a>.
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 => t a -> Bool

-- | Returns the size/length of a finite structure as an <a>Int</a>. 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 => t a -> Int

-- | Extract a monoidal summary of a <a>Path</a>.
measure :: Monoid a => Path a -> a

-- | <i>O(log h)</i> <tt>xs `<tt>isAncestorOf'</tt> ys</tt> holds when
--   <tt>xs</tt> is a prefix starting at the root of path <tt>ys</tt>.
isAncestorOf :: Monoid b => Path a -> Path b -> Bool

-- | <i>O(log (h - k))</i> to <tt><a>keep</a> k</tt> elements of
--   <a>Path</a> of <a>length</a> <tt>h</tt>
--   
--   This solves the online version of the "level ancestor problem" with no
--   preprocessing in <i>O(log h)</i> time, improving known complexity
--   bounds.
--   
--   <a>http://en.wikipedia.org/wiki/Level_ancestor_problem</a>
keep :: Monoid a => Int -> Path a -> Path a

-- | <i>O(log (h - k))</i> to keep <tt>k</tt> elements of <a>Path</a> of
--   <a>length</a> <tt>h</tt>, 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)

-- | <i>O(log k)</i> to <tt><a>drop</a> k</tt> elements from a <a>Path</a>
drop :: Monoid a => Int -> Path a -> Path a

-- | <i>O(log k)</i> to drop <tt>k</tt> elements from a <a>Path</a> 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)

-- | <i>O(1)</i> Compare to see if two trees have the same leaf key
(~=) :: Path a -> Path b -> Bool
infix 4 ~=

-- | <i>O(log h)</i> Compute the lowest common ancestor of two paths
lca :: (Monoid a, Monoid b) => Path a -> Path b -> Path a

-- | <i>O(log h)</i> 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.Path
instance Data.Foldable.Foldable Data.LCA.Online.Monoidal.Tree


-- | Provides online calculation of the the lowest common ancestor in
--   <i>O(log h)</i> by compressing the spine of a <a>Path</a> using a
--   skew-binary random access list.
--   
--   This library implements the technique described in my talk
--   
--   
--   <a>http://www.slideshare.net/ekmett/skewbinary-online-lowest-common-ancestor-search</a>
--   
--   to improve the known asymptotic bounds on both online lowest common
--   ancestor search
--   
--   <a>http://en.wikipedia.org/wiki/Lowest_common_ancestor</a>
--   
--   and the online level ancestor problem:
--   
--   <a>http://en.wikipedia.org/wiki/Level_ancestor_problem</a>
--   
--   Algorithms used here assume that the key values chosen for <tt>k</tt>
--   are globally unique.
module Data.LCA.Online

-- | Compressed paths using skew binary random access lists
data Path a

-- | <i>O(log h)</i> Compute the lowest common ancestor of two paths.
lca :: Path a -> Path b -> Path a

-- | The <a>empty</a> <a>Path</a>
empty :: Path a

-- | <i>O(1)</i> Invariant: most operations assume that the keys <tt>k</tt>
--   are globally unique
--   
--   Extend the <a>Path</a> with a new node ID and value.
cons :: Int -> a -> Path a -> Path a

-- | <i>O(1)</i> Extract the node ID and value from the newest node on the
--   <a>Path</a>.
uncons :: Path a -> Maybe (Int, a, Path a)

-- | <i>O(1)</i> Extract the node ID and value from the newest node on the
--   <a>Path</a>, slightly faster than <a>uncons</a>.
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 => t a -> Bool

-- | Returns the size/length of a finite structure as an <a>Int</a>. 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 => t a -> Int

-- | <i>O(log h)</i> <tt>xs <a>isAncestorOf</a> ys</tt> holds when
--   <tt>xs</tt> is a prefix starting at the root of <a>Path</a>
--   <tt>ys</tt>.
isAncestorOf :: Path a -> Path b -> Bool

-- | <i>O(log (h - k))</i> to <tt><a>keep</a> k</tt> elements of
--   <a>Path</a> of <a>length</a> <tt>h</tt>
--   
--   This solves the online version of the "level ancestor problem" with no
--   preprocessing in <i>O(log h)</i> time, improving known complexity
--   bounds.
--   
--   <a>http://en.wikipedia.org/wiki/Level_ancestor_problem</a>
keep :: Int -> Path a -> Path a

-- | <i>O(log k)</i> to <tt><a>drop</a> k</tt> elements from a <a>Path</a>
drop :: Int -> Path a -> Path a

-- | Traverse a <a>Path</a> with access to the node IDs.
traverseWithKey :: Applicative f => (Int -> a -> f b) -> Path a -> f (Path b)

-- | Convert a <a>Path</a> to a list of <tt>(ID, value)</tt> pairs.
toList :: Path a -> [(Int, a)]

-- | Build a <a>Path</a> from a list of <tt>(ID, value)</tt> pairs.
fromList :: [(Int, a)] -> Path a

-- | <i>O(1)</i> Compare to see if two trees have the same leaf key
(~=) :: Path a -> Path b -> Bool
infix 4 ~=
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.Path
instance Data.Foldable.Foldable Data.LCA.Online.Path
instance Data.Traversable.Traversable Data.LCA.Online.Path
instance GHC.Base.Functor Data.LCA.Online.Tree
instance Data.Foldable.Foldable Data.LCA.Online.Tree
instance Data.Traversable.Traversable Data.LCA.Online.Tree
