| "use strict" |
| |
| module.exports = createRBTree |
| |
| var RED = 0 |
| var BLACK = 1 |
| |
| function RBNode(color, key, value, left, right, count) { |
| this._color = color |
| this.key = key |
| this.value = value |
| this.left = left |
| this.right = right |
| this._count = count |
| } |
| |
| function cloneNode(node) { |
| return new RBNode(node._color, node.key, node.value, node.left, node.right, node._count) |
| } |
| |
| function repaint(color, node) { |
| return new RBNode(color, node.key, node.value, node.left, node.right, node._count) |
| } |
| |
| function recount(node) { |
| node._count = 1 + (node.left ? node.left._count : 0) + (node.right ? node.right._count : 0) |
| } |
| |
| function RedBlackTree(compare, root) { |
| this._compare = compare |
| this.root = root |
| } |
| |
| var proto = RedBlackTree.prototype |
| |
| Object.defineProperty(proto, "keys", { |
| get: function() { |
| var result = [] |
| this.forEach(function(k,v) { |
| result.push(k) |
| }) |
| return result |
| } |
| }) |
| |
| Object.defineProperty(proto, "values", { |
| get: function() { |
| var result = [] |
| this.forEach(function(k,v) { |
| result.push(v) |
| }) |
| return result |
| } |
| }) |
| |
| //Returns the number of nodes in the tree |
| Object.defineProperty(proto, "length", { |
| get: function() { |
| if(this.root) { |
| return this.root._count |
| } |
| return 0 |
| } |
| }) |
| |
| //Insert a new item into the tree |
| proto.insert = function(key, value) { |
| var cmp = this._compare |
| //Find point to insert new node at |
| var n = this.root |
| var n_stack = [] |
| var d_stack = [] |
| while(n) { |
| var d = cmp(key, n.key) |
| n_stack.push(n) |
| d_stack.push(d) |
| if(d <= 0) { |
| n = n.left |
| } else { |
| n = n.right |
| } |
| } |
| //Rebuild path to leaf node |
| n_stack.push(new RBNode(RED, key, value, null, null, 1)) |
| for(var s=n_stack.length-2; s>=0; --s) { |
| var n = n_stack[s] |
| if(d_stack[s] <= 0) { |
| n_stack[s] = new RBNode(n._color, n.key, n.value, n_stack[s+1], n.right, n._count+1) |
| } else { |
| n_stack[s] = new RBNode(n._color, n.key, n.value, n.left, n_stack[s+1], n._count+1) |
| } |
| } |
| //Rebalance tree using rotations |
| //console.log("start insert", key, d_stack) |
| for(var s=n_stack.length-1; s>1; --s) { |
| var p = n_stack[s-1] |
| var n = n_stack[s] |
| if(p._color === BLACK || n._color === BLACK) { |
| break |
| } |
| var pp = n_stack[s-2] |
| if(pp.left === p) { |
| if(p.left === n) { |
| var y = pp.right |
| if(y && y._color === RED) { |
| //console.log("LLr") |
| p._color = BLACK |
| pp.right = repaint(BLACK, y) |
| pp._color = RED |
| s -= 1 |
| } else { |
| //console.log("LLb") |
| pp._color = RED |
| pp.left = p.right |
| p._color = BLACK |
| p.right = pp |
| n_stack[s-2] = p |
| n_stack[s-1] = n |
| recount(pp) |
| recount(p) |
| if(s >= 3) { |
| var ppp = n_stack[s-3] |
| if(ppp.left === pp) { |
| ppp.left = p |
| } else { |
| ppp.right = p |
| } |
| } |
| break |
| } |
| } else { |
| var y = pp.right |
| if(y && y._color === RED) { |
| //console.log("LRr") |
| p._color = BLACK |
| pp.right = repaint(BLACK, y) |
| pp._color = RED |
| s -= 1 |
| } else { |
| //console.log("LRb") |
| p.right = n.left |
| pp._color = RED |
| pp.left = n.right |
| n._color = BLACK |
| n.left = p |
| n.right = pp |
| n_stack[s-2] = n |
| n_stack[s-1] = p |
| recount(pp) |
| recount(p) |
| recount(n) |
| if(s >= 3) { |
| var ppp = n_stack[s-3] |
| if(ppp.left === pp) { |
| ppp.left = n |
| } else { |
| ppp.right = n |
| } |
| } |
| break |
| } |
| } |
| } else { |
| if(p.right === n) { |
| var y = pp.left |
| if(y && y._color === RED) { |
| //console.log("RRr", y.key) |
| p._color = BLACK |
| pp.left = repaint(BLACK, y) |
| pp._color = RED |
| s -= 1 |
| } else { |
| //console.log("RRb") |
| pp._color = RED |
| pp.right = p.left |
| p._color = BLACK |
| p.left = pp |
| n_stack[s-2] = p |
| n_stack[s-1] = n |
| recount(pp) |
| recount(p) |
| if(s >= 3) { |
| var ppp = n_stack[s-3] |
| if(ppp.right === pp) { |
| ppp.right = p |
| } else { |
| ppp.left = p |
| } |
| } |
| break |
| } |
| } else { |
| var y = pp.left |
| if(y && y._color === RED) { |
| //console.log("RLr") |
| p._color = BLACK |
| pp.left = repaint(BLACK, y) |
| pp._color = RED |
| s -= 1 |
| } else { |
| //console.log("RLb") |
| p.left = n.right |
| pp._color = RED |
| pp.right = n.left |
| n._color = BLACK |
| n.right = p |
| n.left = pp |
| n_stack[s-2] = n |
| n_stack[s-1] = p |
| recount(pp) |
| recount(p) |
| recount(n) |
| if(s >= 3) { |
| var ppp = n_stack[s-3] |
| if(ppp.right === pp) { |
| ppp.right = n |
| } else { |
| ppp.left = n |
| } |
| } |
| break |
| } |
| } |
| } |
| } |
| //Return new tree |
| n_stack[0]._color = BLACK |
| return new RedBlackTree(cmp, n_stack[0]) |
| } |
| |
| |
| //Visit all nodes inorder |
| function doVisitFull(visit, node) { |
| if(node.left) { |
| var v = doVisitFull(visit, node.left) |
| if(v) { return v } |
| } |
| var v = visit(node.key, node.value) |
| if(v) { return v } |
| if(node.right) { |
| return doVisitFull(visit, node.right) |
| } |
| } |
| |
| //Visit half nodes in order |
| function doVisitHalf(lo, compare, visit, node) { |
| var l = compare(lo, node.key) |
| if(l <= 0) { |
| if(node.left) { |
| var v = doVisitHalf(lo, compare, visit, node.left) |
| if(v) { return v } |
| } |
| var v = visit(node.key, node.value) |
| if(v) { return v } |
| } |
| if(node.right) { |
| return doVisitHalf(lo, compare, visit, node.right) |
| } |
| } |
| |
| //Visit all nodes within a range |
| function doVisit(lo, hi, compare, visit, node) { |
| var l = compare(lo, node.key) |
| var h = compare(hi, node.key) |
| var v |
| if(l <= 0) { |
| if(node.left) { |
| v = doVisit(lo, hi, compare, visit, node.left) |
| if(v) { return v } |
| } |
| if(h > 0) { |
| v = visit(node.key, node.value) |
| if(v) { return v } |
| } |
| } |
| if(h > 0 && node.right) { |
| return doVisit(lo, hi, compare, visit, node.right) |
| } |
| } |
| |
| |
| proto.forEach = function rbTreeForEach(visit, lo, hi) { |
| if(!this.root) { |
| return |
| } |
| switch(arguments.length) { |
| case 1: |
| return doVisitFull(visit, this.root) |
| break |
| |
| case 2: |
| return doVisitHalf(lo, this._compare, visit, this.root) |
| break |
| |
| case 3: |
| if(this._compare(lo, hi) >= 0) { |
| return |
| } |
| return doVisit(lo, hi, this._compare, visit, this.root) |
| break |
| } |
| } |
| |
| //First item in list |
| Object.defineProperty(proto, "begin", { |
| get: function() { |
| var stack = [] |
| var n = this.root |
| while(n) { |
| stack.push(n) |
| n = n.left |
| } |
| return new RedBlackTreeIterator(this, stack) |
| } |
| }) |
| |
| //Last item in list |
| Object.defineProperty(proto, "end", { |
| get: function() { |
| var stack = [] |
| var n = this.root |
| while(n) { |
| stack.push(n) |
| n = n.right |
| } |
| return new RedBlackTreeIterator(this, stack) |
| } |
| }) |
| |
| //Find the ith item in the tree |
| proto.at = function(idx) { |
| if(idx < 0) { |
| return new RedBlackTreeIterator(this, []) |
| } |
| var n = this.root |
| var stack = [] |
| while(true) { |
| stack.push(n) |
| if(n.left) { |
| if(idx < n.left._count) { |
| n = n.left |
| continue |
| } |
| idx -= n.left._count |
| } |
| if(!idx) { |
| return new RedBlackTreeIterator(this, stack) |
| } |
| idx -= 1 |
| if(n.right) { |
| if(idx >= n.right._count) { |
| break |
| } |
| n = n.right |
| } else { |
| break |
| } |
| } |
| return new RedBlackTreeIterator(this, []) |
| } |
| |
| proto.ge = function(key) { |
| var cmp = this._compare |
| var n = this.root |
| var stack = [] |
| var last_ptr = 0 |
| while(n) { |
| var d = cmp(key, n.key) |
| stack.push(n) |
| if(d <= 0) { |
| last_ptr = stack.length |
| } |
| if(d <= 0) { |
| n = n.left |
| } else { |
| n = n.right |
| } |
| } |
| stack.length = last_ptr |
| return new RedBlackTreeIterator(this, stack) |
| } |
| |
| proto.gt = function(key) { |
| var cmp = this._compare |
| var n = this.root |
| var stack = [] |
| var last_ptr = 0 |
| while(n) { |
| var d = cmp(key, n.key) |
| stack.push(n) |
| if(d < 0) { |
| last_ptr = stack.length |
| } |
| if(d < 0) { |
| n = n.left |
| } else { |
| n = n.right |
| } |
| } |
| stack.length = last_ptr |
| return new RedBlackTreeIterator(this, stack) |
| } |
| |
| proto.lt = function(key) { |
| var cmp = this._compare |
| var n = this.root |
| var stack = [] |
| var last_ptr = 0 |
| while(n) { |
| var d = cmp(key, n.key) |
| stack.push(n) |
| if(d > 0) { |
| last_ptr = stack.length |
| } |
| if(d <= 0) { |
| n = n.left |
| } else { |
| n = n.right |
| } |
| } |
| stack.length = last_ptr |
| return new RedBlackTreeIterator(this, stack) |
| } |
| |
| proto.le = function(key) { |
| var cmp = this._compare |
| var n = this.root |
| var stack = [] |
| var last_ptr = 0 |
| while(n) { |
| var d = cmp(key, n.key) |
| stack.push(n) |
| if(d >= 0) { |
| last_ptr = stack.length |
| } |
| if(d < 0) { |
| n = n.left |
| } else { |
| n = n.right |
| } |
| } |
| stack.length = last_ptr |
| return new RedBlackTreeIterator(this, stack) |
| } |
| |
| //Finds the item with key if it exists |
| proto.find = function(key) { |
| var cmp = this._compare |
| var n = this.root |
| var stack = [] |
| while(n) { |
| var d = cmp(key, n.key) |
| stack.push(n) |
| if(d === 0) { |
| return new RedBlackTreeIterator(this, stack) |
| } |
| if(d <= 0) { |
| n = n.left |
| } else { |
| n = n.right |
| } |
| } |
| return new RedBlackTreeIterator(this, []) |
| } |
| |
| //Removes item with key from tree |
| proto.remove = function(key) { |
| var iter = this.find(key) |
| if(iter) { |
| return iter.remove() |
| } |
| return this |
| } |
| |
| //Returns the item at `key` |
| proto.get = function(key) { |
| var cmp = this._compare |
| var n = this.root |
| while(n) { |
| var d = cmp(key, n.key) |
| if(d === 0) { |
| return n.value |
| } |
| if(d <= 0) { |
| n = n.left |
| } else { |
| n = n.right |
| } |
| } |
| return |
| } |
| |
| //Iterator for red black tree |
| function RedBlackTreeIterator(tree, stack) { |
| this.tree = tree |
| this._stack = stack |
| } |
| |
| var iproto = RedBlackTreeIterator.prototype |
| |
| //Test if iterator is valid |
| Object.defineProperty(iproto, "valid", { |
| get: function() { |
| return this._stack.length > 0 |
| } |
| }) |
| |
| //Node of the iterator |
| Object.defineProperty(iproto, "node", { |
| get: function() { |
| if(this._stack.length > 0) { |
| return this._stack[this._stack.length-1] |
| } |
| return null |
| }, |
| enumerable: true |
| }) |
| |
| //Makes a copy of an iterator |
| iproto.clone = function() { |
| return new RedBlackTreeIterator(this.tree, this._stack.slice()) |
| } |
| |
| //Swaps two nodes |
| function swapNode(n, v) { |
| n.key = v.key |
| n.value = v.value |
| n.left = v.left |
| n.right = v.right |
| n._color = v._color |
| n._count = v._count |
| } |
| |
| //Fix up a double black node in a tree |
| function fixDoubleBlack(stack) { |
| var n, p, s, z |
| for(var i=stack.length-1; i>=0; --i) { |
| n = stack[i] |
| if(i === 0) { |
| n._color = BLACK |
| return |
| } |
| //console.log("visit node:", n.key, i, stack[i].key, stack[i-1].key) |
| p = stack[i-1] |
| if(p.left === n) { |
| //console.log("left child") |
| s = p.right |
| if(s.right && s.right._color === RED) { |
| //console.log("case 1: right sibling child red") |
| s = p.right = cloneNode(s) |
| z = s.right = cloneNode(s.right) |
| p.right = s.left |
| s.left = p |
| s.right = z |
| s._color = p._color |
| n._color = BLACK |
| p._color = BLACK |
| z._color = BLACK |
| recount(p) |
| recount(s) |
| if(i > 1) { |
| var pp = stack[i-2] |
| if(pp.left === p) { |
| pp.left = s |
| } else { |
| pp.right = s |
| } |
| } |
| stack[i-1] = s |
| return |
| } else if(s.left && s.left._color === RED) { |
| //console.log("case 1: left sibling child red") |
| s = p.right = cloneNode(s) |
| z = s.left = cloneNode(s.left) |
| p.right = z.left |
| s.left = z.right |
| z.left = p |
| z.right = s |
| z._color = p._color |
| p._color = BLACK |
| s._color = BLACK |
| n._color = BLACK |
| recount(p) |
| recount(s) |
| recount(z) |
| if(i > 1) { |
| var pp = stack[i-2] |
| if(pp.left === p) { |
| pp.left = z |
| } else { |
| pp.right = z |
| } |
| } |
| stack[i-1] = z |
| return |
| } |
| if(s._color === BLACK) { |
| if(p._color === RED) { |
| //console.log("case 2: black sibling, red parent", p.right.value) |
| p._color = BLACK |
| p.right = repaint(RED, s) |
| return |
| } else { |
| //console.log("case 2: black sibling, black parent", p.right.value) |
| p.right = repaint(RED, s) |
| continue |
| } |
| } else { |
| //console.log("case 3: red sibling") |
| s = cloneNode(s) |
| p.right = s.left |
| s.left = p |
| s._color = p._color |
| p._color = RED |
| recount(p) |
| recount(s) |
| if(i > 1) { |
| var pp = stack[i-2] |
| if(pp.left === p) { |
| pp.left = s |
| } else { |
| pp.right = s |
| } |
| } |
| stack[i-1] = s |
| stack[i] = p |
| if(i+1 < stack.length) { |
| stack[i+1] = n |
| } else { |
| stack.push(n) |
| } |
| i = i+2 |
| } |
| } else { |
| //console.log("right child") |
| s = p.left |
| if(s.left && s.left._color === RED) { |
| //console.log("case 1: left sibling child red", p.value, p._color) |
| s = p.left = cloneNode(s) |
| z = s.left = cloneNode(s.left) |
| p.left = s.right |
| s.right = p |
| s.left = z |
| s._color = p._color |
| n._color = BLACK |
| p._color = BLACK |
| z._color = BLACK |
| recount(p) |
| recount(s) |
| if(i > 1) { |
| var pp = stack[i-2] |
| if(pp.right === p) { |
| pp.right = s |
| } else { |
| pp.left = s |
| } |
| } |
| stack[i-1] = s |
| return |
| } else if(s.right && s.right._color === RED) { |
| //console.log("case 1: right sibling child red") |
| s = p.left = cloneNode(s) |
| z = s.right = cloneNode(s.right) |
| p.left = z.right |
| s.right = z.left |
| z.right = p |
| z.left = s |
| z._color = p._color |
| p._color = BLACK |
| s._color = BLACK |
| n._color = BLACK |
| recount(p) |
| recount(s) |
| recount(z) |
| if(i > 1) { |
| var pp = stack[i-2] |
| if(pp.right === p) { |
| pp.right = z |
| } else { |
| pp.left = z |
| } |
| } |
| stack[i-1] = z |
| return |
| } |
| if(s._color === BLACK) { |
| if(p._color === RED) { |
| //console.log("case 2: black sibling, red parent") |
| p._color = BLACK |
| p.left = repaint(RED, s) |
| return |
| } else { |
| //console.log("case 2: black sibling, black parent") |
| p.left = repaint(RED, s) |
| continue |
| } |
| } else { |
| //console.log("case 3: red sibling") |
| s = cloneNode(s) |
| p.left = s.right |
| s.right = p |
| s._color = p._color |
| p._color = RED |
| recount(p) |
| recount(s) |
| if(i > 1) { |
| var pp = stack[i-2] |
| if(pp.right === p) { |
| pp.right = s |
| } else { |
| pp.left = s |
| } |
| } |
| stack[i-1] = s |
| stack[i] = p |
| if(i+1 < stack.length) { |
| stack[i+1] = n |
| } else { |
| stack.push(n) |
| } |
| i = i+2 |
| } |
| } |
| } |
| } |
| |
| //Removes item at iterator from tree |
| iproto.remove = function() { |
| var stack = this._stack |
| if(stack.length === 0) { |
| return this.tree |
| } |
| //First copy path to node |
| var cstack = new Array(stack.length) |
| var n = stack[stack.length-1] |
| cstack[cstack.length-1] = new RBNode(n._color, n.key, n.value, n.left, n.right, n._count) |
| for(var i=stack.length-2; i>=0; --i) { |
| var n = stack[i] |
| if(n.left === stack[i+1]) { |
| cstack[i] = new RBNode(n._color, n.key, n.value, cstack[i+1], n.right, n._count) |
| } else { |
| cstack[i] = new RBNode(n._color, n.key, n.value, n.left, cstack[i+1], n._count) |
| } |
| } |
| |
| //Get node |
| n = cstack[cstack.length-1] |
| //console.log("start remove: ", n.value) |
| |
| //If not leaf, then swap with previous node |
| if(n.left && n.right) { |
| //console.log("moving to leaf") |
| |
| //First walk to previous leaf |
| var split = cstack.length |
| n = n.left |
| while(n.right) { |
| cstack.push(n) |
| n = n.right |
| } |
| //Copy path to leaf |
| var v = cstack[split-1] |
| cstack.push(new RBNode(n._color, v.key, v.value, n.left, n.right, n._count)) |
| cstack[split-1].key = n.key |
| cstack[split-1].value = n.value |
| |
| //Fix up stack |
| for(var i=cstack.length-2; i>=split; --i) { |
| n = cstack[i] |
| cstack[i] = new RBNode(n._color, n.key, n.value, n.left, cstack[i+1], n._count) |
| } |
| cstack[split-1].left = cstack[split] |
| } |
| //console.log("stack=", cstack.map(function(v) { return v.value })) |
| |
| //Remove leaf node |
| n = cstack[cstack.length-1] |
| if(n._color === RED) { |
| //Easy case: removing red leaf |
| //console.log("RED leaf") |
| var p = cstack[cstack.length-2] |
| if(p.left === n) { |
| p.left = null |
| } else if(p.right === n) { |
| p.right = null |
| } |
| cstack.pop() |
| for(var i=0; i<cstack.length; ++i) { |
| cstack[i]._count-- |
| } |
| return new RedBlackTree(this.tree._compare, cstack[0]) |
| } else { |
| if(n.left || n.right) { |
| //Second easy case: Single child black parent |
| //console.log("BLACK single child") |
| if(n.left) { |
| swapNode(n, n.left) |
| } else if(n.right) { |
| swapNode(n, n.right) |
| } |
| //Child must be red, so repaint it black to balance color |
| n._color = BLACK |
| for(var i=0; i<cstack.length-1; ++i) { |
| cstack[i]._count-- |
| } |
| return new RedBlackTree(this.tree._compare, cstack[0]) |
| } else if(cstack.length === 1) { |
| //Third easy case: root |
| //console.log("ROOT") |
| return new RedBlackTree(this.tree._compare, null) |
| } else { |
| //Hard case: Repaint n, and then do some nasty stuff |
| //console.log("BLACK leaf no children") |
| for(var i=0; i<cstack.length; ++i) { |
| cstack[i]._count-- |
| } |
| var parent = cstack[cstack.length-2] |
| fixDoubleBlack(cstack) |
| //Fix up links |
| if(parent.left === n) { |
| parent.left = null |
| } else { |
| parent.right = null |
| } |
| } |
| } |
| return new RedBlackTree(this.tree._compare, cstack[0]) |
| } |
| |
| //Returns key |
| Object.defineProperty(iproto, "key", { |
| get: function() { |
| if(this._stack.length > 0) { |
| return this._stack[this._stack.length-1].key |
| } |
| return |
| }, |
| enumerable: true |
| }) |
| |
| //Returns value |
| Object.defineProperty(iproto, "value", { |
| get: function() { |
| if(this._stack.length > 0) { |
| return this._stack[this._stack.length-1].value |
| } |
| return |
| }, |
| enumerable: true |
| }) |
| |
| |
| //Returns the position of this iterator in the sorted list |
| Object.defineProperty(iproto, "index", { |
| get: function() { |
| var idx = 0 |
| var stack = this._stack |
| if(stack.length === 0) { |
| var r = this.tree.root |
| if(r) { |
| return r._count |
| } |
| return 0 |
| } else if(stack[stack.length-1].left) { |
| idx = stack[stack.length-1].left._count |
| } |
| for(var s=stack.length-2; s>=0; --s) { |
| if(stack[s+1] === stack[s].right) { |
| ++idx |
| if(stack[s].left) { |
| idx += stack[s].left._count |
| } |
| } |
| } |
| return idx |
| }, |
| enumerable: true |
| }) |
| |
| //Advances iterator to next element in list |
| iproto.next = function() { |
| var stack = this._stack |
| if(stack.length === 0) { |
| return |
| } |
| var n = stack[stack.length-1] |
| if(n.right) { |
| n = n.right |
| while(n) { |
| stack.push(n) |
| n = n.left |
| } |
| } else { |
| stack.pop() |
| while(stack.length > 0 && stack[stack.length-1].right === n) { |
| n = stack[stack.length-1] |
| stack.pop() |
| } |
| } |
| } |
| |
| //Checks if iterator is at end of tree |
| Object.defineProperty(iproto, "hasNext", { |
| get: function() { |
| var stack = this._stack |
| if(stack.length === 0) { |
| return false |
| } |
| if(stack[stack.length-1].right) { |
| return true |
| } |
| for(var s=stack.length-1; s>0; --s) { |
| if(stack[s-1].left === stack[s]) { |
| return true |
| } |
| } |
| return false |
| } |
| }) |
| |
| //Update value |
| iproto.update = function(value) { |
| var stack = this._stack |
| if(stack.length === 0) { |
| throw new Error("Can't update empty node!") |
| } |
| var cstack = new Array(stack.length) |
| var n = stack[stack.length-1] |
| cstack[cstack.length-1] = new RBNode(n._color, n.key, value, n.left, n.right, n._count) |
| for(var i=stack.length-2; i>=0; --i) { |
| n = stack[i] |
| if(n.left === stack[i+1]) { |
| cstack[i] = new RBNode(n._color, n.key, n.value, cstack[i+1], n.right, n._count) |
| } else { |
| cstack[i] = new RBNode(n._color, n.key, n.value, n.left, cstack[i+1], n._count) |
| } |
| } |
| return new RedBlackTree(this.tree._compare, cstack[0]) |
| } |
| |
| //Moves iterator backward one element |
| iproto.prev = function() { |
| var stack = this._stack |
| if(stack.length === 0) { |
| return |
| } |
| var n = stack[stack.length-1] |
| if(n.left) { |
| n = n.left |
| while(n) { |
| stack.push(n) |
| n = n.right |
| } |
| } else { |
| stack.pop() |
| while(stack.length > 0 && stack[stack.length-1].left === n) { |
| n = stack[stack.length-1] |
| stack.pop() |
| } |
| } |
| } |
| |
| //Checks if iterator is at start of tree |
| Object.defineProperty(iproto, "hasPrev", { |
| get: function() { |
| var stack = this._stack |
| if(stack.length === 0) { |
| return false |
| } |
| if(stack[stack.length-1].left) { |
| return true |
| } |
| for(var s=stack.length-1; s>0; --s) { |
| if(stack[s-1].right === stack[s]) { |
| return true |
| } |
| } |
| return false |
| } |
| }) |
| |
| //Default comparison function |
| function defaultCompare(a, b) { |
| if(a < b) { |
| return -1 |
| } |
| if(a > b) { |
| return 1 |
| } |
| return 0 |
| } |
| |
| //Build a tree |
| function createRBTree(compare) { |
| return new RedBlackTree(compare || defaultCompare, null) |
| } |
