AS3 Binary Tree Bin Packing Algorithm

package rebuild3.game.starling
{
    import flash.display.DisplayObject;
    import flash.display.DisplayObjectContainer;

    /**
     * Atlas packing algorithm for SarahDynamicAtlas.
     * From javascript at http://codeincomplete.com/posts/2011/5/7/bin_packing/
     * https://github.com/jakesgordon/bin-packing/blob/master/js/packer.growing.js
     *
     * @author jakesgordon and Sarah Northway
     */
    public class SarahAtlasLayouter
    {
        /**
         * Changes the x and y of the DisplayObjects in items to fit in an atlas atlasWidth wide
         * and as tall as necessary.
         * @param items an Array of DisplayObjects
         * @param atlasWidth the target width of the atlas eg 1024, 2048 or 4096
         * @param gutterSize space to put between items
         */
        public static function layoutItems(items:Array, atlasWidth:int = 2048, gutterSize:int = 1):void
        {
            if (items.length == 0) {
                return;
            }

            items.sort(function(first:DisplayObject, second:DisplayObject):int {
                return second.height - first.height;
            });

            //var startingWidth:int = Math.ceil(items[0].width) + gutterSize;
            var startingWidth:int = atlasWidth;
            var startingHeight:int = Math.ceil(items[0].height) + gutterSize;
            root = new AtlasNode(0, 0, startingWidth, startingHeight);

            for each (var item:DisplayObject in items) {
                var width:int = Math.ceil(item.width) + gutterSize;
                var height:int = Math.ceil(item.height) + gutterSize;
                var itemName:String = (item as DisplayObjectContainer).getChildAt(0).name;

                var node:AtlasNode = findNode(root, width, height);
                if (node != null) {
                    splitNode(node, width, height);
                    item.x = node.x;
                    item.y = node.y;
                } else {
                    //node = growNode(width, height);
                    node = growDown(width, height);
                    if (node == null) {
                        trace("SarahAtlasLayouter failed, could not grow??", root.width, root.height);
                        return;
                    }
                    item.x = node.x;
                    item.y = node.y;
                }
            }

            root = null;
        }

        private static function findNode(localRoot:AtlasNode, width:int, height:int):AtlasNode
        {
            if (localRoot.used) {
                var newNode:AtlasNode = findNode(localRoot.right, width, height);
                if (newNode != null) {
                    return newNode;
                }
                return findNode(localRoot.down, width, height);
            } else if ((width <= localRoot.width) && (height <= localRoot.height)) {
                return localRoot;
            } else {
                return null;
            }
        }

        private static function splitNode(node:AtlasNode, width:int, height:int):void
        {
            node.used = true;
            // sarah changed this line so down node does not overlap with right
            //node.down = new AtlasNode(node.x, node.y + height, node.width, node.height - height);
            node.down = new AtlasNode(node.x, node.y + height, width, node.height - height);
            node.right = new AtlasNode(node.x + width, node.y, node.width - width, node.height);
        }

        private static function growDown(width:int, height:int):AtlasNode
        {
            var downNode:AtlasNode = new AtlasNode(0, root.height, root.width, height);
            var newRoot:AtlasNode = new AtlasNode(0, 0, root.width, root.height + height, true, downNode, root);
            root = newRoot;

            var node:AtlasNode = findNode(root, width, height);
            if (node != null) {
                splitNode(node, width, height);
                return node;
            }

            // can never happen...?
            return null;
        }

        /*private static function growNode(width:int, height:int):AtlasNode
        {
            var canGrowDown:Boolean  = (width <= root.width);
            var canGrowRight:Boolean = (height <= root.height);

            // attempt to keep square-ish by growing right when height is much greater than width
            var shouldGrowRight:Boolean = canGrowRight && (root.height >= (root.width + width));

            // attempt to keep square-ish by growing down  when width  is much greater than height
            var shouldGrowDown:Boolean = canGrowDown && (root.width >= (root.height + height));

            if (shouldGrowRight) {
                return growRight(width, height);
            } else if (shouldGrowDown) {
                return growDown(width, height);
            } else if (canGrowRight) {
                return growRight(width, height);
            } else if (canGrowDown) {
                return growDown(width, height);
            } else {
                return null; // need to ensure sensible root starting size to avoid this happening
            }
        }*/

        /*private static function growRight(width:int, height:int):AtlasNode
        {
            var rightNode:AtlasNode = new AtlasNode(root.width, 0, width, root.height);
            var newRoot:AtlasNode = new AtlasNode(0, 0, root.width + width, root.height, true, root, rightNode);
            root = newRoot;

            var node:AtlasNode = findNode(root, width, height);
            if (node != null) {
                splitNode(node, width, height);
                return node;
            }

            // can never happen...?
            return null;
        }*/

        /** Temp data while running layoutItems */
        private static var root:AtlasNode;
    }
}

class AtlasNode
{
    public function AtlasNode(x:int, y:int, width:int, height:int,
        used:Boolean = false, down:AtlasNode = null, right:AtlasNode = null)
    {
       this.x = x;
       this.y = y;
       this.width = width;
       this.height = height;
       this.used = used;
       this.down = down;
       this.right = right;
    }

    public function toString():String
    {
        return "(" + x + "," + y + " - " + (x + width) + "," + (y + height + ")");
    }

    public var x:int;
    public var y:int;
    public var width:int;
    public var height:int;
    public var used:Boolean;
    public var down:AtlasNode;
    public var right:AtlasNode;
}