/***************************************************************************
                          main.cpp  -  description
                             -------------------
    begin                : Fri Oct 24 2002
    copyright            : (C) 2002 by Atanas Dimitrov
    email                : adimitro@localhost.localdomain
    build                : i686, 1.7Ghz, 256MB
    X                    : KDE 3.0.3, Xinerama: nVidia GeForce 2 MX, nVidia GeForce 4 MX420
 ***************************************************************************/
#include <stdlib.h>
#include <iostream.h>
#include <unistd.h> //To get SLEEP(3) (Linux Programmer's Manual)
#include <time.h>
#include <string.h>

//There are a few functions that are more or less unnecessary
//like the clear, full, etc. and they could be replaced or erased
//but none the less they were necessary
//for the proper implementation of the heap class and testing purposes. I
//thought I worked too hard to just wipe them off. :-)
//Also it's a bit hard to read but... had to be in a hurry to get some extra credit
//                                :-)

const int defMaxHeapSize = 20;    // Default maximum heap size

const int MAX_PROC_QUEUE=3; //Max number in processor
const int MAX_READY_QUEUE=5;  //Max number in ready queue

const int TRUE=1;  //True constant for processor and ready queue
const int FALSE=0;  //False constant for processor and ready queue
int process_identifier=0;  //Process id number variable for generating new processes into the heap


// ================================ Priority Queue Class implementation ==================
template < class HEAP >
class Heap
{
  public:

    // Constructor
    Heap ( int maxNumber = defMaxHeapSize );

    // Destructor
    ~Heap ();

    //manipulation operations
    void insert ( const HEAP &newElement );
    HEAP removeMax ();
    void clear ();

    //status operations
    int empty () const;
    int full () const;

    // Output heap
    void showStructure () const;

  private:
    int maxSize,   // max
        size;      // actual number
    HEAP *element;   // array to hold
};

//constructor
template<class HEAP>
Heap<HEAP>::Heap( int maxNumber)
{
  maxSize = maxNumber;
  size = 0;
  element = new HEAP [maxSize];
}

//destructor
template <class HEAP>
Heap<HEAP>::~Heap()
{
  clear();size = 0;
}

//insert
template<class HEAP>
void Heap<HEAP>:: insert(const HEAP & newElement)
{
  int currpos = size;
  int parentpos = (size -1)/2;
  int isPosition = 0;

  //I was trying to implement the class before I thought whether I would need this
  if ( full() )
    {cerr << "Trying to insert to a full heap. " << endl;exit(1);}

  // Inserts newElement into the heap;
  element[size] = newElement;
  size ++;

  // if newElement has higher priority, move it upward.
  while ( currpos > 0 && !isPosition)
    {
      if ( element[currpos].pty() >= element[parentpos].pty() )
	      isPosition = 1;
      else
	    {
	       element[currpos] = element[parentpos];
	       element[parentpos] = newElement;
	       currpos = parentpos;
	       parentpos = ( currpos -1 )/2 ;
      }
    }
}


//removeMax removes the element with maximum priority
template<class HEAP>
HEAP Heap<HEAP>::removeMax()
{
  HEAP delItem, temp;
  int currpos, lpos, rpos, isPosition = 0;

  if ( empty() )
    {
      cerr << "Trying to remove from an empty heap. " << endl;
      exit(1);
    }

  // remove highes pri
  delItem = element[0];
  size --;

  // Replace with the bottom right-most element
  element[0] = element[size];
  temp = element[0];

  // set the current position and left and right child positions.
  currpos = 0;
  lpos = 2*currpos + 1;
  rpos = 2*currpos + 2;

  // movedown and restore properties
  while (  size > currpos+1 && !isPosition  )
    {
      //Pretty much compare parent with lft & right and then left and right
      //So it would know what to do
      temp = element[currpos];
      if ( rpos < size )
      {
        if ( element[currpos].pty() > element[lpos].pty() || element[currpos].pty() > element[rpos].pty() )
 	      {
	        if ( element[lpos].pty() < element[rpos].pty() )
	        {
	          element[currpos] = element[lpos];
	          element[lpos] = temp;
	          currpos = lpos;
          }
	        else
	        {
	          element[currpos] = element[rpos];
	          element[rpos] = temp;
	          currpos = rpos;
          }
	      }
      }
      else if ( lpos < size && element[lpos].pty() < element[currpos].pty() )
      {
	      element[currpos] = element[lpos];
	      element[lpos] = temp;
	      currpos = lpos;
      }

      temp = element[currpos];
      lpos = 2*currpos +1;
      rpos = 2*currpos +2;
      if ( ( element[currpos].pty() <= element[lpos].pty() && element[currpos].pty() <= element[rpos].pty() ) || lpos >= size )
          isPosition = 1;
   }
  return delItem;
}

//clear
template<class HEAP>
void Heap<HEAP>:: clear()
{
  delete element;
  size = 0;
}

//empty
template<class HEAP>
int Heap<HEAP>:: empty() const
{
  return size==0;
}

//full
template<class HEAP>
int Heap<HEAP>::full() const
{
  return size == maxSize;
}

//showStructure
template < class HEAP >
void Heap<HEAP>:: showStructure () const
{
    int j;
    if ( size == 0 )
       cout << "Empty heap" << endl;
    else
    {
       cout << "\nThe numbers in the  priority queue are:" << endl;
       for ( j = 0 ; j < size ; j++ )
          cout << element[j].rid() << element[j].ridnum() << ":" << element[j].pty() << ", ";
       cout << endl;
    }
}


//================================================================================
//                          DATA CLASS FOR THE HEAP

class TestData
{
  public:

    void setPty ( int newPty )
        { priority = newPty; }   // set
    int pty () const
        { return priority; }     // return
    void setId (char *newId)
        { strcpy(id, newId); }
    char rid()
        { return *id; }
    void setIdnum ( int newIdnum )
        { idnum = newIdnum; }
    int ridnum() const
        { return idnum; }

  private:
    int priority;
    char id[5];
    int idnum;
};



//===========================================================================
//                                USED FOR THE QUEUE TYPE
struct Proc {

  int prior;
  char id;
  int idnum;
};


//===========================================================================
//                                READY QUEUE CLASS

class ReadyQueue
{
  public:
    ReadyQueue(void);
    void enqueue(Proc);
    Proc serve(void);
    int isempty(void);
    int isfull(void);
    void display(void);

  private:
    int queue_in;
    Proc ready_queue[5];
};

//Constructor
ReadyQueue::ReadyQueue()
{
  queue_in=-1;
}

//ENQUEUE
void ReadyQueue::enqueue(Proc ins_entr)
{
  queue_in++;

  ready_queue[queue_in].prior = ins_entr.prior;
  ready_queue[queue_in].id = ins_entr.id;
  ready_queue[queue_in].idnum = ins_entr.idnum;
  return;
}


//SERVE
Proc ReadyQueue::serve(void)
{
  Proc ret_entr;

  ret_entr.prior = ready_queue[0].prior;
  ret_entr.id = ready_queue[0].id;
  ret_entr.idnum = ready_queue[0].idnum;

  for (int i=0; i < queue_in; i++)
  {
    ready_queue[i].prior = ready_queue[i+1].prior;
    ready_queue[i].id = ready_queue[i+1].id;
    ready_queue[i].idnum = ready_queue[i+1].idnum;
  }
  queue_in--;

  return ret_entr;
}

//CHECK IF EMPTY
int ReadyQueue::isempty(void)
{
  if (queue_in == -1)
    return TRUE;
  else
    return FALSE;
}

//CHECK IF FULL
int ReadyQueue::isfull(void)
{
  if (queue_in == MAX_READY_QUEUE - 1)
    return TRUE;
  else
    return FALSE;
}

//DISPLAY QUEUE
void ReadyQueue::display(void)
{
  cout << "The processes in the ready queue are: ";
  for (int i=0; i<=queue_in; i++)
  {
    cout  << ready_queue[i].id << ready_queue[i].idnum << ":"<<ready_queue[i].prior <<", ";
  }
  cout << "\n";
}


//===========================================================================
//                                THE PROCESSOR QUEUE CLASS
class ProcQueue
{
  public:
    ProcQueue(void);
    void enqueue(Proc);
    Proc serve(void);
    int isempty(void);
    int isfull(void);
    void display(void);

  private:
    int queue_in;
    Proc proc_queue[MAX_PROC_QUEUE];
};


//CONSTRUCTOR
ProcQueue::ProcQueue()
{
  queue_in=-1;
}

//ENQUEUE
void ProcQueue::enqueue(Proc ins_entr)
{
  queue_in++;

  proc_queue[queue_in].prior = ins_entr.prior;
  proc_queue[queue_in].id = ins_entr.id;
  proc_queue[queue_in].idnum = ins_entr.idnum;

  return;
}

//DEQUEUE
Proc ProcQueue::serve(void)
{
  Proc ret_entr;

  ret_entr.prior = proc_queue[0].prior;
  ret_entr.id = proc_queue[0].id;
  ret_entr.idnum = proc_queue[0].idnum;

  for (int i=0; i < queue_in; i++)
  {
    proc_queue[i].prior = proc_queue[i+1].prior;
    proc_queue[i].id = proc_queue[i+1].id;
    proc_queue[i].idnum = proc_queue[i+1].idnum;
  }
  queue_in--;

  return ret_entr;
}

//CHECK IF EMPTY
int ProcQueue::isempty(void)
{
  if (queue_in == -1)
    return TRUE;
  else
    return FALSE;
}

//CHECK IF FULL
int ProcQueue::isfull(void)
{
  if (queue_in == MAX_PROC_QUEUE - 1)
    return TRUE;
  else
    return FALSE;
}

//DISPLAY QUEUE
void ProcQueue::display(void)
{
  cout << "The processes in the processor are: ";
  for (int i=0; i<=queue_in; i++)
  {
    cout  << proc_queue[i].id << proc_queue[i].idnum << ":"<<proc_queue[i].prior <<", ";
  }
  cout << "\n";
}


//FUNCTION TO GENERATE NEW PROCESSES INTO THE HEAP (PRIORITY QUEUE)
TestData generate()
{
       int iP;      //HOLDS THE PRIORITY
       TestData tE;  //ELEMENT TO BE INSERTED
       char temp[4];  //DOESN'T NEED TO BE 4... BUT THIS WILL HOLD THE "P" PART OF THE PROCESS ID

       //GENERATE THE NEW PRIORITY
       iP=1+rand()%10;
       tE.setPty(iP);

       //SET THE PART AFTER "P" OF THE PROCESS ID
       tE.setIdnum(process_identifier);
       process_identifier++;

       //SET THE "P"
       strcpy(temp, "P\0");
       tE.setId(temp);

      cout << "The new generated process is " << tE.rid() << tE.ridnum() << " with priority " << tE.pty() << "\n";
  return tE;
}


//================== MAIN FUNCTION ==============================

int main()
{
    Heap<TestData> testHeap(20);   // Test heap
    TestData testElement;         // Heap element
    int counter=0;                //COUNTER FOR THE TOTAL PROCESSED PROCESSES
    ReadyQueue ready_queue;       //READY QUEUE INITIALIZATION
    ProcQueue  proc_queue;        //PROCESSOR QUEUE INITIALIZATION
    Proc temp_proc, temp_proc1;    // VARIABLES FOR TEMPORARY STORAGE


    //INTRO
    cout << endl;
    cout << "Program to demonstrate long-term queue, ready queue, and processor of an operating system based on"
         << endl << "priorities and time to run in the processor." <<endl;
    cout << "By A. Dimitrov." << endl;
    cout << "Developed with KDevelop 3.0.3-0.7/Redhat Linux 7.3/latest dev packages" <<endl;
    cout << "Control-C works." << endl;
    cout << "Tested under Linux ONLY! Windows WILL DEFINATELY cry out loud! He-he-he!\nGood luck compiling! :-)" << endl << endl;
    sleep(6);

    srand(time( NULL ));

    //FILL UP THE HEAP
    //WILL DISPLAY THEM AS THEY COME FOR TESTING PURPOSES
    while (!testHeap.full())
    {  testHeap.insert(generate()); }

    //DISPLAY THE INITIAL MEMBERS OF ALL
    testHeap.showStructure();
    ready_queue.display();
    proc_queue.display();
    cout << endl;

    //FILL UP THE READY QUEUE
    while ( ready_queue.isfull() != 1)
    {
       //GET ONE OUT FROM HEAP
       testElement = testHeap.removeMax();
       cout << "\n";
       //PUT ONE NEW IN HEAP
       testHeap.insert(generate());

       //DISPLAY WHICH ONE CAME FROM HEAP TO READY
       cout << "Current dispatched number into Ready Queue is: "
              << testElement.rid() << testElement.ridnum()<<":" << testElement.pty()<<".\n";

       //CONVERT FROM TestData TO Proc
       temp_proc.prior = testElement.pty();
       temp_proc.id = testElement.rid();
       temp_proc.idnum = testElement.ridnum();

       //STORE IN READY
       ready_queue.enqueue(temp_proc);

       //NO PROCESS GOES TO PROCESSOR
       cout << "The new entered process in the processor is: NONE.";
       cout <<"\n--------------------------------------------------------------------------";
       //DISPLAY WHAT'S IN ALL
       testHeap.showStructure();
       ready_queue.display();
       proc_queue.display();
    }

    //FILL UP THE PROCESSOR
    while (proc_queue.isfull() !=1 )   //UNTILL NOT FULL
    {
       //GET ONE FROM READY
       proc_queue.enqueue(ready_queue.serve());

        //RESTORE READY TO A FULL STATE AS DESCRIBED ABOVE
        while ( ready_queue.isfull() != 1)
        {
          testElement = testHeap.removeMax();

          cout << "\n";
          testHeap.insert(generate());

          cout << "Current dispatched number into Ready Queue is: "
                    << testElement.rid() << testElement.ridnum()<<":" << testElement.pty()<<".\n";
          temp_proc.prior = testElement.pty();
          temp_proc.id= testElement.rid();
          temp_proc.idnum = testElement.ridnum();

          ready_queue.enqueue(temp_proc);
          cout << "The new entered process in the processor is: NONE";
          cout <<"\n--------------------------------------------------------------------------";
          testHeap.showStructure();
          ready_queue.display();
          proc_queue.display();
        }
    }


    //PROCESS 30 PROCESSES IN THE PROCESSOR COMPLETELY
    while (counter < 30 )
    {
        //GET ONE FROM PROCESSOR
        temp_proc1 = proc_queue.serve();

        //CHECK IF IT NEEDS TO BE PROCESSED AGAIN
        if (temp_proc1.prior > 1)
        {
          //YES

          //DECREASE TIME
          temp_proc1.prior--;

          //GET ONE FROM READY
          temp_proc=ready_queue.serve();

          //STORE IT IN PROCESSOR
          proc_queue.enqueue(temp_proc);

          //PUT THE OLD ONE IN READY
          ready_queue.enqueue(temp_proc1);

          //VALID MESSAGES FOR THIS CASE SINCE NOTHING CAME FROM OR WENT TO THE HEAP
          //AND NOTHING CAME TO READY FROM HEAP SO I SPECIFIED AS FOLLOWS
          cout << "\nThere are no new processes entering the priority queue!\n";
          cout << "There are no processes dispatched from heap into the ready queue!\n";
          cout << "The current dispatched process into the ready queue from the processor is "
                << temp_proc1.id << temp_proc1.idnum << " with priority " << temp_proc1.prior << "\n";
          cout << "The new entered process in the processor is " <<temp_proc.id
                <<temp_proc.idnum << ":"<<temp_proc.prior << ".";
          cout <<"\n--------------------------------------------------------------------------";

          //DISPLAY MEMBERS
          testHeap.showStructure();
          ready_queue.display();
          proc_queue.display();
        }


        //NO

        //IF PROCESS WILL BE DONE AFTER ONCE PROCESSED
        else if (temp_proc1.prior == 1)
        {
            //TELL WHICH ONE IS LEAVING
            cout << "\nProcess has been released with priority " << temp_proc1.prior
                  << " and ID " << temp_proc1.id << temp_proc1.idnum << "\n";

            //GET ONE FROM READY
            temp_proc1=ready_queue.serve();

            //PUT IT IN POROCESSOR
            proc_queue.enqueue(temp_proc1);

            //RESTORE READY AND HEAP TO A FULL STATE

            //GET ONE FROM HEAP
            testElement = testHeap.removeMax();

            //RESTORE HEAP
            testHeap.insert(generate());

            //TELL WHICH IS COMING INTO READY
            cout << "Current dispatched number into Ready Queue is: "
                  << testElement.rid() << testElement.ridnum()<<":" << testElement.pty()<<".\n";

            //CONVER TestData TO Proc
            temp_proc.prior = testElement.pty();
            temp_proc.id = testElement.rid();
            temp_proc.idnum = testElement.ridnum();

            //STORE IT IN READY
            ready_queue.enqueue(temp_proc);

            //TELL WHICH CAME IN PROCESSOR
            cout << "The new entered process in the processor is " <<temp_proc1.id
                  <<temp_proc1.idnum << ":"<<temp_proc1.prior << ".";
            cout <<"\n--------------------------------------------------------------------------";

            //DISPLAY MEMBERS
            testHeap.showStructure();
            ready_queue.display();
            proc_queue.display();


            //INCREASE THE TOTAL PROCESSED COMPLETELY NUMBER
            counter++;
        }


        //IN CASE SOMETHING ELSE HAPPENS
        else
          {return 0;}


    }
    return 0;
}

//END OF PROGRAM