Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Socket
Sign inDemoInstall

splaytree

Package Overview
Dependencies
Maintainers
1
Versions
15
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

splaytree - npm Package Compare versions

Comparing version 3.1.0 to 3.1.1

63

dist/splay.esm.js
/**
* 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

6

package.json
{
"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",

12

src/index.ts

@@ -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 @@

5

typings/index.d.ts

@@ -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 {};
dist/index.d.ts
dist/index.js
dist/node.d.ts
dist/node.js
dist/types.d.ts
dist/types.js
dist/splay.esm.js.map

Sorry, the diff of this file is not supported yet

dist/splay.js.map

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc