#ifndef BINHEAP_H
#define BINHEAP_H

#include <stdexcept>
#include <iostream>

using namespace std;

// Because the templates make it nearly impossible to have the Node class
// held within the BinHeap class, we are putting this out in the open this
// time.  
template <typename T>
struct Node
{
  // The value in this node
  T val;
  
  // The number of elements in the linked list of our children
  unsigned int degree;
  
  // A pointer to the head of our child linked-list (leftmost child)
  Node<T>* child;
  
  // A pointer to a sibling (to our right)
  Node<T>* sibling; 
};


template <typename T> 
class BinHeap
{
  // Whoa, that is some seriously ugly syntax.  
  friend ostream& operator << <T>(ostream&, const BinHeap<T>&);

public:
  // Default constructor
  BinHeap<T>();

  // A handy exception for you to throw when there is nothing in the heap
  // but someone is asking for the min.
  // In order to reference this exception OUTSIDE of the class
  // (in main, for example), you simply call it BinHeap<T>::heap_empty
  // (although in main you'll probably put in an "int" in place of the "T").
  class heap_empty : public exception { } ;

  // Get the min, but don't do anything to the heap
  T min() const throw (heap_empty);

  // Get the min and remove it
  T extractMin() throw (heap_empty);

  // Merge two heaps.
  BinHeap<T>& operator += (BinHeap<T>& H2);

  // Insert the given value
  void insert(T val);

  // How many nodes are in this heap?
  unsigned int size() const;

  // Print out the heap.  This is used by operator <<, because 
  // again the templates make life real tricky.
  void print(ostream& lhs) const;  

 private:

  // A handy function: add the Node* with the smaller value to
  // the head of the other Node*'s child list.  Also increment
  // the degree, etc etc.
  Node<T>* Link(Node<T>* y, Node<T>* z);

  // The Hard Part. 
  // Precondition: Every Node* in both linked lists has a SMALLER degree
  //  than it's "sibling."  (Not <=, <).  
  // Postcondition: The two lists have been linked together, and any
  //  duplicated degrees have been merged together into a higher degree.
  //  The resulting list is returned.
  // 
  // You really ought to implement this in 2 phases:
  // PHASE 1: 
  //  Go through the lists (which you know are "sorted") and make them
  //  into a single, sorted, linked list
  // PHASE 2:
  //  Go through the list and merge/link any adjacent heaps in the list that
  //  are of the same size.
  //  There are really a few options at each step:
  //   1. This one and the next are ordered
  //   2. This one and the next are equal, and are the last two
  //   3. This one and the next, and the one after THAT are equal
  //   4. This one and the next are equal, and the one after that is
  //      bigger.
  //  If you can figure out how to deal with each of these, then this
  //  function isn't that complicated.  You'll want to call Link 
  //  in cases 2 and 4, and just keep moving in cases 1 and 3.  
  Node<T>* HeapMerge(Node<T>* h1, Node<T>* h2);

  // Given a linked-list, reverse it (linked-list based on siblings here)
  Node<T>* revChildren(Node<T>* head, Node<T>* other);

  // A print helper.  Depth governs the number of spaces printed,
  // heap is the index in the master root-list.
  void print(ostream& lhs, Node<T>* root, int depth, int heap) const;

  // The head of the root-list
  Node<T>* head;

  // How many nodes in this list total?  SET this when you call the
  // constructor or do a manual insert.  Increment this by the size
  // of the other list when you call +=.  Set this to 0 (and head to NULL)
  // if you ARE the other list and someone called += on you (otherwise
  // we're gonna have memory problems in a big way.)
  unsigned int _size;

};



#endif // BINHEAP_H