18#ifndef _DECAF_UTIL_PRIORITYQUEUE_H_
19#define _DECAF_UTIL_PRIORITYQUEUE_H_
77 template<
typename E >
88 class PriorityQueueIterator :
public Iterator<E> {
92 PriorityQueueIterator&
operator=(
const PriorityQueueIterator&);
108 __FILE__, __LINE__,
"No more elements to Iterate over.");
112 return queue->elements[position++];
115 virtual bool hasNext()
const {
116 return position < queue->_size;
123 __FILE__, __LINE__,
"No more elements to Iterate over.");
127 queue->removeAt(position--);
131 class ConstPriorityQueueIterator :
public PriorityQueueIterator {
134 ConstPriorityQueueIterator(
const ConstPriorityQueueIterator& );
135 ConstPriorityQueueIterator& operator= (
const ConstPriorityQueueIterator& );
145 "PriorityQueue::Iterator::remove - Not Valid on a Const Iterator");
149 friend class PriorityQueueIterator;
189 __FILE__, __LINE__,
"Passed Comparator Cannot be NULL.");
204 this->getFromCollection(source);
217 this->getFromPriorityQueue(source);
231 this->getFromCollection( source );
242 this->getFromPriorityQueue( source );
253 return new ConstPriorityQueueIterator(
this);
266 delete[] this->elements;
273 virtual bool offer(
const E& value ) {
277 increaseCapacity( _size + 1 );
278 elements[_size++] = value;
289 result = elements[0];
294 virtual bool peek(E& result)
const {
300 result = elements[0];
307 E result = elements[0];
313 __FILE__, __LINE__,
"Unable to remove specified element from the Queue.");
319 for (targetIndex = 0; targetIndex < _size; targetIndex++) {
320 if (0 == _comparator->compare(value, elements[targetIndex])) {
325 if (_size == 0 || _size == targetIndex) {
329 removeAt(targetIndex);
333 virtual bool add(
const E& value) {
353 return this->_comparator;
359 this->elements =
new E[initialSize];
360 this->capacity = initialSize;
367 int current = _size - 1;
368 int parent = (current - 1) / 2;
370 while (current != 0 && _comparator->compare(elements[current], elements[parent]) < 0) {
373 E tmp = elements[current];
374 elements[current] = elements[parent];
375 elements[parent] = tmp;
379 parent = (current - 1) / 2;
383 void downHeap(
int pos) {
386 int child = 2 * current + 1;
388 while (child < _size && !this->
isEmpty()) {
391 if (child + 1 < _size && _comparator->compare(elements[child + 1], elements[child]) < 0) {
396 if (_comparator->compare(elements[current], elements[child]) < 0) {
401 E tmp = elements[current];
402 elements[current] = elements[child];
403 elements[child] = tmp;
407 child = 2 * current + 1;
413 _comparator = c.comparator();
415 for (
int ix = 0; ix < c.size(); ++ix) {
416 this->elements[ix] = c.elements[ix];
422 void getFromCollection(
const Collection<E>& c) {
424 _comparator.reset(
new comparators::Less<E>());
425 std::auto_ptr<Iterator<E> > iter(c.iterator());
427 while (iter->hasNext()) {
428 this->
offer(iter->next());
432 void removeAt(
int index) {
434 elements[index] = elements[_size];
436 elements[_size] = E();
439 void initCapacity(
const Collection<E>& c) {
446 elements =
new E[capacity];
449 elements =
new E[capacity];
453 void increaseCapacity(
int size) {
455 if (
size > capacity) {
458 for (
int ix = 0; ix < capacity; ix++) {
459 newElements[ix] = elements[ix];
464 elements = newElements;
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