splaytree - npm Package Compare versions

Comparing version 0.1.1 to 0.1.2

dist/splay.es6.js

 /**
- * splaytree v0.1.1
+ * splaytree v0.1.2
  * Fast Splay tree for Node and browser
@@ -384,3 +384,3 @@ *
    * @param  {forEachCallback} callback
-   * @return {AVLTree}
+   * @return {SplayTree}
    */
@@ -415,3 +415,35 @@ forEach(callback) {
 
+
   /**
+   * Walk key range from `low` to `high`. Stops if `fn` returns a value.
+   * @param  {Key}      low
+   * @param  {Key}      high
+   * @param  {Function} fn
+   * @param  {*?}       ctx
+   * @return {SplayTree}
+   */
+  range(low, high, fn, ctx) {
+    const Q = [];
+    const compare = this._compare;
+    let node = this._root, cmp;
+
+    while (Q.length !== 0 || node) {
+      if (node) {
+        Q.push(node);
+        node = node.left;
+      } else {
+        node = Q.pop();
+        cmp = compare(node.key, high);
+        if (cmp > 0) {
+          break;
+        } else if (compare(node.key, low) >= 0) {
+          if (fn.call(ctx, node)) return this; // stop if smth is returned
+        }
+        node = node.right;
+      }
+    }
+    return this;
+  }
+
+  /**
    * Returns all keys in order
@@ -418,0 +450,0 @@ * @return {Array<Key>}

dist/splay.js

 /**
- * splaytree v0.1.1
+ * splaytree v0.1.2
  * Fast Splay tree for Node and browser
@@ -401,3 +401,3 @@ *
  * @param{forEachCallback} callback
- * @return {AVLTree}
+ * @return {SplayTree}
  */
@@ -432,3 +432,37 @@ SplayTree.prototype.forEach = function forEach (callback) {
 
+
 /**
+ * Walk key range from `low` to `high`. Stops if `fn` returns a value.
+ * @param{Key}    low
+ * @param{Key}    high
+ * @param{Function} fn
+ * @param{*?}     ctx
+ * @return {SplayTree}
+ */
+SplayTree.prototype.range = function range (low, high, fn, ctx) {
+    var this$1 = this;
+
+  var Q = [];
+  var compare = this._compare;
+  var node = this._root, cmp;
+
+  while (Q.length !== 0 || node) {
+    if (node) {
+      Q.push(node);
+      node = node.left;
+    } else {
+      node = Q.pop();
+      cmp = compare(node.key, high);
+      if (cmp > 0) {
+        break;
+      } else if (compare(node.key, low) >= 0) {
+        if (fn.call(ctx, node)) { return this$1; } // stop if smth is returned
+      }
+      node = node.right;
+    }
+  }
+  return this;
+};
+
+/**
  * Returns all keys in order
@@ -435,0 +469,0 @@ * @return {Array<Key>}

index.d.ts

@@ -11,2 +11,3 @@ export type Node<Key extends any, Value extends any> = {
 export type ForEachCallback<Key, Value> = (node: Node<Key, Value>, index: number) => void
+export type TraverseCallback<Key, Value> = (node: Node<Key, Value>) => (void | boolean)
 
@@ -25,2 +26,3 @@ export default class SplayTree<Key extends any, Value extends any> {
   values(): Array<Value>;
+  range(minKey:Key, maxKey:Key, visit:TraverseCallback<Key, Value>, context?:any);
   pop(): Node<Key, Value>;
@@ -27,0 +29,0 @@ min(): Key;

index.js

@@ -375,3 +375,3 @@ function DEFAULT_COMPARE (a, b) { return a > b ? 1 : a < b ? -1 : 0; }
    * @param  {forEachCallback} callback
-   * @return {AVLTree}
+   * @return {SplayTree}
    */
@@ -406,3 +406,35 @@ forEach(callback) {
 
+
   /**
+   * Walk key range from `low` to `high`. Stops if `fn` returns a value.
+   * @param  {Key}      low
+   * @param  {Key}      high
+   * @param  {Function} fn
+   * @param  {*?}       ctx
+   * @return {SplayTree}
+   */
+  range(low, high, fn, ctx) {
+    const Q = [];
+    const compare = this._compare;
+    let node = this._root, cmp;
+
+    while (Q.length !== 0 || node) {
+      if (node) {
+        Q.push(node);
+        node = node.left;
+      } else {
+        node = Q.pop();
+        cmp = compare(node.key, high);
+        if (cmp > 0) {
+          break;
+        } else if (compare(node.key, low) >= 0) {
+          if (fn.call(ctx, node)) return this; // stop if smth is returned
+        }
+        node = node.right;
+      }
+    }
+    return this;
+  }
+
+  /**
    * Returns all keys in order
@@ -409,0 +441,0 @@ * @return {Array<Key>}

package.json

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

Readme.md

@@ -1,2 +0,2 @@
-# Splay tree [![npm version](https://badge.fury.io/js/splaytree.svg)](https://badge.fury.io/js/avl) [![CircleCI](https://circleci.com/gh/w8r/splay-tree.svg?style=svg)](https://circleci.com/gh/w8r/splay-tree)
+# 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)
 
@@ -51,2 +51,3 @@ [Splay-tree](https://en.wikipedia.org/wiki/Splay_tree): **[fast](#benchmarks)**(non-recursive) and **simple**(< 500 lines of code)
 * `tree.values():Array<*>` - Returns the array of data fields in order
+* `tree.range(lo, high, function(node) {} [, context]):Tree` - Walks the range of keys in order. Stops, if the visitor function returns a non-zero value.
 * `tree.pop():Node` - Removes smallest node
@@ -53,0 +54,0 @@ * `tree.min():key` - Returns min key

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

100009

increased by5.96%

Lines of code

1459

increased by6.57%

Number of lines in readme file

202

increased by0.5%

No dependency changes