package weka.clusterers.forMetisMQI;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;


public class KLPartition {
	
	private Subgraph a = null;
	
	private Subgraph b = null;
	
	private List<Integer> marked = null;

	private KLPartition() {
	}
	
	public KLPartition(Subgraph s) {
		Graph g  = s.getGraph();
		a = s;
		b = new Subgraph(g);
		Iterator<Integer> graphIterator =  g.iterator();
		while(graphIterator.hasNext()) {
			int u = graphIterator.next();
			if(!s.contains(u))
				b.addNode(u);
		}
		marked = new ArrayList<Integer>();
	}
	
	public KLPartition(Graph g){
		a = new Subgraph(g);
		b = new Subgraph(g);
		Random r = Random.instance();
		for(int i=0;i<g.size();i++) {
			if(r.nextBoolean())
				a.addNode(g.getLabel(i));
			else
				b.addNode(g.getLabel(i));
		}
		marked = new ArrayList<Integer>();
	}
	
	/**
	 * Returns the node marked as candidate for swapping or -1 if there aren't node available
	 * for swapping.
	 * @return
	 */
	public int getCandidate() {
		int u;
		if(a.size() > b.size()) {
			u = a.getCandidate(marked);
			if(u == -1)
				u = b.getCandidate(marked);
		} else {
			u = b.getCandidate(marked);
			if(u == -1)
				u = a.getCandidate(marked);
		}
		if(u != -1) {
			marked.add(u);
		}
		return u;
	}
	
	public void swap(int u) {
		Subgraph from = fromSubgraph(u);
		Subgraph to = toSubgraph(u);
		from.remove(u);
		to.addNode(u);
	}
	
	private Subgraph fromSubgraph(int u) {
		Subgraph ret = null;
		if(a.contains(u))
			ret = a;
		if(b.contains(u))
			ret = b;
		return ret;
	}
	
	private Subgraph toSubgraph(int 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 (int)Math.round(0.5 * acc);
	}
	
	public Subgraph getSubgraph() {
		return a;
	}
	
	public Subgraph getComplement() {
		return b;
	}
	
	@Override
	public KLPartition clone(){
		KLPartition clone = new KLPartition();
		clone.a = (Subgraph) a.clone();
		clone.b = (Subgraph) b.clone();
		clone.marked = new ArrayList<Integer>();
		for(int i = 0; i < marked.size(); i++) {
			clone.marked.add(marked.get(i));
		}
		return clone;
	}
	
	@Override
	public String toString(){
		String out = a.toString();
		out = out + "\n";
		out = out + b.toString();
		return out;
	}
}