#ifndef _INTERVALHEAP_H
#define _INTERVALHEAP_H

#include <vector>
using namespace std;

template <class Comparable>
class IntervalHeap;

template <class Comparable>
class IntervalHeapNode
{
   friend class IntervalHeap <Comparable>;

   public:
   Comparable left,
              right;
};

// IntervalHeap class
//
// CONSTRUCTION: with an optional capacity (that defaults to 100)
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// deleteMin( minItem )   --> Remove (and optionally return) smallest item
// Comparable findMin( )  --> Return smallest item
// bool isEmpty( )        --> Return true if empty; else false
// bool isFull( )         --> Return true if full; else false
// void makeEmpty( )      --> Remove all items
// ******************ERRORS********************************
// Throws Underflow and Overflow as warranted

class Underflow{};
class Overflow {};


template <class Comparable>
class IntervalHeap
{
   public:
      explicit IntervalHeap( int cap = 10000 );
      ~IntervalHeap ( ) { delete [] array; }

      bool isEmpty( ) const { return currentSize==0; }

      const Comparable & findMin( ) const;
      const Comparable & findMax( ) const;
      
      void insert( const Comparable & x );

      void deleteMin( );
      void deleteMax( );

      void makeEmpty( );
      void print( ) const;
      
   private:
      int currentSize;  // Number of elements in heap
      int capacity; // Maximum number of elements
      IntervalHeapNode<Comparable> *array;        // The heap array
      
};

#include "IntervalHeap.cpp"
#endif