[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

vigra/bucket_queue.hxx VIGRA

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)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
vigra 1.8.0 (20 Sep 2011)