Comparing version 2.0.2 to 2.0.3
/** | ||
* splaytree v2.0.2 | ||
* splaytree v2.0.3 | ||
* Fast Splay tree for Node and browser | ||
@@ -195,3 +195,4 @@ * | ||
t = splay(i, t, comparator); | ||
if (i === t.key) { /* found it */ | ||
var cmp = comparator(i, t.key); | ||
if (cmp === 0) { /* found it */ | ||
if (t.left === null) { | ||
@@ -767,1 +768,2 @@ x = t.right; | ||
export default Tree; | ||
//# sourceMappingURL=splay.es6.js.map |
/** | ||
* splaytree v2.0.2 | ||
* splaytree v2.0.3 | ||
* Fast Splay tree for Node and browser | ||
@@ -198,3 +198,4 @@ * | ||
t = splay(i, t, comparator); | ||
if (i === t.key) { /* found it */ | ||
var cmp = comparator(i, t.key); | ||
if (cmp === 0) { /* found it */ | ||
if (t.left === null) { | ||
@@ -799,1 +800,2 @@ x = t.right; | ||
}))); | ||
//# sourceMappingURL=splay.js.map |
@@ -186,3 +186,4 @@ /* follows "An implementation of top-down splaying" | ||
t = splay(i, t, comparator); | ||
if (i === t.key) { /* found it */ | ||
var cmp = comparator(i, t.key); | ||
if (cmp === 0) { /* found it */ | ||
if (t.left === null) { | ||
@@ -189,0 +190,0 @@ x = t.right; |
{ | ||
"name": "splaytree", | ||
"version": "2.0.2", | ||
"version": "2.0.3", | ||
"author": "Alexander Milevski <info@w8r.name>", | ||
@@ -23,28 +23,25 @@ "license": "MIT", | ||
"lint": "eslint index.js", | ||
"build": "rollup -c build/rollup.config.umd.js && rollup -c build/rollup.config.es6.js && npm run types", | ||
"build": "rollup -c && npm run types", | ||
"types": "tsc index.d.ts tests/types.ts", | ||
"pretest": "rollup -c build/rollup.config.tests.js", | ||
"prebenchmark": "npm run build", | ||
"benchmark": "node bench/benchmark.js", | ||
"benchmark": "node -r reify bench/benchmark.js", | ||
"start": "npm run test:watch", | ||
"test:watch": "nodemon --watch src --watch tests --exec 'npm test'", | ||
"test": "mocha build/tests-bundle.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" | ||
}, | ||
"devDependencies": { | ||
"@types/node": "^8.0.0", | ||
"avl": "^1.4.3", | ||
"avl": "^1.4.4", | ||
"benchmark": "^2.1.4", | ||
"bintrees": "^1.0.2", | ||
"chai": "^4.1.2", | ||
"eslint": "^4.19.1", | ||
"eslint-config-airbnb-base": "^12.1.0", | ||
"eslint-plugin-import": "^2.11.0", | ||
"mocha": "^5.1.1", | ||
"nodemon": "^1.17.4", | ||
"rollup": "^0.58.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", | ||
"rollup-plugin-multi-entry": "^2.0.2", | ||
"source-map-support": "^0.5.5", | ||
"typescript": "^2.8.3" | ||
"typescript": "^3.0.3" | ||
}, | ||
@@ -51,0 +48,0 @@ "keywords": [ |
# 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) | ||
[Splay-tree](https://en.wikipedia.org/wiki/Splay_tree): **[fast](#benchmarks)**(non-recursive) and **simple**(< 1000 lines of code) | ||
Implementation is adapted directly from Wikipedia with the same API as [w8r/avl](https://github.com/w8r/avl), to run the benchmarks agains other trees. | ||
Implementation is adapted directly from Wikipedia with the same API as [w8r/avl](https://github.com/w8r/avl), to run the benchmarks against other trees. | ||
This tree is based on **top-down** splaying algorithm by D.Sleator. It supports | ||
@@ -48,4 +49,5 @@ - splitting, merging | ||
* `new SplayTree([comparator], [noDuplicates:Boolean])`, where `comparator` is optional comparison function | ||
* `tree.insert(key:any, [data:any]):Node` - Insert item | ||
* `new SplayTree([comparator])`, where `comparator` is optional comparison function | ||
* `tree.insert(key:any, [data:any]):Node` - Insert item, allow duplicate keys | ||
* `tree.add(key:any, [data:any]):Node` - Insert item if it is not present | ||
* `tree.remove(key:any):Boolean` - Remove item | ||
@@ -85,9 +87,5 @@ * `tree.removeNode(Node:any)|Boolean` - Remove node | ||
By default, tree allows duplicate keys. You can disable that by passing `true` | ||
as a second parameter to the tree constructor. In that case if you would try to | ||
instert an item with the key, that is already present in the tree, it will not | ||
be inserted. | ||
However, the default behavior allows for duplicate keys, cause there are cases | ||
where you cannot predict that the keys would be unique (example: overlapping | ||
* `insert()` method allows duplicate keys. This can be useful in certain applications (example: overlapping | ||
points in 2D). | ||
* `add()` method will not allow duplicate keys - if key is already present in the tree, no new node is created | ||
@@ -189,3 +187,3 @@ ## Example | ||
Adding google closure library to the benchmark is, of course, unfair, cause the | ||
node.js version of it is not optimised by the compiler, but in this case it | ||
node.js version of it is not optimized by the compiler, but in this case it | ||
plays the role of straight-forward robust implementation. | ||
@@ -192,0 +190,0 @@ |
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
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
129019
13
1962
223