package weka.clusterers.forMetisMQI;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.Stack;

public class Coarse {
	
	private static boolean debug = true;
	private static PrintStream debugStream = System.err;
	private static int finerSize = 5;

	/**
	 * Return true if the vertex v is matched
	 * 
	 * @param g graph
	 * @param v
	 *            the index of the vertex
	 * @return true if the vertex v is matched, false o.w.
	 */
	private static boolean isMatched(Graph g, List<Integer> match, int v) {
		return match.get(g.getIndex(v)) != g.getIndex(v);
	}

	private static void RMMatch(Graph g, List<Integer> match, List<Integer> map) {
		int labelCounter = 0;
		for (int i = 0; i < g.size(); i++) {
			match.add(i);
			map.add(i);
		}
		g.adjncyPermutation();
		Iterator<Integer> nodeIterator = g.vtxsPermutation().iterator();
		while (nodeIterator.hasNext()) {
			int u = nodeIterator.next();
			if (debug)
				debugStream.println("Visiting node " + u + " Matched = " + isMatched(g,match,u));
			if (!isMatched(g,match,u)) {
				boolean foundMatch = false;
				int matchedNode = -1;
				Iterator<Integer> iterator = g.getNeighbors(u).iterator();
				while(iterator.hasNext() && !foundMatch){
					int v = iterator.next();
					if (!isMatched(g,match,v)) {
						matchedNode = v;
						foundMatch = true;
						if (debug)
							debugStream.println("Found a match with node "
									+ matchedNode);
					}
				}
				if (debug && !foundMatch)
					debugStream.println("There aren't unmatched neighbors.");
				if(foundMatch) {
					match.set(g.getIndex(u), g.getIndex(matchedNode));
					match.set(g.getIndex(matchedNode), g.getIndex(u));
					map.set(g.getIndex(u), labelCounter);
					map.set(g.getIndex(matchedNode), labelCounter);
					if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + getMappedNode(g, map, u));
				} else {
					map.set(g.getIndex(u), labelCounter);
					if(debug) debugStream.println("Node " + u + " with " + " new node id: " + getMappedNode(g, map, u));
				}
				labelCounter++;
			}
		}
	}
	
	private static int getMatchedNode(Graph g, List<Integer> match, int u) {
		return g.getLabel(match.get(g.getIndex(u)));
	}
	
	private static int getMappedNode(Graph g, List<Integer> map, int u) {
		return map.get(g.getIndex(u));
	}
	
	/**
	 * Return a new contracted graph.
	 */
	private static Graph contract(Graph g, List<Integer> match, List<Integer> map) {
		Graph output = new Graph();
		Iterator<Integer> iterator = g.iterator();
		while(iterator.hasNext()) {
			int u = iterator.next();
			output.addNode(getMappedNode(g,map,u));
			Iterator<Integer> it = g.getNeighbors(u).iterator();
			Set<Integer> neighbors = new HashSet<Integer>();
			while(it.hasNext()) {
				int v = it.next();
				neighbors.add(getMappedNode(g,map,v));
			}
			it = g.getNeighbors(getMatchedNode(g,match,u)).iterator();
			while(it.hasNext()) {
				int v = it.next();
				neighbors.add(getMappedNode(g,map,v));
			}
			neighbors.remove(getMappedNode(g,map,u));
			it = neighbors.iterator();
			while(it.hasNext()) {
				int v = it.next();
				output.addNode(v);
				output.addEdgeUndirected(getMappedNode(g,map,u), v, 0);
			}
		}	
		//calcolo dei pesi del nuovo grafo: per ogni arco (u,v) && u < v.
		//w(map(u),map(v)) += w(u,v). 
		for(int i=0; i < g.size(); i++) {
			int u = g.getLabel(i);
			Iterator<Integer> it = g.getNeighbors(u).iterator();
			while(it.hasNext()) {
				int v = it.next();
				if(getMappedNode(g,map,u) != getMappedNode(g,map,v) && output.isEdge(getMappedNode(g,map,u), getMappedNode(g,map,v)) && u < v) {
					output.setWeight(getMappedNode(g,map,u), getMappedNode(g,map,v), output.getWeight(getMappedNode(g,map,u), getMappedNode(g,map,v)) + g.getWeight(u, v));
				}
			}
		}
		for(int i=0; i < g.size(); i++) {
			int u = g.getLabel(i);
			if(isMatched(g,match,u)) {
				int v = getMatchedNode(g,match,u);
				if(u < v) {
					output.getNode(getMappedNode(g,map,u)).vwgt = g.getNode(u).vwgt + g.getNode(v).vwgt;
					output.getNode(getMappedNode(g,map,u)).cewgt = g.getNode(u).cewgt + g.getNode(v).cewgt +
					g.getWeight(u, v);
					output.getNode(getMappedNode(g,map,u)).adjwgt = g.getNode(u).adjwgt + g.getNode(v).adjwgt - 2 *
					g.getWeight(u, v);
				}
			} else {
				output.getNode(getMappedNode(g,map,u)).vwgt = g.getNode(u).vwgt;
				output.getNode(getMappedNode(g,map,u)).cewgt = g.getNode(u).cewgt;
				output.getNode(getMappedNode(g,map,u)).adjwgt = g.getNode(u).adjwgt;
			}
		}
		return output;
	}

	/**
	 * Performs the first stage of the METIS algorithm, using RM.
	 */
	public static CoarserGraphElement coarseOneStep(Graph g) {
		Graph projected = g;
		Graph contracted = null;
		List<Integer> match = new ArrayList<Integer>();
		List<Integer> map = new ArrayList<Integer>();
		RMMatch(g,match,map);
		contracted = contract(g,match,map);
		return new CoarserGraphElement(contracted, projected, match, map);
	}
	
	public static Stack<CoarserGraphElement> coarse(Graph g) {
		Stack<CoarserGraphElement> stack = new Stack<CoarserGraphElement>();
		CoarserGraphElement e;
		Graph curr = g;
	    do {
	    	if(debug)
	    		debugStream.println("-----------------------------------------------------");
	    	e = coarseOneStep(curr);
	    	stack.push(e);
	    	curr = e.getContracted();
	    	if(debug)
	    		debugStream.println("-----------------------------------------------------");
	    } while(e.getProjected().size() > e.getContracted().size() && e.getContracted().size() > finerSize);
	    return stack;
	}

	public static void setFinerSize(int i) {
		finerSize = i;
	}
}