-- 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 O(1) -- access to individual nodes, children, and siblings. @package ForestStructures @version 0.0.1.1 -- | A data structure for a static forest. module Data.Forest.Static -- | Kind of possible TreeOrders. -- -- TODO In for in-order traversal? -- -- TODO Unordered 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 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. data Forest (p :: TreeOrder) v a Forest :: !v a -> !Vector Int -> !Vector (Vector Int) -> !Vector Int -> !Vector Int -> !Vector Int -> Forest (p :: TreeOrder) v a -- | Each node k in [0..n-1] has a label at label ! -- k. [label] :: Forest (p :: TreeOrder) v a -> !v a -- | Each node k has a parent node, or -1 if there is no -- such parent. [parent] :: Forest (p :: TreeOrder) v a -> !Vector Int -- | Each node k has a vector of indices for its children. For -- leaf nodes, the vector is empty. [children] :: Forest (p :: TreeOrder) v a -> !Vector (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. [lsib] :: Forest (p :: TreeOrder) v a -> !Vector Int -- | The right sibling for a node k. [rsib] :: Forest (p :: TreeOrder) v a -> !Vector Int -- | The roots of the individual trees, the forest was constructed from. [roots] :: Forest (p :: TreeOrder) v a -> !Vector Int -- | 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! 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 pre-ordered (!) indices. First argument is the -- starting index. addIndices :: Int -> Tree a -> Tree (Int, a) -- | Add pre-ordered (!) indices, but to a forest. addIndicesF :: Int -> [Tree a] -> [Tree (Int, a)] -- | Add pre-ordered (!) indices to a forest, but throw -- the label away as well. addIndicesF' :: Int -> [Tree a] -> [Tree Int] -- | Add parent + children information. Yields -- (Index,Parent,[Child],Label). Parent is -1 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 newtype vectors that enforce size -- >= 1. 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 :: Vector v a => Forest p v a -> Forest a -- | Wrapped quickcheck instance for Tree. newtype QCTree a QCTree :: Tree a -> QCTree a [getTree] :: QCTree a -> Tree a instance GHC.Generics.Generic (Data.Forest.Static.Forest p v a) instance GHC.Show.Show (v a) => GHC.Show.Show (Data.Forest.Static.Forest p v a) instance GHC.Read.Read (v a) => GHC.Read.Read (Data.Forest.Static.Forest p v a) instance GHC.Classes.Ord (v a) => GHC.Classes.Ord (Data.Forest.Static.Forest p v a) instance GHC.Classes.Eq (v a) => GHC.Classes.Eq (Data.Forest.Static.Forest p v 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 (Data.Forest.Static.QCTree a) instance Test.QuickCheck.Arbitrary.Arbitrary a => Test.QuickCheck.Arbitrary.Arbitrary (Data.Forest.Static.QCTree a) instance GHC.Classes.Ord Data.Forest.Static.Srt instance Control.DeepSeq.NFData (v a) => Control.DeepSeq.NFData (Data.Forest.Static.Forest p v a) instance Data.Aeson.Types.ToJSON.ToJSON (v a) => Data.Aeson.Types.ToJSON.ToJSON (Data.Forest.Static.Forest p v a) instance Data.Aeson.Types.FromJSON.FromJSON (v a) => Data.Aeson.Types.FromJSON.FromJSON (Data.Forest.Static.Forest p v a) -- | A semi-specialized forest structure with the following atomic -- elements: (i) unstructured regions of type a, (ii) binary -- paired regions of type (b,b) with a recursing tree (or -- insertion between the two b's), (iii) juxtaposition of two -- elements, and (iv) an empty structure. module Data.Forest.StructuredPaired -- | A structured forest. data SPForest r t -- | An (unstructured) region with the structured forest. In case -- r forms a monoid SPJ (SPR a) (SPR b) equiv SPR -- (a<>b) should hold. SPR :: r -> SPForest r t -- | A tree within the forest brackets the forest on the left and right -- side with elements of type t. SPT :: t -> SPForest r t -> t -> SPForest r t -- | Juxtaposition of two forests. This allows for simple concatenation of -- forests. In particular, there is no particular position, while lists -- prefer x:xs vs xs++[x]. SPJ :: [SPForest r t] -> SPForest r t -- | An empty forest. SPJ SPE SPE equiv SPE should hold. SPE :: SPForest r t _SPE :: forall r_alxs t_alxt. Prism' (SPForest r_alxs t_alxt) () _SPJ :: forall r_alxs t_alxt. Prism' (SPForest r_alxs t_alxt) [SPForest r_alxs t_alxt] _SPT :: forall r_alxs t_alxt. Prism' (SPForest r_alxs t_alxt) (t_alxt, SPForest r_alxs t_alxt, t_alxt) _SPR :: forall r_alxs t_alxt. Prism' (SPForest r_alxs t_alxt) r_alxs -- | Structured Forests can be transformed into static forests. -- -- TODO types involved! toStaticForest :: SPForest r t -> Forest p v a instance GHC.Base.Functor (Data.Forest.StructuredPaired.SPForest r) instance Data.Foldable.Foldable (Data.Forest.StructuredPaired.SPForest r) instance Data.Traversable.Traversable (Data.Forest.StructuredPaired.SPForest r) instance Data.Bifunctor.Bifunctor Data.Forest.StructuredPaired.SPForest instance Data.Bifoldable.Bifoldable Data.Forest.StructuredPaired.SPForest instance Data.Bitraversable.Bitraversable Data.Forest.StructuredPaired.SPForest instance GHC.Generics.Generic (Data.Forest.StructuredPaired.SPForest r t) instance (GHC.Classes.Ord r, GHC.Classes.Ord t) => GHC.Classes.Ord (Data.Forest.StructuredPaired.SPForest r t) instance (GHC.Classes.Eq r, GHC.Classes.Eq t) => GHC.Classes.Eq (Data.Forest.StructuredPaired.SPForest r t) instance (GHC.Show.Show r, GHC.Show.Show t) => GHC.Show.Show (Data.Forest.StructuredPaired.SPForest r t) instance (GHC.Read.Read r, GHC.Read.Read t) => GHC.Read.Read (Data.Forest.StructuredPaired.SPForest r t)