    package flare.vis.operator.layout
    {
        import flare.util.Arrays;
        import flare.vis.data.NodeSprite;

        import flash.geom.Rectangle;

        /**
         * Layout that places tree nodes in a radial layout, laying out depths of a tree
         * along circles of increasing radius.
         * This layout can be used for both node-link diagrams, where nodes are
         * connected by edges, and for radial space-filling ("sunburst") diagrams.
         * To generate space-filling layouts, nodes should have their shape
         * property set to <code>Shapes.WEDGE</code> and the layout instance should
         * have the <code>useNodeSize<code> property set to false.
         *
         * <p>The algorithm used is an adaptation of a technique by Ka-Ping Yee,
         * Danyel Fisher, Rachna Dhamija, and Marti Hearst, published in the paper
         * <a href="http://citeseer.ist.psu.edu/448292.html">Animated Exploration of
         * Dynamic Graphs with Radial Layout</a>, InfoVis 2001. This algorithm computes
         * a radial layout which factors in possible variation in sizes, and maintains
         * both orientation and ordering constraints to facilitate smooth and
         * understandable transitions between layout configurations.
         * </p>
         */
        public class RadialTreeLayout extends Layout
        {
            // -- Properties ------------------------------------------------------

            /** Property name for storing parameters for this layout. */
            public static const PARAMS:String = "radialTreeLayoutParams";
            /** The default radius increment between depth levels. */
            public static const DEFAULT_RADIUS:int = 50;

            private var _maxDepth:int = 0;
            private var _radiusInc:Number = DEFAULT_RADIUS;
            private var _theta1:Number = Math.PI/2;
            private var _theta2:Number = Math.PI/2 - 2*Math.PI;
            private var _sortAngles:Boolean = true;
            private var _setTheta:Boolean = false;
            private var _autoScale:Boolean = true;
            private var _useNodeSize:Boolean = true;
            private var _prevRoot:NodeSprite = null;

            /** The radius increment between depth levels. */
            public function get radiusIncrement():Number { return _radiusInc; }
            public function set radiusIncrement(r:Number):void { _radiusInc = r; }

            /** Flag determining if nodes should be sorted by angles to help
             *  maintain ordering across different spanning-tree configurations.
             *  This sorting is important for understandable transitions when using
             *  a radial layout of a general graph. However, it is unnecessary for
             *  tree structures and increases the running time of layout. */
            public function get sortAngles():Boolean { return _sortAngles; }
            public function set sortAngles(b:Boolean):void { _sortAngles = b; }

            /** Flag indicating if the layout should automatically be scaled to
             *  fit within the layout bounds. */
            public function get autoScale():Boolean { return _autoScale; }
            public function set autoScale(b:Boolean):void { _autoScale = b; }

            /** The initial angle for the radial layout (in radians). */
            public function get startAngle():Number { return _theta1; }
            public function set startAngle(a:Number):void {
                _theta2 += (a - _theta1);
                _theta1 = a;
                _setTheta = true;
            }

            /** The angular width of the layout (in radians, default is 2 pi). */
            public function get angleWidth():Number { return _theta1 - _theta2; }
            public function set angleWidth(w:Number):void {
                _theta2 = _theta1 - w;
                _setTheta = true;
            }

            /** Flag indicating if node's <code>size</code> property should be
             *  used to determine layout spacing. If a space-filling radial
             *  layout is desired, this value must be false for the layout
             *  to be accurate. */
            public function get useNodeSize():Boolean { return _useNodeSize; }
            public function set useNodeSize(b:Boolean):void {
                _useNodeSize = b;
            }

            // -- Methods ---------------------------------------------------------

            /**
             * Creates a new RadialTreeLayout.
             * @param radius the radius increment between depth levels
             * @param sortAngles flag indicating if nodes should be sorted by angle
             *  to maintain node ordering across spanning-tree configurations
             * @param autoScale flag indicating if the layout should automatically
             *  be scaled to fit within the layout bounds
             */
            public function RadialTreeLayout(radius:Number=DEFAULT_RADIUS,
                sortAngles:Boolean=true, autoScale:Boolean=true)
            {
                layoutType = POLAR;
                _radiusInc = radius;
                _sortAngles = sortAngles;
                _autoScale = autoScale;
            }

            /** @inheritDoc */
            protected override function layout():void
            {
                var n:NodeSprite = layoutRoot as NodeSprite;
                if (n == null) { _t = null; return; }
                var np:Params = params(n);

                // calc relative widths and maximum tree depth
                // performs one pass over the tree
                _maxDepth = 0;
                calcAngularWidth(n, 0);

                if (_autoScale) setScale(layoutBounds);
                if (!_setTheta) calcAngularBounds(n);
                _anchor = layoutAnchor;

                // perform the layout
                if (_maxDepth > 0) {
                    doLayout(n, _radiusInc, _theta1, _theta2);
                } else if (n.childDegree > 0) {
                    n.visitTreeDepthFirst(function(n:NodeSprite):void {
                        n.origin = _anchor;
                        var o:Object = _t.$(n);
                        // collapse to inner radius
                        o.radius = o.h = o.v = _radiusInc / 2;
                        o.alpha = 0;
                        o.mouseEnabled = false;
                        if (n.parentEdge != null)
                            _t.$(n.parentEdge).alpha = false;
                    });
                }

                // update properties of the root node
                np.angle = _theta2 - _theta1;
                n.origin = _anchor;
                update(n, 0, _theta1+np.angle/2, np.angle, true);
                if (!_t.immediate) {
                    delete _t._(n).values.radius;
                    delete _t._(n).values.angle;
                }
                _t.$(n).x = _anchor.x;
                _t.$(n).y = _anchor.y;

                updateEdgePoints(_t);
            }

            private function setScale(bounds:Rectangle):void
            {
                var r:Number = Math.min(bounds.width, bounds.height)/2.0;
                if (_maxDepth > 0) _radiusInc = r / _maxDepth;
            }

            /**
             * Calculates the angular bounds of the layout, attempting to
             * preserve the angular orientation of the display across transitions.
             */
            private function calcAngularBounds(r:NodeSprite):void
            {
                if (_prevRoot == null || r == _prevRoot)
                {
                    _prevRoot = r; return;
                }

                // try to find previous parent of root
                var p:NodeSprite = _prevRoot, pp:NodeSprite;
                while (true) {
                    pp = p.parentNode;
                    if (pp == r) {
                        break;
                    } else if (pp == null) {
                        _prevRoot = r;
                        return;
                    }
                    p = pp;
                }

                // compute offset due to children's angular width
                var dt:Number = 0;

                for each (var n:NodeSprite in sortedChildren(r)) {
                    if (n == p) break;
                    dt += params(n).width;
                }

                var rw:Number = params(r).width;
                var pw:Number = params(p).width;
                dt = -2*Math.PI * (dt+pw/2)/rw;

                // set angular bounds
                _theta1 = dt + Math.atan2(p.y-r.y, p.x-r.x);
                _theta2 = _theta1 + 2*Math.PI;
                _prevRoot = r;
            }

            /**
             * Computes relative measures of the angular widths of each
             * expanded subtree. Node diameters are taken into account
             * to improve space allocation for variable-sized nodes.
             *
             * This method also updates the base angle value for nodes
             * to ensure proper ordering of nodes.
             */
            private function calcAngularWidth(n:NodeSprite, d:int):Number
            {
                if (d > _maxDepth) _maxDepth = d;
                var aw:Number = 0, diameter:Number = 0;
                if (_useNodeSize && d > 0) {
                    //diameter = 1;
                    diameter = n.expanded && n.childDegree > 0 ? 0 : _t.$(n).size;
                } else if (d > 0) {
                    var w:Number = n.width, h:Number = n.height;
                    diameter = Math.sqrt(w*w+h*h)/d;
                    if (isNaN(diameter)) diameter = 0;
                }

                if (n.expanded && n.childDegree > 0) {
                    for (var c:NodeSprite=n.firstChildNode; c!=null; c=c.nextNode)
                    {
                        aw += calcAngularWidth(c, d+1);
                    }
                    aw = Math.max(diameter, aw);
                } else {
                    aw = diameter;
                }
                params(n).width = aw;
                return aw;
            }

            private static function normalize(angle:Number):Number
            {
                while (angle > 2*Math.PI)
                    angle -= 2*Math.PI;
                while (angle < 0)
                    angle += 2*Math.PI;
                return angle;
            }

            private function sortedChildren(n:NodeSprite):Array
            {
                var cc:int = n.childDegree;
                if (cc == 0) return Arrays.EMPTY;
                var angles:Array = new Array(cc);

                if (_sortAngles) {
                    // update base angle for node ordering
                    var base:Number = -_theta1;
                    var p:NodeSprite = n.parentNode;
                    if (p != null) base = normalize(Math.atan2(p.y-n.y, n.x-p.x));

                    // collect the angles
                    var c:NodeSprite = n.firstChildNode;
                    for (var i:uint=0; i<cc; ++i, c=c.nextNode) {
                        angles[i] = normalize(-base + Math.atan2(c.y-n.y,n.x-c.x));
                    }
                    // get array of indices, sorted by angle
                    angles = angles.sort(Array.NUMERIC | Array.RETURNINDEXEDARRAY);
                    // switch in the actual nodes and return
                    for (i=0; i<cc; ++i) {
                        angles[i] = n.getChildNode(angles[i]);
                    }
                } else {
                    for (i=0; i<cc; ++i) {
                        angles[i] = n.getChildNode(i);
                    }
                }

                return angles;
            }

            /**
             * Compute the layout.
             * @param n the root of the current subtree under consideration
             * @param r the radius, current distance from the center
             * @param theta1 the start (in radians) of this subtree's angular region
             * @param theta2 the end (in radians) of this subtree's angular region
             */
            private function doLayout(n:NodeSprite, r:Number,
                theta1:Number, theta2:Number):void
            {
                var dtheta:Number = theta2 - theta1;
                var dtheta2:Number = dtheta / 2.0;
                var width:Number = params(n).width;
                var cfrac:Number, nfrac:Number = 0;

                for each (var c:NodeSprite in sortedChildren(n)) {
                    var cp:Params = params(c);
                    cfrac = cp.width / width;
                    if (c.expanded && c.childDegree > 0)
                    {
                        doLayout(c, r+_radiusInc, theta1 + nfrac*dtheta,
                                                  theta1 + (nfrac+cfrac)*dtheta);
                    }
                    else if (c.childDegree > 0)
                    {
                        var cr:Number = r + _radiusInc;
                        var ca:Number = theta1 + nfrac*dtheta + cfrac*dtheta2;

                        c.visitTreeDepthFirst(function(n:NodeSprite):void {
                            n.origin = _anchor;
                            update(n, cr, minAngle(n.angle, ca), 0, false);
                        });
                    }

                    c.origin = _anchor;
                    var a:Number = minAngle(c.angle, theta1 + nfrac*dtheta + cfrac*dtheta2);
                    cp.angle = cfrac * dtheta;
                    update(c, r, a, cp.angle, true);
                    nfrac += cfrac;
                }
            }

            private function update(n:NodeSprite, r:Number, a:Number,
                                    aw:Number, v:Boolean) : void
            {
                var o:Object = _t.$(n), alpha:Number = v ? 1 : 0;
                o.radius = r;
                o.angle = a;
                if (aw == 0) {
                    o.h = o.v = r - _radiusInc/2;
                } else {
                    o.h = r + _radiusInc/2;
                    o.v = r - _radiusInc/2;
                }
                o.w = aw;
                o.u = a - aw/2;
                o.alpha = alpha;
                o.mouseEnabled = v;
                if (n.parentEdge != null)
                    _t.$(n.parentEdge).alpha = alpha;
            }

            private function params(n:NodeSprite):Params
            {
                var p:Params = n.props[PARAMS];
                if (p == null) {
                    p = new Params();
                    n.props[PARAMS] = p;
                }
                return p;
            }

        } // end of class RadialTreeLayout
    }

    class Params {
        public var width:Number = 0;
        public var angle:Number = 0;
    }