Skip to main content
Module

x/earthstar/deps.ts>FingerprintTree

Earthstar is a tool for private, undiscoverable, offline-first networks.
earthstar-project/earthstar
Go to Latest
class FingerprintTree
extends RedBlackTree<ValueType>
Re-export
import { FingerprintTree } from "https://deno.land/x/earthstar@v10.0.0/deps.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

protected
root: NodeType<ValueType, LiftedType> | null
monoid: LiftingMonoid<ValueType, [LiftedType, [number, ValueType[]]]>

Methods

private
aggregateDown(
node: NodeType<ValueType, LiftedType> | null,
acc: CombinedLabel<ValueType, LiftedType>,
): { label: CombinedLabel<ValueType, LiftedType>; nextTree: NodeType<ValueType, LiftedType> | null; }
private
aggregateUntil(
node: NodeType<ValueType, LiftedType>,
): { label: CombinedLabel<ValueType, LiftedType>; nextTree: NodeType<ValueType, LiftedType> | null; }
private
aggregateUp(
node: NodeType<ValueType, LiftedType>,
): { 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.

private
insertFingerprintNode(value: ValueType): NodeType<ValueType, LiftedType> | null
getFingerprint(
nextTree?: NodeType<ValueType, LiftedType>,
): { 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.

removeFixup(parent: NodeType<ValueType, LiftedType> | null, current: NodeType<ValueType, LiftedType> | null)
rotateNode(node: NodeType<ValueType, LiftedType>, direction: Direction)