// Copyright 2006 The Closure Library Authors. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS-IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

/**
 * @fileoverview A utility class for representing two-dimensional positions.
 *
 */

var Coordinate = new Class.create({
	initialize: function(opt_x, opt_y) {
		this.x = opt_x ? opt_x : 0;
		this.y = opt_y ? opt_y : 0;
	},
	clone: function() {
		return new Coordinate(this.x, this.y);
	},
	equals: function(a, b) {
	  if (a == b) {
	    return true;
	  }
	  if (!a || !b) {
	    return false;
	  }
	  return a.x == b.x && a.y == b.y;
	},
	distance: function(a, b) {
	  var dx = a.x - b.x;
	  var dy = a.y - b.y;
	  return Math.sqrt(dx * dx + dy * dy);
	},
	squaredDistance: function(a, b) {
	  var dx = a.x - b.x;
	  var dy = a.y - b.y;
	  return dx * dx + dy * dy;
	},
	difference: function(a, b) {
	  return new Coordinate(a.x - b.x, a.y - b.y);
	},
	sum: function(a, b) {
	  return new Coordinate(a.x + b.x, a.y + b.y);
	}
});


// Copyright 2008 The Closure Library Authors. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS-IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

/**
 * @fileoverview Datastructure: A point Quad Tree for representing 2D data. Each
 * region has the same ratio as the bounds for the tree.
 *
 * The implementation currently requires pre-determined bounds for data as it
 * can not rebalance itself to that degree.
 *
 *
 * @see ../demos/quadtree.html
 */

var QuadTree = new Class.create({
	initialize: function(minX, minY, maxX, maxY) {
		this.count_ = 0;
		this.root_ = new QuadTree.Node(minX, minY, maxX - minX, maxY - minY);
	},
	getRootNode: function() {
		return this.root_;
	},
	set: function(x, y, value) {
		var root = this.root_;
		if (x < root.x || y < root.y || x > root.x + root.w || y > root.y + root.h) {
	    throw Error('Out of bounds : (' + x + ', ' + y + ')');
	  }
	  if (this.insert_(root, new QuadTree.Point(x, y, value))) {
	    this.count_++;
	  }
	},
	get: function(x, y, opt_default) {
	  var node = this.find_(this.root_, x, y);
	  return node ? node.point.value : opt_default;
	},
	remove: function(x, y) {
	  var node = this.find_(this.root_, x, y);
	  if (node) {
	    var value = node.point.value;
	    node.point = null;
	    node.nodeType = QuadTree.NodeType.EMPTY;
	    this.balance_(node);
	    this.count_--;
	    return value;
	  } else {
	    return null;
	  }
	},
	contains: function(x, y) {
	  return this.get(x, y) != null;
	},
	isEmpty: function() {
	  return this.root_.nodeType == QuadTree.NodeType.EMPTY;
	},
	getCount: function() {
	  return this.count_;
	},
	clear: function() {
	  this.root_.nw = this.root_.ne = this.root_.sw = this.root_.se = null;
	  this.root_.nodeType = QuadTree.NodeType.EMPTY;
	  this.root_.point = null;
	  this.count_ = 0;
	},
	getKeys: function() {
	  var arr = [];
	  this.traverse_(this.root_, function(node) {
	    arr.push(new Coordinate(node.point.x, node.point.y));
	  });
	  return arr;
	},
	getValues: function() {
	  var arr = [];
	  this.traverse_(this.root_, function(node) {
	    // Must have a point because it's a leaf.
	    arr.push(node.point.value);
	  });
	  return arr;
	},
	getKeysFlat: function() {
		var arr = [];
	  this.traverse_(this.root_, function(node) {
	    arr.push([node.point.x, node.point.y]);
	  });
	  return arr;
	},
	clone: function() {
	  var x1 = this.root_.x;
	  var y1 = this.root_.y;
	  var x2 = x1 + this.root_.w;
	  var y2 = y1 + this.root_.h;
	  var clone = new QuadTree(x1, y1, x2, y2);
	  // This is inefficient as the clone needs to recalculate the structure of the
	  // tree, even though we know it already.  But this is easier and can be
	  // optimized when/if needed.
	  this.traverse_(this.root_, function(node) {
	    clone.set(node.point.x, node.point.y, node.point.value);
	  });
	  return clone;
	},
	forEach: function(fn, opt_obj) {
	  this.traverse_(this.root_, function(node) {
	    var coord = new Coordinate(node.point.x, node.point.y);
	    fn.call(opt_obj, node.point.value, coord, this);
	  });
	},
	traverse_: function(node, fn) {
	  switch (node.nodeType) {
	    case QuadTree.NodeType.LEAF:
	      fn.call(this, node);
	      break;
	
	    case QuadTree.NodeType.POINTER:
	      this.traverse_(node.ne, fn);
	      this.traverse_(node.se, fn);
	      this.traverse_(node.sw, fn);
	      this.traverse_(node.nw, fn);
	      break;
	  }
	},
	find_: function(node, x, y) {
	  switch (node.nodeType) {
	    case QuadTree.NodeType.EMPTY:
	      return null;
	
	    case QuadTree.NodeType.LEAF:
	      return node.point.x == x && node.point.y == y ? node : null;
	
	    case QuadTree.NodeType.POINTER:
	      return this.find_(this.getQuadrantForPoint_(node, x, y), x, y);
	
	    default:
	      throw Error('Invalid nodeType');
	  }
	},
	insert_: function(parent, point) {
	  switch (parent.nodeType) {
	    case QuadTree.NodeType.EMPTY:
	      this.setPointForNode_(parent, point);
	      return true;
	
	    case QuadTree.NodeType.LEAF:
	      if (parent.point.x == point.x && parent.point.y == point.y) {
	        this.setPointForNode_(parent, point);
	        return false;
	      } else {
	        this.split_(parent);
	        return this.insert_(parent, point);
	      }
	
	    case QuadTree.NodeType.POINTER:
	      return this.insert_(
	          this.getQuadrantForPoint_(parent, point.x, point.y), point);
	
	    default:
	      throw Error('Invalid nodeType in parent');
	  }
	},
	split_: function(node) {
	  var oldPoint = node.point;
	  node.point = null;
	
	  node.nodeType = QuadTree.NodeType.POINTER;
	
	  var x = node.x;
	  var y = node.y;
	  var hw = node.w / 2;
	  var hh = node.h / 2;
	
	  node.nw = new QuadTree.Node(x, y, hw, hh, node);
	  node.ne = new QuadTree.Node(x + hw, y, hw, hh, node);
	  node.sw = new QuadTree.Node(x, y + hh, hw, hh, node);
	  node.se = new QuadTree.Node(x + hw, y + hh, hw, hh, node);
	
	  this.insert_(node, oldPoint);
	},
	balance_: function(node) {
	  switch (node.nodeType) {
	    case QuadTree.NodeType.EMPTY:
	    case QuadTree.NodeType.LEAF:
	      if (node.parent) {
	        this.balance_(node.parent);
	      }
	      break;
	
	    case QuadTree.NodeType.POINTER:
	      var nw = node.nw, ne = node.ne, sw = node.sw, se = node.se;
	      var firstLeaf = null;
	
	      // Look for the first non-empty child, if there is more than one then we
	      // break as this node can't be balanced.
	      if (nw.nodeType != QuadTree.NodeType.EMPTY) {
	        firstLeaf = nw;
	      }
	      if (ne.nodeType != QuadTree.NodeType.EMPTY) {
	        if (firstLeaf) {
	          break;
	        }
	        firstLeaf = ne;
	      }
	      if (sw.nodeType != QuadTree.NodeType.EMPTY) {
	        if (firstLeaf) {
	          break;
	        }
	        firstLeaf = sw;
	      }
	      if (se.nodeType != QuadTree.NodeType.EMPTY) {
	        if (firstLeaf) {
	          break;
	        }
	        firstLeaf = se;
	      }
	
	      if (!firstLeaf) {
	        // All child nodes are empty: so make this node empty.
	        node.nodeType = QuadTree.NodeType.EMPTY;
	        node.nw = node.ne = node.sw = node.se = null;
	
	      } else if (firstLeaf.nodeType == QuadTree.NodeType.POINTER) {
	        // Only child was a pointer, therefore we can't rebalance.
	        break;
	
	      } else {
	        // Only child was a leaf: so update node's point and make it a leaf.
	        node.nodeType = QuadTree.NodeType.LEAF;
	        node.nw = node.ne = node.sw = node.se = null;
	        node.point = firstLeaf.point;
	      }
	
	      // Try and balance the parent as well.
	      if (node.parent) {
	        this.balance_(node.parent);
	      }
	
	      break;
	  }
	},
	getQuadrantForPoint_: function(parent, x, y) {
	  var mx = parent.x + parent.w / 2;
	  var my = parent.y + parent.h / 2;
	  if (x < mx) {
	    return y < my ? parent.nw : parent.sw;
	  } else {
	    return y < my ? parent.ne : parent.se;
	  }
	},
	setPointForNode_: function(node, point) {
	  if (node.nodeType == QuadTree.NodeType.POINTER) {
	    throw Error('Can not set point for node of type POINTER');
	  }
	  node.nodeType = QuadTree.NodeType.LEAF;
	  node.point = point;
	}
});

QuadTree.NodeType = {
  EMPTY: 0,
  LEAF: 1,
  POINTER: 2
};

QuadTree.Node = new Class.create({
	initialize: function(x, y, w, h, opt_parent) {
		this.x = x;
		this.y = y;
		this.w = w;
		this.h = h;
		this.parent = opt_parent || null;
	},
	nodeType: QuadTree.NodeType.EMPTY,
	nw: null,
	ne: null,
	sw: null,
	se: null,
	point: null

});

QuadTree.Point = new Class.create({
	initialize: function(x, y, opt_value) {
		this.x = x;
		this.y = y;
		this.value = opt_value ? opt_value : null;
	}
});