vtf-logo

PriorityQueueCellArray.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // CONTINUE: add more documentation.
00004 
00010 #if !defined(__ads_PriorityQueueCellArray_h__)
00011 #define __ads_PriorityQueueCellArray_h__
00012 
00013 #include "PriorityQueue.h"
00014 
00015 #include "../array/Array.h"
00016 
00017 #include <vector>
00018 
00019 BEGIN_NAMESPACE_ADS
00020 
00022 
00036 template<typename T, 
00037          typename Key = typename std::iterator_traits<T>::value_type,
00038          class GetKey = Dereference<T>,
00039          class Container = std::vector<T> >
00040 class PriorityQueueCellArray :
00041   public PriorityQueue<T, Key> {
00042  private:
00043 
00044   //
00045   // private typedefs.
00046   //
00047 
00048   typedef PriorityQueue<T, Key> base_type;
00049   typedef GetKey get_key_functor;
00050 
00051  public:
00052 
00053   //
00054   // public typedefs.
00055   //
00056 
00058   typedef typename base_type::element_type element_type;
00060   typedef typename base_type::key_type key_type;
00062   typedef typename base_type::size_type size_type;
00063 
00065   typedef Container container_type;
00067   typedef const container_type& container_const_reference;
00069   typedef typename container_type::value_type value_type;
00071   typedef typename container_type::reference reference;
00073   typedef typename container_type::const_reference const_reference;
00075   typedef typename container_type::iterator iterator;
00077   typedef typename container_type::const_iterator const_iterator;
00078 
00079  private:
00080 
00081   // 
00082   // private typedefs
00083   //
00084 
00085   // The cell array.
00086   typedef Array< 1, container_type > cell_array_type;
00087   // An iterator over cells.
00088   typedef typename cell_array_type::iterator cell_iterator;
00089 
00090  private:
00091 
00092   //
00093   // Member data.
00094   //
00095 
00096   // The cell array.
00097   cell_array_type _array;
00098   // The top cell in the priority queue.
00099   cell_iterator _top;
00100   // The number of elements in the priority queue.
00101   size_type _size;
00102   // The minimum key that will be stored in the queue.
00103   key_type _min_key;
00104   // The span of a single cell.
00105   key_type _delta;
00106   // A lower bound on the keys stored in the top cell.
00107   key_type _lower_bound;
00108   // The number of cells.
00109   int _num_cells;
00110 
00111   // The functor to get the key from an element.
00112   get_key_functor _get_key;
00113 
00114 #ifdef DEBUG_PriorityQueueCellArray
00115   // The index of the top cell (non-cyclic).
00116   int _top_index;
00117 #endif
00118 
00119  public:
00120 
00121   //
00122   // Constructor and destructor.
00123   //
00124 
00126 
00132   PriorityQueueCellArray(key_type min_key, key_type delta, key_type span) :
00133     _array(int(span / delta) + 3),
00134     _top(_array.begin()),
00135     _size(0),
00136     // Adjust it down by delta, because we are not allowed to push into
00137     // the top cell.
00138     _min_key(min_key - delta),
00139     _delta(delta),
00140     _lower_bound(_min_key),
00141     _num_cells(_array.size()),
00142     _get_key()
00143 #ifdef DEBUG_PriorityQueueCellArray
00144                                                                             ,_top_index(0)
00145 #endif
00146   {}
00147 
00149   virtual
00150   ~PriorityQueueCellArray()
00151   {}
00152 
00153   //
00154   // Accessors
00155   //
00156 
00158   container_const_reference 
00159   top() const {
00160     return *_top;
00161   }
00162 
00164   size_type
00165   size() const {
00166     return _size;
00167   }
00168 
00170   bool
00171   empty() const {
00172     return _size == 0;
00173   }
00174 
00176   key_type
00177   lower_bound() const {
00178     return _lower_bound;
00179   }
00180 
00181   //
00182   // Manipulators
00183   //
00184 
00186   void 
00187   push(element_type x) {
00188     ++_size;
00189     _array[ index(_get_key(x)) ].push_back(x);
00190   }
00191 
00193   void 
00194   push(element_type x, key_type k) {
00195     ++_size;
00196     _array[ index(k) ].push_back(x);
00197   }
00198 
00200   void
00201   pop() {
00202     // Adjust the number of elements in the priority queue.
00203     _size -= _top->size();
00204     // Clear the container.
00205     _top->clear();
00206     // Increment the top iterator.
00207     ++_top;
00208     if (_top == _array.end()) {
00209       _top = _array.begin();
00210     }
00211     // Increment the lower bound on keys.
00212     _lower_bound += _delta;
00213 #ifdef DEBUG_PriorityQueueCellArray
00214     ++_top_index;
00215 #endif
00216   }
00217 
00218  private:
00219 
00220   //
00221   // Private member functions.
00222   //
00223 
00224   // Return the index of the appropriate cell.
00225   int
00226   index(key_type k) const {
00227 #ifdef DEBUG_PriorityQueueCellArray
00228     int index = int((k - _min_key) / _delta);
00229     assert(k >= _min_key + _delta && _top_index < index &&
00230             index < _top_index + _num_cells);
00231 #endif
00232     return int((k - _min_key) / _delta) % _num_cells;
00233   }
00234 
00235 };
00236 
00237 END_NAMESPACE_ADS
00238 
00239 #endif

Generated on Fri Aug 24 12:55:27 2007 for Algorithms and Data Structures Package by  doxygen 1.4.7