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

#ifndef PRIORITYQUEUE_HH
#define PRIORITYQUEUE_HH

/**
 * An abstract base class which describes the ADT for priority queues. 
 * The elements in this priority queue are ordered according to a 
 * comparator class.
 *
 * This is the templated version of the PriorityQueue.
 */

template< typename Type, typename Comparator >
class PriorityQueue
{
public:
  /**
   * Constructs a new, empty priority queue.  You don't need
   * to pass in an instance of the Comparator class, since you 
   * can instantiate your own (of course, this means that the 
   * Comparator class must not forbid the default constructor).
   */
  PriorityQueue() {};

  /**
   * A pure 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 reference to the the minimum element in
   * the priority queue.
   */
  virtual const Type& findMin() const = 0;   

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

  /**
   * Removes the minimum element from the priority queue and
   * returns a copy of it.
   */
  virtual Type deleteMin() = 0;          

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

 protected:
  /* The Comparator is a "function object" used to compare two keys.
   *
   * A "function object" is basically a class which abstracts the
   * idea of a function.  Therefore, a "function object" is a class
   * which can be called as if it were a function!
   *
   * A "function object" must overload operator() (the function call
   * operator!) so that it can be called as a function.  Here, our
   * Comparator must compare two objects of type Type, so its
   * operator() is defined to take two arguments and return a bool
   * indicating the relative ordering of its arguments.
   *
   * Our Comparator class is called with the following syntax (this
   * example assumes we have an instance of the Comparator class 
   * named m_comp):
   *
   *   Type t1, t2;
   *   if( m_comp( t1, t2 ) )
   *      ... t1 is "less" than t2 ("less" is defined by the Comparator) ...
   *   else if( m_comp( k2, k1 ) )
   *      ... t2 is "less" than t1 ...
   *   else
   *      ... t1 == t2 ...
   *
   * A Comparator for doubles may look something like this:
   *
   * class DoubleComparator
   * {
   * public:
   *     // This comparator returns whether the first arg is less than
   *     // the second arg.  Note that I can change the behaviour of the
   *     // DoubleComparator's client by, for example, returning
   *     // "left > right".  For instance, if DoubleComparator was used
   *     // by a heap, I could change my heap from a min-heap to a max-heap
   *     // just by changing the comparator!
   *     bool operator()( double left, double right )
   *     {
   *           return left < right;
   *     }
   * };
   */
  Comparator comparator;
};

#endif /* PRIORITYQUEUE_HH */