Skip to main content
Deno 2 is finally here 🎉️
Learn more
Module

x/range_reconcile/mod.ts>FingerprintTree

Efficiently sync sets with range-based set reconciliation
Latest
class FingerprintTree
Re-export
import { FingerprintTree } from "https://deno.land/x/range_reconcile@1.0.2/mod.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)

Type Parameters

ValueType
LiftedType

Properties

private
cachedMinNode: NodeType<ValueType, LiftedType> | null
protected
root: NodeType<ValueType, LiftedType> | null

Methods

private
aggregateDown(
node: NodeType<ValueType, LiftedType> | null,
acc: CombinedLabel<ValueType, LiftedType>,
): { label: CombinedLabel<ValueType, LiftedType>; nextTree: NodeType<ValueType, LiftedType> | null; }
private
aggregateUntil(): { label: CombinedLabel<ValueType, LiftedType>; nextTree: NodeType<ValueType, LiftedType> | null; }
private
aggregateUp(): { label: CombinedLabel<ValueType, LiftedType>; nextTree: NodeType<ValueType, LiftedType> | null; }

Find the first node holding a value greater than or equal to the given value.

getFingerprint(): { 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(value: ValueType): boolean

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.

remove(value: ValueType): boolean

Remove a value frem the tree. Will recalculate labels for all rotated and parent nodes.