This is an automated email from the git hooks/post-receive script.

johanvdw-guest pushed a commit to branch master
in repository node-rbush.

commit 76871340122533d75d80f5a7616c190587e3a7bc
Author: Johan Van de Wauw <johan.vandew...@gmail.com>
Date:   Wed Jan 7 20:54:12 2015 +0100

    Imported Upstream version 1.3.4
---
 .gitignore                |   3 +
 .travis.yml               |   3 +
 MIT-LICENSE               |  19 ++
 README.md                 | 216 +++++++++++++++++
 bench/bulk.bench.js       |  21 ++
 bench/bulksearch.bench.js |  38 +++
 bench/gendata.js          |  26 ++
 bench/insert.bench.js     |  33 +++
 bench/perf.js             | 164 +++++++++++++
 bench/search.bench.js     |  40 ++++
 package.json              |  47 ++++
 rbush.js                  | 587 ++++++++++++++++++++++++++++++++++++++++++++++
 test/test.js              | 329 ++++++++++++++++++++++++++
 viz/viz-cluster.html      |  72 ++++++
 viz/viz-uniform.html      |  68 ++++++
 viz/viz.js                |  96 ++++++++
 16 files changed, 1762 insertions(+)

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..801e184
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+node_modules
+npm-debug.log
+coverage
diff --git a/.travis.yml b/.travis.yml
new file mode 100644
index 0000000..6e5919d
--- /dev/null
+++ b/.travis.yml
@@ -0,0 +1,3 @@
+language: node_js
+node_js:
+  - "0.10"
diff --git a/MIT-LICENSE b/MIT-LICENSE
new file mode 100644
index 0000000..226ace0
--- /dev/null
+++ b/MIT-LICENSE
@@ -0,0 +1,19 @@
+Copyright (c) 2013 Vladimir Agafonkin
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..6022826
--- /dev/null
+++ b/README.md
@@ -0,0 +1,216 @@
+RBush
+=====
+
+RBush is a high-performance JavaScript library for 2D **spatial indexing** of 
points and rectangles
+by [Vladimir Agafonkin](http://github.com/mourner),
+based on an optimized **R-tree** data structure with **bulk insertion** 
support.
+
+*Spatial index* is a special data structure for points and rectangles
+that allows you to perform queries like "all items within this bounding box" 
very efficiently
+(e.g. hundreds of times faster than looping over all items).
+It's most commonly used in maps and data visualizations.
+
+[![Build 
Status](https://travis-ci.org/mourner/rbush.png?branch=master)](https://travis-ci.org/mourner/rbush)
+
+## Demos
+
+The demos contain visualization of trees generated from 50k bulk-loaded random 
points.
+Open web console to see benchmarks;
+click on buttons to insert or remove items;
+click to perform search under the cursor.
+
+* [uniformly distributed random 
data](http://mourner.github.io/rbush/viz/viz-uniform.html)
+* [randomly clustered 
data](http://mourner.github.io/rbush/viz/viz-cluster.html)
+
+## Performance
+
+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).
+
+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
+
+## Usage
+
+### Creating a Tree
+
+```js
+var tree = rbush(9);
+```
+
+An optional argument to `rbush` defines the maximum number of entries in a 
tree node.
+It drastically affects the performance, so you should adjust it
+considering the type of data and search queries you perform.
+
+### Adding and Removing Data
+
+Insert an item:
+
+```js
+var item = [20, 40, 30, 50]; // [x1, y1, x2, y2]
+tree.insert(item);
+```
+
+Remove a previously inserted item:
+
+```js
+tree.remove(item);
+```
+
+Clear all items:
+
+```js
+tree.clear();
+```
+
+Items inserted in the tree can have other arbitrary properties/elements that 
you can access later:
+
+```js
+var item1 = [20, 40, 30, 50, {foo: 'bar'}];
+tree.insert(item1);
+
+var item2 = [15, 15, 30, 30];
+item2.foo = 'bar';
+tree.insert(item2);
+```
+
+### Data Format
+
+By default, RBush assumes the format of data points to be `[minX, minY, maxX, 
maxY]`
+(bounding box coordinates, or just `[x, y, x, y]` for points).
+You can customize this by providing an array with `minX`, `minY`, `maxX`, 
`maxY` accessor strings
+as a second argument to `rbush` like this:
+
+```js
+var tree = rbush(9, ['.minLng', '.minLat', '.maxLng', '.maxLat']);
+tree.insert({id: 'foo', minLng: 30, minLat: 50, maxLng: 40, maxLat: 60});
+```
+
+### Bulk-Inserting Data
+
+Bulk-insert the given data into the tree:
+
+```js
+tree.load([
+       [10, 10, 15, 20],
+       [12, 15, 40, 64.5],
+       ...
+]);
+```
+
+Bulk insertion is usually ~2-3 times faster than inserting items one by one.
+After bulk loading (bulk insertion into an empty tree), subsequent query 
performance is also ~20-30% better.
+
+When you do bulk insertion into an existing tree, it bulk-loads the given data 
into a separate tree
+and inserts the smaller tree into the larger tree.
+This means that bulk insertion works very well for clustered data (where items 
are close to each other),
+but makes query performance worse if the data is scattered.
+
+### Search
+
+```js
+var result = tree.search([40, 20, 80, 70]);
+```
+
+Returns an array of data items (points or rectangles) that the given bounding 
box (`[minX, minY, maxX, maxY]`) intersects.
+
+```js
+var allItems = tree.all();
+```
+
+Returns all items of the tree.
+
+### Export and Import
+
+```js
+// export data as JSON object
+var treeData = tree.toJSON();
+
+// import previously exported data
+var tree = rbush(9).fromJSON(treeData);
+```
+
+Importing and exporting as JSON allows you to use RBush on both the server 
(using Node.js) and the browser combined,
+e.g. first indexing the data on the server and and then importing the 
resulting tree data on the client for searching.
+
+## 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 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)
+* search: standard non-recursive R-tree search
+
+## Papers
+
+* [R-trees: a Dynamic Index Structure For Spatial 
Searching](http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf)
+* [The R*-tree: An Efficient and Robust Access Method for Points and 
Rectangles+](http://dbs.mathematik.uni-marburg.de/publications/myPapers/1990/BKSS90.pdf)
+* [OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for 
R-tree](http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-74/files/FORUM_18.pdf)
+* [Bulk Insertions into R-Trees Using the Small-Tree-Large-Tree 
Approach](http://www.cs.arizona.edu/~bkmoon/papers/dke06-bulk.pdf)
+* [R-Trees: Theory and Applications 
(book)](http://www.apress.com/9781852339777)
+
+## Development
+
+```bash
+npm install  # install dependencies
+
+npm test     # check the code with JSHint and run tests
+npm run perf # run performance benchmarks
+npm run cov  # report test coverage (with more detailed report in 
coverage/lcov-report/index.html)
+```
+
+## Changelog
+
+#### 1.3.4 &mdash; Aug 31, 2014
+
+- Improved bulk insertion performance for a large number of items (e.g. up to 
100% for inserting a million items).
+- Fixed performance regression for high node sizes.
+
+#### 1.3.3 &mdash; Aug 30, 2014
+
+- Improved bulk insertion performance by ~60-70%.
+- Improved insertion performance by ~40%.
+- Improved search performance by ~30%.
+
+#### 1.3.2 &mdash; Nov 25, 2013
+
+- Improved removal performance by ~50%. 
[#18](https://github.com/mourner/rbush/pull/18)
+
+#### 1.3.1 &mdash; Nov 24, 2013
+
+- Fixed minor error in the choose split axis algorithm. 
[#17](https://github.com/mourner/rbush/pull/17)
+- Much better test coverage (near 100%). 
[#6](https://github.com/mourner/rbush/issues/6)
+
+#### 1.3.0 &mdash; Nov 21, 2013
+
+- Significantly improved search performance (especially on large-bbox queries 
— up to 3x faster). [#11](https://github.com/mourner/rbush/pull/11)
+- Added `all` method for getting all of the tree items. 
[#11](https://github.com/mourner/rbush/pull/11)
+- Made `toBBox`, `compareMinX`, `compareMinY` methods public, made it possible 
to avoid Content Security Policy issues by overriding them for custom format. 
[#14](https://github.com/mourner/rbush/pull/14) 
[#12](https://github.com/mourner/rbush/pull/12)
+
+#### 1.2.5 &mdash; Nov 5, 2013
+
+- Fixed a bug where insertion failed on a tree that had all items removed 
previously. [#10](https://github.com/mourner/rbush/issues/10)
+
+#### 1.2.4 &mdash; Oct 25, 2013
+
+- Added Web Workers support. [#9](https://github.com/mourner/rbush/pull/9)
+
+#### 1.2.3 &mdash; Aug 30, 2013
+
+- Added AMD support. [#8](https://github.com/mourner/rbush/pull/8)
+
+#### 1.2.2 &mdash; Aug 27, 2013
+
+- Eliminated recursion when recalculating node bboxes (on insert, remove, 
load).
+
+#### 1.2.0 &mdash; Jul 19, 2013
+
+First fully functional RBush release.
diff --git a/bench/bulk.bench.js b/bench/bulk.bench.js
new file mode 100644
index 0000000..52e31b4
--- /dev/null
+++ b/bench/bulk.bench.js
@@ -0,0 +1,21 @@
+var Benchmark = require('benchmark'),
+    rbush = require('../rbush'),
+    genData = require('./gendata');
+
+var N = 10000,
+    maxFill = 16;
+
+var data = genData(N, 1);
+
+new Benchmark.Suite()
+.add('bulk loading ' + N + ' items (' + maxFill + ' node size)', function () {
+    var tree = rbush(maxFill);
+    tree.load(data);
+})
+.on('error', function(event) {
+    console.log(event.target.error);
+})
+.on('cycle', function(event) {
+    console.log(String(event.target));
+})
+.run();
diff --git a/bench/bulksearch.bench.js b/bench/bulksearch.bench.js
new file mode 100644
index 0000000..39b3af8
--- /dev/null
+++ b/bench/bulksearch.bench.js
@@ -0,0 +1,38 @@
+var Benchmark = require('benchmark'),
+    rbush = require('../rbush'),
+    genData = require('./gendata');
+
+var N = 10000,
+    maxFill = 16;
+
+var data = genData(N, 1);
+var bboxes100 = genData(1000, 100 * Math.sqrt(0.1));
+var bboxes10 = genData(1000, 10);
+var bboxes1 = genData(1000, 1);
+
+var tree = rbush(maxFill);
+tree.load(data);
+
+new Benchmark.Suite()
+.add('1000 searches 10% after bulk loading ' + N, function () {
+    for (i = 0; i < 1000; i++) {
+        tree.search(bboxes100[i]);
+    }
+})
+.add('1000 searches 1% after bulk loading ' + N, function () {
+    for (i = 0; i < 1000; i++) {
+        tree.search(bboxes10[i]);
+    }
+})
+.add('1000 searches 0.01% after bulk loading ' + N, function () {
+    for (i = 0; i < 1000; i++) {
+        tree.search(bboxes1[i]);
+    }
+})
+.on('error', function(event) {
+    console.log(event.target.error);
+})
+.on('cycle', function(event) {
+    console.log(String(event.target));
+})
+.run();
diff --git a/bench/gendata.js b/bench/gendata.js
new file mode 100644
index 0000000..27bf1ae
--- /dev/null
+++ b/bench/gendata.js
@@ -0,0 +1,26 @@
+
+module.exports = genData;
+
+function randBox(size) {
+    var x = Math.random() * (100 - size),
+        y = Math.random() * (100 - size);
+    return [x, y,
+        x + size * Math.random(),
+        y + size * Math.random()];
+}
+
+function genData(N, size) {
+    var data = [];
+    for (var i = 0; i < N; i++) {
+        data.push(randBox(size));
+    }
+    return data;
+};
+
+genData.convert = function (data) {
+    var result = [];
+    for (var i = 0; i < data.length; i++) {
+        result.push({x: data[i][0], y: data[i][1], w: data[i][2] - data[i][0], 
h: data[i][3] - data[i][1]});
+    }
+    return result;
+}
diff --git a/bench/insert.bench.js b/bench/insert.bench.js
new file mode 100644
index 0000000..6fc7ad5
--- /dev/null
+++ b/bench/insert.bench.js
@@ -0,0 +1,33 @@
+var Benchmark = require('benchmark'),
+    rbush = require('../rbush'),
+    genData = require('./gendata');
+
+var RTree = require('rtree');
+
+
+var N = 10000,
+    maxFill = 16;
+
+var data = genData(N, 1);
+var data2 = genData.convert(data);
+
+new Benchmark.Suite()
+.add('insert ' + N + ' items (' + maxFill + ' node size)', function () {
+    var tree = rbush(maxFill);
+    for (var i = 0; i < N; i++) {
+        tree.insert(data[i]);
+    }
+})
+.add('insert ' + N + ' items (' + maxFill + ' node size), old RTree', function 
() {
+    var tree2 = new RTree(maxFill);
+    for (var i = 0; i < N; i++) {
+        tree2.insert(data2[i], i);
+    }
+})
+.on('error', function(event) {
+    console.log(event.target.error);
+})
+.on('cycle', function(event) {
+    console.log(String(event.target));
+})
+.run();
diff --git a/bench/perf.js b/bench/perf.js
new file mode 100644
index 0000000..45c2c79
--- /dev/null
+++ b/bench/perf.js
@@ -0,0 +1,164 @@
+
+var N = 1000000,
+    maxFill = 16;
+
+console.log('number: ' + N);
+console.log('maxFill: ' + maxFill);
+
+
+function randBox(size) {
+    var x = Math.random() * (100 - size),
+        y = Math.random() * (100 - size);
+    return [x, y,
+        x + size * Math.random(),
+        y + size * Math.random()];
+}
+
+function genData(N, size) {
+    var data = [];
+    for (var i = 0; i < N; i++) {
+        data.push(randBox(size));
+    }
+    return data;
+}
+
+
+var data = genData(N, 1);
+
+var rbush = typeof require !== 'undefined' ? require('../rbush.js') : rbush;
+var tree = rbush(maxFill);
+
+
+console.time('insert one by one');
+for (i = 0; i < N; i++) {
+    tree.insert(data[i]);
+}
+console.timeEnd('insert one by one');
+
+
+// console.time('bulk load');
+// tree.load(data);
+// console.timeEnd('bulk load');
+
+
+var bboxes100 = genData(1000, 100 * Math.sqrt(0.1));
+
+console.time('1000 searches 10%');
+for (i = 0; i < 1000; i++) {
+    tree.search(bboxes100[i]);
+}
+console.timeEnd('1000 searches 10%');
+
+
+var bboxes10 = genData(1000, 10);
+
+console.time('1000 searches 1%');
+for (i = 0; i < 1000; i++) {
+    tree.search(bboxes10[i]);
+}
+console.timeEnd('1000 searches 1%');
+
+
+var bboxes1 = genData(1000, 1);
+
+console.time('1000 searches 0.01%');
+for (i = 0; i < 1000; i++) {
+    tree.search(bboxes1[i]);
+}
+console.timeEnd('1000 searches 0.01%');
+
+
+console.time('remove 1000 one by one');
+for (i = 0; i < 1000; i++) {
+    tree.remove(data[i]);
+}
+console.timeEnd('remove 1000 one by one');
+
+
+var data2 = genData(N, 1);
+
+console.time('bulk-insert 1M more');
+tree.load(data2);
+console.timeEnd('bulk-insert 1M more');
+
+
+console.time('1000 searches 1%');
+for (i = 0; i < 1000; i++) {
+    tree.search(bboxes10[i]);
+}
+console.timeEnd('1000 searches 1%');
+
+
+console.time('1000 searches 0.01%');
+for (i = 0; i < 1000; i++) {
+    tree.search(bboxes1[i]);
+}
+console.timeEnd('1000 searches 0.01%');
+
+
+// console.time('100 naive searches 1%');
+// var result;
+// for (var j = 0; j < 100; j++) {
+//     result = [];
+//     for (i = 0; i < N; i++) {
+//         if (tree._intersects(bboxes10[j], data[i])) {
+//             result.push(data[i]);
+//         }
+//     }
+// }
+// console.timeEnd('100 naive searches 1%');
+
+
+
+var RTree = typeof require !== 'undefined' ? require('rtree') : RTree;
+
+var tree2 = new RTree(maxFill);
+
+function convertData(data) {
+    var result = [];
+    for (var i = 0; i < data.length; i++) {
+        result.push({x: data[i][0], y: data[i][1], w: data[i][2] - data[i][0], 
h: data[i][3] - data[i][1]});
+    }
+    return result;
+}
+
+var datab = convertData(data);
+
+console.time('old RTree load one by one');
+for (var i = 0; i < N; i++) {
+    tree2.insert(datab[i], i);
+}
+console.timeEnd('old RTree load one by one');
+
+
+var bboxes100b = convertData(bboxes100);
+
+console.time('1000 searches 10% 2');
+for (i = 0; i < 1000; i++) {
+    tree2.search(bboxes100b[i]);
+}
+console.timeEnd('1000 searches 10% 2');
+
+
+var bboxes10b = convertData(bboxes10);
+
+console.time('1000 searches 1% 2');
+for (i = 0; i < 1000; i++) {
+    tree2.search(bboxes10b[i]);
+}
+console.timeEnd('1000 searches 1% 2');
+
+
+var bboxes1b = convertData(bboxes1);
+
+console.time('1000 searches 0.01% 2');
+for (i = 0; i < 1000; i++) {
+    tree2.search(bboxes1b[i]);
+}
+console.timeEnd('1000 searches 0.01% 2');
+
+console.time('old RTree remove 1000 one by one');
+for (var i = 0; i < 1000; i++) {
+    tree2.remove(datab[i], i);
+}
+console.timeEnd('old RTree remove 1000 one by one');
diff --git a/bench/search.bench.js b/bench/search.bench.js
new file mode 100644
index 0000000..0b03464
--- /dev/null
+++ b/bench/search.bench.js
@@ -0,0 +1,40 @@
+var Benchmark = require('benchmark'),
+    rbush = require('../rbush'),
+    genData = require('./gendata');
+
+var N = 10000,
+    maxFill = 16;
+
+var data = genData(N, 1);
+var bboxes100 = genData(1000, 100 * Math.sqrt(0.1));
+var bboxes10 = genData(1000, 10);
+var bboxes1 = genData(1000, 1);
+
+var tree = rbush(maxFill);
+for (var i = 0; i < N; i++) {
+    tree.insert(data[i]);
+}
+
+new Benchmark.Suite()
+.add('1000 searches 10% after bulk loading ' + N, function () {
+    for (i = 0; i < 1000; i++) {
+        tree.search(bboxes100[i]);
+    }
+})
+.add('1000 searches 1% after bulk loading ' + N, function () {
+    for (i = 0; i < 1000; i++) {
+        tree.search(bboxes10[i]);
+    }
+})
+.add('1000 searches 0.01% after bulk loading ' + N, function () {
+    for (i = 0; i < 1000; i++) {
+        tree.search(bboxes1[i]);
+    }
+})
+.on('error', function(event) {
+    console.log(event.target.error);
+})
+.on('cycle', function(event) {
+    console.log(String(event.target));
+})
+.run();
diff --git a/package.json b/package.json
new file mode 100644
index 0000000..7dd10dd
--- /dev/null
+++ b/package.json
@@ -0,0 +1,47 @@
+{
+  "name": "rbush",
+  "version": "1.3.4",
+  "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": [
+    "spatial",
+    "tree",
+    "search",
+    "rectangle",
+    "index",
+    "math"
+  ],
+  "author": "Vladimir Agafonkin",
+  "repository": {
+    "type": "git",
+    "url": "git://github.com/mourner/rbush.git"
+  },
+  "main": "rbush.js",
+  "devDependencies": {
+    "benchmark": "^1.0.0",
+    "faucet": "0.0.1",
+    "istanbul": "~0.3.0",
+    "jshint": "^2.5.5",
+    "rtree": "~1.4.2",
+    "tape": "^2.14.0"
+  },
+  "scripts": {
+    "test": "jshint rbush.js test/test.js && node test/test.js | faucet",
+    "perf": "node ./debug/perf.js",
+    "cov": "istanbul cover test/test.js -x test/test.js"
+  },
+  "jshintConfig": {
+    "unused": "true",
+    "undef": true,
+    "trailing": true,
+    "eqeqeq": true,
+    "es3": true,
+    "indent": 4,
+    "node": true,
+    "browser": true,
+    "worker": true,
+    "globals": {
+      "define": false
+    }
+  }
+}
diff --git a/rbush.js b/rbush.js
new file mode 100644
index 0000000..b151197
--- /dev/null
+++ b/rbush.js
@@ -0,0 +1,587 @@
+/*
+ (c) 2013, Vladimir Agafonkin
+ RBush, a JavaScript library for high-performance 2D spatial indexing of 
points and rectangles.
+ https://github.com/mourner/rbush
+*/
+
+(function () { 'use strict';
+
+function rbush(maxEntries, format) {
+
+    // jshint newcap: false, validthis: true
+    if (!(this instanceof rbush)) return new rbush(maxEntries, format);
+
+    // max entries in a node is 9 by default; min node fill is 40% for best 
performance
+    this._maxEntries = Math.max(4, maxEntries || 9);
+    this._minEntries = Math.max(2, Math.ceil(this._maxEntries * 0.4));
+
+    if (format) {
+        this._initFormat(format);
+    }
+
+    this.clear();
+}
+
+rbush.prototype = {
+
+    all: function () {
+        return this._all(this.data, []);
+    },
+
+    search: function (bbox) {
+
+        var node = this.data,
+            result = [],
+            toBBox = this.toBBox;
+
+        if (!intersects(bbox, node.bbox)) return result;
+
+        var nodesToSearch = [],
+            i, len, child, childBBox;
+
+        while (node) {
+            for (i = 0, len = node.children.length; i < len; i++) {
+
+                child = node.children[i];
+                childBBox = node.leaf ? toBBox(child) : child.bbox;
+
+                if (intersects(bbox, childBBox)) {
+                    if (node.leaf) result.push(child);
+                    else if (contains(bbox, childBBox)) this._all(child, 
result);
+                    else nodesToSearch.push(child);
+                }
+            }
+            node = nodesToSearch.pop();
+        }
+
+        return result;
+    },
+
+    load: function (data) {
+        if (!(data && data.length)) return this;
+
+        if (data.length < this._minEntries) {
+            for (var i = 0, len = data.length; i < len; i++) {
+                this.insert(data[i]);
+            }
+            return this;
+        }
+
+        // recursively build the tree with the given data from stratch using 
OMT algorithm
+        var node = this._build(data.slice(), 0, data.length - 1, 0);
+
+        if (!this.data.children.length) {
+            // save as is if tree is empty
+            this.data = node;
+
+        } else if (this.data.height === node.height) {
+            // split root if trees have the same height
+            this._splitRoot(this.data, node);
+
+        } else {
+            if (this.data.height < node.height) {
+                // swap trees if inserted one is bigger
+                var tmpNode = this.data;
+                this.data = node;
+                node = tmpNode;
+            }
+
+            // insert the small tree into the large tree at appropriate level
+            this._insert(node, this.data.height - node.height - 1, true);
+        }
+
+        return this;
+    },
+
+    insert: function (item) {
+        if (item) this._insert(item, this.data.height - 1);
+        return this;
+    },
+
+    clear: function () {
+        this.data = {
+            children: [],
+            height: 1,
+            bbox: empty(),
+            leaf: true
+        };
+        return this;
+    },
+
+    remove: function (item) {
+        if (!item) return this;
+
+        var node = this.data,
+            bbox = this.toBBox(item),
+            path = [],
+            indexes = [],
+            i, parent, index, goingUp;
+
+        // depth-first iterative tree traversal
+        while (node || path.length) {
+
+            if (!node) { // go up
+                node = path.pop();
+                parent = path[path.length - 1];
+                i = indexes.pop();
+                goingUp = true;
+            }
+
+            if (node.leaf) { // check current node
+                index = node.children.indexOf(item);
+
+                if (index !== -1) {
+                    // item found, remove the item and condense tree upwards
+                    node.children.splice(index, 1);
+                    path.push(node);
+                    this._condense(path);
+                    return this;
+                }
+            }
+
+            if (!goingUp && !node.leaf && contains(node.bbox, bbox)) { // go 
down
+                path.push(node);
+                indexes.push(i);
+                i = 0;
+                parent = node;
+                node = node.children[0];
+
+            } else if (parent) { // go right
+                i++;
+                node = parent.children[i];
+                goingUp = false;
+
+            } else node = null; // nothing found
+        }
+
+        return this;
+    },
+
+    toBBox: function (item) { return item; },
+
+    compareMinX: function (a, b) { return a[0] - b[0]; },
+    compareMinY: function (a, b) { return a[1] - b[1]; },
+
+    toJSON: function () { return this.data; },
+
+    fromJSON: function (data) {
+        this.data = data;
+        return this;
+    },
+
+    _all: function (node, result) {
+        var nodesToSearch = [];
+        while (node) {
+            if (node.leaf) result.push.apply(result, node.children);
+            else nodesToSearch.push.apply(nodesToSearch, node.children);
+
+            node = nodesToSearch.pop();
+        }
+        return result;
+    },
+
+    _build: function (items, left, right, height) {
+
+        var N = right - left + 1,
+            M = this._maxEntries,
+            node;
+
+        if (N <= M) {
+            // reached leaf level; return leaf
+            node = {
+                children: items.slice(left, right + 1),
+                height: 1,
+                bbox: null,
+                leaf: true
+            };
+            calcBBox(node, this.toBBox);
+            return node;
+        }
+
+        if (!height) {
+            // target height of the bulk-loaded tree
+            height = Math.ceil(Math.log(N) / Math.log(M));
+
+            // target number of root entries to maximize storage utilization
+            M = Math.ceil(N / Math.pow(M, height - 1));
+        }
+
+        // TODO eliminate recursion?
+
+        node = {
+            children: [],
+            height: height,
+            bbox: null
+        };
+
+        // split the items into M mostly square tiles
+
+        var N2 = Math.ceil(N / M),
+            N1 = N2 * Math.ceil(Math.sqrt(M)),
+            i, j, right2, right3;
+
+        multiSelect(items, left, right, N1, this.compareMinX);
+
+        for (i = left; i <= right; i += N1) {
+
+            right2 = Math.min(i + N1 - 1, right);
+
+            multiSelect(items, i, right2, N2, this.compareMinY);
+
+            for (j = i; j <= right2; j += N2) {
+
+                right3 = Math.min(j + N2 - 1, right2);
+
+                // pack each entry recursively
+                node.children.push(this._build(items, j, right3, height - 1));
+            }
+        }
+
+        calcBBox(node, this.toBBox);
+
+        return node;
+    },
+
+    _chooseSubtree: function (bbox, node, level, path) {
+
+        var i, len, child, targetNode, area, enlargement, minArea, 
minEnlargement;
+
+        while (true) {
+            path.push(node);
+
+            if (node.leaf || path.length - 1 === level) break;
+
+            minArea = minEnlargement = Infinity;
+
+            for (i = 0, len = node.children.length; i < len; i++) {
+                child = node.children[i];
+                area = bboxArea(child.bbox);
+                enlargement = enlargedArea(bbox, child.bbox) - area;
+
+                // choose entry with the least area enlargement
+                if (enlargement < minEnlargement) {
+                    minEnlargement = enlargement;
+                    minArea = area < minArea ? area : minArea;
+                    targetNode = child;
+
+                } else if (enlargement === minEnlargement) {
+                    // otherwise choose one with the smallest area
+                    if (area < minArea) {
+                        minArea = area;
+                        targetNode = child;
+                    }
+                }
+            }
+
+            node = targetNode;
+        }
+
+        return node;
+    },
+
+    _insert: function (item, level, isNode) {
+
+        var toBBox = this.toBBox,
+            bbox = isNode ? item.bbox : toBBox(item),
+            insertPath = [];
+
+        // find the best node for accommodating the item, saving all nodes 
along the path too
+        var node = this._chooseSubtree(bbox, this.data, level, insertPath);
+
+        // put the item into the node
+        node.children.push(item);
+        extend(node.bbox, bbox);
+
+        // split on node overflow; propagate upwards if necessary
+        while (level >= 0) {
+            if (insertPath[level].children.length > this._maxEntries) {
+                this._split(insertPath, level);
+                level--;
+            } else break;
+        }
+
+        // adjust bboxes along the insertion path
+        this._adjustParentBBoxes(bbox, insertPath, level);
+    },
+
+    // split overflowed node into two
+    _split: function (insertPath, level) {
+
+        var node = insertPath[level],
+            M = node.children.length,
+            m = this._minEntries;
+
+        this._chooseSplitAxis(node, m, M);
+
+        var newNode = {
+            children: node.children.splice(this._chooseSplitIndex(node, m, M)),
+            height: node.height
+        };
+
+        if (node.leaf) newNode.leaf = true;
+
+        calcBBox(node, this.toBBox);
+        calcBBox(newNode, this.toBBox);
+
+        if (level) insertPath[level - 1].children.push(newNode);
+        else this._splitRoot(node, newNode);
+    },
+
+    _splitRoot: function (node, newNode) {
+        // split root node
+        this.data = {
+            children: [node, newNode],
+            height: node.height + 1
+        };
+        calcBBox(this.data, this.toBBox);
+    },
+
+    _chooseSplitIndex: function (node, m, M) {
+
+        var i, bbox1, bbox2, overlap, area, minOverlap, minArea, index;
+
+        minOverlap = minArea = Infinity;
+
+        for (i = m; i <= M - m; i++) {
+            bbox1 = distBBox(node, 0, i, this.toBBox);
+            bbox2 = distBBox(node, i, M, this.toBBox);
+
+            overlap = intersectionArea(bbox1, bbox2);
+            area = bboxArea(bbox1) + bboxArea(bbox2);
+
+            // choose distribution with minimum overlap
+            if (overlap < minOverlap) {
+                minOverlap = overlap;
+                index = i;
+
+                minArea = area < minArea ? area : minArea;
+
+            } else if (overlap === minOverlap) {
+                // otherwise choose distribution with minimum area
+                if (area < minArea) {
+                    minArea = area;
+                    index = i;
+                }
+            }
+        }
+
+        return index;
+    },
+
+    // sorts node children by the best axis for split
+    _chooseSplitAxis: function (node, m, M) {
+
+        var compareMinX = node.leaf ? this.compareMinX : compareNodeMinX,
+            compareMinY = node.leaf ? this.compareMinY : compareNodeMinY,
+            xMargin = this._allDistMargin(node, m, M, compareMinX),
+            yMargin = this._allDistMargin(node, m, M, compareMinY);
+
+        // if total distributions margin value is minimal for x, sort by minX,
+        // otherwise it's already sorted by minY
+        if (xMargin < yMargin) node.children.sort(compareMinX);
+    },
+
+    // total margin of all possible split distributions where each node is at 
least m full
+    _allDistMargin: function (node, m, M, compare) {
+
+        node.children.sort(compare);
+
+        var toBBox = this.toBBox,
+            leftBBox = distBBox(node, 0, m, toBBox),
+            rightBBox = distBBox(node, M - m, M, toBBox),
+            margin = bboxMargin(leftBBox) + bboxMargin(rightBBox),
+            i, child;
+
+        for (i = m; i < M - m; i++) {
+            child = node.children[i];
+            extend(leftBBox, node.leaf ? toBBox(child) : child.bbox);
+            margin += bboxMargin(leftBBox);
+        }
+
+        for (i = M - m - 1; i >= m; i--) {
+            child = node.children[i];
+            extend(rightBBox, node.leaf ? toBBox(child) : child.bbox);
+            margin += bboxMargin(rightBBox);
+        }
+
+        return margin;
+    },
+
+    _adjustParentBBoxes: function (bbox, path, level) {
+        // adjust bboxes along the given tree path
+        for (var i = level; i >= 0; i--) {
+            extend(path[i].bbox, bbox);
+        }
+    },
+
+    _condense: function (path) {
+        // go through the path, removing empty nodes and updating bboxes
+        for (var i = path.length - 1, siblings; i >= 0; i--) {
+            if (path[i].children.length === 0) {
+                if (i > 0) {
+                    siblings = path[i - 1].children;
+                    siblings.splice(siblings.indexOf(path[i]), 1);
+
+                } else this.clear();
+
+            } else calcBBox(path[i], this.toBBox);
+        }
+    },
+
+    _initFormat: function (format) {
+        // data format (minX, minY, maxX, maxY accessors)
+
+        // uses eval-type function compilation instead of just accepting a 
toBBox function
+        // because the algorithms are very sensitive to sorting functions 
performance,
+        // so they should be dead simple and without inner calls
+
+        // jshint evil: true
+
+        var compareArr = ['return a', ' - b', ';'];
+
+        this.compareMinX = new Function('a', 'b', compareArr.join(format[0]));
+        this.compareMinY = new Function('a', 'b', compareArr.join(format[1]));
+
+        this.toBBox = new Function('a', 'return [a' + format.join(', a') + 
'];');
+    }
+};
+
+
+// calculate node's bbox from bboxes of its children
+function calcBBox(node, toBBox) {
+    node.bbox = distBBox(node, 0, node.children.length, toBBox);
+}
+
+// min bounding rectangle of node children from k to p-1
+function distBBox(node, k, p, toBBox) {
+    var bbox = empty();
+
+    for (var i = k, child; i < p; i++) {
+        child = node.children[i];
+        extend(bbox, node.leaf ? toBBox(child) : child.bbox);
+    }
+
+    return bbox;
+}
+
+function empty() { return [Infinity, Infinity, -Infinity, -Infinity]; }
+
+function extend(a, b) {
+    a[0] = Math.min(a[0], b[0]);
+    a[1] = Math.min(a[1], b[1]);
+    a[2] = Math.max(a[2], b[2]);
+    a[3] = Math.max(a[3], b[3]);
+    return a;
+}
+
+function compareNodeMinX(a, b) { return a.bbox[0] - b.bbox[0]; }
+function compareNodeMinY(a, b) { return a.bbox[1] - b.bbox[1]; }
+
+function bboxArea(a)   { return (a[2] - a[0]) * (a[3] - a[1]); }
+function bboxMargin(a) { return (a[2] - a[0]) + (a[3] - a[1]); }
+
+function enlargedArea(a, b) {
+    return (Math.max(b[2], a[2]) - Math.min(b[0], a[0])) *
+           (Math.max(b[3], a[3]) - Math.min(b[1], a[1]));
+}
+
+function intersectionArea (a, b) {
+    var minX = Math.max(a[0], b[0]),
+        minY = Math.max(a[1], b[1]),
+        maxX = Math.min(a[2], b[2]),
+        maxY = Math.min(a[3], b[3]);
+
+    return Math.max(0, maxX - minX) *
+           Math.max(0, maxY - minY);
+}
+
+function contains(a, b) {
+    return a[0] <= b[0] &&
+           a[1] <= b[1] &&
+           b[2] <= a[2] &&
+           b[3] <= a[3];
+}
+
+function intersects (a, b) {
+    return b[0] <= a[2] &&
+           b[1] <= a[3] &&
+           b[2] >= a[0] &&
+           b[3] >= a[1];
+}
+
+// sort an array so that items come in groups of n unsorted items, with groups 
sorted between each other;
+// combines selection algorithm with binary divide & conquer approach
+
+function multiSelect(arr, left, right, n, compare) {
+    var stack = [left, right],
+        mid;
+
+    while (stack.length) {
+        right = stack.pop();
+        left = stack.pop();
+
+        if (right - left <= n) continue;
+
+        mid = left + Math.ceil((right - left) / n / 2) * n;
+        select(arr, left, right, mid, compare);
+
+        stack.push(left, mid, mid, right);
+    }
+}
+
+// sort array between left and right (inclusive) so that the smallest k 
elements come first (unordered)
+function select(arr, left, right, k, compare) {
+    var n, i, z, s, sd, newLeft, newRight, t, j;
+
+    while (right > left) {
+        if (right - left > 600) {
+            n = right - left + 1;
+            i = k - left + 1;
+            z = Math.log(n);
+            s = 0.5 * Math.exp(2 * z / 3);
+            sd = 0.5 * Math.sqrt(z * s * (n - s) / n) * (i - n / 2 < 0 ? -1 : 
1);
+            newLeft = Math.max(left, Math.floor(k - i * s / n + sd));
+            newRight = Math.min(right, Math.floor(k + (n - i) * s / n + sd));
+            select(arr, newLeft, newRight, k, compare);
+        }
+
+        t = arr[k];
+        i = left;
+        j = right;
+
+        swap(arr, left, k);
+        if (compare(arr[right], t) > 0) swap(arr, left, right);
+
+        while (i < j) {
+            swap(arr, i, j);
+            i++;
+            j--;
+            while (compare(arr[i], t) < 0) i++;
+            while (compare(arr[j], t) > 0) j--;
+        }
+
+        if (compare(arr[left], t) === 0) swap(arr, left, j);
+        else {
+            j++;
+            swap(arr, j, right);
+        }
+
+        if (j <= k) left = j + 1;
+        if (k <= j) right = j - 1;
+    }
+}
+
+function swap(arr, i, j) {
+    var tmp = arr[i];
+    arr[i] = arr[j];
+    arr[j] = tmp;
+}
+
+
+// export as AMD/CommonJS module or global variable
+if (typeof define === 'function' && define.amd) define(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
new file mode 100644
index 0000000..4739142
--- /dev/null
+++ b/test/test.js
@@ -0,0 +1,329 @@
+var rbush = require('../rbush.js'),
+    t = require('tape');
+
+function sortedEqual(t, a, b, compare) {
+    t.same(a.slice().sort(compare), b.slice().sort(compare));
+}
+
+function someData(n) {
+    var data = [];
+
+    for (var i = 0; i < n; i++) {
+        data.push([i, i, i, i]);
+    }
+    return data;
+}
+
+var data = 
[[0,0,0,0],[10,10,10,10],[20,20,20,20],[25,0,25,0],[35,10,35,10],[45,20,45,20],[0,25,0,25],[10,35,10,35],
+    
[20,45,20,45],[25,25,25,25],[35,35,35,35],[45,45,45,45],[50,0,50,0],[60,10,60,10],[70,20,70,20],[75,0,75,0],
+    
[85,10,85,10],[95,20,95,20],[50,25,50,25],[60,35,60,35],[70,45,70,45],[75,25,75,25],[85,35,85,35],[95,45,95,45],
+    
[0,50,0,50],[10,60,10,60],[20,70,20,70],[25,50,25,50],[35,60,35,60],[45,70,45,70],[0,75,0,75],[10,85,10,85],
+    
[20,95,20,95],[25,75,25,75],[35,85,35,85],[45,95,45,95],[50,50,50,50],[60,60,60,60],[70,70,70,70],[75,50,75,50],
+    
[85,60,85,60],[95,70,95,70],[50,75,50,75],[60,85,60,85],[70,95,70,95],[75,75,75,75],[85,85,85,85],[95,95,95,95]];
+
+var testTree = {"children":[{
+    "children":[
+        
{"children":[[0,0,0,0],[10,10,10,10],[20,20,20,20],[25,0,25,0]],"height":1,"bbox":[0,0,25,20],"leaf":true},
+        
{"children":[[0,25,0,25],[10,35,10,35],[25,25,25,25],[20,45,20,45]],"height":1,"bbox":[0,25,25,45],"leaf":true},
+        
{"children":[[50,0,50,0],[35,10,35,10],[60,10,60,10],[45,20,45,20]],"height":1,"bbox":[35,0,60,20],"leaf":true},
+        
{"children":[[50,25,50,25],[35,35,35,35],[60,35,60,35],[45,45,45,45]],"height":1,"bbox":[35,25,60,45],"leaf":true}
+    ],"height":2,"bbox":[0,0,60,45]
+},{
+    "children":[
+        
{"children":[[0,50,0,50],[25,50,25,50],[10,60,10,60],[20,70,20,70]],"height":1,"bbox":[0,50,25,70],"leaf":true},
+        
{"children":[[0,75,0,75],[25,75,25,75],[10,85,10,85],[20,95,20,95]],"height":1,"bbox":[0,75,25,95],"leaf":true},
+        
{"children":[[35,60,35,60],[50,50,50,50],[60,60,60,60],[45,70,45,70]],"height":1,"bbox":[35,50,60,70],"leaf":true},
+        
{"children":[[50,75,50,75],[60,85,60,85],[45,95,45,95],[35,85,35,85]],"height":1,"bbox":[35,75,60,95],"leaf":true}
+    ],"height":2,"bbox":[0,50,60,95]
+},{
+    "children":[
+        
{"children":[[70,20,70,20],[75,0,75,0],[75,25,75,25],[70,45,70,45]],"height":1,"bbox":[70,0,75,45],"leaf":true},
+        
{"children":[[75,50,75,50],[70,70,70,70],[75,75,75,75],[70,95,70,95]],"height":1,"bbox":[70,50,75,95],"leaf":true},
+        
{"children":[[85,10,85,10],[95,20,95,20],[85,35,85,35],[95,45,95,45]],"height":1,"bbox":[85,10,95,45],"leaf":true},
+        
{"children":[[85,60,85,60],[95,70,95,70],[85,85,85,85],[95,95,95,95]],"height":1,"bbox":[85,60,95,95],"leaf":true}
+    ],"height":2,"bbox":[70,0,95,95]
+}],"height":3,"bbox":[0,0,95,95]};
+
+
+t('constructor accepts a format argument to customize the data format', 
function (t) {
+    var tree = rbush(4, ['.minLng', '.minLat', '.maxLng', '.maxLat']);
+    t.same(tree.toBBox({minLng: 1, minLat: 2, maxLng: 3, maxLat: 4}), [1, 2, 
3, 4]);
+    t.end();
+});
+
+t('constructor uses 9 max entries by default', function (t) {
+    var tree = rbush().load(someData(9));
+    t.equal(tree.toJSON().height, 1);
+
+    var tree2 = rbush().load(someData(10));
+    t.equal(tree2.toJSON().height, 2);
+    t.end();
+});
+
+t('#toBBox, #compareMinX, #compareMinY can be overriden to allow custom data 
structures', function (t) {
+
+    var tree = rbush(4);
+    tree.toBBox = function (item) {
+        return [item.minLng, item.minLat, item.maxLng, item.maxLat];
+    };
+    tree.compareMinX = function (a, b) {
+        return a.minLng - b.minLng;
+    };
+    tree.compareMinY = function (a, b) {
+        return a.minLat - b.minLat;
+    };
+
+    var data = [
+        {minLng: -115, minLat:  45, maxLng: -105, maxLat:  55},
+        {minLng:  105, minLat:  45, maxLng:  115, maxLat:  55},
+        {minLng:  105, minLat: -55, maxLng:  115, maxLat: -45},
+        {minLng: -115, minLat: -55, maxLng: -105, maxLat: -45}
+    ];
+
+    tree.load(data);
+
+    function byLngLat (a, b) {
+        return a.minLng - b.minLng || a.minLat - b.minLat;
+    }
+
+    sortedEqual(t, tree.search([-180, -90, 180, 90]), [
+        {minLng: -115, minLat:  45, maxLng: -105, maxLat:  55},
+        {minLng:  105, minLat:  45, maxLng:  115, maxLat:  55},
+        {minLng:  105, minLat: -55, maxLng:  115, maxLat: -45},
+        {minLng: -115, minLat: -55, maxLng: -105, maxLat: -45}
+    ], byLngLat);
+
+    sortedEqual(t, tree.search([-180, -90, 0, 90]), [
+        {minLng: -115, minLat:  45, maxLng: -105, maxLat:  55},
+        {minLng: -115, minLat: -55, maxLng: -105, maxLat: -45}
+    ], byLngLat);
+
+    sortedEqual(t, tree.search([0, -90, 180, 90]), [
+        {minLng: 105, minLat:  45, maxLng: 115, maxLat:  55},
+        {minLng: 105, minLat: -55, maxLng: 115, maxLat: -45}
+    ], byLngLat);
+
+    sortedEqual(t, tree.search([-180, 0, 180, 90]), [
+        {minLng: -115, minLat: 45, maxLng: -105, maxLat: 55},
+        {minLng:  105, minLat: 45, maxLng:  115, maxLat: 55}
+    ], byLngLat);
+
+    sortedEqual(t, tree.search([-180, -90, 180, 0]), [
+        {minLng:  105, minLat: -55, maxLng:  115, maxLat: -45},
+        {minLng: -115, minLat: -55, maxLng: -105, maxLat: -45}
+    ], byLngLat);
+
+    t.end();
+});
+
+t('#load bulk-loads the given data given max node entries and forms a proper 
search tree', function (t) {
+
+    var tree = rbush(4).load(data);
+    sortedEqual(t, tree.all(), rbush(4).fromJSON(testTree).all());
+
+    t.end();
+});
+
+t('#load uses standard insertion when given a low number of items', function 
(t) {
+
+    var tree = rbush(8)
+        .load(data)
+        .load(data.slice(0, 3));
+
+    var tree2 = rbush(8)
+        .load(data)
+        .insert(data[0])
+        .insert(data[1])
+        .insert(data[2]);
+
+    t.same(tree.toJSON(), tree2.toJSON());
+    t.end();
+});
+
+t('#load does nothing if loading empty data', function (t) {
+    var tree = rbush().load([]);
+
+    t.same(tree.toJSON(), rbush().toJSON());
+    t.end();
+});
+
+t('#load properly splits tree root when merging trees of the same height', 
function (t) {
+    var tree = rbush(4)
+        .load(data)
+        .load(data);
+
+    t.equal(tree.toJSON().height, 4);
+    sortedEqual(t, tree.all(), data.concat(data));
+
+    t.end();
+});
+
+t('#load properly merges data of smaller or bigger tree heights', function (t) 
{
+    var smaller = someData(10);
+
+    var tree1 = rbush(4)
+        .load(data)
+        .load(smaller);
+
+    var tree2 = rbush(4)
+        .load(smaller)
+        .load(data);
+
+    t.equal(tree1.toJSON().height, tree2.toJSON().height);
+
+    sortedEqual(t, tree1.all(), data.concat(smaller));
+    sortedEqual(t, tree2.all(), data.concat(smaller));
+
+    t.end();
+});
+
+t('#search finds matching points in the tree given a bbox', function (t) {
+
+    var tree = rbush(4).load(data);
+    var result = tree.search([40, 20, 80, 70]);
+
+    sortedEqual(t, result, [
+        
[70,20,70,20],[75,25,75,25],[45,45,45,45],[50,50,50,50],[60,60,60,60],[70,70,70,70],
+        
[45,20,45,20],[45,70,45,70],[75,50,75,50],[50,25,50,25],[60,35,60,35],[70,45,70,45]
+    ]);
+
+    t.end();
+});
+
+t('#search returns an empty array if nothing found', function (t) {
+    var result = rbush(4).load(data).search([200, 200, 210, 210]);
+
+    t.same(result, []);
+    t.end();
+});
+
+t('#all returns all points in the tree', function(t) {
+
+    var tree = rbush(4).load(data);
+    var result = tree.all();
+
+    sortedEqual(t, result, data);
+    sortedEqual(t, tree.search([0, 0, 100, 100]), data);
+
+    t.end();
+});
+
+t('#toJSON & #fromJSON exports and imports search tree in JSON format', 
function (t) {
+
+    var tree = rbush(4);
+    tree.fromJSON(testTree);
+
+    var tree2 = rbush(4).load(data);
+
+    sortedEqual(t, tree.all(), tree2.all());
+    t.end();
+});
+
+t('#insert adds an item to an existing tree correctly', function (t) {
+    var tree = rbush(4).load([
+        [0, 0, 0, 0],
+        [1, 1, 1, 1],
+        [2, 2, 2, 2]
+    ]);
+    tree.insert([3, 3, 3, 3]);
+
+    t.same(tree.toJSON(), {
+        'children':[[0,0,0,0],[1,1,1,1],[2,2,2,2],[3,3,3,3]],
+        'leaf':true,
+        'height':1,
+        'bbox':[0,0,3,3]
+    });
+
+    tree.insert([1, 1, 2, 2]);
+
+    t.same(tree.toJSON(), {
+        'children':[
+            
{'children':[[0,0,0,0],[1,1,1,1]],'leaf':true,'height':1,'bbox':[0,0,1,1]},
+            
{'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]
+    });
+    t.end();
+});
+
+t('#insert does nothing if given undefined', function (t) {
+    t.same(
+        rbush().load(data),
+        rbush().load(data).insert());
+    t.end();
+});
+
+t('#insert forms a valid tree if items are inserted one by one', function (t) {
+    var tree = rbush(4);
+
+    for (var i = 0; i < data.length; i++) {
+        tree.insert(data[i]);
+    }
+
+    var tree2 = rbush(4).load(data);
+
+    t.ok(tree.toJSON().height - tree2.toJSON().height <= 1);
+
+    sortedEqual(t, tree.all(), tree2.all());
+    t.end();
+});
+
+t('#remove removes items correctly', function (t) {
+    var tree = rbush(4).load(data);
+
+    var len = data.length;
+
+    tree.remove(data[0]);
+    tree.remove(data[1]);
+    tree.remove(data[2]);
+
+    tree.remove(data[len - 1]);
+    tree.remove(data[len - 2]);
+    tree.remove(data[len - 3]);
+
+    sortedEqual(t,
+        data.slice(3, len - 3),
+        tree.all());
+    t.end();
+});
+t('#remove does nothing if nothing found', function (t) {
+    t.same(
+        rbush().load(data),
+        rbush().load(data).remove([13, 13, 13, 13]));
+    t.end();
+});
+t('#remove does nothing if given undefined', function (t) {
+    t.same(
+        rbush().load(data),
+        rbush().load(data).remove());
+    t.end();
+});
+t('#remove brings the tree to a clear state when removing everything one by 
one', function (t) {
+    var tree = rbush(4).load(data);
+
+    for (var i = 0; i < data.length; i++) {
+        tree.remove(data[i]);
+    }
+
+    t.same(tree.toJSON(), rbush(4).toJSON());
+    t.end();
+});
+
+t('#clear should clear all the data in the tree', function (t) {
+    t.same(
+        rbush(4).load(data).clear().toJSON(),
+        rbush(4).toJSON());
+    t.end();
+});
+
+t('should have chainable API', function (t) {
+    t.doesNotThrow(function () {
+        rbush()
+            .load(data)
+            .insert(data[0])
+            .remove(data[0])
+            .fromJSON(testTree);
+    });
+    t.end();
+});
diff --git a/viz/viz-cluster.html b/viz/viz-cluster.html
new file mode 100644
index 0000000..a6298df
--- /dev/null
+++ b/viz/viz-cluster.html
@@ -0,0 +1,72 @@
+<!doctype html>
+
+<title>RBush Tree Visualization</title>
+<canvas id="canvas" width="701" height="701"></canvas>
+<br>
+<button id="insert1">Insert 50000</button>
+<button id="insert2">Insert 1000</button>
+<button id="insert3">Bulk-insert 50000</button>
+<button id="insert4">Bulk-insert 1000</button>
+<button id="remove">Remove leftmost 10000</button>
+
+<script src="../rbush.js"></script>
+<script src="viz.js"></script>
+<script>
+
+var N = 100000,
+    M = 30,
+    R = 100;
+
+function genData(N, M, R) {
+    var data = [];
+    for (var i = 0; i < M; i++) {
+        var cluster = randClusterPoint(R);
+
+        for (var j = 0; j < N / M; j++) {
+            data.push(randClusterBox(cluster, R, 1));
+        }
+    }
+    return data;
+}
+
+var tree = rbush(16);
+var data = [];
+
+genBulkInsert(N, M)();
+
+function genInsertOneByOne(K, M) {
+    return function () {
+        var data2 = genData(K, M, R);
+
+        console.time('insert ' + K + ' items');
+        for (var i = 0; i < K; i++) {
+            tree.insert(data2[i]);
+        }
+        console.timeEnd('insert ' + K + ' items');
+
+        draw();
+    };
+}
+
+function genBulkInsert(K, M) {
+    return function () {
+        var data2 = genData(K, M, R);
+
+        console.time('bulk-insert ' + K + ' items');
+        tree.load(data2);
+        console.timeEnd('bulk-insert ' + K + ' items');
+
+        data = data.concat(data2);
+
+        draw();
+    };
+}
+
+document.getElementById('insert1').onclick = genInsertOneByOne(50000, M);
+document.getElementById('insert2').onclick = genInsertOneByOne(1000, 1);
+document.getElementById('insert3').onclick = genBulkInsert(50000, M);
+document.getElementById('insert4').onclick = genBulkInsert(1000, 1);
+document.getElementById('canvas').onclick = search;
+document.getElementById('remove').onclick = remove;
+
+</script>
diff --git a/viz/viz-uniform.html b/viz/viz-uniform.html
new file mode 100644
index 0000000..4a5bb3c
--- /dev/null
+++ b/viz/viz-uniform.html
@@ -0,0 +1,68 @@
+<!doctype html>
+
+<title>RBush Tree Visualization</title>
+<canvas id="canvas" width="701" height="701"></canvas>
+<br>
+<button id="insert1">Insert 50000</button>
+<button id="insert2">Insert 1000</button>
+<button id="insert3">Bulk-insert 50000</button>
+<button id="insert4">Bulk-insert 1000</button>
+<button id="remove">Remove leftmost 10000</button>
+
+<script src="../rbush.js"></script>
+<script src="viz.js"></script>
+<script>
+
+var N = 50000;
+
+function genData(N) {
+    var data = [];
+    for (var i = 0; i < N; i++) {
+        data[i] = randBox(1);
+    }
+    return data;
+}
+
+var tree = rbush(10);
+var data = [];
+
+genBulkInsert(N)();
+
+function genInsertOneByOne(K) {
+    return function () {
+        var data2 = genData(K);
+
+        console.time('insert ' + K + ' items');
+        for (var i = 0; i < K; i++) {
+            tree.insert(data2[i]);
+        }
+        console.timeEnd('insert ' + K + ' items');
+
+        data = data.concat(data2);
+
+        draw();
+    };
+}
+
+function genBulkInsert(K) {
+    return function () {
+        var data2 = genData(K);
+
+        console.time('bulk-insert ' + K + ' items');
+        tree.load(data2);
+        console.timeEnd('bulk-insert ' + K + ' items');
+
+        data = data.concat(data2);
+
+        draw();
+    };
+}
+
+document.getElementById('insert1').onclick = genInsertOneByOne(50000);
+document.getElementById('insert2').onclick = genInsertOneByOne(1000);
+document.getElementById('insert3').onclick = genBulkInsert(50000);
+document.getElementById('insert4').onclick = genBulkInsert(1000);
+document.getElementById('canvas').onclick = search;
+document.getElementById('remove').onclick = remove;
+
+</script>
diff --git a/viz/viz.js b/viz/viz.js
new file mode 100644
index 0000000..e6d3714
--- /dev/null
+++ b/viz/viz.js
@@ -0,0 +1,96 @@
+var W = 700,
+    canvas = document.getElementById('canvas'),
+    ctx = canvas.getContext('2d');
+
+function randBox(size) {
+    var x = Math.random() * (W - size),
+        y = Math.random() * (W - size);
+    return [
+        x, y,
+        x + size * Math.random(),
+        y + size * Math.random()
+    ];
+}
+
+function randPoint() {
+    var x = Math.random() * W,
+        y = Math.random() * W;
+    return [x, y];
+}
+
+function randClusterPoint(dist) {
+    var x = dist + Math.random() * (W - dist * 2),
+        y = dist + Math.random() * (W - dist * 2);
+    return [x, y];
+}
+
+function randClusterBox(cluster, dist, size) {
+    var x = cluster[0] - dist + 2 * dist * (Math.random() + Math.random() + 
Math.random()) / 3,
+        y = cluster[1] - dist + 2 * dist * (Math.random() + Math.random() + 
Math.random()) / 3;
+
+    return [
+        x, y,
+        x + size * Math.random(),
+        y + size * Math.random()
+    ];
+}
+
+var colors = ['#f40', '#37f', '#0b0'],
+    rects;
+
+function drawTree(node, level) {
+    if (!node) { return; }
+
+    var rect = [];
+
+    rect.push(level ? colors[(level - 1) % colors.length] : 'grey');
+    rect.push(level ? 1 / level : 1);
+    rect.push([
+        Math.round(node.bbox[0]) + 0.5,
+        Math.round(node.bbox[1]) + 0.5,
+        Math.round(node.bbox[2] - node.bbox[0]),
+        Math.round(node.bbox[3] - node.bbox[1])
+    ]);
+
+    rects.push(rect);
+
+    if (node.leaf) return;
+    if (level === 6) { return; }
+
+    for (var i = 0; i < node.children.length; i++) {
+        drawTree(node.children[i], level + 1);
+    }
+}
+
+function draw() {
+    rects = [];
+    drawTree(tree.data, 0);
+
+    ctx.fillStyle = 'white';
+    ctx.fillRect(0, 0, W + 1, W + 1);
+
+    for (var i = rects.length - 1; i >= 0; i--) {
+        ctx.strokeStyle = rects[i][0];
+        ctx.globalAlpha = rects[i][1];
+        ctx.strokeRect.apply(ctx, rects[i][2]);
+    }
+}
+
+function search(e) {
+    console.time('1 pixel search');
+    tree.search([e.clientX, e.clientY, e.clientX + 1, e.clientY + 1]);
+    console.timeEnd('1 pixel search');
+}
+
+function remove() {
+    data.sort(tree.compareMinX);
+    console.time('remove 10000');
+    for (var i = 0; i < 10000; i++) {
+        tree.remove(data[i]);
+    }
+    console.timeEnd('remove 10000');
+
+    data.splice(0, 10000);
+
+    draw();
+};

-- 
Alioth's /usr/local/bin/git-commit-notice on 
/srv/git.debian.org/git/pkg-grass/node-rbush.git

_______________________________________________
Pkg-grass-devel mailing list
Pkg-grass-devel@lists.alioth.debian.org
http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-grass-devel

Reply via email to