/******************************************************

** Name: 

** Filename: Radix.cpp

** Project #: 

** Project Description: This program will read an input 
   file called radixdata.txt, which contains a list of 
   numbers that are six digits long. The computer will 
   use this input and perform a radix sort of the numbers 
   using the queue class. The results of the sort will then 
   be printed to the screen.

** Output:All the numbers inputed from the radixdata.txt 
   printed to the screen in numerical order.

** Input: A group of numbers six digits in length in a 
   file called radixdata.txt.

** Algorithm: Instruct user on program purpose.
              Read data in from file radixdata.txt
	      Use while loop
	      Insert data in Q holder 
	      Transfer holder to tempholder
	      Print out tempholder
              Perform RadixSort using sorter[]
	      Use a for loop to read through each digit 
	      starting with the last
	      Use a for loop to read all entries in sorter 
	      place number from holder into associated sorter 
	      Use a for loop to read through all the sorter
	      Transfer data from the sorter to the holder
              Print the sorted contents of Q holder
	      End

******************************************************/
// Include files
#include <iostream>    // used for cin, cout
#include <conio.h>
#include <fstream>     // file input/output
#include <queue>       // class for queue's
#include <string>      // used for string's
using namespace std;

// Global Type Declarations
typedef queue<string> Q;

// Function Prototypes
void instruct(void);
void pause ();

int main()
{	
    // Declaration section
    Q holder, tempholder, sorter[10];
    const int  Digits = 6;            // Number of digits per item
    char numInput[Digits];            // Stores data input
    int bin;                          // Stores digits of queue
    int run1;                         // Records runs for print
    int run2;                         // Records runs for print

    // Executable section
	instruct ();

	cout << "Inserting Data In The Queue\n" ;
	cout << "----------------------------\n" << endl;

    ifstream inDataFile( "radixdata.txt", ios::in); //Open Data File
     if ( !inDataFile )
	{
	cerr << "File could not be opened\n";
	exit(1);
	}
		
	inDataFile >> numInput;	          //Read In Data
	while ( !inDataFile.eof())        //Stop When End Of File Reached
	      {
	      holder.push(numInput);      //Put Data In Queue
              inDataFile >> numInput;     //Read In Next Line Of Data
	      }

		run1 = 0;
		tempholder = holder;                 //Copy holder queue to tempholder
		cout << "Data In The Queue\n\n";
        while (!tempholder.empty())
	      {					     //Print Out Unsorted Queue
	      cout << tempholder.front() << " ";
	      tempholder.pop();
              run1++;

		if ( run1 % 10 == 0 )
		    cout <<endl;
	      }

		cout << "\n\nBeginning Sort Of The Queue" << endl;
		cout << "----------------------------" << endl;
		pause();

    for ( int i = Digits - 1; i > - 1; i-- ) //Begin Sort Of Queue Using Sorter
	{
        while (!holder.empty())
	      {
	      bin = (static_cast<int>(holder.front().at(i))) - 48;
	      sorter[bin].push(holder.front());
              holder.pop();
	      }
    for ( int j = 0; j <= 9; j++ )
	{
	while (!sorter[j].empty())           //Run Through Sorter
	      {
	       holder.push(sorter[j].front());//Push Front Digit From Holder
               sorter[j].pop();}              //Pop Out From Sorter   
	      }
	}
      
	       run2 = 0;
	       cout << "Data In The Sorted Queue\n\n";              
	       while (!holder.empty())
		     {			         //Print Out Sorted Queue
		      cout << holder.front() << " ";
		      holder.pop();
                      run2++;

		if ( run2 % 10 == 0 )
			cout <<endl;
		     }

    pause();
    return 0;
}
void instruct (void)
{
	  // Declaration section

	  // Executable section
        cout << "\t************************************************************"<< endl;
	cout << "\t* This program will read an input file named radixdata.txt,*"<< endl;
	cout << "\t* which contains a list of numbers that are six digits in  *"<< endl;
	cout << "\t* length.The computer will use this input and perform a    *"<< endl;
	cout << "\t* radix sort of the numbers using the queue class. The     *"<< endl;
	cout << "\t* results of the sort will then be printed to the screen.  *"<< endl;                                 
	cout << "\t************************************************************"<< endl;
	cout << endl;
}
void pause ()
{
    // Declaration section

    // Executable section
    cout << "\nPress any key to continue...";
    getch();
    cout << "\r";
    cout << "                            ";
    cout << "\r";
}
/*
Program Output

        ************************************************************
        * This program will read an input file named radixdata.txt,*
        * which contains a list of numbers that are six digits in  *
        * length.The computer will use this input and perform a    *
        * radix sort of the numbers using the queue class. The     *
        * results of the sort will then be printed to the screen.  *
        ************************************************************

Inserting Data In The Queue
----------------------------

Data In The Queue

524434 550815 753752 792685 147534 128082 089576 918716 857534 979838
112728 297738 252382 817961 302914 082100 490576 073770 680599 249408
591516 365341 140206 131551 135475 666445 196530 272975 022277 976330
471886 456729 604095 837608 085480 673448 911551 233465 979732 792991
871438 259400 662418 542230 221271 214864 286552 300714 373719 319058


Beginning Sort Of The Queue
----------------------------

Press any key to continue...

Data In The Sorted Queue

022277 073770 082100 085480 089576 112728 128082 131551 135475 140206
147534 196530 214864 221271 233465 249408 252382 259400 272975 286552
297738 300714 302914 319058 365341 373719 456729 471886 490576 524434
542230 550815 591516 604095 662418 666445 673448 680599 753752 792685
792991 817961 837608 857534 871438 911551 918716 976330 979732 979838

Press any key to continue...
*/