/*-
 * Copyright (c) 2009, Alexandre P. Francisco <aplf@ist.utl.pt>
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

package rank;

import cern.colt.GenericSorting;
import cern.colt.Swapper;
import cern.colt.function.IntComparator;
import cern.colt.list.IntArrayList;
import cern.colt.map.OpenIntDoubleHashMap;


public class Sweep {

	private final OpenIntDoubleHashMap rankVector;
	private int[] sortedIndex;

	private double bestScore;
	private int best;
	private int next;
	
	private int firstBest;
	private double firstBestScore;
	private final OpenIntDoubleHashMap core;
	private int coreCtl;
	
	private Cluster cl;

	public Sweep(WeightedImmutableGraph g, OpenIntDoubleHashMap v, double alpha, OpenIntDoubleHashMap c, double scale) {
		//graph = g;
		rankVector = v;

		bestScore = 0;
		best = -1;
		next = 0;

		firstBest = -1;
		firstBestScore = 0;
		core = c;
		coreCtl = c.size();
		
		cl = new Cluster(g, alpha);

		IntArrayList rankIndexList = rankVector.keys();
		sortedIndex = rankIndexList.elements();
		
		// (Re)normalize rank vector.
		for (int i = 0; i < sortedIndex.length; i++)
			rankVector.put(sortedIndex[i], rankVector.get(sortedIndex[i]) / g.outweight(sortedIndex[i]));
		
		Swapper swapper = new Swapper() {
			public void swap(int a, int b) {
				int t = sortedIndex[a];
				sortedIndex[a] = sortedIndex[b];
				sortedIndex[b] = t;
			}
		};
		
		IntComparator comp = new IntComparator() {
			public int compare(int a, int b) {
				return rankVector.get(sortedIndex[a]) >
					rankVector.get(sortedIndex[b]) ?
					-1 :
					rankVector.get(sortedIndex[a]) < 
					rankVector.get(sortedIndex[b]) ?
					1 : 
					(sortedIndex[a] < sortedIndex[b] ?
					 -1 :
					 (sortedIndex[a] == sortedIndex [b] ? 0 : 1));
			}
		};
	
		//LOGGER.info("Sorting...");
		GenericSorting.quickSort(0, sortedIndex.length, comp, swapper);
		
		/* Uncomment to print the ranking...
		System.out.println("Ranking:");
		for (int i = 0; i < sortedIndex.length; i++)
			System.out.println(sortedIndex[i] + " -> " + rankVector.get(sortedIndex[i]));
		System.out.println("---");
		*/
		
		while (next <= scale*c.size() && next < sortedIndex.length)
			expand();
	}

	public double getBestScore() {
		return bestScore;
	}

	public int getOptimalIndex() {
		return best;
	}
	
	public int getFirstBestIndex() {
		return firstBest;
	}
	
	public double getFirstBestScore() {
		return firstBestScore;
	}

	public int[] getSortedIndex() {
		return sortedIndex;
	}

	private void expand() {
		cl.add(sortedIndex[next]);
		
		double currScore = cl.getScore();

		if (coreCtl > 0) {
			bestScore = currScore;
			best = next;
			
			firstBest = next;
			firstBestScore = currScore;
		} else if (currScore >= bestScore) { // '<' or '<='... beta should take care of it...
			bestScore = currScore;
			best = next;
			
			if (firstBest == (next - 1)) {
				firstBest = next;
				firstBestScore = currScore;
			}
		}

		//LOGGER.debug("rank[" + next + "] -> (" + sortedIndex[next] + ", " + rankVector.getQuick(sortedIndex[next]) + ")");
		//LOGGER.debug("Volume: " + cl.getVolume() + " (" + graph.numArcs() + ")");
		//LOGGER.debug("Cut size: " + cl.getCutSize());
		//LOGGER.debug("Score: " + currScore + " (Min: " + bestScore + ")");

		if (core.containsKey(sortedIndex[next]))
			coreCtl --;
		
		next++;	
	}
}