/*
 * sort_city.c
 * This program reads city listings from a file and sorts them in several ways.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LINE 100
#define MAX_NAME 50

/* A city listing: */
struct _City
{
  char   *name;             /* The city name. */
  char   *country;          /* In which state it is located. */
  int    population;        /* Its population. */
};

typedef struct _City City;

/* A comparison function for two cities by their population: */
int comp_city_by_population (const void *p1, const void *p2)
{
  const City *p_city1 = *((const City **) p1);
  const City *p_city2 = *((const City **) p2);

  return (p_city2->population - p_city1->population); 
}

/* A comparison function for two cities by their name: */
int comp_city_by_name (const void *p1, const void *p2)
{
  const City *p_city1 = *((const City **) p1);
  const City *p_city2 = *((const City **) p2);

  return (strcmp (p_city1->name, p_city2->name)); 
}

/* Prototypes: */
int read_cities (const char *filename, City ***p_p_cities, int *n_cities);
void free_cities (City **p_cities, int n_cities);

/* ------------------------------------------------------------------------
 * The main:
 */
int main ()
{
  City       **p_cities;       /* A vector of pointers to city objects. */
  int        n_cities;         /* Its size. */
  int        rc;
  int        i;
  
  /* Read the city listings from the input file "cities.txt". */
  rc = read_cities ("cities.txt", &p_cities, &n_cities);

  if (rc == -1)
  {
    /* File was not found. */
    printf ("Failed to open the input file 'cities.txt'.\n");
    return (1);
  }
  else if (rc == -2)
  {
    /* Illegal file format. */
    printf ("The input file 'cities.txt' has an illegal format.\n");
    return (1);
  }

  /* Sort the cities by their name. */
  qsort (p_cities, n_cities, sizeof (City *),
         comp_city_by_name);

  printf ("Cities sorted by name:\n");
  for (i = 0; i < n_cities; i++)
    printf ("    %s, %s, %d\n",
            p_cities[i]->name, p_cities[i]->country, p_cities[i]->population);

  getchar();

  /* Sort the cities by their population. */
  qsort (p_cities, n_cities, sizeof (City *),
         comp_city_by_population);

  printf ("Cities sorted by population:\n");
  for (i = 0; i < n_cities; i++)
    printf ("%3d) %s, %s, %d\n", i+1,
            p_cities[i]->name, p_cities[i]->country, p_cities[i]->population);

  /* Free memory. */
  free_cities (p_cities, n_cities);

  return (0);
}

/* ------------------------------------------------------------------------
 * Function: read_cities
 * Purpose:  Allocate and read a vector of pointers to city entries.
 * Input:    filename   - The input file name.
 * Output:   p_p_cities - The allocated vector of pointers.
 *           n_cities   - The number of cities read.
 * Returns:   1 - Success.
 *           -1 - File cannot be opened.
 *           -2 - Illegal file format.
 */
int read_cities (const char *filename, 
		 City ***p_p_cities, int *n_cities)
{
  FILE       *p_file;         /* The input file. */
  City       **p_cities;      /* The vector of city pointers. */
  char       line[MAX_LINE];  /* Auxiliary line buffer. */
  const char *p_comma1;       /* The location of the first ',' in the line. */
  const char *p_comma2;       /* The location of the second ',' in the line. */
  int        l_name;          /* Length of the current city name. */
  int        l_country;       /* Length of the current country name. */
  int        i;               /* Current city index. */

  *p_p_cities = NULL;

  /* Open the input file. */
  p_file = fopen (filename, "r");

  if (p_file == NULL)
    return (-1);

  /* The input file should the city listings, using the following format:
     | n
     | city-1,country-1,population-1
     | city-2,country-2,population-2
     |   :       :           :
     | city-n,country-n,population-n

     Read the number of cities. */
  if (fgets (line, MAX_LINE, p_file) == NULL)
  {
    fclose (p_file);
    return (-2);
  }

  *n_cities = atoi(line);
  if (*n_cities == 0)
  {
    fclose (p_file);
    return (-2);
  }

  /* Allocate memory for the city listings and read them. */
  p_cities = (City **) malloc (sizeof(City *) * (*n_cities));

  for (i = 0; i < *n_cities; i++)
  {
    /* Read the current line. */
    if (fgets (line, MAX_LINE, p_file) == NULL)
    {
      fclose (p_file);
      return (-2);
    }

    /* Analyze the listing - locate the delimiting comma characters. */
    p_comma1 = strchr (line, ',');
    p_comma2 = (p_comma1 != NULL) ? strchr (p_comma1 + 1, ',') : NULL;

    if (p_comma1 == NULL || p_comma2 == NULL)
    {
      fclose (p_file);
      return (-2);
    }

    /* Allocate the current city and set its information. */
    p_cities[i] = (City *) malloc (sizeof(City));

    l_name = p_comma1 - line;
    p_cities[i]->name = (char *) malloc (sizeof(char) * (l_name + 1));
    strncpy (p_cities[i]->name, line, l_name);
    p_cities[i]->name[l_name] = '\0';

    l_country = p_comma2 - p_comma1 - 1;
    p_cities[i]->country = (char *) malloc (sizeof(char) * (l_country + 1));
    strncpy (p_cities[i]->country, p_comma1 + 1, l_country);
    p_cities[i]->country[l_country] = '\0';

    p_cities[i]->population = atoi(p_comma2 + 1);
  }

  /* Successful termination. */
  fclose (p_file);

  *p_p_cities = p_cities;
  return (1);
}

/* ------------------------------------------------------------------------
 * Function: free_cities
 * Purpose:  Free a vector of pointers to city entries.
 * Input:    n_cities - The number of cities in the vector.
 * In/Out:   p_cities - The vector to be freed.
 * Returns:  Nothing.
 */
void free_cities (City **p_cities, int n_cities)
{
  int    i;

  /* Go over the vector of cities and free each one. */
  for (i = 0; i < n_cities; i++)
  {
    free (p_cities[i]->name);
    free (p_cities[i]->country);
    free (p_cities[i]);
  }

  /* Free the entire vector. */
  free (p_cities);

  return;
}