| 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 :: Type -> Type) a = Forest {}
- forestWith :: forall (v :: Type -> Type) a (p :: TreeOrder). Vector v a => (forall a1. [Tree a1] -> [a1]) -> [Tree a] -> Forest p v a
- forestPre :: forall (v :: Type -> Type) a. Vector v a => [Tree a] -> Forest 'Pre v a
- forestPost :: forall (v :: Type -> Type) a. 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 :: forall (p :: TreeOrder) (v :: Type -> Type) a. Forest p v a -> Vector Int
- leftMostLeaf :: forall (p :: TreeOrder) (v :: Type -> Type) a. Forest p v a -> Int -> Int
- rightMostLeaves :: forall (p :: TreeOrder) (v :: Type -> Type) a. Forest p v a -> Vector Int
- rightMostLeaf :: forall (p :: TreeOrder) (v :: Type -> Type) a. Forest p v a -> Int -> Int
- leftKeyRoots :: forall (v :: Type -> Type) a. Forest 'Post v a -> Vector Int
- sortedSubForests :: forall (p :: TreeOrder) (v :: Type -> Type) a. Forest p v a -> [Vector Int]
- newtype Srt = Srt {}
- forestToTrees :: forall (v :: Type -> Type) a (p :: TreeOrder). Vector v a => Forest p v a -> Forest a
- newtype QCTree a = QCTree {}
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 :: Type -> Type) a 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
| |
Instances
forestWith :: forall (v :: Type -> Type) a (p :: TreeOrder). Vector v a => (forall a1. [Tree a1] -> [a1]) -> [Tree a] -> Forest p 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!
forestPre :: forall (v :: Type -> Type) a. Vector v a => [Tree a] -> Forest 'Pre v a Source #
Construct a pre-ordered forest.
forestPost :: forall (v :: Type -> Type) a. Vector v a => [Tree a] -> Forest 'Post v a Source #
Construct a post-ordered 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.
leftMostLeaves :: forall (p :: TreeOrder) (v :: Type -> Type) a. Forest p v a -> Vector Int Source #
Return the left-most leaf for each node.
leftMostLeaf :: forall (p :: TreeOrder) (v :: Type -> Type) a. Forest p v a -> Int -> Int Source #
Just the leaf-most leaf for a certain node.
rightMostLeaves :: forall (p :: TreeOrder) (v :: Type -> Type) a. Forest p v a -> Vector Int Source #
Return the right-most leaf for each node.
rightMostLeaf :: forall (p :: TreeOrder) (v :: Type -> Type) a. Forest p v a -> Int -> Int Source #
Given a tree, and a node index, return the right-most leaf for the node.
leftKeyRoots :: forall (v :: Type -> Type) a. 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 :: forall (p :: TreeOrder) (v :: Type -> Type) a. 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 :: forall (v :: Type -> Type) a (p :: TreeOrder). Vector v a => Forest p v a -> Forest a Source #
Given a forest, return the list of trees that constitue the forest.