//--------------------------------------------------------------
// Datalogi 2A, February 2002
//
// K opgave: Heap skeleton
//
// Jens Kristian Jensen / Martin Zachariasen
//--------------------------------------------------------------
#ifndef MY_HEAP_H
#define MY_HEAP_H

template < class P, class I >
struct my_heap_node {
  P    key;   // priority (or key) of this element
  I    inf;   // information associated with this element
  //...
};


template < class P, class I >
class my_heap {
  // Define some types related to this class
  typedef my_heap_node<P,I>* item;
  typedef P prio_type;
  typedef I inf_type;

 public:

  // Constructor.
  my_heap() {
    //...
  }
  
  // Return priority of an element.
  const P& prio(item it) const { 
    return it->key; 
  }

  // Return information for an element.
  const I& inf(item it) const {
    return it->inf;
  }

  // Return information for an element.
  const I& operator[](item it) const  {
    return inf(it); 
  }

  // Get reference to element information. 
  I& operator[](item it) {
    return (*it).inf; 
  }

  // Change element information.
  void change_inf(item it, I i) {
    it->inf = i;
  }
  
  // Insert element with priority "p" and information "i" into
  // priority queue. Return item for inserted element.
  item insert(P p, I i) {
    //...
  }

  // Find element having smallest priority value.
  item find_min() const {
    //...
  }
  
  // Delete elment having smallest priority value.
  void del_min() {
    //...
  }
  
  // Delete an element from the priority queue.
  void del_item(item it) {
    //...
  }
  
  // Decrease priority for an element in the priority queue.
  void decrease_p(item it, P x) {
    //...
  }
  
  // Return size of queue (i.e., number of elements).
  int size() const {
    //...
  }

  // Is priority queue empty?
  bool empty() const { 
    return (size() == 0); 
  }

  // Clear heap.
  void clear() {
    //...
  }
  
 private:
  //...
  
};

#endif