splaytree - npm Package Compare versions

Comparing version 0.1.2 to 0.1.3

dist/splay.es6.js

 /**
- * 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

dist/splay.js

 /**
- * 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 @@

index.d.ts

@@ -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>
 }

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);
+}

package.json

 {
   "name": "splaytree",
-  "version": "0.1.2",
+  "version": "0.1.3",
   "author": "Alexander Milevski <[e-mail]>",
@@ -5,0 +5,0 @@ "license": "MIT",

Readme.md

@@ -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**

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

114755

increased by14.74%

Lines of code

1613

increased by10.56%

No dependency changes