// PriorityQueue.hh -- contains the declaration of the abstract class PriorityQueue.

#ifndef PRIORITYQUEUE_HH
#define PRIORITYQUEUE_HH

#include "Comparator.hh"
#include <cassert>  // For definition of assert
#include <cstddef>  // For definition of NULL

/**
 * An abstract base class which describes the ADT for priority queues. 
 * The elements in this priority queue are ordered according to a 
 * comparator functor which must be passed in during construction
 * of a priority queue.  
 *
 * Since we do not know the type of the objects which will be stored in 
 * this priority queue, we will store (generic) pointers to the client's 
 * data, instead of the data itself.  Note that this places the burden of
 * memory management on the client.  A void* is a pointer to any type.
 */
class PriorityQueue {
public:
  /**
   * Constructs a new, empty priority queue ordered by the given 
   * comparator.
   */
  PriorityQueue(Comparator c) {
	  assert( c != NULL );
	  comparator = c;
  }
	
  /**
   * A virtual destructure is used to ensure proper dynamic
   * dispatch of the destrutors for all subclasses.
   */
  virtual ~PriorityQueue() {}

  /**
   * Returns true if the priority queue has no elements.
   */
  virtual bool isEmpty() const = 0;

  /**
   * Returns a const pointer to the the minimum element in
   * the priority queue.
   */
  virtual const void* findMin() const = 0;   

  /**
   * Insert item into the priority queue.
   */
  virtual void insert(const void *item) = 0;    

  /**
   * Removes the minimum element from the priority queue and
   * returns a const pointer to it.
   */
  virtual const void* deleteMin() = 0;          

  /**
   * Removes all elements from the priority queue.
   * This should not deallocate memory for the elements!
   */
  virtual void clear() = 0;                 

 protected:
  // the comparator functor used for ordering the priority queue
  Comparator comparator;
};

#endif /* PRIORITYQUEUE_HH */