#ifndef _PQ_H
#define _PQ_H

// templated priority queue class
// written and modified many times
// 11/27/95 
//          to use vector class rather than array type
// 12/30/96
//          changed to use two templated classes, one for
//          item, one for priority (old version had int
//          for priority)
//          also added DeleteMin in two ways: one has
//          parameters to return values when deleting
//
// 11/99    changed to tvector class
// 
// 2/00     changed to single template parameter
// operations:
//
// tpqueue()
//     construct pqueue using standard < operator
//
// tpqueue(const Comparer& comp)
//     construct pqueue using comparer object comp, see comparer.h
//
// void insert(const Kind& )
//     insert Kind object 
//
// int size()    const
//     returns the number of elements in the priority queue
//
// bool isEmpty() const
//     returns true if pqueue is empty, otherwise returns false
//
// void deletemin()
//     remove minimal element from queue
//
// void deletemin(Kind &)
//     remove minimal element and return it 
//
// Kind&  getmin()
//     return minimal element
//
// Complexity:
//
// a heap-based implementation is used, so minelt is O(1)
// and insert/deletemin are O(log n) where n is # of items in pqueue
// (insert is O(1) average case)
//

#include "tvector.h"
#include "comparer.h"


template <class Kind>
class tpqueue
{
  public:
    tpqueue();
    tpqueue(const Comparer<Kind>& cmp);
    ~tpqueue();
    void insert(const Kind & kind);      // insert kind
    int size()     const;                // return # of elements
    bool isEmpty() const;                // return true iff empty

    void deletemin();                    // remove min elt from 
    void deletemin(Kind &);              // remove/return min elt
    Kind& getmin( );                     // return min elt

    void dump() const;
    
  private:
    void init (int n);                   // reserve space for n elements

    const Comparer<Kind>& myComp;

    static Comparer<Kind> ourComp;
    
    void heapify(int vroot);             // percolate down function
    tvector<Kind> myList;                // array of prioritized stuff
    int myNumElts;                       // # elements in priority queue
};

// uncomment line below if including source code 
#include "tpq.cpp"

#endif