    package flare.analytics.cluster
    {
        import flare.util.Arrays;
        import flare.util.Property;
        import flare.util.Sort;
        import flare.vis.data.Data;
        import flare.vis.data.DataList;
        import flare.vis.data.EdgeSprite;
        import flare.vis.data.NodeSprite;
        import flare.vis.data.Tree;
        import flare.vis.operator.Operator;

        /**
         * Base class for clustering operators that construct a hierarchical
         * clustering tree. Provides methods for taking a sequence of
         * merge operations by a clustering algorithm and constructing a
         * resulting cluster tree.
         *
         * <p>Once a clustering has been computed, each node included in the
         * analysis will be annotated with both its cluster membership
         * using the name indicated by the <code>clusterField</code> property.
         * By default, this class will attempt to pick an optimal level of the
         * cluster tree at which to break up items into discrete clusters.
         * However, clients can invoke the <code>labelNodes</code> method with
         * a specific merge number which indicates the point at which to "cut"
         * the cluster tree into discrete sub-clusters. This class also annotates
         * nodes with a sequence number using the name indicated by the
         * <code>sequenceField</code> property. The sequence number allows items
         * to be sorted in a way that attempts to preserve the clustered structure.
         * Additionally, the <code>clusterTree</code> property will return a
         * <code>flare.vis.data.Tree</code> instance that can be used to
         * visualize the structure of the cluster tree.</p>
         */
        public class HierarchicalCluster extends Operator
        {
            /** @private */
            protected var _idx:Property = Property.$("props.sequence");
            /** @private */
            protected var _com:Property = Property.$("props.cluster");

            /** @private */
            protected var _qvals:Array;
            /** @private */
            protected var _merges:MergeEdge;
            /** @private */
            protected var _size:int;
            /** @private */
            protected var _tree:Tree;
            /** @private */
            protected var _group:String = Data.NODES;

            /** The data group to cluster. */
            public function get group():String { return _group; }
            public function set group(g:String):void { _group = g; }

            /** The property in which to store cluster indices. This property
             *  is used to annotate nodes with the community they belong to
             *  (indicated as an integer index). The default value
             *  is "props.cluster". */
            public function get clusterField():String { return _com.name; }
            public function set clusterField(f:String):void { _com = Property.$(f); }

            /** The property in which to store sequence indices. This property
             *  is used to annotate nodes with their sequence index along the
             *  computed cluster tree. This value can be used to sort the nodes
             *  in a way that best preserves community structure. The default value
             *  is "props.sequence". */
            public function get sequenceField():String { return _idx.name; }
            public function set sequenceField(f:String):void { _idx = Property.$(f); }

            /** Computed criterion values for each merge in the cluster tree. */
            public function get criteria():Array { return _qvals; }

            /** The cluster tree of detected community structures. The leaf nodes
             *  correspond to each of the nodes in the input graph, and include the
             *  same <code>data</code> property. Non-leaf nodes indicate merges
             *  made by the clustering algorithm, and have <code>data</code>
             *  properties that include the <code>merge</code> number (1 for the
             *  first merger, 2 for the second, etc), the <code>criterion</code>
             *  value computed for that merge, and the <code>size</code> of the
             *  cluster rooted at that node (the number of descendants in the
             *  cluster tree).
             */
            public function get clusterTree():Tree { return _tree; }

            // --------------------------------------------------------------------

            /**
             * Creates a new HierarchicalCluster instance.
             */
            public function HierarchicalCluster()
            {
                super();
            }

            /**
             * Labels nodes with their cluster membership, determined by
             * the given merge number. If the merge number is less than
             * zero or unprovided, the merge number that maximizes the
             * clustering criteria will be assumed.
             * @param merge the merge number at which to compute the clusters
             */
            public function labelNodes(merge:int=-1):void
            {
                if (merge < 0) merge = Arrays.maxIndex(_qvals);
                var com:int, idx:int;
                var helper:Function = function(n:NodeSprite):void
                {
                    var nn:NodeSprite;
                    if (n.childDegree && n.data.merge > merge)
                    {
                        for (var i:int=0; i<n.childDegree; ++i)
                            helper(n.getChildNode(i));
                    }
                    else if (n.childDegree)
                    {
                        n.visitTreeDepthFirst(function(c:NodeSprite):void {
                            if (c.childDegree==0) {
                                nn = c.props.node;
                                _com.setValue(nn, com);
                                _idx.setValue(nn, idx++);
                            }
                        });
                        com++;
                    }
                    else
                    {
                        nn = n.props.node;
                        _com.setValue(nn, com++);
                        _idx.setValue(nn, idx++);
                    }
                }
                helper(_tree.root);
            }

            /**
             * @private
             * Constructs the cluster tree from the cluster results
             */
            protected function buildTree(list:DataList):Tree
            {
                var tree:Tree = new Tree();

                var e:MergeEdge, i:int, j:int, ii:int, map:Object = {};
                var l:NodeSprite, r:NodeSprite, p:NodeSprite;

                // populate the leaf notes
                for (i=0; i<_size; ++i) {
                    map[i] = (p = new NodeSprite());
                    p.data = list[i].data;
                    p.props.node = list[i];
                    p.props.size = 0;
                }

                // build up the tree
                for (ii=0, e=_merges.next; e!=null; ++ii, e=e.next) {
                    i = e.i;
                    j = e.j;
                    l = map[i];
                    r = map[j];
                    map[i] = (p = new NodeSprite());
                    if (l.props.size >= r.props.size) {
                        p.addChildEdge(new EdgeSprite(p, l));
                        p.addChildEdge(new EdgeSprite(p, r));
                    } else {
                        p.addChildEdge(new EdgeSprite(p, r));
                        p.addChildEdge(new EdgeSprite(p, l));
                    }
                    p.data.merge = ii + 1;
                    p.data.criterion = _qvals[ii];
                    p.props.size = 2 + l.props.size + r.props.size;
                    delete map[j];
                }

                // build and sort array of cluster roots
                var roots:Array = [];
                for each (var n:NodeSprite in map) roots.push(n);
                roots.sort(Sort.$("-props.size"));

                // merge cluster roots into final tree, if needed
                if (roots.length == 1) {
                    p = NodeSprite(roots[0]);
                } else {
                    p = new NodeSprite();
                    p.data.merge = ii;
                    for each (n in roots) {
                        p.addChildEdge(new EdgeSprite(p, n));
                    }
                }
                tree.root = p;
                return tree;
            }

        } // end of class HierarchicalCluster
    }