/*******************************************************************************
* Purpose of this program:  Program to simulate stations ordering based on Mok
* and Wards binary countdown
* protocol.  The program only iterates once so there is no dynamic host
* numbering involved.  The protocol accepts up to 20 station numbers as 3 digit
* intergers. No decimals please.
********************************************************************************
* Functions:
*  	 order:  the heart of the protocol,  performs the ordering.
*
*		 get_stations:  gets the station numbers.  This is a function so that
*      					different methods can be easily interchanged.
*
*		 resize: Resize the taable to throw out any unwanted values, namely
*              those values who do not have the current bit set.
*              Please note that this function will only return if the bithigh
*              value is false,  meaning tat noone has this bit set
*
*		 check: Checks the bit in question and sets bit high to true or false.
*      		 By checks the bit in question meaning does anyone use this bit.
*
*		 error: If there is an invalid input..eg. a station number that is
*             four digits or negative,  other than -1 which is used for
*             controlling the input.
*
*		 main:  is the main body of the program which calls the above functions.
********************************************************************************
*By:  Chuck Hall,  for Dr. K.Kowalski,  CSC451,  Computer networks
*10-97 last update
*******************************************************************************/
//c++ source file.

#include<iostream.h>           //include the standard io package.
#include<stdlib.h>             //We need this for exit();

#define true        1
#define false       0
#define quit        -1
#define firstbit    0x200      //the convention here is firstbit = msb
#define secondbit   0x100      //tenthbit = lsb
#define thirdbit    0x80
#define fourthbit   0x40
#define fifthbit    0x20      //define masks for each bit in the 3 digit number
#define sixthbit    0x10      //a 3 digit int has 10 binary digits.
#define seventhbit  0x8
#define eigthbit    0x4
#define ninthbit    0x2
#define tenthbit    0x1
int count=1;                   //Ok 1 global to maintain the Global count.
int MasterList[20];

typedef int* station_list;    //define types for the station list
typedef short flag;           //and the high bit flag...the bit is set

void get_stations(int &size, station_list &list);
void order(int &size, station_list &list);
void error(){cout<<"\n\nERROR: Values must be between 0 and 999\n\n";}
flag check(station_list templist, int size, int bitnum);
void resize(station_list &templist,int &size, int bitnum, flag bithigh);
void output(int MList[]);

int main()
{
   int size=0;
   station_list slist;


	cout << "\n\nThis program performs stations ordering based on"
        << "\nMok and Wards Binary Countdown Protocol."<<endl
        << "This is a simulation of a Datalink layer network protocol\n\n";

   //read the station numbers from input
   get_stations(size, slist);  //post: size = size counting from 1 not from 0

   if(size==0){cout<<"\n\n No stations\n";}
   else if(size==1){cout<<"The only station:"<<slist[size-1]<<endl;}
   else {cout<<endl<<endl<<"The long order is: "<<endl;order(size, slist);}

   output(MasterList);
   cout << "\n\nThank you for using the Mok and Ward Simulator"<<endl;
	return 0;
}

//read the station numbers from stdin
void get_stations(int &size, station_list &list)
{
  	cout<<"\n\nInput a station number as a 3 digit integer or enter -1 to quit.\n"
     	 <<"You can enter up to 20 numbers.\n";
  	int temp[20];                  //create a temp array to hold input
   int ioBuff=0, i;                   //create a buffer and a counter
   size = 0;                      //make sure size is 0,  this is a new list

   while(size < 20)
   {
       cin >> ioBuff;
       if(ioBuff==-1){break;}        //read into the buffer
       if((ioBuff <-1)||(ioBuff > 999)){error();exit(1);}
   	 temp[size] = ioBuff;
       size++;
   }
   if(size==0){return;}
   list = new int[size];
   for(i=0;i<=size;i++)
   {
   	list[i] = temp [i];
   }
}

void order(int &size, station_list &list)
{
	int i;
   flag bithigh=false;
   station_list templist;
   int tempsize, temp;

   if(size == 0){return;}
   else if(size == 1)
   {
   	cout<<count << ":  "<< list[size-1] <<endl;
      //cout<<"The station number is: " << list[size-1]<<endl;
      MasterList[count] = list[size-1];
      count++;
      return;
   }

   else
   {
      //make a scratch copy of the table and size
      tempsize = size;
      templist = new int[size];
      for(i=0;i<tempsize;i++)
   	{
   		templist[i] = list[i];
   	}

   	//check the first bit
      bithigh = check(templist, tempsize, firstbit);
   	//if there is some station with the first bit high,
      //remove first bit low stations
		resize(templist,tempsize,firstbit,bithigh);

      //check the second bit
      bithigh = check(templist, tempsize, secondbit);
      resize(templist,tempsize,secondbit,bithigh);

      //check the third bit
      bithigh = check(templist,tempsize,thirdbit);
      resize(templist,tempsize,thirdbit,bithigh);

      //check the fourth bit
      bithigh = check(templist,tempsize,fourthbit);
      resize(templist,tempsize,fourthbit,bithigh);

      //check the fifth bit
      bithigh = check(templist,tempsize,fifthbit);
      resize(templist,tempsize,fifthbit,bithigh);

      //check the sixth bit
      bithigh = check(templist,tempsize,sixthbit);
      resize(templist,tempsize,sixthbit,bithigh);

      //check the seventh bit
      bithigh = check(templist,tempsize,seventhbit);
      resize(templist,tempsize,seventhbit,bithigh);

      //check the eigth bit
      bithigh = check(templist,tempsize,eigthbit);
      resize(templist,tempsize,eigthbit,bithigh);

      //check the ninth bit
      bithigh = check(templist,tempsize,ninthbit);
      resize(templist,tempsize,ninthbit,bithigh);

      //check the last bit,  the lsb
      bithigh = check(templist,tempsize,tenthbit);
      resize(templist,tempsize,tenthbit,bithigh);


      //Now clean up
      cout<< count<< ":  "<<templist[0] << endl;
      //cout<<"The Station number is: "<<templist[0]<<endl;
      MasterList[count] = templist[0];
      count++;
      temp = templist[0];
      delete[] templist;

      //now find the list element from templist in list and remove it
      for(i=0;i<size;i++)
      {
      	if(temp == list[i]){list[i] = -1;}
      }
      templist = new int[size-1];
      int j=0;
      for(i=0;i<size;i++)
      {
      	if(list[i] != -1)
         {
         	templist[j] = list[i];
            j++;
         }
      }//end for
      delete[] list;
      size--;
      list = new int[size];
      for(i=0;i<size;i++)
      {
      	list[i] = templist[i];
      }
      delete[] templist;
      order(size,list);
   } //end else case
} //end order function


//the function that checks the bits
flag check(station_list templist, int size, int bitnum)
{
	int i=0, temp;
   flag bithigh = false;
   for(i=0;((bithigh==false) && (i<size));i++)
   {
   	temp = (templist[i] & bitnum);
      if(temp == bitnum){bithigh = true;}
   }
   return bithigh;
} //end check

//resize the table
void resize(station_list &templist,int &size, int bitnum, flag bithigh)
{
   int newsize = size, i=0, j=0;
   station_list templist2;

	if(bithigh == false){return;}

   //or else mark the values to be removed from the table with a -1
   for(i=0;i<size;i++)
   {
   	if((templist[i] & bitnum) != bitnum){templist[i]=-1; newsize--;}
   }

   //resize the list
  	templist2= new int[newsize];
  	for(i=0;i<size;i++)
   {
   	if(templist[i]==-1){}//do nothing
      else{templist2[j] = templist[i];j++;}
   }
   //clean up and reset the size and the new templist
   size = newsize;
   delete[] templist;
   templist = new int[newsize];
   //copy the scratch templist to the templist
   for(i=0;i<newsize;i++)
   {
   	templist[i] = templist2[i];
   }
   delete[] templist2;
} //end resize

void output(int MList[])
{
   int i=0;
   cout<<endl<<endl<<"In short the order is: "<<endl;
	for(i=1;i<(count);i++)
   {
   	cout<< MList[i]<<" ";
   }
} //end output