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


-- | Tree- and forest structures
--   
--   This library provides both static and dynamic tree and forest
--   structures. Once a tree structure is static, it can be mappend onto a
--   linearized representation, which is beneficial for algorithms that do
--   not modify the internal tree structure, but need fast <tt>O(1)</tt>
--   access to individual nodes, children, and siblings.
@package ForestStructures
@version 0.0.0.2


-- | A data structure for a static forest.
module Data.Forest.Static

-- | Kind of possible <tt>TreeOrder</tt>s.
--   
--   TODO <tt>In</tt> for in-order traversal?
--   
--   TODO <tt>Unordered</tt> for trees that have no sorted order?
data TreeOrder
Pre :: TreeOrder
Post :: TreeOrder
Unordered :: TreeOrder

-- | A static forest structure. While traversals are always explicitly
--   possible by following the indices, the nodes themselves shall always
--   be ordered by the type <tt>p :: TreeOrder</tt>. This is not completely
--   enforced, given that <tt>Forest</tt> is exporting the constructor, but
--   encouraged via construction with helper functions. The labels of type
--   <tt>a</tt> (in <tt>label</tt>) require a vector structure <tt>v</tt>
--   for <tt>O(1)</tt> access.
data Forest (p :: TreeOrder) v a
[Forest] :: (Vector v a) => {label :: v a  Each node @k@ in @[0..n-1]@ has a label at @label ! k@., parent :: Vector Int  Each node @k@ has a parent node, or @-1@ if there is no such parent., children :: Vector (Vector Int)  Each node @k@ has a vector of indices for its children. For leaf nodes, the vector is empty., lsib :: Vector Int  The left sibling for a node @k@. Will *not* cross subtrees. I.e. if @k@ is @lsib@ of @l@, then @k@ and @l@ have the same parent., rsib :: Vector Int  The right sibling for a node @k@., roots :: Vector Int  The roots of the individual trees, the forest was constructed from.} -> Forest p v a

-- | Construct a static <a>Forest</a> with a tree traversal function. I.e.
--   <tt>forestWith preorderF trees</tt> will construct a pre-order forest
--   from the list of <tt>trees</tt>.
--   
--   Siblings span trees in the forest!
forestWith :: (Vector v a) => (forall a. [Tree a] -> [a]) -> [Tree a] -> Forest (p :: TreeOrder) v a

-- | Construct a pre-ordered forest.
forestPre :: (Vector v a) => [Tree a] -> Forest Pre v a

-- | Construct a post-ordered forest.
forestPost :: (Vector v a) => [Tree a] -> Forest Post v a

-- | Add <tt>pre-ordered</tt> <tt>(!)</tt> indices. First argument is the
--   starting index.
addIndices :: Int -> Tree a -> Tree (Int, a)

-- | Add <tt>pre-ordered</tt> <tt>(!)</tt> indices, but to a forest.
addIndicesF :: Int -> [Tree a] -> [Tree (Int, a)]

-- | Add <tt>pre-ordered</tt> <tt>(!)</tt> indices to a forest, but throw
--   the label away as well.
addIndicesF' :: Int -> [Tree a] -> [Tree Int]

-- | Add parent + children information. Yields
--   <tt>(Index,Parent,[Child],Label)</tt>. Parent is <tt>-1</tt> if root
--   node.
parentChildrenF :: Int -> [Tree (Int, a)] -> [Tree (Int, Int, [Int], a)]

-- | Return a map with all the nearest siblings for each node, for a
--   forest.
lrSiblingF :: [Tree (Int, a)] -> Map Int (Int, Int)

-- | Return a map with all the nearest siblings for each node, for a tree.
lrSibling :: Tree (Int, a) -> Map Int (Int, Int)

-- | Return the left-most leaf for each node.
leftMostLeaves :: Forest p v a -> Vector Int

-- | Just the leaf-most leaf for a certain node.
leftMostLeaf :: Forest p v a -> Int -> Int

-- | Return the right-most leaf for each node.
rightMostLeaves :: Forest p v a -> Vector Int

-- | Given a tree, and a node index, return the right-most leaf for the
--   node.
rightMostLeaf :: Forest p v a -> Int -> Int

-- | Return all left key roots. These are the nodes that have no (super-)
--   parent with the same left-most leaf.
--   
--   This function is somewhat specialized for tree editing.
--   
--   TODO group by
leftKeyRoots :: Forest Post v a -> Vector Int

-- | Returns the list of all sorted subsets of subforests in the forest. If
--   the forest is given in pre-order, then The subsets are returned in
--   reversed pre-order.
--   
--   TODO turn this into <tt>newtype vectors</tt> that enforce <tt>size
--   &gt;= 1</tt>.
sortedSubForests :: Forest p v a -> [Vector Int]
newtype Srt
Srt :: [Int] -> Srt
[unSrt] :: Srt -> [Int]

-- | Given a forest, return the list of trees that constitue the forest.
forestToTrees :: Forest p v a -> Forest a

-- | Wrapped quickcheck instance for <a>Tree</a>.
newtype QCTree a
QCTree :: Tree a -> QCTree a
[getTree] :: QCTree a -> Tree a
test1 :: [Tree Char]
test2 :: [Tree Char]
runtest :: [Tree Char] -> IO ()
instance GHC.Show.Show a => GHC.Show.Show (Data.Forest.Static.QCTree a)
instance GHC.Show.Show Data.Forest.Static.Srt
instance GHC.Classes.Eq Data.Forest.Static.Srt
instance (GHC.Show.Show a, GHC.Show.Show (v a)) => GHC.Show.Show (Data.Forest.Static.Forest p v a)
instance GHC.Classes.Ord Data.Forest.Static.Srt
instance Test.QuickCheck.Arbitrary.Arbitrary a => Test.QuickCheck.Arbitrary.Arbitrary (Data.Forest.Static.QCTree a)