    package flare.vis.operator.filter
    {
        import flare.animate.Transitioner;
        import flare.vis.data.Data;
        import flare.vis.data.DataSprite;
        import flare.vis.data.EdgeSprite;
        import flare.vis.data.NodeSprite;
        import flare.vis.data.Tree;
        import flare.vis.operator.Operator;

        /**
         * Filter operator that computes a fisheye degree-of-interest function over
         * a tree structure. Visibility and DOI (degree-of-interest) values are set
         * for the nodes and edges in the structure. This function includes a set
         * of focus nodes, and includes neighbors only in a limited window around
         * these foci. The size of this window is determined by this operator's
         * <code>distance</code> property. All ancestors of a focus up to the root
         * of the tree are considered foci as well. By convention, DOI values start
         * at zero for focus nodes, with decreasing negative numbers for each hop
         * away from a focus. The DOI values computed by this filter are stored in
         * the <code>DataSprite.props.doi</code> property.
         *
         * <p>This form of filtering was described by George Furnas as early as 1981.
         * For more information about Furnas' fisheye view calculation and DOI values,
         * take a look at G.W. Furnas, "The FISHEYE View: A New Look at Structured
         * Files," Bell Laboratories Tech. Report, Murray Hill, New Jersey, 1981.
         * Available online at <a href="http://citeseer.nj.nec.com/furnas81fisheye.html">
         * http://citeseer.nj.nec.com/furnas81fisheye.html</a>.</p>
         */
        public class FisheyeTreeFilter extends Operator
        {
            /** An array of focal NodeSprites. */
            public var focusNodes:/*NodeSprite*/Array;
            /** Graph distance within within which items wll be visible. */
            public var distance:int;

            private var _divisor:Number;
            private var _root:NodeSprite;
            private var _t:Transitioner;

            /**
             * Creates a new FisheyeTreeFilter
             * @param focusNodes focusNodes an array of focal NodeSprites. Graph
             *  distance is measured as the minimum number of edge-hops to one of
             *  these nodes or their ancestors up to the root.
             * @param distance graph distance within which items will be visible
             */
            public function FisheyeTreeFilter(focusNodes:Array=null,distance:int=1)
            {
                this.focusNodes = focusNodes;
                this.distance = distance;
            }

            /** @inheritDoc */
            public override function operate(t:Transitioner=null):void
            {
                _t = (t==null ? Transitioner.DEFAULT : t);
                var tree:Tree = visualization.tree;
                _divisor = tree.nodes.length;
                _root = tree.root;

                // mark the items
                visualization.data.visit(function(ds:DataSprite):void {
                    ds.props.doi = -Number.MAX_VALUE;
                });

                // compute the fisheye over nodes
                for each (var fn:NodeSprite in focusNodes) {
                    visitFocus(fn, null);
                }
                visitFocus(_root, null);

                // mark unreached items
                visualization.data.visit(function(ds:DataSprite):void {
                    if (ds.props.doi == -Number.MAX_VALUE)
                        setVisibility(ds, false);
                });
            }

            /**
             * Set the visibility of a data sprite.
             */
            private function setVisibility(ds:DataSprite, visible:Boolean):void
            {
                var alpha:Number = visible ? 1 : 0;
                var obj:Object = _t.$(ds);

                obj.alpha = alpha;
                if (ds is NodeSprite)
                    (ds as NodeSprite).expanded = (ds.props.doi > -distance);
                if (_t.immediate) {
                    ds.visible = visible;
                } else {
                    obj.visible = visible;
                }
            }

            /**
             * Visit a focus node.
             */
            private function visitFocus(n:NodeSprite, c:NodeSprite):void
            {
                if (n.props.doi <= -1 ) {
                    visit(n, c, 0, 0);
                    if (distance > 0) visitDescendants(n, c);
                    visitAncestors(n);
                }
            }

            /**
             * Visit a specific node and update its degree-of-interest.
             */
            private function visit(n:NodeSprite, c:NodeSprite, doi:int, ldist:int):void
            {
                setVisibility(n, true);
                var localDOI:Number = -ldist / Math.min(1000.0, _divisor);
                n.props.doi = doi + localDOI;

                if (c != null) {
                    var e:EdgeSprite = c.parentEdge;
                    e.props.doi = c.props.doi;
                    setVisibility(e, true);
                }
            }

            /**
             * Visit tree ancestors and their other descendants.
             */
            private function visitAncestors(n:NodeSprite):void
            {
                if (n == _root) return;
                visitFocus(n.parentNode, n);
            }

            /**
             * Traverse tree descendents.
             */
            private function visitDescendants(p:NodeSprite, skip:NodeSprite):void
            {
                var lidx:int = (skip == null ? 0 : skip.parentIndex);

                p.expanded = p.childDegree > 0;
                for (var i:int=0; i<p.childDegree; ++i) {
                    var c:NodeSprite = p.getChildNode(i);
                    if (c == skip) continue;

                    var doi:int = int(p.props.doi - 1);
                    visit(c, c, doi, Math.abs(lidx-i));
                    if (doi > -distance) visitDescendants(c, null);
                }
            }

        } // end of class FisheyeTreeFilter
    }