// Program to print numbers between 1 and N as Roman numerals
// in alphabetical order
// File:    roman-num.cc
// Author:  Henry M. Walker
// Date:    May 29, 1998

// Basic Roman numerals:
//              1   I         5   V         10   X    
//             50   L       100   C        500   D
//           1000   M      5000   Y      10000   Z        

#include "apstring.cpp"

const num_width = 19; // width of field to print Roman numerals

struct num_pair {
   apstring numeral;
   int number;
   };

void generate_numeral (int i, apstring & numeral);
// procedure to determine numeral string for given integer

void sort (int N, num_pair pair_array[]);
// procedure to sort (numeral, number) pairs by numeral

void print (int N, num_pair pair_array[]);
// procedure to print (numeral, number) pairs in columns

int main (void) {
  //  procedure reads number N, generates integers between 1 and N,
  //  alphabetizes those integers, and prints the result.

  int N;  // number of numerals to be generated and sorted
  int i;  // index variable

  cout << "Program to print numbers between 1 and N " << endl;
  cout << "as Roman numerals in alphabetical order" << endl;

  // enter number N
  cout << "Enter an integer N between 1 and 39,999:  ";
  do 
    {
      cin  >> N;
      if (N <= 0 || N >= 40000)
         cout << "integer must be between 1 and 39,999; try again:  ";
    }
  while (N <= 0 || N >= 40000);

  // generate (numeral, number) pairs in range
  num_pair pair_array[N+1];

  for (i=1; i<= N; i++) {
     generate_numeral (i, pair_array[i].numeral);
     pair_array[i].number = i;
  }

  // sort (numeral, number) pairs
  sort (N, pair_array);

  // print numbers in columns
  print (N, pair_array);

  return 0;
}

apstring gen_digit_str (int d, apstring units, 
                               apstring fives, apstring tens) {
  switch (d) {
      case 0: return ("");
      case 1: return (units);
      case 2: return (units+units);
      case 3: return (units+units+units);
      case 4: return (units+fives);
      case 5: return (fives);
      case 6: return (fives+units);
      case 7: return (fives+units+units);
      case 8: return (fives+units+units+units);
      case 9: return (units+tens);
     default: cout << "error: parameter to gen_digit_str out of range"
                   << endl;
  }
}

void generate_numeral (int i, apstring & numeral) {
// procedure to determine numeral string for given integer
  // approach:
  //     consider string for each digit individually
  //     combine strings to get entire numeral;
  apstring unit_str = gen_digit_str(        i % 10, "I", "V", "X");
  apstring tens_str = gen_digit_str(   (i/10) % 10, "X", "L", "C");
  apstring hund_str = gen_digit_str(  (i/100) % 10, "C", "D", "M");
  apstring thou_str = gen_digit_str( (i/1000) % 10, "M", "Y", "Z");
  apstring tthou_str= gen_digit_str((i/10000) % 10, "Z", "?", "?");

  numeral = tthou_str + thou_str + hund_str + tens_str + unit_str;
}

void print (int N, num_pair pair_array[]) {
// procedure to print (numeral, number) pairs in columns
  int i;  

  cout << "The Roman numerals in alphabetical order are:" << endl;

  // create string of blanks of width num_width;
  apstring blanks;
  for (i=1; i<num_width; i++) {
     blanks += ' ';
  }

  cout.setf(ios::fixed);
  for (i=1; i<= N; i++) {
    // print initial blanks
    int num_blanks = num_width - pair_array[i].numeral.length();
    cout << blanks.substr(0, num_blanks);

    // print (numeral, number) pair
    cout << pair_array[i].numeral;
    cout.width (7);
    cout << pair_array[i].number;

    // add spacing
    if (i % 3 == 0)
      cout << endl;
  }
  cout << endl;
}

void sort (int N, num_pair pair_array[]) {
// procedure to sort (numeral, number) pairs by numeral
// this version uses an insertion sort
   int i, j;

   num_pair current, temp;

   for (i=2; i<= N; i++) {
      current.numeral = pair_array[i].numeral;
      current.number  = pair_array[i].number;
      
      j = i-1;
      while (j>=1 && pair_array[j].numeral >  current.numeral) {
         pair_array[j+1].numeral = pair_array[j].numeral;
         pair_array[j+1].number  = pair_array[j].number;
         j--;
      }

     pair_array[j+1].numeral = current.numeral;
     pair_array[j+1].number  = current.number;
   }
}