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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 | 1x 1x 1x 1x 1x 100x 100x 100x 100x 100x 100x 1x 17x 17x 17x 7x 7x 10x 14x 13x 13x 10x 10x 1x 91x 91x 91x 91x 91x 91x 91x 91x 91x 1x 44x 44x 44x 44x 44x 44x 44x 44x | import * as Tree from '#tree'
import {append, isNonEmptyArray, type NonEmptyArray} from '#Array'
import {K} from '#Function'
import {HKT, Option, pipe, Struct} from 'effect'
/**
* A zipper encodes a location with a tree, allowing for efficient navigation
* @typeParam A The underlying type of the tree.
* and update of immutable trees.
* @category zipper
*/
export interface Zipper<A> extends ZipperLevel<A> {
/** Tree node that is the current focus. */
focus: Tree.Tree<A>
/**
* Everything required to rebuild all levels of the tree _above_ this one.
* At the root level of a tree this array will be empty, when focused
* on any of the children of the root node it will hold a single level,
* and so on. The number of levels found is the depth of the zipper.
*/
levels: ZipperLevel<A>[]
}
/**
* Everything required to rebuild a level of the tree and all below it.
* To recreate the level we add the focus node between the `lefts` and the
* `rights` then add this forest to the parent value to get a tree.
* @typeParam A The underlying type of the tree.
* @category zipper
*/
export interface ZipperLevel<A> {
/** All children of the parent that are _to the left_ of the focus node. */
lefts: Tree.Tree<A>[]
/** All children of the parent that are _to the right_ of the focus node. */
rights: Tree.Tree<A>[]
/**
* Parent node _value_ of the focus node at the level we are encoding. All
* nodes have a parent except the root node.
*/
parent: Option.Option<A>
}
/**
* Create a new zipper focused on the root node of the given tree.
* @typeParam A The underlying type of the tree.
* @param focus The tree at the focus of the new zipper.
* @returns A new zipper focused on the given tree root node.
* @category zipper
*/
export const fromTree = <A>(focus: Tree.Tree<A>): Zipper<A> => ({
focus,
levels: [],
lefts: [],
rights: [],
parent: Option.none(),
})
/**
* Convert a zipper back into a tree.
* @typeParam A The underlying type of the tree.
* @param zipper The zipper that will be converted into a tree.
* @returns The tree encoded by the zipper.
* @category zipper
* @function
*/
export const toTree = <A>(zipper: Zipper<A>): Tree.Tree<A> => {
const {focus, levels} = zipper
const bottom: Tree.Tree<A> = fromLevel(focus, zipper)
if (!isNonEmptyArray(levels)) {
return bottom
}
let current: Tree.Tree<A> = bottom
for (let i = levels.length; i--; i >= 0) {
current = fromLevel(current, levels[i] as ZipperLevel<A>)
}
return current
}
/**
* Type lambda for the `Zipper<A>` type.
* `Kind<ZipperTypeLambda, never, unknown, unknown, A> ≡ Zipper<A>`
* @category zipper
*/
export interface ZipperTypeLambda extends HKT.TypeLambda {
readonly type: Zipper<this['Target']>
}
/**
* Type lambda for the `ZipperLevel<A>` type.
* `Kind<ZipperLevelTypeLambda, never, unknown, unknown, A> ≡ ZipperLevel<A>`
* @category zipper
*/
export interface ZipperLevelTypeLambda extends HKT.TypeLambda {
readonly type: ZipperLevel<this['Target']>
}
/**
* Type of function that takes a zipper and returns an option of a zipper.
* See {@link OptionalZipperOf} for a version that fixes the type parameter.
* @category zipper
*/
export interface OptionalZipper {
<A>(zipper: Zipper<A>): Option.Option<Zipper<A>>
}
/**
* Just like {@link OptionalZipper} except the type parameter `A` is fixed.
* @category zipper
*/
export interface OptionalZipperOf<A> {
(zipper: Zipper<A>): Option.Option<Zipper<A>>
}
/**
* Extract the underlying type `A` of the zipper.
* @category zipper
*/
export type ZipperType<Z extends Zipper<any>> =
Z extends Zipper<infer A> ? A : never
/**
* Push the zipper itself into its own level stack.
* Helpful when navigating _down_.
* @category internal
*/
export function pushSelf<A>(zipper: Zipper<A>): {
levels: NonEmptyArray<ZipperLevel<A>>
parent: Option.Option<A>
} {
return {
parent: pipe(zipper.focus, Tree.getValue, Option.some),
levels: append(
zipper.levels,
Struct.pick(zipper, 'lefts', 'rights', 'parent'),
),
}
}
/**
* Rebuild a level of the tree.
* @category internal
*/
export function fromLevel<A>(
focus: Tree.Tree<A>,
{lefts, rights, parent}: ZipperLevel<A>,
): Tree.Tree<A> {
return Option.match(parent, {
onNone: K(focus),
onSome: parent => Tree.tree(parent, [...lefts, focus, ...rights]),
})
}
|