var totalCities = 7;
var cities = [];
var order = [];

var shortestDistance;
var shortestPathFound = [];

var iterations= 1;

function setup() {
  // put setup code here
  createCanvas(400, 800);
  for (let i = 0; i < totalCities; i++) {
    var v = createVector(random(width), random(height/2));
    cities[i] = v;
    order[i] = i;
  }
  shortestDistance = calcDistance(cities);
  console.log("Shortest distance found: " + shortestDistance);
  shortestPathFound = order.slice();
  
  frameRate(10);
}

function drawshortestPathFound(shortestPathFound) {
  beginShape();
  strokeWeight(2);
  noFill();
  for (let i = 0; i < shortestPathFound.length; i++) {
    if (i == 0 || i == shortestPathFound.length - 1) {
      stroke("blue");
      fill("blue");
      ellipse(cities[shortestPathFound[i]].x, cities[shortestPathFound[i]].y, 20, 20);
    }
    noFill();
    stroke("magenta");

    vertex(cities[shortestPathFound[i]].x, cities[shortestPathFound[i]].y);
  }
  endShape();
}

function draw() {
  background(75);

  var completedness = "Percentage complete: " + Math.round((iterations/factorial(cities.length))*100) + "%";

  textSize(14);
  fill(255);
  text(completedness, 10, 20);

  textSize(14);
  fill(255);
  text("Number of cities: " + cities.length, width/2, 20);
  text("Permutations: " + factorial(cities.length), width/2, 40);

  textSize(10);
  var s ="";
  s = order.toString().split(",").join("");
  fill(255);
  text("Order: " + s, 10, height- 20);

  translate(0,20);
  stroke(255);
  beginShape();
  strokeWeight(2);
  noFill();
  for (let i = 0; i < cities.length; i++) {

    vertex(cities[order[i]].x, cities[order[i]].y);
  }
  endShape();

  fill("green");
  for (let i = 0; i < cities.length; i++) {
    ellipse(cities[i].x, cities[i].y, 10, 10);
  }



  var currentDistance = calcDistance(cities);

  if (currentDistance < shortestDistance) {
    shortestDistance = currentDistance;
    console.log("New Shortest distance found: " + shortestDistance);
    shortestPathFound = order.slice();
    //console.log(shortestPathFound);
  }

  translate(0, height/2);
  drawshortestPathFound(shortestPathFound);

  fill("green");
  for (let i = 0; i < cities.length; i++) {
    ellipse(cities[i].x, cities[i].y, 10, 10);
  }

  translate(0,-(height/2)+20);

  nextOrder();

  iterations++;

}

// Swap array members
function swap(arr, i, j) {
    var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function calcDistance(points) {
  var totalDist = 0;
  for (let i = 0; i < order.length -1; i++) {
    var currentCity = order[i];
    var nextCity = order[i+1];
    totalDist += dist(
      points[currentCity].x,
      points[currentCity].y,
      points[nextCity].x,
      points[nextCity].y
    );
  }

  console.log(totalDist);
  return totalDist;
}


// Lexicographic ordering alogortithm
function nextOrder() {
  
  // 1. Find the largest i such that P[i]<P[i+1]
 
  var largestI = -1; // start with a negative index
 
  for (let i = 0; i < order.length-1; i++) {
    if(order[i] < order[i +1])
    {
      largestI = i;
    }
    
  }
 
 
  // 1. Find the largest j such that P[i]<P[j]
  var largestJ = -1; // start with a negative index
 
  for (let j = 0; j < order.length; j++) {
   if(order[largestI] < order[j])
   {
     largestJ = j;
   }  
 }
 
 // 3. Swap largestI and LargestJ
 if(largestI != -1 || largestJ != -1){
   swap(order, largestI ,largestJ);
 }
 
 // 4. Reverse elements in the array from largestI + 1 to the end 
 var arrayEndReversed = order.splice(largestI+1).reverse();
 order = order.concat(arrayEndReversed);
 
 textSize(16);
 var s ="";
 s = order.toString().split(",").join("");
 fill(255);
 text("Order: " + s, 10, height- 20);
  
 
  // If no such i (such that P[i]<P[i+1]) we are finished
  if(largestI == -1)
  {   
    noLoop();
    console.log("Finished");
  }
 
  
 }


 function factorial(n){
  if(n<0){
    return -1;
  }
  else if(n == 0){
    return 1;
  }
  else{

    return n * factorial(n-1);
  }

 }