// Programming Assignment 6 Example Solution
// CS 176, Summer 2001

#include <cstdlib>
#include <fstream>
#include <string>
#include <cctype>

// This is a fairly complicated problem, not because it's difficult, but
// because it requires lots of steps to solve.  However, by taking deep breaths
// and small steps, it can be sloved with a minimum of anguish.

// First, we need a data structure to represent the contents of a router-tables
// file and some handy operations on the representation.

struct router_record {

  // The name of the network segment to which this record applies.

     string segment_name;

  // The name of the router to which this record applies.

     string router_name;

  // The number of bytes in the router table for this router.

     int table_size;

  // A pointer to a block of dynamic memory containing the router table.

     char * router_table;

  // Initialize a router record.

     router_record() {
       segment_name = "";
       router_name = "";
       table_size = 0;
       router_table = 0;
       }

  // The routing table is a block of dynamic memory, and needs to be deleted
  // before the associated router-record value disappears, otherwise garbage
  // will result.  However, a router-record value need not have a router table,
  // in which case router_table will be 0.

    ~router_record() {
      if (router_table != 0)
	delete [] router_table;
      }

  // Print the contents of this router record to std-err.

     void print(void) const {
       cerr << "segment name is " << segment_name;
       cerr << ", router name is " << router_name;
       cerr << ", table size is " << table_size << ".\n";
       }

  // Compare this router record to the router record rr and return true if this
  // record is greater than rr.  A router record r1 is greater than the router
  // record r2 if either 
  //
  //   the segment name associated with r1 is greater than the segment name
  //   associated with r2; for example "Wilmington" > "Altoona"
  //
  // or
  //
  //   The two segment names are the same and the router name associated with
  //   r1 is greater than the router name associated with r2.
  //
  // The diligent reader will recognize this as a lexicographic order.

     bool operator > (const router_record & rr) const {
       return 
	 (segment_name > rr.segment_name) ||
	 ((segment_name == rr.segment_name) && (router_name > rr.router_name));
       }
  };

// To solve the problem, we need to
//
//  1 Read in the contents of the routing-table file.
//
      static router_record ** read_router_records(const string &);
//    
//  2 Sort the router tables to group network segments and order routers within
//    a segment.
//
      static void sort_router_records(router_record *[]);
//
//  3 Write the router-tables to the proper files.
//
      static void write_segment_files(router_record *[]);
//
//  4 Clean up and exit.


int main() {
  const string rt_filename = "routing-tables";
  router_record ** router_record_ptrs = read_router_records(rt_filename);

  sort_router_records(router_record_ptrs);

  write_segment_files(router_record_ptrs);

  for (int i = 0; router_record_ptrs[i] != 0; i++)
    delete router_record_ptrs[i];
  delete [] router_record_ptrs;
  }


// The tricky thing about reading records from the routing-table file is that
// we don't know how many records are in the file.  However, assuming we know
// how to read the next available record from the file
//
     static router_record * read_router_record(ifstream &);
//
// we can deal with this problem relatively easily by allocating some space for
// the routing-table records and re-allocating more space when needed.  
//
// The return value for read_router_records() should be an array of router
// records.  However, because each router record is large, it would be best to
// minimize copying costs from the old smaller to new larger array.  One way to
// do this is keep an array of pointers to router records; each pointer is
// considerably smaller than an router-record value.  Because the array may be
// larger than the number of records read, the next element after the last
// valid pointer is 0 to indicate the end of valid router-record pointers.

static router_record ** read_router_records(const string & rt_filename) {

  // Read the contents of the router-table file with the name rt_filename.
  // Return a pointer to an array containing pointers to the router-record
  // information read; the end of the list is marked with the 0 pointer.  It is
  // the caller's responsibilty to free the dynamic memory allocated for the
  // both the array and the records.

  ifstream ins(rt_filename.c_str());
  if (!ins) {
    cerr << "Can't open the routine-table file \"" << rt_filename << "\".\n";
    exit(EXIT_FAILURE);
    }

  const int records_increment = 100;
  int records_max = records_increment;
  router_record ** records = new router_record *[records_max];
  int record_cnt = 0;

  do {
    if (record_cnt >= records_max) {
      int new_records_max = records_max + records_increment;
      router_record ** new_records = new router_record *[new_records_max];

      memcpy(new_records, records, sizeof(router_record *)*record_cnt);

      delete [] records;
      records = new_records;
      records_max = new_records_max;
      }

    }
  while ((records[record_cnt++] = read_router_record(ins)) != 0);

  return records;
  }


// A router record has three parts: the segment name, the router name, and the
// routing table data.  Reading the first and third parts are trickey because
// both can have a variable size; segment names can have a varying number of
// words (as in "Washington D. C.") and routing tables can have a varying
// number of bytes.  Because we have to read the segment name before we can get
// to the routing table, let's worry about the segment name here and delay the
// problem of reading routing tables until later.
//
     static void read_router_table(ifstream &, char * &, int &);
//
// The key to reading segment names correctly is to recognize that a router
// name cannot be part of a segment name.  If you keep reading words until you
// read a router name, then all the words you read before must be part of the
// segment name.  This approach assumes we know how to tell when a word is a
// router name.
//
     static bool is_router_name(const string &);
//
// Once the segment and router names have been straightened out, we can
// complete the router record by reading the routing table.

static router_record * read_router_record(ifstream & ins) {

  // Read the next router record from the input stream ins; return a pointer to
  // the router record read.  It is the caller's responsibilty to free the
  // dynamic memory allocated for the record.

  router_record * rr_ptr = new router_record;

  ins >> rr_ptr->segment_name;
  if (!ins.good()) {
    delete rr_ptr;
    return 0;
    }

  while (true) {
    ins >> rr_ptr->router_name;
    if (!ins.good()) {
      cerr << "Error during router name read.\n";
      exit(EXIT_FAILURE);
      }
    if (is_router_name(rr_ptr->router_name))
      break;
    rr_ptr->segment_name += " " + rr_ptr->router_name;
    }

  read_router_table(ins, rr_ptr->router_table, rr_ptr->table_size);

  return rr_ptr;
  }


// A router name starts with an 'R' followed by one or more decimal digits.

static bool is_router_name(const string & word) {

  // Return true if and only if word contains a valid router name.

  if (word[0] != 'R') return false;
  for (int i = word.size() - 1; i > 0; i--)
    if (!isdigit(word[i])) return false;
  return true;
  }


// Reading router tables is complicated not only because the tabels have
// unknown and varying size, but also because each table is delimited by a
// different character pair.  Assuming for the moment we know how to deal with
// the delimiter characters
//
     static void read_delimiter_characters(ifstream &, char &, char &);
//
// we can deal with the variable size in the same way we did for reading
// records from the routing-table file: allocate an array of bytes and grow it
// as needed.  The need to check for two delimiters adds a bit of complication
// to this code, but not too much.

static void read_router_table(
  ifstream & ins, char * & router_table, int & table_size) {

  // Read router table data from the input stream ins.  After the call
  // router_table contains a pointer to the dynamic memory allocated to hold
  // the router table data and table_size contains the number of bytes of
  // router table data read.  It is the caller's responsibility to free the
  // memory allocated for the router-table data.

  char delim1, delim2;
  read_delimiter_characters(ins, delim1, delim2);

  const int table_increment = 100;
  int table_max = 100;
  router_table = new char[table_max];
  table_size = 0;

  while (true) {
    if (table_size + 1 >= table_max) {
      int new_table_max = table_max + table_increment;
      char * new_router_table = new char[new_table_max];

      memcpy(new_router_table, router_table, table_size);

      delete [] router_table;
      router_table = new_router_table;
      table_max = new_table_max;
      }
    
    router_table[table_size] = ins.get();
    if (ins.eof()) {
      cerr << "Error during routing-table data read.\n";
      exit(EXIT_FAILURE);
      }

    if (router_table[table_size] == delim1) {
      char c;
      c = ins.get();
      if (!ins.good()) {
	cerr << "Error during second delimiter character read.\n";
	exit(EXIT_FAILURE);
	}
      if (c == delim2)
	break;
      else
	router_table[++table_size] = c;
      }

    table_size++;
    }
  }


// The first two characters after the space characters following the router
// name are the delimiter characters.  Reading them is simple, complicated only
// by the need to check for I-O errors.

static void read_delimiter_characters(ifstream & ins, char & d1, char & d2) {

  // Read the routing-table delimiter characters from the input stream ins; d1
  // contains the first character and d2 contains the second character.

  do {
    d1 = ins.get();
    if (!ins.good()) {
      cerr << "Error during first delimiter character read.\n";
      exit(EXIT_FAILURE);
      }
    }
  while ((' ' == d1) || ('\n' == d1));

  d2 = ins.get();
  if (!ins.good()) {
    cerr << "Error during second delimiter character read.\n";
    exit(EXIT_FAILURE);
    }
  }


// Once the routing-table records have been read in, they are sorted in
// preparation for writing the individual network-segment files.  The sort is a
// simple selection sort, and uses the operator >() defined for router records.

static void sort_router_records(router_record * router_record_ptrs[]) {

  // Sort the router records given in router_record_ptrs.  After the sort the
  // records in ascending order by network name; within each network segment
  // the records in ascending order by router name.

  for (int top = 0; router_record_ptrs[top] != 0; top++) {
    int smallest = top;
    for (int current = smallest + 1; router_record_ptrs[current] != 0; current++)
      if (*router_record_ptrs[smallest] > *router_record_ptrs[current])
	smallest = current;
    router_record * rrp = router_record_ptrs[smallest];
    router_record_ptrs[smallest] = router_record_ptrs[top];
    router_record_ptrs[top] = rrp;
    }
  }


// Given a sorted list of router records, each block of records with the same
// segment name serves as the basis for creating the network-segment files.
//
     static void write_segment_file(router_record **, int, int);


static void write_segment_files(router_record * router_record_ptrs[]) {

  // Create the network-segment files from the list of router records given in
  // router_record_ptrs; the records are assumed to be sorted by network
  // segments.

  int start = 0;

  while (router_record_ptrs[start] != 0) {
    int end = start + 1;
    while ((router_record_ptrs[end] != 0) && 
	   (router_record_ptrs[start]->segment_name == router_record_ptrs[end]->segment_name))
      end++;
    write_segment_file(router_record_ptrs, start, end);
    start = end;
    }
  }


// Assuming we know how to construct a file name from a network segment name,
//
     static string make_file_name(const string &);
//
// creating the network-segment file involves writing out the individual
// records associated with the segment name.

static void write_segment_file(
  router_record * router_record_ptrs[], int start, int end) {

  // Create a network-segment file and write the records in the block
  // router_record_ptrs[start..end-1] to the file.  All records in the block
  // are assumed to contain the same segment record, and are assumed to be the
  // only records with that segment name.

  const string rt_filename = make_file_name(router_record_ptrs[start]->segment_name);
  ofstream outs(rt_filename.c_str());
  if (!outs) {
    cerr << "Can't open the router-segment file \"" << rt_filename << "\".\n";
    return;
    }

  while (start < end) {
    const router_record * const rrp = router_record_ptrs[start++];
    outs << rrp->router_name << " " << rrp->table_size << " ";
    outs.write(rrp->router_table, rrp->table_size);
    }

  outs.close();
  }


// Turning a segment name into a file name involves converting the segment name
// into lower case, replacing all spaces with hyphens, and adding ".rt".

static string make_file_name(const string & segment_name) {

  // Return a string containing segment_name as a network-segment file name.

  string fn = segment_name;

  for (int i = fn.size() - 1; i >= 0; i--)
    if (' ' == fn[i])
      fn[i] = '-';
    else if (isupper(fn[i]))
      fn[i] = tolower(fn[i]);

  return fn + ".rt";
  }