Comparing version 3.0.1 to 3.1.0
/** | ||
* splaytree v3.0.1 | ||
* splaytree v3.1.0 | ||
* Fast Splay tree for Node and browser | ||
@@ -10,4 +10,4 @@ * | ||
class Node { | ||
constructor(key, data) { | ||
var Node = /** @class */ (function () { | ||
function Node(key, data) { | ||
this.next = null; | ||
@@ -19,3 +19,4 @@ this.key = key; | ||
} | ||
} | ||
return Node; | ||
}()); | ||
@@ -32,7 +33,7 @@ /* follows "An implementation of top-down splaying" | ||
function splay(i, t, comparator) { | ||
const N = new Node(null, null); | ||
let l = N; | ||
let r = N; | ||
var N = new Node(null, null); | ||
var l = N; | ||
var r = N; | ||
while (true) { | ||
const cmp = comparator(i, t.key); | ||
var cmp = comparator(i, t.key); | ||
//if (i < t.key) { | ||
@@ -44,3 +45,3 @@ if (cmp < 0) { | ||
if (comparator(i, t.left.key) < 0) { | ||
const y = t.left; /* rotate right */ | ||
var y = t.left; /* rotate right */ | ||
t.left = y.right; | ||
@@ -62,3 +63,3 @@ y.right = t; | ||
if (comparator(i, t.right.key) > 0) { | ||
const y = t.right; /* rotate left */ | ||
var y = t.right; /* rotate left */ | ||
t.right = y.left; | ||
@@ -85,3 +86,3 @@ y.left = t; | ||
function insert(i, data, t, comparator) { | ||
const node = new Node(i, data); | ||
var node = new Node(i, data); | ||
if (t === null) { | ||
@@ -92,3 +93,3 @@ node.left = node.right = null; | ||
t = splay(i, t, comparator); | ||
const cmp = comparator(i, t.key); | ||
var cmp = comparator(i, t.key); | ||
if (cmp < 0) { | ||
@@ -107,7 +108,7 @@ node.left = t.left; | ||
function split(key, v, comparator) { | ||
let left = null; | ||
let right = null; | ||
var left = null; | ||
var right = null; | ||
if (v) { | ||
v = splay(key, v, comparator); | ||
const cmp = comparator(v.key, key); | ||
var cmp = comparator(v.key, key); | ||
if (cmp === 0) { | ||
@@ -128,3 +129,3 @@ left = v.left; | ||
} | ||
return { left, right }; | ||
return { left: left, right: right }; | ||
} | ||
@@ -145,4 +146,4 @@ function merge(left, right, comparator) { | ||
if (root) { | ||
out(`${prefix}${isTail ? '└── ' : '├── '}${printNode(root)}\n`); | ||
const indent = prefix + (isTail ? ' ' : '│ '); | ||
out("" + prefix + (isTail ? '└── ' : '├── ') + printNode(root) + "\n"); | ||
var indent = prefix + (isTail ? ' ' : '│ '); | ||
if (root.left) | ||
@@ -154,4 +155,5 @@ printRow(root.left, indent, false, out, printNode); | ||
} | ||
class Tree { | ||
constructor(comparator = DEFAULT_COMPARE) { | ||
var Tree = /** @class */ (function () { | ||
function Tree(comparator) { | ||
if (comparator === void 0) { comparator = DEFAULT_COMPARE; } | ||
this._root = null; | ||
@@ -164,11 +166,11 @@ this._size = 0; | ||
*/ | ||
insert(key, data) { | ||
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 | ||
*/ | ||
add(key, data) { | ||
const node = new Node(key, data); | ||
Tree.prototype.add = function (key, data) { | ||
var node = new Node(key, data); | ||
if (this._root === null) { | ||
@@ -179,5 +181,5 @@ node.left = node.right = null; | ||
} | ||
const comparator = this._comparator; | ||
const t = splay(key, this._root, comparator); | ||
const cmp = comparator(key, t.key); | ||
var comparator = this._comparator; | ||
var t = splay(key, this._root, comparator); | ||
var cmp = comparator(key, t.key); | ||
if (cmp === 0) | ||
@@ -200,3 +202,3 @@ this._root = t; | ||
return this._root; | ||
} | ||
}; | ||
/** | ||
@@ -206,14 +208,14 @@ * @param {Key} key | ||
*/ | ||
remove(key) { | ||
Tree.prototype.remove = function (key) { | ||
this._root = this._remove(key, this._root, this._comparator); | ||
} | ||
}; | ||
/** | ||
* Deletes i from the tree if it's there | ||
*/ | ||
_remove(i, t, comparator) { | ||
let x; | ||
Tree.prototype._remove = function (i, t, comparator) { | ||
var x; | ||
if (t === null) | ||
return null; | ||
t = splay(i, t, comparator); | ||
const cmp = comparator(i, t.key); | ||
var cmp = comparator(i, t.key); | ||
if (cmp === 0) { /* found it */ | ||
@@ -231,8 +233,8 @@ if (t.left === null) { | ||
return t; /* It wasn't there */ | ||
} | ||
}; | ||
/** | ||
* Removes and returns the node with smallest key | ||
*/ | ||
pop() { | ||
let node = this._root; | ||
Tree.prototype.pop = function () { | ||
var node = this._root; | ||
if (node) { | ||
@@ -246,11 +248,11 @@ while (node.left) | ||
return null; | ||
} | ||
}; | ||
/** | ||
* Find without splaying | ||
*/ | ||
findStatic(key) { | ||
let current = this._root; | ||
const compare = this._comparator; | ||
Tree.prototype.findStatic = function (key) { | ||
var current = this._root; | ||
var compare = this._comparator; | ||
while (current) { | ||
const cmp = compare(key, current.key); | ||
var cmp = compare(key, current.key); | ||
if (cmp === 0) | ||
@@ -264,4 +266,4 @@ return current; | ||
return null; | ||
} | ||
find(key) { | ||
}; | ||
Tree.prototype.find = function (key) { | ||
if (this._root) { | ||
@@ -273,8 +275,8 @@ this._root = splay(key, this._root, this._comparator); | ||
return this._root; | ||
} | ||
contains(key) { | ||
let current = this._root; | ||
const compare = this._comparator; | ||
}; | ||
Tree.prototype.contains = function (key) { | ||
var current = this._root; | ||
var compare = this._comparator; | ||
while (current) { | ||
const cmp = compare(key, current.key); | ||
var cmp = compare(key, current.key); | ||
if (cmp === 0) | ||
@@ -288,7 +290,7 @@ return true; | ||
return false; | ||
} | ||
forEach(visitor, ctx) { | ||
let current = this._root; | ||
const Q = []; /* Initialize stack s */ | ||
let done = false; | ||
}; | ||
Tree.prototype.forEach = function (visitor, ctx) { | ||
var current = this._root; | ||
var Q = []; /* Initialize stack s */ | ||
var done = false; | ||
while (!done) { | ||
@@ -310,11 +312,11 @@ if (current !== null) { | ||
return this; | ||
} | ||
}; | ||
/** | ||
* Walk key range from `low` to `high`. Stops if `fn` returns a value. | ||
*/ | ||
range(low, high, fn, ctx) { | ||
const Q = []; | ||
const compare = this._comparator; | ||
let node = this._root; | ||
let cmp; | ||
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) { | ||
@@ -339,30 +341,37 @@ if (node) { | ||
return this; | ||
} | ||
}; | ||
/** | ||
* Returns array of keys | ||
*/ | ||
keys() { | ||
const keys = []; | ||
this.forEach(({ key }) => keys.push(key)); | ||
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 | ||
*/ | ||
values() { | ||
const values = []; | ||
this.forEach(({ data }) => values.push(data)); | ||
Tree.prototype.values = function () { | ||
var values = []; | ||
this.forEach(function (_a) { | ||
var data = _a.data; | ||
return values.push(data); | ||
}); | ||
return values; | ||
} | ||
min() { | ||
}; | ||
Tree.prototype.min = function () { | ||
if (this._root) | ||
return this.minNode(this._root).key; | ||
return null; | ||
} | ||
max() { | ||
}; | ||
Tree.prototype.max = function () { | ||
if (this._root) | ||
return this.maxNode(this._root).key; | ||
return null; | ||
} | ||
minNode(t = this._root) { | ||
}; | ||
Tree.prototype.minNode = function (t) { | ||
if (t === void 0) { t = this._root; } | ||
if (t) | ||
@@ -372,4 +381,5 @@ while (t.left) | ||
return t; | ||
} | ||
maxNode(t = this._root) { | ||
}; | ||
Tree.prototype.maxNode = function (t) { | ||
if (t === void 0) { t = this._root; } | ||
if (t) | ||
@@ -379,11 +389,11 @@ while (t.right) | ||
return t; | ||
} | ||
}; | ||
/** | ||
* Returns node at given index | ||
*/ | ||
at(index) { | ||
let current = this._root; | ||
let done = false; | ||
let i = 0; | ||
const Q = []; | ||
Tree.prototype.at = function (index) { | ||
var current = this._root; | ||
var done = false; | ||
var i = 0; | ||
var Q = []; | ||
while (!done) { | ||
@@ -407,6 +417,6 @@ if (current) { | ||
return null; | ||
} | ||
next(d) { | ||
let root = this._root; | ||
let successor = null; | ||
}; | ||
Tree.prototype.next = function (d) { | ||
var root = this._root; | ||
var successor = null; | ||
if (d.right) { | ||
@@ -418,5 +428,5 @@ successor = d.right; | ||
} | ||
const comparator = this._comparator; | ||
var comparator = this._comparator; | ||
while (root) { | ||
const cmp = comparator(d.key, root.key); | ||
var cmp = comparator(d.key, root.key); | ||
if (cmp === 0) | ||
@@ -432,6 +442,6 @@ break; | ||
return successor; | ||
} | ||
prev(d) { | ||
let root = this._root; | ||
let predecessor = null; | ||
}; | ||
Tree.prototype.prev = function (d) { | ||
var root = this._root; | ||
var predecessor = null; | ||
if (d.left !== null) { | ||
@@ -443,5 +453,5 @@ predecessor = d.left; | ||
} | ||
const comparator = this._comparator; | ||
var comparator = this._comparator; | ||
while (root) { | ||
const cmp = comparator(d.key, root.key); | ||
var cmp = comparator(d.key, root.key); | ||
if (cmp === 0) | ||
@@ -457,17 +467,19 @@ break; | ||
return predecessor; | ||
} | ||
clear() { | ||
}; | ||
Tree.prototype.clear = function () { | ||
this._root = null; | ||
this._size = 0; | ||
return this; | ||
} | ||
toList() { | ||
}; | ||
Tree.prototype.toList = function () { | ||
return toList(this._root); | ||
} | ||
}; | ||
/** | ||
* Bulk-load items. Both array have to be same size | ||
*/ | ||
load(keys, values = [], presort = false) { | ||
let size = keys.length; | ||
const comparator = this._comparator; | ||
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 | ||
@@ -481,3 +493,3 @@ if (presort) | ||
else { // that re-builds the whole tree from two in-order traversals | ||
const mergedList = mergeLists(this.toList(), createList(keys, values), comparator); | ||
var mergedList = mergeLists(this.toList(), createList(keys, values), comparator); | ||
size = this._size + size; | ||
@@ -487,14 +499,23 @@ this._root = sortedListToBST({ head: mergedList }, 0, size); | ||
return this; | ||
} | ||
isEmpty() { return this._root === null; } | ||
get size() { return this._size; } | ||
get root() { return this._root; } | ||
toString(printNode = (n) => String(n.key)) { | ||
const out = []; | ||
printRow(this._root, '', true, (v) => out.push(v), printNode); | ||
}; | ||
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(''); | ||
} | ||
update(key, newKey, newData) { | ||
const comparator = this._comparator; | ||
let { left, right } = split(key, this._root, comparator); | ||
}; | ||
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) { | ||
@@ -507,14 +528,15 @@ right = insert(newKey, newData, right, comparator); | ||
this._root = merge(left, right, comparator); | ||
} | ||
split(key) { | ||
}; | ||
Tree.prototype.split = function (key) { | ||
return split(key, this._root, this._comparator); | ||
} | ||
} | ||
}; | ||
return Tree; | ||
}()); | ||
function loadRecursive(keys, values, start, end) { | ||
const size = end - start; | ||
var size = end - start; | ||
if (size > 0) { | ||
const middle = start + Math.floor(size / 2); | ||
const key = keys[middle]; | ||
const data = values[middle]; | ||
const node = new Node(key, data); | ||
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); | ||
@@ -527,5 +549,5 @@ node.right = loadRecursive(keys, values, middle + 1, end); | ||
function createList(keys, values) { | ||
const head = new Node(null, null); | ||
let p = head; | ||
for (let i = 0; i < keys.length; i++) { | ||
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]); | ||
@@ -537,7 +559,7 @@ } | ||
function toList(root) { | ||
let current = root; | ||
const Q = []; | ||
let done = false; | ||
const head = new Node(null, null); | ||
let p = head; | ||
var current = root; | ||
var Q = []; | ||
var done = false; | ||
var head = new Node(null, null); | ||
var p = head; | ||
while (!done) { | ||
@@ -561,7 +583,7 @@ if (current) { | ||
function sortedListToBST(list, start, end) { | ||
const size = end - start; | ||
var size = end - start; | ||
if (size > 0) { | ||
const middle = start + Math.floor(size / 2); | ||
const left = sortedListToBST(list, start, middle); | ||
const root = list.head; | ||
var middle = start + Math.floor(size / 2); | ||
var left = sortedListToBST(list, start, middle); | ||
var root = list.head; | ||
root.left = left; | ||
@@ -575,6 +597,6 @@ list.head = list.head.next; | ||
function mergeLists(l1, l2, compare) { | ||
const head = new Node(null, null); // dummy | ||
let p = head; | ||
let p1 = l1; | ||
let p2 = l2; | ||
var head = new Node(null, null); // dummy | ||
var p = head; | ||
var p1 = l1; | ||
var p2 = l2; | ||
while (p1 !== null && p2 !== null) { | ||
@@ -602,5 +624,5 @@ if (compare(p1.key, p2.key) < 0) { | ||
return; | ||
const pivot = keys[(left + right) >> 1]; | ||
let i = left - 1; | ||
let j = right + 1; | ||
var pivot = keys[(left + right) >> 1]; | ||
var i = left - 1; | ||
var j = right + 1; | ||
while (true) { | ||
@@ -615,3 +637,3 @@ do | ||
break; | ||
let tmp = keys[i]; | ||
var tmp = keys[i]; | ||
keys[i] = keys[j]; | ||
@@ -618,0 +640,0 @@ keys[j] = tmp; |
/** | ||
* splaytree v3.0.1 | ||
* splaytree v3.1.0 | ||
* Fast Splay tree for Node and browser | ||
@@ -4,0 +4,0 @@ * |
{ | ||
"name": "splaytree", | ||
"version": "3.0.1", | ||
"version": "3.1.0", | ||
"author": "Alexander Milevski <info@w8r.name>", | ||
@@ -8,2 +8,4 @@ "license": "MIT", | ||
"main": "dist/splay.js", | ||
"browser": "dist/splay.js", | ||
"unpkg": "dist/splay.js", | ||
"module": "dist/splay.esm.js", | ||
@@ -10,0 +12,0 @@ "types": "typings/index.d.ts", |
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
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
85549
18
2537