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

package project;

import java.util.Random;
import java.io.*;

public class Solution implements Cloneable, Serializable {

  private static GeometricGraph graph;
  private static int[][] adjacancyMatrix;
  private int[] partitionVector;
  private int[] partitionImbalance;
  private Random numberGen;
  private int order = 0;
  private int partitionSize = 0;
  private int partitionFactor = 0;
  private int cutEdges = 0;
  private double alpha = 1;
  
  public Solution(GeometricGraph g, int k) {
    graph = g;
    order = graph.getOrder();
    
    if ((order % k) == 0) {
      partitionVector = new int[order];
      adjacancyMatrix = graph.getAdjacancyMatrix();
      partitionImbalance = new int[k];
      partitionFactor = k;
      partitionSize = (int)order/k;
      
      numberGen = new Random();
      
      // Initialise partitionVector, If partitionVector[i] == k then vertex i is in partition k.
      // For each partition p 0<=p<k, pick a vertex v at random without repitition and assign p to it.
      int splitSize = 0;
      int index = 0;
      int i = 0;
      int j = 0;
      
      i = order;
      while (i-- > 0) 
	partitionVector[i] = 0;
      
      // Start at 1 because all vertices are in partition 0 by default
      i = 0;
      while (++i < partitionFactor) {
	splitSize = 0;
	while (splitSize < partitionSize) {
	  index = Math.abs(numberGen.nextInt() % order);
	  if (partitionVector[index] == 0) {
	    partitionVector[index] = i;
	    splitSize++;
	  } 
	}	
      }
      
      // Initialise partitionImbalance vector
      i = partitionFactor;
      while (i-- > 0) {
	// Initialise partition sizes
	partitionImbalance[i] = 0;
      }
      
      // Initialise cutEdges
      for (i=0; i<order; i++) {
	for (j=i; j<order; j++) {
	  if (g.hasEdge(i,j)) {
	    if (partitionVector[i] != partitionVector[j]) {
	      // vertices are in different partitions
	      cutEdges++;
	    }
	  }
	}
      }

    } else {
      System.err.println("Error: The graph may only be divided evenly!");
    }
  }
  
  public Solution(GeometricGraph g, int k, int[] pvector) {
    
    graph = g;
    order = graph.getOrder();
    int index;
    int i=0;
    int j=0;
    numberGen = new Random();
    
    if (pvector.length == order) {
      if ((order % k) == 0) {
	partitionVector = pvector;		
	adjacancyMatrix = graph.getAdjacancyMatrix();
	partitionImbalance = new int[k];
	partitionFactor = k;
	partitionSize = (int)order/k;

	// Initialise  partitionImbalance vector
	index = partitionFactor;
	while (index-- > 0) {
	  partitionImbalance[index] = -partitionSize;
	}
	
	// Calculate imbalance of each partition and total external cost
	index = partitionVector.length;
	while(index-- > 0) 
	  partitionImbalance[partitionVector[index]]++;

	// Initialise cutEdges
	for (i=0; i<order; i++) {
	  for (j=i; j<order; j++) {
	    if (g.hasEdge(i,j)) {
	      if (partitionVector[i] != partitionVector[j]) {
		// vertices are in different partitions
		cutEdges++;
	      }
	    }
	  }
	}
      }
    }
  }

  /**
    * Used to initialise a Solution if has been read from a file and no other instance of Solution exists.
    */
  public void setGraph(GeometricGraph g) {
    graph = g;
    adjacancyMatrix = g.getAdjacancyMatrix();
  }
 
  /**
    * @return The array representing the partitioning of the graph
    */
  public int[] getPartition() {
    return(partitionVector);
  }

  public void setPartition(int[] pvector) {
    
    int index;
    int i=0;
    int j=0;
    
    if (pvector.length == order) {
      System.arraycopy(pvector, 0, partitionVector, 0, partitionVector.length);
	
      // Initialise  partitionImbalance vector
      index = partitionFactor;
      while (index-- > 0) {
	partitionImbalance[index] = -partitionSize;
      }
	
      // Calculate imbalance of each partition and total external cost
      index = partitionVector.length;
      while(index-- > 0) 
	partitionImbalance[partitionVector[index]]++;
      
      // Recalculate cutEdges
      cutEdges = 0;
      for (i=0; i<order; i++) {
	for (j=i; j<order; j++) {
	  if (graph.hasEdge(i,j)) {
	    if (partitionVector[i] != partitionVector[j]) {
	      // vertices are in different partitions
	      cutEdges++;
	    }
	  }
	}
      }
    }
  }

  /**
    * This changes the factor by which the imbalance of the partitioning is scaled.
    *
    * @see getImbalance()
    */
  public void setImbalanceWeight(double w) {
    // This is the factor by which the imbalance is scaled.
    alpha = w;
  }
  
  public void printStatus() {
    // Test code
    int index;
    int arrayLength = 0;
    
    System.out.println("Partition Imbalance"); 
    System.out.println("================"); 
    index = -1;
    arrayLength = partitionImbalance.length; 
    while (++index < arrayLength)    
      System.out.print(partitionImbalance[index] + " ");
    System.out.println("");
    
    System.out.println("Partition Cost"); 
    System.out.println("================"); 
    index = -1;

    System.out.println("Cutedges: " + cutEdges);
    System.out.println("Solution Cost: " + getCost());
    System.out.println("________________________________________");
    System.out.println("");
  }
  
  public Object clone() {
    Solution s = (Solution)null;
    int length;
    try {
      // This is the basic clone step 
      s = (Solution)super.clone();
      
      // Need to clone all the non primitive members also. 
      length = partitionVector.length;	
      s.partitionVector = new int[length];
      System.arraycopy(partitionVector, 0, s.partitionVector, 0, length);
      
      length = partitionImbalance.length;  
      s.partitionImbalance = new int[length];
      System.arraycopy(partitionImbalance, 0, s.partitionImbalance, 0, length);
      
    } catch (CloneNotSupportedException e) {
      System.err.println("System error: Clone failed");
      System.err.println(e.getMessage());
    }
    return(s);
  }
  
  /**
    * @return A copy of the Solution in which a vertex has been moved to a different partition.
    */
  public Solution randomLegalMigration() {
    int vertex = Math.abs(numberGen.nextInt() % order);
    int sourcePartition = partitionVector[vertex]; 
    int destinationPartition = Math.abs(numberGen.nextInt() % partitionFactor);
    
    while (sourcePartition == destinationPartition) {
      destinationPartition = Math.abs(numberGen.nextInt() % partitionFactor);
    }
    
    Solution newSolution = (Solution)null;
    
    try {
      newSolution = (Solution)this.clone();
      newSolution.migrate(vertex, sourcePartition, destinationPartition);
    } catch (Exception e) {
      System.err.println("Clone Error: " + e.getMessage());
    }
    return(newSolution);
  }
  
  /**
    * @return A copy of the Solution in which the input vertex has been moved to the input partition.
    */
  public Solution legalMigration(int vertex, int destinationPartition) {
    int sourcePartition = partitionVector[vertex];
    
    if (sourcePartition == destinationPartition) {
      return(this);
    } else {
      Solution newSolution = (Solution)null;
      try {
	newSolution = (Solution)this.clone();
	newSolution.migrate(vertex, sourcePartition, destinationPartition);
      } catch (Exception e) {
	System.err.println("Clone Error: " + e.getMessage());
      }
      return(newSolution);
    }
  }
  
  private void migrate(int vertex, int sourcePartition, int destinationPartition) {
    
    Random numberGen = new Random();
    int vertexInternalCost = 0;
    int vertexExternalCost = 0;
    int vertexExternalCostWrtTarget = 0;
    int currentPartition = 0;
    
    // These values are calculated dynamically. They could be stored in an array but since
    // vertexExternalCostWrtTarget MUST be calculated, this loop still has to occur.
    for (int i=0; i<order; i++) {
      if ((adjacancyMatrix[i][vertex] != 0) && (vertex != i)) {
	currentPartition = partitionVector[i];
	if (currentPartition == sourcePartition) {
	  vertexInternalCost++;
	} else {
	  if (currentPartition == destinationPartition) {
	    // The cost with respect to the destination partition
	    vertexExternalCostWrtTarget++;
	  }
	}
      }
    }
    
    // Perform the actual migration
    partitionVector[vertex] = destinationPartition;
    
    partitionImbalance[sourcePartition] -= 1;
    partitionImbalance[destinationPartition] += 1;
    
    cutEdges += (vertexInternalCost - vertexExternalCostWrtTarget);
  }
  
  /**
    * @return A copy of the Solution in which the input vertices are exchanged.
    */
  public Solution switchVertices(int vertex0, int vertex1) {
    
    Solution newSolution = (Solution)null;
    try {
      newSolution = (Solution)this.clone(); 
    } catch(Exception e) {
      System.err.println("Clone Error: " + e.getMessage()); 
    }
    
    try {
      newSolution.swapVertices(vertex0, vertex1);
    } catch(BadVertexSwapException e) {
      // Tried to swap two vertices which are in same partition. 
      // This is a Null operation.
    } 
    return(newSolution);
  }
  
  /**
    * This performs switchVertices with two random vertices from different partitions.
    */
  public Solution switchRandomVertices() {
    int vertex0 = Math.abs(numberGen.nextInt()) % order;
    int vertex1 = Math.abs(numberGen.nextInt()) % order;
    
    // Make sure both vertices are from different partitions	
    while (partitionVector[vertex0] == partitionVector[vertex1]) {
      vertex1++;
      vertex1 %= order;
    }
    return(switchVertices(vertex0, vertex1));
  }
  
  private void swapVertices(int vertex0, int vertex1) throws BadVertexSwapException {
    Random numberGen = new Random();
    int vertex0InternalCost = 0;
    int vertex0ExternalCost = 0;
    int vertex0ExternalCostWrtTarget = 0;
    int vertex1InternalCost = 0;    
    int vertex1ExternalCost = 0;
    int vertex1ExternalCostWrtTarget = 0; 
    int vertex0Partition = partitionVector[vertex0];
    int vertex1Partition = partitionVector[vertex1];
    int currentPartition = 0;
    
    if ((partitionVector[vertex0] == partitionVector[vertex1]) || (vertex0 == vertex1)) {
      throw(new BadVertexSwapException());
    } else {
      
      // Calculate Internal and External cost of each vertex, and the 
      // external cost of each with respect to the target partition.
      for (int i=0; i<order; i++) {
	if ((adjacancyMatrix[i][vertex0] != 0) && (i != vertex0)) {
	  currentPartition = partitionVector[i];
	  if (currentPartition == vertex0Partition) {
	    vertex0InternalCost++;
	  } else {
	    if (currentPartition == vertex1Partition) {
	      // The cost with respect to the destination partition
	      vertex0ExternalCostWrtTarget++;
	    } else {
	      // The cost wrt to all other partitions
	      vertex0ExternalCost++;
	    }
	  }
	}
	
	if ((adjacancyMatrix[i][vertex1] != 0) && (i != vertex1)) {
	  currentPartition = partitionVector[i]; 
	  if (currentPartition == vertex1Partition) {
	    vertex1InternalCost++;
	  } else { 
	    if (currentPartition == vertex0Partition) {
	      // The cost with respect to the destination partition 
	      vertex1ExternalCostWrtTarget++;
	    } else { 
	      // The cost wrt to all other partitions 
	      vertex1ExternalCost++;
	    } 
	  } 
	} 
      }
      
      // System.out.print("Vertex0: " + vertex0 + " I: " + vertex0InternalCost + " Ew: " + vertex0ExternalCostWrtTarget);
      // System.out.println(" :: Vertex1: " + vertex1 + " I: " + vertex1InternalCost + " Ew: " + vertex1ExternalCostWrtTarget);
      // Perform the actual migration
      partitionVector[vertex0] = vertex1Partition;
      partitionVector[vertex1] = vertex0Partition; 
      
      cutEdges += ((vertex0InternalCost - vertex0ExternalCostWrtTarget) + (vertex1InternalCost - vertex1ExternalCostWrtTarget));
      cutEdges += (2 * adjacancyMatrix[vertex0][vertex1]);
    }
  }
  
  public void balance() {
   
 // Redistribute the nodes so that each partition has the same amount.
    int partitionIndex = 0;
    int vertexIndex=0;

    for(int i=0; i<partitionFactor; i++) {
      // Search for a partition with too few vertices
      while((partitionIndex < partitionFactor) && (partitionImbalance[partitionIndex] >= 0)) {
	partitionIndex++;
      }
	
      if (partitionIndex < partitionFactor) {
	// Found a partition with too few vertices
	while((partitionImbalance[partitionIndex] < 0) && (partitionImbalance[i] > 0)) {
	  // Move the vertices of lowest cost from partition i to partition partitionIndex
	  int maxVertices = (partitionImbalance[i] - partitionImbalance[partitionIndex]);

	}
      }
    }    
  }      
    
  private void balancePartitions(int srcPartition, int destPartition) {
    int maxVertices = (partitionImbalance[srcPartition] - partitionImbalance[destPartition]);    
    int gainList[] = new int[order];
    int vertexCount = 0;
    int maxGain = Integer.MIN_VALUE;
    int swapVertex = 0;
    int i=0;

    // Set all values to min
    while(i<order) 
      gainList[i++] = Integer.MIN_VALUE;

    // Calculate gain for each vertex in srcPartition
    for (i=0; i<order; i++) {
      if (partitionVector[i] == srcPartition) {
	gainList[vertexCount++] = gain(vertexCount, destPartition);
      } 
    }
    
    // find vertex yielding maximum gain
    i=0;
    while (gainList[i] != Integer.MIN_VALUE) {
      if (gainList[i++] > maxGain) 
	swapVertex=i;
    }
    
    


  }

  private int gain(int partition, int vertex) {
    return (2 * (getExternalCostWRT(vertex,partition) - getInternalCost(vertex)));
  }

  private int getInternalCost(int vertex) {
    // Returns the internal cost of a vertex
    
    int internalCost = 0;
    for(int n=0; n<order; n++) {
      if ((graph.hasEdge(vertex, n)) && (partitionVector[n] == partitionVector[vertex])) {
	internalCost++;
      }
    }
    return(internalCost);
  }

  private int getExternalCostWRT(int vertex, int targetPartition) {
    
    int vertexPartition = partitionVector[vertex];
    int cost = 0;

    for(int n=0; n<order; n++) {
      if (graph.hasEdge(vertex,n)) {
	if (partitionVector[n] == targetPartition){
	  cost++;
	}
      }
    }
    return(cost);
  }
  
  /**
    * Crossover consists of taking two vectors, breaking each into two segments and
    * recombining opposite segements to produce to new vectors.
    *
    * @param mate            A Solution with which to perform the crossover operation.
    * @param crossOverPoint  The point in the chromosome at which to perform crossover
    * @return The two derived Solutions contained in an array.
    */
  public Solution[] singlePointCrossOver(Solution  mate, int crossOverPoint) {
    Solution[] children = new Solution[2];
    int[] childVector0 = new int[order];
    int[] childVector1 = new int[order];

    System.arraycopy(this.partitionVector, 0, childVector0, 0, crossOverPoint);
    System.arraycopy(mate.partitionVector, 0, childVector1, 0, crossOverPoint);

    System.arraycopy(mate.partitionVector, crossOverPoint, childVector0, crossOverPoint, (order - crossOverPoint));
    System.arraycopy(this.partitionVector, crossOverPoint, childVector1, crossOverPoint, (order - crossOverPoint));

    children[0] = new Solution(this.graph, partitionFactor, childVector0);
    children[1] = new Solution(this.graph, partitionFactor, childVector1);
    return(children);
  }

  /**
    * This performs singlePointCrossOver at a random legal position.
    * @return The two derived Solutions contained in an array.
    */
  public Solution[] randomSinglePointCrossOver(Solution  mate) {
    int crossOverPoint = Math.abs(numberGen.nextInt() % order);
    return(singlePointCrossOver(mate, crossOverPoint));
  }

  /**
    * Mutation consists of changing the values in a segment of a chromosome in some way.
    *
    * @param startPoint   The position in the Chromosome at which to start the mutation.
    * @param blockLength  The length of the block to be mutated.
    *
    * @return A copy of the Solution with the block mutated.
    */
  public Solution mutate(int startPoint, int blockLength) {

    int finishPoint = startPoint + blockLength;
    int i;
    int[] newVector = new int[order];
    System.arraycopy(partitionVector, 0, newVector, 0, order);

    if (finishPoint < order) {
      for (i=startPoint; i<=finishPoint; i++) {
	newVector[i] %= partitionFactor;
      }
    } else {
      for (i=startPoint; i<order; i++) {
	newVector[i] %= partitionFactor;
      }
      finishPoint %= order;
      for (i=startPoint; i<=finishPoint; i++) { 
	newVector[i] %= partitionFactor;
      }
    }
    return(new Solution(this.graph, partitionFactor, newVector));
  }

  /** 
    * Adjust the input vector so that all values occur equal numbers
    * of times thus representing a balanced solution.
    */
  public void postProcess() {

    // Redistribute the nodes so that each partition has the same amount.
    int partitionIndex = 0;
    for(int i=0; i<partitionFactor; i++) {
      // Search for a partition with too many vertices
      while((partitionIndex < partitionFactor) && (partitionImbalance[partitionIndex] <= 0)) {
	partitionIndex++;
      }
	
      if (partitionIndex < partitionFactor) {

	// Found a partition with surplus vertices
	while((partitionImbalance[partitionIndex] > 0) && (partitionImbalance[i] < 0)) {
	  // Search for a vertex in partition partitionIndex
	  int vertex = Math.abs(numberGen.nextInt() % order); 
	  while (partitionVector[vertex] != partitionIndex) {
	    vertex++;
	    vertex %= order;
	  }
	  // Move the vertex  to partition i.
	  partitionVector[vertex]  = i;
	  partitionImbalance[partitionIndex]--;
	  partitionImbalance[i]++;
	}
      }
    }
    
    // Recalculate cutEdges 
    int i=0;
    int j=0;
    cutEdges = 0;
    for (i=0; i<order; i++) {
      for (j=i; j<order; j++) {
	if (graph.hasEdge(i,j)) {
	  if (partitionVector[i] != partitionVector[j]) {
	    // vertices are in different partitions
	    cutEdges++;
	  }
	}
      }
    }

    // Reset imbalance vector
    for (i=0; i<partitionFactor; i++) {
      partitionImbalance[i] = 0;
    }
  }
  
  /**
    * @return The number of edges cut in the partitioning
    */
  public int getCutEdges() {
    return(cutEdges);
  }
  
  /**
    * @return The sum of the squares of the differences between the size of the partitions and the average size.
    */
  public int getImbalance() {
    int index = partitionFactor;
    int imbalanceCost = 0;
    while (index-- > 0)
      imbalanceCost += Math.pow(partitionImbalance[index],2);
	
    return(imbalanceCost);
  }
    
  /**
    * @return The number of edges cut + the imbalance of the partition
    */
  public double getCost() {
    return(cutEdges + (alpha * getImbalance()));
  }
  
  /**
    * @return The partition to which the input vertex belongs.
    */
  public int getVertexPartition(int vertex) {
    return(partitionVector[vertex]);
  }

  public void writeToFile(String filename) {
    try {
      ObjectOutputStream os = new ObjectOutputStream(new FileOutputStream(filename));
      os.writeObject(this);
      os.close();
    } catch (Exception e) {
      System.err.println("Error writing object: " + e.getMessage());
    }
  }
      
  /**
    * @param  filename The name of a file containing a Serialized Solution
    *
    * @return The Solution read from the file.
    */
  public static Solution readFromFile(String filename) {
    Solution s = (Solution)null;
    try {
      ObjectInputStream in = new ObjectInputStream(new FileInputStream(filename));
      s = (Solution)in.readObject();
    } catch (Exception e) {
      System.err.println("Error reading object: " + e.getMessage());
    }
    return(s);
  }
  
  private void testCrossOver(Solution s) {
    Solution[] offspring = new Solution[2];
    System.out.println("Crossing to following vectors..");

    int i=0;
    for (i=0; i<order; i++) {
      System.out.print(this.partitionVector[i] + " ");
    }
    System.out.println();
    for (i=0; i<order; i++) {
      System.out.print(s.partitionVector[i] + " ");
    }
    System.out.println();

    offspring = randomSinglePointCrossOver(s);
      
    System.out.println("Derived vectors");
    for (i=0; i<order; i++) {
      System.out.print(offspring[0].partitionVector[i] + " ");
    }
    System.out.println();
    for (i=0; i<order; i++) {
      System.out.print(offspring[1].partitionVector[i] + " ");
    }
    System.out.println();
  }
    
  public static void main(String[] args) {
    
    if (args.length == 3) {
      GeometricGraph g = GeometricGraph.readFromFile(args[0]);
      int k = new Integer(args[1]).intValue();	
      String solutionFileName = args[2];
      
      Solution s = new Solution(g,k);
      System.out.print("Writing to file.....");
      s.writeToFile(solutionFileName);
      System.out.println("done");
      System.out.println("");
      System.out.print("Reading Solution from file....");
      s = Solution.readFromFile(solutionFileName);
      s.setGraph(g);
      System.out.println("done");
    } else if (args.length == 2) {
      GeometricGraph g = GeometricGraph.readFromFile(args[0]);
      int k = new Integer(args[1]).intValue();	
      Solution s = new Solution(g,k);
      System.out.println("Solution has cost: " + s.getCost() + "," + s.getCutEdges());
      s.setPartition(s.getPartition());
      System.out.println("Solution has cost: " + s.getCost() + "," + s.getCutEdges());
      s = s.randomSinglePointCrossOver(s)[0];
      System.out.println("Solution has cost: " + s.getCost() + "," + s.getCutEdges());
      s.postProcess();
      System.out.println("Solution has cost: " + s.getCost() + "," + s.getCutEdges());
      s.setPartition(s.getPartition());
      System.out.println("Solution has cost: " + s.getCost() + "," + s.getCutEdges());
    } else {
      System.err.println("Usage Error: Solution GraphFile k SolutionFile");
    }
  }
}