Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

geo-tree

Package Overview
Dependencies
Maintainers
1
Versions
18
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

geo-tree - npm Package Compare versions

Comparing version 0.1.4 to 1.0.0

.eslintrc.json

52

package.json
{
"name": "geo-tree",
"version": "0.1.4",
"description": "High performance library for map-related operations",
"export-symbol": "GeoTree",
"dependencies": {},
"devDependencies": {
"gulp": "^3.8.9",
"gulp-jshint": "^1.8.5",
"gulp-istanbul": "^0.3.1",
"gulp-mocha": "^1.1.1",
"gulp-browserify": "^0.5.0",
"gulp-rename": "^1.2.0",
"gulp-uglify": "^1.0.1",
"gulp-sym": "0.0.14"
"version": "1.0.0",
"description": "High performance library for geographical map-related operations",
"license": "MIT",
"author": "Roman Kaspar <roman@salsitasoft.com>",
"repository": {
"type": "git",
"url": "git@github.com:salsita/geo-tree.git"
},
"bugs": {
"url": "https://github.com/salsita/geo-tree/issues"
},
"engines": {
"node": ">= 0.8.0"
"node": ">= 6.0.0"
},
"main": "src/geo-tree.js",
"scripts": {
"test": "gulp test"
"test": "eslint src test && jest test/*.spec.js --coverage"
},
"repository": {
"type": "git",
"url": "git@github.com:salsita/geo-tree.git"
},
"keywords": [
"javascript",
"geo tree",
"geographical",
"map",
"tree",
"geo-tree",
"red-black tree",

@@ -35,7 +30,12 @@ "Z-order curve",

],
"author": "Roman Kaspar <roman@salsitasoft.com> (https://salsitasoft.com/)",
"license": "MIT",
"bugs": {
"url": "https://github.com/salsita/geo-tree/issues"
}
"devDependencies": {
"eslint": "^4.10.0",
"eslint-config-standard": "^10.2.1",
"eslint-plugin-import": "^2.8.0",
"eslint-plugin-node": "^5.2.1",
"eslint-plugin-promise": "^3.6.0",
"eslint-plugin-standard": "^3.0.1",
"jest": "^21.2.1"
},
"dependencies": {}
}

225

README.md

@@ -1,3 +0,9 @@

# Geo-tree library
[![Dependency Status](https://img.shields.io/david/salsita/geo-tree.svg)](https://david-dm.org/salsita/geo-tree)
[![devDependency Status](https://img.shields.io/david/dev/salsita/geo-tree.svg)](https://david-dm.org/salsita/geo-tree?type=dev)
![Downloads](https://img.shields.io/npm/dm/geo-tree.svg?style=flat)
![Licence](https://img.shields.io/npm/l/geo-tree.svg?style=flat)
[![Known Vulnerabilities](https://snyk.io/test/github/salsita/geo-tree/badge.svg)](https://snyk.io/test/github/salsita/geo-tree)
# geo-tree library
Geo-tree library is a tool for working with map objects. The primary use-case is

@@ -27,61 +33,39 @@ creating a set of map-related objects (i.e. each of them having its latitude,

In `node.js` environment, just do the usual:
```
$ npm i geo-tree
```
npm install geo-node --save
... and in your code:
Since that moment on, you can use it as:
```
const GeoTree = require('geo-tree');
const gt = new GeoTree();
```
var GeoTree = require('geo-tree');
var gt = new GeoTree();
// use it as you like
## Working from source code
If you want to use it in the browser directly, add a `<script>` tag with the
built library into your html:
```
$ git clone git@github.com:salsita/geo-tree.git
$ cd geo-tree
$ npm i
$ npm test
```
<script src="geo-tree.min.js" type="text/javascript"></script>
Eslint is used for linting the source code, and jest as the test runner. The test coverage report
is stored in `coverage` directory after testing.
And then you can use `window.GeoTree` constructor function that is exported by
the library the same way as in `node.js`:
There are also two additional test files in `test` directory:
* `benchmark.js`: run it before you make changes to the source code, and then after, to see
the performance impact of your change,
* `test.js`: playground for your new feature(s).
<script>
var gt = new GeoTree();
// use it as you like
</script>
To run them, just do
```
$ node test/benchmark
```
and
```
$ node test/test
```
If you need the `GeoTree` constructor function to be exported under different
name, see the build procedure below...
## Build procedure
If you want to build the library (that can be used as `<script>` tag in your
HTML code) from the `node.js` sources, make sure you have `grunt` client
installed along with `nmp` utility. Then issue:
$ npm install
$ grunt
This will build you the library and its minified version into `lib` directory.
The symbol, under which the main `GeoTree` constructor function is exported, is
defined in `package.json` file under `export-symbol` key. By default, it has
`GeoTree` value, so the constructor is available as `window.GeoTree` name. If
you need the constructor to be available under different name, just edit the
`export-symbol` key in `package.json` and build the library again.
## Tests
The code is unit tested using `mocha` testing framework together with unit test
coverage tool `istanbul`. All `.spec.js` files are in `test` directory.
There are also two more files in `test` directory:
* `benchmark.js`: there are some performance related tests, I use them to make
sure code updates don't have any negative impacts on performance, and
* `test.js`: where I test ideas, API, ...
These tests are executed in `node`.
The unit test coverage reports are generated into `test/coverage` directory, so
when editing / adding new features to the library yourself, make sure tests still
pass, or that you actually add unit tests for new functionality as needed.
## API

@@ -91,17 +75,13 @@

The `GeoTree` constructor function is the only exported object for both `node`
and standalone browser library versions.
The `GeoTree` constructor function is the only exported library symbols.
You require it as:
```
const GeoTree = require('geo-tree');
```
So in `node`, you get access to it as:
var GeoTree = require('geo-tree');
and in browser you use the `<script>` tag:
<script src="geo-tree.min.js" type="text/javascript"></script>
To create new empty set (tree), do:
```
const set = new GeoTree();
```
var set = new GeoTree();
### Insert

@@ -119,36 +99,41 @@

Assume we want to insert:
```
lat: 48.85886, lng: 2.34706, data: 'Paris, France'
lat: 52.50754, lng: 13.42614, data: 'Berlin, Germany'
lat: 50.05967, lng: 14.46562, data: 'Prague, Czech Republic'
```
lat: 48.85886, lng: 2.34706, data: 'Paris, France'
lat: 52.50754, lng: 13.42614, data: 'Berlin, Germany'
lat: 50.05967, lng: 14.46562, data: 'Prague, Czech Republic'
Function `insert()` can be invoked with single parameter: object
```
{
lat: ...,
lng: ...,
data: ...
}
```
{
lat: ...,
lng: ...,
data: ...
}
So you would invoke it 3 times to insert the above 3 items, inserting one each
time, e.g. to insert Paris, you'd do:
```
set.insert({lat: 48.85886, lng: 2.34706, data: 'Paris, France'});
```
set.insert({lat: 48.85886, lng: 2.34706, data: 'Paris, France'});
For bulk insert, you can pass an array of the above mentioned objects, they will
be inserted sequentially. So to insert all 3 of them in one `insert()`
invocation, you'd do:
```
set.insert([
{lat: 48.85886, lng: 2.34706, data: 'Paris, France'},
{lat: 52.50754, lng: 13.42614, data: 'Berlin, Germany'},
{lat: 50.05967, lng: 14.46562, data: 'Prague, Czech Republic'}
]);
```
set.insert([
{lat: 48.85886, lng: 2.34706, data: 'Paris, France'},
{lat: 52.50754, lng: 13.42614, data: 'Berlin, Germany'},
{lat: 50.05967, lng: 14.46562, data: 'Prague, Czech Republic'}
]);
Last option is to pass `lat`, `lng` and `data` as 3 arguments to `insert()`,
which will insert one item with associated coordinates and data. E.g. to insert
Prague, you'd do:
```
set.insert(50.05967, 14.46562, 'Prague, Czech Republic');
```
set.insert(50.05967, 14.46562, 'Prague, Czech Republic');
There is no need to have unique `lat`, `lng` pairs when inserting the items.

@@ -168,4 +153,6 @@

set.find();
// --> ['Prague, Czech Republic', 'Paris, France', 'Berlin, Germany']
```
set.find();
// --> ['Prague, Czech Republic', 'Paris, France', 'Berlin, Germany']
```

@@ -175,4 +162,6 @@ Specifying single object argument `{lat: ..., lng: ...}`, the function returns

set.find({lat: 48.85886, lng: 2.34706});
// --> ['Paris, France']
```
set.find({lat: 48.85886, lng: 2.34706});
// --> ['Paris, France']
```

@@ -183,4 +172,6 @@ You can pass two `lat`/`lng` objects to `find()`, in which case it will return

set.find({lat: 45, lng: 0}, {lat: 55, lng: 14});
// --> ['Paris, France', 'Berlin, Germany']
```
set.find({lat: 45, lng: 0}, {lat: 55, lng: 14});
// --> ['Paris, France', 'Berlin, Germany']
```

@@ -196,7 +187,9 @@ Finally, you can pass one `lat`/`lng` object, a float number, and optionally a

set.find({lat: 51, lng: 14}, 2.0);
// --> ['Prague, Czech Republic', 'Berlin, Germany']
```
set.find({lat: 51, lng: 14}, 2.0);
// --> ['Prague, Czech Republic', 'Berlin, Germany']
set.find({lat: 51, lng: 17}, 200.0, 'mi');
// --> ['Prague, Czech Republic', 'Berlin, Germany']
set.find({lat: 51, lng: 17}, 200.0, 'mi');
// --> ['Prague, Czech Republic', 'Berlin, Germany']
```

@@ -209,8 +202,10 @@ ### Iteration over all items

set.forEach(function(data) { console.log(data); });
/* prints to console:
Paris, France
Prague, Czech Republic
Berlin, Germany
*/
```
set.forEach(function(data) { console.log(data); });
/* prints to console:
Paris, France
Prague, Czech Republic
Berlin, Germany
*/
```

@@ -228,11 +223,5 @@ Same as for the `find()` method: the order passed `data` items to the callback

## Development
Soon(-ish), we plan to add suport for:
* `remove` operation (i.e. removing geo objects from the sets)
* cluster calculation
## Change-log
* 1.0.0 (2017-11-03): Major rework of infrastructure (gulp no more, jest, eslint, ...)
* 0.1.4 (2014-10-27): Gulp build system replaced Grunt

@@ -243,1 +232,23 @@ * 0.1.3 (2014-10-21): Repo migrated from my private account to salsita account

* 0.1.0 (2014-09-04): initial version (`insert`, `find` and `forEach` operations)
## MIT License
Copyright (c) 2014-2017 Salsita Software
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.

59

src/geo-tree.js

@@ -19,3 +19,2 @@ // geo-tree implementation (using red-black tree and z-curve)

function getValidationFn(center, dist, units) {
function toDeg(rad) { return rad * 180.0 / Math.PI; }

@@ -44,5 +43,5 @@ function toRad(deg) { return deg * Math.PI / 180.0; }

validate: function(coord) {
var dlat = center.lat - coord.lat;
var dlng = center.lng - coord.lng;
return (dlat * dlat + dlng * dlng <= radius2);
var dLat = center.lat - coord.lat;
var dLng = center.lng - coord.lng;
return (dLat * dLat + dLng * dLng <= radius2);
}

@@ -58,10 +57,10 @@ };

// Haversine algo (http://mathforum.org/library/drmath/view/51879.html)
var dlat = toRad(center.lat - coord.lat);
var dlng = toRad(center.lng - coord.lng);
var sin_dlat_2 = Math.sin(dlat/2);
var sin_dlng_2 = Math.sin(dlng/2);
var cos_ce_lat = Math.cos(toRad(center.lat));
var cos_co_lat = Math.cos(toRad(coord.lat));
var a = sin_dlat_2 * sin_dlat_2 + cos_ce_lat * cos_co_lat * sin_dlng_2 * sin_dlng_2;
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
var dLat = toRad(center.lat - coord.lat);
var dLng = toRad(center.lng - coord.lng);
var sinDLat2 = Math.sin(dLat / 2);
var sinDLng2 = Math.sin(dLng / 2);
var cosCeLat = Math.cos(toRad(center.lat));
var cosCoLat = Math.cos(toRad(coord.lat));
var a = sinDLat2 * sinDLat2 + cosCeLat * cosCoLat * sinDLng2 * sinDLng2;
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
return (R * c <= adjustedDist);

@@ -84,8 +83,8 @@ }

var lat, lng, data;
if ('number' === typeof(arg1)) {
if (typeof arg1 === 'number') {
lat = arg1;
lng = arg2;
data = arg3;
} else if ('object' === typeof(arg1)) {
if ('number' === typeof(arg1.length)) {
} else if (typeof arg1 === 'object') {
if (typeof arg1.length === 'number') {
for (var i = 0; i < arg1.length; i++) { this.insert(arg1[i]); }

@@ -104,3 +103,3 @@ return;

var idx = curve.xy2d(iLat, iLng);
this.tree.insert(idx, { idx: idx, lat: lat, lng: lng, data: data} );
this.tree.insert(idx, { idx: idx, lat: lat, lng: lng, data: data });
};

@@ -116,5 +115,5 @@

var all, radius, validate;
all = (0 === arguments.length);
all = (arguments.length === 0);
if (undefined === arg2) { arg2 = arg1; }
if ('number' === typeof(arg2)) {
if (typeof arg2 === 'number') {
var _tmp = getValidationFn(arg1, arg2, arg3);

@@ -124,3 +123,8 @@ radius = _tmp.angle;

}
var minLat, maxLat, minLng, maxLng, minIdx = -Infinity, maxIdx = Infinity;
var minLat;
var maxLat;
var minLng;
var maxLng;
var minIdx = -Infinity;
var maxIdx = Infinity;
if (!all) {

@@ -140,11 +144,14 @@ if (undefined === radius) {

}
minIdx = curve.xy2d(Math.round((minLat + 90.0) * 100000),
Math.round((minLng + 180.0) * 100000));
maxIdx = curve.xy2d(Math.round((maxLat + 90.0) * 100000),
Math.round((maxLng + 180.0) * 100000));
minIdx = curve.xy2d(Math.round((minLat + 90.0) * 100000), Math.round((minLng + 180.0) * 100000));
maxIdx = curve.xy2d(Math.round((maxLat + 90.0) * 100000), Math.round((maxLng + 180.0) * 100000));
}
var candidates = this.tree.find(minIdx, maxIdx);
var i, item, lat, lng, res = [];
if (all) { for (i = 0; i < candidates.length; i++) { res.push(candidates[i].data); } }
else {
var i;
var item;
var lat;
var lng;
var res = [];
if (all) {
for (i = 0; i < candidates.length; i++) { res.push(candidates[i].data); }
} else {
if (undefined === radius) {

@@ -151,0 +158,0 @@ // rectangle

57

src/red-black.js

@@ -13,5 +13,5 @@ // red-black tree implementation

var RED = 0;
var BLACK = 1;
var RED = 0, BLACK = 1;
// --- NODE ---

@@ -59,5 +59,6 @@

RBTree.prototype.insert = function(arg1, arg2) {
if ('number' === typeof(arg1)) { this._insert(arg1, arg2); }
else if ('object' === typeof(arg1)) {
if ('number' === typeof(arg1.length)) {
if (typeof arg1 === 'number') {
this._insert(arg1, arg2);
} else if (typeof arg1 === 'object') {
if (typeof arg1.length === 'number') {
var ref;

@@ -85,7 +86,5 @@ for (var i = 0; i < arg1.length; i++) {

if (key < p.key) {
if (p.left) { p = p.left; }
else { n = p.left = new RBNode(p, key, value); break; }
if (p.left) { p = p.left; } else { n = p.left = new RBNode(p, key, value); break; }
} else {
if (p.right) { p = p.right; }
else { n = p.right = new RBNode(p, key, value); break; }
if (p.right) { p = p.right; } else { n = p.right = new RBNode(p, key, value); break; }
}

@@ -108,3 +107,4 @@ }

g.left = n; n.parent = g;
if (p.right = n.left) { n.left.parent = p; }
p.right = n.left
if (p.right) { n.left.parent = p; }
n.left = p; p.parent = n;

@@ -114,3 +114,4 @@ n = p; p = n.parent;

g.right = n; n.parent = g;
if (p.left = n.right) { n.right.parent = p; }
p.left = n.right;
if (p.left) { n.right.parent = p; }
n.right = p; p.parent = n;

@@ -122,11 +123,14 @@ n = p; p = n.parent;

if (n === p.left) {
if (g.left = p.right) { p.right.parent = g; }
g.left = p.right;
if (g.left) { p.right.parent = g; }
p.right = g;
} else {
if (g.right = p.left) { p.left.parent = g; }
g.right = p.left;
if (g.right) { p.left.parent = g; }
p.left = g;
}
pg = g.parent;
if (pg) { if (g === pg.left) { pg.left = p; } else { pg.right = p; } }
else { this.root = p; p.color = BLACK; }
if (pg) {
if (g === pg.left) { pg.left = p; } else { pg.right = p; }
} else { this.root = p; p.color = BLACK; }
p.parent = pg; g.parent = p;

@@ -137,3 +141,2 @@ break;

// supported args:

@@ -146,3 +149,4 @@ // key -- single numeric value, exact match

var res = [];
var node, stack = [this.root];
var node;
var stack = [this.root];
while (stack.length) {

@@ -155,3 +159,6 @@ node = stack.pop();

// flatten res:
var flatRes = [], i, j, _ref;
var flatRes = [];
var i;
var j;
var _ref;
for (i = 0; i < res.length; i++) {

@@ -169,3 +176,4 @@ _ref = res[i];

dfs(node.left);
var ref = node.values, key = node.key;
var ref = node.values;
var key = node.key;
for (var i = 0; i < ref.length; i++) { callback(ref[i], key); }

@@ -185,3 +193,2 @@ dfs(node.right);

// RBTree.prototype.remove = function(arg1, arg2) {
// TODO
// };

@@ -198,5 +205,7 @@

if (!node) { return; }
/* istanbul ignore else */
if (silent) { res += node.dump(); }
else { console.log(((undefined !== indent) ? indent + '+ ' : '') + node.dump()); }
if (silent) {
res += node.dump();
} else {
console.log(((undefined !== indent) ? indent + '+ ' : '') + node.dump());
}
var s = (undefined === indent) ? '' : (indent + ' ');

@@ -206,6 +215,4 @@ dumpNode(node.left, s);

}
/* istanbul ignore if */
if (!silent) { console.log('--- dump start ---'); }
dumpNode(this.root);
/* istanbul ignore if */
if (!silent) { console.log('--- dump end ---'); }

@@ -212,0 +219,0 @@ return res;

4

src/z-curve.js

@@ -8,3 +8,5 @@ // z-curve implementation mapping 2D coordinates into 1D (single index) scalar

xy2d: function(x, y) {
var bit = 1, max = Math.max(x,y), res = 0.0;
var bit = 1;
var max = Math.max(x, y);
var res = 0.0;
while (bit <= max) { bit <<= 1; }

@@ -11,0 +13,0 @@ bit >>= 1;

107

test/benchmark.js

@@ -7,3 +7,2 @@ // Usage: node benchmark

var RBTree = require('../src/red-black');

@@ -13,19 +12,22 @@ var N = 1 << 20;

function benchmark(name, data, sort) {
var i, ts_start, ts_end, tree = new RBTree();
var i;
var tsStart;
var tsEnd;
var tree = new RBTree();
console.log('\ndistribution "' + name + '":');
// insert
ts_start = new Date();
tsStart = new Date();
tree.insert(data, sort);
ts_end = new Date();
console.log('insert (1M) ... ' + (ts_end - ts_start) + 'ms');
tsEnd = new Date();
console.log('insert (1M) ... ' + (tsEnd - tsStart) + 'ms');
// find one
ts_start = new Date();
for (i = 0; i < N/4; i++) { tree.find(i * 4); }
ts_end = new Date();
console.log('find-one (250k) ... ' + (ts_end - ts_start) + 'ms');
tsStart = new Date();
for (i = 0; i < N / 4; i++) { tree.find(i * 4); }
tsEnd = new Date();
console.log('find-one (250k) ... ' + (tsEnd - tsStart) + 'ms');
// find range
ts_start = new Date();
for (i = 0; i < N/1024; i++) { tree.find(i * 1024, i * 1024 + 10240); }
ts_end = new Date();
console.log('find-range (1k x 10k) ... ' + (ts_end - ts_start) + 'ms');
tsStart = new Date();
for (i = 0; i < N / 1024; i++) { tree.find(i * 1024, i * 1024 + 10240); }
tsEnd = new Date();
console.log('find-range (1k x 10k) ... ' + (tsEnd - tsStart) + 'ms');
//

@@ -38,3 +40,3 @@ tree = null;

arr = [];
for (i = 0; i < N; i++) { arr.push({key:i}); }
for (i = 0; i < N; i++) { arr.push({ key: i }); }
benchmark('linear', arr);

@@ -47,7 +49,9 @@

arr = [];
for (i = 0; i < N-1; i++) { arr.push(i); }
var _arr = [], step = N, idx;
for (i = 0; i < N - 1; i++) { arr.push(i); }
var _arr = [];
var step = N;
var idx;
while (step > 1) {
idx = step/2 - 1;
while (idx < N-1) { _arr.push({key: arr[idx]}); idx += step; }
idx = step / 2 - 1;
while (idx < N - 1) { _arr.push({ key: arr[idx] }); idx += step; }
step /= 2;

@@ -61,31 +65,36 @@ }

var tree = new GeoTree();
var ts_start, ts_end;
var tsStart, tsEnd;
console.log('START');
ts_start = new Date();
var lat, lng, data = [];
tsStart = new Date();
var lat;
var lng;
var data = [];
for (i = 0; i < N; i++) {
lat = Math.random() * 180.0 - 90.0;
lng = Math.random() * 360.0 - 180.0;
data.push({lat: lat, lng: lng, data: {lat:lat, lng:lng}});
data.push({ lat: lat, lng: lng, data: { lat: lat, lng: lng } });
}
ts_end = new Date();
console.log('random data generated: ' + (ts_end - ts_start) + 'ms');
tsEnd = new Date();
console.log('random data generated: ' + (tsEnd - tsStart) + 'ms');
ts_start = new Date();
tsStart = new Date();
tree.insert(data);
ts_end = new Date();
console.log('data (1M) inserted into geo tree: ' + (ts_end - ts_start) + 'ms');
tsEnd = new Date();
console.log('data (1M) inserted into geo tree: ' + (tsEnd - tsStart) + 'ms');
var j, d;
var j;
var d;
for (d = 0; d < 4; d++) {
for (j = 0; j < 3; j++) {
for (i = 0; i < 3; i++) {
ts_start = new Date();
tree.find({ lat: 10.0 + (160.0/2) * i - 90.0, lng: 20.0 + (320.0/2) * j -180.0 }, 1.0+d*3.0);
ts_end = new Date();
console.log('find({ lat: ' + (10.0 + (160.0/2) * i - 90.0) + ', lng: ' +
(20.0 + (320.0/2) * j - 180.0) + ' }, r = ' +
(1.0+d*3.0) + '): ' + (ts_end - ts_start) + 'ms');
} } }
for (j = 0; j < 3; j++) {
for (i = 0; i < 3; i++) {
tsStart = new Date();
tree.find({ lat: 10.0 + (160.0 / 2) * i - 90.0, lng: 20.0 + (320.0 / 2) * j - 180.0 }, 1.0 + d * 3.0);
tsEnd = new Date();
console.log('find({ lat: ' + (10.0 + (160.0 / 2) * i - 90.0) +
', lng: ' + (20.0 + (320.0 / 2) * j - 180.0) +
' }, r = ' + (1.0 + d * 3.0) + '): ' + (tsEnd - tsStart) + 'ms');
}
}
}

@@ -95,20 +104,20 @@ console.log('\n------------------------------------------------------------\n');

var res;
ts_start = new Date();
tsStart = new Date();
res = tree.find({lat: 0.0, lng: 0.0}, 5.0);
ts_end = new Date();
console.log('find({ lat: 0.0, lng: 0.0 }, 5.0): ' + (ts_end - ts_start) + 'ms, res.length: ' + res.length);
ts_start = new Date();
tsEnd = new Date();
console.log('find({ lat: 0.0, lng: 0.0 }, 5.0): ' + (tsEnd - tsStart) + 'ms, res.length: ' + res.length);
tsStart = new Date();
res = tree.find({lat: 0.0, lng: 0.0}, 556.6, 'km');
ts_end = new Date();
console.log('find({ lat: 0.0, lng: 0.0 }, 556.6, "km"): ' + (ts_end - ts_start) + 'ms, res.length: ' + res.length);
tsEnd = new Date();
console.log('find({ lat: 0.0, lng: 0.0 }, 556.6, "km"): ' + (tsEnd - tsStart) + 'ms, res.length: ' + res.length);
console.log('\n');
ts_start = new Date();
tsStart = new Date();
res = tree.find({lat: 50.0, lng: 0.0}, 5.0);
ts_end = new Date();
console.log('find({ lat: 50.0, lng: 0.0 }, 5.0): ' + (ts_end - ts_start) + 'ms, res.length: ' + res.length);
ts_start = new Date();
tsEnd = new Date();
console.log('find({ lat: 50.0, lng: 0.0 }, 5.0): ' + (tsEnd - tsStart) + 'ms, res.length: ' + res.length);
tsStart = new Date();
res = tree.find({lat: 50.0, lng: 0.0}, 556.6, 'km');
ts_end = new Date();
console.log('find({ lat: 50.0, lng: 0.0 }, 556.6, "km"): ' + (ts_end - ts_start) + 'ms, res.length: ' + res.length);
tsEnd = new Date();
console.log('find({ lat: 50.0, lng: 0.0 }, 556.6, "km"): ' + (tsEnd - tsStart) + 'ms, res.length: ' + res.length);

45

test/geo-tree.spec.js

@@ -8,22 +8,26 @@ var assert = require('assert');

function createTestSet() {
/* eslint-disable key-spacing */
gt.insert([
{lat: -10.0, lng: -10.0, data: 'data1'},
{lat: 0.0, lng: -10.0, data: 'data2'},
{lat: 10.0, lng: -10.0, data: 'data3'},
{lat: -10.0, lng: 0.0, data: 'data4'},
{lat: 0.0, lng: 0.0, data: 'data5'},
{lat: 10.0, lng: 0.0, data: 'data6'},
{lat: -10.0, lng: 10.0, data: 'data7'},
{lat: 0.0, lng: 10.0, data: 'data8'},
{lat: 10.0, lng: 10.0, data: 'data9'}
{ lat: -10.0, lng: -10.0, data: 'data1' },
{ lat: 0.0, lng: -10.0, data: 'data2' },
{ lat: 10.0, lng: -10.0, data: 'data3' },
{ lat: -10.0, lng: 0.0, data: 'data4' },
{ lat: 0.0, lng: 0.0, data: 'data5' },
{ lat: 10.0, lng: 0.0, data: 'data6' },
{ lat: -10.0, lng: 10.0, data: 'data7' },
{ lat: 0.0, lng: 10.0, data: 'data8' },
{ lat: 10.0, lng: 10.0, data: 'data9' }
]);
/* eslint-enable key-spacing */
}
function createDistTestSet() {
/* eslint-disable key-spacing */
gt.insert([
{lat: 50.0755, lng: 14.4378, data: 'Praha'}, // dist: Brno: 184.538km, Ostrava: 275.401km, Plzen: 85.023km
{lat: 49.1951, lng: 16.6068, data: 'Brno'}, // dist: Ostrava: 138.475km, Plzen: 241.577km
{lat: 49.8209, lng: 18.2625, data: 'Ostrava'},// dist: Plzen: 351.482km
{lat: 49.7384, lng: 13.3736, data: 'Plzen'} //
{ lat: 50.0755, lng: 14.4378, data: 'Praha' }, // dist: Brno: 184.538km, Ostrava: 275.401km, Plzen: 85.023km
{ lat: 49.1951, lng: 16.6068, data: 'Brno' }, // dist: Ostrava: 138.475km, Plzen: 241.577km
{ lat: 49.8209, lng: 18.2625, data: 'Ostrava' }, // dist: Plzen: 351.482km
{ lat: 49.7384, lng: 13.3736, data: 'Plzen' } //
]);
/* eslint-enable key-spacing */
}

@@ -37,5 +41,3 @@

describe('geo-tree module', function() {
beforeEach(function() { gt = new GeoTree(); log = []; });

@@ -64,3 +66,3 @@

it('insert (single object)', function() {
gt.insert({lat:-90.0, lng:-180.0, data:'hello'});
gt.insert({lat: -90.0, lng: -180.0, data: 'hello'});
assert.equal(gt.dump(true),

@@ -73,4 +75,4 @@ '[k:0,c:B,#:1,l:NULL,r:NULL,p:NULL,v:[{"idx":0,"lat":-90,"lng":-180,"data":"hello"}]]'

gt.insert([
{lat:-90.0, lng:-180.0, data:'hello'},
{lat:-90.0, lng:-180.0, data:'world'}
{lat: -90.0, lng: -180.0, data: 'hello'},
{lat: -90.0, lng: -180.0, data: 'world'}
]);

@@ -90,4 +92,3 @@ assert.equal(gt.dump(true),

var res = gt.find().sort();
var expect = ['data1', 'data2', 'data3', 'data4', 'data5',
'data6', 'data7', 'data8', 'data9'];
var expect = ['data1', 'data2', 'data3', 'data4', 'data5', 'data6', 'data7', 'data8', 'data9'];
assert.equal(res.length, expect.length);

@@ -196,4 +197,3 @@ expect.forEach(function(val, idx) { assert.equal(res[idx], val); });

gt.forEach(addLog);
var expect = ['data1', 'data2', 'data3', 'data4', 'data5',
'data6', 'data7', 'data8', 'data9'];
var expect = ['data1', 'data2', 'data3', 'data4', 'data5', 'data6', 'data7', 'data8', 'data9'];
log = log.sort();

@@ -203,3 +203,2 @@ assert.equal(log.length, expect.length);

});
});

20

test/red-black.spec.js

@@ -9,3 +9,3 @@ var assert = require('assert');

[99, 50, 80, 65, 70, 40, 41, 42, 48, 47, 45, 43, 55, 57, 58, 59, 60, 61, 62]
.forEach(function(i) { rbt.insert({key: i, value: i}); });
.forEach(function(i) { rbt.insert({ key: i, value: i }); });
}

@@ -19,5 +19,3 @@

describe('red-black module', function() {
beforeEach(function() { rbt = new RBTree(); log = []; });

@@ -40,3 +38,3 @@

// single {key: ..., value: ...} object
rbt.insert({key:10, value:10});
rbt.insert({ key: 10, value: 10 });
assert.equal(rbt.dump(true), '[k:10,c:B,#:1,l:NULL,r:NULL,p:NULL,v:[10]]');

@@ -47,8 +45,4 @@ });

// [ { key: ..., value: ... }, ... ] -- array of the above objects
rbt.insert([{key:20, value:20}, {key:10, value:10}, {key:30, value:30}]);
assert.equal(rbt.dump(true),
'[k:20,c:B,#:1,l:10,r:30,p:NULL,v:[20]]' +
'[k:10,c:R,#:1,l:NULL,r:NULL,p:20,v:[10]]' +
'[k:30,c:R,#:1,l:NULL,r:NULL,p:20,v:[30]]'
);
rbt.insert([{ key: 20, value: 20 }, { key: 10, value: 10 }, { key: 30, value: 30 }]);
assert.equal(rbt.dump(true), '[k:20,c:B,#:1,l:10,r:30,p:NULL,v:[20]][k:10,c:R,#:1,l:NULL,r:NULL,p:20,v:[10]][k:30,c:R,#:1,l:NULL,r:NULL,p:20,v:[30]]');
});

@@ -76,4 +70,4 @@

it('insert (traversal code)', function() {
rbt.insert([{key:10,value:10},{key:15,value:15},{key:5,value:5},
{key:1,value:1},{key:6,value:6},{key:20,value:20}]);
rbt.insert([{ key: 10, value: 10 }, { key: 15, value: 15 }, { key: 5, value: 5 },
{ key: 1, value: 1 }, { key: 6, value: 6 }, { key: 20, value: 20 }]);
assert.equal(rbt.dump(true),

@@ -137,3 +131,2 @@ '[k:10,c:B,#:1,l:5,r:15,p:NULL,v:[10]]' +

it('find (range search: not found)', function() {

@@ -177,3 +170,2 @@ createTestTree();

});
});

16

test/test.js

@@ -8,7 +8,7 @@ // Usage: node test

var data = [
{lat: 50.0791306, lng:14.4293712, data: 'Prague'},
{lat: 48.85837, lng: 2.294481, data: 'Paris'},
{lat: 51.500728, lng: -0.124626, data: 'London'},
{lat: -33.9593169, lng: 18.6741289, data: 'Cape Town'},
{lat: 52.5075419, lng: 13.4261419, data: 'Berlin'}
{ lat: 50.0791306, lng: 14.4293712, data: 'Prague' },
{ lat: 48.85837, lng: 2.294481, data: 'Paris' },
{ lat: 51.500728, lng: -0.124626, data: 'London' },
{ lat: -33.9593169, lng: 18.6741289, data: 'Cape Town' },
{ lat: 52.5075419, lng: 13.4261419, data: 'Berlin' }
];

@@ -21,5 +21,5 @@

console.log('\nfind all:\n', tree.find());
console.log('\nfind exact:\n', tree.find({lat:-33.9593169, lng: 18.6741289}));
console.log('\nfind radius:\n', tree.find({lat: 49, lng: 14}, 2));
console.log('\nfind rectangle:\n', tree.find({lat: 45, lng: 12}, {lat: 55, lng: 15}));
console.log('\nfind exact:\n', tree.find({ lat: -33.9593169, lng: 18.6741289 }));
console.log('\nfind radius:\n', tree.find({ lat: 49, lng: 14 }, 2));
console.log('\nfind rectangle:\n', tree.find({ lat: 45, lng: 12 }, { lat: 55, lng: 15 }));

@@ -26,0 +26,0 @@ console.log('\nforEach test:');

8

test/z-curve.spec.js

@@ -6,7 +6,7 @@ var assert = require('assert');

it('should verify xy2d()', function() {
assert.equal(curve.xy2d(0,0), 0);
assert.equal(curve.xy2d(0,1), 1);
assert.equal(curve.xy2d(1,0), 2);
assert.equal(curve.xy2d(1023,1023), 1048575);
assert.equal(curve.xy2d(0, 0), 0);
assert.equal(curve.xy2d(0, 1), 1);
assert.equal(curve.xy2d(1, 0), 2);
assert.equal(curve.xy2d(1023, 1023), 1048575);
});
});
.jshintrc
.npmignore
gulpfile.js
lib/geo-tree-0.1.4.js
lib/geo-tree-0.1.4.min.js
LICENSE

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