!function(t,r){"object"==typeof exports&&"undefined"!=typeof module?module.exports=r():"function"==typeof define&&define.amd?define(r):(t="undefined"!=typeof globalThis?globalThis:t||self).KDBush=r()}(this,(function(){"use strict";const t=[Int8Array,Uint8Array,Uint8ClampedArray,Int16Array,Uint16Array,Int32Array,Uint32Array,Float32Array,Float64Array];class r{static from(n){if(!(n instanceof ArrayBuffer))throw new Error("Data must be an instance of ArrayBuffer.");const[s,e]=new Uint8Array(n,0,2);if(219!==s)throw new Error("Data does not appear to be in a KDBush format.");const i=e>>4;if(1!==i)throw new Error(`Got v${i} data when expected v1.`);const o=t[15&e];if(!o)throw new Error("Unrecognized array type.");const[h]=new Uint16Array(n,2,1),[a]=new Uint32Array(n,4,1);return new r(a,h,o,n)}constructor(r,n=64,s=Float64Array,e){if(isNaN(r)||r<0)throw new Error(`Unpexpected numItems value: ${r}.`);this.numItems=+r,this.nodeSize=Math.min(Math.max(+n,2),65535),this.ArrayType=s,this.IndexArrayType=r<65536?Uint16Array:Uint32Array;const i=t.indexOf(this.ArrayType),o=2*r*this.ArrayType.BYTES_PER_ELEMENT,h=r*this.IndexArrayType.BYTES_PER_ELEMENT,a=(8-h%8)%8;if(i<0)throw new Error(`Unexpected typed array class: ${s}.`);e&&e instanceof ArrayBuffer?(this.data=e,this.ids=new this.IndexArrayType(this.data,8,r),this.coords=new this.ArrayType(this.data,8+h+a,2*r),this._pos=2*r,this._finished=!0):(this.data=new ArrayBuffer(8+o+h+a),this.ids=new this.IndexArrayType(this.data,8,r),this.coords=new this.ArrayType(this.data,8+h+a,2*r),this._pos=0,this._finished=!1,new Uint8Array(this.data,0,2).set([219,16+i]),new Uint16Array(this.data,2,1)[0]=n,new Uint32Array(this.data,4,1)[0]=r)}add(t,r){const n=this._pos>>1;return this.ids[n]=n,this.coords[this._pos++]=t,this.coords[this._pos++]=r,n}finish(){const t=this._pos>>1;if(t!==this.numItems)throw new Error(`Added ${t} items when expected ${this.numItems}.`);return n(this.ids,this.coords,this.nodeSize,0,this.numItems-1,0),this._finished=!0,this}range(t,r,n,s){if(!this._finished)throw new Error("Data not yet indexed - call index.finish().");const{ids:e,coords:i,nodeSize:o}=this,h=[0,e.length-1,0],a=[];for(;h.length;){const d=h.pop()||0,f=h.pop()||0,p=h.pop()||0;if(f-p<=o){for(let o=p;o<=f;o++){const h=i[2*o],d=i[2*o+1];h>=t&&h<=n&&d>=r&&d<=s&&a.push(e[o])}continue}const c=p+f>>1,u=i[2*c],y=i[2*c+1];u>=t&&u<=n&&y>=r&&y<=s&&a.push(e[c]),(0===d?t<=u:r<=y)&&(h.push(p),h.push(c-1),h.push(1-d)),(0===d?n>=u:s>=y)&&(h.push(c+1),h.push(f),h.push(1-d))}return a}within(t,r,n){if(!this._finished)throw new Error("Data not yet indexed - call index.finish().");const{ids:s,coords:e,nodeSize:i}=this,h=[0,s.length-1,0],a=[],d=n*n;for(;h.length;){const f=h.pop()||0,p=h.pop()||0,c=h.pop()||0;if(p-c<=i){for(let n=c;n<=p;n++)o(e[2*n],e[2*n+1],t,r)<=d&&a.push(s[n]);continue}const u=c+p>>1,y=e[2*u],w=e[2*u+1];o(y,w,t,r)<=d&&a.push(s[u]),(0===f?t-n<=y:r-n<=w)&&(h.push(c),h.push(u-1),h.push(1-f)),(0===f?t+n>=y:r+n>=w)&&(h.push(u+1),h.push(p),h.push(1-f))}return a}}function n(t,r,e,i,o,h){if(o-i<=e)return;const a=i+o>>1;s(t,r,a,i,o,h),n(t,r,e,i,a-1,1-h),n(t,r,e,a+1,o,1-h)}function s(t,r,n,i,o,h){for(;o>i;){if(o-i>600){const e=o-i+1,a=n-i+1,d=Math.log(e),f=.5*Math.exp(2*d/3),p=.5*Math.sqrt(d*f*(e-f)/e)*(a-e/2<0?-1:1);s(t,r,n,Math.max(i,Math.floor(n-a*f/e+p)),Math.min(o,Math.floor(n+(e-a)*f/e+p)),h)}const a=r[2*n+h];let d=i,f=o;for(e(t,r,i,n),r[2*o+h]>a&&e(t,r,i,o);d<f;){for(e(t,r,d,f),d++,f--;r[2*d+h]<a;)d++;for(;r[2*f+h]>a;)f--}r[2*i+h]===a?e(t,r,i,f):(f++,e(t,r,f,o)),f<=n&&(i=f+1),n<=f&&(o=f-1)}}function e(t,r,n,s){i(t,n,s),i(r,2*n,2*s),i(r,2*n+1,2*s+1)}function i(t,r,n){const s=t[r];t[r]=t[n],t[n]=s}function o(t,r,n,s){const e=t-n,i=r-s;return e*e+i*i}return r}));