kdTree-min.js

function swap(t,n,o){const i=t[n];t[n]=t[o],t[o]=i}function partition(t,n,o,e,r){const l=t[e][r];var u=n;for(swap(t,e,o-1),i=n;i<o-1;++i)t[i][r]<l&&(u<i&&swap(t,u,i),++u);return u<o-1&&swap(t,u,o-1),u}function lower_bound(t,n,o,i,e){for(var r=o-n;r>0;){let o=Math.floor(r/2);t[n+o][e]<i?(n+=o+1,r-=o+1):r=o}return n}function smallMedian(t,n,o,i){if(o-n<3)return n;const e=t[n+0],l=t[n+1],u=t[n+2],s=e[i],h=l[i],f=u[i];if(s<=h?f<h&&(f<s?(t[n+0]=u,t[n+1]=e,t[n+2]=l):(t[n+1]=u,t[n+2]=l)):f<h?(t[n+0]=u,t[n+1]=l,t[n+2]=e):f<s?(t[n+0]=l,t[n+1]=u,t[n+2]=e):(t[n+0]=l,t[n+1]=e),n+3==o)return n+1;for(r=n+3;r<o;++r){const o=lower_bound(t,n,r,t[r][i],i);if(o<r){const n=t[r];for(j=r;j>o;--j)t[j]=t[j-1];t[o]=n}}return Math.floor((n+o)/2)}function find_good_pivot_pos(t,n,o,e){if(o<=n+5)return smallMedian(t,n,o,e);var r=n;for(i=n;i<o;i+=5){const n=Math.min(i+5,o);swap(t,smallMedian(t,i,n,e),r),++r}return select(t,n,r,Math.floor((n+r)/2),e)}function select(t,n,o,i,e){for(;;){if(n+1==o)return n;let r=Math.floor((n+o)/2);if(i==(r=partition(t,n,o,r,e)))return i;i<r?o=r:n=r+1}}!function(t,n){"function"==typeof define&&define.amd?define(["exports"],n):"object"==typeof exports?n(exports):n(t)}(this,function(t){function n(t,n,o){this.obj=t,this.left=null,this.right=null,this.parent=o,this.dimIdx=n}function o(t){this.content=[],this.scoreFunction=t}o.prototype={push:function(t){this.content.push(t),this.bubbleUp(this.content.length-1)},pop:function(){var t=this.content[0],n=this.content.pop();return this.content.length>0&&(this.content[0]=n,this.sinkDown(0)),t},peek:function(){return this.content[0]},remove:function(t){for(var n=this.content.length,o=0;o<n;o++)if(this.content[o]==t){var i=this.content.pop();return void(o!=n-1&&(this.content[o]=i,this.scoreFunction(i)<this.scoreFunction(t)?this.bubbleUp(o):this.sinkDown(o)))}throw new Error("Node not found.")},size:function(){return this.content.length},bubbleUp:function(t){for(var n=this.content[t];t>0;){var o=Math.floor((t+1)/2)-1,i=this.content[o];if(!(this.scoreFunction(n)<this.scoreFunction(i)))break;this.content[o]=n,this.content[t]=i,t=o}},sinkDown:function(t){for(var n=this.content.length,o=this.content[t],i=this.scoreFunction(o);;){var e=2*(t+1),r=e-1,l=null;if(r<n){var u=this.content[r],s=this.scoreFunction(u);s<i&&(l=r)}if(e<n){var h=this.content[e];this.scoreFunction(h)<(null==l?i:s)&&(l=e)}if(null==l)break;this.content[t]=this.content[l],this.content[l]=o,t=l}}},t.kdTree=function(t,i,e){var r,l=this;Array.isArray(t)?this.root=function o(i,r,l,u){const s=l%e.length,h=e[s];if(i==r)return null;if(i+1==r)return new n(t[i],s,u);const f=Math.floor((i+r)/2);select(t,i,r,f,h);const c=new n(t[f],s,u);return c.left=o(i,f,l+1,c),c.right=o(f+1,r,l+1,c),c}(0,t.length,0,null):(r=t,l.root=r,function t(n){n.left&&(n.left.parent=n,t(n.left)),n.right&&(n.right.parent=n,t(n.right))}(l.root)),this.toJSON=function(t){t||(t=this.root);const o=new n(t.obj,t.dimIdx,null);return t.left&&(o.left=l.toJSON(t.left)),t.right&&(o.right=l.toJSON(t.right)),o},this.insert=function(t){const o=function n(o,i){if(null===o)return i;const r=e[o.dimIdx];return t[r]<o.obj[r]?n(o.left,o):n(o.right,o)}(this.root,null);if(null===o)return void(this.root=new n(t,0,null));const i=new n(t,(o.dimIdx+1)%e.length,o),r=e[o.dimIdx];t[r]<o.obj[r]?o.left=i:o.right=i},this.remove=function(t){var n;null!==(n=function n(o){if(null===o)return null;if(o.obj===t)return o;const i=e[o.dimIdx];return t[i]<o.obj[i]?n(o.left):n(o.right)}(l.root))&&function t(n){var o,i,r;function u(t,n){var o,i,r,l,s;return null===t?null:(o=e[n],t.dimIdx===n?null!==t.left?u(t.left,n):t:(i=t.obj[o],r=u(t.left,n),l=u(t.right,n),s=t,null!==r&&r.obj[o]<i&&(s=r),null!==l&&l.obj[o]<s.obj[o]&&(s=l),s))}if(null===n.left&&null===n.right)return null===n.parent?void(l.root=null):(r=e[n.parent.dimIdx],void(n.obj[r]<n.parent.obj[r]?n.parent.left=null:n.parent.right=null));null!==n.right?(i=(o=u(n.right,n.dimIdx)).obj,t(o),n.obj=i):(i=(o=u(n.left,n.dimIdx)).obj,t(o),n.right=n.left,n.left=null,n.obj=i)}(n)},this.nearest=function(t,n,r){var u,s,h;function f(t,o){h.push([t,o]),h.size()>n&&h.pop()}if(h=new o(function(t){return-t[1]}),r)for(u=0;u<n;u+=1)h.push([null,r]);for(l.root&&function o(r){var l,u;const s=e[r.dimIdx],c=i(t,r.obj);var a={};for(d=0;d<e.length;++d)a[e[d]]=r.obj[e[d]];a[s]=t[s];const p=i(a,r.obj);null!==r.right||null!==r.left?(o(l=null===r.right?r.left:null===r.left?r.right:t[s]<r.obj[s]?r.left:r.right),(h.size()<n||c<h.peek()[1])&&f(r,c),(h.size()<n||Math.abs(p)<h.peek()[1])&&null!==(u=l===r.left?r.right:r.left)&&o(u)):(h.size()<n||c<h.peek()[1])&&f(r,c)}(l.root),s=[],u=0;u<Math.min(n,h.content.length);u+=1)h.content[u][0]&&s.push([h.content[u][0].obj,h.content[u][1]]);return s},this.balanceFactor=function(){return function t(n){return null===n?0:Math.max(t(n.left),t(n.right))+1}(l.root)/(Math.log(function t(n){return null===n?0:t(n.left)+t(n.right)+1}(l.root))/Math.log(2))}},t.staticKdTree=function(t,n,i){var e=this;function r(t){return Math.floor((t[0]+t[1])/2)}this.points=t,this.root=function t(n,o,l){if(n+1>=o)return;const u=i[l%i.length],s=r([n,o]);select(e.points,n,o,s,u),t(n,s,l+1),t(s+1,o,l+1)}(0,e.points.length,0),this.nearest=function(l,u,s){var h,f,c;function a(t,n){c.push([t,n]),c.size()>u&&c.pop()}if(c=new o(function(t){return-t[1]}),s)for(h=0;h<u;h+=1)c.push([null,s]);for(e.points.length>0&&function t(o,s){const h=r(o),f=e.points[h],p=s%i.length,g=i[p];var b,v;const j=n(l,f);var m={};for(d=0;d<i.length;++d)m[i[d]]=f[i[d]];m[g]=l[g];const w=n(m,f),[M,x]=o;if(1==x-M)return void((c.size()<u||j<c.peek()[1])&&a(o,j));const k=[M,h],I=[h+1,x];I[0]==I[1]?(b=k,v=I):k[0]==k[1]?(b=I,v=k):l[g]<f[g]?(b=k,v=I):(b=I,v=k),t(b,s+1),(c.size()<u||j<c.peek()[1])&&a(o,j),(c.size()<u||Math.abs(w)<c.peek()[1])&&v[0]<v[1]&&t(v,s+1)}([0,t.length],0),f=[],h=0;h<Math.min(u,c.content.length);h+=1)bounds=c.content[h][0],null!=bounds&&f.push([e.points[r(bounds)],c.content[h][1]]);return f}},t.BinaryHeap=o});