killer-trees

killer-trees

A collection of immutable data structures, providing a thin wrapper around the weight-balanced-tree package. These offer a more JavaScript-y, class-based API.

Gets/sets/deletes are O(log n) for List, Map, and Set.

List

import List from 'killer-trees/List';

let l = new List([1, 2, 3]);
l.at(1); // 2
l = l.push(4, 5);

Insertions and deletions at any index are also O(log n); no re-indexing needed!

List API.

Map

Map keys can be of any type.

// Import as `KtMap` to avoid conflicting with the `Map` built-in if needed.
import KtMap from 'killer-trees/Map';

let m = new KtMap([['a', 1], [{}, 2], [Symbol(), 3]]);
m.get('a'); // 1
m = m.set('a', 2);

Map API.

Record

Records have a fixed set of properties, defined with Record.define. They're stored more efficiently than maps and type-checked against a specific object type.

Records are currently implemented by storing values as an array, rather than a tree internally. That means gets are O(1), and sets/deletes are O(n), where n is the number of values in the record. Copying an array for small values of n is extremely fast and exhibits less GC pressure than updating a persistent tree.

import Record from 'killer-trees/Record';

type IPoint = {
  x: number,
  y: number,
};

const Point = Record.define<IPoint>({x: 0, y: 0});
let p = new Point({x: 10});
p.get('x'); // 10
p = p.set('x', 20);

Record API.

Set

Unlike the JavaScript Set built-in or Immutable.Set, killer-trees/Set stores values in a defined order. The order is determined by the compareValues static method, which can be overridden by subclassing Set. Sets can store values of any type.

// Import as `KtSet` to avoid conflicting with the `Set` built-in if needed.
import KtSet from 'killer-trees/Set';

new KtSet([1, {}, Symbol()]);

Note: killer-trees/Set's default compareValues method will sort most primitives (other than symbols) in a consistent order across realms and execution environments. Objects and symbols, however, will only be sorted consistently within the current realm and execution environment, and the order is not meaningful.

Set API.

Comparison with Immutable.js

Technical differences

• killer-trees is based on weight-balanced trees. Immutable.js is based on hash array mapped tries. These have different performance trade-offs. For example, HAMTs have better lookup performance, but trees perform better at concatenation, splicing, and order-preserving set operations. See the results under benchmark/.
• killer-trees's Set is explicitly ordered, and the value comparison logic can be customized by subclassing and overriding the compareValues method.

Superficial differences

• While TypeScript definitions are also provided and maintained, Flow support is prioritized here.
• killer-trees provides a class-based API (new List()), whereas Immutable.js uses factory functions (Immutable.List()).
• killer-trees is a lightweight wrapper around weight-balanced-tree. Immutable.js is a larger and more feature-rich library.

License

MIT