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
}