functional-red-black-tree
Advanced tools
Comparing version 0.0.0 to 1.0.0
{ | ||
"name": "functional-red-black-tree", | ||
"version": "0.0.0", | ||
"version": "1.0.0", | ||
"description": "A fully persistent balanced binary search tree", | ||
@@ -9,11 +9,9 @@ "main": "rbtree.js", | ||
}, | ||
"dependencies": { | ||
}, | ||
"dependencies": {}, | ||
"devDependencies": { | ||
"iota-array": "~0.0.1", | ||
"tape": "~1.1.1", | ||
"tap": "~0.4.4" | ||
"iota-array": "^0.0.1", | ||
"tape": "^2.12.0" | ||
}, | ||
"scripts": { | ||
"test": "tap test/*.js" | ||
"test": "tape test/*.js" | ||
}, | ||
@@ -20,0 +18,0 @@ "repository": { |
@@ -29,13 +29,2 @@ "use strict" | ||
function toJSON(node) { | ||
var result = { color: node._color ? "black" : "red", key: node.key, value: node.value } | ||
if(node.left) { | ||
result.left = toJSON(node.left) | ||
} | ||
if(node.right) { | ||
result.right = toJSON(node.right) | ||
} | ||
return result | ||
} | ||
function RedBlackTree(compare, root) { | ||
@@ -51,3 +40,3 @@ this._compare = compare | ||
var result = [] | ||
this.foreach(function(k,v) { | ||
this.forEach(function(k,v) { | ||
result.push(k) | ||
@@ -62,3 +51,3 @@ }) | ||
var result = [] | ||
this.foreach(function(k,v) { | ||
this.forEach(function(k,v) { | ||
result.push(v) | ||
@@ -296,3 +285,3 @@ }) | ||
proto.foreach = function(visit, lo, hi) { | ||
proto.forEach = function rbTreeForEach(visit, lo, hi) { | ||
if(!this.root) { | ||
@@ -611,3 +600,3 @@ return | ||
} | ||
stack[i-1] = s | ||
stack[i-1] = z | ||
return | ||
@@ -701,3 +690,3 @@ } | ||
} | ||
stack[i-1] = s | ||
stack[i-1] = z | ||
return | ||
@@ -704,0 +693,0 @@ } |
@@ -57,3 +57,3 @@ functional-red-black-tree | ||
- [`tree.end`](#treeend) | ||
- [`tree.foreach(visitor(key,value)[, lo[, hi]])`](#treeforeachvisitorkeyvalue-lo-hi) | ||
- [`tree.forEach(visitor(key,value)[, lo[, hi]])`](#treeforEachvisitorkeyvalue-lo-hi) | ||
- [`tree.root`](#treeroot) | ||
@@ -164,3 +164,3 @@ - [Node properties](#node-properties) | ||
### `tree.foreach(visitor(key,value)[, lo[, hi]])` | ||
### `tree.forEach(visitor(key,value)[, lo[, hi]])` | ||
Walks a visitor function over the nodes of the tree in order. | ||
@@ -167,0 +167,0 @@ |
@@ -74,3 +74,3 @@ "use strict" | ||
var ptr = 0 | ||
u.foreach(-Infinity, Infinity, function(k,v) { | ||
u.forEach(function(k,v) { | ||
t.equals(k, arr[ptr++]) | ||
@@ -111,3 +111,3 @@ }) | ||
var visit_vals = [] | ||
u.foreach(function(k,v) { | ||
u.forEach(function(k,v) { | ||
visit_keys.push(k) | ||
@@ -122,3 +122,3 @@ visit_vals.push(v) | ||
visit_vals = [] | ||
t.equals(u.foreach(function(k,v) { | ||
t.equals(u.forEach(function(k,v) { | ||
if(k === 5) { | ||
@@ -136,3 +136,3 @@ return 1000 | ||
visit_vals = [] | ||
u.foreach(function(k,v) { | ||
u.forEach(function(k,v) { | ||
visit_keys.push(k) | ||
@@ -147,3 +147,3 @@ visit_vals.push(v) | ||
visit_vals = [] | ||
t.equals(u.foreach(function(k,v) { | ||
t.equals(u.forEach(function(k,v) { | ||
if(k === 12) { | ||
@@ -162,3 +162,3 @@ return 1000 | ||
visit_vals = [] | ||
u.foreach(function(k,v) { | ||
u.forEach(function(k,v) { | ||
visit_keys.push(k) | ||
@@ -173,3 +173,3 @@ visit_vals.push(v) | ||
visit_vals = [] | ||
t.equals(u.foreach(function(k,v) { | ||
t.equals(u.forEach(function(k,v) { | ||
if(k === 12) { | ||
@@ -358,2 +358,49 @@ return 1000 | ||
t.end() | ||
}) | ||
}) | ||
tape("slab-sequence", function(t) { | ||
var tree = makeTree() | ||
tree=tree.insert(0, 0) | ||
checkTree(tree, t) | ||
t.same(tree.values, [0]) | ||
tree=tree.insert(1, 1) | ||
checkTree(tree, t) | ||
t.same(tree.values, [0,1]) | ||
tree=tree.insert(0.5, 2) | ||
checkTree(tree, t) | ||
t.same(tree.values, [0,2,1]) | ||
tree=tree.insert(0.25, 3) | ||
checkTree(tree, t) | ||
t.same(tree.values, [0,3,2,1]) | ||
tree=tree.remove(0) | ||
checkTree(tree, t) | ||
t.same(tree.values, [3,2,1]) | ||
tree=tree.insert(0.375, 4) | ||
checkTree(tree, t) | ||
t.same(tree.values, [3, 4, 2, 1]) | ||
tree=tree.remove(1) | ||
checkTree(tree, t) | ||
t.same(tree.values, [3,4,2]) | ||
tree=tree.remove(0.5) | ||
checkTree(tree, t) | ||
t.same(tree.values, [3,4]) | ||
tree=tree.remove(0.375) | ||
checkTree(tree, t) | ||
t.same(tree.values, [3]) | ||
tree=tree.remove(0.25) | ||
checkTree(tree, t) | ||
t.same(tree.values, []) | ||
t.end() | ||
}) |
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
No v1
QualityPackage is not semver >=1. This means it is not stable and does not support ^ ranges.
Found 1 instance in 1 package
41720
2
1287
1