d3-quadtree - npm Package Compare versions

Comparing version 0.2.1 to 0.3.0

build/d3-quadtree.js

 (function (global, factory) {
   typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
   typeof define === 'function' && define.amd ? define(['exports'], factory) :
-  (factory((global.d3_quadtree = {})));
+  (factory((global.d3_quadtree = global.d3_quadtree || {})));
 }(this, function (exports) { 'use strict';
 
-  function pointX(p) {
-    return p[0];
-  }
+  var version = "0.3.0";
 
-  function pointY(p) {
-    return p[1];
-  }
-
-  function functor(x) {
+  function constant(x) {
     return function() {
@@ -21,196 +15,227 @@ return x;
 
-  function Node() {
-    this.x = null;
-    this.y = null;
-    this.leaf = true;
-    this.data = null;
-    this.nodes = [];
+  function Leaf(point) {
+    this.point = point;
   }
 
-  function visit(callback, node, x1, y1, x2, y2) {
-    if (!callback(node, x1, y1, x2, y2)) {
-      var sx = (x1 + x2) / 2,
-          sy = (y1 + y2) / 2,
-          children = node.nodes;
-      if (children[0]) visit(callback, children[0], x1, y1, sx, sy);
-      if (children[1]) visit(callback, children[1], sx, y1, x2, sy);
-      if (children[2]) visit(callback, children[2], x1, sy, sx, y2);
-      if (children[3]) visit(callback, children[3], sx, sy, x2, y2);
+  function root_add(point) {
+    if (isNaN(x = point[0]) || isNaN(y = point[1])) return; // ignore invalid points
+
+    var point0,
+        node = this._root,
+        parent,
+        grandparent,
+        x,
+        y,
+        xm,
+        ym,
+        x0 = this._x0,
+        y0 = this._y0,
+        x1 = this._x1,
+        y1 = this._y1,
+        right,
+        bottom,
+        i,
+        i0;
+
+    // If the tree is empty, initialize the root as a leaf.
+    if (!node) {
+      this._root = new Leaf(point);
+      this._x0 = this._x1 = x;
+      this._y0 = this._y1 = y;
+      return;
     }
-  }
 
-  function find(root, x, y, x0, y0, x3, y3) {
-    var minDistance2 = Infinity,
-        closestNode;
+    // Expand the tree to cover the new point, if necessary.
+    if (x0 > x || x > x1 || y0 > y || y > y1) {
+      xm = x0 === x1 ? Math.max(Math.abs(x0 - x), Math.abs(y0 - y)) : (x1 - x0) * 2;
+      switch (i = (y < (y0 + y1) / 2) << 1 | (x < (x0 + x1) / 2)) {
+        case 0: do parent = new Array(4), parent[i] = node, node = parent, x1 = x0 + xm, y1 = y0 + xm, xm *= 2; while (x > x1 || y > y1); break;
+        case 1: do parent = new Array(4), parent[i] = node, node = parent, x0 = x1 - xm, y1 = y0 + xm, xm *= 2; while (x0 > x || y > y1); break;
+        case 2: do parent = new Array(4), parent[i] = node, node = parent, x1 = x0 + xm, y0 = y1 - xm, xm *= 2; while (x > x1 || y0 > y); break;
+        case 3: do parent = new Array(4), parent[i] = node, node = parent, x0 = x1 - xm, y0 = y1 - xm, xm *= 2; while (x0 > x || y0 > y); break;
+      }
+      this._root = node;
+      this._x0 = x0, this._x1 = x1;
+      this._y0 = y0, this._y1 = y1;
+    }
 
-    (function findChild(node, x1, y1, x2, y2) {
+    // Find the appropriate leaf node for the new point.
+    do {
+      if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;
+      if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;
+      grandparent = parent, parent = node, node = node[i0 = i, i = bottom << 1 | right];
+    } while (node);
 
-      // stop searching if this cell can’t contain a closer node
-      if (x1 > x3 || y1 > y3 || x2 < x0 || y2 < y0) return;
+    // If the new point is in an empty node, just add it.
+    if (!(point0 = parent.point)) return void (parent[i] = new Leaf(point));
 
-      // visit this point
-      if (node.x != null) {
-        var dx = x - node.x,
-            dy = y - node.y,
-            distance2 = dx * dx + dy * dy;
-        if (distance2 < minDistance2) {
-          var distance = Math.sqrt(minDistance2 = distance2);
-          x0 = x - distance, y0 = y - distance;
-          x3 = x + distance, y3 = y + distance;
-          closestNode = node;
-        }
-      }
+    // If the new point is exactly coincident with the specified point, add it.
+    if (x === point0[0] && y === point0[1]) {
+      point.next = point0;
+      parent.point = point;
+      return;
+    }
 
-      // bisect the current node
-      var children = node.nodes,
-          xm = (x1 + x2) / 2,
-          ym = (y1 + y2) / 2,
-          right = x >= xm,
-          below = y >= ym;
+    // Otherwise, split the leaf node until the old and new point are separated.
+    parent = grandparent[i0] = new Array(4);
+    while (i === (i0 = (point0[1] >= ym) << 1 | (point0[0] >= xm))) {
+      parent = parent[i] = new Array(4);
+      if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;
+      if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;
+      i = bottom << 1 | right;
+    }
 
-      // visit closest cell first
-      for (var i = below << 1 | right, j = i + 4; i < j; ++i) {
-        if (node = children[i & 3]) switch (i & 3) {
-          case 0: findChild(node, x1, y1, xm, ym); break;
-          case 1: findChild(node, xm, y1, x2, ym); break;
-          case 2: findChild(node, x1, ym, xm, y2); break;
-          case 3: findChild(node, xm, ym, x2, y2); break;
-        }
-      }
-    })(root, x0, y0, x3, y3);
+    parent[i0] = new Leaf(point0);
+    parent[i] = new Leaf(point);
+  }
 
-    return closestNode && closestNode.data;
+  function Quad(node, x0, y0, x1, y1) {
+    this.node = node;
+    this.x0 = x0;
+    this.y0 = y0;
+    this.x1 = x1;
+    this.y1 = y1;
   }
 
-  function quadtree() {
-    var x = pointX,
-        y = pointY,
+  function root_eachAfter(callback) {
+    var quads = [], next = [], q;
+    if (this._root) quads.push(new Quad(this._root, this._x0, this._y0, this._x1, this._y1));
+    while (q = quads.pop()) {
+      var node = q.node, child, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1, xm = (x0 + x1) / 2, ym = (y0 + y1) / 2;
+      if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym));
+      if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym));
+      if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1));
+      if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1));
+      next.push(q);
+    }
+    while (q = next.pop()) {
+      callback(q.node, q.x0, q.y0, q.x1, q.y1);
+    }
+    return this;
+  }
+
+  function root_eachBefore(callback) {
+    var quads = [], q, node = this._root, child, x0, y0, x1, y1;
+    if (node) quads.push(new Quad(node, this._x0, this._y0, this._x1, this._y1));
+    while (q = quads.pop()) {
+      if (!callback(node = q.node, x0 = q.x0, y0 = q.y0, x1 = q.x1, y1 = q.y1)) {
+        var xm = (x0 + x1) / 2, ym = (y0 + y1) / 2;
+        if (child = node[3]) quads.push(new Quad(child, xm, ym, x1, y1));
+        if (child = node[2]) quads.push(new Quad(child, x0, ym, xm, y1));
+        if (child = node[1]) quads.push(new Quad(child, xm, y0, x1, ym));
+        if (child = node[0]) quads.push(new Quad(child, x0, y0, xm, ym));
+      }
+    }
+    return this;
+  }
+
+  function root_find(x, y) {
+    var minDistance2 = Infinity,
+        minPoint,
+        x0 = this._x0,
+        y0 = this._y0,
         x1,
+        y1,
         x2,
-        y1,
-        y2;
+        y2,
+        x3 = this._x1,
+        y3 = this._y1,
+        quads = [],
+        node = this._root,
+        q,
+        i;
 
-    function quadtree(data) {
-      var d,
-          fx = typeof x === "function" ? x : functor(x),
-          fy = typeof y === "function" ? y : functor(y),
-          xs,
-          ys,
-          i,
-          n,
-          x1_,
-          y1_,
-          x2_,
-          y2_;
+    if (node) quads.push(new Quad(node, x0, y0, x3, y3));
 
-      if (!data) data = [];
+    while (q = quads.pop()) {
+      node = q.node, x1 = q.x0, y1 = q.y0, x2 = q.x1, y2 = q.y1;
 
-      if (x1 != null) {
-        x1_ = x1, y1_ = y1, x2_ = x2, y2_ = y2;
-      } else {
-        // Compute bounds, and cache points temporarily.
-        x2_ = y2_ = -(x1_ = y1_ = Infinity);
-        xs = [], ys = [];
-        n = data.length;
-        for (i = 0; i < n; ++i) {
-          var x_ = +fx(d = data[i], i, data),
-              y_ = +fy(d, i, data);
-          if (x_ < x1_) x1_ = x_;
-          if (y_ < y1_) y1_ = y_;
-          if (x_ > x2_) x2_ = x_;
-          if (y_ > y2_) y2_ = y_;
-          xs.push(x_);
-          ys.push(y_);
+      // Stop searching if this quadrant can’t contain a closer node.
+      if (!node || x1 > x3 || y1 > y3 || x2 < x0 || y2 < y0) continue;
+
+      // Visit this point.
+      if (node.point) {
+        var dx = x - node.point[0],
+            dy = y - node.point[1],
+            d2 = dx * dx + dy * dy;
+        if (d2 < minDistance2) {
+          var d = Math.sqrt(minDistance2 = d2);
+          x0 = x - d, y0 = y - d;
+          x3 = x + d, y3 = y + d;
+          minPoint = node.point;
         }
       }
 
-      // Squarify the bounds.
-      var dx = x2_ - x1_,
-          dy = y2_ - y1_;
-      if (isFinite(dx) && isFinite(dy)) {
-        if (dx > dy) y2_ = y1_ + dx;
-        else x2_ = x1_ + dy;
-      }
+      // Bisect the current quadrant.
+      var xm = (x1 + x2) / 2,
+          ym = (y1 + y2) / 2;
 
-      // Recursively inserts the specified point at the node or one of its
-      // descendants. The bounds are defined by [x1, x2] and [y1, y2].
-      function insert(node, d, x, y, x1, y1, x2, y2) {
-        if (isNaN(x) || isNaN(y)) return; // ignore invalid points
-        if (node.leaf) {
-          var nx = node.x,
-              ny = node.y;
-          if (nx != null) {
-            // If the point at this leaf node is at the same position as the new
-            // point we are adding, we leave the point associated with the
-            // internal node while adding the new point to a child node. This
-            // avoids infinite recursion.
-            if ((Math.abs(nx - x) + Math.abs(ny - y)) < .01) {
-              insertChild(node, d, x, y, x1, y1, x2, y2);
-            } else {
-              var d0 = node.data;
-              node.x = node.y = node.data = null;
-              insertChild(node, d0, nx, ny, x1, y1, x2, y2);
-              insertChild(node, d, x, y, x1, y1, x2, y2);
-            }
-          } else {
-            node.x = x, node.y = y, node.data = d;
-          }
-        } else {
-          insertChild(node, d, x, y, x1, y1, x2, y2);
-        }
+      quads.push(
+        new Quad(node[3], xm, ym, x2, y2),
+        new Quad(node[2], x1, ym, xm, y2),
+        new Quad(node[1], xm, y1, x2, ym),
+        new Quad(node[0], x1, y1, xm, ym)
+      );
+
+      // Visit the closest quadrant first.
+      if (i = (y >= ym) << 1 | (x >= xm)) {
+        q = quads[quads.length - 1];
+        quads[quads.length - 1] = quads[quads.length - 1 - i];
+        quads[quads.length - 1 - i] = q;
       }
+    }
 
-      // Recursively inserts the specified point [x, y] into a descendant of node
-      // n. The bounds are defined by [x1, x2] and [y1, y2].
-      function insertChild(node, d, x, y, x1, y1, x2, y2) {
-        // Compute the split point, and the quadrant in which to insert the point.
-        var xm = (x1 + x2) / 2,
-            ym = (y1 + y2) / 2,
-            right = x >= xm,
-            below = y >= ym,
-            i = below << 1 | right;
+    return minPoint;
+  }
 
-        // Recursively insert into the child node.
-        node.leaf = false;
-        node = node.nodes[i] || (node.nodes[i] = new Node);
+  function Root() {
+    this._x0 =
+    this._y0 =
+    this._x1 =
+    this._y1 = NaN;
+    this._root = null;
+  }
 
-        // Update the bounds as we recurse.
-        if (right) x1 = xm; else x2 = xm;
-        if (below) y1 = ym; else y2 = ym;
-        insert(node, d, x, y, x1, y1, x2, y2);
-      }
+  var rootProto = Root.prototype;
+  rootProto.add = root_add;
+  rootProto.eachAfter = root_eachAfter;
+  rootProto.eachBefore = root_eachBefore;
+  rootProto.find = root_find;
 
-      var root = new Node;
+  function defaultX(d) {
+    return d[0];
+  }
 
-      root.add = function(d) {
-        insert(root, d, +fx(d, ++i), +fy(d, i), x1_, y1_, x2_, y2_);
-        return root;
-      };
+  function defaultY(d) {
+    return d[1];
+  }
 
-      root.visit = function(callback) {
-        visit(callback, root, x1_, y1_, x2_, y2_);
-        return root;
-      };
+  function quadtree() {
+    var x = defaultX,
+        y = defaultY,
+        ox,
+        oy,
+        l;
 
-      // Find the closest point to the specified point.
-      // TODO allow the initial search extent to be specified?
-      // TODO allow the initial minimum distance to be specified?
-      // TODO allow searching below any node?
-      root.find = function(x, y) {
-        return find(root, x, y, x1_, y1_, x2_, y2_);
-      };
+    function quadtree(data) {
+      var d, i, n = data.length, p,
+          xi, yi,
+          x0 = -Infinity,
+          y0 = -Infinity,
+          x1 = Infinity,
+          y1 = Infinity,
+          root = new Root;
 
-      // Insert all points.
-      i = -1;
-      if (x1 == null) {
-        while (++i < n) {
-          insert(root, data[i], xs[i], ys[i], x1_, y1_, x2_, y2_);
-        }
-        --i; // index of last insertion
-      } else {
-        data.forEach(root.add);
+      if (ox != null) {
+        root._root = new Array(4);
+        root._x0 = x0 = ox, root._x1 = x1 = ox + l;
+        root._y0 = y0 = oy, root._y1 = y1 = oy + l;
       }
 
-      // Discard captured fields.
-      xs = ys = data = d = null;
+      for (i = 0; i < n; ++i) {
+        xi = +x(d = data[i], i, data), yi = +y(d, i, data);
+        if (x0 > xi || xi >= x1 || y0 > yi || yi >= y1) continue;
+        p = [xi, yi], p.data = d, p.index = i;
+        root.add(p);
+      }
 
@@ -221,21 +246,15 @@ return root;
     quadtree.x = function(_) {
-      return arguments.length ? (x = _, quadtree) : x;
+      return arguments.length ? (x = typeof _ === "function" ? _ : constant(+_), quadtree) : x;
     };
 
     quadtree.y = function(_) {
-      return arguments.length ? (y = _, quadtree) : y;
+      return arguments.length ? (y = typeof _ === "function" ? _ : constant(+_), quadtree) : y;
     };
 
     quadtree.extent = function(_) {
-      if (!arguments.length) return x1 == null ? null : [[x1, y1], [x2, y2]];
-      if (_ == null) x1 = y1 = x2 = y2 = null;
-      else x1 = +_[0][0], y1 = +_[0][1], x2 = +_[1][0], y2 = +_[1][1];
-      return quadtree;
+      return arguments.length ? (_ == null ? ox = oy = l = null : (ox = +_[0][0], oy = +_[0][1], l = Math.max(_[1][0] - ox, _[1][1] - oy)), quadtree) : ox == null ? null : [[ox, oy], [ox + l, oy + l]];
     };
 
     quadtree.size = function(_) {
-      if (!arguments.length) return x1 == null ? null : [x2 - x1, y2 - y1];
-      if (_ == null) x1 = y1 = x2 = y2 = null;
-      else x1 = y1 = 0, x2 = +_[0], y2 = +_[1];
-      return quadtree;
+      return arguments.length ? (_ == null ? ox = oy = l = null : (ox = oy = 0, l = Math.max(+_[0], +_[1])), quadtree) : ox == null ? null : [l, l];
     };
@@ -246,4 +265,2 @@
 
-  var version = "0.2.1";
-
   exports.version = version;
@@ -250,0 +267,0 @@ exports.quadtree = quadtree;

build/d3-quadtree.min.js

@@ -1,1 +0,1 @@
-!function(n,t){"object"==typeof exports&&"undefined"!=typeof module?t(exports):"function"==typeof define&&define.amd?define(["exports"],t):t(n.d3_quadtree={})}(this,function(n){"use strict";function t(n){return n[0]}function e(n){return n[1]}function u(n){return function(){return n}}function r(){this.x=null,this.y=null,this.leaf=!0,this.data=null,this.nodes=[]}function i(n,t,e,u,r,f){if(!n(t,e,u,r,f)){var a=(e+r)/2,l=(u+f)/2,o=t.nodes;o[0]&&i(n,o[0],e,u,a,l),o[1]&&i(n,o[1],a,u,r,l),o[2]&&i(n,o[2],e,l,a,f),o[3]&&i(n,o[3],a,l,r,f)}}function f(n,t,e,u,r,i,f){var a,l=1/0;return function o(n,s,c,d,h){if(!(s>i||c>f||u>d||r>h)){if(null!=n.x){var v=t-n.x,x=e-n.y,y=v*v+x*x;if(l>y){var p=Math.sqrt(l=y);u=t-p,r=e-p,i=t+p,f=e+p,a=n}}for(var g=n.nodes,b=(s+d)/2,m=(c+h)/2,N=t>=b,k=e>=m,q=k<<1|N,w=q+4;w>q;++q)if(n=g[3&q])switch(3&q){case 0:o(n,s,c,b,m);break;case 1:o(n,b,c,d,m);break;case 2:o(n,s,m,b,h);break;case 3:o(n,b,m,d,h)}}}(n,u,r,i,f),a&&a.data}function a(){function n(n){function t(n,t,u,r,i,f,a,l){if(!isNaN(u)&&!isNaN(r))if(n.leaf){var o=n.x,s=n.y;if(null!=o)if(Math.abs(o-u)+Math.abs(s-r)<.01)e(n,t,u,r,i,f,a,l);else{var c=n.data;n.x=n.y=n.data=null,e(n,c,o,s,i,f,a,l),e(n,t,u,r,i,f,a,l)}else n.x=u,n.y=r,n.data=t}else e(n,t,u,r,i,f,a,l)}function e(n,e,u,i,f,a,l,o){var s=(f+l)/2,c=(a+o)/2,d=u>=s,h=i>=c,v=h<<1|d;n.leaf=!1,n=n.nodes[v]||(n.nodes[v]=new r),d?f=s:l=s,h?a=c:o=c,t(n,e,u,i,f,a,l,o)}var h,v,x,y,p,g,b,m,N,k="function"==typeof c?c:u(c),q="function"==typeof d?d:u(d);if(n||(n=[]),null!=a)g=a,b=o,m=l,N=s;else for(m=N=-(g=b=1/0),v=[],x=[],p=n.length,y=0;p>y;++y){var w=+k(h=n[y],y,n),M=+q(h,y,n);g>w&&(g=w),b>M&&(b=M),w>m&&(m=w),M>N&&(N=M),v.push(w),x.push(M)}var F=m-g,j=N-b;isFinite(F)&&isFinite(j)&&(F>j?N=b+F:m=g+j);var z=new r;if(z.add=function(n){return t(z,n,+k(n,++y),+q(n,y),g,b,m,N),z},z.visit=function(n){return i(n,z,g,b,m,N),z},z.find=function(n,t){return f(z,n,t,g,b,m,N)},y=-1,null==a){for(;++y<p;)t(z,n[y],v[y],x[y],g,b,m,N);--y}else n.forEach(z.add);return v=x=n=h=null,z}var a,l,o,s,c=t,d=e;return n.x=function(t){return arguments.length?(c=t,n):c},n.y=function(t){return arguments.length?(d=t,n):d},n.extent=function(t){return arguments.length?(null==t?a=o=l=s=null:(a=+t[0][0],o=+t[0][1],l=+t[1][0],s=+t[1][1]),n):null==a?null:[[a,o],[l,s]]},n.size=function(t){return arguments.length?(null==t?a=o=l=s=null:(a=o=0,l=+t[0],s=+t[1]),n):null==a?null:[l-a,s-o]},n}var l="0.2.1";n.version=l,n.quadtree=a});
+!function(t,n){"object"==typeof exports&&"undefined"!=typeof module?n(exports):"function"==typeof define&&define.amd?define(["exports"],n):n(t.d3_quadtree=t.d3_quadtree||{})}(this,function(t){"use strict";function n(t){return function(){return t}}function e(t){this.point=t}function i(t){if(!isNaN(o=t[0])&&!isNaN(h=t[1])){var n,i,r,o,h,s,u,a,f,_,y,p=this._root,x=this._x0,l=this._y0,w=this._x1,d=this._y1;if(!p)return this._root=new e(t),this._x0=this._x1=o,void(this._y0=this._y1=h);if(x>o||o>w||l>h||h>d){switch(s=x===w?Math.max(Math.abs(x-o),Math.abs(l-h)):2*(w-x),_=((l+d)/2>h)<<1|(x+w)/2>o){case 0:do i=new Array(4),i[_]=p,p=i,w=x+s,d=l+s,s*=2;while(o>w||h>d);break;case 1:do i=new Array(4),i[_]=p,p=i,x=w-s,d=l+s,s*=2;while(x>o||h>d);break;case 2:do i=new Array(4),i[_]=p,p=i,w=x+s,l=d-s,s*=2;while(o>w||l>h);break;case 3:do i=new Array(4),i[_]=p,p=i,x=w-s,l=d-s,s*=2;while(x>o||l>h)}this._root=p,this._x0=x,this._x1=w,this._y0=l,this._y1=d}do(a=o>=(s=(x+w)/2))?x=s:w=s,(f=h>=(u=(l+d)/2))?l=u:d=u,r=i,i=p,p=p[(y=_,_=f<<1|a)];while(p);if(!(n=i.point))return void(i[_]=new e(t));if(o===n[0]&&h===n[1])return t.next=n,void(i.point=t);for(i=r[y]=new Array(4);_===(y=(n[1]>=u)<<1|n[0]>=s);)i=i[_]=new Array(4),(a=o>=(s=(x+w)/2))?x=s:w=s,(f=h>=(u=(l+d)/2))?l=u:d=u,_=f<<1|a;i[y]=new e(n),i[_]=new e(t)}}function r(t,n,e,i,r){this.node=t,this.x0=n,this.y0=e,this.x1=i,this.y1=r}function o(t){var n,e=[],i=[];for(this._root&&e.push(new r(this._root,this._x0,this._y0,this._x1,this._y1));n=e.pop();){var o,h=n.node,s=n.x0,u=n.y0,a=n.x1,f=n.y1,_=(s+a)/2,y=(u+f)/2;(o=h[0])&&e.push(new r(o,s,u,_,y)),(o=h[1])&&e.push(new r(o,_,u,a,y)),(o=h[2])&&e.push(new r(o,s,y,_,f)),(o=h[3])&&e.push(new r(o,_,y,a,f)),i.push(n)}for(;n=i.pop();)t(n.node,n.x0,n.y0,n.x1,n.y1);return this}function h(t){var n,e,i,o,h,s,u=[],a=this._root;for(a&&u.push(new r(a,this._x0,this._y0,this._x1,this._y1));n=u.pop();)if(!t(a=n.node,i=n.x0,o=n.y0,h=n.x1,s=n.y1)){var f=(i+h)/2,_=(o+s)/2;(e=a[3])&&u.push(new r(e,f,_,h,s)),(e=a[2])&&u.push(new r(e,i,_,f,s)),(e=a[1])&&u.push(new r(e,f,o,h,_)),(e=a[0])&&u.push(new r(e,i,o,f,_))}return this}function s(t,n){var e,i,o,h,s,u,a,f=1/0,_=this._x0,y=this._y0,p=this._x1,x=this._y1,l=[],w=this._root;for(w&&l.push(new r(w,_,y,p,x));u=l.pop();)if(w=u.node,i=u.x0,o=u.y0,h=u.x1,s=u.y1,!(!w||i>p||o>x||_>h||y>s)){if(w.point){var d=t-w.point[0],c=n-w.point[1],v=d*d+c*c;if(f>v){var g=Math.sqrt(f=v);_=t-g,y=n-g,p=t+g,x=n+g,e=w.point}}var A=(i+h)/2,b=(o+s)/2;l.push(new r(w[3],A,b,h,s),new r(w[2],i,b,A,s),new r(w[1],A,o,h,b),new r(w[0],i,o,A,b)),(a=(n>=b)<<1|t>=A)&&(u=l[l.length-1],l[l.length-1]=l[l.length-1-a],l[l.length-1-a]=u)}return e}function u(){this._x0=this._y0=this._x1=this._y1=NaN,this._root=null}function a(t){return t[0]}function f(t){return t[1]}function _(){function t(t){var n,s,a,f,_,y=t.length,p=-(1/0),x=-(1/0),l=1/0,w=1/0,d=new u;for(null!=e&&(d._root=new Array(4),d._x0=p=e,d._x1=l=e+r,d._y0=x=i,d._y1=w=i+r),s=0;y>s;++s)f=+o(n=t[s],s,t),_=+h(n,s,t),p>f||f>=l||x>_||_>=w||(a=[f,_],a.data=n,a.index=s,d.add(a));return d}var e,i,r,o=a,h=f;return t.x=function(e){return arguments.length?(o="function"==typeof e?e:n(+e),t):o},t.y=function(e){return arguments.length?(h="function"==typeof e?e:n(+e),t):h},t.extent=function(n){return arguments.length?(null==n?e=i=r=null:(e=+n[0][0],i=+n[0][1],r=Math.max(n[1][0]-e,n[1][1]-i)),t):null==e?null:[[e,i],[e+r,i+r]]},t.size=function(n){return arguments.length?(null==n?e=i=r=null:(e=i=0,r=Math.max(+n[0],+n[1])),t):null==e?null:[r,r]},t}var y="0.3.0",p=u.prototype;p.add=i,p.eachAfter=o,p.eachBefore=h,p.find=s,t.version=y,t.quadtree=_});

index.js

@@ -0,1 +1,2 @@
+export {version} from "./build/package";
 export {default as quadtree} from "./src/quadtree";

package.json

 {
   "name": "d3-quadtree",
-  "version": "0.2.1",
+  "version": "0.3.0",
   "description": "Two-dimensional recursive spatial subdivision.",
@@ -22,10 +22,10 @@ "keywords": [
   "scripts": {
-    "pretest": "mkdir -p build && node -e 'process.stdout.write(\"var version = \\\"\" + require(\"./package.json\").version + \"\\\"; export * from \\\"../index\\\"; export {version};\");' > build/bundle.js && rollup -f umd -n d3_quadtree -o build/d3-quadtree.js -- build/bundle.js",
-    "test": "faucet `find test -name '*-test.js'` && eslint index.js src",
-    "prepublish": "npm run test && uglifyjs build/d3-quadtree.js -c -m -o build/d3-quadtree.min.js && rm -f build/d3-quadtree.zip && zip -j build/d3-quadtree.zip -- LICENSE README.md build/d3-quadtree.js build/d3-quadtree.min.js",
-    "postpublish": "VERSION=`node -e 'console.log(require(\"./package.json\").version)'`; git push && git tag -am \"Release $VERSION.\" v${VERSION} && git push --tags && cp build/d3-quadtree.js ../d3.github.com/d3-quadtree.v0.2.js && cp build/d3-quadtree.min.js ../d3.github.com/d3-quadtree.v0.2.min.js && cd ../d3.github.com && git add d3-quadtree.v0.2.js d3-quadtree.v0.2.min.js && git commit -m \"d3-quadtree ${VERSION}\" && git push"
+    "pretest": "rm -rf build && mkdir build && json2module package.json > build/package.js && rollup -f umd -n d3_quadtree -o build/d3-quadtree.js -- index.js",
+    "test": "tape 'test/**/*-test.js' && eslint index.js src",
+    "prepublish": "npm run test && uglifyjs build/d3-quadtree.js -c -m -o build/d3-quadtree.min.js",
+    "postpublish": "VERSION=`node -e 'console.log(require(\"./package.json\").version)'`; git push && git push --tags && cp build/d3-quadtree.js ../d3.github.com/d3-quadtree.v0.3.js && cp build/d3-quadtree.min.js ../d3.github.com/d3-quadtree.v0.3.min.js && cd ../d3.github.com && git add d3-quadtree.v0.3.js d3-quadtree.v0.3.min.js && git commit -m \"d3-quadtree ${VERSION}\" && git push && cd - && zip -j build/d3-quadtree.zip -- LICENSE README.md build/d3-quadtree.js build/d3-quadtree.min.js"
   },
   "devDependencies": {
-    "d3-array": "~0.7.1",
-    "faucet": "0.0",
+    "d3-array": "0.7",
+    "json2module": "0.0",
     "rollup": "0.25",
@@ -32,0 +32,0 @@ "tape": "4",

README.md

@@ -14,9 +14,14 @@ # d3-quadtree
 
-If you use NPM, `npm install d3-quadtree`. Otherwise, download the [latest release](https://github.com/d3/d3-quadtree/releases/latest). The released bundle supports AMD, CommonJS, and vanilla environments. Create a custom build using [Rollup](https://github.com/rollup/rollup) or your preferred bundler. You can also load directly from [d3js.org](https://d3js.org):
+If you use NPM, `npm install d3-quadtree`. Otherwise, download the [latest release](https://github.com/d3/d3-quadtree/releases/latest). You can also load directly from [d3js.org](https://d3js.org), either as a [standalone library](https://d3js.org/d3-quadtree.v0.3.min.js) or as part of [D3 4.0 alpha](https://github.com/mbostock/d3/tree/4). AMD, CommonJS, and vanilla environments are supported. In vanilla, a `d3_quadtree` global is exported:
 
 ```html
-<script src="https://d3js.org/d3-quadtree.v0.2.min.js"></script>
+<script src="https://d3js.org/d3-quadtree.v0.3.min.js"></script>
+<script>
+
+var quadtree = d3_quadtree.quadtree();
+
+</script>
 ```
 
-In a vanilla environment, a `d3_quadtree` global is exported. [Try d3-quadtree in your browser.](https://tonicdev.com/npm/d3-quadtree)
+[Try d3-quadtree in your browser.](https://tonicdev.com/npm/d3-quadtree)
 
@@ -27,35 +32,14 @@ ## API Reference
 
-Creates a new [quadtree factory](#_quadtree) with the default [*x*-accessor](#quadtree_x), [*y*-accessor](#quadtree_y) and [extent](#quadtree_extent). The returned factory function can be used to create any number of quadtrees from data.
+Creates a new quadtree generator with the default [*x*-accessor](#quadtree_x), [*y*-accessor](#quadtree_y) and [extent](#quadtree_extent). The returned generator can be used to [create](#_quadtree) any number of quadtree roots from data.
 
-<a name="_quadtree" href="#_quadtree">#</a> <i>quadtree</i>([<i>data</i>])
+<a name="_quadtree" href="#_quadtree">#</a> <i>quadtree</i>(<i>data</i>)
 
-Constructs a new quadtree for the specified array of *data*, returning the root node of a new quadtree. The *x*- and *y*-coordinates of each data point are determined using the current [*x*-](#quadtree_x) and [*y*-](#quadtree_y)accessor functions. To build a quadtree by adding points incrementally, the specified *data* array can be empty or omitted and then points can be later [added](#root_add) to the returned root node; in this case, you must explicitly specify the [extent](#quadtree_extent) of the quadtree.
+Constructs a new [quadtree root node](#quadtree-nodes) for the specified array of *data*. The *x*- and *y*-coordinates of each data point are determined using the current [*x*-](#quadtree_x) and [*y*-](#quadtree_y)accessors; each point in the quadtree is represented as a two-element array of numbers [*x*, *y*] with the following additional properties:
 
-Each node in the quadtree has several properties:
+* `data` - the datum associated with this node.
+* `index` - the index of the datum associated with this node.
 
-* `nodes` - a sparse array of four child nodes: top-left, top-right, bottom-left, bottom-right.
-* `leaf` - a boolean indicating whether this is an internal node or a leaf node.
-* `data` - the datum associated with this node, if any; may apply to either internal or leaf nodes.
-* `x` - the *x*-coordinate of the associated point, if any.
-* `y` - the *y*-coordinate of the associated point, if any.
-
-The returned root node also defines [add](#root_add) and [visit](#root_visit) methods.
-
-<a name="root_add" href="#root_add">#</a> <i>root</i>.<b>add</b>(<i>datum</i>)
-
-Adds the specified new *datum* to this quadtree and returns *root*.
-
-<a name="root_find" href="#root_find">#</a> <i>root</i>.<b>find</b>(<i>x</i>, <i>y</i>)
-
-Given a point ⟨*x*,*y*⟩, returns the closest datum in this quadtree.
-
-<a name="root_visit" href="#root_visit">#</a> <i>root</i>.<b>visit</b>(<i>callback</i>)
-
-Visits each node in this quadtree, invoking the specified *callback* with arguments {*node*, *x1*, *y1*, *x2*, *y2*} for each node, where *node* is the node being visited, ⟨*x1*, *y1*⟩ is the top-left corner, and ⟨*x2*, *y2*⟩ is the bottom-right corner. Returns *root*. Nodes are traversed in pre-order. If the *callback* returns true for a given node, then the children of that node are not visited; otherwise, all child nodes are visited.
-
-Note that the coordinate system used by the quadtree is arbitrary, so a more precise definition is that *x1* <= *x2* and *y1* <= *y2*. In the typical coordinate system used by SVG and Canvas, the origin ⟨0,0⟩ is in the top-left corner, and thus ⟨*x1*, *y1*⟩ is also the top-left corner of the current node.
-
 <a name="quadtree_x" href="#quadtree_x">#</a> <i>quadtree</i>.<b>x</b>([<i>x</i>])
 
-If *x* is specified, sets the *x*-coordinate accessor and returns this quadtree factory. If *x* is not specified, returns the current *x*-coordinate accessor, which defaults to:
+If *x* is specified, sets the *x*-coordinate accessor and returns this quadtree generator. If *x* is not specified, returns the current *x*-coordinate accessor, which defaults to:
 
@@ -68,7 +52,7 @@ ```js
 
-For each point added to the quadtree, either during [initial construction](#_quadtree) or lazily [added](#root_add), the *x*-accessor is invoked, being passed the current datum `d` and index `i`. The *x*-accessor must then return a numeric value indicating the *x*-coordinate of the point corresponding to the given datum. The *x*-accessor may also be defined as a constant number rather than a function, if desired.
+For each point added to the quadtree, the *x*-accessor is invoked, being passed the current datum `d` and index `i`. The *x*-accessor must then return a numeric value indicating the *x*-coordinate of the point corresponding to the given datum. The *x*-accessor may also be defined as a constant number rather than a function, if desired.
 
 <a name="quadtree_y" href="#quadtree_y">#</a> <i>quadtree</i>.<b>y</b>([<i>y</i>])
 
-If *y* is specified, sets the y-coordinate accessor and returns this quadtree factory. If *y* is not specified, returns the current *y*-coordinate accessor, which defaults to:
+If *y* is specified, sets the y-coordinate accessor and returns this quadtree generator. If *y* is not specified, returns the current *y*-coordinate accessor, which defaults to:
 
@@ -81,10 +65,53 @@ ```js
 
-For each point added to the quadtree, either during [initial construction](#_quadtree) or lazily [added](#root_add), the *y*-accessor is invoked, being passed the current datum `d` and index `i`. The *y*-accessor must then return a numeric value indicating the *y*-coordinate of the point corresponding to the given datum. The *y*-accessor may also be defined as a constant number rather than a function, if desired.
+For each point added to the quadtree, the *y*-accessor is invoked, being passed the current datum `d` and index `i`. The *y*-accessor must then return a numeric value indicating the *y*-coordinate of the point corresponding to the given datum. The *y*-accessor may also be defined as a constant number rather than a function, if desired.
 
 <a name="quadtree_extent" href="#quadtree_extent">#</a> <i>quadtree</i>.<b>extent</b>([<i>extent</i>])
 
-If *extent* is specified, sets the current extent and returns this quadtree factory. If *extent* is not specified, returns the current extent, which defaults to null. When the extent is null, an extent will be computed automatically by scanning the array of input data points passed to the [quadtree constructor](#_quadtree). Otherwise, the *extent* must be specified as a two-dimensional array [​[*x0*, *y0*], [​*x1*, *y1*]​], where *x0* and *y0* are the lower bounds of the extent, and *x1* and *y1* are the upper bounds of the extent. Setting an extent is required when constructing a quadtree lazily from an initially-empty set of nodes.
+If *extent* is specified, sets the current extent and returns this quadtree generator. The *extent* must be specified as a two-dimensional array [​[*x0*, *y0*], [​*x1*, *y1*]​], where *x0* and *y0* are the inclusive lower bounds of the extent and *x1* and *y1* are the exclusive upper bounds, or null. If *extent* is not specified, returns the current extent, which defaults to null. When the extent is not null, any point outside the extent is ignored when [constructing the quadtree](#_quadtree).
 
 <a name="quadtree_size" href="#quadtree_size">#</a> <i>quadtree</i>.<b>size</b>([<i>size</i>])
 
-An alias for [*quadtree*.extent](#quadtree_extent) where the minimum *x* and *y* of the extent are ⟨0,0⟩. Given a quadtree factory `q`, this is equivalent to `q.extent([[0, 0], size])`.
+If *size* is specified, sets the current extent and returns this quadtree generator. The *size* must be specified as a two-element array of numbers [[​*x1*, *y1*]​], where *x1* and *y1* are the exclusive upper bounds, or null; the lower bounds of the extent are implicitly ⟨0,0⟩. If *size* is not specified, returns the current upper bounds of the extent, which defaults to null. When the extent is not null, any point outside the extent is ignored when [constructing the quadtree](#_quadtree).
+
+This is a convenience method for setting the [extent](#quadtree_extent) where the lower bounds of the extent are ⟨0,0⟩. For example, this:
+
+```js
+quadtree.size([960, 500]);
+```
+
+Is equivalent to this:
+
+```js
+quadtree.extent([[0, 0], [960, 500]]);
+```
+
+### Quadtree Nodes
+
+Internal nodes of the quadtree are represented as sparse four-element arrays in left-to-right, top-to-bottom order:
+
+* `0` - the top-left quadrant
+* `1` - the top-right quadrant
+* `2` - the bottom-left quadrant
+* `3` - the bottom-right quadrant
+
+Leaf nodes of the quadtree are represent as objects with the following property:
+
+* `point` - a two-element array of numbers [*x*, *y*]
+
+If there are multiple coincident points in the quadtree, then *point*.next forms a linked list of coincident points.
+
+<a name="root_add" href="#root_add">#</a> <i>root</i>.<b>add</b>(<i>point</i>)
+
+Adds the specified new *point* to this quadtree and returns *root*. The point must be represented as a two-element array of numbers [*x*, *y*].
+
+<a name="root_find" href="#root_find">#</a> <i>root</i>.<b>find</b>(<i>x</i>, <i>y</i>)
+
+Given a point ⟨*x*,*y*⟩, returns the closest point in this quadtree.
+
+<a name="root_eachBefore" href="#root_eachBefore">#</a> <i>root</i>.<b>eachBefore</b>(<i>callback</i>)
+
+Visits each node in this quadtree in pre-order traversal, invoking the specified *callback* with arguments *node*, *x0*, *y0*, *x1*, *y1* for each node, where *node* is the node being visited, ⟨*x0*, *y0*⟩ are the lower bounds of the node, and ⟨*x1*, *y1*⟩ are the upper bounds. (Assuming that positive *x* is right and positive *y* is down, as is typically the case in Canvas and SVG, ⟨*x0*, *y0*⟩ is the top-left corner and ⟨*x1*, *y1*⟩ is the lower-right corner; however, the coordinate system is arbitrary, so more formally *x0* <= *x1* and *y0* <= *y1*.) Returns *root*. If the *callback* returns true for a given node, then the children of that node are not visited; otherwise, all child nodes are visited.
+
+<a name="root_eachAfter" href="#root_eachAfter">#</a> <i>root</i>.<b>eachAfter</b>(<i>callback</i>)
+
+Visits each node in this quadtree in post-order traversal, invoking the specified *callback* with arguments *node*, *x0*, *y0*, *x1*, *y1* for each node, where *node* is the node being visited, ⟨*x0*, *y0*⟩ are the lower bounds of the node, and ⟨*x1*, *y1*⟩ are the upper bounds. (Assuming that positive *x* is right and positive *y* is down, as is typically the case in Canvas and SVG, ⟨*x0*, *y0*⟩ is the top-left corner and ⟨*x1*, *y1*⟩ is the lower-right corner; however, the coordinate system is arbitrary, so more formally *x0* <= *x1* and *y0* <= *y1*.) Returns *root*.

src/quadtree.js

@@ -1,210 +0,41 @@
-function pointX(p) {
-  return p[0];
-}
+import constant from "./constant";
+import Root from "./root";
 
-function pointY(p) {
-  return p[1];
+function defaultX(d) {
+  return d[0];
 }
 
-function functor(x) {
-  return function() {
-    return x;
-  };
+function defaultY(d) {
+  return d[1];
 }
 
-function Node() {
-  this.x = null;
-  this.y = null;
-  this.leaf = true;
-  this.data = null;
-  this.nodes = [];
-}
-
-function visit(callback, node, x1, y1, x2, y2) {
-  if (!callback(node, x1, y1, x2, y2)) {
-    var sx = (x1 + x2) / 2,
-        sy = (y1 + y2) / 2,
-        children = node.nodes;
-    if (children[0]) visit(callback, children[0], x1, y1, sx, sy);
-    if (children[1]) visit(callback, children[1], sx, y1, x2, sy);
-    if (children[2]) visit(callback, children[2], x1, sy, sx, y2);
-    if (children[3]) visit(callback, children[3], sx, sy, x2, y2);
-  }
-}
-
-function find(root, x, y, x0, y0, x3, y3) {
-  var minDistance2 = Infinity,
-      closestNode;
-
-  (function findChild(node, x1, y1, x2, y2) {
-
-    // stop searching if this cell can’t contain a closer node
-    if (x1 > x3 || y1 > y3 || x2 < x0 || y2 < y0) return;
-
-    // visit this point
-    if (node.x != null) {
-      var dx = x - node.x,
-          dy = y - node.y,
-          distance2 = dx * dx + dy * dy;
-      if (distance2 < minDistance2) {
-        var distance = Math.sqrt(minDistance2 = distance2);
-        x0 = x - distance, y0 = y - distance;
-        x3 = x + distance, y3 = y + distance;
-        closestNode = node;
-      }
-    }
-
-    // bisect the current node
-    var children = node.nodes,
-        xm = (x1 + x2) / 2,
-        ym = (y1 + y2) / 2,
-        right = x >= xm,
-        below = y >= ym;
-
-    // visit closest cell first
-    for (var i = below << 1 | right, j = i + 4; i < j; ++i) {
-      if (node = children[i & 3]) switch (i & 3) {
-        case 0: findChild(node, x1, y1, xm, ym); break;
-        case 1: findChild(node, xm, y1, x2, ym); break;
-        case 2: findChild(node, x1, ym, xm, y2); break;
-        case 3: findChild(node, xm, ym, x2, y2); break;
-      }
-    }
-  })(root, x0, y0, x3, y3);
-
-  return closestNode && closestNode.data;
-}
-
 export default function() {
-  var x = pointX,
-      y = pointY,
-      x1,
-      x2,
-      y1,
-      y2;
+  var x = defaultX,
+      y = defaultY,
+      ox,
+      oy,
+      l;
 
   function quadtree(data) {
-    var d,
-        fx = typeof x === "function" ? x : functor(x),
-        fy = typeof y === "function" ? y : functor(y),
-        xs,
-        ys,
-        i,
-        n,
-        x1_,
-        y1_,
-        x2_,
-        y2_;
+    var d, i, n = data.length, p,
+        xi, yi,
+        x0 = -Infinity,
+        y0 = -Infinity,
+        x1 = Infinity,
+        y1 = Infinity,
+        root = new Root;
 
-    if (!data) data = [];
-
-    if (x1 != null) {
-      x1_ = x1, y1_ = y1, x2_ = x2, y2_ = y2;
-    } else {
-      // Compute bounds, and cache points temporarily.
-      x2_ = y2_ = -(x1_ = y1_ = Infinity);
-      xs = [], ys = [];
-      n = data.length;
-      for (i = 0; i < n; ++i) {
-        var x_ = +fx(d = data[i], i, data),
-            y_ = +fy(d, i, data);
-        if (x_ < x1_) x1_ = x_;
-        if (y_ < y1_) y1_ = y_;
-        if (x_ > x2_) x2_ = x_;
-        if (y_ > y2_) y2_ = y_;
-        xs.push(x_);
-        ys.push(y_);
-      }
+    if (ox != null) {
+      root._root = new Array(4);
+      root._x0 = x0 = ox, root._x1 = x1 = ox + l;
+      root._y0 = y0 = oy, root._y1 = y1 = oy + l;
     }
 
-    // Squarify the bounds.
-    var dx = x2_ - x1_,
-        dy = y2_ - y1_;
-    if (isFinite(dx) && isFinite(dy)) {
-      if (dx > dy) y2_ = y1_ + dx;
-      else x2_ = x1_ + dy;
+    for (i = 0; i < n; ++i) {
+      xi = +x(d = data[i], i, data), yi = +y(d, i, data);
+      if (x0 > xi || xi >= x1 || y0 > yi || yi >= y1) continue;
+      p = [xi, yi], p.data = d, p.index = i;
+      root.add(p);
     }
 
-    // Recursively inserts the specified point at the node or one of its
-    // descendants. The bounds are defined by [x1, x2] and [y1, y2].
-    function insert(node, d, x, y, x1, y1, x2, y2) {
-      if (isNaN(x) || isNaN(y)) return; // ignore invalid points
-      if (node.leaf) {
-        var nx = node.x,
-            ny = node.y;
-        if (nx != null) {
-          // If the point at this leaf node is at the same position as the new
-          // point we are adding, we leave the point associated with the
-          // internal node while adding the new point to a child node. This
-          // avoids infinite recursion.
-          if ((Math.abs(nx - x) + Math.abs(ny - y)) < .01) {
-            insertChild(node, d, x, y, x1, y1, x2, y2);
-          } else {
-            var d0 = node.data;
-            node.x = node.y = node.data = null;
-            insertChild(node, d0, nx, ny, x1, y1, x2, y2);
-            insertChild(node, d, x, y, x1, y1, x2, y2);
-          }
-        } else {
-          node.x = x, node.y = y, node.data = d;
-        }
-      } else {
-        insertChild(node, d, x, y, x1, y1, x2, y2);
-      }
-    }
-
-    // Recursively inserts the specified point [x, y] into a descendant of node
-    // n. The bounds are defined by [x1, x2] and [y1, y2].
-    function insertChild(node, d, x, y, x1, y1, x2, y2) {
-      // Compute the split point, and the quadrant in which to insert the point.
-      var xm = (x1 + x2) / 2,
-          ym = (y1 + y2) / 2,
-          right = x >= xm,
-          below = y >= ym,
-          i = below << 1 | right;
-
-      // Recursively insert into the child node.
-      node.leaf = false;
-      node = node.nodes[i] || (node.nodes[i] = new Node);
-
-      // Update the bounds as we recurse.
-      if (right) x1 = xm; else x2 = xm;
-      if (below) y1 = ym; else y2 = ym;
-      insert(node, d, x, y, x1, y1, x2, y2);
-    }
-
-    var root = new Node;
-
-    root.add = function(d) {
-      insert(root, d, +fx(d, ++i), +fy(d, i), x1_, y1_, x2_, y2_);
-      return root;
-    };
-
-    root.visit = function(callback) {
-      visit(callback, root, x1_, y1_, x2_, y2_);
-      return root;
-    };
-
-    // Find the closest point to the specified point.
-    // TODO allow the initial search extent to be specified?
-    // TODO allow the initial minimum distance to be specified?
-    // TODO allow searching below any node?
-    root.find = function(x, y) {
-      return find(root, x, y, x1_, y1_, x2_, y2_);
-    };
-
-    // Insert all points.
-    i = -1;
-    if (x1 == null) {
-      while (++i < n) {
-        insert(root, data[i], xs[i], ys[i], x1_, y1_, x2_, y2_);
-      }
-      --i; // index of last insertion
-    } else {
-      data.forEach(root.add);
-    }
-
-    // Discard captured fields.
-    xs = ys = data = d = null;
-
     return root;
@@ -214,21 +45,15 @@ }
   quadtree.x = function(_) {
-    return arguments.length ? (x = _, quadtree) : x;
+    return arguments.length ? (x = typeof _ === "function" ? _ : constant(+_), quadtree) : x;
   };
 
   quadtree.y = function(_) {
-    return arguments.length ? (y = _, quadtree) : y;
+    return arguments.length ? (y = typeof _ === "function" ? _ : constant(+_), quadtree) : y;
   };
 
   quadtree.extent = function(_) {
-    if (!arguments.length) return x1 == null ? null : [[x1, y1], [x2, y2]];
-    if (_ == null) x1 = y1 = x2 = y2 = null;
-    else x1 = +_[0][0], y1 = +_[0][1], x2 = +_[1][0], y2 = +_[1][1];
-    return quadtree;
+    return arguments.length ? (_ == null ? ox = oy = l = null : (ox = +_[0][0], oy = +_[0][1], l = Math.max(_[1][0] - ox, _[1][1] - oy)), quadtree) : ox == null ? null : [[ox, oy], [ox + l, oy + l]];
   };
 
   quadtree.size = function(_) {
-    if (!arguments.length) return x1 == null ? null : [x2 - x1, y2 - y1];
-    if (_ == null) x1 = y1 = x2 = y2 = null;
-    else x1 = y1 = 0, x2 = +_[0], y2 = +_[1];
-    return quadtree;
+    return arguments.length ? (_ == null ? ox = oy = l = null : (ox = oy = 0, l = Math.max(+_[0], +_[1])), quadtree) : ox == null ? null : [l, l];
   };
@@ -235,0 +60,0 @@

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

32047

increased by20.26%

Number of package files

18

increased by80%

Lines of code

467

increased by11.99%

Number of lines in readme file

114

increased by31.03%

Worsened metrics

Number of medium supply chain risk alerts

1

increased byInfinity%

No dependency changes