package flare.vis.operator.layout
{
    import flare.util.Orientation;
    import flare.util.Property;
    import flare.vis.data.EdgeSprite;
    import flare.vis.data.NodeSprite;
    
    /**
     * Layout that places items in a dendrogram for displaying the results of
     * hierarchical clustering. This class computes a dendrogram layout and sets
     * edge control points to create "U" shaped dendrogram branches. It is
     * common, though by no means required, to hide the node instances in a
     * dendrogram display.
     * 
     * <p>To determine the height of dendrogram branches, a distance property
     * can be provided. The values of this property will directly determine
     * node heights by laying out the depth axis using a linear scale of
     * distance values. The distance property should be set for all non-leaf
     * nodes in the tree. Typically, leaf nodes have a distance of zero,
     * resulting in an aligned list of leaf nodes.</p>
     */
    public class DendrogramLayout extends Layout
    {
        // TODO: support axes, too
        
        private var _orient:String = Orientation.TOP_TO_BOTTOM; // the orientation of the tree
        private var _dp:Property;
        
        private var _leafCount:int;
        private var _leafIndex:int = 0;
        private var _maxDist:Number;
        private var _b1:Number;
        private var _db:Number;
        private var _d1:Number;
        private var _dd:Number;
        
        /** Data property to use as the distance field for
         *  determining the height values of dendrogram branches. */
        public function get distanceProperty():String { return _dp.name; }
        public function set distanceProperty(dp:String):void {
            _dp = Property.$(dp);
        }
        
        /** The orientation of the dendrogram */
        public function get orientation():String { return _orient; }
        public function set orientation(o:String):void { _orient = o; }
        
        /**
         * Creates a new DendrogramLayout.
         * @param distField data property to use as the distance field for
         *  determining the height values of dendrogram branches
         * @param orientation the orientation of the dendrogram
         */
        public function DendrogramLayout(distField:String=null,
            orientation:String=Orientation.TOP_TO_BOTTOM)
        {
            _dp = distField==null ? null : Property.$(distField);
            _orient = orientation;
        }
        
        /** @inheritDoc */
        protected override function layout():void
        {
            init();
            doLayout(visualization.tree.root);
        }
        
        /**
         * Initialize the layout.
         */
        private function init():void
        {
            var root:NodeSprite = visualization.tree.root;
            _leafCount = visualization.tree.countLeaves();
            _leafIndex = 0;
            _maxDist = _dp!=null ? _dp.getValue(root) : computeHeights(root);
            
            switch (_orient) {
                case Orientation.TOP_TO_BOTTOM:
                    _b1 = layoutBounds.left;
                    _db = layoutBounds.width;
                    _d1 = layoutBounds.bottom;
                    _dd = -layoutBounds.height;
                    break;
                case Orientation.BOTTOM_TO_TOP:
                    _b1 = layoutBounds.left;
                    _db = layoutBounds.width;
                    _d1 = layoutBounds.top;
                    _dd = layoutBounds.height;
                    break;
                case Orientation.LEFT_TO_RIGHT:
                    _b1 = layoutBounds.top;
                    _db = layoutBounds.height;
                    _d1 = layoutBounds.right;
                    _dd = -layoutBounds.width;
                    break;
                case Orientation.RIGHT_TO_LEFT:
                    _b1 = layoutBounds.top;
                    _db = layoutBounds.height;
                    _d1 = layoutBounds.left;
                    _dd = layoutBounds.width;
                    break;
            }
        }
        
        private function computeHeights(n:NodeSprite):int
        {
            n.u = 0;
            for (var i:int=0; i<n.childDegree; ++i) {
                n.u = Math.max(n.u, 1 + computeHeights(n.getChildNode(i)));
            }
            return n.u;
        }
        
        private function doLayout(n:NodeSprite):Number
        {
            var d:Number = _dp!=null ? _dp.getValue(n) : n.u;
            d = _d1 + _dd * (d / _maxDist);
            
            if (n.childDegree > 0) {
                var b:Number = 0, bc:Number;
                for (var i:int=0; i<n.childDegree; ++i) {
                    var c:NodeSprite = n.getChildNode(i);
                    b += (bc=doLayout(c));
                    layoutEdge(c.parentEdge, bc, d);
                }
                b /= n.childDegree;
            } else {
                var step:Number = 1.0 / _leafCount;
                b = _b1 + _db * step * (0.5 + _leafIndex++);
            }
            layoutNode(n, b, d);
            return b;
        }
        
        private function layoutNode(n:NodeSprite, b:Number, d:Number):void
        {
            var o:Object = _t.$(n);
            if (Orientation.isVertical(_orient)) {
                o.x = b; o.y = d;
            } else {
                o.x = d; o.y = b;
            }
        }
        
        private function layoutEdge(e:EdgeSprite, b:Number, d:Number):void
        {
            var vert:Boolean = Orientation.isVertical(_orient);
            if (e.points == null) {
                var s:NodeSprite = e.source;
                var t:NodeSprite = e.target;
                e.points = [(s.x+t.x)/2, (s.y+t.y)/2];
            }
            _dummy.x = b; b = _dummy.x;
            _dummy.x = d; d = _dummy.x;
            _t.$(e).points = vert ? [b, d] : [d, b];
        }
        
    } // end of class DendrogramLayout
}