#include <math.h>
#include <limits.h>
#include <stdio.h>

#include "TwoDView.h"
#include "tspheaders.h"
#include "prototypes.h"
/********************************************************************/
/* This file contains a number of miscellaneous functions used in all
   of the TSP algorithms.
*/
/********************************************************************/



/********************************************************************/
/* Function: kfrom
   given i and j, figure out what the k coordinate is.
*/
/********************************************************************/
int kfrom(int l, int m, int n)
{ 
int i,j,k;

if (l < m) {
  i = l;
  j = m;
}
else {
  i = m;
  j = l;
}

k = i*n - i*(i+1)/2+j-i-1;
return(k);
}     

/********************************************************************/
/* Function: ClosestCities
   given a list of cities, figure out which two are closest, and
   return the distance between them.  
   From and To will contain the indices of the cities.
   The function returns the distance between them.
*/
/********************************************************************/
float ClosestCities(float *Distance, int *From, int *To, int NumberOfCities) {
int i,j,k;
float MinDistance;

MinDistance = INT_MAX;
for(i=0;i<NumberOfCities;i++) {
  for(j=(i+1);j<NumberOfCities;j++) {
    k = kfrom(i,j,NumberOfCities);
    if (Distance[k] < MinDistance) {
#ifdef DEBUGMYDIR
      printf("k is %d i is %d j is %d \n",k,i,j);
      printf("changing mindistance from %f to %f \n",MinDistance,Distance[k]);
#endif
      MinDistance = Distance[k];
      *From = i;
      *To = j;
    }
  }
}

return(MinDistance);
}

/********************************************************************/
/* Function: FarthestCities
   given a list of cities, figure out which two are farthest, and
   return the distance between them.
   From and To will contain the indices of the cities.
   The function returns the distance between them.
*/
/********************************************************************/
float FarthestCities(float *Distance, int *From, int *To, int NumberOfCities) {
int i,j,k;
float BigDistance;

BigDistance = 0;
for(i=0;i<NumberOfCities;i++) {
  for(j=(i+1);j<NumberOfCities;j++) {
    k = kfrom(i,j,NumberOfCities);
    if (Distance[k] > BigDistance) {
 #ifdef DEBUGMYDIR
      printf("k is %d i is %d j is %d \n",k,i,j);
      printf("changing bigdistance from %f to %f \n",BigDistance,Distance[k]);
 #endif
      BigDistance = Distance[k];
      *From = i;
      *To = j;
    }
  }
}

return(BigDistance);
}


/********************************************************************/
/* Function: ValidTour
   given a tour and 2 edges to exchange, figure out if the tour is
   valid if the two edges are exchanged.
*/
/********************************************************************/
int ValidTour(int *Tour, int Edge1, int Edge2, int Reverse, 
              int NumberOfCities) {

int i,To1,BeginningCity,CurrentCity,GoingThroughTour,IsATour,
    StillLooking,AtEdge,NextEdge,NumberOfCitiesVisited;

int *TestingTour;

/* allocate space for TestingTour */
TestingTour = (int *)malloc(2*NumberOfCities*sizeof(int));
if (TestingTour == (int *) 0)
  printf("Malloc for TestingTour failed. \n");
 for (i=0;i<2*NumberOfCities;i+=2) {
   TestingTour[i] = Tour[i];
   TestingTour[i+1] = Tour[i+1];
 }

/* exchange the edges in the tour. */
/* if Reverse == 1, then make To From and From To. */
if (Reverse) {
  To1 = TestingTour[2*Edge1+1];
  TestingTour[2*Edge1+1] = TestingTour[2*Edge2+1];
  TestingTour[2*Edge2+1] = To1;
}
else {
/* if Reverse == 0, then take the second edge as is. */
  To1 = TestingTour[2*Edge1+1];
  TestingTour[2*Edge1+1] = TestingTour[2*Edge2];
  TestingTour[2*Edge2] = To1;
}

GoingThroughTour = 1;
IsATour = 0;
BeginningCity = TestingTour[0];
CurrentCity = TestingTour[1];
NumberOfCitiesVisited = 0;
AtEdge = 0;

while (GoingThroughTour) {
  /* set NextEdge to be the next edge after AtEdge in the tour. */
  if (AtEdge >= (NumberOfCities-1)) {
    NextEdge = 0;
  }
  else {
    NextEdge = AtEdge + 1;
  }

  StillLooking = 1;
  while ((StillLooking) && (GoingThroughTour)) {
    
    /* look to see if the To of NextEdge is the city we want. */
    if (TestingTour[2*NextEdge] == CurrentCity) {
      NumberOfCitiesVisited+=1;
      if (CurrentCity == BeginningCity) {
        if (NumberOfCitiesVisited == NumberOfCities) {
          /* then we have found a valid tour. */
          IsATour = 1;
          GoingThroughTour = 0;
        }
        else {
          /* otherwise, this tour has subtours. */
          GoingThroughTour = 0;
        }
      }
      CurrentCity = TestingTour[2*NextEdge+1];
      AtEdge = NextEdge;
      StillLooking = 0;
    }
    else {
      /* look to see if the From of NextEdge is the city we want. */
      if (TestingTour[2*NextEdge+1] == CurrentCity) {
        NumberOfCitiesVisited+=1;
        if (CurrentCity == BeginningCity) {
          if (NumberOfCitiesVisited == NumberOfCities) {
            /* then we have found a valid tour. */
            IsATour = 1;
            GoingThroughTour = 0;
          }
          else {
            /* otherwise, this tour has subtours. */
            GoingThroughTour = 0;
          }
        }
            
        CurrentCity = TestingTour[2*NextEdge];
        AtEdge = NextEdge;
        StillLooking = 0;
      }
    }

    /* get ready to look at the next edge. */
    if (AtEdge >= (NumberOfCities-1)) {
      if (NextEdge == (AtEdge-1)) {
        StillLooking = 0;
        GoingThroughTour = 0;
      }
      else {
        NextEdge+=1;
      }
    }
    else {
      if (NextEdge >= (NumberOfCities - 1)) {
        NextEdge = 0;
      }
      else {
        NextEdge+=1;
      }
    }
  }
}
free(TestingTour);
return(IsATour);
}
  
  
  
