package weka.clusterers.forMetisMQI.coarse;

import java.io.PrintStream;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import weka.clusterers.forMetisMQI.graph.Edge;
import weka.clusterers.forMetisMQI.graph.Node;
import weka.clusterers.forMetisMQI.graph.UndirectedGraph;

import edu.uci.ics.jung.graph.util.Pair;

public class Coarse {
	
	private static boolean debug = false;
	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(Map<Node,Node> match, Node v) {
		if(match.containsKey(v))
			return !match.get(v).equals(v);
		else
			return false;
	}

	private static void RMMatch(UndirectedGraph g, Map<Node,Node> match, Map<Node,Node> map) {
		int labelCounter = 0;
		Iterator<Node> nodeIterator = g.vtxsPermutation().iterator();
		while (nodeIterator.hasNext()) {
			Node u = nodeIterator.next();
			if (debug)
				debugStream.println("Visiting node " + u + " Matched = " + isMatched(match,u));
			if (!isMatched(match,u)) {
				boolean foundMatch = false;
				Node matchedNode = null;
				Iterator<Node> iterator = g.getNeighborsPermutation(u).iterator();
				while(iterator.hasNext() && !foundMatch){
					Node v = iterator.next();
					if (!isMatched(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.");
				Node newNode = new Node(Integer.toString(labelCounter));
				if(foundMatch) {
					match.put(u, matchedNode);
					match.put(matchedNode, u);
					map.put(u, newNode);
					map.put(matchedNode, newNode);
					if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + getMappedNode(map, u));
				} else {
					match.put(u, u);
					map.put(u, newNode);
					if(debug) debugStream.println("Node " + u + " with " + " new node id: " + getMappedNode(map, u));
				}
				labelCounter++;
			}
		}
	}
	
	private static Node getMatchedNode(Map<Node,Node> match, Node u) {
		return match.get(u);
	}
	
	private static Node getMappedNode(Map<Node,Node> map, Node u) {
		return map.get(u);
	}
	
	/**
	 * Return a new contracted graph.
	 */
	private static UndirectedGraph contract(UndirectedGraph g, Map<Node,Node> match, Map<Node,Node> map) {
		UndirectedGraph output = new UndirectedGraph();
		Iterator<Node> iterator = g.getVertices().iterator();
		int i = 0;
		while(iterator.hasNext()) {
			Node u = iterator.next();
			output.addVertex(getMappedNode(map,u));
			
			Set<Node> neighbors = new HashSet<Node>();
			Iterator<Node> it = g.getNeighbors(u).iterator();
			while(it.hasNext())
				neighbors.add(getMappedNode(map, it.next()));
			it = g.getNeighbors(getMatchedNode(match, u)).iterator();
			while(it.hasNext())
				neighbors.add(getMappedNode(map, it.next()));
			neighbors.remove(getMappedNode(map,u));
			it = neighbors.iterator();
			while(it.hasNext()) {
				Node v = it.next();
				output.addVertex(v);
				output.addEdge(new Edge(Integer.toString(i),0,0),getMappedNode(map,u), v);
				i++;
			}
		}
		
		//calcolo dei pesi del nuovo grafo: per ogni arco (u,v) && u < v.
		//w(map(u),map(v)) += w(u,v).
		
		Iterator<Edge> edgeIterator = g.getEdges().iterator();
		while(edgeIterator.hasNext()) {
			Edge oldEdge = edgeIterator.next();
			Pair<Node> srcDst = g.getEndpoints(oldEdge);
			Node src = srcDst.getFirst();
			Node dst = srcDst.getSecond();
			Node srcMapped = getMappedNode(map, src);
			Node dstMapped = getMappedNode(map, dst);
			if(!srcMapped.equals(dstMapped) && output.containsEdge(srcMapped, dstMapped)) {
				Edge newEdge = output.findEdge(srcMapped, dstMapped);
				newEdge.setWeight(newEdge.getWeight() + oldEdge.getWeight());
			}
		}
		iterator = g.getVertices().iterator();
		Set<Node> nodesComplete = new HashSet<Node>();
		while(iterator.hasNext()) {
			Node u = iterator.next();
			if(isMatched(match,u)) {
				Node v = getMatchedNode(match,u);
				if(!nodesComplete.contains(u)) {
					getMappedNode(map,u).setVwgt(u.getVwgt() + v.getVwgt());
					getMappedNode(map,u).setCewgt(u.getCewgt() + v.getCewgt() + g.findEdge(u, v).getWeight());
					nodesComplete.add(u);
					nodesComplete.add(v);
				}
			} else {
				getMappedNode(map,u).setVwgt(u.getVwgt());
				getMappedNode(map,u).setCewgt(u.getCewgt());
			}
		}
		return output;
	}

	/**
	 * Performs the first stage of the METIS algorithm, using RM.
	 */
	private static CoarserGraphElement coarseOneStep(UndirectedGraph g) {
		UndirectedGraph projected = g;
		UndirectedGraph contracted = null;
		Map<Node,Node> match = new HashMap<Node,Node>();
		Map<Node,Node> map = new HashMap<Node,Node>();
		RMMatch(g,match,map);
		contracted = contract(g,match,map);
		return new CoarserGraphElement(contracted, projected, match, map);
	}

	
	/**
	 * Performs at least one contraction of the given the graph, and goes on until the graph
	 * is under the desidered size (see setFinerSize()).
	 * @param g
	 * @return the stack of contracted graphs
	 */
	public static Stack<CoarserGraphElement> coarse(UndirectedGraph g) {
		Stack<CoarserGraphElement> stack = new Stack<CoarserGraphElement>();
		CoarserGraphElement e = null;
		UndirectedGraph curr = g;
		int i = 0;
		
	    do {
	    	if(debug)
	    		debugStream.println("--------CONTRACTION-nr" + i +"------------------------------");
	    	e = coarseOneStep(curr);
	    	stack.push(e);
	    	curr = e.getContracted();
	    	if(debug) {
	    		debugStream.println("-----------EXPANDED----------------------------------");
	    		debugStream.println(e.getProjected().toString());
	    		debugStream.println("-----------CONTRACTED--------------------------------");
	    		debugStream.println(e.getContracted().toString());
	    	}
	    	i++;
	    } while(e.getProjected().getVertexCount() > e.getContracted().getVertexCount() && e.getContracted().getVertexCount() > finerSize);
	    return stack;
	}

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