[node-rbush] 01/05: Imported Upstream version 1.4.2
Sebastiaan Couwenberg
sebastic at moszumanska.debian.org
Thu Dec 17 03:15:58 UTC 2015
This is an automated email from the git hooks/post-receive script.
sebastic pushed a commit to branch master
in repository node-rbush.
commit 43137ede9962b4b274616e11d1696b98d6851d4a
Author: Bas Couwenberg <sebastic at xs4all.nl>
Date: Thu Dec 17 04:08:09 2015 +0100
Imported Upstream version 1.4.2
---
README.md | 22 +++++++++++++---------
package.json | 44 +++++++++-----------------------------------
rbush.js | 18 +++++++++++-------
test/test.js | 5 +++--
4 files changed, 36 insertions(+), 53 deletions(-)
diff --git a/README.md b/README.md
index e47944b..a856921 100644
--- a/README.md
+++ b/README.md
@@ -27,16 +27,16 @@ click to perform search under the cursor.
The following sample performance test was done by generating
random uniformly distributed rectangles of ~0.01% area and setting `maxEntries` to `16`
(see `debug/perf.js` script).
-Performed with Node.js v0.10.22 on a Retina Macbook Pro 15 (mid-2012).
+Performed with Node.js v5.2.0 on a Retina Macbook Pro 15 (mid-2012).
Test | RBush | [old RTree](https://github.com/imbcmdth/RTree) | Improvement
---------------------------- | ------ | ------ | ----
-insert 1M items one by one | 6.18s | 16.46s | 2.7x
-1000 searches of 0.01% area | 0.07s | 2.52s | 35x
-1000 searches of 1% area | 0.53s | 5.03s | 9.6x
-1000 searches of 10% area | 2.45s | 16.76s | 6.8x
-remove 1000 items one by one | 0.03s | 3.2s | 118x
-bulk-insert 1M items | 1.99s | n/a | 8.3x
+insert 1M items one by one | 4.7s | 9.26s | 2x
+1000 searches of 0.01% area | 0.06s | 1.12s | 20x
+1000 searches of 1% area | 0.43s | 2.73s | 6.3x
+1000 searches of 10% area | 2.19s | 11.56s | 5.3x
+remove 1000 items one by one | 0.02s | 1.44s | 65x
+bulk-insert 1M items | 1.38s | n/a | 6.7x
## Usage
@@ -134,7 +134,7 @@ Returns all items of the tree.
var result = tree.collides([40, 20, 80, 70]);
```
-Returns `true` if there are any items in the given bounding box, otherwise `false`.
+Returns `true` if there are any items intersecting the given bounding box, otherwise `false`.
### Export and Import
@@ -157,7 +157,7 @@ check out [rbush-knn](https://github.com/mourner/rbush-knn).
## Algorithms Used
-* single insertion: non-recursive R-tree insertion with overlap minimizing split routine from R*-tree (split is very effective in JS, while other R*-tree modifications like reinsertion on overflow and overlap minimizing subtree search are too slow and not worth it)
+* single insertion: non-recursive R-tree insertion with overlap minimizing split routine from R\*-tree (split is very effective in JS, while other R\*-tree modifications like reinsertion on overflow and overlap minimizing subtree search are too slow and not worth it)
* single deletion: non-recursive R-tree deletion using depth-first tree traversal with free-at-empty strategy (entries in underflowed nodes are not reinserted, instead underflowed nodes are kept in the tree and deleted only when empty, which is a good compromise of query vs removal performance)
* bulk loading: OMT algorithm (Overlap Minimizing Top-down Bulk Loading) combined with Floyd–Rivest selection algorithm
* bulk insertion: STLT algorithm (Small-Tree-Large-Tree)
@@ -187,6 +187,10 @@ RBush should run on Node and all major browsers. The only caveat: IE 8 needs an
## Changelog
+#### 1.4.2 — Dec 16, 2015
+
+- 50% faster insertion.
+
#### 1.4.1 — Sep 16, 2015
- Fixed insertion in IE8.
diff --git a/package.json b/package.json
index 89c90f3..9ebe175 100644
--- a/package.json
+++ b/package.json
@@ -1,6 +1,6 @@
{
"name": "rbush",
- "version": "1.4.1",
+ "version": "1.4.2",
"description": "High-performance 2D spatial index for rectangles (based on R*-tree with bulk loading and bulk insertion algorithms)",
"homepage": "https://github.com/mourner/rbush",
"keywords": [
@@ -19,9 +19,10 @@
"main": "rbush.js",
"devDependencies": {
"benchmark": "^1.0.0",
- "eslint": "^0.19.0",
+ "eslint": "^1.10.3",
+ "eslint-config-mourner": "^1.0.1",
"faucet": "0.0.1",
- "istanbul": "~0.3.13",
+ "istanbul": "~0.4.1",
"rtree": "~1.4.2",
"tape": "^4.0.0"
},
@@ -31,41 +32,14 @@
"cov": "istanbul cover test/test.js -x test/test.js"
},
"eslintConfig": {
+ "extends": "mourner",
"rules": {
- "no-use-before-define": [
- 2,
- "nofunc"
- ],
- "camelcase": 2,
- "space-after-function-name": 2,
- "space-in-parens": 2,
- "space-before-blocks": 2,
- "space-after-keywords": 2,
- "comma-style": 2,
- "no-lonely-if": 2,
- "no-else-return": 2,
- "no-empty": 2,
- "no-new": 2,
- "key-spacing": 2,
- "space-in-brackets": 2,
- "quotes": [
- 2,
- "single"
- ],
- "no-multi-spaces": 0,
- "new-cap": 0,
- "no-new-func": 0,
- "curly": 0,
- "no-underscore-dangle": 0,
- "no-constant-condition": 0,
- "no-shadow": 0
+ "indent": 0,
+ "strict": 0,
+ "new-cap": 0
},
"env": {
- "node": true,
- "browser": true
- },
- "globals": {
- "define": false
+ "amd": true
}
}
}
diff --git a/rbush.js b/rbush.js
index ca54327..f6975df 100644
--- a/rbush.js
+++ b/rbush.js
@@ -4,7 +4,8 @@
https://github.com/mourner/rbush
*/
-(function () { 'use strict';
+(function () {
+'use strict';
function rbush(maxEntries, format) {
@@ -233,12 +234,11 @@ rbush.prototype = {
M = Math.ceil(N / Math.pow(M, height - 1));
}
- // TODO eliminate recursion?
-
node = {
children: [],
height: height,
- bbox: null
+ bbox: null,
+ leaf: false
};
// split the items into M mostly square tiles
@@ -344,7 +344,9 @@ rbush.prototype = {
var newNode = {
children: node.children.splice(splitIndex, node.children.length - splitIndex),
- height: node.height
+ height: node.height,
+ bbox: null,
+ leaf: false
};
if (node.leaf) newNode.leaf = true;
@@ -360,7 +362,9 @@ rbush.prototype = {
// split root node
this.data = {
children: [node, newNode],
- height: node.height + 1
+ height: node.height + 1,
+ bbox: null,
+ leaf: false
};
calcBBox(this.data, this.toBBox);
},
@@ -609,7 +613,7 @@ function swap(arr, i, j) {
// export as AMD/CommonJS module or global variable
-if (typeof define === 'function' && define.amd) define('rbush', function() { return rbush; });
+if (typeof define === 'function' && define.amd) define('rbush', function () { return rbush; });
else if (typeof module !== 'undefined') module.exports = rbush;
else if (typeof self !== 'undefined') self.rbush = rbush;
else window.rbush = rbush;
diff --git a/test/test.js b/test/test.js
index 9fc820b..ff016ff 100644
--- a/test/test.js
+++ b/test/test.js
@@ -218,7 +218,7 @@ t('#collides returns false if nothing found', function (t) {
t.end();
});
-t('#all returns all points in the tree', function(t) {
+t('#all returns all points in the tree', function (t) {
var tree = rbush(4).load(data);
var result = tree.all();
@@ -263,7 +263,8 @@ t('#insert adds an item to an existing tree correctly', function (t) {
{'children':[[1,1,2,2],[2,2,2,2],[3,3,3,3]],'height':1,'leaf':true,'bbox':[1,1,3,3]}
],
'height':2,
- 'bbox':[0,0,3,3]
+ 'bbox':[0,0,3,3],
+ 'leaf':false
});
t.end();
});
--
Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-grass/node-rbush.git
More information about the Pkg-grass-devel
mailing list