package {
	import flash.geom.*;
	import flash.display.BitmapData;
	import flash.display.MovieClip;
	import flash.text.TextField;
	import flash.events.*;
	import flash.sampler.StackFrame;

	public class RectanglePacker
	{
		protected var w:int;
		protected var h:int;
		protected var root:RectangleNode;
		public var NextAllocationID = 0;
		
		public function get width():int { return w; }
		public function get height():int { return h; }
		
		public function RectanglePacker(w, h)
		{
			this.w = w;
			this.h = h;
			root = new RectangleNode(0, 0, w, h, this);
			root.AllocationID = -1;
		}
		protected var area = 0;
		
		protected var testRender:MovieClip = new MovieClip();
		
		public function GetRoot():RectangleNode
		{
			return root;
		}
		
		public function GetLeafNodes():Array
		{
			return GetLeafNodesInternal(root);
		}
		
		protected function GetLeafNodesInternal(n:RectangleNode):Array
		{
			if (n.InUse) return [n];
			var ret:Array = new Array();
			if (n.Left) ret = GetLeafNodesInternal(n.Left);
			if (n.Right) ret = ret.concat(GetLeafNodesInternal(n.Right));
			return ret;
		}
		
		public function GetUsedArea()
		{
			return area;
		}
		
		public function get efficiency()
		{
			return area / (w * h);
		}
		
		protected function RectCost(w, h)
		{
			if (w == 0 || h == 0) return 99999999;
			return (Math.max(w, h) / Math.min(w, h)) * w * h;
		}
		
		protected function EnumerateTree(r:RectangleNode = null, indent = "")
		{
			if (r == null) r = this.root;
			var str = "";
			str += indent + r.NodeID + "   r:" + r.Removed + "  iu" + r.InUse + "  ifs" + r.IsFreeSpace + "  " + r.Rect.left + "," + r.Rect.top + " -> " + r.Rect.right + "," + r.Rect.bottom + "\n";
			if (r.Left) str += EnumerateTree(r.Left, indent + "  ");
			if (r.Right) str += EnumerateTree(r.Left, indent + "  ");
			return str;
		}
		
		/*
		 * Remove a list of nodes from the tree.
		 *  - fullyDestroy: if not set, the nodes will be reused as nodes representing the new empty space in the tree
		 *					if set, the nodes will be duplicated as new objects to be inserted into the tree as blank space,
		 					leaving the original objects intact (in case something still references them)
		 */
		public function RemoveNodes(nodes:Array, fullyDestroy = true)
		{
			
			/* DEBUG CHECKS */
			/*
			this.PerformDebugCheck();
			
			var str = "";
			for (var i = 0; i < nodes.length; i++)
			{
				str += nodes[i].NodeID + "\n";
			}
			
			var orig = nodes.concat();
			
			var strs = [str, EnumerateTree()];
			
			RenderDetailsBox.StartTrack("PackRemoveTime");
						
			for (var i = 0; i < nodes.length; i++)
			{
				var n:RectangleNode = nodes[i];
				if (n.Host != this)
				{
					throw new Error("bad host!");
				}
			}
			*/
			/* END DEBUG CHECKS */
			
			var i, n:RectangleNode, p:RectangleNode;
			
			// setup the Removed flag on every node that should be removed
			// we also check at this time to see if any more nodes need to be removed, such as a parent of
			// 2 removed nodes (we want to optimize the tree to get rid of completely empty subtrees)
			for (i = 0; i < nodes.length; i++)
			{
				n = nodes[i];				
				if (n.Host == this)
				{
					n.Removed = true;
					
					if (n.InUse)
					{
						// sum up the total removed area
						area -= n.Rect.width * n.Rect.height;
					}
					
					if (n.Parent != null)
					{
						p = n.Parent;
						// check and see if the current node's parent still has any valid children
						if ((p.Left.IsFreeSpace || p.Left.Removed) && (p.Right.IsFreeSpace || p.Right.Removed))
						{
							// all of the current nodes siblings are either being removed or are blank, so
							// we can remove the parent too
							if (p.Left.IsFreeSpace)
							{
								// the left child was empty space before, so we can remove it (if it wasn't
								// empty space it is already being removed so it doesn't need to be added
								// to the list)
								if (nodes.indexOf(p.Left) == -1) nodes.push(p.Left);
							}
							if (p.Right.IsFreeSpace)
							{
								// the right child was empty space before, so we can remove it
								if (nodes.indexOf(p.Right) == -1) nodes.push(p.Right);
							}
							if (p != root && nodes.indexOf(p) == -1)
							{
								// remove the parent node too (provided it isn't the root!)
								nodes.push(p);
							}
						}
					}
				}
			}
			
			// now we have an expanded list of all nodes that will actually be cut out to return an optimized tree,
			// so go ahead and remove them
			for (i = 0; i < nodes.length; i++)
			{
				n = nodes[i];
				
				if (n.Parent != null)
				{
					// n is getting removed, so n.Parent may have some changes to its pointers (provided n.Parent is not
					// also getting removed!)
					p = n.Parent;
					
					if (!p.Removed)
					{
						if (p.Left && p.Right)
						{
							var newNode:RectangleNode;
							if (p.Left.Removed && p.Right.Removed)
							{
								// both children were removed, but the parent wasn't, so the parent must be root
								// (since we never remove the root)
								if (p != root)
								{
									throw new Error("should be root");
								}
								p.Left.Parent = null;
								p.Right.Parent = null;
								p.Left = null;
								p.Right = null;
								p.InUse = false;								
							} else if (!p.Left.Removed) {
								// Right node removed, Left node not removed
								if (!p.Left.IsFreeSpace)
								{
									if (fullyDestroy)
									{
										// duplicate the node representing empty space so the original node
										// remains untouched
										newNode = new RectangleNode(0, 0, 0, 0, this);
										newNode.MakeFromNode(p.Right);
										newNode.UpdateLinksFromNode(p.Right);
									}
									// Left node is used
									p.Right.InUse = false;
									p.Right.Left = null;
									p.Right.Right = null;
									p.Right.Removed = false;
								} else {
									throw new Error("should have been caught above!");
								}
							} else {
								// Left node removed, Right node not removed
								if (!p.Right.IsFreeSpace)
								{
									if (fullyDestroy)
									{
										// duplicate the node representing empty space so the original node
										// remains untouched
										newNode = new RectangleNode(0, 0, 0, 0, this);
										newNode.MakeFromNode(p.Left);
										newNode.UpdateLinksFromNode(p.Left);
									}
									// Left node is used
									//p.Left.Removed = true;
									p.Left.InUse = false;
									p.Left.Left = null;
									p.Left.Right = null;
									p.Left.Removed = false;
									//p.Left.Parent = null;									
								} else {
									throw new Error("should have been caught above!");
								}
							}
						} else {
							// huh? how does n.Parent == p but p has no children? something went wrong
							throw new Error("shouldn't have gotten here");
						}
					}
				}
				//strs.push(EnumerateTree());
			}
		}
		
		public function Insert(w, h, useInstead:RectangleNode = null):RectangleNode
		{
			
			var node:RectangleNode = FindSizedNode(w, h, root);
			
			if (node == null)
			{
				//UHOH, texture full
				return null;
			}
			area += w * h;
			node.InUse = true;
			
			var splitVertFirstCost = 0;
			if (w < node.Rect.width)
			{
				splitVertFirstCost = RectCost(node.Rect.width - w, node.Rect.height) + RectCost(w, node.Rect.height - h);
			}
			
			var splitHorizFirstCost = 0;
			if (h < node.Rect.height)
			{
				splitHorizFirstCost = RectCost(node.Rect.width - w, h) + RectCost(node.Rect.width, node.Rect.height - h);
			}
			
			
			
			if (splitVertFirstCost <= splitHorizFirstCost)
			{
				node.Flags.push("SplitVertFirst");
				if (w < node.Rect.width)
				{
					node.Flags.push("SplitVert");
					node.InUse = false;
					// split node vertically
					SplitVert(node, w);
					node.Left.InUse = true;
					node = node.Left;
				}
				if (h < node.Rect.height)
				{
					node.Flags.push("SplitHorz");
					node.InUse = false;
					SplitHoriz(node, h);
					node.Left.InUse = true;
					node = node.Left;
				}
			} else {
				node.Flags.push("SplitHorzFirst");
				if (h < node.Rect.height)
				{
					node.Flags.push("SplitVert");
					node.InUse = false;
					SplitHoriz(node, h);
					node.Left.InUse = true;
					node = node.Left;
				}
				if (w < node.Rect.width)
				{
					node.Flags.push("SplitHorz");
					node.InUse = false;
					// split node vertically
					SplitVert(node, w);
					node.Left.InUse = true;
					node = node.Left;
				}
			}			
			NextAllocationID++;
			if (useInstead)
			{
				useInstead.MakeFromNode(node);
				useInstead.UpdateLinksFromNode(node);
				useInstead.Flags = node.Flags;
				node = useInstead;
				node.Flags.push("UseInstead");
			}
			
			//if (!CheckOKNode(node)) node.Flags.push("BadNode");
			
			return node;
		}
		public function CheckOKNode(n:RectangleNode, r:RectangleNode = null)
		{
			if (r == null) r = this.root;
			if (n != r && r.InUse && n.Rect.intersection(r.Rect).size.length > 0)
			{
				var ancestor:RectangleNode = FindCommonNode(n, r);
				throw new Error("bad node allocated!");
				return false;
			}
			var ok = true;
			if (r.Left) ok = ok && CheckOKNode(n, r.Left);
			if (r.Right) ok = ok && CheckOKNode(n, r.Right);
			return ok;
		}
		
		public function PerformDebugCheck()
		{
			DebugInternal(this.root);
		}
		
		protected function DebugInternal(n:RectangleNode)
		{
			if (n.Host != this)
			{
				throw new Error("problem with host!");
			}
			if (n.IsFreeSpace)
			{
				if (n.Left || n.Right)
				{
					throw new Error("shouldn't have children");
				}
			}
			if ((n.Left && !n.Right) || (n.Right && !n.Left))
			{
				throw new Error("mismatched children");
			}
			if (n.Left && n.Left.Parent != n)
			{
				throw new Error("left child has bad parent");
			}
			if (n.Right && n.Right.Parent != n)
			{
				throw new Error("right child has bad parent");
			}
			if (n.Parent && n.Parent.Left != n && n.Parent.Right != n)
			{
				throw new Error("problem with parent");
			}
			if (n.Left) DebugInternal(n.Left);
			if (n.Right) DebugInternal(n.Right);
		}
		
		public function FindCommonNode(a:RectangleNode, b:RectangleNode)
		{
			var aHistory = [];
			var bHistory = [];
			while (a != null)
			{
				aHistory.push(a);
				a = a.Parent;
			}
			while (b != null)
			{
				bHistory.push(b);
				b = b.Parent;
			}
			var i = aHistory.length - 1;
			var j = bHistory.length - 1;
			var same = null;
			while (i >= 0 && j >= 0)
			{
				if (aHistory[i] == bHistory[j])
				{
					same = aHistory[i];
				} else {
					break;
				}
				i--;
				j--;
			}
			return same;
		}
		
		public function TestRender()
		{
			while (testRender.numChildren > 0)
			{
				testRender.removeChildAt(0);
			}
			testRender.graphics.clear();
			TestRenderNode(root, testRender);
			return testRender;
		}
		protected function TestRenderNode(n:RectangleNode, m:MovieClip)
		{
			var g:MovieClip = new MovieClip();
			m.addChild(g);
			g.graphics.lineStyle(1, 0, 1);
			if (n.Left != null) TestRenderNode(n.Left, m);
			if (n.Left != null) TestRenderNode(n.Right, m);
			if (n.InUse)
			{
				g.graphics.beginFill(0xFFFF00, 0.2);
			}
			g.graphics.drawRect(n.Rect.x, n.Rect.y, n.Rect.width, n.Rect.height);
			if (n.InUse)
			{
				g.graphics.endFill();
				var t:TextField = new TextField();
				t.text = n.NodeID;
				t.x = n.Rect.x + n.Rect.width / 2.0;
				t.y = n.Rect.y + n.Rect.height / 2.0;
				g.addChild(t);
				g.addEventListener(MouseEvent.MOUSE_OVER, function(e){MouseOver(n,g,t);});
				g.addEventListener(MouseEvent.MOUSE_OUT, function(e){MouseOut(n,g,t);});
			}
			
		}
		public function MouseOver(n:RectangleNode, g:MovieClip, t:TextField)
		{
			if (n.InUse)
			{
				//_trace(Math.round(n.LastAccessTime / 1000));
			}
			var p:RectangleNode = n.Parent;
			if (p)
			{
				g.graphics.clear();
				g.graphics.lineStyle(1, 0, 1);
				g.graphics.beginFill(p.IsFreeSpace ? 0x0000FF : 0xFF0000, 0.4);
				g.graphics.drawRect(p.Rect.x, p.Rect.y, p.Rect.width, p.Rect.height);
				g.graphics.endFill();
				t.text = p.NodeID;
				if (g.oldListener) g.removeEventListener(MouseEvent.CLICK, g.oldListener);
				g.oldListener = function(e){MouseOver(p, g, t);};
				g.addEventListener(MouseEvent.CLICK, g.oldListener);
			}
		}
		public function MouseOut(n:RectangleNode, g:MovieClip, t:TextField)
		{			
			g.graphics.clear();
			g.graphics.lineStyle(1, 0, 1);
			g.graphics.beginFill(0xFFFF00, 0.2);
			g.graphics.drawRect(n.Rect.x, n.Rect.y, n.Rect.width, n.Rect.height);
			g.graphics.endFill();
			t.text = n.NodeID;
		}
		protected function SplitVert(node:RectangleNode, leftWidth)
		{
			node.Left = new RectangleNode(node.Rect.x, node.Rect.y, leftWidth, node.Rect.height, this);
			node.Left.AllocationID = NextAllocationID;
			node.Left.Parent = node;
			node.Right = new RectangleNode(node.Rect.x + leftWidth, node.Rect.y, node.Rect.width - leftWidth, node.Rect.height, this);
			node.Right.AllocationID = NextAllocationID;
			node.Right.Parent = node;
			
			//CheckOKNode(node.Left);
			//CheckOKNode(node.Right);
		}
		protected function SplitHoriz(node:RectangleNode, topHeight)
		{
			node.Left = new RectangleNode(node.Rect.x, node.Rect.y, node.Rect.width, topHeight, this);
			node.Left.AllocationID = NextAllocationID;
			node.Left.Parent = node;
			node.Right = new RectangleNode(node.Rect.x, node.Rect.y + topHeight, node.Rect.width, node.Rect.height - topHeight, this);
			node.Right.AllocationID = NextAllocationID;
			node.Right.Parent = node;
			
			//CheckOKNode(node.Left);
			//CheckOKNode(node.Right);
		}
		protected function FindSizedNode(w, h, node:RectangleNode):RectangleNode
		{
			if (node.InUse) return null;
			if (node.Rect.width >= w && node.Rect.height >= h)
			{
				if (node.Left != null && node.Right != null)
				{
					var t:RectangleNode = FindSizedNode(w, h, node.Left);
					if (t != null) return t;
					t = FindSizedNode(w, h, node.Right);
					return t;
				} else {
					return node;
				}
			}
			return null;
		}
		
		public function LoadTree(details)
		{
			this.root = new RectangleNode(0, 0, 0, 0, this);
			root.ReadJSON(details);
			
			this.NextAllocationID = 0;
			this.area = 0;
			
			var queue:Array = new Array();
			queue.push(root);
			while (queue.length > 0)
			{
				var node:RectangleNode = queue.shift();
				node.AllocationID = NextAllocationID;
				node.MinAllocationID = NextAllocationID;
				if (node.Left) queue.push(node.Left);
				if (node.Right) queue.push(node.Right);
				if (node.InUse) this.area += node.Rect.width * node.Rect.height;
			}
			NextAllocationID++;
		}

		public function GetNodePath(node:RectangleNode)
		{
			var output:String = "";
			while (node != this.root)
			{
				output = (node == node.Parent.Left ? "l" : "r") + output;
				node = node.Parent;
			}
			return output;
		}
		
		public function GetNodeFromPath(path:String):RectangleNode
		{
			var node:RectangleNode = this.root;
			for (var i = 0; i < path.length; i++)
			{
				if (!node) return null;
				if (path.charAt(i) == "r")
				{
					node = node.Right;
				} else {
					node = node.Left;
				}
			}
			return node;
		}
	}
}