Comparing version 3.1.0 to 3.1.1
/** | ||
* splaytree v3.1.0 | ||
* splaytree v3.1.1 | ||
* Fast Splay tree for Node and browser | ||
@@ -10,2 +10,45 @@ * | ||
/*! ***************************************************************************** | ||
Copyright (c) Microsoft Corporation. All rights reserved. | ||
Licensed under the Apache License, Version 2.0 (the "License"); you may not use | ||
this file except in compliance with the License. You may obtain a copy of the | ||
License at http://www.apache.org/licenses/LICENSE-2.0 | ||
THIS CODE IS PROVIDED ON AN *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY | ||
KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED | ||
WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE, | ||
MERCHANTABLITY OR NON-INFRINGEMENT. | ||
See the Apache Version 2.0 License for specific language governing permissions | ||
and limitations under the License. | ||
***************************************************************************** */ | ||
function __generator(thisArg, body) { | ||
var _ = { label: 0, sent: function() { if (t[0] & 1) throw t[1]; return t[1]; }, trys: [], ops: [] }, f, y, t, g; | ||
return g = { next: verb(0), "throw": verb(1), "return": verb(2) }, typeof Symbol === "function" && (g[Symbol.iterator] = function() { return this; }), g; | ||
function verb(n) { return function (v) { return step([n, v]); }; } | ||
function step(op) { | ||
if (f) throw new TypeError("Generator is already executing."); | ||
while (_) try { | ||
if (f = 1, y && (t = op[0] & 2 ? y["return"] : op[0] ? y["throw"] || ((t = y["return"]) && t.call(y), 0) : y.next) && !(t = t.call(y, op[1])).done) return t; | ||
if (y = 0, t) op = [op[0] & 2, t.value]; | ||
switch (op[0]) { | ||
case 0: case 1: t = op; break; | ||
case 4: _.label++; return { value: op[1], done: false }; | ||
case 5: _.label++; y = op[1]; op = [0]; continue; | ||
case 7: op = _.ops.pop(); _.trys.pop(); continue; | ||
default: | ||
if (!(t = _.trys, t = t.length > 0 && t[t.length - 1]) && (op[0] === 6 || op[0] === 2)) { _ = 0; continue; } | ||
if (op[0] === 3 && (!t || (op[1] > t[0] && op[1] < t[3]))) { _.label = op[1]; break; } | ||
if (op[0] === 6 && _.label < t[1]) { _.label = t[1]; t = op; break; } | ||
if (t && _.label < t[2]) { _.label = t[2]; _.ops.push(op); break; } | ||
if (t[2]) _.ops.pop(); | ||
_.trys.pop(); continue; | ||
} | ||
op = body.call(thisArg, _); | ||
} catch (e) { op = [6, e]; y = 0; } finally { f = t = 0; } | ||
if (op[0] & 5) throw op[1]; return { value: op[0] ? op[1] : void 0, done: true }; | ||
} | ||
} | ||
var Node = /** @class */ (function () { | ||
@@ -502,2 +545,20 @@ function Node(key, data) { | ||
}; | ||
Tree.prototype[Symbol.iterator] = function () { | ||
var n; | ||
return __generator(this, function (_a) { | ||
switch (_a.label) { | ||
case 0: | ||
n = this.minNode(); | ||
_a.label = 1; | ||
case 1: | ||
if (!n) return [3 /*break*/, 3]; | ||
return [4 /*yield*/, n]; | ||
case 2: | ||
_a.sent(); | ||
n = this.next(n); | ||
return [3 /*break*/, 1]; | ||
case 3: return [2 /*return*/]; | ||
} | ||
}); | ||
}; | ||
return Tree; | ||
@@ -504,0 +565,0 @@ }()); |
1269
dist/splay.js
/** | ||
* splaytree v3.1.0 | ||
* splaytree v3.1.1 | ||
* Fast Splay tree for Node and browser | ||
@@ -11,611 +11,672 @@ * | ||
(function (global, factory) { | ||
typeof exports === 'object' && typeof module !== 'undefined' ? module.exports = factory() : | ||
typeof define === 'function' && define.amd ? define(factory) : | ||
(global.SplayTree = factory()); | ||
typeof exports === 'object' && typeof module !== 'undefined' ? module.exports = factory() : | ||
typeof define === 'function' && define.amd ? define(factory) : | ||
(global.SplayTree = factory()); | ||
}(this, (function () { 'use strict'; | ||
var Node = /** @class */ (function () { | ||
function Node(key, data) { | ||
this.next = null; | ||
this.key = key; | ||
this.data = data; | ||
this.left = null; | ||
this.right = null; | ||
} | ||
return Node; | ||
}()); | ||
/*! ***************************************************************************** | ||
Copyright (c) Microsoft Corporation. All rights reserved. | ||
Licensed under the Apache License, Version 2.0 (the "License"); you may not use | ||
this file except in compliance with the License. You may obtain a copy of the | ||
License at http://www.apache.org/licenses/LICENSE-2.0 | ||
/* follows "An implementation of top-down splaying" | ||
* by D. Sleator <sleator@cs.cmu.edu> March 1992 | ||
*/ | ||
function DEFAULT_COMPARE(a, b) { | ||
return a > b ? 1 : a < b ? -1 : 0; | ||
} | ||
/** | ||
* Simple top down splay, not requiring i to be in the tree t. | ||
*/ | ||
function splay(i, t, comparator) { | ||
var N = new Node(null, null); | ||
var l = N; | ||
var r = N; | ||
while (true) { | ||
var cmp = comparator(i, t.key); | ||
//if (i < t.key) { | ||
if (cmp < 0) { | ||
if (t.left === null) | ||
break; | ||
//if (i < t.left.key) { | ||
if (comparator(i, t.left.key) < 0) { | ||
var y = t.left; /* rotate right */ | ||
t.left = y.right; | ||
y.right = t; | ||
t = y; | ||
if (t.left === null) | ||
break; | ||
} | ||
r.left = t; /* link right */ | ||
r = t; | ||
t = t.left; | ||
//} else if (i > t.key) { | ||
} | ||
else if (cmp > 0) { | ||
if (t.right === null) | ||
break; | ||
//if (i > t.right.key) { | ||
if (comparator(i, t.right.key) > 0) { | ||
var y = t.right; /* rotate left */ | ||
t.right = y.left; | ||
y.left = t; | ||
t = y; | ||
if (t.right === null) | ||
break; | ||
} | ||
l.right = t; /* link left */ | ||
l = t; | ||
t = t.right; | ||
} | ||
else | ||
break; | ||
} | ||
/* assemble */ | ||
l.right = t.left; | ||
r.left = t.right; | ||
t.left = N.right; | ||
t.right = N.left; | ||
return t; | ||
} | ||
function insert(i, data, t, comparator) { | ||
var node = new Node(i, data); | ||
if (t === null) { | ||
node.left = node.right = null; | ||
return node; | ||
} | ||
t = splay(i, t, comparator); | ||
var cmp = comparator(i, t.key); | ||
if (cmp < 0) { | ||
node.left = t.left; | ||
node.right = t; | ||
t.left = null; | ||
} | ||
else if (cmp >= 0) { | ||
node.right = t.right; | ||
node.left = t; | ||
t.right = null; | ||
} | ||
return node; | ||
} | ||
function split(key, v, comparator) { | ||
var left = null; | ||
var right = null; | ||
if (v) { | ||
v = splay(key, v, comparator); | ||
var cmp = comparator(v.key, key); | ||
if (cmp === 0) { | ||
left = v.left; | ||
right = v.right; | ||
} | ||
else if (cmp < 0) { | ||
right = v.right; | ||
v.right = null; | ||
left = v; | ||
} | ||
else { | ||
left = v.left; | ||
v.left = null; | ||
right = v; | ||
} | ||
} | ||
return { left: left, right: right }; | ||
} | ||
function merge(left, right, comparator) { | ||
if (right === null) | ||
return left; | ||
if (left === null) | ||
return right; | ||
right = splay(left.key, right, comparator); | ||
right.left = left; | ||
return right; | ||
} | ||
/** | ||
* Prints level of the tree | ||
*/ | ||
function printRow(root, prefix, isTail, out, printNode) { | ||
if (root) { | ||
out("" + prefix + (isTail ? '└── ' : '├── ') + printNode(root) + "\n"); | ||
var indent = prefix + (isTail ? ' ' : '│ '); | ||
if (root.left) | ||
printRow(root.left, indent, false, out, printNode); | ||
if (root.right) | ||
printRow(root.right, indent, true, out, printNode); | ||
} | ||
} | ||
var Tree = /** @class */ (function () { | ||
function Tree(comparator) { | ||
if (comparator === void 0) { comparator = DEFAULT_COMPARE; } | ||
this._root = null; | ||
this._size = 0; | ||
this._comparator = comparator; | ||
} | ||
/** | ||
* Inserts a key, allows duplicates | ||
*/ | ||
Tree.prototype.insert = function (key, data) { | ||
this._size++; | ||
return this._root = insert(key, data, this._root, this._comparator); | ||
}; | ||
/** | ||
* Adds a key, if it is not present in the tree | ||
*/ | ||
Tree.prototype.add = function (key, data) { | ||
var node = new Node(key, data); | ||
if (this._root === null) { | ||
node.left = node.right = null; | ||
this._size++; | ||
this._root = node; | ||
} | ||
var comparator = this._comparator; | ||
var t = splay(key, this._root, comparator); | ||
var cmp = comparator(key, t.key); | ||
if (cmp === 0) | ||
this._root = t; | ||
else { | ||
if (cmp < 0) { | ||
node.left = t.left; | ||
node.right = t; | ||
t.left = null; | ||
} | ||
else if (cmp > 0) { | ||
node.right = t.right; | ||
node.left = t; | ||
t.right = null; | ||
} | ||
this._size++; | ||
this._root = node; | ||
} | ||
return this._root; | ||
}; | ||
/** | ||
* @param {Key} key | ||
* @return {Node|null} | ||
*/ | ||
Tree.prototype.remove = function (key) { | ||
this._root = this._remove(key, this._root, this._comparator); | ||
}; | ||
/** | ||
* Deletes i from the tree if it's there | ||
*/ | ||
Tree.prototype._remove = function (i, t, comparator) { | ||
var x; | ||
if (t === null) | ||
return null; | ||
t = splay(i, t, comparator); | ||
var cmp = comparator(i, t.key); | ||
if (cmp === 0) { /* found it */ | ||
if (t.left === null) { | ||
x = t.right; | ||
} | ||
else { | ||
x = splay(i, t.left, comparator); | ||
x.right = t.right; | ||
} | ||
this._size--; | ||
return x; | ||
} | ||
return t; /* It wasn't there */ | ||
}; | ||
/** | ||
* Removes and returns the node with smallest key | ||
*/ | ||
Tree.prototype.pop = function () { | ||
var node = this._root; | ||
if (node) { | ||
while (node.left) | ||
node = node.left; | ||
this._root = splay(node.key, this._root, this._comparator); | ||
this._root = this._remove(node.key, this._root, this._comparator); | ||
return { key: node.key, data: node.data }; | ||
} | ||
return null; | ||
}; | ||
/** | ||
* Find without splaying | ||
*/ | ||
Tree.prototype.findStatic = function (key) { | ||
var current = this._root; | ||
var compare = this._comparator; | ||
while (current) { | ||
var cmp = compare(key, current.key); | ||
if (cmp === 0) | ||
return current; | ||
else if (cmp < 0) | ||
current = current.left; | ||
else | ||
current = current.right; | ||
} | ||
return null; | ||
}; | ||
Tree.prototype.find = function (key) { | ||
if (this._root) { | ||
this._root = splay(key, this._root, this._comparator); | ||
if (this._comparator(key, this._root.key) !== 0) | ||
return null; | ||
} | ||
return this._root; | ||
}; | ||
Tree.prototype.contains = function (key) { | ||
var current = this._root; | ||
var compare = this._comparator; | ||
while (current) { | ||
var cmp = compare(key, current.key); | ||
if (cmp === 0) | ||
return true; | ||
else if (cmp < 0) | ||
current = current.left; | ||
else | ||
current = current.right; | ||
} | ||
return false; | ||
}; | ||
Tree.prototype.forEach = function (visitor, ctx) { | ||
var current = this._root; | ||
var Q = []; /* Initialize stack s */ | ||
var done = false; | ||
while (!done) { | ||
if (current !== null) { | ||
Q.push(current); | ||
current = current.left; | ||
} | ||
else { | ||
if (Q.length !== 0) { | ||
current = Q.pop(); | ||
visitor.call(ctx, current); | ||
current = current.right; | ||
} | ||
else | ||
done = true; | ||
} | ||
} | ||
return this; | ||
}; | ||
/** | ||
* Walk key range from `low` to `high`. Stops if `fn` returns a value. | ||
*/ | ||
Tree.prototype.range = function (low, high, fn, ctx) { | ||
var Q = []; | ||
var compare = this._comparator; | ||
var node = this._root; | ||
var 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 array of keys | ||
*/ | ||
Tree.prototype.keys = function () { | ||
var keys = []; | ||
this.forEach(function (_a) { | ||
var key = _a.key; | ||
return keys.push(key); | ||
}); | ||
return keys; | ||
}; | ||
/** | ||
* Returns array of all the data in the nodes | ||
*/ | ||
Tree.prototype.values = function () { | ||
var values = []; | ||
this.forEach(function (_a) { | ||
var data = _a.data; | ||
return values.push(data); | ||
}); | ||
return values; | ||
}; | ||
Tree.prototype.min = function () { | ||
if (this._root) | ||
return this.minNode(this._root).key; | ||
return null; | ||
}; | ||
Tree.prototype.max = function () { | ||
if (this._root) | ||
return this.maxNode(this._root).key; | ||
return null; | ||
}; | ||
Tree.prototype.minNode = function (t) { | ||
if (t === void 0) { t = this._root; } | ||
if (t) | ||
while (t.left) | ||
t = t.left; | ||
return t; | ||
}; | ||
Tree.prototype.maxNode = function (t) { | ||
if (t === void 0) { t = this._root; } | ||
if (t) | ||
while (t.right) | ||
t = t.right; | ||
return t; | ||
}; | ||
/** | ||
* Returns node at given index | ||
*/ | ||
Tree.prototype.at = function (index) { | ||
var current = this._root; | ||
var done = false; | ||
var i = 0; | ||
var Q = []; | ||
while (!done) { | ||
if (current) { | ||
Q.push(current); | ||
current = current.left; | ||
} | ||
else { | ||
if (Q.length > 0) { | ||
current = Q.pop(); | ||
if (i === index) | ||
return current; | ||
i++; | ||
current = current.right; | ||
} | ||
else | ||
done = true; | ||
} | ||
} | ||
return null; | ||
}; | ||
Tree.prototype.next = function (d) { | ||
var root = this._root; | ||
var successor = null; | ||
if (d.right) { | ||
successor = d.right; | ||
while (successor.left) | ||
successor = successor.left; | ||
return successor; | ||
} | ||
var comparator = this._comparator; | ||
while (root) { | ||
var cmp = comparator(d.key, root.key); | ||
if (cmp === 0) | ||
break; | ||
else if (cmp < 0) { | ||
successor = root; | ||
root = root.left; | ||
} | ||
else | ||
root = root.right; | ||
} | ||
return successor; | ||
}; | ||
Tree.prototype.prev = function (d) { | ||
var root = this._root; | ||
var predecessor = null; | ||
if (d.left !== null) { | ||
predecessor = d.left; | ||
while (predecessor.right) | ||
predecessor = predecessor.right; | ||
return predecessor; | ||
} | ||
var comparator = this._comparator; | ||
while (root) { | ||
var cmp = comparator(d.key, root.key); | ||
if (cmp === 0) | ||
break; | ||
else if (cmp < 0) | ||
root = root.left; | ||
else { | ||
predecessor = root; | ||
root = root.right; | ||
} | ||
} | ||
return predecessor; | ||
}; | ||
Tree.prototype.clear = function () { | ||
this._root = null; | ||
this._size = 0; | ||
return this; | ||
}; | ||
Tree.prototype.toList = function () { | ||
return toList(this._root); | ||
}; | ||
/** | ||
* Bulk-load items. Both array have to be same size | ||
*/ | ||
Tree.prototype.load = function (keys, values, presort) { | ||
if (values === void 0) { values = []; } | ||
if (presort === void 0) { presort = false; } | ||
var size = keys.length; | ||
var comparator = this._comparator; | ||
// sort if needed | ||
if (presort) | ||
sort(keys, values, 0, size - 1, comparator); | ||
if (this._root === null) { // empty tree | ||
this._root = loadRecursive(keys, values, 0, size); | ||
this._size = size; | ||
} | ||
else { // that re-builds the whole tree from two in-order traversals | ||
var mergedList = mergeLists(this.toList(), createList(keys, values), comparator); | ||
size = this._size + size; | ||
this._root = sortedListToBST({ head: mergedList }, 0, size); | ||
} | ||
return this; | ||
}; | ||
Tree.prototype.isEmpty = function () { return this._root === null; }; | ||
Object.defineProperty(Tree.prototype, "size", { | ||
get: function () { return this._size; }, | ||
enumerable: true, | ||
configurable: true | ||
}); | ||
Object.defineProperty(Tree.prototype, "root", { | ||
get: function () { return this._root; }, | ||
enumerable: true, | ||
configurable: true | ||
}); | ||
Tree.prototype.toString = function (printNode) { | ||
if (printNode === void 0) { printNode = function (n) { return String(n.key); }; } | ||
var out = []; | ||
printRow(this._root, '', true, function (v) { return out.push(v); }, printNode); | ||
return out.join(''); | ||
}; | ||
Tree.prototype.update = function (key, newKey, newData) { | ||
var comparator = this._comparator; | ||
var _a = split(key, this._root, comparator), left = _a.left, right = _a.right; | ||
if (comparator(key, newKey) < 0) { | ||
right = insert(newKey, newData, right, comparator); | ||
} | ||
else { | ||
left = insert(newKey, newData, left, comparator); | ||
} | ||
this._root = merge(left, right, comparator); | ||
}; | ||
Tree.prototype.split = function (key) { | ||
return split(key, this._root, this._comparator); | ||
}; | ||
return Tree; | ||
}()); | ||
function loadRecursive(keys, values, start, end) { | ||
var size = end - start; | ||
if (size > 0) { | ||
var middle = start + Math.floor(size / 2); | ||
var key = keys[middle]; | ||
var data = values[middle]; | ||
var node = new Node(key, data); | ||
node.left = loadRecursive(keys, values, start, middle); | ||
node.right = loadRecursive(keys, values, middle + 1, end); | ||
return node; | ||
} | ||
return null; | ||
} | ||
function createList(keys, values) { | ||
var head = new Node(null, null); | ||
var p = head; | ||
for (var i = 0; i < keys.length; i++) { | ||
p = p.next = new Node(keys[i], values[i]); | ||
} | ||
p.next = null; | ||
return head.next; | ||
} | ||
function toList(root) { | ||
var current = root; | ||
var Q = []; | ||
var done = false; | ||
var head = new Node(null, null); | ||
var p = head; | ||
while (!done) { | ||
if (current) { | ||
Q.push(current); | ||
current = current.left; | ||
} | ||
else { | ||
if (Q.length > 0) { | ||
current = p = p.next = Q.pop(); | ||
current = current.right; | ||
} | ||
else | ||
done = true; | ||
} | ||
} | ||
p.next = null; // that'll work even if the tree was empty | ||
return head.next; | ||
} | ||
function sortedListToBST(list, start, end) { | ||
var size = end - start; | ||
if (size > 0) { | ||
var middle = start + Math.floor(size / 2); | ||
var left = sortedListToBST(list, start, middle); | ||
var root = list.head; | ||
root.left = left; | ||
list.head = list.head.next; | ||
root.right = sortedListToBST(list, middle + 1, end); | ||
return root; | ||
} | ||
return null; | ||
} | ||
function mergeLists(l1, l2, compare) { | ||
var head = new Node(null, null); // dummy | ||
var p = head; | ||
var p1 = l1; | ||
var p2 = l2; | ||
while (p1 !== null && p2 !== null) { | ||
if (compare(p1.key, p2.key) < 0) { | ||
p.next = p1; | ||
p1 = p1.next; | ||
} | ||
else { | ||
p.next = p2; | ||
p2 = p2.next; | ||
} | ||
p = p.next; | ||
} | ||
if (p1 !== null) { | ||
p.next = p1; | ||
} | ||
else if (p2 !== null) { | ||
p.next = p2; | ||
} | ||
return head.next; | ||
} | ||
function sort(keys, values, left, right, compare) { | ||
if (left >= right) | ||
return; | ||
var pivot = keys[(left + right) >> 1]; | ||
var i = left - 1; | ||
var j = right + 1; | ||
while (true) { | ||
do | ||
i++; | ||
while (compare(keys[i], pivot) < 0); | ||
do | ||
j--; | ||
while (compare(keys[j], pivot) > 0); | ||
if (i >= j) | ||
break; | ||
var tmp = keys[i]; | ||
keys[i] = keys[j]; | ||
keys[j] = tmp; | ||
tmp = values[i]; | ||
values[i] = values[j]; | ||
values[j] = tmp; | ||
} | ||
sort(keys, values, left, j, compare); | ||
sort(keys, values, j + 1, right, compare); | ||
} | ||
THIS CODE IS PROVIDED ON AN *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY | ||
KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED | ||
WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE, | ||
MERCHANTABLITY OR NON-INFRINGEMENT. | ||
return Tree; | ||
See the Apache Version 2.0 License for specific language governing permissions | ||
and limitations under the License. | ||
***************************************************************************** */ | ||
function __generator(thisArg, body) { | ||
var _ = { label: 0, sent: function() { if (t[0] & 1) throw t[1]; return t[1]; }, trys: [], ops: [] }, f, y, t, g; | ||
return g = { next: verb(0), "throw": verb(1), "return": verb(2) }, typeof Symbol === "function" && (g[Symbol.iterator] = function() { return this; }), g; | ||
function verb(n) { return function (v) { return step([n, v]); }; } | ||
function step(op) { | ||
if (f) throw new TypeError("Generator is already executing."); | ||
while (_) try { | ||
if (f = 1, y && (t = op[0] & 2 ? y["return"] : op[0] ? y["throw"] || ((t = y["return"]) && t.call(y), 0) : y.next) && !(t = t.call(y, op[1])).done) return t; | ||
if (y = 0, t) op = [op[0] & 2, t.value]; | ||
switch (op[0]) { | ||
case 0: case 1: t = op; break; | ||
case 4: _.label++; return { value: op[1], done: false }; | ||
case 5: _.label++; y = op[1]; op = [0]; continue; | ||
case 7: op = _.ops.pop(); _.trys.pop(); continue; | ||
default: | ||
if (!(t = _.trys, t = t.length > 0 && t[t.length - 1]) && (op[0] === 6 || op[0] === 2)) { _ = 0; continue; } | ||
if (op[0] === 3 && (!t || (op[1] > t[0] && op[1] < t[3]))) { _.label = op[1]; break; } | ||
if (op[0] === 6 && _.label < t[1]) { _.label = t[1]; t = op; break; } | ||
if (t && _.label < t[2]) { _.label = t[2]; _.ops.push(op); break; } | ||
if (t[2]) _.ops.pop(); | ||
_.trys.pop(); continue; | ||
} | ||
op = body.call(thisArg, _); | ||
} catch (e) { op = [6, e]; y = 0; } finally { f = t = 0; } | ||
if (op[0] & 5) throw op[1]; return { value: op[0] ? op[1] : void 0, done: true }; | ||
} | ||
} | ||
var Node = /** @class */ (function () { | ||
function Node(key, data) { | ||
this.next = null; | ||
this.key = key; | ||
this.data = data; | ||
this.left = null; | ||
this.right = null; | ||
} | ||
return Node; | ||
}()); | ||
/* follows "An implementation of top-down splaying" | ||
* by D. Sleator <sleator@cs.cmu.edu> March 1992 | ||
*/ | ||
function DEFAULT_COMPARE(a, b) { | ||
return a > b ? 1 : a < b ? -1 : 0; | ||
} | ||
/** | ||
* Simple top down splay, not requiring i to be in the tree t. | ||
*/ | ||
function splay(i, t, comparator) { | ||
var N = new Node(null, null); | ||
var l = N; | ||
var r = N; | ||
while (true) { | ||
var cmp = comparator(i, t.key); | ||
//if (i < t.key) { | ||
if (cmp < 0) { | ||
if (t.left === null) | ||
break; | ||
//if (i < t.left.key) { | ||
if (comparator(i, t.left.key) < 0) { | ||
var y = t.left; /* rotate right */ | ||
t.left = y.right; | ||
y.right = t; | ||
t = y; | ||
if (t.left === null) | ||
break; | ||
} | ||
r.left = t; /* link right */ | ||
r = t; | ||
t = t.left; | ||
//} else if (i > t.key) { | ||
} | ||
else if (cmp > 0) { | ||
if (t.right === null) | ||
break; | ||
//if (i > t.right.key) { | ||
if (comparator(i, t.right.key) > 0) { | ||
var y = t.right; /* rotate left */ | ||
t.right = y.left; | ||
y.left = t; | ||
t = y; | ||
if (t.right === null) | ||
break; | ||
} | ||
l.right = t; /* link left */ | ||
l = t; | ||
t = t.right; | ||
} | ||
else | ||
break; | ||
} | ||
/* assemble */ | ||
l.right = t.left; | ||
r.left = t.right; | ||
t.left = N.right; | ||
t.right = N.left; | ||
return t; | ||
} | ||
function insert(i, data, t, comparator) { | ||
var node = new Node(i, data); | ||
if (t === null) { | ||
node.left = node.right = null; | ||
return node; | ||
} | ||
t = splay(i, t, comparator); | ||
var cmp = comparator(i, t.key); | ||
if (cmp < 0) { | ||
node.left = t.left; | ||
node.right = t; | ||
t.left = null; | ||
} | ||
else if (cmp >= 0) { | ||
node.right = t.right; | ||
node.left = t; | ||
t.right = null; | ||
} | ||
return node; | ||
} | ||
function split(key, v, comparator) { | ||
var left = null; | ||
var right = null; | ||
if (v) { | ||
v = splay(key, v, comparator); | ||
var cmp = comparator(v.key, key); | ||
if (cmp === 0) { | ||
left = v.left; | ||
right = v.right; | ||
} | ||
else if (cmp < 0) { | ||
right = v.right; | ||
v.right = null; | ||
left = v; | ||
} | ||
else { | ||
left = v.left; | ||
v.left = null; | ||
right = v; | ||
} | ||
} | ||
return { left: left, right: right }; | ||
} | ||
function merge(left, right, comparator) { | ||
if (right === null) | ||
return left; | ||
if (left === null) | ||
return right; | ||
right = splay(left.key, right, comparator); | ||
right.left = left; | ||
return right; | ||
} | ||
/** | ||
* Prints level of the tree | ||
*/ | ||
function printRow(root, prefix, isTail, out, printNode) { | ||
if (root) { | ||
out("" + prefix + (isTail ? '└── ' : '├── ') + printNode(root) + "\n"); | ||
var indent = prefix + (isTail ? ' ' : '│ '); | ||
if (root.left) | ||
printRow(root.left, indent, false, out, printNode); | ||
if (root.right) | ||
printRow(root.right, indent, true, out, printNode); | ||
} | ||
} | ||
var Tree = /** @class */ (function () { | ||
function Tree(comparator) { | ||
if (comparator === void 0) { comparator = DEFAULT_COMPARE; } | ||
this._root = null; | ||
this._size = 0; | ||
this._comparator = comparator; | ||
} | ||
/** | ||
* Inserts a key, allows duplicates | ||
*/ | ||
Tree.prototype.insert = function (key, data) { | ||
this._size++; | ||
return this._root = insert(key, data, this._root, this._comparator); | ||
}; | ||
/** | ||
* Adds a key, if it is not present in the tree | ||
*/ | ||
Tree.prototype.add = function (key, data) { | ||
var node = new Node(key, data); | ||
if (this._root === null) { | ||
node.left = node.right = null; | ||
this._size++; | ||
this._root = node; | ||
} | ||
var comparator = this._comparator; | ||
var t = splay(key, this._root, comparator); | ||
var cmp = comparator(key, t.key); | ||
if (cmp === 0) | ||
this._root = t; | ||
else { | ||
if (cmp < 0) { | ||
node.left = t.left; | ||
node.right = t; | ||
t.left = null; | ||
} | ||
else if (cmp > 0) { | ||
node.right = t.right; | ||
node.left = t; | ||
t.right = null; | ||
} | ||
this._size++; | ||
this._root = node; | ||
} | ||
return this._root; | ||
}; | ||
/** | ||
* @param {Key} key | ||
* @return {Node|null} | ||
*/ | ||
Tree.prototype.remove = function (key) { | ||
this._root = this._remove(key, this._root, this._comparator); | ||
}; | ||
/** | ||
* Deletes i from the tree if it's there | ||
*/ | ||
Tree.prototype._remove = function (i, t, comparator) { | ||
var x; | ||
if (t === null) | ||
return null; | ||
t = splay(i, t, comparator); | ||
var cmp = comparator(i, t.key); | ||
if (cmp === 0) { /* found it */ | ||
if (t.left === null) { | ||
x = t.right; | ||
} | ||
else { | ||
x = splay(i, t.left, comparator); | ||
x.right = t.right; | ||
} | ||
this._size--; | ||
return x; | ||
} | ||
return t; /* It wasn't there */ | ||
}; | ||
/** | ||
* Removes and returns the node with smallest key | ||
*/ | ||
Tree.prototype.pop = function () { | ||
var node = this._root; | ||
if (node) { | ||
while (node.left) | ||
node = node.left; | ||
this._root = splay(node.key, this._root, this._comparator); | ||
this._root = this._remove(node.key, this._root, this._comparator); | ||
return { key: node.key, data: node.data }; | ||
} | ||
return null; | ||
}; | ||
/** | ||
* Find without splaying | ||
*/ | ||
Tree.prototype.findStatic = function (key) { | ||
var current = this._root; | ||
var compare = this._comparator; | ||
while (current) { | ||
var cmp = compare(key, current.key); | ||
if (cmp === 0) | ||
return current; | ||
else if (cmp < 0) | ||
current = current.left; | ||
else | ||
current = current.right; | ||
} | ||
return null; | ||
}; | ||
Tree.prototype.find = function (key) { | ||
if (this._root) { | ||
this._root = splay(key, this._root, this._comparator); | ||
if (this._comparator(key, this._root.key) !== 0) | ||
return null; | ||
} | ||
return this._root; | ||
}; | ||
Tree.prototype.contains = function (key) { | ||
var current = this._root; | ||
var compare = this._comparator; | ||
while (current) { | ||
var cmp = compare(key, current.key); | ||
if (cmp === 0) | ||
return true; | ||
else if (cmp < 0) | ||
current = current.left; | ||
else | ||
current = current.right; | ||
} | ||
return false; | ||
}; | ||
Tree.prototype.forEach = function (visitor, ctx) { | ||
var current = this._root; | ||
var Q = []; /* Initialize stack s */ | ||
var done = false; | ||
while (!done) { | ||
if (current !== null) { | ||
Q.push(current); | ||
current = current.left; | ||
} | ||
else { | ||
if (Q.length !== 0) { | ||
current = Q.pop(); | ||
visitor.call(ctx, current); | ||
current = current.right; | ||
} | ||
else | ||
done = true; | ||
} | ||
} | ||
return this; | ||
}; | ||
/** | ||
* Walk key range from `low` to `high`. Stops if `fn` returns a value. | ||
*/ | ||
Tree.prototype.range = function (low, high, fn, ctx) { | ||
var Q = []; | ||
var compare = this._comparator; | ||
var node = this._root; | ||
var 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 array of keys | ||
*/ | ||
Tree.prototype.keys = function () { | ||
var keys = []; | ||
this.forEach(function (_a) { | ||
var key = _a.key; | ||
return keys.push(key); | ||
}); | ||
return keys; | ||
}; | ||
/** | ||
* Returns array of all the data in the nodes | ||
*/ | ||
Tree.prototype.values = function () { | ||
var values = []; | ||
this.forEach(function (_a) { | ||
var data = _a.data; | ||
return values.push(data); | ||
}); | ||
return values; | ||
}; | ||
Tree.prototype.min = function () { | ||
if (this._root) | ||
return this.minNode(this._root).key; | ||
return null; | ||
}; | ||
Tree.prototype.max = function () { | ||
if (this._root) | ||
return this.maxNode(this._root).key; | ||
return null; | ||
}; | ||
Tree.prototype.minNode = function (t) { | ||
if (t === void 0) { t = this._root; } | ||
if (t) | ||
while (t.left) | ||
t = t.left; | ||
return t; | ||
}; | ||
Tree.prototype.maxNode = function (t) { | ||
if (t === void 0) { t = this._root; } | ||
if (t) | ||
while (t.right) | ||
t = t.right; | ||
return t; | ||
}; | ||
/** | ||
* Returns node at given index | ||
*/ | ||
Tree.prototype.at = function (index) { | ||
var current = this._root; | ||
var done = false; | ||
var i = 0; | ||
var Q = []; | ||
while (!done) { | ||
if (current) { | ||
Q.push(current); | ||
current = current.left; | ||
} | ||
else { | ||
if (Q.length > 0) { | ||
current = Q.pop(); | ||
if (i === index) | ||
return current; | ||
i++; | ||
current = current.right; | ||
} | ||
else | ||
done = true; | ||
} | ||
} | ||
return null; | ||
}; | ||
Tree.prototype.next = function (d) { | ||
var root = this._root; | ||
var successor = null; | ||
if (d.right) { | ||
successor = d.right; | ||
while (successor.left) | ||
successor = successor.left; | ||
return successor; | ||
} | ||
var comparator = this._comparator; | ||
while (root) { | ||
var cmp = comparator(d.key, root.key); | ||
if (cmp === 0) | ||
break; | ||
else if (cmp < 0) { | ||
successor = root; | ||
root = root.left; | ||
} | ||
else | ||
root = root.right; | ||
} | ||
return successor; | ||
}; | ||
Tree.prototype.prev = function (d) { | ||
var root = this._root; | ||
var predecessor = null; | ||
if (d.left !== null) { | ||
predecessor = d.left; | ||
while (predecessor.right) | ||
predecessor = predecessor.right; | ||
return predecessor; | ||
} | ||
var comparator = this._comparator; | ||
while (root) { | ||
var cmp = comparator(d.key, root.key); | ||
if (cmp === 0) | ||
break; | ||
else if (cmp < 0) | ||
root = root.left; | ||
else { | ||
predecessor = root; | ||
root = root.right; | ||
} | ||
} | ||
return predecessor; | ||
}; | ||
Tree.prototype.clear = function () { | ||
this._root = null; | ||
this._size = 0; | ||
return this; | ||
}; | ||
Tree.prototype.toList = function () { | ||
return toList(this._root); | ||
}; | ||
/** | ||
* Bulk-load items. Both array have to be same size | ||
*/ | ||
Tree.prototype.load = function (keys, values, presort) { | ||
if (values === void 0) { values = []; } | ||
if (presort === void 0) { presort = false; } | ||
var size = keys.length; | ||
var comparator = this._comparator; | ||
// sort if needed | ||
if (presort) | ||
sort(keys, values, 0, size - 1, comparator); | ||
if (this._root === null) { // empty tree | ||
this._root = loadRecursive(keys, values, 0, size); | ||
this._size = size; | ||
} | ||
else { // that re-builds the whole tree from two in-order traversals | ||
var mergedList = mergeLists(this.toList(), createList(keys, values), comparator); | ||
size = this._size + size; | ||
this._root = sortedListToBST({ head: mergedList }, 0, size); | ||
} | ||
return this; | ||
}; | ||
Tree.prototype.isEmpty = function () { return this._root === null; }; | ||
Object.defineProperty(Tree.prototype, "size", { | ||
get: function () { return this._size; }, | ||
enumerable: true, | ||
configurable: true | ||
}); | ||
Object.defineProperty(Tree.prototype, "root", { | ||
get: function () { return this._root; }, | ||
enumerable: true, | ||
configurable: true | ||
}); | ||
Tree.prototype.toString = function (printNode) { | ||
if (printNode === void 0) { printNode = function (n) { return String(n.key); }; } | ||
var out = []; | ||
printRow(this._root, '', true, function (v) { return out.push(v); }, printNode); | ||
return out.join(''); | ||
}; | ||
Tree.prototype.update = function (key, newKey, newData) { | ||
var comparator = this._comparator; | ||
var _a = split(key, this._root, comparator), left = _a.left, right = _a.right; | ||
if (comparator(key, newKey) < 0) { | ||
right = insert(newKey, newData, right, comparator); | ||
} | ||
else { | ||
left = insert(newKey, newData, left, comparator); | ||
} | ||
this._root = merge(left, right, comparator); | ||
}; | ||
Tree.prototype.split = function (key) { | ||
return split(key, this._root, this._comparator); | ||
}; | ||
Tree.prototype[Symbol.iterator] = function () { | ||
var n; | ||
return __generator(this, function (_a) { | ||
switch (_a.label) { | ||
case 0: | ||
n = this.minNode(); | ||
_a.label = 1; | ||
case 1: | ||
if (!n) return [3 /*break*/, 3]; | ||
return [4 /*yield*/, n]; | ||
case 2: | ||
_a.sent(); | ||
n = this.next(n); | ||
return [3 /*break*/, 1]; | ||
case 3: return [2 /*return*/]; | ||
} | ||
}); | ||
}; | ||
return Tree; | ||
}()); | ||
function loadRecursive(keys, values, start, end) { | ||
var size = end - start; | ||
if (size > 0) { | ||
var middle = start + Math.floor(size / 2); | ||
var key = keys[middle]; | ||
var data = values[middle]; | ||
var node = new Node(key, data); | ||
node.left = loadRecursive(keys, values, start, middle); | ||
node.right = loadRecursive(keys, values, middle + 1, end); | ||
return node; | ||
} | ||
return null; | ||
} | ||
function createList(keys, values) { | ||
var head = new Node(null, null); | ||
var p = head; | ||
for (var i = 0; i < keys.length; i++) { | ||
p = p.next = new Node(keys[i], values[i]); | ||
} | ||
p.next = null; | ||
return head.next; | ||
} | ||
function toList(root) { | ||
var current = root; | ||
var Q = []; | ||
var done = false; | ||
var head = new Node(null, null); | ||
var p = head; | ||
while (!done) { | ||
if (current) { | ||
Q.push(current); | ||
current = current.left; | ||
} | ||
else { | ||
if (Q.length > 0) { | ||
current = p = p.next = Q.pop(); | ||
current = current.right; | ||
} | ||
else | ||
done = true; | ||
} | ||
} | ||
p.next = null; // that'll work even if the tree was empty | ||
return head.next; | ||
} | ||
function sortedListToBST(list, start, end) { | ||
var size = end - start; | ||
if (size > 0) { | ||
var middle = start + Math.floor(size / 2); | ||
var left = sortedListToBST(list, start, middle); | ||
var root = list.head; | ||
root.left = left; | ||
list.head = list.head.next; | ||
root.right = sortedListToBST(list, middle + 1, end); | ||
return root; | ||
} | ||
return null; | ||
} | ||
function mergeLists(l1, l2, compare) { | ||
var head = new Node(null, null); // dummy | ||
var p = head; | ||
var p1 = l1; | ||
var p2 = l2; | ||
while (p1 !== null && p2 !== null) { | ||
if (compare(p1.key, p2.key) < 0) { | ||
p.next = p1; | ||
p1 = p1.next; | ||
} | ||
else { | ||
p.next = p2; | ||
p2 = p2.next; | ||
} | ||
p = p.next; | ||
} | ||
if (p1 !== null) { | ||
p.next = p1; | ||
} | ||
else if (p2 !== null) { | ||
p.next = p2; | ||
} | ||
return head.next; | ||
} | ||
function sort(keys, values, left, right, compare) { | ||
if (left >= right) | ||
return; | ||
var pivot = keys[(left + right) >> 1]; | ||
var i = left - 1; | ||
var j = right + 1; | ||
while (true) { | ||
do | ||
i++; | ||
while (compare(keys[i], pivot) < 0); | ||
do | ||
j--; | ||
while (compare(keys[j], pivot) > 0); | ||
if (i >= j) | ||
break; | ||
var tmp = keys[i]; | ||
keys[i] = keys[j]; | ||
keys[j] = tmp; | ||
tmp = values[i]; | ||
values[i] = values[j]; | ||
values[j] = tmp; | ||
} | ||
sort(keys, values, left, j, compare); | ||
sort(keys, values, j + 1, right, compare); | ||
} | ||
return Tree; | ||
}))); | ||
//# sourceMappingURL=splay.js.map |
{ | ||
"name": "splaytree", | ||
"version": "3.1.0", | ||
"version": "3.1.1", | ||
"author": "Alexander Milevski <info@w8r.name>", | ||
@@ -36,3 +36,4 @@ "license": "MIT", | ||
"prepublishOnly": "npm run build && npm test", | ||
"clean": "rm -rf dist coverage .nyc" | ||
"clean": "rm -rf dist coverage .nyc", | ||
"coverage": "codecov -f coverage/*.json" | ||
}, | ||
@@ -46,2 +47,3 @@ "devDependencies": { | ||
"chai": "^4.2.0", | ||
"codecov": "^3.8.3", | ||
"mocha": "^6.2.0", | ||
@@ -48,0 +50,0 @@ "nodemon": "^1.19.2", |
@@ -384,3 +384,3 @@ import Node from './node'; | ||
public minNode(t = this._root) : Node<Key, Value> { | ||
public minNode(t = this._root) : Node<Key, Value> | null { | ||
if (t) while (t.left) t = t.left; | ||
@@ -391,3 +391,3 @@ return t; | ||
public maxNode(t = this._root) : Node<Key, Value> { | ||
public maxNode(t = this._root) : Node<Key, Value> | null { | ||
if (t) while (t.right) t = t.right; | ||
@@ -534,2 +534,10 @@ return t; | ||
} | ||
*[Symbol.iterator]() { | ||
let n = this.minNode(); | ||
while (n) { | ||
yield n; | ||
n = this.next(n); | ||
} | ||
} | ||
} | ||
@@ -536,0 +544,0 @@ |
@@ -57,4 +57,4 @@ import Node from './node'; | ||
max(): Key | null; | ||
minNode(t?: Node<Key, Value>): Node<Key, Value>; | ||
maxNode(t?: Node<Key, Value>): Node<Key, Value>; | ||
minNode(t?: Node<Key, Value>): Node<Key, Value> | null; | ||
maxNode(t?: Node<Key, Value>): Node<Key, Value> | null; | ||
/** | ||
@@ -81,3 +81,4 @@ * Returns node at given index | ||
}; | ||
[Symbol.iterator](): IterableIterator<Node<Key, Value>>; | ||
} | ||
export {}; |
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
Mixed license
License(Experimental) Package contains multiple licenses.
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
75206
17
12
1
1987