package flare.vis.operator.layout
{
    import flare.animate.Transitioner;
    import flare.util.Arrays;
    import flare.util.Shapes;
    import flare.vis.data.DataSprite;
    import flare.vis.data.EdgeSprite;
    import flare.vis.data.NodeSprite;
    import flare.vis.operator.Operator;

    /**
     * Layout that routes edges in a graph so that they form groups, reducing
     * clutter. This operator requires that a tree structure (for example, a
     * computed spanning tree) be defined over the graph. The class also sets
     * all edges' <code>shape</code> property to <code>Shapes.BSPLINE</code>
     * and can optionally compute <code>alpha</code> values to improve edge
     * visibility.
     * 
     * <p>The algorithm uses the tree path between two nodes to define control
     * points for routing a b-spline curve. The technique is adapted from
     * Danny Holten's work on
     * <a href="http://www.win.tue.nl/~dholten/papers/bundles_infovis.pdf">
     * Hierarchical Edge Bundles</a>, InfoVis 2006.</p>
     */
    public class BundledEdgeRouter extends Operator
    {
        /** Determines how "tight" the edges are bundled. At 0, all edges are
         *  unbundled straight lines. At 1, the edges bundle together tightly.
         *  The default is 0.85. */
        public var bundling:Number = 0.85;
        /** Removes the shared ancestor along a node path. */
        public var removeSharedAncestor:Boolean = false;
        
        /**
         * Creates a new BundledEdgeRouter 
         * @param bundling the tightness of edge bundles
         */
        public function BundledEdgeRouter(bundling:Number=0.85,
            removeSharedAncestor:Boolean=false)
        {
            this.bundling = bundling;
            this.removeSharedAncestor = removeSharedAncestor;
        }
        
        /** @inheritDoc */
        public override function operate(t:Transitioner=null):void
        {
            t = (t==null ? Transitioner.DEFAULT : t);
            
            var u:NodeSprite, v:NodeSprite, pu:NodeSprite, pv:NodeSprite;
            var p1:Array = [], p2:Array = [];
            var d1:int, d2:int, o:Object;
            var ux:Number, uy:Number, dx:Number, dy:Number;
            
            // compute edge bundles
            for each (var e:EdgeSprite in visualization.data.edges) {
                u = e.source; p1.push(pu=u); d1 = u.depth;
                v = e.target; p2.push(pv=v); d2 = v.depth;
                
                // trace paths to the least common ancestor of u,v
                while (d1 > d2) { p1.push(pu=pu.parentNode); --d1; }
                while (d2 > d1) { p2.push(pv=pv.parentNode); --d2; }
                while (pu != pv) {
                    p1.push(pu=pu.parentNode);
                    p2.push(pv=pv.parentNode);
                }
                
                // collect b-spline control points
                var p:Array = t.$(e).points;
                if (p==null) { p = []; } else { Arrays.clear(p); }
                
                d1 = p1.length;
                d2 = p2.length;
                if ((d1+d2)==4 && d1>1 && d2>1) { // shared parent
                    addPoint(p, p1[1], t);
                } else {
                    var off:int = removeSharedAncestor ? 1 : 0;
                    for (var i:int=1; i<p1.length-off; ++i)
                        addPoint(p, p1[i], t);
                    for (i=p2.length-1; --i>=1;)
                        addPoint(p, p2[i], t);
                }
                
                // set the bundling strength by adjusting control points
                var b:Number = bundling, ib:Number = 1-b, N:int = p.length;
                if (b < 1) {
                    o = t.$(u); ux = o.x; uy = o.y;
                    o = t.$(v);    dx = o.x; dy = o.y;
                    dx = (dx-ux)/(N+2);
                    dy = (dy-uy)/(N+2);

                    for (i=0; i<N; i+=2) {
                        p[i]   = b*p[i]   + ib*(ux + (i+2)*dx);
                        p[i+1] = b*p[i+1] + ib*(uy + (i+2)*dy);
                    }
                }
                
                o = t.$(e);
                o.points = p;
                e.shape = Shapes.BSPLINE;
                
                // clean-up
                Arrays.clear(p1);
                Arrays.clear(p2);
            }
        }
        
        private static function addPoint(p:Array, d:DataSprite, t:Transitioner):void
        {
            var o:Object = t.$(d);
            p.push(o.x);
            p.push(o.y);
        }
        
    } // end of class BundledEdgeRouter
}