include/AD/contain/priqueue.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 priority_queue_h
  26 #define priority_queue_h
  27
  28 ///////////////////////////////////////////////////////////////////////
  29 //  Class PriQueue<T> is a binary heap array based
  30 //  priority queue parameterized by the element type
  31 //  and the implementation array type.
  32 //
  33 //    Suitable implementation array types include
  34 //        FixArray<T>   --- array with size fixed at compile type
  35 //        Array<T>      --- array with size fixed at creation type
  36 //        VarArray<T>   --- growable array
  37 //        Indexable<T>  --- array-like object with fast growth
  38 //
  39 //  If a variable sized priority queue is desired, see also pagodas or
  40 //  splay trees, which are also implemented in this library.
  41 ///////////////////////////////////////////////////////////////////////
  42
  43 #include <AD/generic/generic.h>  // Generic definitions
  44
  45 template<class T, class A>
  46    class PriQueue : public A {
  47
  48       int elemCount;  // number of elements currently here
  49
  50    public:
  51
  52       ///////////////////////////////////////////////////////////
  53       // Constructors and destructor
  54       ///////////////////////////////////////////////////////////
  55       PriQueue(int size) : A(size), elemCount(0) {}
  56       PriQueue(const PriQueue& Q) : A(Q.capacity()) { *this = Q; }
  57      ~PriQueue() {}
  58
  59       ///////////////////////////////////////////////////////////
  60       // Assignment
  61       ///////////////////////////////////////////////////////////
  62       void operator = (const PriQueue&);
  63
  64       ///////////////////////////////////////////////////////////
  65       // Selectors
  66       //   Method capacity() and operator [] are inherited from
  67       // the base class.
  68       ///////////////////////////////////////////////////////////
  69       // int capacity()         const; // inherited
  70       // T& operator [] (int i) const; // inherited
  71       inline int  size()               const { return elemCount; }
  72       inline Bool is_empty()           const { return elemCount == 0; }
  73       inline Bool is_full()            const { return elemCount == capacity(); }
  74       inline const T&   min()          const { return (*this)[0]; }
  75       inline       T&   min()                { return (*this)[0]; }
  76
  77       ///////////////////////////////////////////////////////////
  78       // Mutators
  79       ///////////////////////////////////////////////////////////
  80       inline void clear()            { elemCount = 0; }
  81       inline void delete_min()       { dequeue(); }
  82       void enqueue(const T&);
  83       void requeue(int);
  84       void dequeue(int = 0);
  85    };
  86
  87 ///////////////////////////////////////////////////////////////////////
  88 //  Assignment is redefined to copy only the existing elements
  89 ///////////////////////////////////////////////////////////////////////
  90 template<class T, class A>
  91    void PriQueue<T,A>::operator = (const PriQueue<T,A>& Q)
  92    {  if (this != &Q) {
  93          elemCount = Q.elemCount;
  94          for (register int i = elemCount-1; i >= 0; i--) (*this)[i] = Q[i];
  95       }
  96    }
  97
  98 ///////////////////////////////////////////////////////////////////////
  99 // Both insert and deletion algorithms below have been
 100 // optimized to eliminate unnecessary assignments.
 101 // The basic technique is quite simple: instead of swaping
 102 // existing elements during reorganization, propagate the ``hole''
 103 // instead.  This way we can cut down the number of moves
 104 // by approximately 1/2.
 105 ///////////////////////////////////////////////////////////////////////
 106 template<class T,class A>
 107    void PriQueue<T,A>::dequeue(register int i)
 108    {   register int j;
 109
 110        // Integer |i| is the index to the current ``hole''
 111        // and integer |j| is the index of its left child.
 112        // Therefore |j+1| is the index of the right child.
 113        // The pointer |pivot| fingers the current ``out of place''
 114        // element.  We'll proceed from the root (or the |i|th
 115        // element if the argument |i| is supplied) of the heap and work
 116        // our way down to the leaves.
 117
 118        --elemCount;   // one less element
 119        register T& pivot = (*this)[elemCount];  // last element
 120
 121        for ( ; (j = i + i + 1) <= elemCount; i = j) {
 122           if (compare(pivot,(*this)[j]) < 0) {
 123              if (j <= elemCount && compare((*this)[j], (*this)[j+1]) < 0) j++;
 124           } else if (j > elemCount || compare(pivot, (*this)[j+1]) >= 0) break;
 125           (*this)[i] = (*this)[j];
 126        }
 127        (*this)[i] = pivot;
 128    }
 129
 130 ///////////////////////////////////////////////////////////////////////
 131 //  Enqueuing an element
 132 ///////////////////////////////////////////////////////////////////////
 133 template<class T, class A>
 134    void PriQueue<T,A>::enqueue(const T& element)
 135    {  register int i, j;
 136
 137       // Integer |i| is the index to the current ``hole'' while
 138       // integer |j| is the index of its root, which is equal
 139       // to |(i - 1)/2|.  We'll start from the bottom of the heap
 140       // and work our way up to the root(min element).
 141
 142       for (i = elemCount; i > 0; i = j) {
 143          j = (i-1) / 2;
 144          if (compare((*this)[j], element) < 0) break;
 145          (*this)[i] = (*this)[j];
 146       }
 147       (*this)[i] = element;
 148       elemCount++;
 149    }
 150
 151 ///////////////////////////////////////////////////////////////////////
 152 // Requeuing is the operation of moving an element
 153 // towards the front of the heap.   This is handled in a
 154 // manner similar to the ``enqueue'' operation.
 155 ///////////////////////////////////////////////////////////////////////
 156 template<class T, class A>
 157    void PriQueue<T,A>::requeue(register int i)
 158    {  register int j;
 159       register T& pivot = (*this)[i];
 160       for ( ; i > 0; i = j) {
 161          j = (i-1) / 2;
 162          if (compare((*this)[j], pivot) < 0) break;
 163          (*this)[i] = (*this)[j];
 164       }
 165       (*this)[i] = pivot;
 166    }
 167
 168 #endif