package weka.clusterers.forMetisMQI;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.Map.Entry;

import weka.clusterers.forMetisMQI.Graph.NodeInfo;

public class Subgraph {
	
	private Graph g = null;
	private BitSet nodes = null;
	private List<Integer> listOfNodes = null;
	private HashMap<Integer,Integer> ID = null;
	private HashMap<Integer,Integer> ED = null;
	private HashMap<Integer,List<Integer>> bucketGain = null;
	private SortedSet<Integer> gainSet = null;
	private boolean recomputeGain = true;
	
	public Subgraph(Graph g){
		this.g = g;
		nodes = new BitSet(g.size());
		listOfNodes = new ArrayList<Integer>();
		ID = new HashMap<Integer,Integer>();
		ED = new HashMap<Integer,Integer>();
		bucketGain = new HashMap<Integer, List<Integer>>();
		gainSet = new TreeSet<Integer>();
	}
	
	public Graph getGraph() {
		return g;
	}
	
	public void addNode(int u) {
		nodes.set(g.getIndex(u));
		listOfNodes.add(u);
		ID.put(u, 0);
		ED.put(u, 0);
		recomputeGain = true;
	}
	
	private void computeDegree() {
		for(int i = 0; i < size(); i++) {
			int u = listOfNodes.get(i);
			Iterator<Integer> it = g.getNeighbors(u).iterator();
			int newID = 0;
			int newED = 0;
			while(it.hasNext()) {
				int v = it.next();
				if(contains(v))
					newID = newID + g.getWeight(u, v);
				else
					newED = newED + g.getWeight(u, v);
				ID.put(u, newID);
				ED.put(u, newED);
			}
		}
	}
	
	private void computeGain() {
		bucketGain.clear();
		gainSet.clear();
		ID.clear();
		ED.clear();
		computeDegree();
		for(int i = 0; i < size(); i++) {
			int u = listOfNodes.get(i);
			int gainU = ED.get(u) - ID.get(u);
			if(!bucketGain.containsKey(gainU)) {
				bucketGain.put(gainU, new ArrayList<Integer>());
			}
			bucketGain.get(gainU).add(u);
			gainSet.add(gainU);
		}
		recomputeGain = false;
	}
	
	public int getCandidate() {
		return getCandidate(new ArrayList<Integer>());
	}
	
	/**
	 * 
	 * @param marked 
	 * @return the candidate node for swap or -1 if there aren't available nodes.
	 */
	public int getCandidate(List<Integer> marked) {
		if(recomputeGain)
			computeGain();
		int candidate = -1;
		Iterator<Integer> iterator = ((TreeSet<Integer>)gainSet).descendingIterator();
		while(iterator.hasNext() && (candidate == -1)) {
			int gain = iterator.next();
			Iterator<Integer> nodes = bucketGain.get(gain).iterator();
			while(nodes.hasNext() && (candidate == -1)) {
				int u = nodes.next();
				if(!marked.contains(u))
					candidate = u;
			}
		}
		return candidate;
	}
	
	public int gain(int u){
		if(recomputeGain)
			computeGain();
		return ED.get(u) - ID.get(u);
	}
	
	public void remove(int u) {
		if(recomputeGain)
			computeGain();
		int gainU = gain(u);
		nodes.set(g.getIndex(u), false);
		listOfNodes.remove(listOfNodes.indexOf(u));
		ID.remove(u);
		ED.remove(u);
		List<Integer> l = bucketGain.get(gainU);
		l.remove(l.indexOf(u));
		if(l.size() == 0) {
			bucketGain.remove(gainU);
			gainSet.remove(gainU);
		}
		recomputeGain = true;
	}
	
	public int size() {
		return listOfNodes.size();
	}
	
	public Iterator<Integer> iterator() {
		return listOfNodes.iterator();
	}
	
	public boolean isEdge(int u, int v) {
		return nodes.get(g.getIndex(u)) && nodes.get(g.getIndex(v)) && g.isEdge(u, v);
	}
	
	public boolean contains(int u) {
		return nodes.get(g.getIndex(u));
	}
	
	public List<Integer> getNeighbours(int u) {
		List<Integer> neighbors = new ArrayList<Integer>();
		Iterator<Integer> iterator = g.getNeighbors(u).iterator(); 
		while(iterator.hasNext()) {
			int v = iterator.next();
			if(contains(v) && isEdge(u, v))
				neighbors.add(v);
		}
		return neighbors;
	}
	
	public int getExternalDegree() {
		if(recomputeGain)
			computeGain();
		int acc = 0;
		Iterator<Integer> it = ED.values().iterator();
		while(it.hasNext())
			acc = acc + it.next();
		return acc;
	}
	
	@Override
	public String toString() {
		String out = "[";
		Iterator<Integer> it = listOfNodes.iterator();
		while(it.hasNext()) {
			int u = it.next();
			out = out + u + ",";
		}
		out = out + "]";
		return out;
	}
	
	public List<Integer> getBoundary() {
		if(recomputeGain)
			computeGain();
		Iterator<Entry<Integer,Integer>> EDIterator = ED.entrySet().iterator();
		List<Integer> boundary = new ArrayList<Integer>();
		while(EDIterator.hasNext()) {
			Entry<Integer,Integer> entry = EDIterator.next();
			if(entry.getValue() > 0)
				boundary.add(entry.getKey());
		}
		return boundary;
	}
	
	private Subgraph() {
		
	}
	
	@Override
	public Subgraph clone() {
		Subgraph clone = new Subgraph();
		clone.g = g.clone();
		
		clone.nodes = (BitSet)nodes.clone();
		
		clone.listOfNodes = new ArrayList<Integer>();
		for(int i = 0; i < listOfNodes.size(); i++) {
			clone.listOfNodes.add(listOfNodes.get(i));
		}
		
		clone.ID = new HashMap<Integer, Integer>();
		Iterator<Entry<Integer,Integer>> i = ID.entrySet().iterator();
		while(i.hasNext()) {
			Entry<Integer,Integer> entry = i.next();
			clone.ID.put(entry.getKey(), entry.getValue());
		}
		
		clone.ED = new HashMap<Integer, Integer>();
		i = ED.entrySet().iterator();
		while(i.hasNext()) {
			Entry<Integer,Integer> entry = i.next();
			clone.ED.put(entry.getKey(), entry.getValue());
		}
		
		clone.bucketGain = new HashMap<Integer, List<Integer>>();
		Iterator<Entry<Integer,List<Integer>>>it = bucketGain.entrySet().iterator();
		while(it.hasNext()) {
			Entry<Integer,List<Integer>> entry = it.next();
			List<Integer> bucketClone = new ArrayList<Integer>();
			List<Integer> bucket = entry.getValue();
			for(int j = 0; j < bucket.size(); j++) {
				bucketClone.add(bucket.get(j));
			}
			clone.bucketGain.put(entry.getKey(), bucketClone);
		}
		
		clone.gainSet = new TreeSet<Integer>();
		Iterator<Integer> gainIt = gainSet.iterator();
		while(gainIt.hasNext()) {
			gainSet.add(gainIt.next());
		}
		
		clone.recomputeGain = recomputeGain;
		
		return clone;
	}
}