Comparing version 0.1.2 to 0.1.3
/** | ||
* splaytree v0.1.2 | ||
* splaytree v0.1.3 | ||
* Fast Splay tree for Node and browser | ||
@@ -524,13 +524,16 @@ * | ||
/** | ||
* Bulk-load items | ||
* @param {Array<Key>} keys | ||
* Bulk-load items. Both array have to be same size | ||
* @param {Array<Key>} keys | ||
* @param {Array<Value>} [values] | ||
* @param {Boolean} [presort=false] Pre-sort keys and values, using | ||
* tree's comparator. Sorting is done | ||
* in-place | ||
* @return {AVLTree} | ||
*/ | ||
load(keys = [], values = []) { | ||
if (Array.isArray(keys)) { | ||
for (var i = 0, len = keys.length; i < len; i++) { | ||
this.insert(keys[i], values[i]); | ||
} | ||
} | ||
load(keys = [], values = [], presort = false) { | ||
if (this._size !== 0) throw new Error('bulk-load: tree is not empty'); | ||
const size = keys.length; | ||
if (presort) sort(keys, values, 0, size - 1, this._compare); | ||
this._root = loadRecursive(null, keys, values, 0, size); | ||
this._size = size; | ||
return this; | ||
@@ -555,5 +558,65 @@ } | ||
get size() { return this._size; } | ||
/** | ||
* Create a tree and load it with items | ||
* @param {Array<Key>} keys | ||
* @param {Array<Value>?} [values] | ||
* @param {Function?} [comparator] | ||
* @param {Boolean?} [presort=false] Pre-sort keys and values, using | ||
* tree's comparator. Sorting is done | ||
* in-place | ||
* @param {Boolean?} [noDuplicates=false] Allow duplicates | ||
* @return {SplayTree} | ||
*/ | ||
static createTree(keys, values, comparator, presort, noDuplicates) { | ||
const tree = new SplayTree(comparator, noDuplicates); | ||
tree.load(keys, values, presort); | ||
return tree; | ||
} | ||
} | ||
function loadRecursive (parent, keys, values, start, end) { | ||
const size = end - start; | ||
if (size > 0) { | ||
const middle = start + Math.floor(size / 2); | ||
const key = keys[middle]; | ||
const data = values[middle]; | ||
const node = { key, data, parent }; | ||
node.left = loadRecursive(node, keys, values, start, middle); | ||
node.right = loadRecursive(node, keys, values, middle + 1, end); | ||
return node; | ||
} | ||
return null; | ||
} | ||
function sort(keys, values, left, right, compare) { | ||
if (left >= right) return; | ||
const pivot = keys[(left + right) >> 1]; | ||
let i = left - 1; | ||
let j = right + 1; | ||
while (true) { | ||
do i++; while (compare(keys[i], pivot) < 0); | ||
do j--; while (compare(keys[j], pivot) > 0); | ||
if (i >= j) break; | ||
let tmp = keys[i]; | ||
keys[i] = keys[j]; | ||
keys[j] = tmp; | ||
tmp = values[i]; | ||
values[i] = values[j]; | ||
values[j] = tmp; | ||
} | ||
sort(keys, values, left, j, compare); | ||
sort(keys, values, j + 1, right, compare); | ||
} | ||
export default SplayTree; | ||
//# sourceMappingURL=splay.es6.js.map |
/** | ||
* splaytree v0.1.2 | ||
* splaytree v0.1.3 | ||
* Fast Splay tree for Node and browser | ||
@@ -543,17 +543,20 @@ * | ||
/** | ||
* Bulk-load items | ||
* @param{Array<Key>}keys | ||
* Bulk-load items. Both array have to be same size | ||
* @param{Array<Key>} keys | ||
* @param{Array<Value>}[values] | ||
* @param{Boolean} [presort=false] Pre-sort keys and values, using | ||
* tree's comparator. Sorting is done | ||
* in-place | ||
* @return {AVLTree} | ||
*/ | ||
SplayTree.prototype.load = function load (keys, values) { | ||
var this$1 = this; | ||
SplayTree.prototype.load = function load (keys, values, presort) { | ||
if ( keys === void 0 ) keys = []; | ||
if ( values === void 0 ) values = []; | ||
if ( presort === void 0 ) presort = false; | ||
if (Array.isArray(keys)) { | ||
for (var i = 0, len = keys.length; i < len; i++) { | ||
this$1.insert(keys[i], values[i]); | ||
} | ||
} | ||
if (this._size !== 0) { throw new Error('bulk-load: tree is not empty'); } | ||
var size = keys.length; | ||
if (presort) { sort(keys, values, 0, size - 1, this._compare); } | ||
this._root = loadRecursive(null, keys, values, 0, size); | ||
this._size = size; | ||
return this; | ||
@@ -579,4 +582,63 @@ }; | ||
/** | ||
* Create a tree and load it with items | ||
* @param{Array<Key>} keys | ||
* @param{Array<Value>?} [values] | ||
* @param{Function?} [comparator] | ||
* @param{Boolean?} [presort=false] Pre-sort keys and values, using | ||
* tree's comparator. Sorting is done | ||
* in-place | ||
* @param{Boolean?} [noDuplicates=false] Allow duplicates | ||
* @return {SplayTree} | ||
*/ | ||
SplayTree.createTree = function createTree (keys, values, comparator, presort, noDuplicates) { | ||
var tree = new SplayTree(comparator, noDuplicates); | ||
tree.load(keys, values, presort); | ||
return tree; | ||
}; | ||
Object.defineProperties( SplayTree.prototype, prototypeAccessors ); | ||
function loadRecursive (parent, keys, values, start, end) { | ||
var size = end - start; | ||
if (size > 0) { | ||
var middle = start + Math.floor(size / 2); | ||
var key = keys[middle]; | ||
var data = values[middle]; | ||
var node = { key: key, data: data, parent: parent }; | ||
node.left = loadRecursive(node, keys, values, start, middle); | ||
node.right = loadRecursive(node, keys, values, middle + 1, end); | ||
return node; | ||
} | ||
return null; | ||
} | ||
function sort(keys, values, left, right, compare) { | ||
if (left >= right) { return; } | ||
var pivot = keys[(left + right) >> 1]; | ||
var i = left - 1; | ||
var j = right + 1; | ||
while (true) { | ||
do { i++; } while (compare(keys[i], pivot) < 0); | ||
do { j--; } while (compare(keys[j], pivot) > 0); | ||
if (i >= j) { break; } | ||
var tmp = keys[i]; | ||
keys[i] = keys[j]; | ||
keys[j] = tmp; | ||
tmp = values[i]; | ||
values[i] = values[j]; | ||
values[j] = tmp; | ||
} | ||
sort(keys, values, left, j, compare); | ||
sort(keys, values, j + 1, right, compare); | ||
} | ||
return SplayTree; | ||
@@ -583,0 +645,0 @@ |
@@ -32,3 +32,3 @@ export type Node<Key extends any, Value extends any> = { | ||
forEach(callback: ForEachCallback<Key, Value>): SplayTree<Key, Value>; | ||
load(keys: Array<Key>, values?:Array<Value>): SplayTree<Key, Value>; | ||
load(keys: Array<Key>, values?:Array<Value>, presort?:Boolean): SplayTree<Key, Value>; | ||
prev(node: Node<Key, Value>): Node<Key, Value>; | ||
@@ -39,2 +39,3 @@ next(node: Node<Key, Value>): Node<Key, Value>; | ||
destroy(): SplayTree<Key, Value>; | ||
static createTree(keys: Array<any>, values?:Array<any>, comparator?: Comparator<any>, presort?:Boolean, noDuplicates?: boolean):SplayTree<any,any> | ||
} |
79
index.js
@@ -515,13 +515,16 @@ function DEFAULT_COMPARE (a, b) { return a > b ? 1 : a < b ? -1 : 0; } | ||
/** | ||
* Bulk-load items | ||
* @param {Array<Key>} keys | ||
* Bulk-load items. Both array have to be same size | ||
* @param {Array<Key>} keys | ||
* @param {Array<Value>} [values] | ||
* @param {Boolean} [presort=false] Pre-sort keys and values, using | ||
* tree's comparator. Sorting is done | ||
* in-place | ||
* @return {AVLTree} | ||
*/ | ||
load(keys = [], values = []) { | ||
if (Array.isArray(keys)) { | ||
for (var i = 0, len = keys.length; i < len; i++) { | ||
this.insert(keys[i], values[i]); | ||
} | ||
} | ||
load(keys = [], values = [], presort = false) { | ||
if (this._size !== 0) throw new Error('bulk-load: tree is not empty'); | ||
const size = keys.length; | ||
if (presort) sort(keys, values, 0, size - 1, this._compare); | ||
this._root = loadRecursive(null, keys, values, 0, size); | ||
this._size = size; | ||
return this; | ||
@@ -546,2 +549,62 @@ } | ||
get size() { return this._size; } | ||
/** | ||
* Create a tree and load it with items | ||
* @param {Array<Key>} keys | ||
* @param {Array<Value>?} [values] | ||
* @param {Function?} [comparator] | ||
* @param {Boolean?} [presort=false] Pre-sort keys and values, using | ||
* tree's comparator. Sorting is done | ||
* in-place | ||
* @param {Boolean?} [noDuplicates=false] Allow duplicates | ||
* @return {SplayTree} | ||
*/ | ||
static createTree(keys, values, comparator, presort, noDuplicates) { | ||
const tree = new SplayTree(comparator, noDuplicates); | ||
tree.load(keys, values, presort); | ||
return tree; | ||
} | ||
} | ||
function loadRecursive (parent, keys, values, start, end) { | ||
const size = end - start; | ||
if (size > 0) { | ||
const middle = start + Math.floor(size / 2); | ||
const key = keys[middle]; | ||
const data = values[middle]; | ||
const node = { key, data, parent }; | ||
node.left = loadRecursive(node, keys, values, start, middle); | ||
node.right = loadRecursive(node, keys, values, middle + 1, end); | ||
return node; | ||
} | ||
return null; | ||
} | ||
function sort(keys, values, left, right, compare) { | ||
if (left >= right) return; | ||
const pivot = keys[(left + right) >> 1]; | ||
let i = left - 1; | ||
let j = right + 1; | ||
while (true) { | ||
do i++; while (compare(keys[i], pivot) < 0); | ||
do j--; while (compare(keys[j], pivot) > 0); | ||
if (i >= j) break; | ||
let tmp = keys[i]; | ||
keys[i] = keys[j]; | ||
keys[j] = tmp; | ||
tmp = values[i]; | ||
values[i] = values[j]; | ||
values[j] = tmp; | ||
} | ||
sort(keys, values, left, j, compare); | ||
sort(keys, values, j + 1, right, compare); | ||
} |
{ | ||
"name": "splaytree", | ||
"version": "0.1.2", | ||
"version": "0.1.3", | ||
"author": "Alexander Milevski <info@w8r.name>", | ||
@@ -5,0 +5,0 @@ "license": "MIT", |
@@ -59,3 +59,3 @@ # Splay tree [![npm version](https://badge.fury.io/js/splaytree.svg)](https://badge.fury.io/js/splaytree) [![CircleCI](https://circleci.com/gh/w8r/splay-tree.svg?style=svg)](https://circleci.com/gh/w8r/splay-tree) | ||
* `tree.next(node):Node` - Successor node | ||
* `tree.load(keys:Array<*>, [values:Array<*>]):Tree` - Bulk-load items | ||
* `tree.load(keys:Array<*>, [values:Array<*>][,presort=false]):Tree` - Bulk-load items. If `presort` is `true`, it will sort keys and values using the comparator(in-place!). You can only use it on an empty tree. | ||
@@ -62,0 +62,0 @@ **Comparator** |
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
114755
1613