/********************************************************************************
 *  
 *  File:  PQ.h
 *  Author: Shawn Stoffer
 *  Description:  This is the definition file for the PQ class.  It includes the 
 *                class definition for PQElement which will be used as a base 
 *                class, and for the main class PQ which is the actual priority 
 *                queue.
 *  Systems:  Designed for Linux, SunOS, and AIX, but should work anywhere, as
 *            it is not using any specific system calls.
 *******************************************************************************/

#ifndef _PQ_H_
#define _PQ_H_

#include <iostream.h>
#include <time.h>

class PQElement {
public:
  friend class PQ;

  PQElement(int priority = 0);
  
  virtual ~PQElement();

  // These are functions for setting or getting this elements priority.
  // This philosophy supports the concept of information hiding better than
  // just making member variable public.  And in case we change anything later
  // having to do with what this element does, all that needs to be changed is
  // the functions here.
  void SetPrio(int newp); // Set the priority for this element.
  int Priority(); // Get this PQElement's current priority.
  void SetIndex(int nidx); // Set this elements idx.
  int Index(); // Get this elements idx.

 private:
  int prio;
  int index; // 0 means it is no longer on the queue.
};

//  The actual PQ class declaration.
class PQ {
public:
  friend class Teller;

  //Constructors.
  PQ();        // Default...create a 1 length queue.
  PQ(size_t nsize);    // create a size length queue.  Don't initialize.

  virtual ~PQ();       // Run through the array with a for loop, destroy each element.

  // The ideas here are based upon the book's algorithm, as that is an 
  // efficient and simple way to do it.

  // upheap assumes that the int given to it is a valid location on the heap.
  // this function will crash if sent an invalid location.
  void upheap(int);
  
  // If insert is given a bad pointer then it will insert this value into the
  // table, which will cause problems further into the implentation.
  void insert(PQElement *);

  // The int passed in is assumed to be a valid heap location, and if it is 
  // not this function will crash, as it is accessing unallocated memory.
  void downheap(int);
  
  // This will remove an element from the heap, from the location argument it
  // is given and then fix the heap.
  void extract(size_t);

  // This function will remove the top element from the queue and move 
  // elements accordingly so that the top element is replaced.
  PQElement * remove();

  // This function will check the top element from the queue's time and return
  // that integer.
  int check();

  // the pointer passed in is assumed to be a valid pointer, and if it is not, 
  // this function will cause a bug throughout the rest of the implementation.
  PQElement * replace(PQElement *);

  // This function is just in case the calling program ever knows that it 
  // will need a queue that is larger than it originally allocated.
  void resize(size_t);
 private:
  PQ(const PQ&);             //These will never be used.
  void operator=(const PQ&); // These will never be used.

  PQElement ** queue; // The queue, each list should only be one element long.
  long size;       // The maximum queue size with the current allocated memory.
  long used;         // The current usage of the queue(in elements).
};
#endif