/*
 * SA.class
 * Part of package project
 *
 * Author: Philip Bradley
 *
 */

package project;

import java.util.Random;


public class SA {
	
  Random numberGen;

  public SA(GeometricGraph g, int partitionSize, double initProb, double coolingRate, float sizeFactor, double minRatio, double iWeight, int maxIterations, boolean singleVertexMigrations) {
    Solution s = new Solution(g,partitionSize);
    
    if (singleVertexMigrations) {
      Solution newSol = singleVertexMigrationAnnealing(g, partitionSize, initProb, coolingRate, sizeFactor, minRatio, iWeight, s, maxIterations);
      singleVertexMigrationAnnealing(g, partitionSize, 0.1, coolingRate, (float)0.4, minRatio, 10, newSol, maxIterations);
    } else {
      doubleVertexMigrationAnnealing(g, partitionSize, initProb, coolingRate, sizeFactor, minRatio, s, maxIterations);
    }
  }

  
  public SA(GeometricGraph g, int partitionSize, double initProb, double coolingRate, float sizeFactor, double minRatio, double iWeight, String solnFile, int maxIterations, boolean singleVertexMigrations) {
    Solution s = Solution.readFromFile(solnFile);
    s.setGraph(g);
    
    if (singleVertexMigrations) {
      singleVertexMigrationAnnealing(g, partitionSize, initProb, coolingRate, sizeFactor, minRatio, iWeight, s, maxIterations);
    } else {
      doubleVertexMigrationAnnealing(g, partitionSize, initProb, coolingRate, sizeFactor, minRatio, s, maxIterations);
    }	
  }
  
  private Solution singleVertexMigrationAnnealing(GeometricGraph g, int k, double initProb, double coolingRate, float sizeFactor, double minRatio, double iWeight, Solution initSolution, int maxIterations) {
    
    numberGen = new Random();
    double temperature;
    double delta = 0;
    double initDelta = 0;
    double newCost = 0;
    long finishTime;	
    int index = 0;
    int numberAcceptedMoves = 0;
    double ratioAcceptedMoves = 1;
    int minPercentCount = 0;
    Solution currentSolution = initSolution;
    Solution bestSolution;
    Solution newSolution;
    Solution testSolution;
    currentSolution.setImbalanceWeight(iWeight);
    double currentCost = currentSolution.getCost();
    double bestCost = currentCost;
    int activeVertex = 0;
    int partitionCount = 0;
    int migrationCount = 0;
    int graphOrder = g.getOrder();
    int runLength = (int)(graphOrder * sizeFactor);
    int totalIterations = 0;
    int targetPartition = 0;
    int verticesExamined = 0;
    bestSolution = (Solution)currentSolution.clone();
    boolean freeVertex[] = new boolean[graphOrder];
    boolean currentVertexAccepted = false;
    
    // Initialise array freeVertex to True. Initially all vertices are 
    // available for migrations.
    for (index=0; index<graphOrder; index++) {
      freeVertex[index] = true;
    }
    
    // Perform breadth first search re-ordering on graph
    g.BFSReordering(Math.abs(numberGen.nextInt()) % graphOrder);
    
    index = 1000;
    testSolution = (Solution)currentSolution.clone();
    while (index > 0) {
      newSolution = testSolution.randomLegalMigration();
      delta = newSolution.getCost() - testSolution.getCost();
      
      if (delta > 0) {
	initDelta += delta;
	index--;
      }
      testSolution = newSolution;
    }
    initDelta /= 1000;
    
    // Calculate temperature based on average uphill delta
    temperature = -initDelta/(Math.log(initProb));
    System.out.println("# Temperature: " + temperature + " Cost: " + currentSolution.getCost() + " Cut Edges " + currentSolution.getCutEdges()); 
    
    /* Vertices are picked at random without repitition. When a vertex 'n' is picked false is recorded
     * in position n in the freeVertex array. When a vertex is accepted the array is reset (to true).
     */
    long startTime = System.currentTimeMillis();
    activeVertex = Math.abs(numberGen.nextInt()) % graphOrder;
    currentVertexAccepted = false;
    while (minPercentCount < maxIterations) {    
      targetPartition = Math.abs(numberGen.nextInt()) % k;
      
      // Try active vertex in all partitions starting with one at random and advancing (and wrapping if necessary)
      while (partitionCount < k) {

	targetPartition++;            //  Get the next partition
	targetPartition %= k;

	newSolution = currentSolution.legalMigration(activeVertex, targetPartition);
	currentCost = currentSolution.getCost();
	newCost = newSolution.getCost();
	delta = (newSolution.getCost() - currentSolution.getCost());
	
	if (delta < 0) {
	  currentSolution = (Solution)newSolution.clone();
	  numberAcceptedMoves++;
	  currentVertexAccepted = true;
	  // System.out.print(temperature + " " + currentSolution.getCost() + " ");
	  // System.out.println(currentSolution.getCutEdges());
	  
	  if (newCost < bestCost)
	    bestSolution = (Solution)currentSolution.clone();
	} else if (delta > 0) {
	  if (probabilityFunction(delta, temperature)) {
	    currentSolution = (Solution)newSolution.clone();
	    numberAcceptedMoves++; 
	    currentVertexAccepted = true;
	    // System.out.print(temperature + " " + currentSolution.getCost() + " ");
	    // System.out.println(currentSolution.getCutEdges());
	  }
	}

	// After trying vertex activeVertex with partition partitionCount, try activeVertex with partitionCount + 1.
	partitionCount++;
	migrationCount++;
	totalIterations++;
	
	if (migrationCount == runLength) {
	  ratioAcceptedMoves = (double)numberAcceptedMoves/runLength;
	  if (ratioAcceptedMoves > minRatio) {
	    minPercentCount = 0;
	  } else {
	    minPercentCount++;
	  }

	  // Reduce the temperature and reset the count
	  temperature *= coolingRate;
	  migrationCount = 0;
	  numberAcceptedMoves = 0;
	}
      }
      // Finished trying vertex: acticeVertex against all partitions
      // Reset the partitionCount and find a new vertex.

      partitionCount = 0; 
      
      // If the vertex has been selected and cannot be migrated,it is no longer considered for further migration
      // If it has been accepted, then all vertices are made available for migration again.
      if (currentVertexAccepted == false) {
	// Make this vertex unavailable for selection
	freeVertex[activeVertex] = false;
      } else {
	// Reset the 'availability' of vertices
	for (index=0; index<graphOrder; index++) {
	  freeVertex[index] = true;
	}
      }
      
      //If all the vertices have been tried then make all vertices available again
      if (verticesExamined == graphOrder) {
	for (index=0; index<graphOrder; index++) {
	  freeVertex[index] = true;
	}
	verticesExamined = 0;
      }

      // Search for a vertex that has not already been tried
      do {
	activeVertex = (Math.abs(numberGen.nextInt()) % graphOrder);
      } while (!freeVertex[activeVertex]);
      verticesExamined++;
    }          
    
    finishTime = System.currentTimeMillis();
    System.out.println("# Total running time in milliseconds: " + (finishTime - startTime) + ": Total Iterations: " + totalIterations);
    System.out.println("# Best Solution: " + bestSolution.getCost() + " " + bestSolution.getCutEdges() + " " + bestSolution.getImbalance());
    return(bestSolution);
  }
  
  private void doubleVertexMigrationAnnealing(GeometricGraph g, int k, double initProb, double coolingRate, float sizeFactor, double minRatio, Solution initSolution, int maxIterations) {
    
    System.out.println("Performing doubleVertexMigrations");
    numberGen = new Random();
    double temperature;
    double delta = 0;
    double initDelta = 0;
    double newCost = 0;
    long finishTime;	
    int index = 0;
    int numberAcceptedMoves = 0;
    double ratioAcceptedMoves = 1;
    int minPercentCount = 0;
    Solution currentSolution = initSolution;
    Solution bestSolution;
    Solution newSolution;
    Solution testSolution;
    double currentCost = currentSolution.getCost();
    double bestCost = currentCost;
    int migrationCount = 0;
    int graphOrder = g.getOrder();
    int runLength = (int)(graphOrder * sizeFactor);
    int totalIterations = 0;
    bestSolution = (Solution)currentSolution.clone();
    boolean freeVertex[] = new boolean[graphOrder];
    boolean currentVertexAccepted = false;
    
    // Initialise array freeVertex to True. Initially all vertices are 
    // available for migrations.
    for (index=0; index<graphOrder; index++) {
      freeVertex[index] = true;
    }
    
    // Perform breadth first search re-ordering on graph
    g.BFSReordering(Math.abs(numberGen.nextInt()) % graphOrder);
    
    index = 1000;
    testSolution = (Solution)currentSolution.clone();
    while (index > 0) {
      newSolution = testSolution.switchRandomVertices();
      delta = newSolution.getCost() - testSolution.getCost();
      
      if (delta > 0) {
	initDelta += delta;
	index--;
      }
      testSolution = newSolution;
    }
    initDelta /= 1000;
    
    // Calculate temperature based on average uphill delta
    temperature = -initDelta/(Math.log(initProb));
    System.out.println(temperature + " " + currentSolution.getCost() + " " + currentSolution.getCutEdges()); 
    
    /* Vertices are picked at random without repitition. When a vertex 'n' is picked false is recorded
     * in position n in the freeVertex array. 
     * For each vertex, check if swapping it with every other vertex can yield a gain. 
     */
    long startTime = System.currentTimeMillis();
    int vertexCount = 0;
    int swapVertex = 0;
    int activeVertex = 0;
    
    while (minPercentCount < maxIterations) {    
      swapVertex = Math.abs(numberGen.nextInt()) % graphOrder;
      activeVertex = Math.abs(numberGen.nextInt()) % graphOrder;
      
      while (vertexCount < graphOrder) {
	swapVertex++;
	swapVertex %= graphOrder;
	newSolution = currentSolution.switchVertices(activeVertex, swapVertex);
	currentCost = currentSolution.getCost();
	newCost = newSolution.getCost();
	delta = (newSolution.getCost() - currentSolution.getCost());
	migrationCount++;
	totalIterations++;
	
	if (delta < 0) {
	  currentSolution = (Solution)newSolution.clone();
	  vertexCount = 0;
	  numberAcceptedMoves++;
	  currentVertexAccepted |= true;
	  // System.out.print(temperature + " " + currentSolution.getCost() + " ");
	  // System.out.println(currentSolution.getCutEdges());
	  
	  if (newCost < bestCost)
	    bestSolution = (Solution)currentSolution.clone();
	} else if (delta > 0) {
	  if (probabilityFunction(delta, temperature)) {
	    currentSolution = (Solution)newSolution.clone();
	    vertexCount = 0; 
	    numberAcceptedMoves++; 
	    currentVertexAccepted |= true;
	    
	    // System.out.print(temperature + " " + currentSolution.getCost() + " ");
	    // System.out.println(currentSolution.getCutEdges());
	    
	  } else {
	    vertexCount++;
	  }
	} else {
	  // Don't explore plateaus
	  vertexCount++;
	}
	
	if (migrationCount == runLength) {
	  ratioAcceptedMoves = (double)numberAcceptedMoves/runLength;
	  if (ratioAcceptedMoves > minRatio) {
	    minPercentCount = 0;
	  } else {
	    minPercentCount++;
	  }
	  
	  temperature *= coolingRate;
	  migrationCount = 0;
	  numberAcceptedMoves = 0;
	}
      } 
      vertexCount = 0; 
      
      // If the vertex has been selected and cannot be migrated,it is no longer considered for further migration
      // If it has been accepted, then all vertices are made available for migration again.
      if (currentVertexAccepted == false) {
	freeVertex[activeVertex] = false;
      } else {
	for (index=0; index<graphOrder; index++) {
	  freeVertex[index] = true;
	}
      }
      
      // Search for a vertex that has not already been tried
      
      do {
	activeVertex = (Math.abs(numberGen.nextInt()) % graphOrder);
      } while (!freeVertex[activeVertex]);
    }          
    
    finishTime = System.currentTimeMillis();
    System.out.println("# Total running time in milliseconds: " + (finishTime - startTime) + ": Total Iterations: " + totalIterations);
    System.out.println("# Best Solution: " + bestSolution.getCost() + " " + bestSolution.getCutEdges());
  }
  
  private boolean probabilityFunction(double delta, double temp) {
    
    double index = (-delta/temp);
    double probability = Math.exp(index)/2;               		//number between 0 & 1
    int cutoffValue = (int)Math.rint(1000000 * probability); 	//integer between 0 & 1000000
    int testValue = Math.abs(numberGen.nextInt() % 1000000); 	//integer between 0 & 1000000
    
    // System.out.println("Probability: " + probability);
    
    if (testValue < cutoffValue) {
      // This has probability of 'probability'
      return(true);
    } else {
      return(false);
    }
  }
  
  public static void main(String[] args) {
    
    int numberOfArgs = args.length;
    int i = 0;	
    String tmpString = new String();
    GeometricGraph g = (GeometricGraph)null;
    int partition = 0;
    double initProb = 0;
    double rate = 0;
    float sizeFactor = 0;
    double minRatio = 0;
    double imbalanceScaling = Integer.MIN_VALUE;
    String filename = "";
    int maxIterations = 0;
    boolean singleVertexMigrations = false;
    
    
    if ((numberOfArgs != 15) && (numberOfArgs != 17) && (numberOfArgs != 19)) {
      System.err.println("Error:");
      System.err.println("SA -g GraphFile -p Partition Size [-sol Solution File] -i initProb -l Size Factor -r Cooling Rate -f Freeze Percent [-s Imbalance Scaling] -mx maxIterations -[single|double]");
    } else {
      while (i < numberOfArgs) {
	
	tmpString = args[i];
	if (tmpString.equals("-g")) {
	  // System.out.print("Reading graph from file...");
	  g = GeometricGraph.readFromFile(args[++i]);	
	  // System.out.println("done");
	} else if (tmpString.equals("-p")) {
	  partition = new Integer(args[++i]).intValue();       	
	} else if (tmpString.equals("-i")) {
	  initProb = new Double(args[++i]).doubleValue();
	} else if (tmpString.equals("-l")) {
	  sizeFactor = new Float(args[++i]).floatValue();
	} else if (tmpString.equals("-r")) {
	  rate  = new Double(args[++i]).doubleValue();
	} else if (tmpString.equals("-f")) {
	  minRatio = new Double(args[++i]).doubleValue();
	} else if (tmpString.equals("-s")) {
	  imbalanceScaling = new Double(args[++i]).doubleValue();
	} else if (tmpString.equals("-sol")) {
	  filename = args[++i];
	} else if (tmpString.equals("-mx")) {
	  maxIterations = new Integer(args[++i]).intValue();
	} else if (tmpString.equals("-single")) {
	  singleVertexMigrations = true;
	  if (imbalanceScaling == Integer.MIN_VALUE) {
	    System.err.println("Error: a value for Imbalance Scaling must be supplied for single vertex migrations");
	    System.exit(-1);
	  }
	} else if (tmpString.equals("-double")) { 
	  singleVertexMigrations = false;
	  if (imbalanceScaling != Integer.MIN_VALUE) 
	    System.out.println("#Warning: Value for Imbalance Scaling will be ignored!");
	} else {
	  System.err.println("Error: arg: " + args[i]);
	  System.exit(1);
	}
	i++;
      }
      
      System.out.println("# Running SA on graph of order " + g.getOrder() + " and size " + g.getSize());
      System.out.println("# graph Connected: " + g.isConnected());
      if (filename.equals("")) {
	SA s = new SA(g, partition, initProb, rate, sizeFactor, minRatio, imbalanceScaling, maxIterations, singleVertexMigrations);
      } else {
	SA s = new SA(g, partition, initProb, rate, sizeFactor, minRatio, imbalanceScaling, filename, maxIterations, singleVertexMigrations);
      }
    }
  }
  
}