// FILE: pqueue.h
// CLASS PROVIDED: PriorityQueue (a priority queue of items)
//
// TYPEDEF and MEMBER CONSTANT for the PriorityQueue class:
//   static const size_t CAPACITY = ______
//     PriorityQueue::CAPACITY is the maximum number of entries that
//     may be be in the priority queue at any one time.
//
//   typedef _____ Item 
//     The type Item is the data type of the items in the Priority Queue.
//     It may be any of the C++ built-in types (int, char, etc.), or a class 
//     with a default constructor, a copy constructor, and assignment operator.
//
// CONSTRUCTOR for the PriorityQueue class:
//   PriorityQueue( )
//     Postcondition: The PriorityQueue has been initialized with no Items.
//
// MODIFICATION MEMBER FUNCTIONS for the PriorityQueue class:
//   void insert(const Item& entry, unsigned int priority)
//     Postcondition: A new copy of entry has been inserted with the specified
//     priority.
//
//   Item get_front( )
//     Precondition: size( ) > 0.
//     Postcondition: The highest priority item has been returned and has been
//     removed from the PriorityQueue. (If several items have equal priority,
//     then there is no guarantee about which one will come out first!
//     This differs from our first priority queue.)
//
// CONSTANT MEMBER FUNCTIONS for the PriorityQueue class:
//   size_t size( ) const
//     Postcondition: Return value is the total number of items in the
//     PriorityQueue.
//
//   bool is_empty( ) const
//     Postcondition: Return value is true if the PriorityQueue is empty.
//
// VALUE SEMANTICS for the PriorityQueue class:
//   Assignments and the copy constructor may be used with
//   PriorityQueue objects

#ifndef PQUEUE_H
#define PQUEUE_H

#include <cstdlib>

class PriorityQueue {
  public:
    typedef int Item;
    static const std::size_t CAPACITY = 5000;
    PriorityQueue( );
    void insert(const Item& entry, unsigned int priority);
    Item get_front( );
    std::size_t size( ) const {
      return many_items; }
    bool is_empty( ) const {
      return (many_items == 0); }
    void print_tree(const char message[ ] = "", std::size_t i = 0) const;
  private:
    struct OneItemInfo {
      Item data;
      unsigned int priority; };
    OneItemInfo heap[CAPACITY];
    std::size_t many_items;
    bool is_leaf(std::size_t i) const;
    std::size_t parent_index(std::size_t i) const;
    unsigned int parent_priority(std::size_t i) const;
    std::size_t big_child_index(std::size_t i) const;
    unsigned int big_child_priority(std::size_t i) const;
    void swap_with_parent(std::size_t i);
};

#endif