activemq-cpp-3.9.5
PriorityQueue.h
Go to the documentation of this file.
1/*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18#ifndef _DECAF_UTIL_PRIORITYQUEUE_H_
19#define _DECAF_UTIL_PRIORITYQUEUE_H_
20
21#include <decaf/util/Config.h>
24#include <decaf/util/Iterator.h>
27
28#include <decaf/lang/Math.h>
29#include <decaf/lang/Pointer.h>
32
33#include <memory>
34
35namespace decaf {
36namespace util {
37
39 protected:
40
41 static const int DEFAULT_CAPACITY;
42 static const int DEFAULT_CAPACITY_RATIO;
43
44 virtual ~PriorityQueueBase() {}
45 };
46
77 template< typename E >
78 class PriorityQueue : public AbstractQueue<E>, private PriorityQueueBase {
79 private:
80
81 int _size;
82 int capacity;
83 E* elements;
85
86 private:
87
88 class PriorityQueueIterator : public Iterator<E> {
89 private:
90
91 PriorityQueueIterator(const PriorityQueueIterator&);
92 PriorityQueueIterator& operator=(const PriorityQueueIterator&);
93
94 private:
95
96 int position;
97 bool allowRemove;
98 PriorityQueue* queue;
99
100 public:
101
102 PriorityQueueIterator( PriorityQueue* queue ) : position( 0 ), allowRemove( false ), queue( queue ) {}
103
104 virtual E next() {
105
106 if (!hasNext()) {
108 __FILE__, __LINE__, "No more elements to Iterate over.");
109 }
110
111 allowRemove = true;
112 return queue->elements[position++];
113 }
114
115 virtual bool hasNext() const {
116 return position < queue->_size;
117 }
118
119 virtual void remove() {
120
121 if (!allowRemove) {
123 __FILE__, __LINE__, "No more elements to Iterate over.");
124 }
125
126 allowRemove = false;
127 queue->removeAt(position--);
128 }
129 };
130
131 class ConstPriorityQueueIterator : public PriorityQueueIterator {
132 private:
133
134 ConstPriorityQueueIterator( const ConstPriorityQueueIterator& );
135 ConstPriorityQueueIterator& operator= ( const ConstPriorityQueueIterator& );
136
137 public:
138
139 ConstPriorityQueueIterator(const PriorityQueue* queue) :
140 PriorityQueueIterator(const_cast<PriorityQueue*>(queue)) {}
141
142 virtual void remove() {
144 __FILE__, __LINE__,
145 "PriorityQueue::Iterator::remove - Not Valid on a Const Iterator");
146 }
147 };
148
149 friend class PriorityQueueIterator;
150
151 public:
152
156 PriorityQueue() : AbstractQueue<E>(), _size(0), capacity(0), elements( NULL), _comparator() {
157 this->initQueue(DEFAULT_CAPACITY, new comparators::Less<E>());
158 }
159
166 PriorityQueue(int initialCapacity) :
167 AbstractQueue<E>(), _size(0), capacity(0), elements( NULL), _comparator() {
168
169 this->initQueue(initialCapacity, new comparators::Less<E>());
170 }
171
184 PriorityQueue(int initialCapacity, Comparator<E>* comparator) :
185 AbstractQueue<E>(), _size(0), capacity(0), elements( NULL), _comparator() {
186
187 if (comparator == NULL) {
189 __FILE__, __LINE__, "Passed Comparator Cannot be NULL.");
190 }
191
192 this->initQueue(initialCapacity, comparator);
193 }
194
202 AbstractQueue<E>(), _size(0), capacity(0), elements( NULL), _comparator() {
203
204 this->getFromCollection(source);
205 }
206
215 AbstractQueue<E>(), _size(0), capacity(0), elements( NULL), _comparator() {
216
217 this->getFromPriorityQueue(source);
218 }
219
220 virtual ~PriorityQueue() {
221 delete [] elements;
222 }
223
231 this->getFromCollection( source );
232 return *this;
233 }
234
242 this->getFromPriorityQueue( source );
243 return *this;
244 }
245
246 public:
247
249 return new PriorityQueueIterator(this);
250 }
251
253 return new ConstPriorityQueueIterator(this);
254 }
255
256 virtual int size() const {
257 return this->_size;
258 }
259
260 virtual void clear() {
261
262 // TODO - Provide a more efficient way to clear the array without reallocating it
263 // we should keep the size it grew to since if reused it could get that big
264 // again and reallocating all that memory could be to slow.
265
266 delete[] this->elements;
267
268 this->elements = new E[DEFAULT_CAPACITY];
269 this->capacity = DEFAULT_CAPACITY;
270 this->_size = 0;
271 }
272
273 virtual bool offer( const E& value ) {
274
275 // TODO - Check for Null and throw exception
276
277 increaseCapacity( _size + 1 );
278 elements[_size++] = value;
279 upHeap();
280 return true;
281 }
282
283 virtual bool poll(E& result) {
284
285 if (this->isEmpty()) {
286 return false;
287 }
288
289 result = elements[0];
290 removeAt(0);
291 return true;
292 }
293
294 virtual bool peek(E& result) const {
295
296 if (this->isEmpty()) {
297 return false;
298 }
299
300 result = elements[0];
301 return true;
302 }
303
304 virtual E remove() {
305
306 if (!this->isEmpty()) {
307 E result = elements[0];
308 removeAt(0);
309 return result;
310 }
311
313 __FILE__, __LINE__, "Unable to remove specified element from the Queue.");
314 }
315
316 virtual bool remove(const E& value) {
317
318 int targetIndex = 0;
319 for (targetIndex = 0; targetIndex < _size; targetIndex++) {
320 if (0 == _comparator->compare(value, elements[targetIndex])) {
321 break;
322 }
323 }
324
325 if (_size == 0 || _size == targetIndex) {
326 return false;
327 }
328
329 removeAt(targetIndex);
330 return true;
331 }
332
344
353 return this->_comparator;
354 }
355
356 private:
357
358 void initQueue(int initialSize, Comparator<E>* comparator) {
359 this->elements = new E[initialSize];
360 this->capacity = initialSize;
361 this->_size = 0;
362 this->_comparator.reset(comparator);
363 }
364
365 void upHeap() {
366
367 int current = _size - 1;
368 int parent = (current - 1) / 2;
369
370 while (current != 0 && _comparator->compare(elements[current], elements[parent]) < 0) {
371
372 // swap the two
373 E tmp = elements[current];
374 elements[current] = elements[parent];
375 elements[parent] = tmp;
376
377 // update parent and current positions.
378 current = parent;
379 parent = (current - 1) / 2;
380 }
381 }
382
383 void downHeap(int pos) {
384
385 int current = pos;
386 int child = 2 * current + 1;
387
388 while (child < _size && !this->isEmpty()) {
389
390 // compare the children if they exist
391 if (child + 1 < _size && _comparator->compare(elements[child + 1], elements[child]) < 0) {
392 child++;
393 }
394
395 // compare selected child with parent
396 if (_comparator->compare(elements[current], elements[child]) < 0) {
397 break;
398 }
399
400 // swap the two
401 E tmp = elements[current];
402 elements[current] = elements[child];
403 elements[child] = tmp;
404
405 // update child and current positions
406 current = child;
407 child = 2 * current + 1;
408 }
409 }
410
411 void getFromPriorityQueue(const PriorityQueue<E>& c) {
412 initCapacity(c);
413 _comparator = c.comparator();
414
415 for (int ix = 0; ix < c.size(); ++ix) {
416 this->elements[ix] = c.elements[ix];
417 }
418
419 _size = c.size();
420 }
421
422 void getFromCollection(const Collection<E>& c) {
423 initCapacity(c);
424 _comparator.reset(new comparators::Less<E>());
425 std::auto_ptr<Iterator<E> > iter(c.iterator());
426
427 while (iter->hasNext()) {
428 this->offer(iter->next());
429 }
430 }
431
432 void removeAt(int index) {
433 _size--;
434 elements[index] = elements[_size];
435 downHeap(index);
436 elements[_size] = E();
437 }
438
439 void initCapacity(const Collection<E>& c) {
440
441 delete[] elements;
442 _size = 0;
443
444 if (c.isEmpty()) {
445 capacity = 1;
446 elements = new E[capacity];
447 } else {
448 capacity = (int) lang::Math::ceil((double) c.size() * 1.1);
449 elements = new E[capacity];
450 }
451 }
452
453 void increaseCapacity(int size) {
454
455 if (size > capacity) {
456 E* newElements = new E[size * DEFAULT_CAPACITY_RATIO];
457
458 for (int ix = 0; ix < capacity; ix++) {
459 newElements[ix] = elements[ix];
460 }
461
462 delete[] elements;
463
464 elements = newElements;
465 capacity = size * DEFAULT_CAPACITY_RATIO;
466 }
467 }
468 };
469
470}}
471
472#endif /* _DECAF_UTIL_PRIORITYQUEUE_H_ */
static double ceil(double value)
Returns the natural logarithm (base e) of a double value.
Decaf's implementation of a Smart Pointer that is a template on a Type and is Thread Safe if the defa...
Definition Pointer.h:53
void reset(T *value=NULL)
Resets the Pointer to hold the new value.
Definition Pointer.h:161
Definition IllegalArgumentException.h:31
Definition IllegalStateException.h:32
Definition NullPointerException.h:32
Definition UnsupportedOperationException.h:32
virtual bool isEmpty() const
Returns true if this collection contains no elements.
Definition AbstractCollection.h:214
AbstractQueue()
Definition AbstractQueue.h:51
The root interface in the collection hierarchy.
Definition Collection.h:69
A comparison function, which imposes a total ordering on some collection of objects.
Definition Comparator.h:40
Defines an object that can be used to iterate over the elements of a collection.
Definition Iterator.h:34
Definition NoSuchElementException.h:31
Definition PriorityQueue.h:38
virtual ~PriorityQueueBase()
Definition PriorityQueue.h:44
static const int DEFAULT_CAPACITY
Definition PriorityQueue.h:41
static const int DEFAULT_CAPACITY_RATIO
Definition PriorityQueue.h:42
PriorityQueue(int initialCapacity, Comparator< E > *comparator)
Creates a Priority Queue with the default initial capacity.
Definition PriorityQueue.h:184
virtual bool remove(const E &value)
Removes a single instance of the specified element from the collection.
Definition PriorityQueue.h:316
virtual bool add(const E &value)
Returns true if this collection changed as a result of the call.(Returns false if this collection doe...
Definition PriorityQueue.h:333
PriorityQueue()
Creates a Priority Queue with the default initial capacity.
Definition PriorityQueue.h:156
PriorityQueue< E > & operator=(const Collection< E > &source)
Assignment operator, assign another Collection to this one.
Definition PriorityQueue.h:230
virtual int size() const
Returns the number of elements in this collection.
Definition PriorityQueue.h:256
virtual bool poll(E &result)
Gets and removes the element in the head of the queue.
Definition PriorityQueue.h:283
virtual bool offer(const E &value)
Inserts the specified element into the queue provided that the condition allows such an operation.
Definition PriorityQueue.h:273
PriorityQueue(int initialCapacity)
Creates a Priority Queue with the capacity value supplied.
Definition PriorityQueue.h:166
virtual E remove()
Gets and removes the element in the head of the queue.Throws a NoSuchElementException if there is no ...
Definition PriorityQueue.h:304
virtual ~PriorityQueue()
Definition PriorityQueue.h:220
PriorityQueue(const Collection< E > &source)
Creates a PriorityQueue containing the elements in the specified Collection.
Definition PriorityQueue.h:201
virtual decaf::util::Iterator< E > * iterator()
Definition PriorityQueue.h:248
virtual void clear()
Removes all of the elements from this collection (optional operation).This collection will be empty a...
Definition PriorityQueue.h:260
friend class PriorityQueueIterator
Definition PriorityQueue.h:149
PriorityQueue(const PriorityQueue< E > &source)
Creates a PriorityQueue containing the elements in the specified priority queue.
Definition PriorityQueue.h:214
virtual decaf::util::Iterator< E > * iterator() const
Definition PriorityQueue.h:252
virtual bool peek(E &result) const
Gets but not removes the element in the head of the queue.
Definition PriorityQueue.h:294
decaf::lang::Pointer< Comparator< E > > comparator() const
obtains a Copy of the Pointer instance that this PriorityQueue is using to compare the elements in th...
Definition PriorityQueue.h:352
Simple Less Comparator that compares to elements to determine if the first is less than the second.
Definition Less.h:39
#define DECAF_CATCH_EXCEPTION_CONVERT(sourceType, targetType)
Macro for catching an exception of one type and then rethrowing as another type.
Definition ExceptionDefines.h:39
#define DECAF_CATCH_RETHROW(type)
Macro for catching and rethrowing an exception of a given type.
Definition ExceptionDefines.h:27
#define DECAF_CATCHALL_THROW(type)
A catch-all that throws a known exception.
Definition ExceptionDefines.h:50
#define NULL
Definition Config.h:33
#define DECAF_API
Definition Config.h:29
Definition AbstractCollection.h:33
Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements.
Definition AprPool.h:25