include/AD/contain/mmheap.h

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef min_max_heap_h
  26 #define min_max_heap_h
  27
  28 //////////////////////////////////////////////////////////////////////////////
  29 //  A min-max heap is a variant of binary heap that allows O(1) minimum
  30 //  and maximum extraction.  The other operations(enqueue, delete_min)
  31 //  stays at O(log n).
  32 //////////////////////////////////////////////////////////////////////////////
  33
  34 #include <A/generic/ordering.h>
  35
  36 template <class T, class Array>
  37    class MinMaxHeap : public Array {
  38       int queued_elements; // number of elements on queue
  39    public:
  40
  41       //////////////////////////////////////////////////////////////////////
  42       //  Constructors and destructor
  43       //////////////////////////////////////////////////////////////////////
  44       MinMaxHeap(size) : queued_elements(0), Array(size) {}
  45       MinMaxHeap(const MinMaxHeap& H) : Array(H.size()) { *this = H; }
  46      ~MinMaxHeap() {}
  47
  48       //////////////////////////////////////////////////////////////////////
  49       // Assignment
  50       //////////////////////////////////////////////////////////////////////
  51       MinMaxHeap& operator = (const MinMaxHeap&);
  52
  53       //////////////////////////////////////////////////////////////////////
  54       //  Selectors
  55       //////////////////////////////////////////////////////////////////////
  56       int  size()     const { return queued_elements; }
  57       // int  capacity() const; // inherited from Array
  58       Bool is_empty() const { return queued_elements == 0; }
  59       Bool is_full()  const { return queued_elements == capacity(); }
  60       T&   min()      const;
  61       T&   max()      const;
  62
  63       //////////////////////////////////////////////////////////////////////
  64       //  Mutators
  65       //////////////////////////////////////////////////////////////////////
  66       Ix   insert(const T& e) { return enqueue(e); }
  67       Ix   enqueue(const T&);
  68       Bool delete_min();
  69       Bool delete_max();
  70
  71       //////////////////////////////////////////////////////////////////////
  72       //  Iterators
  73       //////////////////////////////////////////////////////////////////////
  74       // Inherited from class Array
  75    };
  76
  77 ////////////////////////////////////////////////////////////////////////////
  78 //  Implementation of the template methods
  79 ////////////////////////////////////////////////////////////////////////////
  80 template <class T, class A>
  81    MinMaxHeap<T,A>& MinMaxHeap<T,A>::operator = (const MinMaxHeap<T,A>& H)
  82    {  if (this != &H) {
  83       }
  84       return *this;
  85    }
  86
  87 template <class T, class A>
  88    Ix MinMaxHeap<T,A>::enqueue(const T& e)
  89    {
  90    }
  91
  92 template <class T, class A>
  93    Bool MinMaxHeap<T,A>::delete_min()
  94    {
  95    }
  96
  97 template <class T, class A>
  98    Bool MinMaxHeap<T,A>::delete_max()
  99    {
 100    }
 101
 102 #endif