| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Data.Forest.Static
Contents
Description
A data structure for a static forest.
Synopsis
- data TreeOrder
- data Forest (p :: TreeOrder) v a where
- forestWith :: Vector v a => (forall a. [Tree a] -> [a]) -> [Tree a] -> Forest (p :: TreeOrder) v a
- forestPre :: Vector v a => [Tree a] -> Forest Pre v a
- forestPost :: Vector v a => [Tree a] -> Forest Post v a
- addIndices :: Int -> Tree a -> Tree (Int, a)
- addIndicesF :: Int -> [Tree a] -> [Tree (Int, a)]
- addIndicesF' :: Int -> [Tree a] -> [Tree Int]
- parentChildrenF :: Int -> [Tree (Int, a)] -> [Tree (Int, Int, [Int], a)]
- lrSiblingF :: [Tree (Int, a)] -> Map Int (Int, Int)
- lrSibling :: Tree (Int, a) -> Map Int (Int, Int)
- leftMostLeaves :: Forest p v a -> Vector Int
- leftMostLeaf :: Forest p v a -> Int -> Int
- rightMostLeaves :: Forest p v a -> Vector Int
- rightMostLeaf :: Forest p v a -> Int -> Int
- leftKeyRoots :: Forest Post v a -> Vector Int
- sortedSubForests :: Forest p v a -> [Vector Int]
- newtype Srt = Srt {}
- forestToTrees :: Forest p v a -> Forest a
- newtype QCTree a = QCTree {}
- test1 :: [Tree Char]
- test2 :: [Tree Char]
- runtest :: [Tree Char] -> IO ()
Documentation
Kind of possible TreeOrders.
TODO In for in-order traversal?
TODO Unordered for trees that have no sorted order?
data Forest (p :: TreeOrder) v a where Source #
A static forest structure. While traversals are always explicitly
possible by following the indices, the nodes themselves shall always be
ordered by the type p :: TreeOrder. This is not completely enforced,
given that Forest is exporting the constructor, but encouraged via
construction with helper functions. The labels of type a (in label)
require a vector structure v for O(1) access.
Constructors
| Forest | |
Fields
| |
forestWith :: Vector v a => (forall a. [Tree a] -> [a]) -> [Tree a] -> Forest (p :: TreeOrder) v a Source #
Construct a static Forest with a tree traversal function. I.e.
forestWith preorderF trees will construct a pre-order forest from the
list of trees.
Siblings span trees in the forest!
addIndices :: Int -> Tree a -> Tree (Int, a) Source #
Add pre-ordered (!) indices. First argument is the starting index.
addIndicesF :: Int -> [Tree a] -> [Tree (Int, a)] Source #
Add pre-ordered (!) indices, but to a forest.
addIndicesF' :: Int -> [Tree a] -> [Tree Int] Source #
Add pre-ordered (!) indices to a forest, but throw the label away as
well.
parentChildrenF :: Int -> [Tree (Int, a)] -> [Tree (Int, Int, [Int], a)] Source #
Add parent + children information. Yields
(Index,Parent,[Child],Label). Parent is -1 if root node.
lrSiblingF :: [Tree (Int, a)] -> Map Int (Int, Int) Source #
Return a map with all the nearest siblings for each node, for a forest.
lrSibling :: Tree (Int, a) -> Map Int (Int, Int) Source #
Return a map with all the nearest siblings for each node, for a tree.
rightMostLeaf :: Forest p v a -> Int -> Int Source #
Given a tree, and a node index, return the right-most leaf for the node.
leftKeyRoots :: Forest Post v a -> Vector Int Source #
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
sortedSubForests :: Forest p v a -> [Vector Int] Source #
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 newtype vectors that enforce size >= 1.
forestToTrees :: Forest p v a -> Forest a Source #
Given a forest, return the list of trees that constitue the forest.
QuickCheck
Wrapped quickcheck instance for Tree.