import { FingerprintTree } from "https://deno.land/x/range_reconcile@0.1.0/src/fingerprint_tree/fingerprint_tree.ts";
A self-balancing tree which can return fingerprints for ranges of items it holds using a provided monoid.
Constructors
new
FingerprintTree(monoid: LiftingMonoid<ValueType, LiftedType>, compare: (a: ValueType, b: ValueType) => number)Properties
protected
root: NodeType<ValueType, LiftedType> | nullmonoid: LiftingMonoid<ValueType, [LiftedType, [number, ValueType[]]]>
Methods
private
aggregateDown(node: NodeType<ValueType, LiftedType> | null,
y: ValueType,
acc: CombinedLabel<ValueType, LiftedType>,
private
aggregateUntil(): { label: CombinedLabel<ValueType, LiftedType>; nextTree: NodeType<ValueType, LiftedType> | null; }private
aggregateUp(): { label: CombinedLabel<ValueType, LiftedType>; nextTree: NodeType<ValueType, LiftedType> | null; }private
findGteNode(value: ValueType): NodeType<ValueType, LiftedType> | nullFind the first node holding a value greater than or equal to the given value.
private
insertFingerprintNode(value: ValueType): NodeType<ValueType, LiftedType> | nullgetFingerprint(): { fingerprint: LiftedType; size: number; items: ValueType[]; nextTree: NodeType<ValueType, LiftedType> | null; }
Calculates a fingerprint of items within the given range, inclusive of xx and exclusive of y. Also returns the size of the range, the items contained within it,
Return the lowest value within this tree. Useful for constructing the maximum range of the tree, which will be [x, x) where x is the result of this function.
Insert a value into the tree. Will create a lifted value for the resulting node, and update the labels of all rotated and parent nodes in the tree.
removeFixup(parent: NodeType<ValueType, LiftedType> | null, current: NodeType<ValueType, LiftedType> | null)
rotateNode(node: NodeType<ValueType, LiftedType>, direction: Direction)