//////////////////////////////////////////////////////////////////////////
// Traveling Salesman Problem with PThreads.
// Note: this is a C++ program: compile it with CC (not cc)
//
// Starting city is assumed to be city 0.
//////////////////////////////////////////////////////////////////////////

#include <iostream.h>
#include <stdlib.h>
#include <limits.h>
#include <assert.h>
#include <pthread.h>

#include "tsp.h"

Path Shortest;
Queue Q;

int NumCities, NumThreads;

int **Dist;			// Dist[i][j] =  distance from  i to j

// This is another way to initialize these things:
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

///////////////////////////////////////////////////////////////////////////

Path::Path ()
{ 
  length=0; 
  visited=1;
  for (int i=0; i<NumCities; i++) city[i]=i;
}

void Path::AddCity (int i)
{
  assert(visited<=i && i<NumCities);

  // swap city[i] and city[visted]
  int tmp = city[visited];
  city[visited] = city[i];
  city[i] = tmp;

  // visit city[visited]
  length += Dist[city[visited-1]][city[visited]];
  visited++;
}

void Path::Print()
{
  for (int i=0; i<visited; i++) cout << ' ' << city[i];
  cout << "; length = " << length << endl;
}

///////////////////////////////////////////////////////////////////////////

void Queue::Put(Path *P) 
{ 
  pthread_mutex_lock(&Qlock);
  assert(size<MAXQSIZE); 
  path[size++]=P;
  pthread_cond_signal(&Qcond);   // in case someone was waiting in Queue
  pthread_mutex_unlock(&Qlock);
}

Path *Queue::Get()
{
  pthread_mutex_lock(&Qlock);
  while (size==0) {             // note the while here
				// why is it necessary (instead of an if)?
    waiting++;
    if (waiting==NumThreads) {  // tell the others that everybody's waiting
      pthread_cond_broadcast(&Qcond);
      pthread_mutex_unlock(&Qlock);
      return NULL;
    }
    else {
      pthread_cond_wait(&Qcond, &Qlock); // wait, since other threads may put paths
      if (waiting==NumThreads) {
	// if this happens after awakening, then we are done
	pthread_mutex_unlock(&Qlock);
	return NULL;
      }
    } 
    waiting--;
  }

  // find the shortest path in the queue
  int best = 0;
  for (int i=1; i<size; i++) {
    if (path[i]->length < path[best]->length)
      best = i;
  }

  // to decrease the size of the queue, move the last element
  Path *p = path[best]; 
  path[best] = path[--size];

  pthread_mutex_unlock(&Qlock);
  return p;
}

///////////////////////////////////////////////////////////////////////////

void Fill_Dist()
{
  cout << "Distance matrix:\n";
  Dist = new int*[NumCities];
  for (int i=0; i<NumCities; i++) {
    Dist[i] = new int[NumCities];
    for (int j=0; j<NumCities; j++) {
      // Not necessary, but let's make Dist simmetric:
      if (i==j) 
	Dist[i][j] = 0;
      else if (j<i) 
	Dist[i][j] = Dist[j][i];
      else
	Dist[i][j] = rand()%1000; 
      cout << Dist[i][j] << '\t';
    }
    cout << endl << endl;
  }
}


void* tsp (void* arg)
{ 
  while (!Q.isEmpty()) {
    Path *p = Q.Get(); 
    
    // For each city not yet visited, extend the path:
    for (int i=p->visited; i<NumCities; i++) {
      Path *q = new Path(*p);	// initially q is a clone of p
      q->AddCity(i);

      // decide what to do with new path
      if (q->visited==NumCities) {
	// Add last hop to return to origin:
	q->length += Dist[q->city[NumCities-1]][0];

	// update Shortest, if q is better
	pthread_mutex_lock(&mutex);
	if (q->length < Shortest.length) Shortest = *q;
	pthread_mutex_unlock(&mutex);

	delete q;
      } 
      else {
	Q.Put(q);
	// Possible optimization: compute lower bound
	// to complete this path; discard if bad
      }
    }

    delete p;			// p is not needed any more
  }
}


int main(int argc, char *argv[])
{
  if (argc!=3) {
    cout << "Usage: " << argv[0] << " num_cities num_threads\n";
    exit(-1);
  }  

  NumCities = atoi(argv[1]);
  assert(NumCities<=MAXCITIES);
  NumThreads = atoi(argv[2]);

  Fill_Dist();			// initialize Distance matrix

  Path *P = new Path;    
  Q.Put(P);			// initialize Q with one zero-length path
  Shortest.length = INT_MAX;    // The initial Shortest path must be bad

  pthread_t thread;		// just a dummy variable

  for (int i=1; i<NumThreads; i++) 
    if (pthread_create (&thread, NULL, tsp, NULL) != 0 )
      perror("Can't create thread");

  tsp(NULL);			// no reason to exempt this thread from working
  
  // if we are done, then everybody's done, so no reason to join

  cout << "Shortest path:";
  Shortest.Print();

}