package weka.clusterers.forMetisMQI.graph;

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

import edu.uci.ics.jung.algorithms.filters.FilterUtils;


public class Subgraph {
	
	private UndirectedGraph g = null;
	
	private Set<Node> nodes = null;
	
	private HashMap<Node,Integer> ID = null;
	private HashMap<Node,Integer> ED = null;
	private HashMap<Integer,List<Node>> bucketGain = null;
	private SortedSet<Integer> gainSet = null;
	private boolean recomputeGain = true;
	
	public Subgraph(UndirectedGraph g){
		this.g = g;
		nodes = new HashSet<Node>();
		ID = new HashMap<Node,Integer>();
		ED = new HashMap<Node,Integer>();
		bucketGain = new HashMap<Integer, List<Node>>();
		gainSet = new TreeSet<Integer>();
	}
	
	public Subgraph(UndirectedGraph g, Set<Node> nodes) {
		this.g = g;
		this.nodes = new HashSet<Node>();
		this.ID = new HashMap<Node,Integer>();
		this.ED = new HashMap<Node,Integer>();
		this.bucketGain = new HashMap<Integer, List<Node>>();
		this.gainSet = new TreeSet<Integer>();
		Iterator<Node> nodesIterator = nodes.iterator();
		while(nodesIterator.hasNext()) {
			addVertex(nodesIterator.next());
		}
	}
	
	public UndirectedGraph getGraph() {
		return g;
	}
	
	/**
	 * Adds to the subgraph the node u iff u belongs to the graph.
	 * @param u
	 */
	public void addVertex(Node u) {
		if(g.containsVertex(u)) {
			nodes.add(u);
			ID.put(u, 0);
			ED.put(u, 0);
			recomputeGain = true;
		}
	}
	
	private void computeDegree() {
		Iterator<Node> subgraphIterator = nodes.iterator();
		while(subgraphIterator.hasNext()) {
			Node u = subgraphIterator.next();
			Iterator<Node> nborsIterator = g.getNeighbors(u).iterator();
			int newID = 0;
			int newED = 0;
			while(nborsIterator.hasNext()) {
				Node v = nborsIterator.next();
				if(contains(v))
					newID = newID + g.findEdge(u, v).getWeight();
				else
					newED = newED + g.findEdge(u, v).getWeight();
			}
			ID.put(u, newID);
			ED.put(u, newED);
		}
	}
	
	private void computeGain() {
		bucketGain.clear();
		gainSet.clear();
		ID.clear();
		ED.clear();
		computeDegree();
		Iterator<Node> subgraphIterator = nodes.iterator();
		while(subgraphIterator.hasNext()) {
			Node u = subgraphIterator.next();
			int gainU = ED.get(u) - ID.get(u);
			if(!bucketGain.containsKey(gainU)) {
				bucketGain.put(gainU, new ArrayList<Node>());
			}
			bucketGain.get(gainU).add(u);
			gainSet.add(gainU);
		}
		recomputeGain = false;
	}
	
	public Node getCandidate() {
		return getCandidate(new HashSet<Node>());
	}
	
	/**
	 * 
	 * @param marked 
	 * @return the candidate node for swap or <code>null</code> if there aren't available nodes.
	 */
	public Node getCandidate(Set<Node> marked) {
		if(recomputeGain)
			computeGain();
		Node candidate = null;
		Iterator<Integer> iterator = ((TreeSet<Integer>)gainSet).descendingIterator();
		while(iterator.hasNext() && (candidate == null)) {
			int gain = iterator.next();
			Iterator<Node> nodes = bucketGain.get(gain).iterator();
			while(nodes.hasNext() && (candidate == null)) {
				Node u = nodes.next();
				if(!marked.contains(u))
					candidate = u;
			}
		}
		return candidate;
	}
	
	public int gain(Node u){
		if(recomputeGain)
			computeGain();
		return ED.get(u) - ID.get(u);
	}
	
	public void removeVertex(Node u) {
		if(recomputeGain)
			computeGain();
		int gainU = gain(u);
		nodes.remove(u);
		ID.remove(u);
		ED.remove(u);
		List<Node> l = bucketGain.get(gainU);
		l.remove(l.indexOf(u));
		if(l.size() == 0) {
			bucketGain.remove(gainU);
			gainSet.remove(gainU);
		}
		recomputeGain = true;
	}
	
	public int getVertexCount() {
		return nodes.size();
	}
	
	public Edge findEdge(Node v1, Node v2) {
		Edge e = null;
		if(contains(v1) && contains(v2))
			e = g.findEdge(v1, v2);
		return e;
	}
	
	public int getWeight(Node u, Node v) {
		int ret = -1;
		if(containsEdge(u,v))
			ret = g.findEdge(u, v).getWeight();
		return ret;
	}
	
	public Iterator<Node> iterator() {
		return nodes.iterator();
	}
	
	public boolean containsEdge(Node u, Node v) {
		return contains(u) && contains(v) && g.containsEdge(u, v);
	}
	
	public boolean contains(Node u) {
		return nodes.contains(u);
	}
	
	public List<Node> getNeighbors(Node u) {
		List<Node> neighbors = new ArrayList<Node>();
		Iterator<Node> iterator = g.getNeighbors(u).iterator(); 
		while(iterator.hasNext()) {
			Node v = iterator.next();
			if(contains(v) && containsEdge(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() {
		if(getVertexCount() == 0)
			return "[]";
		StringBuffer out =new StringBuffer("[");
		Iterator<Node> it = nodes.iterator();
		while(it.hasNext()) {
			Node u = it.next();
			out.append(u.toString() + ",");
		}
		out.setLength(out.length() - 1);
		out.append("]");
		return out.toString();
	}
	
	public List<Node> getBoundary() {
		if(recomputeGain)
			computeGain();
		Iterator<Entry<Node,Integer>> EDIterator = ED.entrySet().iterator();
		List<Node> boundary = new ArrayList<Node>();
		while(EDIterator.hasNext()) {
			Entry<Node,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 = new HashSet<Node>();
		Iterator<Node> graphIterator =clone.g.getVertices().iterator();
		while(graphIterator.hasNext()) {
			Node u = graphIterator.next();
			if(contains(u))
				clone.nodes.add(u);
		}
		
		clone.bucketGain = new HashMap<Integer, List<Node>>();
		clone.gainSet = new TreeSet<Integer>();
		clone.ID = new HashMap<Node, Integer>();
		clone.ED = new HashMap<Node, Integer>();
		
		clone.computeGain();
		
		return clone;
	}
	
	public UndirectedGraph createInducedSubgraph() {
		return FilterUtils.createInducedSubgraph(nodes,g);
	}
}