/** * Minified by jsDelivr using Terser v5.48.0. * Original file: /npm/flatbush@4.6.2/flatbush.js * * Do NOT use SRI with dynamically generated files! More information: https://www.jsdelivr.com/using-sri-with-dynamic-files */ !function(t,s){"object"==typeof exports&&"undefined"!=typeof module?module.exports=s():"function"==typeof define&&define.amd?define([],s):(t="undefined"!=typeof globalThis?globalThis:t||self).Flatbush=s()}(this,function(){var t=class{constructor(t=1/0,s=Float64Array,i=Uint32Array){const e=t!==1/0;this.ids=e?new i(t):[],this.values=e?new s(t):[],this.capacity=t,this.length=0}clear(){this.length=0}push(t,s){if(this.length===this.capacity)throw new RangeError("Queue is at capacity.");let i=this.length++;for(;i>0;){const t=i-1>>1,e=this.values[t];if(s>=e)break;this.ids[i]=this.ids[t],this.values[i]=e,i=t}this.ids[i]=t,this.values[i]=s}pop(){if(0===this.length)return;const t=this.ids,s=this.values,i=t[0],e=--this.length;if(e>0){const i=t[e],n=s[e];let o=0;const r=e>>1;for(;o=n)break;t[o]=t[h],s[o]=s[h],o=h}t[o]=i,s[o]=n}return i}peek(){return this.length>0?this.ids[0]:void 0}peekValue(){return this.length>0?this.values[0]:void 0}shrink(){Array.isArray(this.ids)&&(this.ids.length=this.length),Array.isArray(this.values)&&(this.values.length=this.length)}};const s=[Int8Array,Uint8Array,Uint8ClampedArray,Int16Array,Uint16Array,Int32Array,Uint32Array,Float32Array,Float64Array];function i(t,s){let i=0,e=s.length-1;for(;i>1;s[n]>t?e=n:i=n+1}return s[i]}function e(t,s,i,e,n){const o=t[e];t[e]=t[n],t[n]=o;const r=4*e,h=4*n,a=s[r],l=s[r+1],c=s[r+2],f=s[r+3];s[r]=s[h],s[r+1]=s[h+1],s[r+2]=s[h+2],s[r+3]=s[h+3],s[h]=a,s[h+1]=l,s[h+2]=c,s[h+3]=f;const d=i[e];i[e]=i[n],i[n]=d}function n(t,s){let i=t^s,e=65535^i,n=65535^(t|s),o=t&(65535^s),r=i|e>>1,h=i>>1^i,a=n^n>>1^e&o>>1,l=o^i&n>>1^o>>1;return i=r&r>>2^h&h>>2,e=r&h>>2^h&(r^h)>>2,n=a^r&a>>2^h&l>>2,o=l^h&a>>2^(r^h)&l>>2,r=i&i>>4^e&e>>4,h=i&e>>4^e&(i^e)>>4,a=n^i&n>>4^e&o>>4,l=o^e&n>>4^(i^e)&o>>4,n=a^r&a>>8^h&l>>8,o=l^h&a>>8^(r^h)&l>>8,n^=n>>1,o^=o>>1,i=t^s,e=o|65535^(i|n),i=16711935&(i|i<<8),i=252645135&(i|i<<4),i=858993459&(i|i<<2),i=1431655765&(i|i<<1),e=16711935&(e|e<<8),e=252645135&(e|e<<4),e=858993459&(e|e<<2),e=1431655765&(e|e<<1),((e<<1|i)>>>0)-2147483648}return class o{static from(t,i=0){if(i%8!=0)throw new Error("byteOffset must be 8-byte aligned.");if(!t||void 0===t.byteLength||"buffer"in t)throw new Error("Data must be an instance of ArrayBuffer or SharedArrayBuffer.");const[e,n]=new Uint8Array(t,i+0,2);if(251!==e)throw new Error("Data does not appear to be in a Flatbush format.");const r=n>>4;if(3!==r)throw new Error(`Got v${r} data when expected v3.`);const h=s[15&n];if(!h)throw new Error("Unrecognized array type.");const[a]=new Uint16Array(t,i+2,1),[l]=new Uint32Array(t,i+4,1);return new o(l,a,h,void 0,t,i)}constructor(i,e=16,n=Float64Array,o=ArrayBuffer,r,h=0){if(void 0===i)throw new Error("Missing required argument: numItems.");if(isNaN(i)||i<=0)throw new Error(`Unexpected numItems value: ${i}.`);this.numItems=+i,this.nodeSize=Math.min(Math.max(+e,2),65535),this.byteOffset=h;let a=i,l=a;this._levelBounds=[4*a];do{a=Math.ceil(a/this.nodeSize),l+=a,this._levelBounds.push(4*l)}while(1!==a);this.ArrayType=n,this.IndexArrayType=l<16384?Uint16Array:Uint32Array;const c=s.indexOf(n),f=4*l*n.BYTES_PER_ELEMENT;if(c<0)throw new Error(`Unexpected typed array class: ${n}.`);const d=n,u=this.IndexArrayType;if(r)this.data=r,this._boxes=new d(r,h+8,4*l),this._indices=new u(r,h+8+f,l),this._pos=4*l,this.minX=this._boxes[this._pos-4],this.minY=this._boxes[this._pos-3],this.maxX=this._boxes[this._pos-2],this.maxY=this._boxes[this._pos-1];else{const t=this.data=new o(8+f+l*this.IndexArrayType.BYTES_PER_ELEMENT);this._boxes=new d(t,8,4*l),this._indices=new u(t,8+f,l),this._pos=0,this.minX=1/0,this.minY=1/0,this.maxX=-1/0,this.maxY=-1/0,new Uint8Array(t,0,2).set([251,48+c]),new Uint16Array(t,2,1)[0]=e,new Uint32Array(t,4,1)[0]=i}this._queue=new t}add(t,s,i=t,e=s){const n=this._pos,o=n>>2,r=this._boxes;return this._indices[o]=o,r[n]=t,r[n+1]=s,r[n+2]=i,r[n+3]=e,this._pos=n+4,tthis.maxX&&(this.maxX=i),e>this.maxY&&(this.maxY=e),o}finish(){if(this._pos>>2!==this.numItems)throw new Error(`Added ${this._pos>>2} items when expected ${this.numItems}.`);const t=this._boxes;if(this.numItems<=this.nodeSize)return t[this._pos++]=this.minX,t[this._pos++]=this.minY,t[this._pos++]=this.maxX,void(t[this._pos++]=this.maxY);const{numItems:s,minX:i,minY:o,nodeSize:r,_indices:h,_levelBounds:a}=this,l=this.maxX-i||1,c=this.maxY-o||1,f=new Int32Array(s),d=65535/l,u=65535/c;for(let e=0,r=0;e=Math.floor(n/r))continue;const a=t[o],l=t[o+n>>1],c=t[n],f=a>l!=a>c?a:lf);if(d>=u)break;e(t,s,i,d,u)}h.push(o,u,u+1,n)}}(f,t,h,0,s-1,r);let p=4*s;for(let s=0,i=0;s>2]=s,t[p++]=n,t[p++]=o,t[p++]=a,t[p++]=l}}this._pos=p}search(t,s,i,e,n){if(this._pos!==this._boxes.length)throw new Error("Data not yet indexed - call index.finish().");const{_boxes:o,_levelBounds:r,_indices:h,nodeSize:a}=this,l=4*this.numItems;let c=o.length-4,f=r.length-1;const d=[],u=[];let p=!1;for(;void 0!==c;){const m=Math.min(c+4*a,r[f]),y=c>=l;if(p)this._collectContained(c,m,f,l,u,n);else for(let r=c;rc)continue;const p=o[r+3];if(s>p)continue;const m=0|h[r>>2];if(y){const n=+(t<=a&&s<=l&&i>=c&&e>=p);d.push(m|n,f-1)}else(void 0===n||n(m,a,l,c,p))&&u.push(m)}f=d.pop(),c=d.pop(),void 0!==c&&(p=!(1&~c),c&=-2)}return u}_collectContained(t,s,i,e,n,o){const r=this._boxes,h=this._indices;let a=t;for(let t=i;t>0;t--)a=h[a>>2];const l=Math.min(a+(s-t)*this.nodeSize**i,e);if(void 0===o)for(;a>2]);else for(;a>2];o(t,r[a],r[a+1],r[a+2],r[a+3])&&n.push(t)}}neighbors(t,s,e=1/0,n=1/0,o){if(this._pos!==this._boxes.length)throw new Error("Data not yet indexed - call index.finish().");const{_boxes:r,_levelBounds:h,_indices:a,_queue:l,nodeSize:c}=this,f=4*this.numItems,d=4*c,u=[],p=1===e;let m=n*n;for(l.push(r.length-4<<1,0);l.length;){const n=l.ids[0];if(1&n){if(l.pop(),u.push(n>>1),u.length===e)break;continue}l.pop();const c=n>>1,y=cm)continue;const _=0|a[i>>2];y?(void 0===o||o(_))&&(l.push(_<<1|1,u),p&&u