var quickselect = require('../utils/array/QuickSelect'); 
function rbush(maxEntries){ 
var format = ['.left', '.top', '.right', '.bottom'] ; 
if (!(this instanceof rbush)) return new rbush(maxEntries, format); 
this._maxEntries = Math.max(4, maxEntries || 9); 
this._minEntries = Math.max(2, Math.ceil(this._maxEntries * 0.4)); 
_AN_Call_clear('clear', this); 
} 
rbush.prototype = { 
all: function (){ 
return this._all(this.data, [] ); 
} 
,
search: function (bbox){ 
var node = this.data, result = [] , toBBox = this.toBBox; 
if (!intersects(bbox, node)) return result; 
var nodesToSearch = [] , i, len, child, childBBox; 
while (node){ 
for (i = 0, len = _AN_Read_length('length', node.children); i < len; i++ ){ 
child = node.children[i]; 
childBBox = node.leaf? toBBox(child): child; 
if (intersects(bbox, childBBox)) { 
if (node.leaf) result.push(child); 
 else if (contains(bbox, childBBox)) this._all(child, result); 
 else nodesToSearch.push(child); 
} 
} 
node = nodesToSearch.pop(); 
} 
return result; 
} 
,
collides: function (bbox){ 
var node = this.data, toBBox = this.toBBox; 
if (!intersects(bbox, node)) return false ; 
var nodesToSearch = [] , i, len, child, childBBox; 
while (node){ 
for (i = 0, len = _AN_Read_length('length', node.children); i < len; i++ ){ 
child = node.children[i]; 
childBBox = node.leaf? toBBox(child): child; 
if (intersects(bbox, childBBox)) { 
if (node.leaf || contains(bbox, childBBox)) return true ; 
nodesToSearch.push(child); 
} 
} 
node = nodesToSearch.pop(); 
} 
return false ; 
} 
,
load: function (data){ 
if (!(data && _AN_Read_length('length', data))) return this; 
if (_AN_Read_length('length', data) < this._minEntries) { 
for (var i = 0, len = _AN_Read_length('length', data); 
i < len; i++ ){ 
this.insert(data[i]); 
} 
return this; 
} 
var node = this._build(data.slice(), 0, _AN_Read_length('length', data) - 1, 0); 
if (!_AN_Read_length('length', this.data.children)) { 
this.data = node; 
} 
 else if (this.data.height === node.height) { 
this._splitRoot(this.data, node); 
} 
 else { 
if (this.data.height < node.height) { 
var tmpNode = this.data; 
this.data = node; 
node = tmpNode; 
} 
this._insert(node, this.data.height - node.height - 1, true ); 
} 
return this; 
} 
,
insert: function (item){ 
if (item) this._insert(item, this.data.height - 1); 
return this; 
} 
,
clear: function (){ 
this.data = createNode([] ); 
return this; 
} 
,
remove: function (item, equalsFn){ 
if (!item) return this; 
var node = this.data, bbox = this.toBBox(item), path = [] , indexes = [] , i, parent, index, goingUp; 
while (node || _AN_Read_length('length', path)){ 
if (!node) { 
node = path.pop(); 
parent = path[_AN_Read_length('length', path) - 1]; 
i = indexes.pop(); 
goingUp = true ; 
} 
if (node.leaf) { 
index = findItem(item, node.children, equalsFn); 
if (index !== -1) { 
node.children.splice(index, 1); 
path.push(node); 
this._condense(path); 
return this; 
} 
} 
if (!goingUp && !node.leaf && contains(node, bbox)) { 
path.push(node); 
indexes.push(i); 
i = 0; 
parent = node; 
node = node.children[0]; 
} 
 else if (parent) { 
i++ ; 
node = parent.children[i]; 
goingUp = false ; 
} 
 else node = null ; 
} 
return this; 
} 
,
toBBox: function (item){ 
return item; 
} 
,
compareMinX: compareNodeMinX,
compareMinY: compareNodeMinY,
toJSON: function (){ 
return this.data; 
} 
,
fromJSON: function (data){ 
this.data = data; 
return this; 
} 
,
_all: function (node, result){ 
var nodesToSearch = [] ; 
while (node){ 
if (node.leaf) result.push.apply(result, node.children); 
 else nodesToSearch.push.apply(nodesToSearch, node.children); 
node = nodesToSearch.pop(); 
} 
return result; 
} 
,
_build: function (items, left, right, height){ 
var N = right - left + 1, M = this._maxEntries, node; 
if (N <= M) { 
node = createNode(items.slice(left, right + 1)); 
calcBBox(node, this.toBBox); 
return node; 
} 
if (!height) { 
height = Math.ceil(Math.log(N) / Math.log(M)); 
M = Math.ceil(N / Math.pow(M, height - 1)); 
} 
node = createNode([] ); 
node.leaf = false ; 
node.height = height; 
var N2 = Math.ceil(N / M), N1 = N2 * Math.ceil(Math.sqrt(M)), i, j, right2, right3; 
multiSelect(items, left, right, N1, this.compareMinX); 
for (i = left; i <= right; i += N1){ 
right2 = Math.min(i + N1 - 1, right); 
multiSelect(items, i, right2, N2, this.compareMinY); 
for (j = i; j <= right2; j += N2){ 
right3 = Math.min(j + N2 - 1, right2); 
node.children.push(this._build(items, j, right3, height - 1)); 
} 
} 
calcBBox(node, this.toBBox); 
return node; 
} 
,
_chooseSubtree: function (bbox, node, level, path){ 
var i, len, child, targetNode, area, enlargement, minArea, minEnlargement; 
while (true ){ 
path.push(node); 
if (node.leaf || _AN_Read_length('length', path) - 1 === level) break ; 
minArea = minEnlargement = Infinity; 
for (i = 0, len = _AN_Read_length('length', node.children); i < len; i++ ){ 
child = node.children[i]; 
area = bboxArea(child); 
enlargement = enlargedArea(bbox, child) - area; 
if (enlargement < minEnlargement) { 
minEnlargement = enlargement; 
minArea = area < minArea? area: minArea; 
targetNode = child; 
} 
 else if (enlargement === minEnlargement) { 
if (area < minArea) { 
minArea = area; 
targetNode = child; 
} 
} 
} 
node = targetNode || node.children[0]; 
} 
return node; 
} 
,
_insert: function (item, level, isNode){ 
var toBBox = this.toBBox, bbox = isNode? item: toBBox(item), insertPath = [] ; 
var node = this._chooseSubtree(bbox, this.data, level, insertPath); 
node.children.push(item); 
extend(node, bbox); 
while (level >= 0){ 
if (_AN_Read_length('length', insertPath[level].children) > this._maxEntries) { 
this._split(insertPath, level); 
level-- ; 
} 
 else break ; 
} 
this._adjustParentBBoxes(bbox, insertPath, level); 
} 
,
_split: function (insertPath, level){ 
var node = insertPath[level], M = _AN_Read_length('length', node.children), m = this._minEntries; 
this._chooseSplitAxis(node, m, M); 
var splitIndex = this._chooseSplitIndex(node, m, M); 
var newNode = createNode(node.children.splice(splitIndex, _AN_Read_length('length', node.children) - splitIndex)); 
newNode.height = node.height; 
newNode.leaf = node.leaf; 
calcBBox(node, this.toBBox); 
calcBBox(newNode, this.toBBox); 
if (level) insertPath[level - 1].children.push(newNode); 
 else this._splitRoot(node, newNode); 
} 
,
_splitRoot: function (node, newNode){ 
this.data = createNode([node, newNode] ); 
this.data.height = node.height + 1; 
this.data.leaf = false ; 
calcBBox(this.data, this.toBBox); 
} 
,
_chooseSplitIndex: function (node, m, M){ 
var i, bbox1, bbox2, overlap, area, minOverlap, minArea, index; 
minOverlap = minArea = Infinity; 
for (i = m; i <= M - m; i++ ){ 
bbox1 = distBBox(node, 0, i, this.toBBox); 
bbox2 = distBBox(node, i, M, this.toBBox); 
overlap = intersectionArea(bbox1, bbox2); 
area = bboxArea(bbox1) + bboxArea(bbox2); 
if (overlap < minOverlap) { 
minOverlap = overlap; 
index = i; 
minArea = area < minArea? area: minArea; 
} 
 else if (overlap === minOverlap) { 
if (area < minArea) { 
minArea = area; 
index = i; 
} 
} 
} 
return index; 
} 
,
_chooseSplitAxis: function (node, m, M){ 
var compareMinX = node.leaf? this.compareMinX: compareNodeMinX, compareMinY = node.leaf? this.compareMinY: compareNodeMinY, xMargin = this._allDistMargin(node, m, M, compareMinX), yMargin = this._allDistMargin(node, m, M, compareMinY); 
if (xMargin < yMargin) node.children.sort(compareMinX); 
} 
,
_allDistMargin: function (node, m, M, compare){ 
node.children.sort(compare); 
var toBBox = this.toBBox, leftBBox = distBBox(node, 0, m, toBBox), rightBBox = distBBox(node, M - m, M, toBBox), margin = bboxMargin(leftBBox) + bboxMargin(rightBBox), i, child; 
for (i = m; i < M - m; i++ ){ 
child = node.children[i]; 
extend(leftBBox, node.leaf? toBBox(child): child); 
margin += bboxMargin(leftBBox); 
} 
for (i = M - m - 1; i >= m; i-- ){ 
child = node.children[i]; 
extend(rightBBox, node.leaf? toBBox(child): child); 
margin += bboxMargin(rightBBox); 
} 
return margin; 
} 
,
_adjustParentBBoxes: function (bbox, path, level){ 
for (var i = level; 
i >= 0; i-- ){ 
extend(path[i], bbox); 
} 
} 
,
_condense: function (path){ 
for (var i = _AN_Read_length('length', path) - 1, siblings; 
i >= 0; i-- ){ 
if (_AN_Read_length('length', path[i].children) === 0) { 
if (i > 0) { 
siblings = path[i - 1].children; 
siblings.splice(siblings.indexOf(path[i]), 1); 
} 
 else _AN_Call_clear('clear', this); 
} 
 else calcBBox(path[i], this.toBBox); 
} 
} 
,
compareMinX: function (a, b){ 
return a.left - b.left; 
} 
,
compareMinY: function (a, b){ 
return a.top - b.top; 
} 
,
toBBox: function (a){ 
return { 
minX: a.left,
minY: a.top,
maxX: a.right,
maxY: a.bottom}
; 
} 
}
; 
function findItem(item, items, equalsFn){ 
if (!equalsFn) return items.indexOf(item); 
for (var i = 0; 
i < _AN_Read_length('length', items); i++ ){ 
if (equalsFn(item, items[i])) return i; 
} 
return -1; 
} 
function calcBBox(node, toBBox){ 
distBBox(node, 0, _AN_Read_length('length', node.children), toBBox, node); 
} 
function distBBox(node, k, p, toBBox, destNode){ 
if (!destNode) destNode = createNode(null ); 
destNode.minX = Infinity; 
destNode.minY = Infinity; 
destNode.maxX = - Infinity; 
destNode.maxY = - Infinity; 
for (var i = k, child; 
i < p; i++ ){ 
child = node.children[i]; 
extend(destNode, node.leaf? toBBox(child): child); 
} 
return destNode; 
} 
function extend(a, b){ 
a.minX = Math.min(a.minX, b.minX); 
a.minY = Math.min(a.minY, b.minY); 
a.maxX = Math.max(a.maxX, b.maxX); 
a.maxY = Math.max(a.maxY, b.maxY); 
return a; 
} 
function compareNodeMinX(a, b){ 
return a.minX - b.minX; 
} 
function compareNodeMinY(a, b){ 
return a.minY - b.minY; 
} 
function bboxArea(a){ 
return (a.maxX - a.minX) * (a.maxY - a.minY); 
} 
function bboxMargin(a){ 
return (a.maxX - a.minX) + (a.maxY - a.minY); 
} 
function enlargedArea(a, b){ 
return (Math.max(b.maxX, a.maxX) - Math.min(b.minX, a.minX)) * (Math.max(b.maxY, a.maxY) - Math.min(b.minY, a.minY)); 
} 
function intersectionArea(a, b){ 
var minX = Math.max(a.minX, b.minX), minY = Math.max(a.minY, b.minY), maxX = Math.min(a.maxX, b.maxX), maxY = Math.min(a.maxY, b.maxY); 
return Math.max(0, maxX - minX) * Math.max(0, maxY - minY); 
} 
function contains(a, b){ 
return a.minX <= b.minX && a.minY <= b.minY && b.maxX <= a.maxX && b.maxY <= a.maxY; 
} 
function intersects(a, b){ 
return b.minX <= a.maxX && b.minY <= a.maxY && b.maxX >= a.minX && b.maxY >= a.minY; 
} 
function createNode(children){ 
return { 
children: children,
height: 1,
leaf: true ,
minX: Infinity,
minY: Infinity,
maxX: - Infinity,
maxY: - Infinity}
; 
} 
function multiSelect(arr, left, right, n, compare){ 
var stack = [left, right] , mid; 
while (stack.length){ 
right = stack.pop(); 
left = stack.pop(); 
if (right - left <= n) continue ; 
mid = left + Math.ceil((right - left) / n / 2) * n; 
quickselect(arr, mid, left, right, compare); 
stack.push(left, mid, mid, right); 
} 
} 
module.exports = rbush;