/****************************************************************************
| HEADER FILE FOR THE priority MODULE (priority.h)
|
| EXPORTED ITEMS:
| CompleteBinaryTree Class:
|   A complete binary tree.  Each node in the tree contains data of type
|   DataAtOneNode.
|
| template <class Entry>
| class PriorityQueue
|   A priority queue of entries.  Each entry in the priority queue has type
|   Entry, and has a priority of type int.
|
| METHODS FOR THE CompleteBinaryTree CLASS
|
| CompleteBinaryTree(unsigned int RequestedCapacity);
|   This is the constructor.  RequestedCapacity is the maximum capacity which
|   is requested for this priority queue.
| 
| int Empty();
|   Returns true if the tree is empty; otherwise, returns false.
|
| 
| int Full();
|   Returns true if the tree is full; otherwise, returns false.
|
| 
| unsigned int Size();
|   Returns the number of nodes in the tree.
|
| void AddNode(DataAtOneNode NewEntry);
|   Precondition: Full returns false.
|   Postcondition: A new node has been added to the complete binary tree, at
|   the next available location.  The entry stored in this node is
|   NewEntry.
|   
| 
| void RemoveNode();
|   Precondition: Size > 0.
|   Postcondition: The most-recently added node has been removed
|   from the tree. 
| 
| void ChangeEntry(unsigned int NodeNumber, DataAtOneNode NewEntry);
|   Precondition: Index < Size.
|   Postcondition: The data stored at the node with number Index has been
|   changed to NewEntry, and the tree is otherwise unchanged.  Note:
|   The Root is node number 0, the next level has nodes 1 and 2, and so on.
|
| 
| void FetchEntry(unsigned int NodeNumber, DataAtOneNode& Result);
|   Precondition: Index < Size.
|   Postcondition: The value of Result has been set to the data stored at
|   node number Index.  The tree is unchanged.
|
| 
| void SwapWithParent(unsigned int Index);
|   Precondition: 0 < Index < Size.
|   Postcondition: The data stored at the node with number Index has been
|   swapped with the data stored at the parent of that node.  The tree is
|   otherwise unchanged.
|
| METHODS FOR THE PriorityQueue CLASS
|
| PriorityQueue(unsigned int RequestedCapacity);
|   This is the constructor.  RequestedCapacity is the maximum capacity which
|   is requested for this priority queue.
|
| void Insert(Entry NewEntry, int Priority);
|   Precondition: Full() returns false.
|   Postcondition: A new copy of NewEntry has been added to the priority queue
|   with the given Priority.
|
| void GetFront(Entry& Result);
|   Precondition: The priority queue is not empty.
|   Postcondition: The highest priority entry of the priority queue has been
|   assigned to Result, and has been removed from the queue.  (If several
|   entries have the same priority, then they are removed in FIFO order.)
|
| int Empty();
|   Returns true if the priority queue is empty; otherwise, returns false.
|
| int Full();
|   Returns true if the priority queue can NOT accept another item;
|   otherwise, returns false.
|
| unsigned int Size();
|   Returns the total number of entries in the priority queue.
|**************************************************************************/

/* In general, we do not want to include all these definitions if they have
|  already been included from some other location.  Therefore, we check whether
|  the definitions have previously been defined, and if so then we skip to
|  the end of this file. */
#ifndef PRIORITY_DEFINITIONS
#define PRIORITY_DEFINITIONS

#include <iostream.h>   // Permits writing of error messages to cerr
#include <stdlib.h>     // Permits use of exit
#define FALSE 0
#define TRUE 1

template <class DataAtOneNode>
class CompleteBinaryTree {
  // Student may define whatever private data fields are needed
    unsigned int Used;
    unsigned int Capacity;
    DataAtOneNode* Data;
  public:
    CompleteBinaryTree(unsigned int RequestedCapacity);
    int Empty();
    int Full();
    unsigned int Size();
    void AddNode(DataAtOneNode NewEntry);
    void RemoveNode();
    void ChangeEntry(unsigned int NodeNumber, DataAtOneNode NewEntry);
    void FetchEntry(unsigned int NodeNumber, DataAtOneNode& Result);
    void SwapWithParent(unsigned int Index);
    ~CompleteBinaryTree() { delete [] Data; }
};

template <class Entry, class PriorityType>
class PriorityQueueData {
  public:
    Entry Value;
    PriorityType Priority;
    int TimeStamp;
};

template <class Entry, class PriorityType>
class PriorityQueue {
  private:
    typedef PriorityQueueData<Entry, PriorityType> DataAtOneNode;
    CompleteBinaryTree<DataAtOneNode> Heap;
    unsigned int NumberOfCallsToInsert;
    int PeckingOrder(unsigned int Index1, unsigned int Index2);
    void ReheapifyUp();
    void ReheapifyDown();
  public:
    PriorityQueue(unsigned int RequestedCapacity);
    void Print();
    void Insert(Entry NewEntry, PriorityType Priority);
    void GetFront(Entry& Result);
    int Empty() { return Heap.Empty(); }
    int Full()  { return Heap.Full(); }
    unsigned int Size() { return Heap.Size(); }
};

template <class Entry, class PriorityType>
void PriorityQueue<Entry,PriorityType>::Print() {
  int I;
  for (I = 0; I < Size(); I++) {
    DataAtOneNode D;
    Heap.FetchEntry(I, D);
    cout << I << " " << D.Priority << " " << D.Value << endl;
  }
}

/**********************************************************************
| Implementation of the complete binary tree. */

template <class DataAtOneNode>
CompleteBinaryTree<DataAtOneNode>::
CompleteBinaryTree(unsigned int RequestedCapacity) {
  Used = 0;
  Capacity = RequestedCapacity;
  Data = new DataAtOneNode[RequestedCapacity];
}
  
template <class DataAtOneNode>
int CompleteBinaryTree<DataAtOneNode>::Empty() {
  return (Used == 0);
}

template <class DataAtOneNode>
int CompleteBinaryTree<DataAtOneNode>::Full() {
  return (Used == Capacity);
}

template <class DataAtOneNode>
unsigned int CompleteBinaryTree<DataAtOneNode>::Size() {
  return Used;
}

template <class DataAtOneNode>
void CompleteBinaryTree<DataAtOneNode>::AddNode(DataAtOneNode NewEntry) {
  if (Full()) {
    cerr << "ERROR in AddNode: Full tree." << endl;
    exit(0);
  }
  Data[Used++] = NewEntry;
}

template <class DataAtOneNode>
void CompleteBinaryTree<DataAtOneNode>::RemoveNode() {
  if (Empty()) {
    cerr << "ERROR in RemoveNode: Empty tree." << endl;
    exit(0);
  }
  Used--;
}

template <class DataAtOneNode>
void CompleteBinaryTree<DataAtOneNode>::
ChangeEntry(unsigned int Index, DataAtOneNode NewEntry) {
  if (Index >= Used) {
    cerr << "ERROR in ChangeEntry: Index too big." << endl;
    exit(0);
  }
  Data[Index] = NewEntry;
}

template <class DataAtOneNode>
void CompleteBinaryTree<DataAtOneNode>::
FetchEntry(unsigned int Index, DataAtOneNode& Result) {
  if (Index >= Used) {
    cerr << "ERROR in FetchEntry: Index too big." << endl;
    exit(0);
  }
  Result = Data[Index];
}

template <class DataAtOneNode>
void CompleteBinaryTree<DataAtOneNode>::SwapWithParent(unsigned int Index) {
  if ((Index == 0) || (Index >= Used)) {
    cerr << "ERROR in ChangeEntry: Illegal Index." << endl;
    exit(0);
  }
  unsigned int ParentIndex = (Index-1)/2;
  DataAtOneNode Temp = Data[Index];
  Data[Index] = Data[ParentIndex];
  Data[ParentIndex] = Temp;
}

/**********************************************************************
| PriorityQueue Implementation.
| Note: All methods must make sure that the field NumberOfCallsToInsert
| is always equal to the number of times that Insert has been called for
| this object.  When a new entry is inserted, the value of that item's
| TimeStamp is set to the current value of NumberOfCallsToInsert.
| Therefore, a smaller timestamp indicates an earlier entry time. */

template <class Entry, class PriorityType>
PriorityQueue<Entry, PriorityType>::
PriorityQueue(unsigned int RequestedCapacity)
: Heap(RequestedCapacity)
{
}

template <class Entry, class PriorityType>
int PriorityQueue<Entry, PriorityType>::
PeckingOrder(unsigned int Index1, unsigned int Index2) {
/*  This is a private method that will be useful within the implementation
|   of ReheapifyUp and ReheapifyDown.
|   Precondition: Index1 and Index2 are both less than or equal to Size.
|   Postcondition: In the Heap, the node with Index1 is compared to the
|   node with Index2.  This function returns true under any of the following
|   conditions:
|     a. If (Priority of Index1) > (Priority of Index2).
|     b. Or, if the Priorities are equal and 
|        (TimeStamp of Index 1) < (TimeStamp of Index 2).
|   Otherwise, the function returns false. */
  DataAtOneNode Value1, Value2;
  Heap.FetchEntry(Index1, Value1);
  Heap.FetchEntry(Index2, Value2);
  if (Value1.Priority > Value2.Priority) return TRUE;
  if (Value1.Priority < Value2.Priority) return FALSE;
  return Value1.TimeStamp < Value2.TimeStamp;
}

template <class Entry, class PriorityType>
void PriorityQueue<Entry, PriorityType>::ReheapifyDown() {
/*  This is a private method that will be useful within the implementation
|   of Insert.
|   Precondition: The heap contains at least one entry, and Heap is a valid
|   heap with one possible exception: The value stored in the root might
|   be less than its children.
|   Postcondition: The heap has been reheapified downward so that it is once
|   again a valid heap. */
  unsigned int Index = 0;
  do {
    unsigned int BigIndex = Index;
    unsigned int Left = Index*2 + 1;
    unsigned int Right = Left+1;
    if ((Left < Size()) && PeckingOrder(Left, BigIndex)) BigIndex = Left;
    if ((Right < Size()) && PeckingOrder(Right, BigIndex)) BigIndex = Right;
    if (BigIndex == Index) return;
    Heap.SwapWithParent(BigIndex);
    Index = BigIndex;
  }
  while (TRUE);
}

template <class Entry, class PriorityType>
void PriorityQueue<Entry, PriorityType>::ReheapifyUp() {
/*  This is a private method that will be useful within the implementation
|   of GetFront.
|   Precondition: Heap is a valid heap with one possible exception: The value
|   stored in the final node might be more than its parent.
|   Postcondition: The heap has been reheapified upward so that it is once
|   again a valid heap. */
  unsigned int Index = Size()-1;
  unsigned int ParentIndex;
  while (Index && PeckingOrder(Index, ParentIndex = (Index-1)/2)) {
    Heap.SwapWithParent(Index);
    Index = ParentIndex;
  }
}
  
template <class Entry, class PriorityType>
void PriorityQueue<Entry, PriorityType>::Insert(Entry NewEntry, PriorityType Priority) {
  DataAtOneNode Record;
  Record.Value = NewEntry;
  Record.Priority = Priority;
  Record.TimeStamp = NumberOfCallsToInsert++;
  Heap.AddNode(Record);
  ReheapifyUp();
}

template <class Entry, class PriorityType>
void PriorityQueue<Entry, PriorityType>::GetFront(Entry& Result) {
  DataAtOneNode Record;
  Heap.FetchEntry(0, Record);
  Result = Record.Value;
  Heap.FetchEntry(Size()-1, Record);
  Heap.ChangeEntry(0, Record);
  Heap.RemoveNode();
  if (Size() > 0) ReheapifyDown();
}

#endif