package flare.analytics.cluster
{
    import flare.animate.Transitioner;
    import flare.util.math.IMatrix;
    import flare.vis.data.Data;
    import flare.vis.data.DataList;
    
    /**
     * Hierarchically clusters a set of items using agglomerative clustering.
     * This approach continually merges the most similar items (those with the
     * minimum distance between them) into clusters, until all items have been
     * merged into a final resulting cluster tree. Clients must provide a
     * distance function that takes as input two <code>DataSprite</code>
     * instances and returns a <code>Number</code>.
     * <p>This class supports both <i>minimum-link</i> clustering, in which the
     * distance between clusters is measured as the distance between the two
     * nearest items in each cluster, and <i>maximum-link</i> clustering, in
     * which distance is measured using the two furthest items in each cluster.
     * </p>
     * <p>For a richer description, see
     * <a href="http://en.wikipedia.org/wiki/Cluster_analysis#Agglomerative_hierarchical_clustering">
     * the Wikipedia article on Cluster Analysis</a>.
     * </p>
     */
    public class AgglomerativeCluster extends HierarchicalCluster
    {        
        /** A function defining distances between items. */
        public var distance:Function = null;
        
        /** If true, minimum-link distances are computed between clusters.
         *  If false, maximum-link distances are computed between clusters. */
        public var minLink:Boolean = true;

        // --------------------------------------------------------------------
        
        /**
         * Creates a new agglomerative cluster instance
         */
        public function AgglomerativeCluster(group:String=Data.NODES)
        {
            this.group = group;
        }
        
        /** @inheritDoc */
        public override function operate(t:Transitioner=null):void
        {
            calculate(visualization.data.group(group), distance);
        }
        
        /**
         * Calculates the community structure clustering. As a result of this
         * method, a cluster tree will be computed and graph nodes will be
         * annotated with both community and sequence indices.
         * @param list a data list to cluster
         * @param d a distance function
         */
        public function calculate(list:DataList, d:Function):void
        {
            compute(list.distanceMatrix(d));
            _tree = buildTree(list);
            labelNodes();
        }
        
        /** Computes the clustering */
        private function compute(Z:IMatrix):void
        {
            _merges = new MergeEdge(-1, -1);
            _qvals = [];
            _size = Z.rows;
            
            var m:MergeEdge = _merges;
            var i:uint, j:uint, k:int, s:int, t:int, ii:uint, jj:uint;
            var min:Number, a:uint, b:uint, bb:uint, imax:int;
            var v:Number, sum:Number=0, Q:Number=0, Qmax:Number=0, dQ:Number;
            
            // initialize matrix
            var N:int = Z.rows;
            var idx:/*int*/Array = new Array(N);
            for (i=0; i<N; ++i) {
                idx[i] = i;
                Z.set(i,i,Number.POSITIVE_INFINITY);
            }
            
            // run the clustering algorithm
            for (var iter:int=0; iter<N-1; ++iter) {
                // find the nodes to merge
                min = Number.MAX_VALUE;
                for (ii=0; ii<idx.length; ++ii) {
                    i = idx[ii];
                    for (jj=ii+1; jj<idx.length; ++jj) {
                        j = idx[jj];
                        v = Z.get(i,j);
                        if (v < min) {
                            min = v;
                            a = i;
                            b = j; bb = jj;
                        }
                    }
                }
                i = a; j = b; jj = bb;
                
                // perform merge on graph
                for (k=0; k<N; ++k) {
                    if (minLink) {
                        v = Math.min(Z.get(i,k), Z.get(j,k)); // min link
                    } else {
                        v = Math.max(Z.get(i,k), Z.get(j,k)); // max link
                    }
                    Z.set(i, k, v);
                    Z.set(k, i, v);
                }
                for (k=0; k<N; ++k) {
                    Z.set(j, k, Number.POSITIVE_INFINITY);
                    Z.set(k, j, Number.POSITIVE_INFINITY);
                }
                idx.splice(jj, 1);
                
                Q += min;
                if (Q > Qmax) {
                    Qmax = Q;
                    imax = iter;
                }
                _qvals.push(Q);
                m = m.add(new MergeEdge(i,j));
            }
        }
        
    } // end of class AgglomerativeCluster
}