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
earthstar-project/range-reconcile
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; }
private
findGteNode(value: ValueType): 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,

getLowestValue(): ValueType

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.