/***************************************************************************
                          main.cpp  -  description
                             -------------------
    begin                : Fri Sep 20 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>

//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
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 << "The numbers in the queue are:" << endl;
       for ( j = 0 ; j < size ; j++ )
          cout << element[j].pty() << ", ";
       cout << endl;  }
}

//heap element class



//================================================================================


class TestData
{
  public:

    void setPty ( int newPty )
        { priority = newPty; }   // set
    int pty () const
        { return priority; }     // return

  private:
    int priority;
};

//Main Function
int main()
{
    Heap<TestData> testHeap(20);   // Test heap
    TestData testElement;         // Heap element
    int inputPty, i;              // Input priority and counter for the loop

    cout << endl;
    cout << "Program to demonstrate long-term queue of an operating system based on"
         << endl << "priorities." <<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 may puke! He-he-he!" << endl << endl;
    sleep(6);
    srand(time( NULL ));
    for (i=0; i<20; i++)
    {
       inputPty=1+rand()%100;
       testElement.setPty(inputPty);
       cout << "Inserting... " << testElement.pty() << endl;
       testHeap.insert(testElement);
    }
    cout << endl;
    sleep(3);
    testHeap.showStructure();
    cout << endl;
    i=0;
    while (i==0)
    {
       testElement = testHeap.removeMax();
       cout << "Current dispatched number is: "
                    << " pty = " << testElement.pty() << endl;
       // srand(time( NULL )); Not sure if this would have to be here or not
        //It does bring up random numbers in both cases
       inputPty=1+rand()%100;
       testElement.setPty(inputPty);
       cout << "The new coming number is: " << testElement.pty() << endl;
       testHeap.insert(testElement);
       testHeap.showStructure();
       sleep(2);
       cout << endl << endl;
    }


    return 0;
}