Untitled

/**
 * tsp.c
 * Builds tours of cities in input according to one of three possible
 * heuristics.  Names of cities are given on the command line along
 * with the heuristics to use and the name of a file containing the
 * locations (latitude, longitude) of the cities.  For example,
 *
 * ./TSP ne_6.dat -given -nearest -insert HVN ALB MHT BDL ORH PVD
 *
 * where ne_6.dat could contain
 *
 * HVN,41.26388889,-72.88694444
 * ALB,42.74916667,-73.80194444
 * MHT,42.93277778,-71.43583333
 * BDL,41.93916667,-72.68333333
 * ORH,42.26722222,-71.87555556
 * PVD,41.72388889,-71.42833333   
 *
 * @author CPSC 223 Staff and you
 * @version 2025.01.31.0
 */

#define _GNU_SOURCE

// SEE THIS FILE FOR DECLARATIONS AND DOCUMENTATION OF SUGGESTED FUNCTIONS
#include "tsp.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>
#include <math.h>

#include "location.h"

int main(int argc, char **argv)
{
  int exit_code = 0;
  // the index on the command line of the origin city
  // TODO: this is hard-coded as if there is always one method
  // after the filename; fix that to account for more than one
  
  // *** CHANGED ***:
  // Instead of hard-coding origin=3, we parse the command line to find 
  // where city names begin (i.e., the first non-'-' argument after argv[1]).
  // We'll call that "origin".
  if (argc < 3)
    {
      // Not enough arguments: must at least have datafile + 2 city names (or 1 heuristic + 1 city, etc.)
      fprintf(stderr, "Usage: %s datafile [heuristics...] city1 city2...\n", argv[0]);
      exit_code = 1;
      goto cleanup;

    }

  // *** ADDED ***: Identify the heuristics vs. city names.
  size_t origin = 0;  // will store the index of the first city name
  for (size_t i = 2; i < (size_t)argc; i++)
    {
      if (argv[i][0] != '-')
        {
          origin = i;
          break;
        }
    }

  // *** ADDED ***: Check for error if no city arguments were found
  if (origin == 0 || (argc - origin) < 2)
    {
      fprintf(stderr, "Error: need at least one data file and at least two cities.\n");
      exit_code = 1;
      goto cleanup;

    }

  // the number of cities on the command line
  // TODO: maybe add some more error checking here

  // *** CHANGED ***: Instead of "size_t origin=3", we do:
  size_t num_cities = argc - origin;

  // *** ADDED ***: Also handle the data filename
  const char *filename = argv[1];

  // *** ADDED ***: We'll store heuristics (the args from 2..(origin-1) that start with '-')
  // so we can apply them later in the order encountered.
  char *heuristics[100];
  size_t hcount = 0;
  for (size_t i = 2; i < origin; i++)
    {
      // This is presumably a heuristic, e.g. -given, -nearest, -insert
      heuristics[hcount++] = argv[i];
    }

  // *** ADDED ***: We'll store the city names as typed
  char *cityNames[1000];
  for (size_t i = 0; i < num_cities; i++)
    {
      cityNames[i] = argv[origin + i];
    }

  // initialize names and indices of cities in the tour
  // TODO: read coordinates from the file and make this work for any
  // cities on the command line; you will need to do something
  // different to allocate and initialize the array since this assumes
  // there are 6 (HVN ALB MHT BDL ORH PVD), but you can use this to test
  // the algorithms without having to worry about reading input

  // *** REMOVED *** the old hard-coded array
  // *** ADDED ***: We'll read from the file using read_file or inline logic
  FILE *fp = fopen(filename, "r");
  if (!fp)
    {
      fprintf(stderr, "Error: cannot open file %s\n", filename);
      exit_code = 1;
      goto cleanup;
    }

  // We can read up to 1000 cities from the file
  city allCities[1000];
  size_t readCount = read_file(fp, 1000, allCities);  // see read_file below
  fclose(fp);

  // *** ADDED ***: We must match each city from cityNames[] to the data in allCities[].
  // We'll build an array "citiesFinal" in the order typed on the command line.
  city citiesFinal[1000];
  for (size_t c = 0; c < num_cities; c++)
    {
      bool found = false;
      for (size_t j = 0; j < readCount; j++)
        {
          // match by city name
          if (strcmp(cityNames[c], allCities[j].name) == 0)
            {
              citiesFinal[c] = allCities[j];
              // The "index" is the order in which the city was typed
              citiesFinal[c].index = c;
              found = true;
              break;
            }
        }
      if (!found)
        {
          fprintf(stderr, "Error: city '%s' not found in data file.\n", cityNames[c]);
          exit_code = 1;
          goto cleanup;
        }
    }

  // iterate over methods requested on command line

  // *** CHANGED ***: Now we have "hcount" heuristics in heuristics[], 
  // each one we apply in order to a *copy* of citiesFinal.
  // Then we print the result. 
  if (hcount == 0)
    {
      // If no heuristics, produce no output
      return 0;
    }

  for (size_t a = 0; a < hcount; a++)
    {
      // Make a fresh working copy
      city working[1000];
      for (size_t i = 0; i < num_cities; i++)
        {
          working[i] = citiesFinal[i];
        }

      if (strcmp(heuristics[a], "-insert") == 0)
        {
          route_insert(num_cities, working);
        }
      else if (strcmp(heuristics[a], "-nearest") == 0)
        {
          route_nearest(num_cities, working);
        }
      else if (strcmp(heuristics[a], "-given") == 0)
        {
          // do nothing: "given" means the city order is as typed
        }
      // if unknown heuristic, we just skip it or do nothing

      normalize_start(num_cities, working);
      normalize_direction(num_cities, working);

      double total = calculate_total(num_cities, working);
      printf("%-10s: %12.2f ", heuristics[a], total);
      print_tour(num_cities, working);
    }

  // TODO: there may be other opportunities for error checking!
    cleanup: // label for memory deallocation
        // ALWAYS free memory so no leaks remain
        for (size_t i = 0; i < readCount; i++)
        {
            free((void *)allCities[i].name);
            // casting away const if needed; or make name a plain char*
        }
 return exit_code;
}


void route_insert(size_t n, city tour[])
{
  size_t best_orig, best_dest;
    find_closest_pair(n, tour, &best_orig, &best_dest);

    // put them in positions [0] and [1]
    swap(tour, 0, best_orig);
    if (best_dest == 0)
        best_dest = best_orig;
    swap(tour, 1, best_dest);

    size_t subtour_len = 2;

    // Insert the rest
    while (subtour_len < n)
    {
        // pick city closest to entire subtour
        size_t next = find_closest_to_tour(n, tour, subtour_len);

        // find best insertion spot
        size_t ins = find_insertion_point(n, tour, subtour_len, next);

        // shift the city from index 'next' into 'ins'
        city temp = tour[next];
        for (size_t k = next; k > ins; k--)
        {
            tour[k] = tour[k - 1];
        }
        tour[ins] = temp;

        subtour_len++;
    }
}

void find_closest_pair(size_t n, city tour[], size_t *best_orig, size_t *best_dest)
{
  double min_dist = 41000.0; // larger than the world's circumfrence in km
  for (size_t i = 0; i < n; i++)
    {
      for (size_t j = i + 1; j < n; j++)
        {
          double dist = location_distance(&tour[i].loc, &tour[j].loc);
          if (dist < min_dist)
            {
              min_dist = dist;
              *best_orig = i;
              *best_dest = j;
            }
        }
    }
}

size_t find_closest_to_tour(size_t n, city tour[], size_t tour_len)
{
    size_t best_index = tour_len; // start by picking the first uninserted city
    double best_dist  = 47000.0;

    for (size_t i = tour_len; i < n; i++)
    {
        // distance from city i to the subtour is 
        // the min distance to any city in [0..tour_len-1]
        double dist_i = 47000.0;
        for (size_t j = 0; j < tour_len; j++)
        {
            double d = location_distance(&tour[i].loc, &tour[j].loc);
            if (d < dist_i)
                dist_i = d;
        }
        if (dist_i < best_dist)
        {
            best_dist = dist_i;
            best_index = i;
        }
    }
    return best_index;
}



size_t find_insertion_point(size_t n, city tour[], size_t subtour_len, size_t next)
{
  double best_increase = 1e20;
    size_t best_pos      = 0;

    for (size_t i = 0; i < subtour_len; i++)
    {
        size_t i_next = (i + 1 == subtour_len) ? 0 : (i + 1);

        double old_dist = location_distance(&tour[i].loc, &tour[i_next].loc);
        double new_dist = location_distance(&tour[i].loc, &tour[next].loc)
                        + location_distance(&tour[next].loc, &tour[i_next].loc);
        double increase = new_dist - old_dist;

        if (increase < best_increase)
        {
            best_increase = increase;
            best_pos = i + 1; 
        }
    }
    return best_pos;
}

void route_nearest(size_t n, city tour[])
{
  for (size_t i = 0; i < n - 1; i++)
  {
    size_t j = find_closest_city(tour, i, i + 1, n - 1);
    swap(tour, i + 1, j);
  }
}

size_t find_closest_city(city tour[], size_t c, size_t from, size_t to)
{
  size_t best_index = from;     //initializing index by starting it at from
  double best_distance = location_distance(&tour[c].loc,&tour[from].loc);    //initializing location distance by having the best distance b between c and from
  for (size_t i = from + 1; i <= to; i++)
  {
    double distance = location_distance(&tour[c].loc,&tour[i].loc); // loops through and stores distance between c and i loop 

    if (distance < best_distance)
    {
      best_distance = distance; // setting new best_distance
      best_index = i;
    }
  }
  return best_index;
}

double calculate_total(size_t n, city tour[])
{
  double tot = 0.0;
  for (int i = 0; i < n; i++) 
  {
    tot += location_distance(&tour[i].loc,&tour[(i+1) % n].loc);
  }
  return tot;
}

void swap(city arr[], size_t i, size_t j)
{
  if (i != j)
    {
      city temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
}

void normalize_start(size_t n, city tour[])
{
  int results = 0;
  for (int i = 0; i < n; i++) 
  {
    if (tour[i].index == 0)
    {
      results = i;
      break;
    }
  }
  city temp[n];
  for (int i = 0; i < n; i++) 
  {
    temp[i] = tour[(results + i) % n];
  }
  for (int i = 0; i < n; i++) 
  {
    tour[i] = temp[i];
  }
}

void normalize_direction(size_t n, city tour[])
{
    if (n < 2) {
        return;
    }

    if (tour[n-1].index < tour[1].index)
    {
        size_t left = 1;
        size_t right = n - 1;
        while (left < right)
        {
            swap(tour, left, right);
            left++;
            right--;
        }
    }
}

int read_file(FILE *in, size_t n, city cities[])
{
  size_t count = 0;

  // keep reading lines until we reach 'n' or EOF
  while (count < n)
    {
      char line[256];
      if (!fgets(line, sizeof(line), in))
        {
          break; // no more lines
        }
      // parse
      char code[128];
      double lat, lon;
      // city names can contain anything except commas or newlines
      // so we read until the first comma, then lat, then lon
      int scanned = sscanf(line, "%[^,],%lf,%lf", code, &lat, &lon);
      if (scanned == 3)
        {
          // store in our array
          // we can allocate a copy of 'code' or store a pointer if safe
          // We'll do a simple approach: store code in a buffer
          // but in a real scenario we might do a safer dynamic approach
          char *name_copy = malloc(strlen(code) + 1);
          if (!name_copy) 
            {
              fprintf(stderr, "Out of memory.\n");
              exit(1);
            }
          strcpy(name_copy, code);

          cities[count].name = name_copy; 
          cities[count].loc.lat = lat;
          cities[count].loc.lon = lon;
          cities[count].index = 0;  // will be overridden later
          count++;
        }
      else
        {
          // malformed line or partial data
          // we can ignore or break
          // We'll just ignore for now
        }
    }

  return count;
}

void print_tour(size_t n, city cities[])
{
  if (n == 0)
    {
      return;
    }
  
  fprintf(stdout, "%s", cities[0].name);
  for (size_t i = 1; i < n; i++)
    {
      fprintf(stdout, " %s", cities[i].name);
    }
  fprintf(stdout, " %s\n", cities[0].name);
}