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


-- | A tree used to merge and maintain paths
--   
--   This package contains two modules: <a>Data.LCRSTree</a> and
--   <a>Data.PathTree</a>.
--   
--   A <a>PathTree</a> is a tree used to build unified paths from some
--   node. This means being able to merge multiple paths, that may overlap
--   at the root, in a sensible way. The module comes with a set of
--   functions to add paths.
--   
--   A Left-Children-Right-Siblings tree (<a>LCRSTree</a>) is a tree that
--   represents a multi-way tree (aka, a Rose Tree) in a binary-tree
--   format. It is the underlying implementation of <a>PathTree</a>.
--   
--   
--   <a>https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree</a>
@package PathTree
@version 0.1.1.0


module Data.LCRSTree

-- | A Left-child-right-sibling tree.
--   <a>https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree</a>
data LCRSTree n
Empty :: LCRSTree n
Leaf :: n -> (LCRSTree n) -> LCRSTree n
Node :: n -> (LCRSTree n) -> (LCRSTree n) -> LCRSTree n

-- | Functor instance

-- | Return the depth of the tree. This means the depth of the longest
--   branch
lcrsDepth :: Integral i => LCRSTree n -> i

-- | Convert a <a>Tree</a> into a <a>LCRSTree</a>
fromRoseTree :: Tree n -> LCRSTree n

-- | Convert a <a>LCRSTree</a> into a <a>Tree</a>
--   
--   This function fails if a non-top <a>Node</a> is passed. A non-top node
--   is a node <tt>Node n c s</tt> where <tt>s /= Empty</tt>.
toRoseTree :: LCRSTree n -> Tree n
instance GHC.Classes.Eq n => GHC.Classes.Eq (Data.LCRSTree.LCRSTree n)
instance GHC.Show.Show n => GHC.Show.Show (Data.LCRSTree.LCRSTree n)
instance GHC.Base.Functor Data.LCRSTree.LCRSTree
instance Data.Foldable.Foldable Data.LCRSTree.LCRSTree


-- | This module implements multiple functions using a <a>LCRSTree</a> to
--   create a tree where the mode of insertion are paths.
module Data.PathTree

-- | A path tree is simply a <a>LCRSTree</a>
type PathTree n = LCRSTree n

-- | A Left-child-right-sibling tree.
--   <a>https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree</a>
data LCRSTree n
Empty :: LCRSTree n
Leaf :: n -> (LCRSTree n) -> LCRSTree n
Node :: n -> (LCRSTree n) -> (LCRSTree n) -> LCRSTree n

-- | Insert a value <i>a</i> into the path <i>[n]</i> into a tree.
insert :: (Eq n) => [n] -> PathTree n -> PathTree n

-- | Like <a>insert</a>, but will use <i>f</i> to decide what to do if an
--   existing value already exists at the path.
insertWith :: (Eq n) => (n -> n -> n) -> [n] -> PathTree n -> PathTree n

-- | Like <a>insert</a>, but replaces the value at the path. May seem odd
--   to replace a value that is equal to itself, but this can be used with
--   partially-equal types for some flexibility.
insertReplace :: (Eq n) => [n] -> PathTree n -> PathTree n

-- | Given a single path, create a tree from it.
fromPath :: [n] -> PathTree n

-- | Like <a>fromPath</a>, but for multiple paths.
fromPaths :: Eq n => [[n]] -> PathTree n

-- | Like <a>fromPaths</a> but applies <i>f</i> if a give path already
--   exists.
fromPathsWith :: Eq n => (n -> n -> n) -> [[n]] -> PathTree n

-- | Like <a>fromPaths</a> but if two equal paths are passed, the former
--   one will be replaced.
fromPathsReplace :: Eq n => [[n]] -> PathTree n

-- | Returns all paths from the root node(s). Note that <tt>toPaths .
--   fromPaths</tt> may NOT return the same tree back due to some
--   reordering of siblings.
toPaths :: PathTree n -> [[n]]

-- | Given a path, determine if it exists fully. For a path to "exists
--   fully" means that it ends on a level that contains a leaf.
pathExists :: Eq n => [n] -> LCRSTree n -> Bool