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 2.0.3 to 3.0.0

dist/splay.esm.js
dist/splay.esm.js.map
src/index.ts
src/node.ts
src/types.ts
typings/index.d.ts
typings/node.d.ts
typings/types.d.ts

1313

dist/splay.js
/**
* splaytree v2.0.3
* splaytree v3.0.0
* Fast Splay tree for Node and browser

@@ -16,780 +16,601 @@ *

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;
}
/**
* @typedef {*} Key
*/
/**
* @typedef {*} Value
*/
/**
* @typedef {function(node:Node):void} Visitor
*/
/**
* @typedef {function(a:Key, b:Key):number} Comparator
*/
/**
* @param {function(node:Node):string} NodePrinter
*/
/**
* @typedef {Object} Node
* @property {Key} Key
* @property {Value=} data
* @property {Node} left
* @property {Node} right
*/
var Node = function Node (key, data) {
this.key = key;
this.data = data;
this.left = null;
this.right= null;
};
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.
* @param {Key} i
* @param {Node?} t
* @param {Comparator} comparator
*/
function splay (i, t, comparator) {
if (t === null) { return t; }
var l, r, y;
var N = new Node();
l = 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) {
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) {
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;
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;
/* assemble */
l.right = t.left;
r.left = t.right;
t.left = N.right;
t.right = N.left;
return t;
}
/**
* @param {Key} i
* @param {Value} data
* @param {Comparator} comparator
* @param {Tree} tree
* @return {Node} root
*/
function insert (i, data, t, comparator, tree) {
var node = new Node(i, data);
tree._size++;
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;
}
/**
* Insert i into the tree t, unless it's already there.
* @param {Key} i
* @param {Value} data
* @param {Comparator} comparator
* @param {Tree} tree
* @return {Node} root
*/
function add (i, data, t, comparator, tree) {
var node = new Node(i, data);
if (t === null) {
node.left = node.right = null;
tree._size++;
return node;
}
t = splay(i, t, comparator);
var cmp = comparator(i, t.key);
if (cmp === 0) { return t; }
else {
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;
node.left = t.left;
node.right = t;
t.left = null;
}
tree._size++;
else if (cmp >= 0) {
node.right = t.right;
node.left = t;
t.right = null;
}
return node;
}
}
/**
* Deletes i from the tree if it's there
* @param {Key} i
* @param {Tree} tree
* @param {Comparator} comparator
* @param {Tree} tree
* @return {Node} new root
*/
function remove (i, t, comparator, tree) {
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;
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;
}
}
tree._size--;
return x;
}
return t; /* It wasn't there */
return { left: left, right: right };
}
function split (key, v, comparator) {
var left, right;
if (v === null) {
left = right = null;
} else {
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;
}
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
* @param {Node} root
* @param {String} prefix
* @param {Boolean} isTail
* @param {Array<string>} out
* @param {Function(node:Node):String} printNode
*/
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); }
}
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 = function Tree (comparator) {
if ( comparator === void 0 ) comparator = DEFAULT_COMPARE;
this._comparator = comparator;
this._root = null;
this._size = 0;
};
var prototypeAccessors = { size: { configurable: true } };
/**
* Inserts a key, allows duplicates
* @param{Key} key
* @param{Value=} data
* @return {Node|null}
*/
Tree.prototype.insert = function insert$1 (key, data) {
return this._root = insert(key, data, this._root, this._comparator, this);
};
/**
* Adds a key, if it is not present in the tree
* @param{Key} key
* @param{Value=} data
* @return {Node|null}
*/
Tree.prototype.add = function add$1 (key, data) {
return this._root = add(key, data, this._root, this._comparator, this);
};
/**
* @param{Key} key
* @return {Node|null}
*/
Tree.prototype.remove = function remove$1 (key) {
this._root = remove(key, this._root, this._comparator, this);
};
/**
* Removes and returns the node with smallest key
* @return {?Node}
*/
Tree.prototype.pop = function pop () {
var node = this._root;
if (node) {
while (node.left) { node = node.left; }
this._root = splay(node.key,this._root, this._comparator);
this._root = remove(node.key, this._root, this._comparator, this);
return { key: node.key, data: node.data };
}
return null;
};
/**
* @param{Key} key
* @return {Node|null}
*/
Tree.prototype.findStatic = function findStatic (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;
};
/**
* @param{Key} key
* @return {Node|null}
*/
Tree.prototype.find = function find (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;
};
/**
* @param{Key} key
* @return {Boolean}
*/
Tree.prototype.contains = function contains (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;
};
/**
* @param{Visitor} visitor
* @param{*=} ctx
* @return {SplayTree}
*/
Tree.prototype.forEach = function forEach (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; }
var Tree = /** @class */ (function () {
function Tree(comparator) {
if (comparator === void 0) { comparator = DEFAULT_COMPARE; }
this._root = null;
this._size = 0;
this._comparator = comparator;
}
}
return this;
};
/**
* Walk key range from `low` to `high`. Stops if `fn` returns a value.
* @param{Key} low
* @param{Key} high
* @param{Function} fn
* @param{*?} ctx
* @return {SplayTree}
*/
Tree.prototype.range = function range (low, high, fn, ctx) {
var this$1 = this;
var Q = [];
var compare = this._comparator;
var node = this._root, 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$1; } // stop if smth is returned
}
node = node.right;
}
}
return this;
};
/**
* Returns array of keys
* @return {Array<Key>}
*/
Tree.prototype.keys = function keys () {
var keys = [];
this.forEach(function (ref) {
var key = ref.key;
return keys.push(key);
/**
* 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
});
return keys;
};
/**
* Returns array of all the data in the nodes
* @return {Array<Value>}
*/
Tree.prototype.values = function values () {
var values = [];
this.forEach(function (ref) {
var data = ref.data;
return values.push(data);
Object.defineProperty(Tree.prototype, "root", {
get: function () { return this._root; },
enumerable: true,
configurable: true
});
return values;
};
/**
* @return {Key|null}
*/
Tree.prototype.min = function min () {
if (this._root) { return this.minNode(this._root).key; }
return null;
};
/**
* @return {Key|null}
*/
Tree.prototype.max = function max () {
if (this._root) { return this.maxNode(this._root).key; }
return null;
};
/**
* @return {Node|null}
*/
Tree.prototype.minNode = function minNode (t) {
if ( t === void 0 ) t = this._root;
if (t) { while (t.left) { t = t.left; } }
return t;
};
/**
* @return {Node|null}
*/
Tree.prototype.maxNode = function maxNode (t) {
if ( t === void 0 ) t = this._root;
if (t) { while (t.right) { t = t.right; } }
return t;
};
/**
* Returns node at given index
* @param{number} index
* @return {?Node}
*/
Tree.prototype.at = function at (index) {
var current = this._root, done = false, 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; }
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;
};
/**
* @param{Node} d
* @return {Node|null}
*/
Tree.prototype.next = function next (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;
};
/**
* @param{Node} d
* @return {Node|null}
*/
Tree.prototype.prev = function prev (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;
};
/**
* @return {SplayTree}
*/
Tree.prototype.clear = function clear () {
this._root = null;
this._size = 0;
return this;
};
/**
* @return {NodeList}
*/
Tree.prototype.toList = function toList$1 () {
return toList(this._root);
};
/**
* Bulk-load items. Both array have to be same size
* @param{Array<Key>} keys
* @param{Array<Value>}[values]
* @param{Boolean} [presort=false] Pre-sort keys and values, using
* tree's comparator. Sorting is done
* in-place
* @return {AVLTree}
*/
Tree.prototype.load = function load (keys, values, presort) {
if ( keys === void 0 ) keys = [];
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(this._root, 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;
};
/**
* @return {Boolean}
*/
Tree.prototype.isEmpty = function isEmpty () { return this._root === null; };
prototypeAccessors.size.get = function () { return this._size; };
/**
* @param{NodePrinter=} printNode
* @return {String}
*/
Tree.prototype.toString = function toString (printNode) {
if ( printNode === void 0 ) printNode = function (n) { return n.key; };
var out = [];
printRow(this._root, '', true, function (v) { return out.push(v); }, printNode);
return out.join('');
};
Tree.prototype.update = function update (key, newKey, newData) {
var comparator = this._comparator;
var ref = split(key, this._root, comparator);
var left = ref.left;
var right = ref.right;
this._size--;
if (comparator(key, newKey) < 0) {
right = insert(newKey, newData, right, comparator, this);
} else {
left = insert(newKey, newData, left, comparator, this);
}
this._root = merge(left, right, comparator);
};
Tree.prototype.split = function split$1 (key) {
return split(key, this._root, this._comparator);
};
Object.defineProperties( Tree.prototype, prototypeAccessors );
function loadRecursive (parent, 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 = { key: key, data: data, parent: parent };
node.left = loadRecursive(node, keys, values, start, middle);
node.right = loadRecursive(node, keys, values, middle + 1, end);
return node;
}
return null;
return null;
}
function createList(keys, values) {
var head = { next: null };
var p = head;
for (var i = 0; i < keys.length; i++) {
p = p.next = { key: keys[i], data: values[i] };
}
p.next = null;
return head.next;
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 = [], done = false;
var head = { next: 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; }
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;
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;
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) {
if ( compare === void 0 ) compare = function (a, b) { return a - b; };
var head = {}; // 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;
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;
}
p = p.next;
}
if (p1 !== null) { p.next = p1; }
else if (p2 !== null) { p.next = p2; }
return head.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);
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);
}

@@ -796,0 +617,0 @@

74

package.json
{
"name": "splaytree",
"version": "2.0.3",
"version": "3.0.0",
"author": "Alexander Milevski <info@w8r.name>",

@@ -8,10 +8,11 @@ "license": "MIT",

"main": "dist/splay.js",
"jsnext:main": "index",
"module": "index",
"types": "index.d.ts",
"module": "dist/splay.esm.js",
"types": "typings/index.d.ts",
"files": [
"dist",
"index.js",
"index.d.ts"
"dist", "typings", "src"
],
"directories": {
"test": "test",
"typings": "typings"
},
"repository": {

@@ -22,6 +23,5 @@ "type": "git",

"scripts": {
"prebuild": "npm run lint",
"lint": "eslint index.js",
"lint": "tslint --project tsconfig.json ./src/*.ts",
"build": "rollup -c && npm run types",
"types": "tsc index.d.ts tests/types.ts",
"types": "tsc --declaration --emitDeclarationOnly",
"prebenchmark": "npm run build",

@@ -31,19 +31,24 @@ "benchmark": "node -r reify bench/benchmark.js",

"test:watch": "nodemon --watch index.js --watch tests --exec 'npm test'",
"test": "mocha -r reify tests/**/*.test.js",
"prepublishOnly": "npm run build && npm test"
"test": "nyc mocha tests/**/*.test.ts",
"posttest": "nyc report --reporter=json",
"prepublishOnly": "npm run build && npm test",
"clean": "rm -rf dist coverage .nyc"
},
"devDependencies": {
"@types/chai": "^4.1.4",
"@types/mocha": "^5.2.2",
"avl": "^1.4.4",
"benchmark": "^2.1.4",
"bintrees": "^1.0.2",
"chai": "^4.1.2",
"eslint": "^5.5.0",
"eslint-config-airbnb-base": "^13.1.0",
"eslint-plugin-import": "^2.14.0",
"mocha": "^5.2.0",
"nodemon": "^1.18.4",
"reify": "^0.17.3",
"rollup": "^0.65.2",
"rollup-plugin-buble": "^0.19.2",
"typescript": "^3.0.3"
"chai": "^4.2.0",
"mocha": "^6.0.2",
"nodemon": "^1.17.5",
"nyc": "^13.3.0",
"reify": "*",
"rollup": "*",
"rollup-plugin-typescript2": "*",
"ts-node": "^6.1.1",
"tslib": "^1.9.3",
"tslint": "^5.14.0",
"typescript": "^2.9.2"
},

@@ -57,3 +62,28 @@ "keywords": [

],
"mocha": {
"require": [
"ts-node/register"
]
},
"nyc": {
"include": [
"src/*.ts"
],
"exclude": [
"tests/**/*.ts"
],
"extension": [
".ts"
],
"require": [
"ts-node/register"
],
"reporter": [
"text-summary",
"html"
],
"sourceMap": true,
"instrument": true
},
"dependencies": {}
}

7

Readme.md

@@ -1,2 +0,2 @@

# Fast splay tree [![npm version](https://badge.fury.io/js/splaytree.svg)](https://badge.fury.io/js/splaytree) [![build](https://travis-ci.org/w8r/splay-tree.svg?branch=master)](https://travis-ci.org/w8r/splay-tree)
# Fast splay tree [![npm version](https://badge.fury.io/js/splaytree.svg)](https://badge.fury.io/js/splaytree) [![build](https://travis-ci.org/w8r/splay-tree.svg?branch=master)](https://travis-ci.org/w8r/splay-tree) ![deps](https://david-dm.org/w8r/splay-tree/status.svg) [![codecov](https://codecov.io/gh/w8r/splay-tree/branch/master/graph/badge.svg)](https://codecov.io/gh/w8r/splay-tree)

@@ -52,4 +52,3 @@ [Splay-tree](https://en.wikipedia.org/wiki/Splay_tree): **[fast](#benchmarks)**(non-recursive) and **simple**(< 1000 lines of code)

* `tree.add(key:any, [data:any]):Node` - Insert item if it is not present
* `tree.remove(key:any):Boolean` - Remove item
* `tree.removeNode(Node:any)|Boolean` - Remove node
* `tree.remove(key:any)` - Remove item
* `tree.find(key):Node|Null` - Return node by its key

@@ -206,3 +205,3 @@ * `tree.findStatic(key):Node|Null` - Return node by its key (doesn't re-balance the tree)

Copyright (c) 2018 Alexander Milevski <info@w8r.name>
Copyright (c) 2019 Alexander Milevski <info@w8r.name>

@@ -209,0 +208,0 @@ Permission is hereby granted, free of charge, to any person obtaining a copy of

dist/splay.es6.js
dist/splay.es6.js.map
index.d.ts
index.js
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