package flare.vis.operator.layout
{
    import flare.animate.Transitioner;
    import flare.util.Property;
    import flare.vis.data.NodeSprite;
    
    import flash.geom.Rectangle;
    
    /**
     * Layout that places node in a TreeMap layout that optimizes for low
     * aspect ratios of visualized tree nodes. TreeMaps are a form of
     * space-filling layout that represents nodes as boxes on the display, with
     * children nodes represented as boxes placed within their parent's box.
     * This layout determines the area of nodes in the tree map by looking up
     * the <code>sizeField</code> property on leaf nodes. By default, this
     * property is "size", such that the layout will look for size
     * values in the <code>DataSprite.size</code> property.
     * 
     * <p>
     * This particular algorithm is taken from Bruls, D.M., C. Huizing, and 
     * J.J. van Wijk, "Squarified Treemaps" In <i>Data Visualization 2000, 
     * Proceedings of the Joint Eurographics and IEEE TCVG Sumposium on 
     * Visualization</i>, 2000, pp. 33-42. Available online at:
     * <a href="http://www.win.tue.nl/~vanwijk/stm.pdf">
     * http://www.win.tue.nl/~vanwijk/stm.pdf</a>.
     * </p>
     * <p>
     * For more information on TreeMaps in general, see 
     * <a href="http://www.cs.umd.edu/hcil/treemap-history/">
     * http://www.cs.umd.edu/hcil/treemap-history/</a>.
     * </p>
     */
    public class TreeMapLayout extends Layout
    {
        private static const AREA:String = "treeMapArea";
        
        private var _kids:Array = new Array();
        private var _row:Array  = new Array();
        private var _r:Rectangle = new Rectangle();
        
        private var _size:Property = Property.$("size");
        
        /** The property from which to access size values for leaf nodes. */
        public function get sizeField():String { return _size.name; }
        public function set sizeField(s:String):void { _size = Property.$(s); }
        
        // --------------------------------------------------------------------
        
        /**
         * Creates a new TreeMapLayout 
         * @param sizeField the data property from which to access the size
         *  value for leaf nodes. The default is the "size" property.
         */
        public function TreeMapLayout(sizeField:String="size") {
            this.sizeField = sizeField;
        }
        
        /** @inheritDoc */
        protected override function layout():void
        {
            // setup
            var root:NodeSprite = layoutRoot as NodeSprite;
            var b:Rectangle = layoutBounds;
            _r.x=b.x; _r.y=b.y; _r.width=b.width-1; _r.height=b.height-1;
            
            // process size values
            computeAreas(root);
            
            // layout root node
            var o:Object = _t.$(root);
            o.x = 0;//_r.x + _r.width/2;
            o.y = 0;//_r.y + _r.height/2;
            o.u = _r.x;
            o.v = _r.y;
            o.w = _r.width;
            o.h = _r.height;
    
            // layout the tree
            updateArea(root, _r);
            doLayout(root, _r);
        }
        
        /**
         * Compute the pixel areas of nodes based on their size values.
         */
        private function computeAreas(root:NodeSprite):void
        {
            var leafCount:int = 0;
        
            // reset all sizes to zero
            root.visitTreeDepthFirst(function(n:NodeSprite):void {
                n.props[AREA] = 0;
            });
        
            // set raw sizes, compute leaf count
            root.visitTreeDepthFirst(function(n:NodeSprite):void {
                if (n.childDegree == 0) {
                    var sz:Number = _size.getValue(_t.$(n));
                    n.props[AREA] = sz;
                    var p:NodeSprite = n.parentNode;
                    for (; p != null; p=p.parentNode)
                        p.props[AREA] += sz;
                    ++leafCount;
                }
            });
        
            // scale sizes by display area factor
            var b:Rectangle = layoutBounds;
            var area:Number = (b.width-1)*(b.height-1);
            var scale:Number = area / root.props[AREA];
            root.visitTreeDepthFirst(function(n:NodeSprite):void {
                n.props[AREA] *= scale;
            });
        }
        
        /**
         * Compute the tree map layout.
         */
        private function doLayout(p:NodeSprite, r:Rectangle):void
        {
            // create sorted list of children's properties
            for (var i:uint = 0; i < p.childDegree; ++i) {
                _kids.push(p.getChildNode(i).props);
            }
            _kids.sortOn(AREA, Array.NUMERIC);
            // update array to point to sprites, not props
            for (i = 0; i < _kids.length; ++i) {
                _kids[i] = _kids[i].self;
            }
            
            // do squarified layout of siblings
            var w:Number = Math.min(r.width, r.height);
            squarify(_kids, _row, w, r); 
            _kids.splice(0, _kids.length); // clear _kids
            
            // recurse
            for (i=0; i<p.childDegree; ++i) {
                var c:NodeSprite = p.getChildNode(i);
                if (c.childDegree > 0) {
                    updateArea(c, r);
                    doLayout(c, r);
                }
            }
        }
        
        private function updateArea(n:NodeSprite, r:Rectangle):void
        {
            var o:Object = _t.$(n);
            r.x = o.u;
            r.y = o.v;
            r.width = o.w;
            r.height = o.h;
            return;
            
            /*
            Rectangle2D b = n.getBounds();
            if ( m_frame == 0.0 ) {
                // if no framing, simply update bounding rectangle
                r.setRect(b);
                return;
            }
            
            // compute area loss due to frame
            double dA = 2*m_frame*(b.getWidth()+b.getHeight()-2*m_frame);
            double A = n.getDouble(AREA) - dA;
            
            // compute renormalization factor
            double s = 0;
            Iterator childIter = n.children();
            while ( childIter.hasNext() )
                s += ((NodeItem)childIter.next()).getDouble(AREA);
            double t = A/s;
            
            // re-normalize children areas
            childIter = n.children();
            while ( childIter.hasNext() ) {
                NodeItem c = (NodeItem)childIter.next();
                c.setDouble(AREA, c.getDouble(AREA)*t);
            }
            
            // set bounding rectangle and return
            r.setRect(b.getX()+m_frame,       b.getY()+m_frame, 
                      b.getWidth()-2*m_frame, b.getHeight()-2*m_frame);
            return;
            */
        }
        
        private function squarify(c:Array, row:Array, w:Number, r:Rectangle):void
        {
            var worst:Number = Number.MAX_VALUE, nworst:Number;
            var len:int;
            
            while ((len=c.length) > 0) {
                // add item to the row list, ignore if negative area
                var item:NodeSprite = c[len-1];
                var a:Number = item.props[AREA];
                if (a <= 0.0) {
                    c.pop();
                    continue;
                }
                row.push(item);
                
                nworst = getWorst(row, w);
                if (nworst <= worst) {
                    c.pop();
                    worst = nworst;
                } else {
                    row.pop(); // remove the latest addition
                    r = layoutRow(row, w, r); // layout the current row
                    w = Math.min(r.width, r.height); // recompute w
                    row.splice(0, row.length); // clear the row
                    worst = Number.MAX_VALUE;
                }
            }
            if (row.length > 0) {
                r = layoutRow(row, w, r); // layout the current row
                row.splice(0, row.length); // clear the row
            }
        }
    
        private function getWorst(rlist:Array, w:Number):Number
        {
            var rmax:Number = Number.MIN_VALUE;
            var rmin:Number = Number.MAX_VALUE;
            var s:Number = 0;

            for each (var n:NodeSprite in rlist) {
                var r:Number = n.props[AREA];
                rmin = Math.min(rmin, r);
                rmax = Math.max(rmax, r);
                s += r;
            }
            s = s*s; w = w*w;
            return Math.max(w*rmax/s, s/(w*rmin));
        }
        
        private function layoutRow(row:Array, ww:Number, r:Rectangle):Rectangle
        {
            var s:Number = 0; // sum of row areas
            for each (var n:NodeSprite in row) {
                s += n.props[AREA];
            }
            
            var xx:Number = r.x, yy:Number = r.y, d:Number = 0;
            var hh:Number = ww==0 ? 0 : s/ww;
            var horiz:Boolean = (ww == r.width);
            
            // set node positions and dimensions
            for each (n in row) {
                var p:NodeSprite = n.parentNode;
                var nw:Number = n.props[AREA]/hh;
                
                var o:Object = _t.$(n);
                if (horiz) {
                    o.u = xx + d;
                    o.v = yy;
                    o.w = nw;
                    o.h = hh;
                    //o.x = xx + d + nw/2;
                    //o.y = yy + hh/2;
                } else {
                    o.u = xx;
                    o.v = yy + d;
                    o.w = hh;
                    o.h = nw;
                    //o.x = xx + hh/2;
                    //o.y = yy + d + nw/2;
                }
                o.x = 0;
                o.y = 0;
                d += nw;
            }
            
            // update space available in rectangle r
            if (horiz) {
                r.x = xx; r.y = yy+hh; r.height -= hh;
            } else {
                r.x = xx+hh; r.y = yy; r.width -= hh;
            }
            return r;
        }
    }
}