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.0.1 to 3.1.0

dist/index.d.ts
dist/index.js
dist/node.d.ts
dist/node.js
dist/types.d.ts
dist/types.js

306

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

2

dist/splay.js
/**
* splaytree v3.0.1
* splaytree v3.1.0
* Fast Splay tree for Node and browser

@@ -4,0 +4,0 @@ *

4

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

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