weight-balanced-tree

A persistent
weight-balanced (bounded balance)
tree for JavaScript.

WBTs can be used to implement persistent maps or sets, where the entries have
a defined order. Indexed access is also O(log n) due to the fact that
indices can be located using the size stored on each node; therefore
they're also a viable option for implementing persistent lists if you don't
need O(1) reads or writes at the head or tail of the list.

* Zero dependencies
* Trees are plain objects
* Works in Node.js and the browser
* Flow and TypeScript definitions included

Installation

This software is released under the
MIT license.

It's published on npm as weight-balanced-tree,

``sh
npm install weight-balanced-tree

or using yarn


yarn add weight-balanced-tree
`

`TypeScript
import * as tree from 'weight-balanced-tree';

// or import functions directly
import insert from 'weight-balanced-tree/insert';
`

API

All API functions are pure and side‑effect free; the tree structure is
treated as immutable and a structurally‑shared copy is returned when
modifications are required.

Many functions of this library require a comparator cmp, which
defines the ordering of the tree. It works in the
same way as the comparator passed to Array.prototype.sort.
Obviously, the comparator should be idempotent and behave consistently for a
particular tree, otherwise the tree can become invalid.

$3

`TypeScript
const empty: EmptyImmutableTree;
`

The empty tree.

Note: The correct way to check if a tree is empty is with tree.size === 0.
The empty object reference won't be consistent across realms or in cases
where a tree is parsed from JSON.

$3

`TypeScript
function create(value: T): ImmutableTree;
`

Creates a tree of size 1 containing value.

$3

`TypeScript
function fromDistinctAscArray(
array: $ReadOnlyArray,
): ImmutableTree;
`

Constructs a new weight-balanced tree from array. array must be sorted
and contain only distinct values. (This is faster than building the tree one
value at a time with insert().)

fromDistinctAscArray will create an invalid tree if array is not
sorted or contains duplicate values. You can check if a tree is valid using
validate().

$3

`TypeScript
type InsertConflictHandler =
(existingTreeValue: T, key: K) => T;

type InsertNotFoundHandler =
(key: K) => T;

type UpdateOptions = {
key: K,
cmp: (key: K, treeValue: T) => number,
isEqual?: (a: T, b: T) => boolean,
onConflict: InsertConflictHandler,
onNotFound: InsertNotFoundHandler,
};

function update(
tree: ImmutableTree,
options: UpdateOptions,
): ImmutableTree;
`

A flexible primitive that can insert, replace, and even remove values in
tree.

key is located using the comparator cmp, which receives the same key
as its first argument, and a value of type T from tree as its second
argument.

* If key exists, onConflict is expected to return a final value to
live at that position. It receives the existing tree value as its first
argument, and key as its second argument.

The returned value must have the same relative position in the tree as
before, otherwise a ValueOrderError is thrown.

If you return existingTreeValue from onConflict, update will
return the same tree reference back. Object.is is used to determine
value equality.

There are several predefined exports in
weight-balanced-tree/update
that can be used for onConflict:

* onConflictThrowError, which throws ValueExistsError.
* onConflictKeepTreeValue, which returns the existing tree value.
* onConflictUseGivenValue, which returns key. (This is only usable
in cases where K is a subtype of T.)
* onConflictRemoveValue, which causes update to remove the value
stored at key from tree.

* If key doesn't exist, onNotFound is invoked to lazily create or
reject the missing value. It only receives one argument: the key passed
to update. Like onConflict, it's expected to return a value to be
inserted or to throw an error.

The following predefined exports in weight-balanced-tree/update can be
used for onNotFound:

* onNotFoundUseGivenValue, which returns key. (This is only usable
in cases where K is a subtype of T.)
* onNotFoundDoNothing, which causes update to perform no insertion
and to return the same tree reference back.
* onNotFoundThrowError, which throws a ValueNotFoundError.

K and T can be different types. That's convenient when using the tree
as a map:

`TypeScript
const cmp = (key1, [key2]) => key1 - key2;

// key = 1, value = 0
let node = tree.create([1, 0]);

// increments the value stored at key 1, or initializes it to 0
node = tree.update(node, {
key: 1,
cmp,
onConflict: ([, value], key) => [key, value + 1],
onNotFound: (key) => [key, 0],
});
`

And here's a "find or insert" implementation:

`TypeScript
interface Item {
readonly key: number;
readonly value: string;
}

function compareKeyWithItemKey(key: number, item: Item): number {
return key - item.key;
}

function findOrInsert(tree, key) {
let item;
const newTree = update(tree, {
key,
cmp: compareKeyWithItemKey,
onConflict: (existingItem: Item) => {
item = existingItem;
return existingItem;
},
onNotFound: (key: number) => {
item = {key, value: 'initialValue'};
return item;
},
});
return [newTree, item];
}
`

For simpler insertion semantics, see insert() below.

$3

`TypeScript
function insert(
tree: ImmutableTree,
value: T,
cmp: (T, T) => number,
onConflict?: InsertConflictHandler,
): NonEmptyImmutableTree;
`

Returns a new version of tree with value inserted. This is a more
specific version of update() that only operates on the value
type T.

cmp is the same as with update, except the first argument received
is the value you passed, and both arguments are of type T.

onConflict is also the same as with update, but here it defaults to
onConflictThrowError if not specified.

There are also some additional exports available that call insert with
different values of onConflict for you:

* insertIfNotExists (passes onConflictKeepTreeValue)
* insertOrReplaceIfExists (passes onConflictUseGivenValue)

insertOrThrowIfExists is an alias of insert.

$3

`TypeScript
function remove(
tree: ImmutableTree,
key: K,
cmp: (key: K, treeValue: T) => number,
): ImmutableTree;
`

Returns a new version of tree with the value located by key removed.

If key is not found in the tree, the same tree reference is returned
back.

If this was the last value in tree, empty is returned.

The cmp function works the same as with update(), with key
being passed as the first argument.

removeIfExists is an alias of remove.

$3

Like remove(), but throws an error if value does not exist
in the tree.

This simply checks if the tree returned from remove is the same
reference.

$3

`TypeScript
function equals(
a: ImmutableTree,
b: ImmutableTree,
isEqual?: (a: T, b: U) => boolean,
): boolean;
`

Returns true if two trees contain the same values in the same order, or
false otherwise.

This works by zipping the trees' values together, and passing each pair of
values to isEqual.

isEqual is optional. If not provided, it defaults to
Object.is.

$3

`TypeScript
function exists(
tree: ImmutableTree,
key: K,
cmp: (a: K, b: T) => number,
): boolean;
`

Returns true if a value matching key exists in tree, or false
otherwise.

This is a convenience function that just checks if findNode()
returns null.

$3

`TypeScript
function filter(
tree: ImmutableTree,
predicate: (value: T) => boolean,
): ImmutableTree;
`

Returns a tree containing only the values that satisfy predicate.

$3

`TypeScript
function find(
tree: ImmutableTree,
key: K,
cmp: (a: K, b: T) => number,
defaultValue: D,
): T | D;
`

Finds a value in tree using the given key and returns it, or
defaultValue if not found.

cmp receives key as its first argument, and a value of type T from
tree as its second argument.

$3

`TypeScript
function findAll(
tree: ImmutableTree,
key: K,
cmp: (a: K, b: T) => number,
): Generator;
`

Iterates over all values in tree found using the given key. This is useful
when cmp implements a left prefix of the comparator used to order tree.

`TypeScript
const cmp = (a, b) => a < b ? -1 : (a > b ? 1 : 0);

// The .value comparison is a left prefix of the tree comparator:
function compareValueAndIndex(a, b) {
return cmp(a.value, b.value) || cmp(a.index, b.index);
}

let node = tree.fromDistinctAscArray([
{value: 'A', index: 1},
{value: 'B', index: 1},
{value: 'C', index: 1},
]);
node = tree.insert(node, {value: 'B', index: 2}, compareValueAndIndex);
node = tree.insert(node, {value: 'B', index: 3}, compareValueAndIndex);

Array.from(
tree.findAll(node, 'B', (key, obj) => cmp(key, obj.value)),
); /* => Returns:
[
{value: 'B', index: 1},
{value: 'B', index: 2},
{value: 'B', index: 3},
] */
`

$3

`TypeScript
function findBy(
tree: ImmutableTree,
cmp: (treeValue: T) => number,
defaultValue: D,
): T | D;
`

Finds a value in tree and returns it, or defaultValue if not found.

cmp receives a value of type T from tree as its first argument.
This allows you to pass in a closure that compares treeValue against a
static key.

$3

`TypeScript
function findNext(
tree: ImmutableTree,
key: K,
cmp: (a: K, b: T) => number,
defaultValue: D,
): T | D;
`

Finds a value in tree using the given key and returns the value
immediately after it, or defaultValue if there is no such value.

key does not have to be found in the tree: if a set has 1 & 3, the next
value from 2 is 3.

findNode()

`TypeScript
function findNode(
tree: ImmutableTree,
key: K,
cmp: (a: K, b: T) => number,
): ImmutableTree | null;
`

This is similar to find(), but returns the entire tree node rather
than just the value.

$3

`TypeScript
function findPrev(
tree: ImmutableTree,
key: K,
cmp: (a: K, b: T) => number,
defaultValue: D,
): T | D;
`

Finds a value in tree using the given key and returns the value
immediately before it, or defaultValue if there is no such value.

key does not have to be found in the tree: if a set has 1 & 3, the previous
value from 2 is 1.

$3

`TypeScript
function findWithIndex(
tree: ImmutableTree,
key: K,
cmp: (a: K, b: T) => number,
defaultValue: D,
): [value: T | D, index: number];
`

Combines find() and indexOf(). Finds a value and its
position in tree using the given key, and returns them as a tuple.
Returns [defaultValue, -1] if not found.

$3

`TypeScript
function validate(
tree: ImmutableTree,
cmp: (a: T, b: T) => number,
): ValidateResult;
`

Returns a ValidateResult indicating whether the given tree is valid
for the comparator cmp: all left subtree values are less than the parent
value, and all right subtrees values are greater than the parent value.

$3

`TypeScript
function indexOf(
tree: ImmutableTree,
key: K,
cmp: (a: K, b: T) => number,
): number;
`

Returns the position of key in tree, or -1 if not found.

$3

`TypeScript
function at(
tree: ImmutableTree,
index: number,
defaultValue?: D,
): T | D;
`

Returns the value positioned at (0-based) index in tree. Negative indices
retrieve values from the end.

This is equivalent to toArray(tree).at(index), but doesn't create an
intermediary array, and locates index in O(log n).

An out-of-bounds index will return defaultValue (or undefined if not
specified).

$3

`TypeScript
function iterate(
tree: ImmutableTree,
start?: number,
end?: number,
): Generator;
`

Returns a JS iterator that traverses the values of the tree in order, optionally
starting from index start (inclusive) and ending at index end (exclusive).

Negative indices can be used for start and end:

`TypeScript
const tree = fromDistinctAscArray([1, 2, 3, 4, 5]);
Array.from(iterate(tree, -4, -1));
// [ 2, 3, 4 ]
`

$3

`TypeScript
function reverseIterate(
tree: ImmutableTree,
start?: number,
end?: number,
): Generator;
`

Returns a JS iterator that traverses the values of the tree in reverse order.

Don't be confused by start and end: they're the same as for iterate.
Think of it as taking a normal slice from start to end, and then
iterating that slice in reverse (so iteration begins at end - 1, got it?).

`TypeScript
const tree = fromDistinctAscArray([1, 2, 3, 4, 5]);

// both 2, 3, 4:
iterate(tree, 1, 4);
iterate(tree, -4, -1);

// both 4, 3, 2:
reverseIterate(tree, 1, 4);
reverseIterate(tree, -4, -1);
`

$3

`TypeScript
function map(tree: ImmutableTree, mapper: (T) => U): ImmutableTree;
`

Returns a new tree with every value passed through mapper.
The mapped values are assumed to have the same relative order as before.

`TypeScript
const numberTree = fromDistinctAscArray([1, 2, 3]);

const stringTree = map(
numberTree,
(num: number) => String(num),
);
`

$3

`TypeScript
function minNode(tree: ImmutableTree): NonEmptyImmutableTree;
`

Returns the "smallest" (left-most) node in tree.

$3

`TypeScript
function minValue(tree: ImmutableTree): T;
`

Returns the "smallest" (left-most) value in tree.

This is equivalent to minNode(tree).value.

$3

`TypeScript
function maxNode(tree: ImmutableTree): NonEmptyImmutableTree;
`

Returns the "largest" (right-most) node in tree.

$3

`TypeScript
function maxValue(tree: ImmutableTree): T;
`

Returns the "largest" (right-most) value in tree.

This is equivalent to maxNode(tree).value.

$3

`TypeScript
function setIndex(
tree: ImmutableTree,
index: number,
value: T,
): NonEmptyImmutableTree;
`

Returns a new version of tree with the value at position index replaced
by value.

Negative indices can be used to update values from the end of the tree. An
out-of-bounds index is a no-op and just returns tree.

If you replace a value with one that has a different relative order, the
tree will become invalid. However, if you're using the tree as a list, where
the index itself is the ordering, then this obviously isn't a concern.

If value is identical to the existing value at index (according to
Object.is), the same tree reference is returned back.

Time complexity: O(log n).

$3

`TypeScript
function updateIndex(
tree: ImmutableTree,
index: number,
updater: (existingTreeValue: T) => T,
): ImmutableTree;
`

This is the same as setIndex(tree, index, updater(at(tree, index))), but
avoids having to walk the tree twice.

$3

`TypeScript
function slice(
tree: ImmutableTree,
start?: number,
end?: number,
): ImmutableTree;
`

Has the same arguments as Array.prototype.slice.

Example:

`TypeScript
const tree = fromDistinctAscArray([1, 2, 3, 4, 5]);
const newTree = slice(tree, 1, 3);
// newTree: [2, 3]
`

Time complexity: O(log n).

$3

`TypeScript
function splice(
tree: ImmutableTree,
start: number,
deleteCount: number,
items: ImmutableTree
): {
readonly tree: ImmutableTree,
readonly deleted: ImmutableTree,
};
`

Has the same arguments as Array.prototype.splice.

Example:

`TypeScript
const tree = fromDistinctAscArray([1, 2, 3, 4, 5]);
const {tree: newTree, deleted} = splice(tree, 1, 2, fromDistinctAscArray([8, 9]));
// newTree: [1, 8, 9, 4, 5]
// deleted: [2, 3]
`

Time complexity: O(log n + m), where n is the size of tree
and m is the size of items.

$3

`TypeScript
function split(
tree: ImmutableTree,
key: K,
cmp: (a: K, b: T) => number,
): [
small: ImmutableTree,
equal: ImmutableTree,
large: ImmutableTree,
];
`

Splits a tree into two: one containing values smaller than key, and one
containing values large than key, according to cmp.

If key exists in the tree, equal will reference the node in tree
containing key; otherwise it will equal the empty tree.

$3

`TypeScript
function splitIndex(
tree: ImmutableTree,
index: number,
): [
small: ImmutableTree,
equal: ImmutableTree,
large: ImmutableTree,
];
`

This is similar to split(), but uses the position in the tree
rather than a key and comparator. Negative indices are not supported.

$3

`TypeScript
function splitLast(tree: NonEmptyImmutableTree): {
readonly tree: ImmutableTree;
readonly value: T;
};
`

Removes the last value from a non-empty tree, and returns an object
containing that value and the remaining tree.

Example:

`TypeScript
const node = fromDistinctAscArray([1, 2, 3]);
const {tree: newNode, value} = splitLast(node);
// newNode: [1, 2]
// value: 3
`

Time complexity: O(log n).

$3

`TypeScript
function splitFirst(tree: NonEmptyImmutableTree): {
readonly tree: ImmutableTree;
readonly value: T;
};
`

Removes the first value from a non-empty tree, and returns an object
containing that value and the remaining tree.

Example:

`TypeScript
const node = fromDistinctAscArray([1, 2, 3]);
const {tree: newNode, value} = splitFirst(node);
// newNode: [2, 3]
// value: 1
`

Time complexity: O(log n).

$3

`TypeScript
function toArray(
tree: ImmutableTree,
): Array;
`

Flattens tree into an array of values.

$3

`TypeScript
function union(
t1: ImmutableTree,
t2: ImmutableTree,
cmp: (a: T, b: T) => number,
combiner?: (v1: T, v2: T) => T,
): ImmutableTree;
`

Merges two trees together using the comparator cmp.

combiner handles the case where an equivalent value appears in both
trees, and is expected to return the final value to use in the union. If not
specified, by union will prefer values in t1. If you return a different
value, then the relative sort order must be preserved; otherwise
ValueOrderError is thrown.

$3

`TypeScript
function difference(
t1: ImmutableTree,
t2: ImmutableTree,
cmp: (a: T, b: T) => number,
): ImmutableTree;
`

Returns a new tree with values in t1 that aren't in t2, using the
comparator cmp.

$3

`TypeScript
function symmetricDifference(
t1: ImmutableTree,
t2: ImmutableTree,
cmp: (a: T, b: T) => number,
): ImmutableTree;
`

Returns a new tree with values that are in either t1 or t2, but not
in both, using the comparator cmp.

$3

`TypeScript
function intersection(
t1: ImmutableTree,
t2: ImmutableTree,
cmp: (a: T, b: T) => number,
combiner?: (v1: T, v2: T) => T,
): ImmutableTree;
`

Returns a new tree with values common to both t1 and t2, using the
comparator cmp.

combiner determines which value is chosen; by default it returns the value
from the first tree, t1. If you return a different value, then the
relative sort order must be preserved; otherwise ValueOrderError is thrown.

$3

`TypeScript
function isDisjointFrom(
tree: ImmutableTree,
other: ImmutableTree,
cmp: (a: T, b: T) => number,
): boolean;
`

Returns true if tree and other have no values in common, or false
otherwise.

$3

`TypeScript
function isSubsetOf(
tree: ImmutableTree,
other: ImmutableTree,
cmp: (a: T, b: T) => number,
): boolean;
`

Returns true if all values in tree are in other, or false otherwise.

$3

`TypeScript
function isSupersetOf(
tree: ImmutableTree,
other: ImmutableTree,
cmp: (a: T, b: T) => number,
): boolean;
`

Returns true if all values in other are in tree, or false otherwise.

$3

`TypeScript
function join(
left: ImmutableTree,
value: T,
right: ImmutableTree
): NonEmptyImmutableTree;
`

Implements the join operation.

This is a low-level operation, and the resulting tree is not checked for
validity.

$3

`TypeScript
function join2(
left: ImmutableTree,
right: ImmutableTree
): ImmutableTree;
`

Implements the join2 operation.

This is a low-level operation, and the resulting tree is not checked for
validity.

$3

`TypeScript
function zip(
t1: ImmutableTree,
t2: ImmutableTree,
): Generator<[T | void, U | void], void, void>;
`

Zips two trees together, returning an iterable of tuples: the first tuple
contains the first values of both trees, the second tuple contains the second
values of both trees, and so on. If the trees are of different sizes,
undefined is used within a tuple where a corresponding value is missing.

Performance

Performance will largely depend on the size of your data and the cost of your
comparator function. See the
benchmark/
folder for comparisons against Immutable.js
and mori.

Tests

`sh


Unit tests

./node_modules/.bin/c8 node --test test/index.js

Monkey tests

node --test test/monkey.js

TypeScript tests

./node_modules/.bin/tsd
``

Changelog

See CHANGELOG.md.

References

1. Adams, Stephen.
"Implementing Sets Efficiently in a Functional Language."
University of Southampton, n.d.
Accessed at http://groups.csail.mit.edu/mac/users/adams/BB/92-10.ps

2. GHC's Data.Map.Internal.

3. Join-based tree algorithms