37 #ifndef VIGRA_BUCKET_QUEUE_HXX
38 #define VIGRA_BUCKET_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)
404 #endif // VIGRA_BUCKET_QUEUE_HXX
bool empty() const
Queue contains no elements. Equivalent to size() == 0.
Definition: bucket_queue.hxx:333
priority_type maxIndex() const
Maximum index (i.e. priority) allowed in this queue. Equivalent to bucket_count - 1...
Definition: bucket_queue.hxx:109
Priority queue implemented using bucket sort.
Definition: bucket_queue.hxx:69
size_type size() const
Number of elements in this queue.
Definition: bucket_queue.hxx:93
Heap-based priority queue compatible to BucketQueue.
Definition: bucket_queue.hxx:290
void push(value_type const &v)
Insert new element.
Definition: bucket_queue.hxx:264
const_reference top() const
The current top element.
Definition: bucket_queue.hxx:123
priority_type topPriority() const
Priority of the current top element.
Definition: bucket_queue.hxx:348
BucketQueue(size_type bucket_count=256)
Create bucket queue with.
Definition: bucket_queue.hxx:86
MappedBucketQueue(unsigned int bucket_count=256, PriorityFunctor const &priority=PriorityFunctor())
Create a queue with.
Definition: bucket_queue.hxx:251
void pop()
Remove the current top element.
Definition: bucket_queue.hxx:363
void push(value_type const &v, priority_type priority)
Insert new element.
Definition: bucket_queue.hxx:142
PriorityQueue()
Create empty priority queue.
Definition: bucket_queue.hxx:319
Definition: array_vector.hxx:58
reference front()
Definition: array_vector.hxx:279
priority_type topPriority() const
Priority of the current top element.
Definition: bucket_queue.hxx:116
void pop()
Remove the current top element.
Definition: bucket_queue.hxx:131
Priority queue implemented using bucket sort (STL compatible).
Definition: bucket_queue.hxx:232
void push(value_type const &v, priority_type priority)
Insert new element.
Definition: bucket_queue.hxx:370
bool empty() const
Queue contains no elements. Equivalent to size() == 0.
Definition: bucket_queue.hxx:101
const_reference top() const
The current top element.
Definition: bucket_queue.hxx:355
priority_type maxIndex() const
Maximum index (i.e. priority) allowed in this queue. Equivalent to bucket_count - 1...
Definition: bucket_queue.hxx:341
size_type size() const
Definition: array_vector.hxx:330
size_type size() const
Number of elements in this queue.
Definition: bucket_queue.hxx:325