Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | 1x 1x 1x 1x 203x 1x 1x 1x 1x 102x 102x 102x 1x | import {
leaf,
tree,
treePara,
type ForestTypeLambda,
type Tree,
type TreeProductFolderK,
} from '#tree'
import * as TreeF from '#treeF'
import {Array, flow, pipe, Tuple} from 'effect'
import type {NonEmptyArray} from 'effect/Array'
/**
* The set of all bottom-grounded subtrees of a tree. This is the set
* of every subtree of the tree `T` that:
*
* 1. The subtree root is a node of `T`. Every node in `T` appears exactly
* once in its subtrees list as root node.
* 2. The leaves of the subtree are exactly the leaves reachable from its
* root node in the tree `T`. This makes it _bottom-grounded_.
*
* The number of such subtrees of a tree is the number of nodes in the tree.
*
* For example consider the tree:
*
* ```txt
* ┬root
* ├┬a
* │├─b
* │└─c
* └┬d
* ├─e
* └─f
* ```
* `bottomSubtrees` will return for this tree _seven_ trees, one per node:
*
* ```txt
* 1. ─b 4. ─e 7. ┬root
* ├┬a
* 2. ─c 5. ─f │├─b
* │└─c
* 3. ┬a 6. ┬d └┬d
* ├─b ├─e ├─e
* └─c └─f └─f
* ```
* @category ops
* @function
*/
export const bottomSubtrees = <A>(self: Tree<A>): NonEmptyArray<Tree<A>> =>
pipe(self, treePara(bottomSubtreesFold))
/**
* Collect all bottom-grounded subtrees of a single tree level.
* @category fold
* @function
*/
export const bottomSubtreesFold: TreeProductFolderK<ForestTypeLambda> =
TreeF.match({
onLeaf: flow(leaf, Array.of),
onBranch: (value, forest) => [
...pipe(forest, Array.map(Tuple.getSecond), Array.flatten),
pipe(forest, Array.map(Tuple.getFirst), tree.flipped(value)),
],
})
|