jtBaseApp/node_modules/@arcgis/core/geohash/GeohashTree.js

/*
All material copyright ESRI, All Rights Reserved, unless otherwise specified.
See https://js.arcgis.com/4.25/esri/copyright.txt for details.
*/
import t from"../core/CircularArray.js";import{isSome as e,mapOr as s}from"../core/maybe.js";import{decodeGeohashXY as i}from"./geohashUtils.js";import n from"../geometry/SpatialReference.js";import{convertFromPolygon as o,quantizeOptimizedGeometry as a,convertFromPoint as r}from"../layers/graphics/featureConversionUtils.js";import l from"../layers/graphics/OptimizedGeometry.js";import{project as h}from"../layers/graphics/data/projectionSupport.js";import{FeatureSetReaderJSON as c}from"../views/2d/layers/features/support/FeatureSetReaderJSON.js";class u{constructor(e=[],s,i=8096){this.onRelease=t=>{},this._nodes=0,this._root=new d(this,0,0,0),this._statisticFields=e,this._pool=i?new t(8096):null,this._serviceInfo=s}destroy(){this.clear()}_acquire(t,s,i){this._nodes++;let n=null;return e(this._pool)&&(n=this._pool.dequeue()),e(n)?n.realloc(t,s,i):n=new d(this,t,s,i),n}_release(t){this.onRelease(t),this._nodes--,e(this._pool)&&this._pool.enqueue(t)}get count(){return this._root.count}get size(){return this._nodes}get poolSize(){return s(this._pool,0,(t=>t.size))}get depth(){let t=0;return this.forEach((e=>t=Math.max(t,e.depth))),t}dropLevels(t){this.forEach((e=>{if(e.depth>=t)for(let t=0;t<e.children.length;t++){const s=e.children[t];s&&this._release(s)}})),this.forEach((e=>{if(e.depth>=t)for(let t=0;t<e.children.length;t++)e.children[t]=null}))}clear(){this.forEach((t=>this._release(t))),this._root=new d(this,0,0,0)}insert(t,e,s=0){const i=c.fromOptimizedFeatures([t],this._serviceInfo).getCursor();i.next();const n=i.readGeometry();if(!n)return;const[o,a]=n.coords,r=t.geohashX,l=t.geohashY;this.insertCursor(i,t.displayId,o,a,r,l,e,s)}insertCursor(t,e,s,i,n,o,a,r=0){let l=this._root,h=0,c=0,u=0;for(;null!==l;){if(l.depth>=r&&(l.count+=1,l.xTotal+=s,l.yTotal+=i,l.xGeohashTotal+=n,l.yGeohashTotal+=o,l.referenceId=e,this._updateStatisticsCursor(t,l,1)),h>=a)return void l.add(e);const d=Math.ceil((h+1)/2),f=Math.floor((h+1)/2),x=1-h%2,m=30-(3*d+2*f),g=30-(2*d+3*f),y=(n&7*x+3*(1-x)<<m)>>m,p=(o&3*x+7*(1-x)<<g)>>g,_=y+p*(8*x+4*(1-x));c=c<<3*x+2*(1-x)|y,u=u<<2*x+3*(1-x)|p,null==l.children[_]&&(l.children[_]=this._acquire(c,u,h+1)),h+=1,l=l.children[_]}}remove(t,e){const s=c.fromOptimizedFeatures([t],this._serviceInfo).getCursor();s.next();const i=s.readGeometry();if(!i)return;const[n,o]=i.coords,a=t.geohashX,r=t.geohashY;this.removeCursor(s,n,o,a,r,e)}removeCursor(t,e,s,i,n,o){let a=this._root,r=0;for(;null!==a;){if(a.count-=1,a.xTotal-=e,a.yTotal-=s,a.xGeohashTotal-=i,a.yGeohashTotal-=n,this._updateStatisticsCursor(t,a,-1),r>=o)return void a.remove(t.getDisplayId());const l=Math.ceil((r+1)/2),h=Math.floor((r+1)/2),c=1-r%2,u=30-(3*l+2*h),d=30-(2*l+3*h),f=((i&7*c+3*(1-c)<<u)>>u)+((n&3*c+7*(1-c)<<d)>>d)*(8*c+4*(1-c)),x=a.children[f];1===x?.count&&(this._release(x),a.children[f]=null),r+=1,a=x}}forEach(t){let e=this._root;for(;null!==e;){const s=this._linkChildren(e)||e.next;t(e),e=s}}find(t,e,s){return this._root.find(t,e,s,0,0,0)}findIf(t){let e=null;return this.forEach((s=>{t(s)&&(e=s)})),e}findAllIf(t){const e=[];return this.forEach((s=>{t(s)&&e.push(s)})),e}findSingleOccupancyNode(t,e,s,i,n){let o=this._root;for(;null!==o;){const a=o.depth,r=o.xNode,l=o.yNode,h=1-a%2,c=o.xGeohashTotal/o.count,u=o.yGeohashTotal/o.count;if(1===o.count&&t<c&&c<=s&&e<u&&u<=i)return o;if(a>=n){o=o.next;continue}const d=Math.ceil((a+1)/2),f=Math.floor((a+1)/2),x=30-(3*d+2*f),m=30-(2*d+3*f),g=~((1<<x)-1),y=~((1<<m)-1),p=(t&g)>>x,_=(e&y)>>m,v=(s&g)>>x,M=(i&y)>>m,T=r<<3*h+2*(1-h),b=l<<2*h+3*(1-h),k=T+8*h+4*(1-h),N=b+4*h+8*(1-h),I=Math.max(T,p),C=Math.max(b,_),G=Math.min(k,v),L=Math.min(N,M);let S=null,w=null;for(let t=C;t<=L;t++)for(let e=I;e<=G;e++){const s=e-T+(t-b)*(8*h+4*(1-h)),i=o.children[s];i&&(S||(S=i,S.next=o.next),w&&(w.next=i),w=i,i.next=o.next)}o=S||o.next}return null}getRegionDisplayIds(t){let e=this._root;const{bounds:s,geohashBounds:i,level:n}=t,[o,a,r,l]=s,h=[];for(;null!==e;){const t=e.depth,s=e.xNode,c=e.yNode;if(t>=n){const t=e.xTotal/e.count,s=e.yTotal/e.count;t>=o&&t<=r&&s>=a&&s<=l&&e.displayIds.forEach((t=>h.push(t))),e=e.next;continue}const u=Math.ceil((t+1)/2),d=Math.floor((t+1)/2),f=1-t%2,x=30-(3*u+2*d),m=30-(2*u+3*d),g=~((1<<x)-1),y=~((1<<m)-1),p=(i.xLL&g)>>x,_=(i.yLL&y)>>m,v=(i.xTR&g)>>x,M=(i.yTR&y)>>m,T=s<<3*f+2*(1-f),b=c<<2*f+3*(1-f),k=T+8*f+4*(1-f),N=b+4*f+8*(1-f),I=Math.max(T,p),C=Math.max(b,_),G=Math.min(k,v),L=Math.min(N,M);let S=null,w=null;for(let i=C;i<=L;i++)for(let t=I;t<=G;t++){const s=t-T+(i-b)*(8*f+4*(1-f)),n=e.children[s];n&&(S||(S=n,S.next=e.next),w&&(w.next=n),w=n,n.next=e.next)}e=S||e.next}return h}getRegionStatistics(t){let e=this._root,s=0,i=0,n=0;const o={},{bounds:a,geohashBounds:r,level:l}=t,[h,c,u,d]=a;let f=0;for(;null!==e;){const t=e.depth,a=e.xNode,x=e.yNode;if(t>=l){const t=e.xTotal/e.count,a=e.yTotal/e.count;t>h&&t<=u&&a>c&&a<=d&&(s+=e.count,i+=e.xTotal,n+=e.yTotal,1===e.count&&(f=e.referenceId),this._aggregateStatistics(o,e.statistics)),e=e.next;continue}const m=Math.ceil((t+1)/2),g=Math.floor((t+1)/2),y=1-t%2,p=30-(3*m+2*g),_=30-(2*m+3*g),v=~((1<<p)-1),M=~((1<<_)-1),T=(r.xLL&v)>>p,b=(r.yLL&M)>>_,k=(r.xTR&v)>>p,N=(r.yTR&M)>>_,I=a<<3*y+2*(1-y),C=x<<2*y+3*(1-y),G=I+8*y+4*(1-y),L=C+4*y+8*(1-y),S=Math.max(I,T),w=Math.max(C,b),R=Math.min(G,k),F=Math.min(L,N);let j=null,z=null;for(let r=w;r<=F;r++)for(let t=S;t<=R;t++){const a=t-I+(r-C)*(8*y+4*(1-y)),l=e.children[a];if(l){if(r!==w&&r!==F&&t!==S&&t!==R){const t=l.xTotal/l.count,e=l.yTotal/l.count;t>h&&t<=u&&e>c&&e<=d&&(s+=l.count,i+=l.xTotal,n+=l.yTotal,1===l.count&&(f=l.referenceId),this._aggregateStatistics(o,l.statistics));continue}j||(j=l,j.next=e.next),z&&(z.next=l),z=l,l.next=e.next}}e=j||e.next}return{count:s,attributes:this.normalizeStatistics(o,s),xTotal:i,yTotal:n,referenceId:f}}getBins(t){const e=[],{geohashBounds:s,level:i}=t;let n=this._root;for(;null!==n;){const t=n.depth,o=n.xNode,a=n.yNode;if(t>=i){e.push(n),n=n.next;continue}const r=Math.ceil((t+1)/2),l=Math.floor((t+1)/2),h=1-t%2,c=30-(3*r+2*l),u=30-(2*r+3*l),d=~((1<<c)-1),f=~((1<<u)-1),x=(s.xLL&d)>>c,m=(s.yLL&f)>>u,g=(s.xTR&d)>>c,y=(s.yTR&f)>>u,p=o<<3*h+2*(1-h),_=a<<2*h+3*(1-h),v=p+8*h+4*(1-h),M=_+4*h+8*(1-h),T=Math.max(p,x),b=Math.max(_,m),k=Math.min(v,g),N=Math.min(M,y);let I=null,C=null;for(let e=b;e<=N;e++)for(let t=T;t<=k;t++){const s=t-p+(e-_)*(8*h+4*(1-h)),i=n.children[s];i&&(I||(I=i,I.next=n.next),C&&(C.next=i),C=i,i.next=n.next)}n=I||n.next}return e}_linkChildren(t){let e=null,s=null;for(let i=0;i<=t.children.length;i++){const n=t.children[i];n&&(e||(e=n,e.next=t.next),s&&(s.next=n),s=n,n.next=t.next)}return e}_updateStatisticsCursor(t,e,s){for(const i of this._statisticFields){const n=i.name,o=i.inField?t.readAttribute(i.inField):t.getComputedNumericAtIndex(i.inFieldIndex);switch(i.statisticType){case"min":{if(isNaN(o))break;if(!e.statistics[n]){e.statistics[n]={value:o};break}const t=e.statistics[n].value;e.statistics[n].value=Math.min(t,o);break}case"max":{if(isNaN(o))break;if(!e.statistics[n]){e.statistics[n]={value:o};break}const t=e.statistics[n].value;e.statistics[n].value=Math.max(t,o);break}case"count":break;case"sum":case"avg":{e.statistics[n]||(e.statistics[n]={value:0,nanCount:0});const t=e.statistics[n].value,i=e.statistics[n].nanCount??0;null==o||isNaN(o)?e.statistics[n].nanCount=i+s:e.statistics[n].value=t+s*o;break}case"avg_angle":{e.statistics[n]||(e.statistics[n]={x:0,y:0,nanCount:0});const t=e.statistics[n].x,i=e.statistics[n].y,a=e.statistics[n].nanCount??0,r=Math.PI/180;null==o||isNaN(o)?e.statistics[n].nanCount=a+s:(e.statistics[n].x=t+s*Math.cos(o*r),e.statistics[n].y=i+s*Math.sin(o*r));break}case"mode":{e.statistics[n]||(e.statistics[n]={});const t=e.statistics[n][o]||0;e.statistics[n][o]=t+s;break}}}}_aggregateStatistics(t,e){for(const s of this._statisticFields){const i=s.name;switch(s.statisticType){case"min":{if(!t[i]){t[i]={value:e[i].value};break}const s=t[i].value;t[i].value=Math.min(s,e[i].value);break}case"max":{if(!t[i]){t[i]={value:e[i].value};break}const s=t[i].value;t[i].value=Math.max(s,e[i].value);break}case"count":break;case"sum":case"avg":case"avg_angle":case"mode":t[i]||(t[i]={});for(const s in e[i]){const n=t[i][s]||0;t[i][s]=n+e[i][s]}}}}normalizeStatistics(t,e){const s={};for(const i of this._statisticFields){const n=i.name;switch(i.statisticType){case"min":case"max":{const i=t[n];if(!e||!i)break;s[n]=i.value;break}case"count":if(!e)break;s[n]=e;break;case"sum":{if(!e)break;const{value:i,nanCount:o}=t[n];if(!(e-o))break;s[n]=i;break}case"avg":{if(!e)break;const{value:i,nanCount:o}=t[n];if(!(e-o))break;s[n]=i/(e-o);break}case"avg_angle":{if(!e)break;const{x:i,y:o,nanCount:a}=t[n];if(!(e-a))break;const r=i/(e-a),l=o/(e-a),h=180/Math.PI,c=Math.atan2(l,r)*h;s[n]=c;break}case"mode":{const e=t[n];let i=0,o=0,a=null;for(const t in e){const s=e[t];s===i?o+=1:s>i&&(i=s,o=1,a=t)}s[n]="null"===a||o>1?null:a;break}}}return s}}class d{constructor(t,e,s,i){this.count=0,this.xTotal=0,this.yTotal=0,this.statistics={},this.displayId=0,this.referenceId=0,this.displayIds=new Set,this.next=null,this.depth=0,this.xNode=0,this.yNode=0,this.xGeohashTotal=0,this.yGeohashTotal=0,this._tree=t,this.children=new Array(32);for(let n=0;n<this.children.length;n++)this.children[n]=null;this.xNode=e,this.yNode=s,this.depth=i}realloc(t,e,s){for(let i=0;i<this.children.length;i++)this.children[i]=null;return this.xNode=t,this.yNode=e,this.depth=s,this.next=null,this.xGeohashTotal=0,this.yGeohashTotal=0,this.displayId=0,this.referenceId=0,this.xTotal=0,this.yTotal=0,this.count=0,this.statistics={},this.displayIds.clear(),this}get id(){return`${this.xNode}.${this.yNode}`}add(t){this.displayIds.add(t)}remove(t){this.displayIds.delete(t)}getAttributes(){const t=this._tree.normalizeStatistics(this.statistics,this.count);return t.referenceId=null,t.aggregateId=this.id,t.aggregateCount=this.count,t}getGeometry(t,s){const i=this.getLngLatBounds(),[r,c,u,d]=i,f=h({rings:[[[r,c],[r,d],[u,d],[u,c],[r,c]]]},n.WGS84,t),x=o(new l,f,!1,!1);if(e(s)){return a(new l,x,!1,!1,"esriGeometryPolygon",s,!1,!1)}return x}getGeometryCentroid(t,s){const i=this.getLngLatBounds(),[o,c,u,d]=i,f=h({x:(o+u)/2,y:(c+d)/2},n.WGS84,t),x=r(new l,f);if(e(s)){return a(new l,x,!1,!1,"esriGeometryPoint",s,!1,!1)}return x}getLngLatBounds(){const t=this.depth,e=Math.ceil(t/2),s=Math.floor(t/2),n=30-(3*e+2*s),o=30-(2*e+3*s),a=this.xNode<<n,r=this.yNode<<o;return i({geohashX:a,geohashY:r},this.depth)}find(t,e,s,i,n,o){if(i>=s)return this;const a=1-i%2,r=3*a+2*(1-a),l=2*a+3*(1-a),h=30-n-r,c=30-o-l,u=((t&7*a+3*(1-a)<<h)>>h)+((e&3*a+7*(1-a)<<c)>>c)*(8*a+4*(1-a)),d=this.children[u];return null==d?null:d.find(t,e,s,i+1,n+r,o+l)}}export{d as GeohashNode,u as GeohashTree};