/// see /// * Quadtree at wikipedia /// * JavaScript QuadTree Implementation /// * Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space see Quadtree at wikipedia JavaScript QuadTree Implementation * Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space TODO add testcase

class QuadTreeXYAabb{
 /// (x, y, width, height) bounds of the QuadTree
 final _dim = new Aabb3();
 final _splitPoint = new Vector3.zero();

 /// Whether the QuadTree will contain points (true), or items with bounds (width / height)(false).
 final int maxDepth;
 /// The maximum number of children that a node can contain before it is split into sub-nodes.
 final int maxChildren;

 //interleave data [AAbb3, obj, AAbb3, obj, ....]
 final _children = new List();
 //TODO optimize to reuse nodes (recycle, pool)
 final _nodes = new List<QuadTreeXYAabb>(4);
 var _isLeaf = true;

 QuadTreeXYAabb(x, y, w, h, [this.maxDepth = 4, int maxChildren = 4]): this.maxChildren = maxChildren << 1 {
   _dim.min.setValues(x, y, 0.0);
   _dim.max.setValues(x + w, y + h, 0.0);
   _splitPoint.setFrom(_dim.min).add(_dim.max).scale(0.5);
 }

 get isLeaf => _isLeaf;
 get nbItems => (_children.length >> 1) + ((_isLeaf)? 0 : (_nodes[0].nbItems + _nodes[1].nbItems + _nodes[2].nbItems + _nodes[3].nbItems));
 get nbItemsL0 => _children.length >> 1;

 /// use [reset] to reset the instance instead of create a new one with same bounds.
 reset() {
   _children.clear();
   _isLeaf = true;
 }

 bool insert(Aabb3 v, obj) {
   var r = findRegion(v);
   if (r != null) {
     r._insert(v, obj);
//      if (this.maxDepth == 10) {
//        obj.ps.color[obj.i] = (r.maxDepth == 10)? 0x0000ffff : 0x00ff00ff;
//      }
   }
   return (r != null);
 }

 QuadTreeXYAabb findRegion(Aabb3 v) {
   if (v.min.x < _dim.min.x || v.max.x > _dim.max.x || (v.min.y < _dim.min.y) || v.max.y > _dim.max.y) {
     return null;
   }
   return _findRegion(v);
 }

 _findRegion(Aabb3 v) {
   var r = null;
   if (!_isLeaf) {
     var n = (v.min.y <= _splitPoint.y)?  0 : 2;
     n = (v.min.x <= _splitPoint.x)?  n : n + 1;
     r = _nodes[n].findRegion(v);
   }
   return (r == null) ? this : r;
 }

 _insert(Aabb3 v, obj) {
   if (_isLeaf && maxDepth > 0 && _children.length >= maxChildren) {
     _split();
     var data = new List.from(_children, growable: false); // TODO use a static arrays
     _children.clear();
     for (var i = 0; i < data.length; i +=2) {
       insert(data[i], data[i+1]);
     }
     insert(v, obj);
   } else {
     _children.add(v);
     _children.add(obj);
   }
 }

 _split() {
   if(_nodes[0] == null) {
     var x = _dim.min.x;
     var y = _dim.min.y;
     var w2 = _splitPoint.x - _dim.min.x;
     var h2 = _splitPoint.y - _dim.min.y;
     var m = maxChildren >> 1;
     var d = maxDepth - 1;
     _nodes[0] = new QuadTreeXYAabb(x     , y     , w2, h2, d, m);
     _nodes[1] = new QuadTreeXYAabb(x + w2, y     , w2, h2, d, m);
     _nodes[2] = new QuadTreeXYAabb(x     , y + h2, w2, h2, d, m);
     _nodes[3] = new QuadTreeXYAabb(x + w2, y + h2, w2, h2, d, m);
   } else {
     _nodes[0].reset();
     _nodes[1].reset();
     _nodes[2].reset();
     _nodes[3].reset();
   }
   _isLeaf = false;
 }

 retrieve(Aabb3 v, List out) {
   var reg = findRegion(v);
   if (reg !=null && reg != this) {
     reg.retrieve(out, v);
   }
   for (var i = 1; i < _children.length; i +=2) {
     out.add(_children[i]);
   }
   return out;
 }

 scan(Function f) {
   for (var i = 1; i < _children.length; i +=2) {
     var a1 = _children[i];
     for (var j = i + 2; j < _children.length; j +=2) {
       f(a1, _children[j]);
     }
     _scanVsNodes(f, a1);
   }
   if (!_isLeaf) {
     for (var i = 0; i < 4; ++i) {
       _nodes[i].scan(f);
     }
   }
 }

 _scanVsNodes(Function f, a1) {
   if (_isLeaf) return;

   for (var i = 0; i < 4; ++i) {
     var n = _nodes[i];
     n._scanVsChildren(f, a1);
     n._scanVsNodes(f, a1);
   }
 }

 _scanVsChildren(Function f, a1) {
   for (var i = 1; i < _children.length; i +=2) {
     f(a1, _children[i]);
   }
 }

}