function dn(n,e){return n.parent===e.parent?1:2}function pn(n){return n.reduce(gn,0)/n.length}function gn(n,e){return n+e.x}function yn(n){return 1+n.reduce(xn,0)}function xn(n,e){return Math.max(n,e.y)}function mn(n){for(var e;e=n.children;)n=e[0];return n}function vn(n){for(var e;e=n.children;)n=e[e.length-1];return n}function wn(){var n=dn,e=1,t=1,r=!1;function i(u){var l,s=0;u.eachAfter(function(a){var d=a.children;d?(a.x=pn(d),a.y=yn(d)):(a.x=l?s+=n(a,l):0,a.y=0,l=a)});var c=mn(u),f=vn(u),h=c.x-n(c,f)/2,o=f.x+n(f,c)/2;return u.eachAfter(r?function(a){a.x=(a.x-u.x)*e,a.y=(u.y-a.y)*t}:function(a){a.x=(a.x-h)/(o-h)*e,a.y=(1-(u.y?a.y/u.y:1))*t})}return i.separation=function(u){return arguments.length?(n=u,i):n},i.size=function(u){return arguments.length?(r=!1,e=+u[0],t=+u[1],i):r?null:[e,t]},i.nodeSize=function(u){return arguments.length?(r=!0,e=+u[0],t=+u[1],i):r?[e,t]:null},i}function _n(n){var e=0,t=n.children,r=t&&t.length;if(!r)e=1;else for(;--r>=0;)e+=t[r].value;n.value=e}function zn(){return this.eachAfter(_n)}function An(n,e){let t=-1;for(const r of this)n.call(e,r,++t,this);return this}function Mn(n,e){for(var t=this,r=[t],i,u,l=-1;t=r.pop();)if(n.call(e,t,++l,this),i=t.children)for(u=i.length-1;u>=0;--u)r.push(i[u]);return this}function kn(n,e){for(var t=this,r=[t],i=[],u,l,s,c=-1;t=r.pop();)if(i.push(t),u=t.children)for(l=0,s=u.length;l<s;++l)r.push(u[l]);for(;t=i.pop();)n.call(e,t,++c,this);return this}function Rn(n,e){let t=-1;for(const r of this)if(n.call(e,r,++t,this))return r}function Sn(n){return this.eachAfter(function(e){for(var t=+n(e.data)||0,r=e.children,i=r&&r.length;--i>=0;)t+=r[i].value;e.value=t})}function qn(n){return this.eachBefore(function(e){e.children&&e.children.sort(n)})}function In(n){for(var e=this,t=Nn(e,n),r=[e];e!==t;)e=e.parent,r.push(e);for(var i=r.length;n!==t;)r.splice(i,0,n),n=n.parent;return r}function Nn(n,e){if(n===e)return n;var t=n.ancestors(),r=e.ancestors(),i=null;for(n=t.pop(),e=r.pop();n===e;)i=n,n=t.pop(),e=r.pop();return i}function En(){for(var n=this,e=[n];n=n.parent;)e.push(n);return e}function Bn(){return Array.from(this)}function Ln(){var n=[];return this.eachBefore(function(e){e.children||n.push(e)}),n}function bn(){var n=this,e=[];return n.each(function(t){t!==n&&e.push({source:t.parent,target:t})}),e}function*Cn(){var n=this,e,t=[n],r,i,u;do for(e=t.reverse(),t=[];n=e.pop();)if(yield n,r=n.children)for(i=0,u=r.length;i<u;++i)t.push(r[i]);while(t.length)}function O(n,e){n instanceof Map?(n=[void 0,n],e===void 0&&(e=Dn)):e===void 0&&(e=$n);for(var t=new S(n),r,i=[t],u,l,s,c;r=i.pop();)if((l=e(r.data))&&(c=(l=Array.from(l)).length))for(r.children=l,s=c-1;s>=0;--s)i.push(u=l[s]=new S(l[s])),u.parent=r,u.depth=r.depth+1;return t.eachBefore(Z)}function Tn(){return O(this).eachBefore(On)}function $n(n){return n.children}function Dn(n){return Array.isArray(n)?n[1]:null}function On(n){n.data.value!==void 0&&(n.value=n.data.value),n.data=n.data.data}function Z(n){var e=0;do n.height=e;while((n=n.parent)&&n.height<++e)}function S(n){this.data=n,this.depth=this.height=0,this.parent=null}S.prototype=O.prototype={constructor:S,count:zn,each:An,eachAfter:kn,eachBefore:Mn,find:Rn,sum:Sn,sort:qn,path:In,ancestors:En,descendants:Bn,leaves:Ln,links:bn,copy:Tn,[Symbol.iterator]:Cn};function L(n){return n==null?null:F(n)}function F(n){if(typeof n!="function")throw new Error;return n}function q(){return 0}function N(n){return function(){return n}}const Vn=1664525,Wn=1013904223,G=4294967296;function V(){let n=1;return()=>(n=(Vn*n+Wn)%G)/G}function Pn(n){return typeof n=="object"&&"length"in n?n:Array.from(n)}function jn(n,e){let t=n.length,r,i;for(;t;)i=e()*t--|0,r=n[t],n[t]=n[i],n[i]=r;return n}function Kn(n){return J(n,V())}function J(n,e){for(var t=0,r=(n=jn(Array.from(n),e)).length,i=[],u,l;t<r;)u=n[t],l&&Q(l,u)?++t:(l=Yn(i=Xn(i,u)),t=0);return l}function Xn(n,e){var t,r;if(W(e,n))return[e];for(t=0;t<n.length;++t)if(b(e,n[t])&&W(E(n[t],e),n))return[n[t],e];for(t=0;t<n.length-1;++t)for(r=t+1;r<n.length;++r)if(b(E(n[t],n[r]),e)&&b(E(n[t],e),n[r])&&b(E(n[r],e),n[t])&&W(U(n[t],n[r],e),n))return[n[t],n[r],e];throw new Error}function b(n,e){var t=n.r-e.r,r=e.x-n.x,i=e.y-n.y;return t<0||t*t<r*r+i*i}function Q(n,e){var t=n.r-e.r+Math.max(n.r,e.r,1)*1e-9,r=e.x-n.x,i=e.y-n.y;return t>0&&t*t>r*r+i*i}function W(n,e){for(var t=0;t<e.length;++t)if(!Q(n,e[t]))return!1;return!0}function Yn(n){switch(n.length){case 1:return Hn(n[0]);case 2:return E(n[0],n[1]);case 3:return U(n[0],n[1],n[2])}}function Hn(n){return{x:n.x,y:n.y,r:n.r}}function E(n,e){var t=n.x,r=n.y,i=n.r,u=e.x,l=e.y,s=e.r,c=u-t,f=l-r,h=s-i,o=Math.sqrt(c*c+f*f);return{x:(t+u+c/o*h)/2,y:(r+l+f/o*h)/2,r:(o+i+s)/2}}function U(n,e,t){var r=n.x,i=n.y,u=n.r,l=e.x,s=e.y,c=e.r,f=t.x,h=t.y,o=t.r,a=r-l,d=r-f,p=i-s,g=i-h,y=c-u,x=o-u,m=r*r+i*i-u*u,_=m-l*l-s*s+c*c,w=m-f*f-h*h+o*o,v=d*p-a*g,z=(p*w-g*_)/(v*2)-r,k=(g*y-p*x)/v,A=(d*_-a*w)/(v*2)-i,M=(a*x-d*y)/v,I=k*k+M*M-1,R=2*(u+z*k+A*M),H=z*z+A*A-u*u,D=-(Math.abs(I)>1e-6?(R+Math.sqrt(R*R-4*I*H))/(2*I):H/R);return{x:r+z+k*D,y:i+A+M*D,r:D}}function nn(n,e,t){var r=n.x-e.x,i,u,l=n.y-e.y,s,c,f=r*r+l*l;f?(u=e.r+t.r,u*=u,c=n.r+t.r,c*=c,u>c?(i=(f+c-u)/(2*f),s=Math.sqrt(Math.max(0,c/f-i*i)),t.x=n.x-i*r-s*l,t.y=n.y-i*l+s*r):(i=(f+u-c)/(2*f),s=Math.sqrt(Math.max(0,u/f-i*i)),t.x=e.x+i*r-s*l,t.y=e.y+i*l+s*r)):(t.x=e.x+t.r,t.y=e.y)}function en(n,e){var t=n.r+e.r-1e-6,r=e.x-n.x,i=e.y-n.y;return t>0&&t*t>r*r+i*i}function tn(n){var e=n._,t=n.next._,r=e.r+t.r,i=(e.x*t.r+t.x*e.r)/r,u=(e.y*t.r+t.y*e.r)/r;return i*i+u*u}function C(n){this._=n,this.next=null,this.previous=null}function rn(n,e){if(!(u=(n=Pn(n)).length))return 0;var t,r,i,u,l,s,c,f,h,o,a;if(t=n[0],t.x=0,t.y=0,!(u>1))return t.r;if(r=n[1],t.x=-r.r,r.x=t.r,r.y=0,!(u>2))return t.r+r.r;nn(r,t,i=n[2]),t=new C(t),r=new C(r),i=new C(i),t.next=i.previous=r,r.next=t.previous=i,i.next=r.previous=t;n:for(c=3;c<u;++c){nn(t._,r._,i=n[c]),i=new C(i),f=r.next,h=t.previous,o=r._.r,a=t._.r;do if(o<=a){if(en(f._,i._)){r=f,t.next=r,r.previous=t,--c;continue n}o+=f._.r,f=f.next}else{if(en(h._,i._)){t=h,t.next=r,r.previous=t,--c;continue n}a+=h._.r,h=h.previous}while(f!==h.next);for(i.previous=t,i.next=r,t.next=r.previous=r=i,l=tn(t);(i=i.next)!==r;)(s=tn(i))<l&&(t=i,l=s);r=t.next}for(t=[r._],i=r;(i=i.next)!==r;)t.push(i._);for(i=J(t,e),c=0;c<u;++c)t=n[c],t.x-=i.x,t.y-=i.y;return i.r}function Zn(n){return rn(n,V()),n}function Fn(n){return Math.sqrt(n.value)}function Gn(){var n=null,e=1,t=1,r=q;function i(u){const l=V();return u.x=e/2,u.y=t/2,n?u.eachBefore(un(n)).eachAfter(P(r,.5,l)).eachBefore(an(1)):u.eachBefore(un(Fn)).eachAfter(P(q,1,l)).eachAfter(P(r,u.r/Math.min(e,t),l)).eachBefore(an(Math.min(e,t)/(2*u.r))),u}return i.radius=function(u){return arguments.length?(n=L(u),i):n},i.size=function(u){return arguments.length?(e=+u[0],t=+u[1],i):[e,t]},i.padding=function(u){return arguments.length?(r=typeof u=="function"?u:N(+u),i):r},i}function un(n){return function(e){e.children||(e.r=Math.max(0,+n(e)||0))}}function P(n,e,t){return function(r){if(i=r.children){var i,u,l=i.length,s=n(r)*e||0,c;if(s)for(u=0;u<l;++u)i[u].r+=s;if(c=rn(i,t),s)for(u=0;u<l;++u)i[u].r-=s;r.r=c+s}}}function an(n){return function(e){var t=e.parent;e.r*=n,t&&(e.x=t.x+n*e.x,e.y=t.y+n*e.y)}}function fn(n){n.x0=Math.round(n.x0),n.y0=Math.round(n.y0),n.x1=Math.round(n.x1),n.y1=Math.round(n.y1)}function B(n,e,t,r,i){for(var u=n.children,l,s=-1,c=u.length,f=n.value&&(r-e)/n.value;++s<c;)l=u[s],l.y0=t,l.y1=i,l.x0=e,l.x1=e+=l.value*f}function Jn(){var n=1,e=1,t=0,r=!1;function i(l){var s=l.height+1;return l.x0=l.y0=t,l.x1=n,l.y1=e/s,l.eachBefore(u(e,s)),r&&l.eachBefore(fn),l}function u(l,s){return function(c){c.children&&B(c,c.x0,l*(c.depth+1)/s,c.x1,l*(c.depth+2)/s);var f=c.x0,h=c.y0,o=c.x1-t,a=c.y1-t;o<f&&(f=o=(f+o)/2),a<h&&(h=a=(h+a)/2),c.x0=f,c.y0=h,c.x1=o,c.y1=a}}return i.round=function(l){return arguments.length?(r=!!l,i):r},i.size=function(l){return arguments.length?(n=+l[0],e=+l[1],i):[n,e]},i.padding=function(l){return arguments.length?(t=+l,i):t},i}var Qn={depth:-1},ln={},j={};function Un(n){return n.id}function ne(n){return n.parentId}function ee(){var n=Un,e=ne,t;function r(i){var u=Array.from(i),l=n,s=e,c,f,h,o,a,d,p,g,y=new Map;if(t!=null){const x=u.map((w,v)=>te(t(w,v,i))),m=x.map(cn),_=new Set(x).add("");for(const w of m)_.has(w)||(_.add(w),x.push(w),m.push(cn(w)),u.push(j));l=(w,v)=>x[v],s=(w,v)=>m[v]}for(h=0,c=u.length;h<c;++h)f=u[h],d=u[h]=new S(f),(p=l(f,h,i))!=null&&(p+="")&&(g=d.id=p,y.set(g,y.has(g)?ln:d)),(p=s(f,h,i))!=null&&(p+="")&&(d.parent=p);for(h=0;h<c;++h)if(d=u[h],p=d.parent){if(a=y.get(p),!a)throw new Error("missing: "+p);if(a===ln)throw new Error("ambiguous: "+p);a.children?a.children.push(d):a.children=[d],d.parent=a}else{if(o)throw new Error("multiple roots");o=d}if(!o)throw new Error("no root");if(t!=null){for(;o.data===j&&o.children.length===1;)o=o.children[0],--c;for(let x=u.length-1;x>=0&&!(d=u[x],d.data!==j);--x)d.data=null}if(o.parent=Qn,o.eachBefore(function(x){x.depth=x.parent.depth+1,--c}).eachBefore(Z),o.parent=null,c>0)throw new Error("cycle");return o}return r.id=function(i){return arguments.length?(n=L(i),r):n},r.parentId=function(i){return arguments.length?(e=L(i),r):e},r.path=function(i){return arguments.length?(t=L(i),r):t},r}function te(n){n=`${n}`;let e=n.length;return K(n,e-1)&&!K(n,e-2)&&(n=n.slice(0,-1)),n[0]==="/"?n:`/${n}`}function cn(n){let e=n.length;if(e<2)return"";for(;--e>1&&!K(n,e););return n.slice(0,e)}function K(n,e){if(n[e]==="/"){let t=0;for(;e>0&&n[--e]==="\\";)++t;if((t&1)===0)return!0}return!1}function re(n,e){return n.parent===e.parent?1:2}function X(n){var e=n.children;return e?e[0]:n.t}function Y(n){var e=n.children;return e?e[e.length-1]:n.t}function ie(n,e,t){var r=t/(e.i-n.i);e.c-=r,e.s+=t,n.c+=r,e.z+=t,e.m+=t}function ue(n){for(var e=0,t=0,r=n.children,i=r.length,u;--i>=0;)u=r[i],u.z+=e,u.m+=e,e+=u.s+(t+=u.c)}function ae(n,e,t){return n.a.parent===e.parent?n.a:t}function T(n,e){this._=n,this.parent=null,this.children=null,this.A=null,this.a=this,this.z=0,this.m=0,this.c=0,this.s=0,this.t=null,this.i=e}T.prototype=Object.create(S.prototype);function fe(n){for(var e=new T(n,0),t,r=[e],i,u,l,s;t=r.pop();)if(u=t._.children)for(t.children=new Array(s=u.length),l=s-1;l>=0;--l)r.push(i=t.children[l]=new T(u[l],l)),i.parent=t;return(e.parent=new T(null,0)).children=[e],e}function le(){var n=re,e=1,t=1,r=null;function i(f){var h=fe(f);if(h.eachAfter(u),h.parent.m=-h.z,h.eachBefore(l),r)f.eachBefore(c);else{var o=f,a=f,d=f;f.eachBefore(function(m){m.x<o.x&&(o=m),m.x>a.x&&(a=m),m.depth>d.depth&&(d=m)});var p=o===a?1:n(o,a)/2,g=p-o.x,y=e/(a.x+p+g),x=t/(d.depth||1);f.eachBefore(function(m){m.x=(m.x+g)*y,m.y=m.depth*x})}return f}function u(f){var h=f.children,o=f.parent.children,a=f.i?o[f.i-1]:null;if(h){ue(f);var d=(h[0].z+h[h.length-1].z)/2;a?(f.z=a.z+n(f._,a._),f.m=f.z-d):f.z=d}else a&&(f.z=a.z+n(f._,a._));f.parent.A=s(f,a,f.parent.A||o[0])}function l(f){f._.x=f.z+f.parent.m,f.m+=f.parent.m}function s(f,h,o){if(h){for(var a=f,d=f,p=h,g=a.parent.children[0],y=a.m,x=d.m,m=p.m,_=g.m,w;p=Y(p),a=X(a),p&&a;)g=X(g),d=Y(d),d.a=f,w=p.z+m-a.z-y+n(p._,a._),w>0&&(ie(ae(p,f,o),f,w),y+=w,x+=w),m+=p.m,y+=a.m,_+=g.m,x+=d.m;p&&!Y(d)&&(d.t=p,d.m+=m-x),a&&!X(g)&&(g.t=a,g.m+=y-_,o=f)}return o}function c(f){f.x*=e,f.y=f.depth*t}return i.separation=function(f){return arguments.length?(n=f,i):n},i.size=function(f){return arguments.length?(r=!1,e=+f[0],t=+f[1],i):r?null:[e,t]},i.nodeSize=function(f){return arguments.length?(r=!0,e=+f[0],t=+f[1],i):r?[e,t]:null},i}function $(n,e,t,r,i){for(var u=n.children,l,s=-1,c=u.length,f=n.value&&(i-t)/n.value;++s<c;)l=u[s],l.x0=e,l.x1=r,l.y0=t,l.y1=t+=l.value*f}var hn=(1+Math.sqrt(5))/2;function sn(n,e,t,r,i,u){for(var l=[],s=e.children,c,f,h=0,o=0,a=s.length,d,p,g=e.value,y,x,m,_,w,v,z;h<a;){d=i-t,p=u-r;do y=s[o++].value;while(!y&&o<a);for(x=m=y,v=Math.max(p/d,d/p)/(g*n),z=y*y*v,w=Math.max(m/z,z/x);o<a;++o){if(y+=f=s[o].value,f<x&&(x=f),f>m&&(m=f),z=y*y*v,_=Math.max(m/z,z/x),_>w){y-=f;break}w=_}l.push(c={value:y,dice:d<p,children:s.slice(h,o)}),c.dice?B(c,t,r,i,g?r+=p*y/g:u):$(c,t,r,g?t+=d*y/g:i,u),g-=y,h=o}return l}var on=function n(e){function t(r,i,u,l,s){sn(e,r,i,u,l,s)}return t.ratio=function(r){return n((r=+r)>1?r:1)},t}(hn);function ce(){var n=on,e=!1,t=1,r=1,i=[0],u=q,l=q,s=q,c=q,f=q;function h(a){return a.x0=a.y0=0,a.x1=t,a.y1=r,a.eachBefore(o),i=[0],e&&a.eachBefore(fn),a}function o(a){var d=i[a.depth],p=a.x0+d,g=a.y0+d,y=a.x1-d,x=a.y1-d;y<p&&(p=y=(p+y)/2),x<g&&(g=x=(g+x)/2),a.x0=p,a.y0=g,a.x1=y,a.y1=x,a.children&&(d=i[a.depth+1]=u(a)/2,p+=f(a)-d,g+=l(a)-d,y-=s(a)-d,x-=c(a)-d,y<p&&(p=y=(p+y)/2),x<g&&(g=x=(g+x)/2),n(a,p,g,y,x))}return h.round=function(a){return arguments.length?(e=!!a,h):e},h.size=function(a){return arguments.length?(t=+a[0],r=+a[1],h):[t,r]},h.tile=function(a){return arguments.length?(n=F(a),h):n},h.padding=function(a){return arguments.length?h.paddingInner(a).paddingOuter(a):h.paddingInner()},h.paddingInner=function(a){return arguments.length?(u=typeof a=="function"?a:N(+a),h):u},h.paddingOuter=function(a){return arguments.length?h.paddingTop(a).paddingRight(a).paddingBottom(a).paddingLeft(a):h.paddingTop()},h.paddingTop=function(a){return arguments.length?(l=typeof a=="function"?a:N(+a),h):l},h.paddingRight=function(a){return arguments.length?(s=typeof a=="function"?a:N(+a),h):s},h.paddingBottom=function(a){return arguments.length?(c=typeof a=="function"?a:N(+a),h):c},h.paddingLeft=function(a){return arguments.length?(f=typeof a=="function"?a:N(+a),h):f},h}function he(n,e,t,r,i){var u=n.children,l,s=u.length,c,f=new Array(s+1);for(f[0]=c=l=0;l<s;++l)f[l+1]=c+=u[l].value;h(0,s,n.value,e,t,r,i);function h(o,a,d,p,g,y,x){if(o>=a-1){var m=u[o];m.x0=p,m.y0=g,m.x1=y,m.y1=x;return}for(var _=f[o],w=d/2+_,v=o+1,z=a-1;v<z;){var k=v+z>>>1;f[k]<w?v=k+1:z=k}w-f[v-1]<f[v]-w&&o+1<v&&--v;var A=f[v]-_,M=d-A;if(y-p>x-g){var I=d?(p*M+y*A)/d:y;h(o,v,A,p,g,I,x),h(v,a,M,I,g,y,x)}else{var R=d?(g*M+x*A)/d:x;h(o,v,A,p,g,y,R),h(v,a,M,p,R,y,x)}}}function se(n,e,t,r,i){(n.depth&1?$:B)(n,e,t,r,i)}var oe=function n(e){function t(r,i,u,l,s){if((c=r._squarify)&&c.ratio===e)for(var c,f,h,o,a=-1,d,p=c.length,g=r.value;++a<p;){for(f=c[a],h=f.children,o=f.value=0,d=h.length;o<d;++o)f.value+=h[o].value;f.dice?B(f,i,u,l,g?u+=(s-u)*f.value/g:s):$(f,i,u,g?i+=(l-i)*f.value/g:l,s),g-=f.value}else r._squarify=c=sn(e,r,i,u,l,s),c.ratio=e}return t.ratio=function(r){return n((r=+r)>1?r:1)},t}(hn);export{S as Node,wn as cluster,O as hierarchy,Gn as pack,Kn as packEnclose,Zn as packSiblings,Jn as partition,ee as stratify,le as tree,ce as treemap,he as treemapBinary,B as treemapDice,oe as treemapResquarify,$ as treemapSlice,se as treemapSliceDice,on as treemapSquarify};export default null;