Comparing version 0.1.1 to 0.1.2
/** | ||
* 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>} |
/** | ||
* 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>} |
@@ -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; |
34
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>} |
{ | ||
"name": "splaytree", | ||
"version": "0.1.1", | ||
"version": "0.1.2", | ||
"author": "Alexander Milevski <info@w8r.name>", | ||
@@ -5,0 +5,0 @@ "license": "MIT", |
@@ -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 |
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
100009
1459
202