37 #ifndef VIGRA_PRIORITY_QUEUE_HXX
38 #define VIGRA_PRIORITY_QUEUE_HXX
42 #include "array_vector.hxx"
67 template <
class ValueType,
68 bool Ascending =
false>
77 typedef ValueType value_type;
78 typedef ValueType & reference;
79 typedef ValueType
const & const_reference;
80 typedef std::size_t size_type;
81 typedef std::ptrdiff_t priority_type;
87 : buckets_(bucket_count),
111 return (priority_type)buckets_.
size() - 1;
123 const_reference
top()
const
126 return buckets_[top_].
front();
134 buckets_[top_].pop();
136 while(top_ > 0 && buckets_[top_].
size() == 0)
142 void push(value_type
const & v, priority_type priority)
145 buckets_[priority].push(v);
152 template <
class ValueType>
153 class BucketQueue<ValueType, true>
155 ArrayVector<std::queue<ValueType> > buckets_;
161 typedef ValueType value_type;
162 typedef ValueType & reference;
163 typedef ValueType
const & const_reference;
164 typedef std::size_t size_type;
165 typedef std::ptrdiff_t priority_type;
168 : buckets_(bucket_count),
169 size_(0), top_((priority_type)bucket_count)
172 size_type
size()
const
184 return (priority_type)buckets_.
size() - 1;
192 const_reference
top()
const
195 return buckets_[top_].
front();
201 buckets_[top_].pop();
203 while(top_ < (priority_type)buckets_.
size() && buckets_[top_].
size() == 0)
207 void push(value_type
const & v, priority_type priority)
210 buckets_[priority].push(v);
229 template <
class ValueType,
230 class PriorityFunctor,
231 bool Ascending =
false>
235 PriorityFunctor get_priority_;
240 typedef typename BaseType::value_type value_type;
241 typedef typename BaseType::reference reference;
242 typedef typename BaseType::const_reference const_reference;
243 typedef typename BaseType::size_type size_type;
244 typedef typename BaseType::priority_type priority_type;
252 PriorityFunctor
const & priority = PriorityFunctor())
254 get_priority_(priority)
264 void push(value_type
const & v)
266 priority_type index = get_priority_(v);
287 template <
class ValueType,
289 bool Ascending =
false>
292 typedef std::pair<ValueType, PriorityType> ElementType;
296 typename IfBool<Ascending, std::greater<PriorityType>,
297 std::less<PriorityType> >::type cmp;
299 bool operator()(ElementType
const & l, ElementType
const & r)
const
301 return cmp(l.second, r.second);
305 typedef std::priority_queue<ElementType, std::vector<ElementType>, Compare> Heap;
311 typedef ValueType value_type;
312 typedef ValueType & reference;
313 typedef ValueType
const & const_reference;
314 typedef typename Heap::size_type size_type;
315 typedef PriorityType priority_type;
343 return NumericTraits<priority_type>::max();
350 return heap_.top().second;
355 const_reference
top()
const
358 return heap_.top().first;
370 void push(value_type
const & v, priority_type priority)
372 heap_.push(ElementType(v, priority));
376 template <
class ValueType,
378 class PriorityQueue<ValueType, unsigned char, Ascending>
379 :
public BucketQueue<ValueType, Ascending>
382 typedef BucketQueue<ValueType, Ascending> BaseType;
385 : BaseType(NumericTraits<unsigned char>::max()+1)
389 template <
class ValueType,
391 class PriorityQueue<ValueType, unsigned short, Ascending>
392 :
public BucketQueue<ValueType, Ascending>
395 typedef BucketQueue<ValueType, Ascending> BaseType;
398 : BaseType(NumericTraits<unsigned short>::max()+1)
412 template<
class T,
class COMPARE = std::less<T> >
418 typedef T priority_type;
419 typedef int ValueType;
420 typedef ValueType value_type;
421 typedef ValueType const_reference;
430 indices_(maxSize_+1, -1),
431 priorities_(maxSize_+1)
436 return currentSize_ == 0;
441 for(
int i = 0; i < currentSize_; i++)
443 indices_[heap_[i+1]] = -1;
451 return indices_[i] != -1;
466 void push(
const value_type i,
const priority_type p) {
469 indices_[i] = currentSize_;
470 heap_[currentSize_] = i;
472 bubbleUp(currentSize_);
481 const_reference
top()
const {
488 return priorities_[heap_[1]];
494 const int min = heap_[1];
495 swapItems(1, currentSize_--);
498 heap_[currentSize_+1] = -1;
503 return priorities_[i];
508 int ind = indices_[i];
509 swapItems(ind, currentSize_--);
519 if(_gt(p,priorities_[i])){
521 bubbleDown(indices_[i]);
523 else if(_lt(p,priorities_[i])) {
525 bubbleUp(indices_[i]);
531 void swapItems(
const int i,
const int j) {
532 std::swap(heap_[i],heap_[j]);
533 indices_[heap_[i]] = i;
534 indices_[heap_[j]] = j;
537 void bubbleUp(
int k) {
538 while(k > 1 && _gt( priorities_[heap_[k/2]],priorities_[heap_[k]])) {
544 void bubbleDown(
int k) {
546 while(2*k <= currentSize_) {
548 if(j < currentSize_ && _gt(priorities_[heap_[j]] , priorities_[heap_[j+1]]) )
550 if( _leqt(priorities_[heap_[k]] , priorities_[heap_[j]]))
558 bool _lt(
const T & a,
const T & b)
const{
561 bool _leqt(
const T & a,
const T & b)
const{
564 bool _eq(
const T & a,
const T & b)
const{
565 return !comp_(a,b) && !comp_(b,a);
567 bool _gt(
const T & a,
const T & b)
const{
568 return !_eq(a,b) && !comp_(a,b);
570 bool _geqt(
const T & a,
const T & b)
const{
577 std::vector<int> heap_;
578 std::vector<int> indices_;
579 std::vector<T> priorities_;
587 #endif // VIGRA_PRIORITY_QUEUE_HXX