kdbush - npm Package Compare versions

Comparing version 2.0.1 to 3.0.0

kdbush.js

 (function (global, factory) {
 typeof exports === 'object' && typeof module !== 'undefined' ? module.exports = factory() :
 typeof define === 'function' && define.amd ? define(factory) :
-(global.kdbush = factory());
+(global.KDBush = factory());
 }(this, (function () { 'use strict';
 
 function sortKD(ids, coords, nodeSize, left, right, depth) {
-    if (right - left <= nodeSize) return;
+    if (right - left <= nodeSize) { return; }
 
-    var m = Math.floor((left + right) / 2);
+    var m = (left + right) >> 1;
 
@@ -37,3 +37,3 @@ select(ids, coords, m, left, right, depth % 2);
         swapItem(ids, coords, left, k);
-        if (coords[2 * right + inc] > t) swapItem(ids, coords, left, right);
+        if (coords[2 * right + inc] > t) { swapItem(ids, coords, left, right); }
 
@@ -44,7 +44,7 @@ while (i < j) {
             j--;
-            while (coords[2 * i + inc] < t) i++;
-            while (coords[2 * j + inc] > t) j--;
+            while (coords[2 * i + inc] < t) { i++; }
+            while (coords[2 * j + inc] > t) { j--; }
         }
 
-        if (coords[2 * left + inc] === t) swapItem(ids, coords, left, j);
+        if (coords[2 * left + inc] === t) { swapItem(ids, coords, left, j); }
         else {
@@ -55,4 +55,4 @@ j++;
 
-        if (j <= k) left = j + 1;
-        if (k <= j) right = j - 1;
+        if (j <= k) { left = j + 1; }
+        if (k <= j) { right = j - 1; }
     }
@@ -87,3 +87,3 @@ }
                 y = coords[2 * i + 1];
-                if (x >= minX && x <= maxX && y >= minY && y <= maxY) result.push(ids[i]);
+                if (x >= minX && x <= maxX && y >= minY && y <= maxY) { result.push(ids[i]); }
             }
@@ -98,3 +98,3 @@ continue;
 
-        if (x >= minX && x <= maxX && y >= minY && y <= maxY) result.push(ids[m]);
+        if (x >= minX && x <= maxX && y >= minY && y <= maxY) { result.push(ids[m]); }
 
@@ -130,3 +130,3 @@ var nextAxis = (axis + 1) % 2;
             for (var i = left; i <= right; i++) {
-                if (sqDist(coords[2 * i], coords[2 * i + 1], qx, qy) <= r2) result.push(ids[i]);
+                if (sqDist(coords[2 * i], coords[2 * i + 1], qx, qy) <= r2) { result.push(ids[i]); }
             }
@@ -141,3 +141,3 @@ continue;
 
-        if (sqDist(x, y, qx, qy) <= r2) result.push(ids[m]);
+        if (sqDist(x, y, qx, qy) <= r2) { result.push(ids[m]); }
 
@@ -167,41 +167,38 @@ var nextAxis = (axis + 1) % 2;
 
-function kdbush(points, getX, getY, nodeSize, ArrayType) {
-    return new KDBush(points, getX, getY, nodeSize, ArrayType);
-}
+var defaultGetX = function (p) { return p[0]; };
+var defaultGetY = function (p) { return p[1]; };
 
-function KDBush(points, getX, getY, nodeSize, ArrayType) {
-    getX = getX || defaultGetX;
-    getY = getY || defaultGetY;
-    ArrayType = ArrayType || Array;
+var KDBush = function KDBush(points, getX, getY, nodeSize, ArrayType) {
+    if ( getX === void 0 ) getX = defaultGetX;
+    if ( getY === void 0 ) getY = defaultGetY;
+    if ( nodeSize === void 0 ) nodeSize = 64;
+    if ( ArrayType === void 0 ) ArrayType = Float64Array;
 
-    this.nodeSize = nodeSize || 64;
+    this.nodeSize = nodeSize;
     this.points = points;
 
-    this.ids = new ArrayType(points.length);
-    this.coords = new ArrayType(points.length * 2);
+    var IndexArrayType = points.length < 65536 ? Uint16Array : Uint32Array;
 
+    var ids = this.ids = new IndexArrayType(points.length);
+    var coords = this.coords = new ArrayType(points.length * 2);
+
     for (var i = 0; i < points.length; i++) {
-        this.ids[i] = i;
-        this.coords[2 * i] = getX(points[i]);
-        this.coords[2 * i + 1] = getY(points[i]);
+        ids[i] = i;
+        coords[2 * i] = getX(points[i]);
+        coords[2 * i + 1] = getY(points[i]);
     }
 
-    sortKD(this.ids, this.coords, this.nodeSize, 0, this.ids.length - 1, 0);
-}
+    sortKD(ids, coords, nodeSize, 0, ids.length - 1, 0);
+};
 
-KDBush.prototype = {
-    range: function (minX, minY, maxX, maxY) {
-        return range(this.ids, this.coords, minX, minY, maxX, maxY, this.nodeSize);
-    },
+KDBush.prototype.range = function range$1 (minX, minY, maxX, maxY) {
+    return range(this.ids, this.coords, minX, minY, maxX, maxY, this.nodeSize);
+};
 
-    within: function (x, y, r) {
-        return within(this.ids, this.coords, x, y, r, this.nodeSize);
-    }
+KDBush.prototype.within = function within$1 (x, y, r) {
+    return within(this.ids, this.coords, x, y, r, this.nodeSize);
 };
 
-function defaultGetX(p) { return p[0]; }
-function defaultGetY(p) { return p[1]; }
+return KDBush;
 
-return kdbush;
-
 })));

kdbush.min.js

@@ -1,1 +0,1 @@
-!function(t,o){"object"==typeof exports&&"undefined"!=typeof module?module.exports=o():"function"==typeof define&&define.amd?define(o):t.kdbush=o()}(this,function(){"use strict";function e(t,o,n,r,i,s){if(!(i-r<=n)){var h=Math.floor((r+i)/2);!function t(o,n,r,i,s,h){for(;i<s;){if(600<s-i){var e=s-i+1,u=r-i+1,f=Math.log(e),p=.5*Math.exp(2*f/3),a=.5*Math.sqrt(f*p*(e-p)/e)*(u-e/2<0?-1:1),d=Math.max(i,Math.floor(r-u*p/e+a)),c=Math.min(s,Math.floor(r+(e-u)*p/e+a));t(o,n,r,d,c,h)}var l=n[2*r+h],v=i,g=s;for(M(o,n,i,r),n[2*s+h]>l&&M(o,n,i,s);v<g;){for(M(o,n,v,g),v++,g--;n[2*v+h]<l;)v++;for(;n[2*g+h]>l;)g--}n[2*i+h]===l?M(o,n,i,g):M(o,n,++g,s),g<=r&&(i=g+1),r<=g&&(s=g-1)}}(t,o,h,r,i,s%2),e(t,o,n,r,h-1,s+1),e(t,o,n,h+1,i,s+1)}}function M(t,o,n,r){i(t,n,r),i(o,2*n,2*r),i(o,2*n+1,2*r+1)}function i(t,o,n){var r=t[o];t[o]=t[n],t[n]=r}function m(t,o,n,r){var i=t-n,s=o-r;return i*i+s*s}function s(t,o,n,r,i){o=o||h,n=n||u,i=i||Array,this.nodeSize=r||64,this.points=t,this.ids=new i(t.length),this.coords=new i(2*t.length);for(var s=0;s<t.length;s++)this.ids[s]=s,this.coords[2*s]=o(t[s]),this.coords[2*s+1]=n(t[s]);e(this.ids,this.coords,this.nodeSize,0,this.ids.length-1,0)}function h(t){return t[0]}function u(t){return t[1]}return s.prototype={range:function(t,o,n,r){return function(t,o,n,r,i,s,h){for(var e,u,f=[0,t.length-1,0],p=[];f.length;){var a=f.pop(),d=f.pop(),c=f.pop();if(d-c<=h)for(var l=c;l<=d;l++)e=o[2*l],u=o[2*l+1],n<=e&&e<=i&&r<=u&&u<=s&&p.push(t[l]);else{var v=Math.floor((c+d)/2);e=o[2*v],u=o[2*v+1],n<=e&&e<=i&&r<=u&&u<=s&&p.push(t[v]);var g=(a+1)%2;(0===a?n<=e:r<=u)&&(f.push(c),f.push(v-1),f.push(g)),(0===a?e<=i:u<=s)&&(f.push(v+1),f.push(d),f.push(g))}}return p}(this.ids,this.coords,t,o,n,r,this.nodeSize)},within:function(t,o,n){return function(t,o,n,r,i,s){for(var h=[0,t.length-1,0],e=[],u=i*i;h.length;){var f=h.pop(),p=h.pop(),a=h.pop();if(p-a<=s)for(var d=a;d<=p;d++)m(o[2*d],o[2*d+1],n,r)<=u&&e.push(t[d]);else{var c=Math.floor((a+p)/2),l=o[2*c],v=o[2*c+1];m(l,v,n,r)<=u&&e.push(t[c]);var g=(f+1)%2;(0===f?n-i<=l:r-i<=v)&&(h.push(a),h.push(c-1),h.push(g)),(0===f?l<=n+i:v<=r+i)&&(h.push(c+1),h.push(p),h.push(g))}}return e}(this.ids,this.coords,t,o,n,this.nodeSize)}},function(t,o,n,r,i){return new s(t,o,n,r,i)}});
+!function(t,o){"object"==typeof exports&&"undefined"!=typeof module?module.exports=o():"function"==typeof define&&define.amd?define(o):t.KDBush=o()}(this,function(){"use strict";function t(n,r,i,e,h,u){if(!(h-e<=i)){var s=e+h>>1;!function t(n,r,i,e,h,u){for(;h>e;){if(h-e>600){var s=h-e+1,f=i-e+1,p=Math.log(s),a=.5*Math.exp(2*p/3),d=.5*Math.sqrt(p*a*(s-a)/s)*(f-s/2<0?-1:1),v=Math.max(e,Math.floor(i-f*a/s+d)),c=Math.min(h,Math.floor(i+(s-f)*a/s+d));t(n,r,i,v,c,u)}var l=r[2*i+u],g=e,M=h;for(o(n,r,e,i),r[2*h+u]>l&&o(n,r,e,h);g<M;){for(o(n,r,g,M),g++,M--;r[2*g+u]<l;)g++;for(;r[2*M+u]>l;)M--}r[2*e+u]===l?o(n,r,e,M):o(n,r,++M,h),M<=i&&(e=M+1),i<=M&&(h=M-1)}}(n,r,s,e,h,u%2),t(n,r,i,e,s-1,u+1),t(n,r,i,s+1,h,u+1)}}function o(t,o,r,i){n(t,r,i),n(o,2*r,2*i),n(o,2*r+1,2*i+1)}function n(t,o,n){var r=t[o];t[o]=t[n],t[n]=r}function r(t,o,n,r){var i=t-n,e=o-r;return i*i+e*e}var i=function(t){return t[0]},e=function(t){return t[1]},h=function(o,n,r,h,u){void 0===n&&(n=i),void 0===r&&(r=e),void 0===h&&(h=64),void 0===u&&(u=Float64Array),this.nodeSize=h,this.points=o;for(var s=o.length<65536?Uint16Array:Uint32Array,f=this.ids=new s(o.length),p=this.coords=new u(2*o.length),a=0;a<o.length;a++)f[a]=a,p[2*a]=n(o[a]),p[2*a+1]=r(o[a]);t(f,p,h,0,f.length-1,0)};return h.prototype.range=function(t,o,n,r){return function(t,o,n,r,i,e,h){for(var u,s,f=[0,t.length-1,0],p=[];f.length;){var a=f.pop(),d=f.pop(),v=f.pop();if(d-v<=h)for(var c=v;c<=d;c++)u=o[2*c],s=o[2*c+1],u>=n&&u<=i&&s>=r&&s<=e&&p.push(t[c]);else{var l=Math.floor((v+d)/2);u=o[2*l],s=o[2*l+1],u>=n&&u<=i&&s>=r&&s<=e&&p.push(t[l]);var g=(a+1)%2;(0===a?n<=u:r<=s)&&(f.push(v),f.push(l-1),f.push(g)),(0===a?i>=u:e>=s)&&(f.push(l+1),f.push(d),f.push(g))}}return p}(this.ids,this.coords,t,o,n,r,this.nodeSize)},h.prototype.within=function(t,o,n){return function(t,o,n,i,e,h){for(var u=[0,t.length-1,0],s=[],f=e*e;u.length;){var p=u.pop(),a=u.pop(),d=u.pop();if(a-d<=h)for(var v=d;v<=a;v++)r(o[2*v],o[2*v+1],n,i)<=f&&s.push(t[v]);else{var c=Math.floor((d+a)/2),l=o[2*c],g=o[2*c+1];r(l,g,n,i)<=f&&s.push(t[c]);var M=(p+1)%2;(0===p?n-e<=l:i-e<=g)&&(u.push(d),u.push(c-1),u.push(M)),(0===p?n+e>=l:i+e>=g)&&(u.push(c+1),u.push(a),u.push(M))}}return s}(this.ids,this.coords,t,o,n,this.nodeSize)},h});

package.json

 {
   "name": "kdbush",
-  "version": "2.0.1",
+  "version": "3.0.0",
   "description": "A very fast static 2D index for points based on kd-tree.",
   "module": "src/index.js",
   "main": "kdbush.js",
-  "jsdelivr": "dist/kdbush.min.js",
-  "unpkg": "dist/kdbush.min.js",
+  "jsdelivr": "kdbush.min.js",
+  "unpkg": "kdbush.min.js",
   "repository": {
@@ -14,20 +14,19 @@ "type": "git",
   "devDependencies": {
-    "eslint": "^4.19.1",
-    "eslint-config-mourner": "^2.0.1",
-    "esm": "^3.0.48",
-    "rollup": "^0.60.0",
-    "rollup-plugin-uglify": "^4.0.0",
-    "tape": "^4.6.2"
+    "eslint": "^5.5.0",
+    "eslint-config-mourner": "^3.0.0",
+    "esm": "^3.0.82",
+    "rollup": "^0.65.2",
+    "rollup-plugin-buble": "^0.19.2",
+    "rollup-plugin-terser": "^2.0.2",
+    "tape": "^4.9.1"
   },
   "scripts": {
-    "pretest": "eslint test.js src",
+    "pretest": "eslint src test.js bench.js rollup.config.js",
     "test": "tape -r esm test.js",
     "bench": "node -r esm bench.js",
-    "build": "rollup -c"
+    "build": "rollup -c",
+    "prepublishOnly": "npm run build"
   },
   "eslintConfig": {
-    "extends": "mourner",
-    "parserOptions": {
-      "sourceType": "module"
-    }
+    "extends": "mourner"
   },
@@ -34,0 +33,0 @@ "keywords": [

README.md

@@ -1,2 +0,2 @@
-## kdbush [![Build Status](https://travis-ci.org/mourner/kdbush.svg?branch=master)](https://travis-ci.org/mourner/kdbush) [![Simply Awesome](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects)
+## KDBush [![Build Status](https://travis-ci.org/mourner/kdbush.svg?branch=master)](https://travis-ci.org/mourner/kdbush) [![Simply Awesome](https://img.shields.io/badge/simply-awesome-brightgreen.svg)](https://github.com/mourner/projects)
 
@@ -11,5 +11,5 @@ A very fast static spatial index for 2D points based on a flat KD-tree.
 ```js
-var index = kdbush(points);              // make an index
-var ids1 = index.range(10, 10, 20, 20);  // bbox search - minX, minY, maxX, maxY
-var ids2 = index.within(10, 10, 5);      // radius search - x, y, radius
+const index = new KDBush(points);         // make an index
+const ids1 = index.range(10, 10, 20, 20); // bbox search - minX, minY, maxX, maxY
+const ids2 = index.within(10, 10, 5);     // radius search - x, y, radius
 ```
@@ -23,6 +23,6 @@
 // import as a ES module
-import kdbush from 'kdbush';
+import KDBush from 'kdbush';
 
 // or require in Node / Browserify
-const kdbush = require('kdbush');
+const KDBush = require('kdbush');
 ```
@@ -38,3 +38,3 @@
 
-#### kdbush(points[, getX, getY, nodeSize, arrayType])
+#### new KDBush(points[, getX, getY, nodeSize, arrayType])
 
@@ -46,9 +46,9 @@ Creates an index from the given points.
 - `nodeSize`: Size of the KD-tree node, `64` by default. Higher means faster indexing but slower search, and vise versa.
-- `arrayType`: Array type to use for storing indices and coordinate values. `Array` by default, but if your coordinates are integer values, `Int32Array` makes things a bit faster.
+- `arrayType`: Array type to use for storing coordinate values. `Float64Array` by default, but if your coordinates are integer values, `Int32Array` makes things a bit faster.
 
 ```js
-var index = kdbush(points, (p) => p.x, (p) => p.y, 64, Int32Array);
+const index = kdbush(points, p => p.x, p => p.y, 64, Int32Array);
 ```
 
-#### range(minX, minY, maxX, maxY)
+#### index.range(minX, minY, maxX, maxY)
 
@@ -58,6 +58,6 @@ Finds all items within the given bounding box and returns an array of indices that refer to the items in the original `points` input array.
 ```js
-var results = index.range(10, 10, 20, 20).map((id) => points[id]);
+const results = index.range(10, 10, 20, 20).map(id => points[id]);
 ```
 
-#### within(x, y, radius)
+#### index.within(x, y, radius)
 
@@ -67,3 +67,3 @@ Finds all items within a given radius from the query point and returns an array of indices.
 ```js
-var results = index.within(10, 10, 5).map((id) => points[id]);
+const results = index.within(10, 10, 5).map(id => points[id]);
 ```

src/index.js

@@ -6,37 +6,31 @@
 
-export default function kdbush(points, getX, getY, nodeSize, ArrayType) {
-    return new KDBush(points, getX, getY, nodeSize, ArrayType);
-}
+const defaultGetX = p => p[0];
+const defaultGetY = p => p[1];
 
-function KDBush(points, getX, getY, nodeSize, ArrayType) {
-    getX = getX || defaultGetX;
-    getY = getY || defaultGetY;
-    ArrayType = ArrayType || Array;
+export default class KDBush {
+    constructor(points, getX = defaultGetX, getY = defaultGetY, nodeSize = 64, ArrayType = Float64Array) {
+        this.nodeSize = nodeSize;
+        this.points = points;
 
-    this.nodeSize = nodeSize || 64;
-    this.points = points;
+        const IndexArrayType = points.length < 65536 ? Uint16Array : Uint32Array;
 
-    this.ids = new ArrayType(points.length);
-    this.coords = new ArrayType(points.length * 2);
+        const ids = this.ids = new IndexArrayType(points.length);
+        const coords = this.coords = new ArrayType(points.length * 2);
 
-    for (var i = 0; i < points.length; i++) {
-        this.ids[i] = i;
-        this.coords[2 * i] = getX(points[i]);
-        this.coords[2 * i + 1] = getY(points[i]);
+        for (let i = 0; i < points.length; i++) {
+            ids[i] = i;
+            coords[2 * i] = getX(points[i]);
+            coords[2 * i + 1] = getY(points[i]);
+        }
+
+        sort(ids, coords, nodeSize, 0, ids.length - 1, 0);
     }
 
-    sort(this.ids, this.coords, this.nodeSize, 0, this.ids.length - 1, 0);
-}
-
-KDBush.prototype = {
-    range: function (minX, minY, maxX, maxY) {
+    range(minX, minY, maxX, maxY) {
         return range(this.ids, this.coords, minX, minY, maxX, maxY, this.nodeSize);
-    },
+    }
 
-    within: function (x, y, r) {
+    within(x, y, r) {
         return within(this.ids, this.coords, x, y, r, this.nodeSize);
     }
-};
-
-function defaultGetX(p) { return p[0]; }
-function defaultGetY(p) { return p[1]; }
+}

src/range.js

 
 export default function range(ids, coords, minX, minY, maxX, maxY, nodeSize) {
-    var stack = [0, ids.length - 1, 0];
-    var result = [];
-    var x, y;
+    const stack = [0, ids.length - 1, 0];
+    const result = [];
+    let x, y;
 
     while (stack.length) {
-        var axis = stack.pop();
-        var right = stack.pop();
-        var left = stack.pop();
+        const axis = stack.pop();
+        const right = stack.pop();
+        const left = stack.pop();
 
         if (right - left <= nodeSize) {
-            for (var i = left; i <= right; i++) {
+            for (let i = left; i <= right; i++) {
                 x = coords[2 * i];
@@ -21,3 +21,3 @@ y = coords[2 * i + 1];
 
-        var m = Math.floor((left + right) / 2);
+        const m = Math.floor((left + right) / 2);
 
@@ -29,3 +29,3 @@ x = coords[2 * m];
 
-        var nextAxis = (axis + 1) % 2;
+        const nextAxis = (axis + 1) % 2;
 
@@ -32,0 +32,0 @@ if (axis === 0 ? minX <= x : minY <= y) {

src/sort.js

@@ -5,3 +5,3 @@
 
-    var m = Math.floor((left + right) / 2);
+    const m = (left + right) >> 1;
 
@@ -18,15 +18,15 @@ select(ids, coords, m, left, right, depth % 2);
         if (right - left > 600) {
-            var n = right - left + 1;
-            var m = k - left + 1;
-            var z = Math.log(n);
-            var s = 0.5 * Math.exp(2 * z / 3);
-            var sd = 0.5 * Math.sqrt(z * s * (n - s) / n) * (m - n / 2 < 0 ? -1 : 1);
-            var newLeft = Math.max(left, Math.floor(k - m * s / n + sd));
-            var newRight = Math.min(right, Math.floor(k + (n - m) * s / n + sd));
+            const n = right - left + 1;
+            const m = k - left + 1;
+            const z = Math.log(n);
+            const s = 0.5 * Math.exp(2 * z / 3);
+            const sd = 0.5 * Math.sqrt(z * s * (n - s) / n) * (m - n / 2 < 0 ? -1 : 1);
+            const newLeft = Math.max(left, Math.floor(k - m * s / n + sd));
+            const newRight = Math.min(right, Math.floor(k + (n - m) * s / n + sd));
             select(ids, coords, k, newLeft, newRight, inc);
         }
 
-        var t = coords[2 * k + inc];
-        var i = left;
-        var j = right;
+        const t = coords[2 * k + inc];
+        let i = left;
+        let j = right;
 
@@ -62,5 +62,5 @@ swapItem(ids, coords, left, k);
 function swap(arr, i, j) {
-    var tmp = arr[i];
+    const tmp = arr[i];
     arr[i] = arr[j];
     arr[j] = tmp;
 }

src/within.js

 
 export default function within(ids, coords, qx, qy, r, nodeSize) {
-    var stack = [0, ids.length - 1, 0];
-    var result = [];
-    var r2 = r * r;
+    const stack = [0, ids.length - 1, 0];
+    const result = [];
+    const r2 = r * r;
 
     while (stack.length) {
-        var axis = stack.pop();
-        var right = stack.pop();
-        var left = stack.pop();
+        const axis = stack.pop();
+        const right = stack.pop();
+        const left = stack.pop();
 
         if (right - left <= nodeSize) {
-            for (var i = left; i <= right; i++) {
+            for (let i = left; i <= right; i++) {
                 if (sqDist(coords[2 * i], coords[2 * i + 1], qx, qy) <= r2) result.push(ids[i]);
@@ -19,10 +19,10 @@ }
 
-        var m = Math.floor((left + right) / 2);
+        const m = Math.floor((left + right) / 2);
 
-        var x = coords[2 * m];
-        var y = coords[2 * m + 1];
+        const x = coords[2 * m];
+        const y = coords[2 * m + 1];
 
         if (sqDist(x, y, qx, qy) <= r2) result.push(ids[m]);
 
-        var nextAxis = (axis + 1) % 2;
+        const nextAxis = (axis + 1) % 2;
 
@@ -45,5 +45,5 @@ if (axis === 0 ? qx - r <= x : qy - r <= y) {
 function sqDist(ax, ay, bx, by) {
-    var dx = ax - bx;
-    var dy = ay - by;
+    const dx = ax - bx;
+    const dy = ay - by;
     return dx * dx + dy * dy;
 }

No alert changes

Improved metrics

Total package byte prevSize

16951

increased by0.5%

Worsened metrics

Dev dependency count

7

increased by16.67%

Lines of code

309

decreased by-2.52%

No dependency changes