!function(t,e){"object"==typeof exports&&"undefined"!=typeof module?module.exports=e():"function"==typeof define&&define.amd?define(e):(t="undefined"!=typeof globalThis?globalThis:t||self).Supercluster=e()}(this,(function(){"use strict";const t=[Int8Array,Uint8Array,Uint8ClampedArray,Int16Array,Uint16Array,Int32Array,Uint32Array,Float32Array,Float64Array];class e{static from(s){if(!(s instanceof ArrayBuffer))throw new Error("Data must be an instance of ArrayBuffer.");const[n,i]=new Uint8Array(s,0,2);if(219!==n)throw new Error("Data does not appear to be in a KDBush format.");const o=i>>4;if(1!==o)throw new Error(`Got v${o} data when expected v1.`);const r=t[15&i];if(!r)throw new Error("Unrecognized array type.");const[h]=new Uint16Array(s,2,1),[a]=new Uint32Array(s,4,1);return new e(a,h,r,s)}constructor(e,s=64,n=Float64Array,i){if(isNaN(e)||e<0)throw new Error(`Unpexpected numItems value: ${e}.`);this.numItems=+e,this.nodeSize=Math.min(Math.max(+s,2),65535),this.ArrayType=n,this.IndexArrayType=e<65536?Uint16Array:Uint32Array;const o=t.indexOf(this.ArrayType),r=2*e*this.ArrayType.BYTES_PER_ELEMENT,h=e*this.IndexArrayType.BYTES_PER_ELEMENT,a=(8-h%8)%8;if(o<0)throw new Error(`Unexpected typed array class: ${n}.`);i&&i instanceof ArrayBuffer?(this.data=i,this.ids=new this.IndexArrayType(this.data,8,e),this.coords=new this.ArrayType(this.data,8+h+a,2*e),this._pos=2*e,this._finished=!0):(this.data=new ArrayBuffer(8+r+h+a),this.ids=new this.IndexArrayType(this.data,8,e),this.coords=new this.ArrayType(this.data,8+h+a,2*e),this._pos=0,this._finished=!1,new Uint8Array(this.data,0,2).set([219,16+o]),new Uint16Array(this.data,2,1)[0]=s,new Uint32Array(this.data,4,1)[0]=e)}add(t,e){const s=this._pos>>1;return this.ids[s]=s,this.coords[this._pos++]=t,this.coords[this._pos++]=e,s}finish(){const t=this._pos>>1;if(t!==this.numItems)throw new Error(`Added ${t} items when expected ${this.numItems}.`);return s(this.ids,this.coords,this.nodeSize,0,this.numItems-1,0),this._finished=!0,this}range(t,e,s,n){if(!this._finished)throw new Error("Data not yet indexed - call index.finish().");const{ids:i,coords:o,nodeSize:r}=this,h=[0,i.length-1,0],a=[];for(;h.length;){const c=h.pop()||0,p=h.pop()||0,u=h.pop()||0;if(p-u<=r){for(let r=u;r<=p;r++){const h=o[2*r],c=o[2*r+1];h>=t&&h<=s&&c>=e&&c<=n&&a.push(i[r])}continue}const d=u+p>>1,f=o[2*d],l=o[2*d+1];f>=t&&f<=s&&l>=e&&l<=n&&a.push(i[d]),(0===c?t<=f:e<=l)&&(h.push(u),h.push(d-1),h.push(1-c)),(0===c?s>=f:n>=l)&&(h.push(d+1),h.push(p),h.push(1-c))}return a}within(t,e,s){if(!this._finished)throw new Error("Data not yet indexed - call index.finish().");const{ids:n,coords:i,nodeSize:o}=this,h=[0,n.length-1,0],a=[],c=s*s;for(;h.length;){const p=h.pop()||0,u=h.pop()||0,d=h.pop()||0;if(u-d<=o){for(let s=d;s<=u;s++)r(i[2*s],i[2*s+1],t,e)<=c&&a.push(n[s]);continue}const f=d+u>>1,l=i[2*f],m=i[2*f+1];r(l,m,t,e)<=c&&a.push(n[f]),(0===p?t-s<=l:e-s<=m)&&(h.push(d),h.push(f-1),h.push(1-p)),(0===p?t+s>=l:e+s>=m)&&(h.push(f+1),h.push(u),h.push(1-p))}return a}}function s(t,e,i,o,r,h){if(r-o<=i)return;const a=o+r>>1;n(t,e,a,o,r,h),s(t,e,i,o,a-1,1-h),s(t,e,i,a+1,r,1-h)}function n(t,e,s,o,r,h){for(;r>o;){if(r-o>600){const i=r-o+1,a=s-o+1,c=Math.log(i),p=.5*Math.exp(2*c/3),u=.5*Math.sqrt(c*p*(i-p)/i)*(a-i/2<0?-1:1);n(t,e,s,Math.max(o,Math.floor(s-a*p/i+u)),Math.min(r,Math.floor(s+(i-a)*p/i+u)),h)}const a=e[2*s+h];let c=o,p=r;for(i(t,e,o,s),e[2*r+h]>a&&i(t,e,o,r);c<p;){for(i(t,e,c,p),c++,p--;e[2*c+h]<a;)c++;for(;e[2*p+h]>a;)p--}e[2*o+h]===a?i(t,e,o,p):(p++,i(t,e,p,r)),p<=s&&(o=p+1),s<=p&&(r=p-1)}}function i(t,e,s,n){o(t,s,n),o(e,2*s,2*n),o(e,2*s+1,2*n+1)}function o(t,e,s){const n=t[e];t[e]=t[s],t[s]=n}function r(t,e,s,n){const i=t-s,o=e-n;return i*i+o*o}const h={minZoom:0,maxZoom:16,minPoints:2,radius:40,extent:512,nodeSize:64,log:!1,generateId:!1,reduce:null,map:t=>t},a=Math.fround||(c=new Float32Array(1),t=>(c[0]=+t,c[0]));var c;const p=3,u=5,d=6;function f(t,e,s){return{type:"Feature",id:t[e+p],properties:l(t,e,s),geometry:{type:"Point",coordinates:[(n=t[e],360*(n-.5)),y(t[e+1])]}};var n}function l(t,e,s){const n=t[e+u],i=n>=1e4?`${Math.round(n/1e3)}k`:n>=1e3?Math.round(n/100)/10+"k":n,o=t[e+d],r=-1===o?{}:Object.assign({},s[o]);return Object.assign(r,{cluster:!0,cluster_id:t[e+p],point_count:n,point_count_abbreviated:i})}function m(t){return t/360+.5}function g(t){const e=Math.sin(t*Math.PI/180),s=.5-.25*Math.log((1+e)/(1-e))/Math.PI;return s<0?0:s>1?1:s}function y(t){const e=(180-360*t)*Math.PI/180;return 360*Math.atan(Math.exp(e))/Math.PI-90}return class{constructor(t){this.options=Object.assign(Object.create(h),t),this.trees=new Array(this.options.maxZoom+1),this.stride=this.options.reduce?7:6,this.clusterProps=[]}load(t){const{log:e,minZoom:s,maxZoom:n}=this.options;e&&console.time("total time");const i=`prepare ${t.length} points`;e&&console.time(i),this.points=t;const o=[];for(let e=0;e<t.length;e++){const s=t[e];if(!s.geometry)continue;const[n,i]=s.geometry.coordinates,r=a(m(n)),h=a(g(i));o.push(r,h,1/0,e,-1,1),this.options.reduce&&o.push(0)}let r=this.trees[n+1]=this._createTree(o);e&&console.timeEnd(i);for(let t=n;t>=s;t--){const s=+Date.now();r=this.trees[t]=this._createTree(this._cluster(r,t)),e&&console.log("z%d: %d clusters in %dms",t,r.numItems,+Date.now()-s)}return e&&console.timeEnd("total time"),this}getClusters(t,e){let s=((t[0]+180)%360+360)%360-180;const n=Math.max(-90,Math.min(90,t[1]));let i=180===t[2]?180:((t[2]+180)%360+360)%360-180;const o=Math.max(-90,Math.min(90,t[3]));if(t[2]-t[0]>=360)s=-180,i=180;else if(s>i){const t=this.getClusters([s,n,180,o],e),r=this.getClusters([-180,n,i,o],e);return t.concat(r)}const r=this.trees[this._limitZoom(e)],h=r.range(m(s),g(o),m(i),g(n)),a=r.data,c=[];for(const t of h){const e=this.stride*t;c.push(a[e+u]>1?f(a,e,this.clusterProps):this.points[a[e+p]])}return c}getChildren(t){const e=this._getOriginId(t),s=this._getOriginZoom(t),n="No cluster with the specified id.",i=this.trees[s];if(!i)throw new Error(n);const o=i.data;if(e*this.stride>=o.length)throw new Error(n);const r=this.options.radius/(this.options.extent*Math.pow(2,s-1)),h=o[e*this.stride],a=o[e*this.stride+1],c=i.within(h,a,r),d=[];for(const e of c){const s=e*this.stride;o[s+4]===t&&d.push(o[s+u]>1?f(o,s,this.clusterProps):this.points[o[s+p]])}if(0===d.length)throw new Error(n);return d}getLeaves(t,e,s){e=e||10,s=s||0;const n=[];return this._appendLeaves(n,t,e,s,0),n}getTile(t,e,s){const n=this.trees[this._limitZoom(t)],i=Math.pow(2,t),{extent:o,radius:r}=this.options,h=r/o,a=(s-h)/i,c=(s+1+h)/i,p={features:[]};return this._addTileFeatures(n.range((e-h)/i,a,(e+1+h)/i,c),n.data,e,s,i,p),0===e&&this._addTileFeatures(n.range(1-h/i,a,1,c),n.data,i,s,i,p),e===i-1&&this._addTileFeatures(n.range(0,a,h/i,c),n.data,-1,s,i,p),p.features.length?p:null}getClusterExpansionZoom(t){let e=this._getOriginZoom(t)-1;for(;e<=this.options.maxZoom;){const s=this.getChildren(t);if(e++,1!==s.length)break;t=s[0].properties.cluster_id}return e}_appendLeaves(t,e,s,n,i){const o=this.getChildren(e);for(const e of o){const o=e.properties;if(o&&o.cluster?i+o.point_count<=n?i+=o.point_count:i=this._appendLeaves(t,o.cluster_id,s,n,i):i<n?i++:t.push(e),t.length===s)break}return i}_createTree(t){const s=new e(t.length/this.stride|0,this.options.nodeSize,Float32Array);for(let e=0;e<t.length;e+=this.stride)s.add(t[e],t[e+1]);return s.finish(),s.data=t,s}_addTileFeatures(t,e,s,n,i,o){for(const r of t){const t=r*this.stride,h=e[t+u]>1;let a,c,d;if(h)a=l(e,t,this.clusterProps),c=e[t],d=e[t+1];else{const s=this.points[e[t+p]];a=s.properties;const[n,i]=s.geometry.coordinates;c=m(n),d=g(i)}const f={type:1,geometry:[[Math.round(this.options.extent*(c*i-s)),Math.round(this.options.extent*(d*i-n))]],tags:a};let y;y=h||this.options.generateId?e[t+p]:this.points[e[t+p]].id,void 0!==y&&(f.id=y),o.features.push(f)}}_limitZoom(t){return Math.max(this.options.minZoom,Math.min(Math.floor(+t),this.options.maxZoom+1))}_cluster(t,e){const{radius:s,extent:n,reduce:i,minPoints:o}=this.options,r=s/(n*Math.pow(2,e)),h=t.data,a=[],c=this.stride;for(let s=0;s<h.length;s+=c){if(h[s+2]<=e)continue;h[s+2]=e;const n=h[s],p=h[s+1],d=t.within(h[s],h[s+1],r),f=h[s+u];let l=f;for(const t of d){const s=t*c;h[s+2]>e&&(l+=h[s+u])}if(l>f&&l>=o){let t,o=n*f,r=p*f,m=-1;const g=((s/c|0)<<5)+(e+1)+this.points.length;for(const n of d){const a=n*c;if(h[a+2]<=e)continue;h[a+2]=e;const p=h[a+u];o+=h[a]*p,r+=h[a+1]*p,h[a+4]=g,i&&(t||(t=this._map(h,s,!0),m=this.clusterProps.length,this.clusterProps.push(t)),i(t,this._map(h,a)))}h[s+4]=g,a.push(o/l,r/l,1/0,g,-1,l),i&&a.push(m)}else{for(let t=0;t<c;t++)a.push(h[s+t]);if(l>1)for(const t of d){const s=t*c;if(!(h[s+2]<=e)){h[s+2]=e;for(let t=0;t<c;t++)a.push(h[s+t])}}}}return a}_getOriginId(t){return t-this.points.length>>5}_getOriginZoom(t){return(t-this.points.length)%32}_map(t,e,s){if(t[e+u]>1){const n=this.clusterProps[t[e+d]];return s?Object.assign({},n):n}const n=this.points[t[e+p]].properties,i=this.options.map(n);return s&&i===n?Object.assign({},i):i}}}));