Skip to content

Instantly share code, notes, and snippets.

@qwertie
Created August 7, 2018 19:42
Show Gist options
  • Save qwertie/7117d6795db47e5e3ae01736003a4b67 to your computer and use it in GitHub Desktop.
Save qwertie/7117d6795db47e5e3ae01736003a4b67 to your computer and use it in GitHub Desktop.
// Type parameters can have default values,
// so `var t: BTree` means `var t: BTree<any,any>`
export class BTree<K=any, V=any>
{
// Root node (key-value pairs are stored in here)
private _root: BNode<K, V>;
// Total number of items in the collection
_size: number = 0;
// Maximum number of items in a single node
_maxNodeSize: number;
// This function must return less-than-0 if a<b and above-zero if a>b
_compare: (a:K, b:K) => number;
public constructor(entries?: [K,V][],
compare?: (a: K, b: K) => number,
maxNodeSize?: number) { ... }
get size() { return this._size; }
clear() { ... }
get(key: K): V | undefined { ... }
set(key: K, value: V, overwrite?: boolean): boolean { ... }
has(key: K): boolean { ... }
delete(key: K) { ... }
/** 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> { ... }
...
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment