[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]
vigra/bucket_queue.hxx | ![]() |
00001 /************************************************************************/ 00002 /* */ 00003 /* Copyright 2010-2011 by Ullrich Koethe */ 00004 /* */ 00005 /* This file is part of the VIGRA computer vision library. */ 00006 /* The VIGRA Website is */ 00007 /* http://hci.iwr.uni-heidelberg.de/vigra/ */ 00008 /* Please direct questions, bug reports, and contributions to */ 00009 /* ullrich.koethe@iwr.uni-heidelberg.de or */ 00010 /* vigra@informatik.uni-hamburg.de */ 00011 /* */ 00012 /* Permission is hereby granted, free of charge, to any person */ 00013 /* obtaining a copy of this software and associated documentation */ 00014 /* files (the "Software"), to deal in the Software without */ 00015 /* restriction, including without limitation the rights to use, */ 00016 /* copy, modify, merge, publish, distribute, sublicense, and/or */ 00017 /* sell copies of the Software, and to permit persons to whom the */ 00018 /* Software is furnished to do so, subject to the following */ 00019 /* conditions: */ 00020 /* */ 00021 /* The above copyright notice and this permission notice shall be */ 00022 /* included in all copies or substantial portions of the */ 00023 /* Software. */ 00024 /* */ 00025 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */ 00026 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */ 00027 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */ 00028 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */ 00029 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */ 00030 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ 00031 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */ 00032 /* OTHER DEALINGS IN THE SOFTWARE. */ 00033 /* */ 00034 /************************************************************************/ 00035 00036 00037 #ifndef VIGRA_BUCKET_QUEUE_HXX 00038 #define VIGRA_BUCKET_QUEUE_HXX 00039 00040 #include "config.hxx" 00041 #include "error.hxx" 00042 #include "array_vector.hxx" 00043 #include <queue> 00044 00045 namespace vigra { 00046 00047 /** \brief Priority queue implemented using bucket sort. 00048 00049 This template implements functionality similar to <tt><a href="http://www.sgi.com/tech/stl/priority_queue.html">std::priority_queue</a></tt>, 00050 but uses a more efficient algorithm based on bucket sort. It can be used 00051 when all priorities are positive integers in a given range (typically, 0...255). 00052 By default, <tt>BucketQueue<ValueType></tt> sorts the elements in descending order, 00053 i.e. like in <tt>std::priority_queue</tt> the largest element has highest priority. 00054 An ascending queue can be specified as <tt>BucketQueue<ValueType, true></tt>. 00055 Elements with equal priorities are returned in a first-in first-out fashion. 00056 00057 The main difference to <tt>std::priority_queue</tt> is the function <tt>push</tt> 00058 which explicitly takes the priority of the element to be added as a second argument. 00059 This allows optimization of <tt>ValueType</tt>: since the bucket uniquely 00060 determines an element's priority, there is no need for <tt>ValueType</tt> to 00061 store redundant priority information. If compatibility to <tt>std::priority_queue</tt> 00062 is more important, use \ref vigra::MappedBucketQueue. 00063 00064 <b>\#include</b> <vigra/bucket_queue.hxx><br> 00065 Namespace: vigra 00066 */ 00067 template <class ValueType, 00068 bool Ascending = false> // std::priority_queue is descending 00069 class BucketQueue 00070 { 00071 ArrayVector<std::queue<ValueType> > buckets_; 00072 std::size_t size_; 00073 std::ptrdiff_t top_; 00074 00075 public: 00076 00077 typedef ValueType value_type; 00078 typedef ValueType & reference; 00079 typedef ValueType const & const_reference; 00080 typedef std::size_t size_type; 00081 typedef std::ptrdiff_t priority_type; 00082 00083 /** \brief Create bucket queue with \arg bucket_count entries. 00084 Priorities must be integers in the range <tt>[0, ..., bucket_count-1]</tt>. 00085 */ 00086 BucketQueue(size_type bucket_count = 256) 00087 : buckets_(bucket_count), 00088 size_(0), top_(0) 00089 {} 00090 00091 /** \brief Number of elements in this queue. 00092 */ 00093 size_type size() const 00094 { 00095 return size_; 00096 } 00097 00098 /** \brief Queue contains no elements. 00099 Equivalent to <tt>size() == 0</tt>. 00100 */ 00101 bool empty() const 00102 { 00103 return size() == 0; 00104 } 00105 00106 /** \brief Maximum index (i.e. priority) allowed in this queue. 00107 Equivalent to <tt>bucket_count - 1</tt>. 00108 */ 00109 priority_type maxIndex() const 00110 { 00111 return (priority_type)buckets_.size() - 1; 00112 } 00113 00114 /** \brief Priority of the current top element. 00115 */ 00116 priority_type topPriority() const 00117 { 00118 return top_; 00119 } 00120 00121 /** \brief The current top element. 00122 */ 00123 const_reference top() const 00124 { 00125 00126 return buckets_[top_].front(); 00127 } 00128 00129 /** \brief Remove the current top element. 00130 */ 00131 void pop() 00132 { 00133 --size_; 00134 buckets_[top_].pop(); 00135 00136 while(top_ > 0 && buckets_[top_].size() == 0) 00137 --top_; 00138 } 00139 00140 /** \brief Insert new element \arg v with given \arg priority. 00141 */ 00142 void push(value_type const & v, priority_type priority) 00143 { 00144 ++size_; 00145 buckets_[priority].push(v); 00146 00147 if(priority > top_) 00148 top_ = priority; 00149 } 00150 }; 00151 00152 template <class ValueType> 00153 class BucketQueue<ValueType, true> // ascending queue 00154 { 00155 ArrayVector<std::queue<ValueType> > buckets_; 00156 std::size_t size_; 00157 std::ptrdiff_t top_; 00158 00159 public: 00160 00161 typedef ValueType value_type; 00162 typedef ValueType & reference; 00163 typedef ValueType const & const_reference; 00164 typedef std::size_t size_type; 00165 typedef std::ptrdiff_t priority_type; 00166 00167 BucketQueue(size_type bucket_count = 256) 00168 : buckets_(bucket_count), 00169 size_(0), top_((priority_type)bucket_count) 00170 {} 00171 00172 size_type size() const 00173 { 00174 return size_; 00175 } 00176 00177 bool empty() const 00178 { 00179 return size() == 0; 00180 } 00181 00182 priority_type maxIndex() const 00183 { 00184 return (priority_type)buckets_.size() - 1; 00185 } 00186 00187 priority_type topPriority() const 00188 { 00189 return top_; 00190 } 00191 00192 const_reference top() const 00193 { 00194 00195 return buckets_[top_].front(); 00196 } 00197 00198 void pop() 00199 { 00200 --size_; 00201 buckets_[top_].pop(); 00202 00203 while(top_ < (priority_type)buckets_.size() && buckets_[top_].size() == 0) 00204 ++top_; 00205 } 00206 00207 void push(value_type const & v, priority_type priority) 00208 { 00209 ++size_; 00210 buckets_[priority].push(v); 00211 00212 if(priority < top_) 00213 top_ = priority; 00214 } 00215 }; 00216 00217 /** \brief Priority queue implemented using bucket sort (STL compatible). 00218 00219 This template is compatible to <tt><a href="http://www.sgi.com/tech/stl/priority_queue.html">std::priority_queue</a></tt>, 00220 but uses a more efficient algorithm based on bucket sort. It us used 00221 like \ref vigra::BucketQueue, but has an additional <tt>PriorityFunctor</tt> 00222 which extracts the priority value of an element of type <tt>ValueType</tt>. 00223 Thus functor is called within <tt>push</tt> so that it does not need an 00224 extra argument. 00225 00226 <b>\#include</b> <vigra/bucket_queue.hxx><br> 00227 Namespace: vigra 00228 */ 00229 template <class ValueType, 00230 class PriorityFunctor, 00231 bool Ascending = false> 00232 class MappedBucketQueue 00233 : public BucketQueue<ValueType, Ascending> 00234 { 00235 PriorityFunctor get_priority_; 00236 00237 public: 00238 00239 typedef BucketQueue<ValueType, Ascending> BaseType; 00240 typedef typename BaseType::value_type value_type; 00241 typedef typename BaseType::reference reference; 00242 typedef typename BaseType::const_reference const_reference; 00243 typedef typename BaseType::size_type size_type; 00244 typedef typename BaseType::priority_type priority_type; 00245 00246 /** \brief Create a queue with \arg bucket_count entries. 00247 Priorities will be computed by the <tt>PriorityFunctor</tt> 00248 given in \arg priority (i.e. <tt>priority(v)</tt> must result in an integer, 00249 where <tt>v</tt> is an instance of <tt>ValueType</tt>). 00250 */ 00251 MappedBucketQueue(unsigned int bucket_count = 256, 00252 PriorityFunctor const & priority = PriorityFunctor()) 00253 : BaseType(bucket_count), 00254 get_priority_(priority) 00255 {} 00256 00257 /** \brief Insert new element \arg v. 00258 Its priority is calculated by <tt>priority(v)</tt>, 00259 where <tt>priority</tt> is an instance of the 00260 <tt>PriorityFunctor</tt> passed in the constructor. 00261 If the priority is outside the range <tt>[0, ..., bucket_count-1]</tt>, 00262 it is clamped to the range borders. 00263 */ 00264 void push(value_type const & v) 00265 { 00266 priority_type index = get_priority_(v); 00267 00268 // clamp index to the allowed range 00269 if(index > BaseType::maxIndex()) 00270 index = BaseType::maxIndex(); 00271 else if (index < 0) 00272 index = 0; 00273 00274 BaseType::push(v, index); 00275 } 00276 }; 00277 00278 } // namespace vigra 00279 00280 #endif // VIGRA_BUCKET_QUEUE_HXX
© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) |
html generated using doxygen and Python
|