//  File Name:  user.cpp

//  Generate random numbers and store them in a linked list
//  Use CC compiler 

#include <iostream.h>    // because CC does not have <iostream>
#include "ListNode.h"
#include "List.h"
#include "ListItr.h"

extern "C" int rand( );  // Stroustrup, 2nd Edition, page 159
                         // The C++ Programming Language
                         // "Not too random: beware"

//  returns a random integer in the range 1 .. u
int randint (int u )
{
   int r = rand( );
   if (r < 0) r = -r;
   return 1 + ( r % u );
}

int main ( )
{
   List<int> L;
   ListItr<int> itr = L.zeroth( );

   int highest;        // random numbers will be in range 1..highest
   // Ask the user for an upper bound on the size of numbers to be sorted.
   cout << endl << "What is the maximum integer value expected? ";
   cin >> highest;
   while ( highest < 2 )
   {
      cout << "The highest value must be greater than 1." << endl;
      cout << "Please enter the maximum integer value expected. ";
      cin >> highest;
   }
 
   int n;       // the number of integers to be sorted. 
   // Ask the user for the number of integers to be sorted.
   cout << "How many integers do you want to sort? ";
   cin >> n;
   while ( n < 0 )
   {
      cout << "It is not possible to sort fewer than zero integers." << endl;
      cout << "Please enter the number of integers to be sorted. ";
      cin >> n;
   }
   cout << endl << "You want to sort " << n << " integers " ;
   cout << "in the range 1.." << highest << "." << endl << endl;
   
   // Fill list L with n integers in the range 1..highest
   for (int count = 0 ; count < n ; count++ )
   {
      L.insert ( randint(highest), itr);
   }

   cout << "The initial list is: " << endl;
   printList ( L );

   // Calculate the length of the longest integer
   // Code to calculate k, the maximum number of digits, goes here

   // Write your pseudocode algorithm for radix sort here

   // Implement your radix sort here

   // Demonstrate that your radix sort worked.
   cout << endl << "The sorted list is: " << endl;
   printList ( L );
   cout << endl;

   // Demonstrate of the += operator to append a list
   cout << endl << "The new list is: " << endl;
   L += L;
   printList ( L );
   cout << endl;
}