package weka.clusterers.forMetisMQI;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;


public class KLPartition {
	
	private Subgraph a = null;
	
	private Subgraph b = null;
	
	private Set<Node> marked = null;

	private KLPartition() {
	}
	
	public KLPartition(Subgraph s) {
		UndirectedGraph g  = s.getGraph();
		a = s;
		b = new Subgraph(g);
		Iterator<Node> graphIterator =  g.getVertices().iterator();
		while(graphIterator.hasNext()) {
			Node u = graphIterator.next();
			if(!s.contains(u))
				b.addVertex(u);
		}
		marked = new HashSet<Node>();
	}
	
	public KLPartition(UndirectedGraph g){
		a = new Subgraph(g);
		b = new Subgraph(g);
		Iterator<Node> graph = g.vtxsPermutation().iterator();
		int i = 0;
		while(graph.hasNext()) {
			Node u = graph.next();
			if((i%2)==0)
				a.addVertex(u);
			else
				b.addVertex(u);
			i++;
		}
		marked = new HashSet<Node>();
	}
	
	/**
	 * Returns the node marked as candidate for swapping or <code>null</code> if there aren't node available
	 * for swapping.
	 * @return
	 */
	public Node getCandidate() {
		Node u;
		if(a.getVertexCount() > b.getVertexCount()) {
			u = a.getCandidate(marked);
			if(u == null)
				u = b.getCandidate(marked);
		} else {
			u = b.getCandidate(marked);
			if(u == null)
				u = a.getCandidate(marked);
		}
		if(u != null) {
			marked.add(u);
		}
		return u;
	}
	
	public void swap(Node u) {
		Subgraph from = fromSubgraph(u);
		Subgraph to = toSubgraph(u);
		from.removeVertex(u);
		to.addVertex(u);
	}
	
	private Subgraph fromSubgraph(Node u) {
		Subgraph ret = null;
		if(a.contains(u))
			ret = a;
		if(b.contains(u))
			ret = b;
		return ret;
	}
	
	private Subgraph toSubgraph(Node u) {
		Subgraph ret = null;
		if(!a.contains(u))
			ret = a;
		if(!b.contains(u))
			ret = b;
		return ret;
	}

	public int edgeCut() {
		int acc = a.getExternalDegree() + b.getExternalDegree();
		return acc;
	}
	
	public Subgraph getSubgraph() {
		return a;
	}
	
	public Subgraph getComplement() {
		return b;
	}
	
	public KLPartition copy(){
		KLPartition clone = new KLPartition();
		clone.a = (Subgraph) a.clone();
		clone.b = (Subgraph) b.clone();
		clone.marked = new HashSet<Node>();
		return clone;
	}
	
	@Override
	public String toString(){
		String out = a.toString();
		out = out + "\n";
		out = out + b.toString();
		return out;
	}
}