package  
{
	import flash.display.Sprite;
	/**
	 * A balanced binary search tree that stores/represents the beach line.
	 * @author Chad Nelson
	 */
	public class BeachLine extends Sprite
	{	
		public static var directrix : Number = Number.POSITIVE_INFINITY;
		public var arcs : Vector.<Parabola> = new Vector.<Parabola>();
		
		public function BeachLine() {}
		
		/**
		 * Initializes the beach line with a node
		 */
		public function initialize(first:VoronoiSite):void {
			arcs.push(new Parabola(first));
			
			// Add graphics to display list
			addChild(arcs[0]);
		}
		
		/**
		 * Replace the leaf of the beachline that represents the arc with a subtree
		 * having three leaves.  The middle leaf stores the new site point, and the other 
		 * two leaves are splitting the found arc into a left and right portion.
		 * @param	site - location of new point
		 * @param	arc - the arc above the site event
		 * @return  (Parabola) the newly created arc
		 */
		public function split(site:VoronoiSite, arc:Parabola):Parabola {
			var left : Parabola;
			var center : Parabola;
			var right : Parabola;
			
			left = new Parabola(arc.site);
			right = new Parabola(arc.site);
			center = new Parabola(site);
			
			// Adjust left-right relationships
			left.left = arc.left;
			left.right = center;
			center.left = left;
			center.right = right;
			right.left = center;
			right.right = arc.right;
			if (arc.right != null) 
				arc.right.left = right;
			if (arc.left != null)
				arc.left.right = left;
			
			// Adjust edge / breakpoint links
			if (arc.edge_right != null) {
				right.edge_right = arc.edge_right;
				if (arc.edge_right.breakpoint1 == arc)
					arc.edge_right.breakpoint1 = right;
				else
					arc.edge_right.breakpoint2 = right;
			}
			
			// Adjust datastructure
			arcs.splice(arcs.indexOf(arc), 1, left, center, right);
			
			// Adjust Graphics
			removeChild(arc);
			addChild(left);
			addChild(center);
			addChild(right);
			
			return center;
		}
		
		/**
		 * Destroys the center Parabola and updates the left and right breakpoint tuples
		 * @param	left
		 * @param	center
		 * @param	right
		 */
		public function destroy(left:Parabola, center:Parabola, right:Parabola):void {
			// Remove center arc
			if (center.parent == this)
				removeChild(center);
			arcs.splice(arcs.indexOf(center), 1);
			
			// Adjust left-right relationships
			left.right = center.right;
			right.left = center.left;
		}
		
		/**
		 * Locates the arc directly above the site
		 * @param	site
		 * @return  the arc above the site (Parabola)
		 */
		public function locateArc(site:VoronoiSite):Parabola {
			var r : uint = arcs.length - 1;
			var l : uint = 0;
			var current : uint;
			var current_node : Parabola;
			
			while (l != r) {
				current = Math.floor((l + r) / 2);
				current_node = arcs[current];
				
				if (current_node.getRightBreakpoint() < site.x) {
					// If site is to the right of this arc
					l = Math.ceil((l + r) / 2);
				} else if (current_node.getLeftBreakpoint() > site.x) {
					// If site is to the left of this arc
					r = current;
				} else {
					r = current;
					l = current;
				}
			}
			return arcs[(l + r) / 2];
		}
	}
}