package  {
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.geom.Point;
	
	/**
	 * Used to calculate and draw the Voronoi Diagram
	 * @author Chad Nelson
	 */
	public class VoronoiDiagram extends Sprite
	{
		//DCEL
		public var sites : Vector.<VoronoiSite>; //faces
		public var nodes : Vector.<VoronoiNode>; //vertices
		public var edges : Vector.<VoronoiEdge>; //edges
		
		// Other
		private var boundingBoxTR : Point;
		private var boundingBoxBL : Point;
		public var events : Vector.<VoronoiEvent>;
		public var circles : Vector.<VoronoiCircleEvent>;
		public var beachline : BeachLine = new BeachLine();
		
		private var wavefront_on : Boolean = false;
		public var eventsHandled : uint = 0;
		/**
		 * Initializes the Voronoi Diagram with no sites
		 */
		public function VoronoiDiagram() { addChild(beachline); }
		
		private function init():void {
			nodes = new Vector.<VoronoiNode>();
			edges = new Vector.<VoronoiEdge>();
			events = new Vector.<VoronoiEvent>();
			circles = new Vector.<VoronoiCircleEvent>();
			eventsHandled = 0;
			// Remove old arcs
			while (beachline.numChildren > 0) beachline.removeChildAt(0);
			beachline.arcs = new Vector.<Parabola>();
			
			boundingBoxTR = new Point(Number.MIN_VALUE, Number.MIN_VALUE);
			boundingBoxBL = new Point(Number.MAX_VALUE, Number.MAX_VALUE);
			for each(var s : VoronoiSite in sites) {
				if (s.x > boundingBoxTR.x)
					boundingBoxTR.x = s.x;
				if (s.y > boundingBoxTR.y)
					boundingBoxTR.y = s.y;
				if (s.x < boundingBoxBL.x)
					boundingBoxBL.x = s.x;
				if (s.y < boundingBoxBL.y)
					boundingBoxBL.y = s.y;
			}
			boundingBoxBL.x -= 0.05 * (boundingBoxTR.x - boundingBoxBL.x);
			boundingBoxBL.y -= 0.05 * (boundingBoxTR.y - boundingBoxBL.y);
			boundingBoxTR.x += 0.05 * (boundingBoxTR.x - boundingBoxBL.x);
			boundingBoxTR.y += 0.05 * (boundingBoxTR.y - boundingBoxBL.y);
		}
		
		/**
		 * Initializes the Voronoi Diagram with a set P of points in the plane
		 * @param	P - set of points in the plane
		 */		
		public function setSites(P : Vector.<VoronoiSite>):void {
			sites = P;
			// Initialize beachline BST, DCEL, and priority queue of events
			init();
			for each(var site : VoronoiSite in sites) {
				site.edges = new Vector.<VoronoiEdge>();
				events.push(new VoronoiSiteEvent(site));
			}
			events.sort(Utility.eventComparator);
			
			wavefront_on = false;
			BeachLine.directrix = Number.POSITIVE_INFINITY;
		}
		
		/**
		 * Calculates & draws a partial or complete Voronoi Diagram.
		 * @param	y - The final y-coordinate of the beach line
		 */
		public function calculate(y:Number = Number.NEGATIVE_INFINITY):void {
			while (nextEvent(y));
			wavefront_on = (events.length != 0);
			
			if (y == Number.NEGATIVE_INFINITY)
				tieToBoundingBox();
		}

		
		public function nextEvent(y : Number = Number.NEGATIVE_INFINITY):Boolean {
			if (events.length == 0)
				return false;
			
			var current_event : VoronoiEvent;
			wavefront_on = true;
			current_event = events.shift();
			if (current_event.y < y) {
				events.unshift(current_event);
				return false;
			}
			BeachLine.directrix = current_event.y;
			
			if (current_event.type == VoronoiEventType.SITE)
				handleSiteEvent(VoronoiSiteEvent(current_event));
			else if (current_event.type == VoronoiEventType.CIRCLE)
				handleCircleEvent(VoronoiCircleEvent(current_event));
			
			eventsHandled = eventsHandled+1;
			return true;
		}
		
		private function handleSiteEvent(e:VoronoiSiteEvent):void {
			// If beachline is empty, initialize it with this site
			if (beachline.arcs.length == 0) {
				beachline.initialize(e.site);
				return;
			}
			
			// Locate arc above the site and remove a possible false circle event
			var arc : Parabola = beachline.locateArc(e.site);
			if (arc.circleEvent != null) {
				events.splice(events.indexOf(arc.circleEvent, 0), 1);
				circles.splice(circles.indexOf(arc.circleEvent, 0), 1);
				arc.circleEvent = null;
			}
			
			// Split the arc above the beachline into three arcs
			arc = beachline.split(e.site, arc);
			
			// Creates an edge between the two breakpoints of a given arc (created by a site event).
			var edge : VoronoiEdge = new VoronoiEdge();
			edge.siteA = arc.site;
			edge.siteB = arc.left.site;
			arc.site.edges.push(edge);
			arc.left.site.edges.push(edge);
			edge.breakpoint1 = arc.left;
			edge.breakpoint2 = arc;
			arc.edge_right = edge;
			arc.left.edge_right = edge;
			edges.push(edge);
			
			// Check for circle events
			var circleEvent : VoronoiCircleEvent;
			circleEvent = Utility.checkForCircleEvent(arc.left);
			if (circleEvent != null) {
				events.push(circleEvent);
				circles.push(circleEvent);
				events.sort(Utility.eventComparator);
			}
			circleEvent = Utility.checkForCircleEvent(arc.right);
			if (circleEvent != null) {
				events.push(circleEvent);
				circles.push(circleEvent);
				events.sort(Utility.eventComparator);
			}
		}
		
		
		/**
		 * Handles a circle event
		 * @param	e
		 */
		private function handleCircleEvent(e:VoronoiCircleEvent):void {
			circles.splice(circles.indexOf(e.center.circleEvent), 1);
			// Remove the arc that has vanished from the beach line
			beachline.destroy(e.center.left, e.center, e.center.right);
			
			// Remove any false alarm circle events 
			if (e.center.left.circleEvent != null) {
				events.splice(events.indexOf(e.center.left.circleEvent), 1);
				circles.splice(circles.indexOf(e.center.left.circleEvent), 1);
				e.center.left.circleEvent = null;
			} 
			if (e.center.right.circleEvent != null) {
				events.splice(events.indexOf(e.center.right.circleEvent), 1);
				circles.splice(circles.indexOf(e.center.right.circleEvent), 1);
				e.center.right.circleEvent = null;
			}
			
			// Add a voronoi vertex
			var vertex : VoronoiNode = new VoronoiNode((nodes.length + 1).toString(), e.central_point.x, e.central_point.y);
			nodes.push(vertex);
			// Update incoming edges
			if (e.center.edge_right != null) {
				vertex.edges.push(e.center.edge_right);
				if (e.center.edge_right.node1 == null)
					e.center.edge_right.node1 = vertex;
				else
					e.center.edge_right.node2 = vertex;
					
				if (e.center.edge_right.breakpoint1 == e.center)
					e.center.edge_right.breakpoint1 = null;
				else
					e.center.edge_right.breakpoint2 = null;
			}
			if (e.center.left.edge_right != null) {
				vertex.edges.push(e.center.left.edge_right);
				if (e.center.left.edge_right.node1 == null)
					e.center.left.edge_right.node1 = vertex;
				else
					e.center.left.edge_right.node2 = vertex;
					
				if (e.center.left.edge_right.breakpoint1 == e.center.left)
					e.center.left.edge_right.breakpoint1 = null;
				else
					e.center.left.edge_right.breakpoint2 = null;
			}
			// Create new edge going out
			// Creates an edge between the two breakpoints of a given arc (created by a site event).
			var edge : VoronoiEdge = new VoronoiEdge();
			edge.siteA = e.center.left.site;
			edge.siteB = e.center.right.site;
			e.center.right.site.edges.push(edge);
			e.center.left.site.edges.push(edge);
			edge.node1 = vertex;
			vertex.edges.push(edge);
			edge.breakpoint1 = e.center.left;
			e.center.left.edge_right = edge;
			edges.push(edge);
			
			// Check for circle events
			var circleEvent : VoronoiCircleEvent;
			circleEvent = Utility.checkForCircleEvent(e.center.left);
			if (circleEvent != null) {
				events.unshift(circleEvent);
				circles.push(circleEvent);
				events.sort(Utility.eventComparator);
			}
			circleEvent = Utility.checkForCircleEvent(e.center.right);
			if (circleEvent != null) {
				events.unshift(circleEvent);
				circles.push(circleEvent);
				events.sort(Utility.eventComparator);
			}
		}
		
		
		
		
		public function draw(drawBeachline : Boolean = false, circleEvents : Boolean = true):void {
			graphics.clear();
			
			// Draw BeachLine
			graphics.lineStyle(3, 0x0066AA, 0.5);
			if (wavefront_on || drawBeachline) {
				graphics.moveTo(0, stage.stageHeight-BeachLine.directrix);
				graphics.lineTo(stage.stageWidth, stage.stageHeight - BeachLine.directrix);
			}
				
			// Re-Draw Arcs
			for each (var p : Parabola in beachline.arcs) {
				p.draw();
			}
			
			// Draw edges
			var pt1 : Point = new Point();
			var pt2 : Point = new Point();
			graphics.lineStyle(1, 0, 1);
			for each (var e : VoronoiEdge in edges) {
				if (e.node1 != null) {
					pt1.x = e.node1.x;
					pt1.y = stage.stageHeight - e.node1.y;
					if (e.node2 != null) {
						pt2.x = e.node2.x;
						pt2.y = stage.stageHeight - e.node2.y;
					} else if (e.breakpoint1 != null) {
						pt2.x = e.breakpoint1.getRightBreakpoint();
						pt2.y = stage.stageHeight - e.breakpoint1.valueAt(pt2.x);
					} else {
						pt2.x = e.breakpoint2.getRightBreakpoint();
						pt2.y = stage.stageHeight - e.breakpoint2.valueAt(pt2.x);
					}
				} else {
					if (e.node2 == null) {
						pt1.x = e.breakpoint1.getRightBreakpoint();
						pt1.y = stage.stageHeight - e.breakpoint1.valueAt(pt1.x);
						pt2.x = e.breakpoint2.getRightBreakpoint();
						pt2.y = stage.stageHeight - e.breakpoint2.valueAt(pt2.x);
					} else if (e.breakpoint1 != null) {
						pt1.x = e.breakpoint1.getRightBreakpoint();
						pt1.y = stage.stageHeight - e.breakpoint1.valueAt(pt1.x);
						pt2.x = e.node2.x;
						pt2.y = stage.stageHeight - e.node2.y;
					} else {
						pt1.x = e.breakpoint2.getRightBreakpoint();
						pt1.y = stage.stageHeight - e.breakpoint2.valueAt(pt1.x);
						pt2.x = e.node2.x;
						pt2.y = stage.stageHeight - e.node2.y;
					}
				}
				
				if (!isNaN(pt1.x) && !isNaN(pt1.y) && !isNaN(pt2.x) && !isNaN(pt2.y)) {
					graphics.moveTo(pt1.x, pt1.y);
					graphics.lineTo(pt2.x, pt2.y);
				}
			}
			
			// Draw circles
			if (circleEvents) {
				graphics.lineStyle(3, 0x88DD33, 0.3);
				for each (var c : VoronoiCircleEvent in circles) {
					graphics.beginFill(0, 0);
					graphics.drawCircle(c.central_point.x, stage.stageHeight - c.central_point.y, c.radius);
					graphics.beginFill(0x88DD33, 0.3);
					graphics.drawCircle(c.central_point.x, stage.stageHeight - c.central_point.y, 2);
				}
			}
			
			// Draw Sites
			graphics.lineStyle(1, 0x0000DD);
			graphics.beginFill(0x0000DD, 1);
			for each(var s : VoronoiSite in sites) {
				graphics.drawCircle(s.x, stage.stageHeight - s.y, 1.2);
			}
			
			// Draw Nodes
			graphics.lineStyle(1, 0x333333, 1);
			graphics.beginFill(0x333333, 1);
			for each (var n : VoronoiNode in nodes) {
				graphics.drawCircle(n.x, stage.stageHeight - n.y, 2);
			}
		}
		
		
		/**
		 * Ties loose ends to the bounding box
		 */
		public function tieToBoundingBox():void {
			
		}
		
		/**
		 * Returns the DCEL of the Voronoi Diagram.
		 * Note: calculate() must be called first for the complete diagram to be in the output.
		 * @return a string representation of the DCEL
		 */
		public function outputDCEL():String {
			var o : String = "****** Voronoi Diagram ******\n\n";
			
			// Vertices
			for each (var v:VoronoiNode in nodes)
				o += v.toString();
			o += "\n";
			
			// Faces
			for each (var f:VoronoiSite in sites)
				o += f.toString();
			o += "\n";
			
			// Half-edges
			for each (var e:VoronoiEdge in edges)
				o += e.toString();
			o += "\n";
			
			trace(o);
			return o;
		}
	}
}