/home/vlg/develop/libASSA/libassa/assa/PriorityQueue_Heap.h

Go to the documentation of this file.
00001 // -*- c++ -*-
00002 //------------------------------------------------------------------------------
00003 //                        PriorityQueue_Heap.h
00004 //------------------------------------------------------------------------------
00005 //  Copyright (c) 1999 by Vladislav Grinchenko
00006 //
00007 //  This library is free software; you can redistribute it and/or
00008 //  modify it under the terms of the GNU Library General Public
00009 //  License as published by the Free Software Foundation; either
00010 //  version 2 of the License, or (at your option) any later version.
00011 //------------------------------------------------------------------------------
00012 #ifndef PRIORITY_QUEUE_HEAP_H
00013 #define PRIORITY_QUEUE_HEAP_H
00014 
00015 #include <sys/types.h>
00016 #include <string.h>
00017 
00018 #include "assa/PriorityQueue_Impl.h"
00019 
00020 namespace ASSA {
00021 
00028 template< class T, class Compare >
00029 class PriorityQueue_Heap : public PriorityQueue_Impl< T, Compare >
00030 {
00031 public:
00032     PriorityQueue_Heap (size_t max_ = 0);
00033     PriorityQueue_Heap (size_t, const Compare&);
00034     PriorityQueue_Heap (const PriorityQueue_Heap&);
00035     ~PriorityQueue_Heap ();
00036 
00037     PriorityQueue_Heap& operator= (const PriorityQueue_Heap&);
00038 
00039     void     insert (const T&);
00040     T        pop ();
00041     const T& top () const;
00042     bool     remove (T);
00043     size_t   size ();
00044     T&       operator[] (int idx);
00045 
00046 protected:
00047     void upheap (size_t);
00048     void downheap (size_t);
00049     bool resize (size_t);
00050 
00051     Compare m_comp;
00052     
00053 private:
00054     void allocate (size_t);
00055 
00056     T* m_queue;                 
00057     size_t  m_size;             
00058     size_t  m_curr;             
00059     size_t  m_lwm;              
00060 };
00061 
00062 template< class T, class Compare>
00063 inline
00064 PriorityQueue_Heap<T, Compare>::
00065 PriorityQueue_Heap (size_t maxsz_)
00066     : m_curr (1), m_lwm (20)
00067 {
00068     trace("PriorityQueue_Heap::PriorityQueue_Heap");
00069     allocate (maxsz_);
00070 }
00071 
00072 template< class T, class Compare>
00073 inline
00074 PriorityQueue_Heap<T, Compare>::
00075 PriorityQueue_Heap (size_t maxsz_, const Compare& x_)
00076     : m_comp (x_), m_curr (1), m_lwm (20)
00077 {
00078     allocate (maxsz_);
00079 }
00080 
00081 template< class T, class Compare>
00082 inline void
00083 PriorityQueue_Heap<T, Compare>::
00084 allocate (size_t s_)
00085 {
00086     m_size = s_ > m_lwm ? s_ : m_lwm;
00087     m_queue = new T [m_size];
00088 }
00089 
00090 template< class T, class Compare>
00091 inline 
00092 PriorityQueue_Heap<T, Compare>::
00093 PriorityQueue_Heap (const PriorityQueue_Heap& h_)
00094     : m_comp (h_.m_comp), m_size (h_.m_size), m_curr (h_.m_curr),
00095       m_lwm (h_.m_lwm)
00096 {
00097     allocate (m_size);
00098     ::memcpy (m_queue, h_.m_queue, sizeof(T)*m_curr);
00099 }
00100 
00101 template< class T, class Compare>
00102 PriorityQueue_Heap<T, Compare>&
00103 PriorityQueue_Heap<T, Compare>::
00104 operator= (const PriorityQueue_Heap& h_)
00105 {
00106     delete [] m_queue;
00107     m_comp = h_.m_comp;
00108     m_size = h_.m_size;
00109     m_curr = h_.m_curr;
00110     m_lwm  = h_.m_lwm;
00111     allocate (m_size);
00112     ::memcpy (m_queue, h_.m_queue, sizeof(T)*m_curr);
00113     return *this;
00114 }
00115 
00116 template< class T, class Compare>
00117 inline 
00118 PriorityQueue_Heap<T, Compare>::
00119 ~PriorityQueue_Heap ()
00120 {
00121     delete [] m_queue;
00122 }
00123 
00124 template< class T, class Compare>
00125 void
00126 PriorityQueue_Heap<T, Compare>::
00127 insert (const T& t_)
00128 {
00129     if (m_curr+1 == m_size)  // if array filled up 
00130         resize (m_size*2); // then resize array
00131 
00132     m_queue [m_curr] = t_;
00133     upheap (m_curr);
00134     m_curr++;
00135 }
00136 
00137 template< class T, class Compare>
00138 void
00139 PriorityQueue_Heap<T, Compare>::
00140 upheap (size_t k_)
00141 {
00142     T v = m_queue[k_];
00143     m_queue[0] = 0;
00144 
00145     while ( k_/2 != 0 && m_comp (v, m_queue[k_/2]) ) {
00146         m_queue[k_] = m_queue[k_/2];
00147         k_ = k_/2;
00148     }
00149     m_queue[k_] = v;
00150 }
00151 
00152 template< class T, class Compare>
00153 T
00154 PriorityQueue_Heap<T, Compare>::
00155 pop ()
00156 {
00157     T v = m_queue[1];
00158     m_queue[1] = m_queue[--m_curr];
00159     
00160     downheap (1);
00161     if (m_curr*3 <= m_size && m_curr*2 > m_lwm) {
00162         resize (m_curr*2);
00163     }
00164     return v;
00165 }
00166 
00167 template< class T, class Compare>
00168 inline const T&
00169 PriorityQueue_Heap<T, Compare>::
00170 top () const
00171 {
00172     return (const T&) m_queue[1];
00173 }
00174 
00175 template< class T, class Compare>
00176 void
00177 PriorityQueue_Heap<T, Compare>::
00178 downheap (size_t k_)
00179 {
00180     register size_t j;
00181     T v = m_queue[k_];
00182 
00183     while (k_ <= m_curr/2) {
00184         j = 2*k_;
00185         if (j < m_curr && m_comp (m_queue[j+1], m_queue[j])) 
00186             j++;
00187         if (m_comp (v, m_queue[j])) 
00188             break;
00189         m_queue[k_] = m_queue[j];
00190         k_ = j;
00191     }
00192     m_queue[k_] = v;
00193 }
00194 
00195 template< class T, class Compare>
00196 bool
00197 PriorityQueue_Heap<T, Compare>::
00198 remove (T t_)
00199 {
00200     register size_t i;
00201 
00202     for (i=1; i < m_curr; i++) 
00203         if (m_queue[i] == t_)
00204             break;
00205 
00206     if (i == m_curr)    // not found
00207         return false;
00208 
00209     m_curr--;
00210     if (i == m_curr)    // last element in queue
00211         return true;
00212 
00213     m_queue[i] = m_queue[m_curr];
00214     downheap (i);
00215 
00216     return true;
00217 }
00218 
00219 template< class T, class Compare>
00220 inline size_t
00221 PriorityQueue_Heap<T, Compare>::
00222 size ()
00223 {
00224     return m_curr-1;
00225 }
00226 
00227 template< class T, class Compare>
00228 bool
00229 PriorityQueue_Heap<T, Compare>::
00230 resize (size_t newsz_)
00231 {
00232     if (m_size == newsz_)
00233         return true;
00234 
00235     T* new_chunk = new T[newsz_];
00236     ::memcpy (new_chunk, m_queue, m_curr * sizeof(T));
00237     delete [] m_queue;
00238     m_queue = new_chunk;
00239     m_size = newsz_;
00240     return true;
00241 }
00242 
00243 template< class T, class Compare>
00244 T&
00245 PriorityQueue_Heap<T, Compare>::
00246 operator[] (int idx)
00247 {
00248     return m_queue[idx+1];
00249 }
00250 
00251 } // end namespace ASSA
00252 
00253 #endif /* PRIORITY_QUEUE_HEAP_H */  

Generated on Sun Aug 13 15:08:00 2006 for libassa by  doxygen 1.4.6