summaryrefslogtreecommitdiff
path: root/packages/idb-bridge/src/tree/b+tree.ts
diff options
context:
space:
mode:
Diffstat (limited to 'packages/idb-bridge/src/tree/b+tree.ts')
-rw-r--r--packages/idb-bridge/src/tree/b+tree.ts1070
1 files changed, 676 insertions, 394 deletions
diff --git a/packages/idb-bridge/src/tree/b+tree.ts b/packages/idb-bridge/src/tree/b+tree.ts
index 783c6b049..59a49baa3 100644
--- a/packages/idb-bridge/src/tree/b+tree.ts
+++ b/packages/idb-bridge/src/tree/b+tree.ts
@@ -24,14 +24,29 @@ SPDX-License-Identifier: MIT
// Original repository: https://github.com/qwertie/btree-typescript
-
-import { ISortedMap, ISortedMapF } from './interfaces';
+import { ISortedMap, ISortedMapF } from "./interfaces";
export {
- ISetSource, ISetSink, ISet, ISetF, ISortedSetSource, ISortedSet, ISortedSetF,
- IMapSource, IMapSink, IMap, IMapF, ISortedMapSource, ISortedMap, ISortedMapF
-} from './interfaces';
-
-export type EditRangeResult<V,R=number> = {value?:V, break?:R, delete?:boolean};
+ ISetSource,
+ ISetSink,
+ ISet,
+ ISetF,
+ ISortedSetSource,
+ ISortedSet,
+ ISortedSetF,
+ IMapSource,
+ IMapSink,
+ IMap,
+ IMapF,
+ ISortedMapSource,
+ ISortedMap,
+ ISortedMapF,
+} from "./interfaces";
+
+export type EditRangeResult<V, R = number> = {
+ value?: V;
+ break?: R;
+ delete?: boolean;
+};
type index = number;
@@ -57,7 +72,7 @@ type index = number;
// - V8 source (NewElementsCapacity in src/objects.h): arrays grow by 50% + 16 elements
/** Compares two numbers, strings, arrays of numbers/strings, Dates,
- * or objects that have a valueOf() method returning a number or string.
+ * or objects that have a valueOf() method returning a number or string.
* Optimized for numbers. Returns 1 if a>b, -1 if a<b, and 0 if a===b.
*/
export function defaultComparator(a: any, b: any) {
@@ -66,42 +81,42 @@ export function defaultComparator(a: any, b: any) {
// General case (c is NaN): string / arrays / Date / incomparable things
if (a) a = a.valueOf();
if (b) b = b.valueOf();
- return a < b ? -1 : a > b ? 1 : a == b ? 0 : c;
-};
+ return a < b ? -1 : a > b ? 1 : a == b ? 0 : c;
+}
/**
- * A reasonably fast collection of key-value pairs with a powerful API.
+ * A reasonably fast collection of key-value pairs with a powerful API.
* Largely compatible with the standard Map. BTree is a B+ tree data structure,
* so the collection is sorted by key.
- *
+ *
* B+ trees tend to use memory more efficiently than hashtables such as the
- * standard Map, especially when the collection contains a large number of
- * items. However, maintaining the sort order makes them modestly slower:
+ * standard Map, especially when the collection contains a large number of
+ * items. However, maintaining the sort order makes them modestly slower:
* O(log size) rather than O(1). This B+ tree implementation supports O(1)
* fast cloning. It also supports freeze(), which can be used to ensure that
* a BTree is not changed accidentally.
- *
+ *
* Confusingly, the ES6 Map.forEach(c) method calls c(value,key) instead of
* c(key,value), in contrast to other methods such as set() and entries()
- * which put the key first. I can only assume that the order was reversed on
+ * which put the key first. I can only assume that the order was reversed on
* the theory that users would usually want to examine values and ignore keys.
- * BTree's forEach() therefore works the same way, but a second method
+ * BTree's forEach() therefore works the same way, but a second method
* `.forEachPair((key,value)=>{...})` is provided which sends you the key
- * first and the value second; this method is slightly faster because it is
+ * first and the value second; this method is slightly faster because it is
* the "native" for-each method for this class.
- *
- * Out of the box, BTree supports keys that are numbers, strings, arrays of
- * numbers/strings, Date, and objects that have a valueOf() method returning a
+ *
+ * Out of the box, BTree supports keys that are numbers, strings, arrays of
+ * numbers/strings, Date, and objects that have a valueOf() method returning a
* number or string. Other data types, such as arrays of Date or custom
- * objects, require a custom comparator, which you must pass as the second
- * argument to the constructor (the first argument is an optional list of
+ * objects, require a custom comparator, which you must pass as the second
+ * argument to the constructor (the first argument is an optional list of
* initial items). Symbols cannot be used as keys because they are unordered
* (one Symbol is never "greater" or "less" than another).
- *
+ *
* @example
* Given a {name: string, age: number} object, you can create a tree sorted by
* name and then by age like this:
- *
+ *
* var tree = new BTree(undefined, (a, b) => {
* if (a.name > b.name)
* return 1; // Return a number >0 when a > b
@@ -110,36 +125,36 @@ export function defaultComparator(a: any, b: any) {
* else // names are equal (or incomparable)
* return a.age - b.age; // Return >0 when a.age > b.age
* });
- *
+ *
* tree.set({name:"Bill", age:17}, "happy");
* tree.set({name:"Fran", age:40}, "busy & stressed");
* tree.set({name:"Bill", age:55}, "recently laid off");
* tree.forEachPair((k, v) => {
* console.log(`Name: ${k.name} Age: ${k.age} Status: ${v}`);
* });
- *
+ *
* @description
* The "range" methods (`forEach, forRange, editRange`) will return the number
* of elements that were scanned. In addition, the callback can return {break:R}
* to stop early and return R from the outer function.
- *
+ *
* - TODO: Test performance of preallocating values array at max size
* - TODO: Add fast initialization when a sorted array is provided to constructor
- *
+ *
* For more documentation see https://github.com/qwertie/btree-typescript
*
- * Are you a C# developer? You might like the similar data structures I made for C#:
+ * Are you a C# developer? You might like the similar data structures I made for C#:
* BDictionary, BList, etc. See http://core.loyc.net/collections/
- *
+ *
* @author David Piepgrass
*/
-export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap<K,V>
-{
- private _root: BNode<K, V> = EmptyLeaf as BNode<K,V>;
+export default class BTree<K = any, V = any>
+ implements ISortedMapF<K, V>, ISortedMap<K, V> {
+ private _root: BNode<K, V> = EmptyLeaf as BNode<K, V>;
_size: number = 0;
_maxNodeSize: number;
- _compare: (a:K, b:K) => number;
-
+ _compare: (a: K, b: K) => number;
+
/**
* Initializes an empty B+ tree.
* @param compare Custom function to compare pairs of elements in the tree.
@@ -148,60 +163,78 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap
* @param maxNodeSize Branching factor (maximum items or children per node)
* Must be in range 4..256. If undefined or <4 then default is used; if >256 then 256.
*/
- public constructor(entries?: [K,V][], compare?: (a: K, b: K) => number, maxNodeSize?: number) {
+ public constructor(
+ entries?: [K, V][],
+ compare?: (a: K, b: K) => number,
+ maxNodeSize?: number,
+ ) {
this._maxNodeSize = maxNodeSize! >= 4 ? Math.min(maxNodeSize!, 256) : 32;
this._compare = compare || defaultComparator;
- if (entries)
- this.setPairs(entries);
+ if (entries) this.setPairs(entries);
}
-
+
// ES6 Map<K,V> methods ///////////////////////////////////////////////////
/** Gets the number of key-value pairs in the tree. */
- get size() { return this._size; }
+ get size() {
+ return this._size;
+ }
/** Gets the number of key-value pairs in the tree. */
- get length() { return this._size; }
+ get length() {
+ return this._size;
+ }
/** Returns true iff the tree contains no key-value pairs. */
- get isEmpty() { return this._size === 0; }
+ get isEmpty() {
+ return this._size === 0;
+ }
/** Releases the tree so that its size is 0. */
clear() {
- this._root = EmptyLeaf as BNode<K,V>;
+ this._root = EmptyLeaf as BNode<K, V>;
this._size = 0;
}
- forEach(callback: (v:V, k:K, tree:BTree<K,V>) => void, thisArg?: any): number;
+ forEach(
+ callback: (v: V, k: K, tree: BTree<K, V>) => void,
+ thisArg?: any,
+ ): number;
- /** Runs a function for each key-value pair, in order from smallest to
+ /** Runs a function for each key-value pair, in order from smallest to
* largest key. For compatibility with ES6 Map, the argument order to
- * the callback is backwards: value first, then key. Call forEachPair
+ * the callback is backwards: value first, then key. Call forEachPair
* instead to receive the key as the first argument.
* @param thisArg If provided, this parameter is assigned as the `this`
* value for each callback.
* @returns the number of values that were sent to the callback,
* or the R value if the callback returned {break:R}. */
- forEach<R=number>(callback: (v:V, k:K, tree:BTree<K,V>) => {break?:R}|void, thisArg?: any): R|number {
- if (thisArg !== undefined)
- callback = callback.bind(thisArg);
+ forEach<R = number>(
+ callback: (v: V, k: K, tree: BTree<K, V>) => { break?: R } | void,
+ thisArg?: any,
+ ): R | number {
+ if (thisArg !== undefined) callback = callback.bind(thisArg);
return this.forEachPair((k, v) => callback(v, k, this));
}
- /** Runs a function for each key-value pair, in order from smallest to
+ /** Runs a function for each key-value pair, in order from smallest to
* largest key. The callback can return {break:R} (where R is any value
* except undefined) to stop immediately and return R from forEachPair.
- * @param onFound A function that is called for each key-value pair. This
+ * @param onFound A function that is called for each key-value pair. This
* function can return {break:R} to stop early with result R.
- * The reason that you must return {break:R} instead of simply R
- * itself is for consistency with editRange(), which allows
+ * The reason that you must return {break:R} instead of simply R
+ * itself is for consistency with editRange(), which allows
* multiple actions, not just breaking.
- * @param initialCounter This is the value of the third argument of
- * `onFound` the first time it is called. The counter increases
+ * @param initialCounter This is the value of the third argument of
+ * `onFound` the first time it is called. The counter increases
* by one each time `onFound` is called. Default value: 0
* @returns the number of pairs sent to the callback (plus initialCounter,
* if you provided one). If the callback returned {break:R} then
* the R value is returned instead. */
- forEachPair<R=number>(callback: (k:K, v:V, counter:number) => {break?:R}|void, initialCounter?: number): R|number {
- var low = this.minKey(), high = this.maxKey();
+ forEachPair<R = number>(
+ callback: (k: K, v: V, counter: number) => { break?: R } | void,
+ initialCounter?: number,
+ ): R | number {
+ var low = this.minKey(),
+ high = this.maxKey();
return this.forRange(low!, high!, true, callback, initialCounter);
}
@@ -214,13 +247,13 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap
get(key: K, defaultValue?: V): V | undefined {
return this._root.get(key, defaultValue, this);
}
-
+
/**
* Adds or overwrites a key-value pair in the B+ tree.
* @param key the key is used to determine the sort order of
* data in the tree.
* @param value data to associate with the key (optional)
- * @param overwrite Whether to overwrite an existing key-value pair
+ * @param overwrite Whether to overwrite an existing key-value pair
* (default: true). If this is false and there is an existing
* key-value pair then this method has no effect.
* @returns true if a new key-value pair was added.
@@ -229,14 +262,12 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap
* as well as the value. This has no effect unless the new key
* has data that does not affect its sort order.
*/
- set(key: K, value: V, overwrite?: boolean): boolean {
- if (this._root.isShared)
- this._root = this._root.clone();
+ set(key: K, value: V, overwrite?: boolean): boolean {
+ if (this._root.isShared) this._root = this._root.clone();
var result = this._root.set(key, value, overwrite, this);
- if (result === true || result === false)
- return result;
+ if (result === true || result === false) return result;
// Root node has split, so create a new root node.
- this._root = new BNodeInternal<K,V>([this._root, result]);
+ this._root = new BNodeInternal<K, V>([this._root, result]);
return true;
}
@@ -247,7 +278,7 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap
* @param key Key to detect
* @description Computational complexity: O(log size)
*/
- has(key: K): boolean {
+ has(key: K): boolean {
return this.forRange(key, key, true, undefined) !== 0;
}
@@ -264,42 +295,50 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap
// Clone-mutators /////////////////////////////////////////////////////////
/** Returns a copy of the tree with the specified key set (the value is undefined). */
- with(key: K): BTree<K,V|undefined>;
+ with(key: K): BTree<K, V | undefined>;
/** Returns a copy of the tree with the specified key-value pair set. */
- with<V2>(key: K, value: V2, overwrite?: boolean): BTree<K,V|V2>;
- with<V2>(key: K, value?: V2, overwrite?: boolean): BTree<K,V|V2|undefined> {
- let nu = this.clone() as BTree<K,V|V2|undefined>;
+ with<V2>(key: K, value: V2, overwrite?: boolean): BTree<K, V | V2>;
+ with<V2>(
+ key: K,
+ value?: V2,
+ overwrite?: boolean,
+ ): BTree<K, V | V2 | undefined> {
+ let nu = this.clone() as BTree<K, V | V2 | undefined>;
return nu.set(key, value, overwrite) || overwrite ? nu : this;
}
/** Returns a copy of the tree with the specified key-value pairs set. */
- withPairs<V2>(pairs: [K,V|V2][], overwrite: boolean): BTree<K,V|V2> {
- let nu = this.clone() as BTree<K,V|V2>;
+ withPairs<V2>(pairs: [K, V | V2][], overwrite: boolean): BTree<K, V | V2> {
+ let nu = this.clone() as BTree<K, V | V2>;
return nu.setPairs(pairs, overwrite) !== 0 || overwrite ? nu : this;
}
- /** Returns a copy of the tree with the specified keys present.
+ /** Returns a copy of the tree with the specified keys present.
* @param keys The keys to add. If a key is already present in the tree,
* neither the existing key nor the existing value is modified.
- * @param returnThisIfUnchanged if true, returns this if all keys already
+ * @param returnThisIfUnchanged if true, returns this if all keys already
* existed. Performance note: due to the architecture of this class, all
* node(s) leading to existing keys are cloned even if the collection is
* ultimately unchanged.
- */
- withKeys(keys: K[], returnThisIfUnchanged?: boolean): BTree<K,V|undefined> {
- let nu = this.clone() as BTree<K,V|undefined>, changed = false;
+ */
+ withKeys(
+ keys: K[],
+ returnThisIfUnchanged?: boolean,
+ ): BTree<K, V | undefined> {
+ let nu = this.clone() as BTree<K, V | undefined>,
+ changed = false;
for (var i = 0; i < keys.length; i++)
changed = nu.set(keys[i], undefined, false) || changed;
return returnThisIfUnchanged && !changed ? this : nu;
}
- /** Returns a copy of the tree with the specified key removed.
+ /** Returns a copy of the tree with the specified key removed.
* @param returnThisIfUnchanged if true, returns this if the key didn't exist.
* Performance note: due to the architecture of this class, node(s) leading
* to where the key would have been stored are cloned even when the key
* turns out not to exist and the collection is unchanged.
*/
- without(key: K, returnThisIfUnchanged?: boolean): BTree<K,V> {
+ without(key: K, returnThisIfUnchanged?: boolean): BTree<K, V> {
return this.withoutRange(key, key, true, returnThisIfUnchanged);
}
@@ -309,61 +348,92 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap
* node(s) leading to where the key would have been stored are cloned
* even when the key turns out not to exist.
*/
- withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): BTree<K,V> {
+ withoutKeys(keys: K[], returnThisIfUnchanged?: boolean): BTree<K, V> {
let nu = this.clone();
return nu.deleteKeys(keys) || !returnThisIfUnchanged ? nu : this;
}
/** Returns a copy of the tree with the specified range of keys removed. */
- withoutRange(low: K, high: K, includeHigh: boolean, returnThisIfUnchanged?: boolean): BTree<K,V> {
+ withoutRange(
+ low: K,
+ high: K,
+ includeHigh: boolean,
+ returnThisIfUnchanged?: boolean,
+ ): BTree<K, V> {
let nu = this.clone();
if (nu.deleteRange(low, high, includeHigh) === 0 && returnThisIfUnchanged)
return this;
return nu;
}
- /** Returns a copy of the tree with pairs removed whenever the callback
+ /** Returns a copy of the tree with pairs removed whenever the callback
* function returns false. `where()` is a synonym for this method. */
- filter(callback: (k:K,v:V,counter:number) => boolean, returnThisIfUnchanged?: boolean): BTree<K,V> {
+ filter(
+ callback: (k: K, v: V, counter: number) => boolean,
+ returnThisIfUnchanged?: boolean,
+ ): BTree<K, V> {
var nu = this.greedyClone();
var del: any;
- nu.editAll((k,v,i) => {
- if (!callback(k, v, i)) return del = Delete;
+ nu.editAll((k, v, i) => {
+ if (!callback(k, v, i)) return (del = Delete);
});
- if (!del && returnThisIfUnchanged)
- return this;
+ if (!del && returnThisIfUnchanged) return this;
return nu;
}
/** Returns a copy of the tree with all values altered by a callback function. */
- mapValues<R>(callback: (v:V,k:K,counter:number) => R): BTree<K,R> {
- var tmp = {} as {value:R};
+ mapValues<R>(callback: (v: V, k: K, counter: number) => R): BTree<K, R> {
+ var tmp = {} as { value: R };
var nu = this.greedyClone();
- nu.editAll((k,v,i) => {
- return tmp.value = callback(v, k, i), tmp as any;
+ nu.editAll((k, v, i) => {
+ return (tmp.value = callback(v, k, i)), tmp as any;
});
- return nu as any as BTree<K,R>;
+ return (nu as any) as BTree<K, R>;
}
- /** Performs a reduce operation like the `reduce` method of `Array`.
- * It is used to combine all pairs into a single value, or perform
+ /** Performs a reduce operation like the `reduce` method of `Array`.
+ * It is used to combine all pairs into a single value, or perform
* conversions. `reduce` is best understood by example. For example,
- * `tree.reduce((P, pair) => P * pair[0], 1)` multiplies all keys
- * together. It means "start with P=1, and for each pair multiply
- * it by the key in pair[0]". Another example would be converting
+ * `tree.reduce((P, pair) => P * pair[0], 1)` multiplies all keys
+ * together. It means "start with P=1, and for each pair multiply
+ * it by the key in pair[0]". Another example would be converting
* the tree to a Map (in this example, note that M.set returns M):
- *
+ *
* var M = tree.reduce((M, pair) => M.set(pair[0],pair[1]), new Map())
- *
+ *
* **Note**: the same array is sent to the callback on every iteration.
*/
- reduce<R>(callback: (previous:R,currentPair:[K,V],counter:number,tree:BTree<K,V>) => R, initialValue: R): R;
- reduce<R>(callback: (previous:R|undefined,currentPair:[K,V],counter:number,tree:BTree<K,V>) => R): R|undefined;
- reduce<R>(callback: (previous:R|undefined,currentPair:[K,V],counter:number,tree:BTree<K,V>) => R, initialValue?: R): R|undefined {
- let i = 0, p = initialValue;
- var it = this.entries(this.minKey(), ReusedArray), next;
- while (!(next = it.next()).done)
- p = callback(p, next.value, i++, this);
+ reduce<R>(
+ callback: (
+ previous: R,
+ currentPair: [K, V],
+ counter: number,
+ tree: BTree<K, V>,
+ ) => R,
+ initialValue: R,
+ ): R;
+ reduce<R>(
+ callback: (
+ previous: R | undefined,
+ currentPair: [K, V],
+ counter: number,
+ tree: BTree<K, V>,
+ ) => R,
+ ): R | undefined;
+ reduce<R>(
+ callback: (
+ previous: R | undefined,
+ currentPair: [K, V],
+ counter: number,
+ tree: BTree<K, V>,
+ ) => R,
+ initialValue?: R,
+ ): R | undefined {
+ let i = 0,
+ p = initialValue;
+ var it = this.entries(this.minKey(), ReusedArray),
+ next;
+ while (!(next = it.next()).done) p = callback(p, next.value, i++, this);
return p;
}
@@ -377,53 +447,59 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap
* @param reusedArray Optional array used repeatedly to store key-value
* pairs, to avoid creating a new array on every iteration.
*/
- entries(lowestKey?: K, reusedArray?: (K|V)[]): IterableIterator<[K,V]> {
+ entries(lowestKey?: K, reusedArray?: (K | V)[]): IterableIterator<[K, V]> {
var info = this.findPath(lowestKey);
- if (info === undefined) return iterator<[K,V]>();
- var {nodequeue, nodeindex, leaf} = info;
+ if (info === undefined) return iterator<[K, V]>();
+ var { nodequeue, nodeindex, leaf } = info;
var state = reusedArray !== undefined ? 1 : 0;
- var i = (lowestKey === undefined ? -1 : leaf.indexOf(lowestKey, 0, this._compare) - 1);
+ var i =
+ lowestKey === undefined
+ ? -1
+ : leaf.indexOf(lowestKey, 0, this._compare) - 1;
- return iterator<[K,V]>(() => {
+ return iterator<[K, V]>(() => {
jump: for (;;) {
- switch(state) {
+ switch (state) {
case 0:
if (++i < leaf.keys.length)
- return {done: false, value: [leaf.keys[i], leaf.values[i]]};
+ return { done: false, value: [leaf.keys[i], leaf.values[i]] };
state = 2;
continue;
case 1:
if (++i < leaf.keys.length) {
- reusedArray![0] = leaf.keys[i], reusedArray![1] = leaf.values[i];
- return {done: false, value: reusedArray as [K,V]};
+ (reusedArray![0] = leaf.keys[i]),
+ (reusedArray![1] = leaf.values[i]);
+ return { done: false, value: reusedArray as [K, V] };
}
state = 2;
case 2:
// Advance to the next leaf node
- for (var level = -1;;) {
+ for (var level = -1; ; ) {
if (++level >= nodequeue.length) {
- state = 3; continue jump;
+ state = 3;
+ continue jump;
}
- if (++nodeindex[level] < nodequeue[level].length)
- break;
+ if (++nodeindex[level] < nodequeue[level].length) break;
}
for (; level > 0; level--) {
- nodequeue[level-1] = (nodequeue[level][nodeindex[level]] as BNodeInternal<K,V>).children;
- nodeindex[level-1] = 0;
+ nodequeue[level - 1] = (nodequeue[level][
+ nodeindex[level]
+ ] as BNodeInternal<K, V>).children;
+ nodeindex[level - 1] = 0;
}
leaf = nodequeue[0][nodeindex[0]];
i = -1;
state = reusedArray !== undefined ? 1 : 0;
continue;
case 3:
- return {done: true, value: undefined};
+ return { done: true, value: undefined };
}
}
});
}
/** Returns an iterator that provides items in reversed order.
- * @param highestKey Key at which to start iterating, or undefined to
+ * @param highestKey Key at which to start iterating, or undefined to
* start at minKey(). If the specified key doesn't exist then iteration
* starts at the next lower key (according to the comparator).
* @param reusedArray Optional array used repeatedly to store key-value
@@ -431,49 +507,56 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap
* @param skipHighest Iff this flag is true and the highestKey exists in the
* collection, the pair matching highestKey is skipped, not iterated.
*/
- entriesReversed(highestKey?: K, reusedArray?: (K|V)[], skipHighest?: boolean): IterableIterator<[K,V]> {
+ entriesReversed(
+ highestKey?: K,
+ reusedArray?: (K | V)[],
+ skipHighest?: boolean,
+ ): IterableIterator<[K, V]> {
if ((highestKey = highestKey || this.maxKey()) === undefined)
- return iterator<[K,V]>(); // collection is empty
- var {nodequeue,nodeindex,leaf} = this.findPath(highestKey) || this.findPath(this.maxKey())!;
+ return iterator<[K, V]>(); // collection is empty
+ var { nodequeue, nodeindex, leaf } =
+ this.findPath(highestKey) || this.findPath(this.maxKey())!;
check(!nodequeue[0] || leaf === nodequeue[0][nodeindex[0]], "wat!");
var i = leaf.indexOf(highestKey, 0, this._compare);
- if (!(skipHighest || this._compare(leaf.keys[i], highestKey) > 0))
- i++;
+ if (!(skipHighest || this._compare(leaf.keys[i], highestKey) > 0)) i++;
var state = reusedArray !== undefined ? 1 : 0;
- return iterator<[K,V]>(() => {
+ return iterator<[K, V]>(() => {
jump: for (;;) {
- switch(state) {
+ switch (state) {
case 0:
if (--i >= 0)
- return {done: false, value: [leaf.keys[i], leaf.values[i]]};
+ return { done: false, value: [leaf.keys[i], leaf.values[i]] };
state = 2;
continue;
case 1:
if (--i >= 0) {
- reusedArray![0] = leaf.keys[i], reusedArray![1] = leaf.values[i];
- return {done: false, value: reusedArray as [K,V]};
+ (reusedArray![0] = leaf.keys[i]),
+ (reusedArray![1] = leaf.values[i]);
+ return { done: false, value: reusedArray as [K, V] };
}
state = 2;
case 2:
// Advance to the next leaf node
- for (var level = -1;;) {
+ for (var level = -1; ; ) {
if (++level >= nodequeue.length) {
- state = 3; continue jump;
+ state = 3;
+ continue jump;
}
- if (--nodeindex[level] >= 0)
- break;
+ if (--nodeindex[level] >= 0) break;
}
for (; level > 0; level--) {
- nodequeue[level-1] = (nodequeue[level][nodeindex[level]] as BNodeInternal<K,V>).children;
- nodeindex[level-1] = nodequeue[level-1].length-1;
+ nodequeue[level - 1] = (nodequeue[level][
+ nodeindex[level]
+ ] as BNodeInternal<K, V>).children;
+ nodeindex[level - 1] = nodequeue[level - 1].length - 1;
}
leaf = nodequeue[0][nodeindex[0]];
i = leaf.keys.length;
state = reusedArray !== undefined ? 1 : 0;
continue;
case 3:
- return {done: true, value: undefined};
+ return { done: true, value: undefined };
}
}
});
@@ -481,36 +564,39 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap
/* Used by entries() and entriesReversed() to prepare to start iterating.
* It develops a "node queue" for each non-leaf level of the tree.
- * Levels are numbered "bottom-up" so that level 0 is a list of leaf
+ * Levels are numbered "bottom-up" so that level 0 is a list of leaf
* nodes from a low-level non-leaf node. The queue at a given level L
- * consists of nodequeue[L] which is the children of a BNodeInternal,
+ * consists of nodequeue[L] which is the children of a BNodeInternal,
* and nodeindex[L], the current index within that child list, such
* such that nodequeue[L-1] === nodequeue[L][nodeindex[L]].children.
* (However inside this function the order is reversed.)
*/
- private findPath(key?: K): { nodequeue: BNode<K,V>[][], nodeindex: number[], leaf: BNode<K,V> } | undefined
- {
+ private findPath(
+ key?: K,
+ ):
+ | { nodequeue: BNode<K, V>[][]; nodeindex: number[]; leaf: BNode<K, V> }
+ | undefined {
var nextnode = this._root;
- var nodequeue: BNode<K,V>[][], nodeindex: number[];
+ var nodequeue: BNode<K, V>[][], nodeindex: number[];
if (nextnode.isLeaf) {
- nodequeue = EmptyArray, nodeindex = EmptyArray; // avoid allocations
+ (nodequeue = EmptyArray), (nodeindex = EmptyArray); // avoid allocations
} else {
- nodequeue = [], nodeindex = [];
+ (nodequeue = []), (nodeindex = []);
for (var d = 0; !nextnode.isLeaf; d++) {
- nodequeue[d] = (nextnode as BNodeInternal<K,V>).children;
- nodeindex[d] = key === undefined ? 0 : nextnode.indexOf(key, 0, this._compare);
- if (nodeindex[d] >= nodequeue[d].length)
- return; // first key > maxKey()
+ nodequeue[d] = (nextnode as BNodeInternal<K, V>).children;
+ nodeindex[d] =
+ key === undefined ? 0 : nextnode.indexOf(key, 0, this._compare);
+ if (nodeindex[d] >= nodequeue[d].length) return; // first key > maxKey()
nextnode = nodequeue[d][nodeindex[d]];
}
nodequeue.reverse();
nodeindex.reverse();
}
- return {nodequeue, nodeindex, leaf:nextnode};
+ return { nodequeue, nodeindex, leaf: nextnode };
}
- /** Returns a new iterator for iterating the keys of each pair in ascending order.
+ /** Returns a new iterator for iterating the keys of each pair in ascending order.
* @param firstKey: Minimum key to include in the output. */
keys(firstKey?: K): IterableIterator<K> {
var it = this.entries(firstKey, ReusedArray);
@@ -520,8 +606,8 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap
return n;
});
}
-
- /** Returns a new iterator for iterating the values of each pair in order by key.
+
+ /** Returns a new iterator for iterating the values of each pair in order by key.
* @param firstKey: Minimum key whose associated value is included in the output. */
values(firstKey?: K): IterableIterator<V> {
var it = this.entries(firstKey, ReusedArray);
@@ -540,57 +626,79 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap
}
/** Gets the lowest key in the tree. Complexity: O(log size) */
- minKey(): K | undefined { return this._root.minKey(); }
-
+ minKey(): K | undefined {
+ return this._root.minKey();
+ }
+
/** Gets the highest key in the tree. Complexity: O(1) */
- maxKey(): K | undefined { return this._root.maxKey(); }
+ maxKey(): K | undefined {
+ return this._root.maxKey();
+ }
- /** Quickly clones the tree by marking the root node as shared.
+ /** Quickly clones the tree by marking the root node as shared.
* Both copies remain editable. When you modify either copy, any
* nodes that are shared (or potentially shared) between the two
* copies are cloned so that the changes do not affect other copies.
* This is known as copy-on-write behavior, or "lazy copying". */
- clone(): BTree<K,V> {
+ clone(): BTree<K, V> {
this._root.isShared = true;
- var result = new BTree<K,V>(undefined, this._compare, this._maxNodeSize);
+ var result = new BTree<K, V>(undefined, this._compare, this._maxNodeSize);
result._root = this._root;
result._size = this._size;
return result;
}
- /** Performs a greedy clone, immediately duplicating any nodes that are
+ /** Performs a greedy clone, immediately duplicating any nodes that are
* not currently marked as shared, in order to avoid marking any nodes
* as shared.
* @param force Clone all nodes, even shared ones.
*/
- greedyClone(force?: boolean): BTree<K,V> {
- var result = new BTree<K,V>(undefined, this._compare, this._maxNodeSize);
+ greedyClone(force?: boolean): BTree<K, V> {
+ var result = new BTree<K, V>(undefined, this._compare, this._maxNodeSize);
result._root = this._root.greedyClone(force);
result._size = this._size;
return result;
}
/** Gets an array filled with the contents of the tree, sorted by key */
- toArray(maxLength: number = 0x7FFFFFFF): [K,V][] {
- let min = this.minKey(), max = this.maxKey();
- if (min !== undefined)
- return this.getRange(min, max!, true, maxLength)
+ toArray(maxLength: number = 0x7fffffff): [K, V][] {
+ let min = this.minKey(),
+ max = this.maxKey();
+ if (min !== undefined) return this.getRange(min, max!, true, maxLength);
return [];
}
/** Gets an array of all keys, sorted */
keysArray() {
var results: K[] = [];
- this._root.forRange(this.minKey()!, this.maxKey()!, true, false, this, 0,
- (k,v) => { results.push(k); });
+ this._root.forRange(
+ this.minKey()!,
+ this.maxKey()!,
+ true,
+ false,
+ this,
+ 0,
+ (k, v) => {
+ results.push(k);
+ },
+ );
return results;
}
-
+
/** Gets an array of all values, sorted by key */
valuesArray() {
var results: V[] = [];
- this._root.forRange(this.minKey()!, this.maxKey()!, true, false, this, 0,
- (k,v) => { results.push(v); });
+ this._root.forRange(
+ this.minKey()!,
+ this.maxKey()!,
+ true,
+ false,
+ this,
+ 0,
+ (k, v) => {
+ results.push(v);
+ },
+ );
return results;
}
@@ -599,45 +707,44 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap
return this.toArray().toString();
}
- /** Stores a key-value pair only if the key doesn't already exist in the tree.
+ /** Stores a key-value pair only if the key doesn't already exist in the tree.
* @returns true if a new key was added
- */
+ */
setIfNotPresent(key: K, value: V): boolean {
return this.set(key, value, false);
}
/** Returns the next pair whose key is larger than the specified key (or undefined if there is none) */
- nextHigherPair(key: K): [K,V]|undefined {
+ nextHigherPair(key: K): [K, V] | undefined {
var it = this.entries(key, ReusedArray);
var r = it.next();
- if (!r.done && this._compare(r.value[0], key) <= 0)
- r = it.next();
+ if (!r.done && this._compare(r.value[0], key) <= 0) r = it.next();
return r.value;
}
-
+
/** Returns the next key larger than the specified key (or undefined if there is none) */
- nextHigherKey(key: K): K|undefined {
+ nextHigherKey(key: K): K | undefined {
var p = this.nextHigherPair(key);
return p ? p[0] : p;
}
/** Returns the next pair whose key is smaller than the specified key (or undefined if there is none) */
- nextLowerPair(key: K): [K,V]|undefined {
+ nextLowerPair(key: K): [K, V] | undefined {
var it = this.entriesReversed(key, ReusedArray, true);
return it.next().value;
}
-
+
/** Returns the next key smaller than the specified key (or undefined if there is none) */
- nextLowerKey(key: K): K|undefined {
+ nextLowerKey(key: K): K | undefined {
var p = this.nextLowerPair(key);
return p ? p[0] : p;
}
- /** Edits the value associated with a key in the tree, if it already exists.
+ /** Edits the value associated with a key in the tree, if it already exists.
* @returns true if the key existed, false if not.
- */
- changeIfPresent(key: K, value: V): boolean {
- return this.editRange(key, key, true, (k,v) => ({value})) !== 0;
+ */
+ changeIfPresent(key: K, value: V): boolean {
+ return this.editRange(key, key, true, (k, v) => ({ value })) !== 0;
}
/**
@@ -648,106 +755,154 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap
* @param includeHigh If the `high` key is present, its pair will be included
* in the output if and only if this parameter is true. Note: if the
* `low` key is present, it is always included in the output.
- * @param maxLength Length limit. getRange will stop scanning the tree when
+ * @param maxLength Length limit. getRange will stop scanning the tree when
* the array reaches this size.
* @description Computational complexity: O(result.length + log size)
*/
- getRange(low: K, high: K, includeHigh?: boolean, maxLength: number = 0x3FFFFFF): [K,V][] {
- var results: [K,V][] = [];
- this._root.forRange(low, high, includeHigh, false, this, 0, (k,v) => {
- results.push([k,v])
+ getRange(
+ low: K,
+ high: K,
+ includeHigh?: boolean,
+ maxLength: number = 0x3ffffff,
+ ): [K, V][] {
+ var results: [K, V][] = [];
+ this._root.forRange(low, high, includeHigh, false, this, 0, (k, v) => {
+ results.push([k, v]);
return results.length > maxLength ? Break : undefined;
});
return results;
}
/** Adds all pairs from a list of key-value pairs.
- * @param pairs Pairs to add to this tree. If there are duplicate keys,
- * later pairs currently overwrite earlier ones (e.g. [[0,1],[0,7]]
+ * @param pairs Pairs to add to this tree. If there are duplicate keys,
+ * later pairs currently overwrite earlier ones (e.g. [[0,1],[0,7]]
* associates 0 with 7.)
* @param overwrite Whether to overwrite pairs that already exist (if false,
* pairs[i] is ignored when the key pairs[i][0] already exists.)
* @returns The number of pairs added to the collection.
* @description Computational complexity: O(pairs.length * log(size + pairs.length))
*/
- setPairs(pairs: [K,V][], overwrite?: boolean): number {
+ setPairs(pairs: [K, V][], overwrite?: boolean): number {
var added = 0;
for (var i = 0; i < pairs.length; i++)
- if (this.set(pairs[i][0], pairs[i][1], overwrite))
- added++;
+ if (this.set(pairs[i][0], pairs[i][1], overwrite)) added++;
return added;
}
- forRange(low: K, high: K, includeHigh: boolean, onFound?: (k:K,v:V,counter:number) => void, initialCounter?: number): number;
+ forRange(
+ low: K,
+ high: K,
+ includeHigh: boolean,
+ onFound?: (k: K, v: V, counter: number) => void,
+ initialCounter?: number,
+ ): number;
/**
* Scans the specified range of keys, in ascending order by key.
* Note: the callback `onFound` must not insert or remove items in the
- * collection. Doing so may cause incorrect data to be sent to the
+ * collection. Doing so may cause incorrect data to be sent to the
* callback afterward.
* @param low The first key scanned will be greater than or equal to `low`.
* @param high Scanning stops when a key larger than this is reached.
* @param includeHigh If the `high` key is present, `onFound` is called for
* that final pair if and only if this parameter is true.
- * @param onFound A function that is called for each key-value pair. This
+ * @param onFound A function that is called for each key-value pair. This
* function can return {break:R} to stop early with result R.
- * @param initialCounter Initial third argument of onFound. This value
+ * @param initialCounter Initial third argument of onFound. This value
* increases by one each time `onFound` is called. Default: 0
- * @returns The number of values found, or R if the callback returned
+ * @returns The number of values found, or R if the callback returned
* `{break:R}` to stop early.
* @description Computational complexity: O(number of items scanned + log size)
*/
- forRange<R=number>(low: K, high: K, includeHigh: boolean, onFound?: (k:K,v:V,counter:number) => {break?:R}|void, initialCounter?: number): R|number {
- var r = this._root.forRange(low, high, includeHigh, false, this, initialCounter || 0, onFound);
+ forRange<R = number>(
+ low: K,
+ high: K,
+ includeHigh: boolean,
+ onFound?: (k: K, v: V, counter: number) => { break?: R } | void,
+ initialCounter?: number,
+ ): R | number {
+ var r = this._root.forRange(
+ low,
+ high,
+ includeHigh,
+ false,
+ this,
+ initialCounter || 0,
+ onFound,
+ );
return typeof r === "number" ? r : r.break!;
}
/**
* Scans and potentially modifies values for a subsequence of keys.
- * Note: the callback `onFound` should ideally be a pure function.
- * Specfically, it must not insert items, call clone(), or change
+ * Note: the callback `onFound` should ideally be a pure function.
+ * Specfically, it must not insert items, call clone(), or change
* the collection except via return value; out-of-band editing may
* cause an exception or may cause incorrect data to be sent to
- * the callback (duplicate or missed items). It must not cause a
+ * the callback (duplicate or missed items). It must not cause a
* clone() of the collection, otherwise the clone could be modified
* by changes requested by the callback.
* @param low The first key scanned will be greater than or equal to `low`.
* @param high Scanning stops when a key larger than this is reached.
* @param includeHigh If the `high` key is present, `onFound` is called for
* that final pair if and only if this parameter is true.
- * @param onFound A function that is called for each key-value pair. This
- * function can return `{value:v}` to change the value associated
+ * @param onFound A function that is called for each key-value pair. This
+ * function can return `{value:v}` to change the value associated
* with the current key, `{delete:true}` to delete the current pair,
* `{break:R}` to stop early with result R, or it can return nothing
* (undefined or {}) to cause no effect and continue iterating.
* `{break:R}` can be combined with one of the other two commands.
- * The third argument `counter` is the number of items iterated
+ * The third argument `counter` is the number of items iterated
* previously; it equals 0 when `onFound` is called the first time.
- * @returns The number of values scanned, or R if the callback returned
+ * @returns The number of values scanned, or R if the callback returned
* `{break:R}` to stop early.
- * @description
+ * @description
* Computational complexity: O(number of items scanned + log size)
* Note: if the tree has been cloned with clone(), any shared
- * nodes are copied before `onFound` is called. This takes O(n) time
+ * nodes are copied before `onFound` is called. This takes O(n) time
* where n is proportional to the amount of shared data scanned.
*/
- editRange<R=V>(low: K, high: K, includeHigh: boolean, onFound: (k:K,v:V,counter:number) => EditRangeResult<V,R>|void, initialCounter?: number): R|number {
+ editRange<R = V>(
+ low: K,
+ high: K,
+ includeHigh: boolean,
+ onFound: (k: K, v: V, counter: number) => EditRangeResult<V, R> | void,
+ initialCounter?: number,
+ ): R | number {
var root = this._root;
- if (root.isShared)
- this._root = root = root.clone();
+ if (root.isShared) this._root = root = root.clone();
try {
- var r = root.forRange(low, high, includeHigh, true, this, initialCounter || 0, onFound);
+ var r = root.forRange(
+ low,
+ high,
+ includeHigh,
+ true,
+ this,
+ initialCounter || 0,
+ onFound,
+ );
return typeof r === "number" ? r : r.break!;
} finally {
while (root.keys.length <= 1 && !root.isLeaf)
- this._root = root = root.keys.length === 0 ? EmptyLeaf :
- (root as any as BNodeInternal<K,V>).children[0];
+ this._root = root =
+ root.keys.length === 0
+ ? EmptyLeaf
+ : ((root as any) as BNodeInternal<K, V>).children[0];
}
}
/** Same as `editRange` except that the callback is called for all pairs. */
- editAll<R=V>(onFound: (k:K,v:V,counter:number) => EditRangeResult<V,R>|void, initialCounter?: number): R|number {
- return this.editRange(this.minKey()!, this.maxKey()!, true, onFound, initialCounter);
+ editAll<R = V>(
+ onFound: (k: K, v: V, counter: number) => EditRangeResult<V, R> | void,
+ initialCounter?: number,
+ ): R | number {
+ return this.editRange(
+ this.minKey()!,
+ this.maxKey()!,
+ true,
+ onFound,
+ initialCounter,
+ );
}
/**
@@ -764,13 +919,11 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap
/** Deletes a series of keys from the collection. */
deleteKeys(keys: K[]): number {
- for (var i = 0, r = 0; i < keys.length; i++)
- if (this.delete(keys[i]))
- r++;
+ for (var i = 0, r = 0; i < keys.length; i++) if (this.delete(keys[i])) r++;
return r;
}
- /** Gets the height of the tree: the number of internal nodes between the
+ /** Gets the height of the tree: the number of internal nodes between the
* BTree object and its leaf nodes (zero if there are no internal nodes). */
get height(): number {
for (var node = this._root, h = -1; node != null; h++)
@@ -780,15 +933,15 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap
/** Makes the object read-only to ensure it is not accidentally modified.
* Freezing does not have to be permanent; unfreeze() reverses the effect.
- * This is accomplished by replacing mutator functions with a function
- * that throws an Error. Compared to using a property (e.g. this.isFrozen)
+ * This is accomplished by replacing mutator functions with a function
+ * that throws an Error. Compared to using a property (e.g. this.isFrozen)
* this implementation gives better performance in non-frozen BTrees.
*/
freeze() {
var t = this as any;
- // Note: all other mutators ultimately call set() or editRange()
+ // Note: all other mutators ultimately call set() or editRange()
// so we don't need to override those others.
- t.clear = t.set = t.editRange = function() {
+ t.clear = t.set = t.editRange = function () {
throw new Error("Attempted to modify a frozen BTree");
};
}
@@ -802,7 +955,7 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap
/** Returns true if the tree appears to be frozen. */
get isFrozen() {
- return this.hasOwnProperty('editRange');
+ return this.hasOwnProperty("editRange");
}
/** Scans the tree for signs of serious bugs (e.g. this.size doesn't match
@@ -812,65 +965,81 @@ export default class BTree<K=any, V=any> implements ISortedMapF<K,V>, ISortedMap
* does check that maxKey() of the children of internal nodes are sorted. */
checkValid() {
var size = this._root.checkValid(0, this);
- check(size === this.size, "size mismatch: counted ", size, "but stored", this.size);
+ check(
+ size === this.size,
+ "size mismatch: counted ",
+ size,
+ "but stored",
+ this.size,
+ );
}
}
declare const Symbol: any;
-if (Symbol && Symbol.iterator) // iterator is equivalent to entries()
+if (Symbol && Symbol.iterator)
+ // iterator is equivalent to entries()
(BTree as any).prototype[Symbol.iterator] = BTree.prototype.entries;
(BTree as any).prototype.where = BTree.prototype.filter;
(BTree as any).prototype.setRange = BTree.prototype.setPairs;
(BTree as any).prototype.add = BTree.prototype.set;
-function iterator<T>(next: () => {done?:boolean,value?:T} = (() => ({ done:true, value:undefined }))): IterableIterator<T> {
+function iterator<T>(
+ next: () => { done?: boolean; value?: T } = () => ({
+ done: true,
+ value: undefined,
+ }),
+): IterableIterator<T> {
var result: any = { next };
if (Symbol && Symbol.iterator)
- result[Symbol.iterator] = function() { return this; };
+ result[Symbol.iterator] = function () {
+ return this;
+ };
return result;
}
-
/** Leaf node / base class. **************************************************/
-class BNode<K,V> {
+class BNode<K, V> {
// If this is an internal node, _keys[i] is the highest key in children[i].
keys: K[];
values: V[];
isShared: true | undefined;
- get isLeaf() { return (this as any).children === undefined; }
-
+ get isLeaf() {
+ return (this as any).children === undefined;
+ }
+
constructor(keys: K[] = [], values?: V[]) {
this.keys = keys;
- this.values = values || undefVals as any[];
+ this.values = values || (undefVals as any[]);
this.isShared = undefined;
}
// Shared methods /////////////////////////////////////////////////////////
maxKey() {
- return this.keys[this.keys.length-1];
+ return this.keys[this.keys.length - 1];
}
// If key not found, returns i^failXor where i is the insertion index.
// Callers that don't care whether there was a match will set failXor=0.
- indexOf(key: K, failXor: number, cmp: (a:K, b:K) => number): index {
+ indexOf(key: K, failXor: number, cmp: (a: K, b: K) => number): index {
// TODO: benchmark multiple search strategies
const keys = this.keys;
- var lo = 0, hi = keys.length, mid = hi >> 1;
- while(lo < hi) {
+ var lo = 0,
+ hi = keys.length,
+ mid = hi >> 1;
+ while (lo < hi) {
var c = cmp(keys[mid], key);
- if (c < 0)
- lo = mid + 1;
- else if (c > 0) // key < keys[mid]
+ if (c < 0) lo = mid + 1;
+ else if (c > 0)
+ // key < keys[mid]
hi = mid;
- else if (c === 0)
- return mid;
+ else if (c === 0) return mid;
else {
// c is NaN or otherwise invalid
- if (key === key) // at least the search key is not NaN
+ if (key === key)
+ // at least the search key is not NaN
return keys.length;
- else
- throw new Error("BTree: NaN was used as a key");
+ else throw new Error("BTree: NaN was used as a key");
}
mid = (lo + hi) >> 1;
}
@@ -928,26 +1097,36 @@ class BNode<K,V> {
return this.keys[0];
}
- clone(): BNode<K,V> {
+ clone(): BNode<K, V> {
var v = this.values;
- return new BNode<K,V>(this.keys.slice(0), v === undefVals ? v : v.slice(0));
+ return new BNode<K, V>(
+ this.keys.slice(0),
+ v === undefVals ? v : v.slice(0),
+ );
}
- greedyClone(force?: boolean): BNode<K,V> {
+ greedyClone(force?: boolean): BNode<K, V> {
return this.isShared && !force ? this : this.clone();
}
- get(key: K, defaultValue: V|undefined, tree: BTree<K,V>): V|undefined {
+ get(key: K, defaultValue: V | undefined, tree: BTree<K, V>): V | undefined {
var i = this.indexOf(key, -1, tree._compare);
return i < 0 ? defaultValue : this.values[i];
}
- checkValid(depth: number, tree: BTree<K,V>): number {
- var kL = this.keys.length, vL = this.values.length;
- check(this.values === undefVals ? kL <= vL : kL === vL,
- "keys/values length mismatch: depth", depth, "with lengths", kL, vL);
+ checkValid(depth: number, tree: BTree<K, V>): number {
+ var kL = this.keys.length,
+ vL = this.values.length;
+ check(
+ this.values === undefVals ? kL <= vL : kL === vL,
+ "keys/values length mismatch: depth",
+ depth,
+ "with lengths",
+ kL,
+ vL,
+ );
// Note: we don't check for "node too small" because sometimes a node
- // can legitimately have size 1. This occurs if there is a batch
+ // can legitimately have size 1. This occurs if there is a batch
// deletion, leaving a node of size 1, and the siblings are full so
// it can't be merged with adjacent nodes. However, the parent will
// verify that the average node size is at least half of the maximum.
@@ -957,18 +1136,24 @@ class BNode<K,V> {
// Leaf Node: set & node splitting //////////////////////////////////////////
- set(key: K, value: V, overwrite: boolean|undefined, tree: BTree<K,V>): boolean|BNode<K,V> {
+ set(
+ key: K,
+ value: V,
+ overwrite: boolean | undefined,
+ tree: BTree<K, V>,
+ ): boolean | BNode<K, V> {
var i = this.indexOf(key, -1, tree._compare);
if (i < 0) {
// key does not exist yet
i = ~i;
tree._size++;
-
+
if (this.keys.length < tree._maxNodeSize) {
return this.insertInLeaf(i, key, value, tree);
} else {
// This leaf node is full and must split
- var newRightSibling = this.splitOffRightSide(), target: BNode<K,V> = this;
+ var newRightSibling = this.splitOffRightSide(),
+ target: BNode<K, V> = this;
if (i > this.keys.length) {
i -= this.keys.length;
target = newRightSibling;
@@ -979,8 +1164,7 @@ class BNode<K,V> {
} else {
// Key already exists
if (overwrite !== false) {
- if (value !== undefined)
- this.reifyValues();
+ if (value !== undefined) this.reifyValues();
// usually this is a no-op, but some users may wish to edit the key
this.keys[i] = key;
this.values[i] = value;
@@ -991,15 +1175,14 @@ class BNode<K,V> {
reifyValues() {
if (this.values === undefVals)
- return this.values = this.values.slice(0, this.keys.length);
+ return (this.values = this.values.slice(0, this.keys.length));
return this.values;
}
- insertInLeaf(i: index, key: K, value: V, tree: BTree<K,V>) {
+ insertInLeaf(i: index, key: K, value: V, tree: BTree<K, V>) {
this.keys.splice(i, 0, key);
if (this.values === undefVals) {
- while (undefVals.length < tree._maxNodeSize)
- undefVals.push(undefined);
+ while (undefVals.length < tree._maxNodeSize) undefVals.push(undefined);
if (value === undefined) {
return true;
} else {
@@ -1009,15 +1192,14 @@ class BNode<K,V> {
this.values.splice(i, 0, value);
return true;
}
-
- takeFromRight(rhs: BNode<K,V>) {
+
+ takeFromRight(rhs: BNode<K, V>) {
// Reminder: parent node must update its copy of key for this node
// assert: neither node is shared
// assert rhs.keys.length > (maxNodeSize/2 && this.keys.length<maxNodeSize)
var v = this.values;
if (rhs.values === undefVals) {
- if (v !== undefVals)
- v.push(undefined as any);
+ if (v !== undefVals) v.push(undefined as any);
} else {
v = this.reifyValues();
v.push(rhs.values.shift()!);
@@ -1025,14 +1207,13 @@ class BNode<K,V> {
this.keys.push(rhs.keys.shift()!);
}
- takeFromLeft(lhs: BNode<K,V>) {
+ takeFromLeft(lhs: BNode<K, V>) {
// Reminder: parent node must update its copy of key for this node
// assert: neither node is shared
// assert rhs.keys.length > (maxNodeSize/2 && this.keys.length<maxNodeSize)
var v = this.values;
if (lhs.values === undefVals) {
- if (v !== undefVals)
- v.unshift(undefined as any);
+ if (v !== undefVals) v.unshift(undefined as any);
} else {
v = this.reifyValues();
v.unshift(lhs.values.pop()!);
@@ -1040,36 +1221,42 @@ class BNode<K,V> {
this.keys.unshift(lhs.keys.pop()!);
}
- splitOffRightSide(): BNode<K,V> {
+ splitOffRightSide(): BNode<K, V> {
// Reminder: parent node must update its copy of key for this node
- var half = this.keys.length >> 1, keys = this.keys.splice(half);
- var values = this.values === undefVals ? undefVals : this.values.splice(half);
- return new BNode<K,V>(keys, values);
+ var half = this.keys.length >> 1,
+ keys = this.keys.splice(half);
+ var values =
+ this.values === undefVals ? undefVals : this.values.splice(half);
+ return new BNode<K, V>(keys, values);
}
// Leaf Node: scanning & deletions //////////////////////////////////////////
- forRange<R>(low: K, high: K, includeHigh: boolean|undefined, editMode: boolean, tree: BTree<K,V>, count: number,
- onFound?: (k:K, v:V, counter:number) => EditRangeResult<V,R>|void): EditRangeResult<V,R>|number {
+ forRange<R>(
+ low: K,
+ high: K,
+ includeHigh: boolean | undefined,
+ editMode: boolean,
+ tree: BTree<K, V>,
+ count: number,
+ onFound?: (k: K, v: V, counter: number) => EditRangeResult<V, R> | void,
+ ): EditRangeResult<V, R> | number {
var cmp = tree._compare;
var iLow, iHigh;
if (high === low) {
- if (!includeHigh)
- return count;
+ if (!includeHigh) return count;
iHigh = (iLow = this.indexOf(low, -1, cmp)) + 1;
- if (iLow < 0)
- return count;
+ if (iLow < 0) return count;
} else {
iLow = this.indexOf(low, 0, cmp);
iHigh = this.indexOf(high, -1, cmp);
- if (iHigh < 0)
- iHigh = ~iHigh;
- else if (includeHigh === true)
- iHigh++;
+ if (iHigh < 0) iHigh = ~iHigh;
+ else if (includeHigh === true) iHigh++;
}
- var keys = this.keys, values = this.values;
+ var keys = this.keys,
+ values = this.values;
if (onFound !== undefined) {
- for(var i = iLow; i < iHigh; i++) {
+ for (var i = iLow; i < iHigh; i++) {
var key = keys[i];
var result = onFound(key, values[i], count++);
if (result !== undefined) {
@@ -1078,30 +1265,26 @@ class BNode<K,V> {
throw new Error("BTree illegally changed or cloned in editRange");
if (result.delete) {
this.keys.splice(i, 1);
- if (this.values !== undefVals)
- this.values.splice(i, 1);
+ if (this.values !== undefVals) this.values.splice(i, 1);
tree._size--;
i--;
iHigh--;
- } else if (result.hasOwnProperty('value')) {
+ } else if (result.hasOwnProperty("value")) {
values![i] = result.value!;
}
}
- if (result.break !== undefined)
- return result;
+ if (result.break !== undefined) return result;
}
}
- } else
- count += iHigh - iLow;
+ } else count += iHigh - iLow;
return count;
}
/** Adds entire contents of right-hand sibling (rhs is left unchanged) */
- mergeSibling(rhs: BNode<K,V>, _: number) {
+ mergeSibling(rhs: BNode<K, V>, _: number) {
this.keys.push.apply(this.keys, rhs.keys);
if (this.values === undefVals) {
- if (rhs.values === undefVals)
- return;
+ if (rhs.values === undefVals) return;
this.values = this.values.slice(0, this.keys.length);
}
this.values.push.apply(this.values, rhs.reifyValues());
@@ -1109,33 +1292,33 @@ class BNode<K,V> {
}
/** Internal node (non-leaf node) ********************************************/
-class BNodeInternal<K,V> extends BNode<K,V> {
- // Note: conventionally B+ trees have one fewer key than the number of
+class BNodeInternal<K, V> extends BNode<K, V> {
+ // Note: conventionally B+ trees have one fewer key than the number of
// children, but I find it easier to keep the array lengths equal: each
// keys[i] caches the value of children[i].maxKey().
- children: BNode<K,V>[];
+ children: BNode<K, V>[];
- constructor(children: BNode<K,V>[], keys?: K[]) {
+ constructor(children: BNode<K, V>[], keys?: K[]) {
if (!keys) {
keys = [];
- for (var i = 0; i < children.length; i++)
- keys[i] = children[i].maxKey();
+ for (var i = 0; i < children.length; i++) keys[i] = children[i].maxKey();
}
super(keys);
this.children = children;
}
- clone(): BNode<K,V> {
+ clone(): BNode<K, V> {
var children = this.children.slice(0);
- for (var i = 0; i < children.length; i++)
- children[i].isShared = true;
- return new BNodeInternal<K,V>(children, this.keys.slice(0));
+ for (var i = 0; i < children.length; i++) children[i].isShared = true;
+ return new BNodeInternal<K, V>(children, this.keys.slice(0));
}
- greedyClone(force?: boolean): BNode<K,V> {
- if (this.isShared && !force)
- return this;
- var nu = new BNodeInternal<K,V>(this.children.slice(0), this.keys.slice(0));
+ greedyClone(force?: boolean): BNode<K, V> {
+ if (this.isShared && !force) return this;
+ var nu = new BNodeInternal<K, V>(
+ this.children.slice(0),
+ this.keys.slice(0),
+ );
for (var i = 0; i < nu.children.length; i++)
nu.children[i] = nu.children[i].greedyClone();
return nu;
@@ -1145,141 +1328,229 @@ class BNodeInternal<K,V> extends BNode<K,V> {
return this.children[0].minKey();
}
- get(key: K, defaultValue: V|undefined, tree: BTree<K,V>): V|undefined {
- var i = this.indexOf(key, 0, tree._compare), children = this.children;
- return i < children.length ? children[i].get(key, defaultValue, tree) : undefined;
- }
-
- checkValid(depth: number, tree: BTree<K,V>) : number {
- var kL = this.keys.length, cL = this.children.length;
- check(kL === cL, "keys/children length mismatch: depth", depth, "lengths", kL, cL);
+ get(key: K, defaultValue: V | undefined, tree: BTree<K, V>): V | undefined {
+ var i = this.indexOf(key, 0, tree._compare),
+ children = this.children;
+ return i < children.length
+ ? children[i].get(key, defaultValue, tree)
+ : undefined;
+ }
+
+ checkValid(depth: number, tree: BTree<K, V>): number {
+ var kL = this.keys.length,
+ cL = this.children.length;
+ check(
+ kL === cL,
+ "keys/children length mismatch: depth",
+ depth,
+ "lengths",
+ kL,
+ cL,
+ );
check(kL > 1, "internal node has length", kL, "at depth", depth);
- var size = 0, c = this.children, k = this.keys, childSize = 0;
+ var size = 0,
+ c = this.children,
+ k = this.keys,
+ childSize = 0;
for (var i = 0; i < cL; i++) {
size += c[i].checkValid(depth + 1, tree);
childSize += c[i].keys.length;
check(size >= childSize, "wtf"); // no way this will ever fail
- check(i === 0 || c[i-1].constructor === c[i].constructor, "type mismatch");
+ check(
+ i === 0 || c[i - 1].constructor === c[i].constructor,
+ "type mismatch",
+ );
if (c[i].maxKey() != k[i])
- check(false, "keys[", i, "] =", k[i], "is wrong, should be ", c[i].maxKey(), "at depth", depth);
- if (!(i === 0 || tree._compare(k[i-1], k[i]) < 0))
- check(false, "sort violation at depth", depth, "index", i, "keys", k[i-1], k[i]);
+ check(
+ false,
+ "keys[",
+ i,
+ "] =",
+ k[i],
+ "is wrong, should be ",
+ c[i].maxKey(),
+ "at depth",
+ depth,
+ );
+ if (!(i === 0 || tree._compare(k[i - 1], k[i]) < 0))
+ check(
+ false,
+ "sort violation at depth",
+ depth,
+ "index",
+ i,
+ "keys",
+ k[i - 1],
+ k[i],
+ );
}
- var toofew = childSize < (tree.maxNodeSize >> 1)*cL;
- if (toofew || childSize > tree.maxNodeSize*cL)
- check(false, toofew ? "too few" : "too many", "children (", childSize, size, ") at depth", depth, ", maxNodeSize:", tree.maxNodeSize, "children.length:", cL);
+ var toofew = childSize < (tree.maxNodeSize >> 1) * cL;
+ if (toofew || childSize > tree.maxNodeSize * cL)
+ check(
+ false,
+ toofew ? "too few" : "too many",
+ "children (",
+ childSize,
+ size,
+ ") at depth",
+ depth,
+ ", maxNodeSize:",
+ tree.maxNodeSize,
+ "children.length:",
+ cL,
+ );
return size;
}
// Internal Node: set & node splitting //////////////////////////////////////
- set(key: K, value: V, overwrite: boolean|undefined, tree: BTree<K,V>): boolean|BNodeInternal<K,V> {
- var c = this.children, max = tree._maxNodeSize, cmp = tree._compare;
- var i = Math.min(this.indexOf(key, 0, cmp), c.length - 1), child = c[i];
-
- if (child.isShared)
- c[i] = child = child.clone();
+ set(
+ key: K,
+ value: V,
+ overwrite: boolean | undefined,
+ tree: BTree<K, V>,
+ ): boolean | BNodeInternal<K, V> {
+ var c = this.children,
+ max = tree._maxNodeSize,
+ cmp = tree._compare;
+ var i = Math.min(this.indexOf(key, 0, cmp), c.length - 1),
+ child = c[i];
+
+ if (child.isShared) c[i] = child = child.clone();
if (child.keys.length >= max) {
// child is full; inserting anything else will cause a split.
// Shifting an item to the left or right sibling may avoid a split.
// We can do a shift if the adjacent node is not full and if the
// current key can still be placed in the same node after the shift.
- var other: BNode<K,V>;
- if (i > 0 && (other = c[i-1]).keys.length < max && cmp(child.keys[0], key) < 0) {
- if (other.isShared)
- c[i-1] = other = other.clone();
+ var other: BNode<K, V>;
+ if (
+ i > 0 &&
+ (other = c[i - 1]).keys.length < max &&
+ cmp(child.keys[0], key) < 0
+ ) {
+ if (other.isShared) c[i - 1] = other = other.clone();
other.takeFromRight(child);
- this.keys[i-1] = other.maxKey();
- } else if ((other = c[i+1]) !== undefined && other.keys.length < max && cmp(child.maxKey(), key) < 0) {
- if (other.isShared)
- c[i+1] = other = other.clone();
+ this.keys[i - 1] = other.maxKey();
+ } else if (
+ (other = c[i + 1]) !== undefined &&
+ other.keys.length < max &&
+ cmp(child.maxKey(), key) < 0
+ ) {
+ if (other.isShared) c[i + 1] = other = other.clone();
other.takeFromLeft(child);
this.keys[i] = c[i].maxKey();
}
}
var result = child.set(key, value, overwrite, tree);
- if (result === false)
- return false;
+ if (result === false) return false;
this.keys[i] = child.maxKey();
- if (result === true)
- return true;
+ if (result === true) return true;
// The child has split and `result` is a new right child... does it fit?
- if (this.keys.length < max) { // yes
- this.insert(i+1, result);
+ if (this.keys.length < max) {
+ // yes
+ this.insert(i + 1, result);
return true;
- } else { // no, we must split also
- var newRightSibling = this.splitOffRightSide(), target: BNodeInternal<K,V> = this;
+ } else {
+ // no, we must split also
+ var newRightSibling = this.splitOffRightSide(),
+ target: BNodeInternal<K, V> = this;
if (cmp(result.maxKey(), this.maxKey()) > 0) {
target = newRightSibling;
i -= this.keys.length;
}
- target.insert(i+1, result);
+ target.insert(i + 1, result);
return newRightSibling;
}
}
- insert(i: index, child: BNode<K,V>) {
+ insert(i: index, child: BNode<K, V>) {
this.children.splice(i, 0, child);
this.keys.splice(i, 0, child.maxKey());
}
splitOffRightSide() {
var half = this.children.length >> 1;
- return new BNodeInternal<K,V>(this.children.splice(half), this.keys.splice(half));
+ return new BNodeInternal<K, V>(
+ this.children.splice(half),
+ this.keys.splice(half),
+ );
}
- takeFromRight(rhs: BNode<K,V>) {
+ takeFromRight(rhs: BNode<K, V>) {
// Reminder: parent node must update its copy of key for this node
// assert: neither node is shared
// assert rhs.keys.length > (maxNodeSize/2 && this.keys.length<maxNodeSize)
this.keys.push(rhs.keys.shift()!);
- this.children.push((rhs as BNodeInternal<K,V>).children.shift()!);
+ this.children.push((rhs as BNodeInternal<K, V>).children.shift()!);
}
- takeFromLeft(lhs: BNode<K,V>) {
+ takeFromLeft(lhs: BNode<K, V>) {
// Reminder: parent node must update its copy of key for this node
// assert: neither node is shared
// assert rhs.keys.length > (maxNodeSize/2 && this.keys.length<maxNodeSize)
this.keys.unshift(lhs.keys.pop()!);
- this.children.unshift((lhs as BNodeInternal<K,V>).children.pop()!);
+ this.children.unshift((lhs as BNodeInternal<K, V>).children.pop()!);
}
// Internal Node: scanning & deletions //////////////////////////////////////
- forRange<R>(low: K, high: K, includeHigh: boolean|undefined, editMode: boolean, tree: BTree<K,V>, count: number,
- onFound?: (k:K, v:V, counter:number) => EditRangeResult<V,R>|void): EditRangeResult<V,R>|number
- {
+ forRange<R>(
+ low: K,
+ high: K,
+ includeHigh: boolean | undefined,
+ editMode: boolean,
+ tree: BTree<K, V>,
+ count: number,
+ onFound?: (k: K, v: V, counter: number) => EditRangeResult<V, R> | void,
+ ): EditRangeResult<V, R> | number {
var cmp = tree._compare;
- var iLow = this.indexOf(low, 0, cmp), i = iLow;
- var iHigh = Math.min(high === low ? iLow : this.indexOf(high, 0, cmp), this.keys.length-1);
- var keys = this.keys, children = this.children;
+ var iLow = this.indexOf(low, 0, cmp),
+ i = iLow;
+ var iHigh = Math.min(
+ high === low ? iLow : this.indexOf(high, 0, cmp),
+ this.keys.length - 1,
+ );
+ var keys = this.keys,
+ children = this.children;
if (!editMode) {
// Simple case
- for(; i <= iHigh; i++) {
- var result = children[i].forRange(low, high, includeHigh, editMode, tree, count, onFound);
- if (typeof result !== 'number')
- return result;
+ for (; i <= iHigh; i++) {
+ var result = children[i].forRange(
+ low,
+ high,
+ includeHigh,
+ editMode,
+ tree,
+ count,
+ onFound,
+ );
+ if (typeof result !== "number") return result;
count = result;
}
} else if (i <= iHigh) {
try {
- for(; i <= iHigh; i++) {
- if (children[i].isShared)
- children[i] = children[i].clone();
- var result = children[i].forRange(low, high, includeHigh, editMode, tree, count, onFound);
+ for (; i <= iHigh; i++) {
+ if (children[i].isShared) children[i] = children[i].clone();
+ var result = children[i].forRange(
+ low,
+ high,
+ includeHigh,
+ editMode,
+ tree,
+ count,
+ onFound,
+ );
keys[i] = children[i].maxKey();
- if (typeof result !== 'number')
- return result;
+ if (typeof result !== "number") return result;
count = result;
}
} finally {
// Deletions may have occurred, so look for opportunities to merge nodes.
var half = tree._maxNodeSize >> 1;
- if (iLow > 0)
- iLow--;
- for(i = iHigh; i >= iLow; i--) {
+ if (iLow > 0) iLow--;
+ for (i = iHigh; i >= iLow; i--) {
if (children[i].keys.length <= half)
this.tryMerge(i, tree._maxNodeSize);
}
@@ -1298,10 +1569,11 @@ class BNodeInternal<K,V> extends BNode<K,V> {
tryMerge(i: index, maxSize: number): boolean {
var children = this.children;
if (i >= 0 && i + 1 < children.length) {
- if (children[i].keys.length + children[i+1].keys.length <= maxSize) {
- if (children[i].isShared) // cloned already UNLESS i is outside scan range
+ if (children[i].keys.length + children[i + 1].keys.length <= maxSize) {
+ if (children[i].isShared)
+ // cloned already UNLESS i is outside scan range
children[i] = children[i].clone();
- children[i].mergeSibling(children[i+1], maxSize);
+ children[i].mergeSibling(children[i + 1], maxSize);
children.splice(i + 1, 1);
this.keys.splice(i + 1, 1);
this.keys[i] = children[i].maxKey();
@@ -1311,15 +1583,18 @@ class BNodeInternal<K,V> extends BNode<K,V> {
return false;
}
- mergeSibling(rhs: BNode<K,V>, maxNodeSize: number) {
+ mergeSibling(rhs: BNode<K, V>, maxNodeSize: number) {
// assert !this.isShared;
var oldLength = this.keys.length;
this.keys.push.apply(this.keys, rhs.keys);
- this.children.push.apply(this.children, (rhs as any as BNodeInternal<K,V>).children);
+ this.children.push.apply(
+ this.children,
+ ((rhs as any) as BNodeInternal<K, V>).children,
+ );
// If our children are themselves almost empty due to a mass-delete,
// they may need to be merged too (but only the oldLength-1 and its
// right sibling should need this).
- this.tryMerge(oldLength-1, maxNodeSize);
+ this.tryMerge(oldLength - 1, maxNodeSize);
}
}
@@ -1332,20 +1607,27 @@ class BNodeInternal<K,V> extends BNode<K,V> {
// users from making this array too large, BTree has a maximum node size.
var undefVals: any[] = [];
-const Delete = {delete: true}, DeleteRange = () => Delete;
-const Break = {break: true};
-const EmptyLeaf = (function() {
- var n = new BNode<any,any>(); n.isShared = true; return n;
+const Delete = { delete: true },
+ DeleteRange = () => Delete;
+const Break = { break: true };
+const EmptyLeaf = (function () {
+ var n = new BNode<any, any>();
+ n.isShared = true;
+ return n;
})();
const EmptyArray: any[] = [];
const ReusedArray: any[] = []; // assumed thread-local
function check(fact: boolean, ...args: any[]) {
if (!fact) {
- args.unshift('B+ tree '); // at beginning of message
- throw new Error(args.join(' '));
+ args.unshift("B+ tree "); // at beginning of message
+ throw new Error(args.join(" "));
}
}
/** A BTree frozen in the empty state. */
-export const EmptyBTree = (() => { let t = new BTree(); t.freeze(); return t; })();
+export const EmptyBTree = (() => {
+ let t = new BTree();
+ t.freeze();
+ return t;
+})();
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-28 07:14:54 +0000