
#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 Addition 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 157.

*/
/************************************************************************/
/* 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 NearestAddition(float *Distance,int *Tour,int NumberOfCities) {
#else
float NearestAddition(TwoDView *self,float *data,float *Distance,int *Tour,
                        int NumberOfCities) {
#endif
int i,j,k,m,x,y,I,J,
    From,To,BaseCity,ArcEnd,ReplaceIndex,CurrentCity,
    SubTourEnd,TourIndex,NewCity,NotFound;
int *OnTour, *TourCities;
float NewDistance,OptimalValue;

/* allocate space for OnTour and TourCities */
OnTour = (int *)malloc(NumberOfCities*sizeof(int));
TourCities = (int *)malloc(NumberOfCities*sizeof(int));
if (OnTour == (int *) 0)
  printf("Malloc for OnTour failed. \n");
if (TourCities == (int *) 0)
  printf("Malloc for OnTour failed. \n");
for (i=0;i<NumberOfCities;i++) {
   OnTour[i] = 0;
 }
for (i=0;i<NumberOfCities;i++) {
   TourCities[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 */
 /* these two cities make up the initial subtour  */
 NewDistance = ClosestCities(Distance,&From,&To,NumberOfCities);

 /* if NewDistance doesn't change, there is a problem ... */
 if (NewDistance == 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,NewDistance);
 }
 #endif

 /* OnTour is a list of cities on the tour already. */
 Tour[0] = Tour[3] = From;
 Tour[1] = Tour[2] = To;
 OnTour[From] = OnTour[To] = 1;
 TourCities[0] = From;
 TourCities[1] = To;
 OptimalValue = 2*NewDistance;

 SubTourEnd = 1;
 TourIndex = -1;
 NewCity = NumberOfCities;
 NewDistance = INT_MAX; 

 /* keep adding cities until you include all NumberOfCities of them */
 while (SubTourEnd < NumberOfCities-1) {
 #ifdef DEBUGMYDIR
   printf("Start of Iteration with %d cities in tour \n",SubTourEnd+1);
 #endif
   /* at the end of this while loop, there will be a new city to insert */
   while (TourIndex < SubTourEnd) {
     /* look at the next city already on the tour */
     TourIndex+=1;
     CurrentCity = TourCities[TourIndex];
 #ifdef DEBUGMYDIR
	   printf("Looking at city %d \n",CurrentCity);   
 #endif
     /* look at all arcs starting at CurrentCity */
     I = ArcIndex(CurrentCity,NumberOfCities);
     J = ArcIndex((CurrentCity+1),NumberOfCities);
     for (i=I;i<J;i++) {
       /* j = terminating end of this arc */
       j = i-I+CurrentCity+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(CurrentCity,j,NumberOfCities);
	 if (Distance[k] < NewDistance) {
 #ifdef DEBUGMYDIR
	   printf("Changing cities from %d to %d \n",NewCity,j);   
	   printf("Looking at city %d \n",CurrentCity);   
 #endif
	   NewDistance = Distance[k];
	   NewCity = j;
           BaseCity = CurrentCity;
	 } 
       } 
     }

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

   if (NewCity >= NumberOfCities) {
     printf("Error: new city has not been found for tour. \n");
     CurrentCity = SubTourEnd = NumberOfCities;
     OptimalValue = -1;
   }
   else {
     /* find an arc connected to BaseCity, and replace it with
        the new arc. */
     k = 0;
     NotFound = 1;
     while ((k < SubTourEnd) && (NotFound)) {
       if (Tour[2*k] == BaseCity) {
         ArcEnd  = Tour[2*k+1];
         ReplaceIndex = k;
         NotFound = 0;
       }
       if (Tour[2*k+1] == BaseCity) {
         ArcEnd = Tour[2*k];
         ReplaceIndex = k;
         NotFound = 0;
       }
       k+=1;
     }
     
     if (NotFound) {
       printf("Error: Haven't found arc on Tour Ending at %d \n",BaseCity); 
       CurrentCity = SubTourEnd = NumberOfCities;
       OptimalValue = -1;
     }
     else {
       /* arc between BaseCity and ArcEnd is replaced by arc
          between NewCity and ArcEnd. */
 #ifdef DEBUGMYDIR
       printf("replacing arc from %d to %d with %d to %d \n",
               BaseCity,ArcEnd,NewCity,ArcEnd);
 #endif
       Tour[2*ReplaceIndex] = NewCity;
       Tour[2*ReplaceIndex+1] = ArcEnd;

       /* update the Optimal Value */
       OptimalValue+=Distance[kfrom(NewCity,ArcEnd,NumberOfCities)] -
                     Distance[kfrom(BaseCity,ArcEnd,NumberOfCities)];

       /* add the new arc going from NewCity to BaseCity */
 #ifdef DEBUGMYDIR
       printf("adding arc from %d to %d \n",NewCity,BaseCity);
 #endif
       SubTourEnd+=1;
       Tour[2*SubTourEnd] = NewCity;
       Tour[2*SubTourEnd+1] = BaseCity;
       OnTour[NewCity] = 1;
       TourCities[SubTourEnd] = NewCity;
    
       /* update the Optimal Value */  
       OptimalValue+=NewDistance;

 #ifdef DEBUGMYDIR
       printf("addding %f to Opval to get %f \n",NewDistance,OptimalValue);
 #endif
     }

     /* get ready to start at the top of the list again */
     TourIndex = -1;
     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
    
}
}

/* clean up */
free(OnTour);

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