package alg;

import generator.GraphGenerator;
import graph.Graph;
import graph.TimeGraph;

import index.CoarsenIndex;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Random;

public class SimmulatedAnealing {
	
	
	private TimeGraph tg;
	private int time = 1;
	
	
	Random r = new Random();
	
	// number of structure moves after each time move
	private int smoves_per_tmove = 1;
	
	// Cooling schedule
	private int c = 1;
	private int it_per_timeunit = 1;
	
	
	// Current solution
	private double score;
	double[] ew;
	ArrayList<Integer> nodes;
	ArrayList<Integer> ndegs;
	private int s,e;
	private ArrayList<Integer> edges;
	
	public SimmulatedAnealing(TimeGraph _tg) {
		tg = _tg;
	}
	
	public double aneal(int seeds, int seede, ArrayList<Integer> seededges, int _C) {
		assert(seeds >= 0 && seede >= seeds && tg.gett() > seede):"Bad interval:" + seeds + "-" + seede ;
		c = _C;
		s = seeds;
		e = seede;
		tg.aggregateEdgeWeights(s, e, ew);
	
		// collect edges
		edges = new ArrayList<Integer>();
		for (Integer e: seededges) {
			if (!edges.contains(e) && !edges.contains(tg.getReverseEdgeIndex(e))) {
				edges.add(e);
				score+=ew[e];
			}
		}
		
		// compute nodes and their degrees
		nodes = new ArrayList<Integer>();
		ndegs = new ArrayList<Integer>();
		int ind = -1;
		for (Integer e: edges) {
			ind = nodes.indexOf(tg.endv[e]);
			if (ind<0) {
				nodes.add(tg.endv[e]);
				ndegs.add(0);
				ind = nodes.size()-1;
			}
			ndegs.set(ind,ndegs.get(ind)+1);
			
			ind = nodes.indexOf(tg.getOrigin(e));
			if (ind<0) {
				nodes.add(tg.getOrigin(e));
				ndegs.add(0);
				ind = nodes.size()-1;
			}
			ndegs.set(ind,ndegs.get(ind)+1);
		}
		
		// run the SA
		int conv = 0;
		boolean didTMove = false, didSMove = false;
		int it = 0;		
		
		while (conv < 30) {
			//didTMove = doTimeMove();
			didSMove = doStructMove();
			
			// Track Convergence
			if (didTMove || didSMove) conv = 0;
			else conv++;
			
			// Track Time
			if (it % it_per_timeunit == 0) time++;
			it++;
		}
		return score;
	}

	private boolean doStructMove() {
		boolean moved = false, tried;
		Integer nidx, eidx;
		int ind;
		double nscore;
		
		int moves = 0;
		while (moves < smoves_per_tmove) {
			tried = false;
			while (!tried) {
				tried = false;
				// first choose a node and then an edge
				nidx = nodes.get(r.nextInt(nodes.size()));
				eidx = tg.ind[nidx] + r.nextInt(tg.ind[nidx+1] - tg.ind[nidx]);
				if (edges.contains(eidx) || edges.contains(tg.getReverseEdgeIndex(eidx))){
					if(!edges.contains(eidx)) eidx = tg.getReverseEdgeIndex(eidx);
					Integer n1 = tg.getOrigin(eidx);
					Integer n2 = tg.endv[eidx];
					// if the edge would separate the solution in two non-empty edges sets
					// we will not attempt to do the removal
					edges.remove(eidx);
					// do not remove the last edge
					if (edges.size()==0) {
						edges.add(eidx); continue;
					}
					// do not remove edges that will cause partitioning
					if (ndegs.get(nodes.indexOf(n1)) > 1 && 
						ndegs.get(nodes.indexOf(n2)) > 1 &&
						!tg.sees(n1,n2, edges) ) {
						edges.add(eidx); continue;
					}
					tried = true;
					nscore = score - ew[eidx];
					if (nscore > score) moved = true;
					else {
						// TODO optimize
						double Pa = Math.exp((nscore-score) / (c/Math.log(time+1)));
						if (r.nextDouble() <= Pa) moved = true;
					}
					if (!moved) edges.add(eidx);
					else {
						score = nscore;
						assert(nodes.contains(n1));
						ind = nodes.indexOf(n1);
						ndegs.set(ind, ndegs.get(ind) - 1);
						if (ndegs.get(ind) == 0) { nodes.remove(ind); ndegs.remove(ind);}
						
						assert(nodes.contains(n2));
						ind = nodes.indexOf(n2);
						ndegs.set(ind, ndegs.get(ind) - 1);
						if (ndegs.get(ind) == 0) { nodes.remove(ind); ndegs.remove(ind);}
					}
			
				} else { // add edge
					tried = true;
					nscore = score + ew[eidx];
					if (nscore > score) moved = true;
					else {
						// TODO optimize
						double Pa = Math.exp((nscore-score) / (c/Math.log(time+1)));
						if (r.nextDouble() <= Pa) moved = true;
					}
					if (moved) {
						edges.add(eidx);
						score = nscore;
						ndegs.set(nodes.indexOf(nidx), ndegs.get(nodes.indexOf(nidx)) +1);
						ind = nodes.indexOf(tg.endv[eidx]);
						if (ind<0) {
							nodes.add(tg.endv[eidx]);
							ndegs.add(0);
							ind = nodes.size()-1;
						}
						ndegs.set(ind,ndegs.get(ind)+1);
					}
				}
				if(tried) moves++;
			}
		}
		
		return moved;
	}

	private boolean doTimeMove() {
		boolean moved = false, tried = false;
		int move;
		
		double[] eew = null;
		
		while (!tried) {
			move = r.nextInt(4);
			// check if the move is possible
			if ((move==0 && s == e) ||
					(move==1 && s == 0) ||
					(move==2 && e == tg.gett()-1) ||
					(move==3 && s == e) ) continue;
			tried = true;
			// We consider 4 types of moves s++, s--, e++, e--
			switch (move) {
				case 0:
					tg.aggregateEdgeWeights(s+1, e, eew); break;
				case 1:
					tg.aggregateEdgeWeights(s-1, e,eew); break;
				case 2:
					tg.aggregateEdgeWeights(s, e+1,eew); break;
				case 3:
					tg.aggregateEdgeWeights(s, e-1,eew); break;	
			}
			assert(null != eew);
			
			// compute possible score
			double nscore = 0;
			for (Integer i: edges) nscore += eew[i];
			
			// try to accept
			if (nscore > score) moved = true;
			else {
				// TODO optimize
				double Pa = Math.exp((nscore-score) / (c/Math.log(time+1)));
				if (r.nextDouble() <= Pa) moved = true;
			}
			
			// update the solution and score
			if (moved) {
				score = nscore;
				ew = Arrays.copyOf(eew,eew.length);
				switch (move) {
					case 0: s++; break;
					case 1: s--; break;
					case 2: e++; break;
					case 3: e--; break;	
				}
			}
		}
		return moved; 
	}
	
	public static void main(String[] args) {
		//Graph g = GraphGenerator.getTestGraph();
		Graph g = GraphGenerator.generateScaleFree(100);
		double Pn=0.005, Pp=0.1 , Ps=0.05;
		TimeGraph tg = GraphGenerator.generateTimeNeighborhood(10, Pp, Ps, g);
		System.err.print(tg.toStringTime());
		
		// find a seed
		SimmulatedAnealing sa;
		ArrayList<Integer> sedges = new ArrayList<Integer>();
		BUp b;
		CoarsenIndex ci = new CoarsenIndex(tg, 2);
		
		for (int i = 0; i < tg.gett(); i++) {
			for (int j = 0; j < tg.getm(); j++) {
				if(tg.slices[i].get(j)) {
					sedges.add(j);break;
				}
			}
			sa = new SimmulatedAnealing(tg);
			sa.aneal(i, i, sedges, 2);
			tg.aggregateByTime(sa.s, sa.e);
			b = new BUp(tg.getAggNodeWeighted());
			b.computeOptimalLMSM();
			System.err.print(i + "->[" + sa.s + "," + sa.e + "]\t" + 
					sa.score + "\t" + b.getBestClusterGraph().getScore() + "\t" + ci.UB(sa.s, sa.e) + "\n");
		}
		
	}
	
	
}
