[ 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 /** \brief Heap-based priority queue compatible to BucketQueue.
    00279
    00280     This template is compatible to \ref vigra::BucketQueue, but except arbitrary priority
    00281     types. Internally, it uses a <tt>std::priority_queue</tt>, but implements an
    00282     API where priorities and payload data are separate, like in \ref vigra::BucketQueue.
    00283
    00284     <b>\#include</b> <vigra/bucket_queue.hxx><br>
    00285     Namespace: vigra
    00286 */
    00287 template <class ValueType,
    00288           class PriorityType,
    00289           bool Ascending = false>  // std::priority_queue is descending
    00290 class PriorityQueue
    00291 {
    00292     typedef std::pair<ValueType, PriorityType> ElementType;
    00293
    00294     struct Compare
    00295     {
    00296         typename IfBool<Ascending, std::greater<PriorityType>,
    00297                                    std::less<PriorityType> >::type cmp;
    00298
    00299         bool operator()(ElementType const & l, ElementType const & r) const
    00300         {
    00301             return cmp(l.second, r.second);
    00302         }
    00303     };
    00304
    00305     typedef std::priority_queue<ElementType, std::vector<ElementType>, Compare> Heap;
    00306
    00307     Heap heap_;
    00308
    00309   public:
    00310
    00311     typedef ValueType value_type;
    00312     typedef ValueType & reference;
    00313     typedef ValueType const & const_reference;
    00314     typedef typename Heap::size_type size_type;
    00315     typedef PriorityType priority_type;
    00316
    00317         /** \brief Create empty priority queue.
    00318         */
    00319     PriorityQueue()
    00320     : heap_()
    00321     {}
    00322
    00323         /** \brief Number of elements in this queue.
    00324         */
    00325     size_type size() const
    00326     {
    00327         return heap_.size();
    00328     }
    00329
    00330         /** \brief Queue contains no elements.
    00331              Equivalent to <tt>size() == 0</tt>.
    00332         */
    00333     bool empty() const
    00334     {
    00335         return size() == 0;
    00336     }
    00337
    00338         /** \brief Maximum index (i.e. priority) allowed in this queue.
    00339              Equivalent to <tt>bucket_count - 1</tt>.
    00340         */
    00341     priority_type maxIndex() const
    00342     {
    00343         return NumericTraits<priority_type>::max();
    00344     }
    00345
    00346         /** \brief Priority of the current top element.
    00347         */
    00348     priority_type topPriority() const
    00349     {
    00350         return heap_.top().second;
    00351     }
    00352
    00353         /** \brief The current top element.
    00354         */
    00355     const_reference top() const
    00356     {
    00357
    00358         return heap_.top().first;
    00359     }
    00360
    00361         /** \brief Remove the current top element.
    00362         */
    00363     void pop()
    00364     {
    00365         heap_.pop();
    00366     }
    00367
    00368         /** \brief Insert new element \arg v with given \arg priority.
    00369         */
    00370     void push(value_type const & v, priority_type priority)
    00371     {
    00372         heap_.push(ElementType(v, priority));
    00373     }
    00374 };
    00375
    00376 } // namespace vigra
    00377
    00378 #endif // VIGRA_BUCKET_QUEUE_HXX

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany | html generated using doxygen and Python vigra 1.9.0 (Tue Nov 6 2012)