diff options
Diffstat (limited to 'tools/node_modules/eslint/node_modules/functional-red-black-tree')
5 files changed, 1334 insertions, 0 deletions
diff --git a/tools/node_modules/eslint/node_modules/functional-red-black-tree/LICENSE b/tools/node_modules/eslint/node_modules/functional-red-black-tree/LICENSE new file mode 100644 index 0000000000..8ce206a845 --- /dev/null +++ b/tools/node_modules/eslint/node_modules/functional-red-black-tree/LICENSE @@ -0,0 +1,22 @@ + +The MIT License (MIT) + +Copyright (c) 2013 Mikola Lysenko + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. diff --git a/tools/node_modules/eslint/node_modules/functional-red-black-tree/README.md b/tools/node_modules/eslint/node_modules/functional-red-black-tree/README.md new file mode 100644 index 0000000000..edd19cbf31 --- /dev/null +++ b/tools/node_modules/eslint/node_modules/functional-red-black-tree/README.md @@ -0,0 +1,237 @@ +functional-red-black-tree +========================= +A [fully persistent](http://en.wikipedia.org/wiki/Persistent_data_structure) [red-black tree](http://en.wikipedia.org/wiki/Red%E2%80%93black_tree) written 100% in JavaScript. Works both in node.js and in the browser via [browserify](http://browserify.org/). + +Functional (or fully presistent) data structures allow for non-destructive updates. So if you insert an element into the tree, it returns a new tree with the inserted element rather than destructively updating the existing tree in place. Doing this requires using extra memory, and if one were naive it could cost as much as reallocating the entire tree. Instead, this data structure saves some memory by recycling references to previously allocated subtrees. This requires using only O(log(n)) additional memory per update instead of a full O(n) copy. + +Some advantages of this is that it is possible to apply insertions and removals to the tree while still iterating over previous versions of the tree. Functional and persistent data structures can also be useful in many geometric algorithms like point location within triangulations or ray queries, and can be used to analyze the history of executing various algorithms. This added power though comes at a cost, since it is generally a bit slower to use a functional data structure than an imperative version. However, if your application needs this behavior then you may consider using this module. + +# Install + + npm install functional-red-black-tree + +# Example + +Here is an example of some basic usage: + +```javascript +//Load the library +var createTree = require("functional-red-black-tree") + +//Create a tree +var t1 = createTree() + +//Insert some items into the tree +var t2 = t1.insert(1, "foo") +var t3 = t2.insert(2, "bar") + +//Remove something +var t4 = t3.remove(1) +``` + + +# API + +```javascript +var createTree = require("functional-red-black-tree") +``` + +## Overview + +- [Tree methods](#tree-methods) + - [`var tree = createTree([compare])`](#var-tree-=-createtreecompare) + - [`tree.keys`](#treekeys) + - [`tree.values`](#treevalues) + - [`tree.length`](#treelength) + - [`tree.get(key)`](#treegetkey) + - [`tree.insert(key, value)`](#treeinsertkey-value) + - [`tree.remove(key)`](#treeremovekey) + - [`tree.find(key)`](#treefindkey) + - [`tree.ge(key)`](#treegekey) + - [`tree.gt(key)`](#treegtkey) + - [`tree.lt(key)`](#treeltkey) + - [`tree.le(key)`](#treelekey) + - [`tree.at(position)`](#treeatposition) + - [`tree.begin`](#treebegin) + - [`tree.end`](#treeend) + - [`tree.forEach(visitor(key,value)[, lo[, hi]])`](#treeforEachvisitorkeyvalue-lo-hi) + - [`tree.root`](#treeroot) +- [Node properties](#node-properties) + - [`node.key`](#nodekey) + - [`node.value`](#nodevalue) + - [`node.left`](#nodeleft) + - [`node.right`](#noderight) +- [Iterator methods](#iterator-methods) + - [`iter.key`](#iterkey) + - [`iter.value`](#itervalue) + - [`iter.node`](#iternode) + - [`iter.tree`](#itertree) + - [`iter.index`](#iterindex) + - [`iter.valid`](#itervalid) + - [`iter.clone()`](#iterclone) + - [`iter.remove()`](#iterremove) + - [`iter.update(value)`](#iterupdatevalue) + - [`iter.next()`](#iternext) + - [`iter.prev()`](#iterprev) + - [`iter.hasNext`](#iterhasnext) + - [`iter.hasPrev`](#iterhasprev) + +## Tree methods + +### `var tree = createTree([compare])` +Creates an empty functional tree + +* `compare` is an optional comparison function, same semantics as array.sort() + +**Returns** An empty tree ordered by `compare` + +### `tree.keys` +A sorted array of all the keys in the tree + +### `tree.values` +An array array of all the values in the tree + +### `tree.length` +The number of items in the tree + +### `tree.get(key)` +Retrieves the value associated to the given key + +* `key` is the key of the item to look up + +**Returns** The value of the first node associated to `key` + +### `tree.insert(key, value)` +Creates a new tree with the new pair inserted. + +* `key` is the key of the item to insert +* `value` is the value of the item to insert + +**Returns** A new tree with `key` and `value` inserted + +### `tree.remove(key)` +Removes the first item with `key` in the tree + +* `key` is the key of the item to remove + +**Returns** A new tree with the given item removed if it exists + +### `tree.find(key)` +Returns an iterator pointing to the first item in the tree with `key`, otherwise `null`. + +### `tree.ge(key)` +Find the first item in the tree whose key is `>= key` + +* `key` is the key to search for + +**Returns** An iterator at the given element. + +### `tree.gt(key)` +Finds the first item in the tree whose key is `> key` + +* `key` is the key to search for + +**Returns** An iterator at the given element + +### `tree.lt(key)` +Finds the last item in the tree whose key is `< key` + +* `key` is the key to search for + +**Returns** An iterator at the given element + +### `tree.le(key)` +Finds the last item in the tree whose key is `<= key` + +* `key` is the key to search for + +**Returns** An iterator at the given element + +### `tree.at(position)` +Finds an iterator starting at the given element + +* `position` is the index at which the iterator gets created + +**Returns** An iterator starting at position + +### `tree.begin` +An iterator pointing to the first element in the tree + +### `tree.end` +An iterator pointing to the last element in the tree + +### `tree.forEach(visitor(key,value)[, lo[, hi]])` +Walks a visitor function over the nodes of the tree in order. + +* `visitor(key,value)` is a callback that gets executed on each node. If a truthy value is returned from the visitor, then iteration is stopped. +* `lo` is an optional start of the range to visit (inclusive) +* `hi` is an optional end of the range to visit (non-inclusive) + +**Returns** The last value returned by the callback + +### `tree.root` +Returns the root node of the tree + + +## Node properties +Each node of the tree has the following properties: + +### `node.key` +The key associated to the node + +### `node.value` +The value associated to the node + +### `node.left` +The left subtree of the node + +### `node.right` +The right subtree of the node + +## Iterator methods + +### `iter.key` +The key of the item referenced by the iterator + +### `iter.value` +The value of the item referenced by the iterator + +### `iter.node` +The value of the node at the iterator's current position. `null` is iterator is node valid. + +### `iter.tree` +The tree associated to the iterator + +### `iter.index` +Returns the position of this iterator in the sequence. + +### `iter.valid` +Checks if the iterator is valid + +### `iter.clone()` +Makes a copy of the iterator + +### `iter.remove()` +Removes the item at the position of the iterator + +**Returns** A new binary search tree with `iter`'s item removed + +### `iter.update(value)` +Updates the value of the node in the tree at this iterator + +**Returns** A new binary search tree with the corresponding node updated + +### `iter.next()` +Advances the iterator to the next position + +### `iter.prev()` +Moves the iterator backward one element + +### `iter.hasNext` +If true, then the iterator is not at the end of the sequence + +### `iter.hasPrev` +If true, then the iterator is not at the beginning of the sequence + +# Credits +(c) 2013 Mikola Lysenko. MIT License
\ No newline at end of file diff --git a/tools/node_modules/eslint/node_modules/functional-red-black-tree/bench/test.js b/tools/node_modules/eslint/node_modules/functional-red-black-tree/bench/test.js new file mode 100644 index 0000000000..41c5a31c3a --- /dev/null +++ b/tools/node_modules/eslint/node_modules/functional-red-black-tree/bench/test.js @@ -0,0 +1,11 @@ +"use strict" + +var createTree = require("../rbtree.js") + +var t = createTree() + +var s = Date.now() +for(var i=0; i<100000; ++i) { + t = t.insert(Math.random(), Math.random()) +} +console.log(Date.now() - s)
\ No newline at end of file diff --git a/tools/node_modules/eslint/node_modules/functional-red-black-tree/package.json b/tools/node_modules/eslint/node_modules/functional-red-black-tree/package.json new file mode 100644 index 0000000000..eb2cc4e421 --- /dev/null +++ b/tools/node_modules/eslint/node_modules/functional-red-black-tree/package.json @@ -0,0 +1,68 @@ +{ + "_from": "functional-red-black-tree@^1.0.1", + "_id": "functional-red-black-tree@1.0.1", + "_inBundle": false, + "_integrity": "sha1-GwqzvVU7Kg1jmdKcDj6gslIHgyc=", + "_location": "/eslint/functional-red-black-tree", + "_phantomChildren": {}, + "_requested": { + "type": "range", + "registry": true, + "raw": "functional-red-black-tree@^1.0.1", + "name": "functional-red-black-tree", + "escapedName": "functional-red-black-tree", + "rawSpec": "^1.0.1", + "saveSpec": null, + "fetchSpec": "^1.0.1" + }, + "_requiredBy": [ + "/eslint" + ], + "_resolved": "https://registry.npmjs.org/functional-red-black-tree/-/functional-red-black-tree-1.0.1.tgz", + "_shasum": "1b0ab3bd553b2a0d6399d29c0e3ea0b252078327", + "_spec": "functional-red-black-tree@^1.0.1", + "_where": "/Users/cjihrig/iojs/node/tools/eslint-tmp/node_modules/eslint", + "author": { + "name": "Mikola Lysenko" + }, + "bugs": { + "url": "https://github.com/mikolalysenko/functional-red-black-tree/issues" + }, + "bundleDependencies": false, + "dependencies": {}, + "deprecated": false, + "description": "A fully persistent balanced binary search tree", + "devDependencies": { + "iota-array": "^0.0.1", + "tape": "^2.12.0" + }, + "directories": { + "test": "test" + }, + "homepage": "https://github.com/mikolalysenko/functional-red-black-tree#readme", + "keywords": [ + "functional", + "red", + "black", + "tree", + "binary", + "search", + "balance", + "persistent", + "fully", + "dynamic", + "data", + "structure" + ], + "license": "MIT", + "main": "rbtree.js", + "name": "functional-red-black-tree", + "repository": { + "type": "git", + "url": "git://github.com/mikolalysenko/functional-red-black-tree.git" + }, + "scripts": { + "test": "tape test/*.js" + }, + "version": "1.0.1" +} diff --git a/tools/node_modules/eslint/node_modules/functional-red-black-tree/rbtree.js b/tools/node_modules/eslint/node_modules/functional-red-black-tree/rbtree.js new file mode 100644 index 0000000000..5a69a4090d --- /dev/null +++ b/tools/node_modules/eslint/node_modules/functional-red-black-tree/rbtree.js @@ -0,0 +1,996 @@ +"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) +}
\ No newline at end of file |