
#include <stdlib.h>
#ifdef MYDIR
#else
#include "TwoDView.h"
#include "TwoDTSP.h"
#include <appkit/graphics.h>
#endif
#include <math.h>
#include <limits.h>
#include <stdio.h>
#include "tspheaders.h"
#include "prototypes.h"

/************************************************************************/
/* This function implements the Nearest Neighbor Algorithm for the
   Travelling Salesperson Algorithm.  It provides an approximate optimal
   value rather than the optimal value. 

   Reference: Lawler, Lenstra, et. al., The Traveling Salesman [sic] Problem, 
             1985, Wiley and Sons, p 150.
*/
/************************************************************************/
/* Parameters:   TwoDView *self: Ye Old Drawing Object

                    float *Data: Pointer to the list of points.
                                 Used to draw intermediate graph.

                float *Distance: Pointer to area that contains the
                                 Distances Between Each Pair of Cities

                      int *Tour: Pointer to area that will contain the
                                 indices of the n arcs that are selected 
                                 to be a part of the tour

             int NumberOfCities: Number of cities in the problem
*/
/************************************************************************/
/************************************************************************/
#ifdef MYDIR
float NearestNeighbor(float *Distance,int *Tour,int NumberOfCities) {
#else
float NearestNeighbor(TwoDView *self,float *data,float *Distance,int *Tour,
                        int NumberOfCities) {
#endif
int i,j,k,x,y,I,J,From,To,FirstCity,LastCity,MthCity,SubTourEnd,NewCity;
int *OnTour;
float ThisDistance,NewDistance,OptimalValue;
char msg[256];

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

#ifdef DEBUGMYDIR
for (i=0;i<(NumberOfCities-1)*NumberOfCities/2;i++) {
  printf("Distance[%d] = %f; \n",i,Distance[i]);
}
#endif

/* find the two cities with the minimum distance */
ThisDistance = ClosestCities(Distance,&From,&To,NumberOfCities);

/* if ThisDistance doesn't change, there is a problem ... */
if (ThisDistance == INT_MAX) {
  printf("Error no initial subtour found. \n");
}
#ifdef DEBUGMYDIR
else {
  printf("initial subtour \n");
  printf("from %d to %d distance %f \n",From,To,ThisDistance);
}
#else
sprintf(msg,"from %d to %d distance %f \n",From,To,ThisDistance);
STATUS(msg);
#endif

/* given a subtour of m cities, add city m+1 closest to the mth city. */

/* OnTour indicates status of city 
   1 -- city is on tour 
   0 -- city is not yet on the tour */

Tour[0]  = From;
Tour[1]  = To;
OnTour[From] = OnTour[To] = 1;

FirstCity = From;
MthCity = To;
OptimalValue = ThisDistance;
SubTourEnd = 0;

NewDistance = INT_MAX; 
NewCity = NumberOfCities;

/* keep adding cities until you include all NumberOfCities of them */
while (SubTourEnd < NumberOfCities-2) {

#ifdef DEBUGMYDIR
  printf("Start of Iteration with %d cities in tour \n",SubTourEnd+1);
  printf("MthCity is %d \n",MthCity);
#else
sprintf(msg,"%d cities in tour",SubTourEnd+1);
STATUS(msg);
#endif

  /* look at all arcs starting at From */
  I = ArcIndex(MthCity,NumberOfCities);
  J = ArcIndex((MthCity+1),NumberOfCities);
  for (i=I;i<J;i++) {
    /* j = terminating end of this arc */
    j = i-I+MthCity+1;
    /* if the city at the other end isn't already on the tour ...*/
    if (!OnTour[j]) {
      /* Is the arc a new candidate for insertion? */
      k = kfrom(MthCity,j,NumberOfCities);
      ThisDistance = Distance[k];
      if (ThisDistance < 0) {
        printf("Error: ThisDistance = %f for MthCity %f j %f \n",MthCity,j);
      }
      if (ThisDistance < NewDistance) {
#ifdef DEBUGMYDIR
        printf("Changing new city from %d to %d \n",NewCity,j);    
	printf("MthCity, j, %d %d \n",MthCity,j);
#else
	sprintf(msg,"from %d to %d distance %f \n",From,To,ThisDistance);
	STATUS(msg);
#endif
	NewDistance = ThisDistance;
	NewCity = j;
      } 
    }
  }

  /* look at all arcs ending at MthCity */
  for (i=0;i<MthCity;i++) {
    /* if the starting city isn't already on the tour ...*/
    if (!OnTour[i]) {
      /* Is this arc a new candidate for insertion? */
      k = kfrom(i,MthCity,NumberOfCities);
      ThisDistance = Distance[k];
      if (ThisDistance < 0) {
        printf("Error: ThisDistance = %f for MthCity %f  i %f \n",MthCity,i);
      }
      if (ThisDistance < NewDistance) {
#ifdef DEBUGMYDIR
        printf("Changing cities from %d to %d \n",NewCity,i);   
	printf("MthCity, i,  %d %d \n",MthCity,i);
#else
	sprintf(msg,"Changing cities from %d to %d \n",NewCity,i);
	STATUS(msg);
#endif

	NewDistance = ThisDistance;
	NewCity = i;
      }
    }
  }

  if (NewCity >= NumberOfCities) {
    printf("Error: new city has not been found for tour. \n");
    SubTourEnd = NumberOfCities;
    OptimalValue = -1;
  }
  else {
    /* add the new arc going from MthCity to NewCity to Tour */
#ifdef DEBUGMYDIR
    printf("adding arc from %d to %d \n",MthCity,NewCity);
#endif
    SubTourEnd+=1;
    Tour[2*SubTourEnd] = MthCity;
    Tour[2*SubTourEnd+1] = NewCity;
    OnTour[NewCity] = 1;

    /* update the Optimal Value */  
    OptimalValue+=NewDistance;

#ifdef DEBUGMYDIR
      printf("adding %f to Opval to get %f \n",NewDistance,OptimalValue);
#else
    sprintf(msg,"adding %f to Opval to get %f \n",NewDistance,OptimalValue);
    STATUS(msg);
#endif

    /* get ready to start at the top of the list again */
    LastCity = NewCity;
    MthCity = NewCity;
    NewDistance = INT_MAX; 
    NewCity = NumberOfCities; 

#ifdef DEBUGMYDIR
    /* print out current subtour */
    for (i=0;i<2*(SubTourEnd+1);i++) {
      printf("i tour %d %d \n",i,Tour[i]);
    }
#endif
#ifdef MYDIR
#else
    /* draw the intermediate tour */
    PSnewinstance();
    for(i=0;i<2*(SubTourEnd+1);i+=2) { 
      x = Tour[i];
      y = Tour[i+1];
     [self drawEdge:X(x):Y(x):X(y):Y(y)];
    }
    NXPing();
    [self->optimalValueField setFloatValue: OptimalValue at: 0];
    usleep(self->drawTime);
#endif
  }
}

/* add the final arc going from the first city to the last city */
SubTourEnd+=1;
Tour[2*SubTourEnd] = LastCity;
Tour[2*SubTourEnd+1] = FirstCity;
k = kfrom(FirstCity,LastCity,NumberOfCities);

#ifdef DEBUGMYDIR
      printf("adding %f to Opval to get %f \n",Distance[k],OptimalValue);
#else
    sprintf(msg,"adding %f to Opval to get %f \n",NewDistance,OptimalValue);
    STATUS(msg);
#endif
OptimalValue = OptimalValue + Distance[k];
[self->optimalValueField setFloatValue: OptimalValue at: 0];
/* clean up */
free(OnTour);

/* return the optimal value */
return(OptimalValue);
}
        
