geo-nearby - npm Package Compare versions

Comparing version 1.0.1 to 1.1.0

lib/base.js

@@ -98,2 +98,27 @@ 'use strict';
 
+function binarySearch(set, needle, low, high, max) {
+  var geo = set.geo;
+  var data = set.data;
+
+  while (low <= high) {
+    var mid = low + (high - low >> 1);
+    var value = data[mid][geo];
+    var cmp = value - needle;
+
+    if (cmp < 0) {
+      low  = mid + 1;
+    } else if (cmp > 0) {
+      high = mid - 1;
+    } else {
+      return mid;
+    }
+  }
+
+  if (max) {
+    return (low > 0) ? low - 1 : false;
+  } else {
+    return (low >= 0 && low < data.length) ? low : false;
+  }
+}
+
 function searchBetween(set, min, max) {
@@ -105,12 +130,24 @@ var geo = set.geo;
 
-  for (var i = 0; i < length; i++) {
-    var value = data[i];
-    if (value[geo] >= min && value[geo] <= max) {
-      result.push(value);
+  if (set._sorted) {
+    var _min = binarySearch(set, min, 0, length - 1);
+    var _max = binarySearch(set, max, 0, length - 1, true);
+    if (_min !== false && _max !== false) {
+      for (var i = _min; i <= _max; i++) {
+        result.push(data[i]);
+      }
     }
+
+    return result;
+  } else {
+    for (var i = 0; i < length; i++) {
+      var value = data[i];
+      if (value[geo] >= min && value[geo] <= max) {
+        result.push(value);
+      }
+    }
+
+    return result.sort(function(a, b) {
+      return a[geo] - b[geo];
+    });
   }
-
-  return result.sort(function(a, b) {
-    return a[geo] - b[geo];
-  });
 }
@@ -117,0 +154,0 @@

lib/helpers.js

@@ -33,8 +33,8 @@ 'use strict';
 
-module.exports.isArray = function isArray(array) {
-  return Array.isArray(array);
-};
+var isArray = Array.isArray;
 
+module.exports.isArray = isArray;
+
 module.exports.get = function get(object, path) {
-  if (Array.isArray(path)) {
+  if (isArray(path)) {
     for (var i = 0; i < path.length; i++) {
@@ -55,3 +55,3 @@ object = object[path[i]];
     var value = array[i];
-    if (Array.isArray(value)) {
+    if (isArray(value)) {
       flatten(value, result);
@@ -85,5 +85,5 @@ } else {
 
-  (last + 1 == length) || result.push(rangeIndex[last + 1]);
+  result.push(max);
 
   return result;
 };

main.js

@@ -19,2 +19,3 @@ 'use strict';
   this.geo = options.geo || 'g';
+  this._sorted = options.sorted || false;
   this._limit = this._constLimit = (options.limit && options.limit > 0) ? options.limit : 0;
@@ -43,3 +44,6 @@ return this;
   this._limit = this._constLimit;
-  if (isArray(radius)) {
+
+  if (!lat || !lon || !radius) {
+    return [];
+  } else if (isArray(radius)) {
     var replies = [];
@@ -46,0 +50,0 @@ var range = rangeBetween(radius[0], radius[1]);

package.json

 {
   "name": "geo-nearby",
   "author": "Alexey Bystrov <[e-mail]>",
-  "version": "1.0.1",
-  "description": "Search for nearby locations without DB",
+  "version": "1.1.0",
+  "description": "Uber fast nearby locations search by coordinates. Without DB.",
   "keywords": [
-      "geo nearby",
-      "geolocation",
-      "geo",
-      "nearby",
-      "proximity",
-      "locations",
-      "spatial index",
-      "geohash",
-      "2D spatial index",
-      "spatial",
-      "index",
-      "no db"
+    "geo nearby",
+    "geolocation",
+    "geo",
+    "nearby",
+    "proximity",
+    "locations",
+    "spatial index",
+    "geohash",
+    "2D spatial index",
+    "spatial",
+    "index",
+    "no db"
   ],
   "main": "./main.js",
+  "scripts": {
+    "test": "mocha test"
+  },
   "repository": {
@@ -31,3 +34,7 @@ "type": "git",
   },
+  "devDependencies": {
+    "mocha": "^2.2.5",
+    "should": "^7.0.4"
+  },
   "license": "MIT"
 }

README.md

 geo-nearby
 ==========
+[![Build Status](https://travis-ci.org/strikeentco/geo-nearby.svg)](https://travis-ci.org/strikeentco/geo-nearby) [![License](https://img.shields.io/github/license/strikeentco/geo-nearby.svg?style=flat)](https://github.com/strikeentco/geo-nearby/blob/master/LICENSE)  [![npm](https://img.shields.io/npm/v/geo-nearby.svg?style=flat)](https://www.npmjs.com/package/geo-nearby) [![bitHound Score](https://www.bithound.io/github/strikeentco/geo-nearby/badges/score.svg)](https://www.bithound.io/github/strikeentco/geo-nearby)
 
-
 **Note:** *This module stores all data in memory - remember that.*
 
+Uber fast nearby locations search by coordinates. Without DB.
 
-Search for nearby locations without DB usage.<br>*Inspired by [geo-proximity](https://github.com/arjunmehta/node-geo-proximity).*
+# Usage
 
-
-## Usage
-
-```bash
+```sh
 npm install geo-nearby
@@ -23,9 +21,9 @@ ```
 var dataSet = [
-  { i: 'Perth', g: 3149853951719405 },
-  { i: 'Adelaide', g: 3243323516150966 },
+  { i: 'Perth',     g: 3149853951719405 },
+  { i: 'Adelaide',  g: 3243323516150966 },
   { i: 'Melbourne', g: 3244523307653507 },
-  { i: 'Canberra', g: 3251896081369449 },
-  { i: 'Sydney', g: 3252342838034651 },
-  { i: 'Brisbane', g: 3270013708086451 }
-  { i: 'Sydney', g: 3252342838034651 }
+  { i: 'Canberra',  g: 3251896081369449 },
+  { i: 'Sydney',    g: 3252342838034651 },
+  { i: 'Brisbane',  g: 3270013708086451 },
+  { i: 'Sydney',    g: 3252342838034651 }
 ];
@@ -43,9 +41,9 @@
 var dataSet = [
-  { id: 1, name: 'Perth', geoHash: 3149853951719405 },
-  { id: 2, name: 'Adelaide', geoHash: 3243323516150966 },
+  { id: 1, name: 'Perth',     geoHash: 3149853951719405 },
+  { id: 2, name: 'Adelaide',  geoHash: 3243323516150966 },
   { id: 3, name: 'Melbourne', geoHash: 3244523307653507 },
-  { id: 4, name: 'Canberra', geoHash: 3251896081369449 },
-  { id: 5, name: 'Sydney', geoHash: 3252342838034651 },
-  { id: 6, name: 'Brisbane', geoHash: 3270013708086451 }
-  { id: 7, name: 'Sydney', geoHash: 3252342838034651 }
+  { id: 4, name: 'Canberra',  geoHash: 3251896081369449 },
+  { id: 5, name: 'Sydney',    geoHash: 3252342838034651 },
+  { id: 6, name: 'Brisbane',  geoHash: 3270013708086451 },
+  { id: 7, name: 'Sydney',    geoHash: 3252342838034651 }
 ];
@@ -56,5 +54,5 @@
 
-### Data set
+## Data set
 
-For best performance is recommended to use the default data set syntax:
+For best performance it is recommended to use the default data set syntax:
 
@@ -70,3 +68,3 @@ ```javascript
 
-You can use a `createCompactSet` method for creating a data set with recommended syntax of your data.
+You can use a [`createCompactSet`](#geodatasetcreatecompactsetoptions) method for creating a data set with recommended syntax of your data.
 
@@ -84,6 +82,6 @@ ```javascript
 var dataSet = Geo(data).createCompactSet();
-console.log(Geo(dataSet).nearBy(-33.87, 151.2, 5000));
+console.log(Geo(dataSet, {sorted: true}).nearBy(-33.87, 151.2, 5000));
 ```
 
-You also can change default values for a `createCompactSet` method if your data looks different.
+You also can change default values for a [`createCompactSet`](#geodatasetcreatecompactsetoptions) method if your data looks different.
 
@@ -100,3 +98,3 @@ ```javascript
 var dataSet = Geo(data).createCompactSet({id: '_id', lat: ['coord', 'lat'], lon: ['coord', 'lon']});
-console.log(Geo(dataSet).nearBy(64.54, 40.54, 5000));
+console.log(Geo(dataSet, {sorted: true}).nearBy(64.54, 40.54, 5000));
 ```
@@ -117,8 +115,8 @@
 
-console.log(Geo(dataSet).nearBy(64.54, 40.54, 5000));
+console.log(Geo(dataSet, {sorted: true}).nearBy(64.54, 40.54, 5000));
 ```
 
-## Advanced usage
+# Advanced usage
 
-### Limiting results
+## Limiting results
 
@@ -139,3 +137,3 @@ For limiting results, you have two ways:
 
-**2.** Define limit by `limit()` method. That allows you to define a temporary limit for results.<br>
+**2.** Define limit by `limit()` method. That allows you to define a temporary limit for results.
 
@@ -155,3 +153,3 @@ ```javascript
 
-### A range of distances
+## A range of distances
 
@@ -167,35 +165,52 @@ For a more precise definition, you can use a range of distances.
 
+## Binary search
 
-## Methods
-* `Geo(dataSet, options)` - Constructor.
-  * `dataSet` - *(array)* - data.
-  * `options` - *(object)* - options:
-    + `geo` - *(string)* - key path **(by default = 'g')**.
-    + `limit` - *(integer)* - limit results **(by default = 0, i.e., no limits)**.
+If you created data set by [`createCompactSet`](#geodatasetcreatecompactsetoptions) method or your own data set is sorted by `geohash` property in ascending order, you can activate extremely fast binary search.
 
+Just set `sorted` property as `true` in [Geo](#geodataset-optionsnearbylat-lon-distance) `options`.
+
+A binary search is 20 times faster than normal.
+
 ```javascript
-Geo(dataSet, {geo: 'geo', limit: 1});
+console.log(Geo(dataSet, {sorted: true}).limit(1).nearBy(64.54, 40.54, [250, 30000]));
 ```
-* `Geo(dataSet).createCompactSet(options)` - Method creates data set.
-  * `dataSet` - *(array)* - data.
-  * `options` - *(object)* - options:
-    + `id` - *(string|array)* - key (name|path) **(by default = 2)**.
-    + `lat` - *(string|array)* - key (name|path) **(by default = 0)**.
-    + `lon` - *(string|array)* - key (name|path) **(by default = 1)**.
-    + `sort` - *(string)* - sort by geohash **(by default = 'asc')**.
-    + `file` - *(string)* - file path **(by default = false)**.
 
+# Methods
+
+## Geo(dataSet, [options]).nearBy(lat, lon, distance)
+
+Method found nearby locations.
+
+### Params:
+
+* **dataSet** (*Array*) - Data set.
+* **lat** (*Float*) - Latitude.
+* **lon** (*Float*) - Longitude.
+* **distance** (*Integer|Array*) - Distance in meters.
+* **[options]** (*Object*) - Options:
+  * **geo** (*String*) - Key path (by default = 'g').
+  * **limit** (*Integer*) - Limit results (by default no limits).
+  * **sorted** (*Boolean*) - If data set is sorted in ascending order, set `sorted` as `true` it will enable [binary search](#binary-search) (uber fast mode).
+
 ```javascript
-var dataSet = Geo(data).createCompactSet({id: ['names', 'name', 'id'], sort: 'desc'});
-
-Geo(data).createCompactSet({id: 2, lat: 0, lon: 1, file: './compact.set.json'});
+Geo(dataSet, {geo: 'geo', limit: 1, sorted: true}).nearBy(64.54, 40.54, [500, 300000]);
 ```
-* `Geo(dataSet).limit(0).nearBy(lat, lon, distance)` - Method found nearby locations.
-  + `lat` - *(float)* - latitude.
-  + `lon` - *(float)* - longitude.
-  + `distance` - *(integer|array)* - distance in meters.
-  + `limit()` - *(integer)* - limit results **(by default = 0, i.e., no limits)**.
 
+## Geo(dataSet).createCompactSet([options])
+
+Method creates data set.
+
+### Params:
+
+* **dataSet** (*Array*) - Data set.
+* **[options]** (*Object*) - Options:
+  * **id** (*String|Array*) - Key (name|path) (by default = 2).
+  * **lat** (*String|Array*) - Key (name|path) (by default = 0).
+  * **lon** (*String|Array*) - Key (name|path) (by default = 1).
+  * **file** (*String*) - File path to save.
+
 ```javascript
-Geo(dataSet).limit(1).nearBy(64.54, 40.54, [500, 300000]);
+var dataSet = Geo(data).createCompactSet({id: ['names', 'name', 'id']});
+
+Geo(data).createCompactSet({id: 2, lat: 0, lon: 1, file: './compact.set.json'});
 ```
@@ -202,0 +217,0 @@

No alert changes

Improved metrics

Total package byte prevSize

22207

increased by46.06%

Number of package files

10

increased by25%

Lines of code

412

increased by66.8%

Number of lines in readme file

212

increased by7.61%

Worsened metrics

Dev dependency count

2

increased byInfinity%

No dependency changes