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;
protected var h;
protected var root:RectangleNode;
public var NextAllocationID = 0;
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 */
// 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 (var i = 0; i < nodes.length; i++)
{
var n:RectangleNode = 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)
{
var p:RectangleNode = 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 (var i = 0; i < nodes.length; i++)
{
var n:RectangleNode = 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!)
var p:RectangleNode = n.Parent;
if (!p.Removed)
{
if (p.Left && p.Right)
{
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
var newNode:RectangleNode = 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
var newNode:RectangleNode = 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());
}
RenderDetailsBox.EndTrack("PackRemoveTime");
}
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;
RenderDetailsBox.StartTrack("PackInsertTime");
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");
}
RenderDetailsBox.EndTrack("PackInsertTime");
//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;
}
}
}
