activemq-cpp/src/main/decaf/util/PriorityQueue.h

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef _DECAF_UTIL_PRIORITYQUEUE_H_
#define _DECAF_UTIL_PRIORITYQUEUE_H_

#include <decaf/util/Config.h>
#include <decaf/util/Collection.h>
#include <decaf/util/AbstractQueue.h>
#include <decaf/util/Iterator.h>
#include <decaf/util/Comparator.h>
#include <decaf/util/comparators/Less.h>

#include <decaf/lang/Math.h>
#include <decaf/lang/Pointer.h>
#include <decaf/lang/exceptions/NullPointerException.h>
#include <decaf/lang/exceptions/UnsupportedOperationException.h>

#include <memory>

namespace decaf {
namespace util {

    class DECAF_API PriorityQueueBase {
    protected:

        static const int DEFAULT_CAPACITY;
        static const int DEFAULT_CAPACITY_RATIO;

        virtual ~PriorityQueueBase() {}
    };

    /**
     * An unbounded priority queue based on a binary heap algorithm. The elements of the priority queue
     * are ordered according to their natural ordering, or by a Comparator provided to one of the constructors
     * that accepts Comparators.  A priority queue relying on natural ordering also does not permit insertion
     * of non-comparable objects (doing so may result in a compiler error).
     *
     * The head of this queue is the least element with respect to the specified ordering. If multiple
     * elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily.
     * The queue retrieval operations poll, remove, peek, and element access the element at the head of
     * the queue.
     *
     * A priority queue is unbounded, but has an internal capacity governing the size of an array used to store
     * the elements on the queue. It is always at least as large as the queue size. As elements are added to
     * a priority queue, its capacity grows automatically. The details of the growth policy are not specified.
     *
     * This class and its iterator implement all of the optional methods of the Collection and Iterator
     * interfaces.  The Iterator provided in method iterator() is not guaranteed to traverse the elements of
     * the priority queue in any particular order. If you need ordered traversal, consider using
     * <code>Arrays::sort( pq.toArray() )</code>.
     *
     * Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue
     * instance concurrently if any of the threads modifies the queue. Instead, use the thread-safe
     * PriorityBlockingQueue class.
     *
     * Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods
     * (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods;
     * and constant time for the retrieval methods (peek, element, and size).
     *
     * @since 1.0
     */
    template< typename E >
    class PriorityQueue : public AbstractQueue<E>, private PriorityQueueBase {
    private:

        int _size;
        int capacity;
        E* elements;
        decaf::lang::Pointer< Comparator<E> > _comparator;

    private:

        class PriorityQueueIterator : public Iterator<E> {
        private:

            PriorityQueueIterator(const PriorityQueueIterator&);
            PriorityQueueIterator& operator=(const PriorityQueueIterator&);

        private:

            int position;
            bool allowRemove;
            PriorityQueue* queue;

        public:

            PriorityQueueIterator( PriorityQueue* queue ) : position( 0 ), allowRemove( false ), queue( queue ) {}

            virtual E next() {

                if (!hasNext()) {
                    throw NoSuchElementException(
                        __FILE__, __LINE__, "No more elements to Iterate over.");
                }

                allowRemove = true;
                return queue->elements[position++];
            }

            virtual bool hasNext() const {
                return position < queue->_size;
            }

            virtual void remove() {

                if (!allowRemove) {
                    throw lang::exceptions::IllegalStateException(
                        __FILE__, __LINE__, "No more elements to Iterate over.");
                }

                allowRemove = false;
                queue->removeAt(position--);
            }
        };

        class ConstPriorityQueueIterator : public PriorityQueueIterator {
        private:

            ConstPriorityQueueIterator( const ConstPriorityQueueIterator& );
            ConstPriorityQueueIterator& operator= ( const ConstPriorityQueueIterator& );

        public:

            ConstPriorityQueueIterator(const PriorityQueue* queue) :
                PriorityQueueIterator(const_cast<PriorityQueue*>(queue)) {}

            virtual void remove() {
                throw lang::exceptions::UnsupportedOperationException(
                    __FILE__, __LINE__,
                    "PriorityQueue::Iterator::remove - Not Valid on a Const Iterator");
            }
        };

        friend class PriorityQueueIterator;

    public:

        /**
         * Creates a Priority Queue with the default initial capacity.
         */
        PriorityQueue() : AbstractQueue<E>(), _size(0), capacity(0), elements( NULL), _comparator() {
            this->initQueue(DEFAULT_CAPACITY, new comparators::Less<E>());
        }

        /**
         * Creates a Priority Queue with the capacity value supplied.
         *
         * @param initialCapacity
         *      The initial number of elements allocated to this PriorityQueue.
         */
        PriorityQueue(int initialCapacity) :
            AbstractQueue<E>(), _size(0), capacity(0), elements( NULL), _comparator() {

            this->initQueue(initialCapacity, new comparators::Less<E>());
        }

        /**
         * Creates a Priority Queue with the default initial capacity.  This new PriorityQueue takes
         * ownership of the passed Comparator instance and uses that to determine the ordering of the
         * elements in the Queue.
         *
         * @param initialCapacity
         *      The initial number of elements allocated to this PriorityQueue.
         * @param comparator
         *      The Comparator instance to use in sorting the elements in the Queue.
         *
         * @throws NullPointerException if the passed Comparator is NULL.
         */
        PriorityQueue(int initialCapacity, Comparator<E>* comparator) :
            AbstractQueue<E>(), _size(0), capacity(0), elements( NULL), _comparator() {

            if (comparator == NULL) {
                throw decaf::lang::exceptions::NullPointerException(
                    __FILE__, __LINE__, "Passed Comparator Cannot be NULL.");
            }

            this->initQueue(initialCapacity, comparator);
        }

        /**
         * Creates a PriorityQueue containing the elements in the specified Collection.
         *
         * @param source
         *      the Collection whose elements are to be placed into this priority queue
         */
        PriorityQueue(const Collection<E>& source) :
            AbstractQueue<E>(), _size(0), capacity(0), elements( NULL), _comparator() {

            this->getFromCollection(source);
        }

        /**
         * Creates a PriorityQueue containing the elements in the specified priority queue. This priority
         * queue will be ordered according to the same ordering as the given priority queue.
         *
         * @param source
         *      the priority queue whose elements are to be placed into this priority queue
         */
        PriorityQueue(const PriorityQueue<E>& source) :
            AbstractQueue<E>(), _size(0), capacity(0), elements( NULL), _comparator() {

            this->getFromPriorityQueue(source);
        }

        virtual ~PriorityQueue() {
            delete [] elements;
        }

        /**
         * Assignment operator, assign another Collection to this one.
         *
         * @param source
         *        The Collection to copy to this one.
         */
        PriorityQueue<E>& operator= ( const Collection<E>& source ) {
            this->getFromCollection( source );
            return *this;
        }

        /**
         * Assignment operator, assign another PriorityQueue to this one.
         *
         * @param source
         *        The PriorityQueue to copy to this one.
         */
        PriorityQueue<E>& operator= ( const PriorityQueue<E>& source ) {
            this->getFromPriorityQueue( source );
            return *this;
        }

    public:

        virtual decaf::util::Iterator<E>* iterator() {
            return new PriorityQueueIterator(this);
        }

        virtual decaf::util::Iterator<E>* iterator() const {
            return new ConstPriorityQueueIterator(this);
        }

        virtual int size() const {
            return this->_size;
        }

        virtual void clear() {

            // TODO - Provide a more efficient way to clear the array without reallocating it
            //        we should keep the size it grew to since if reused it could get that big
            //        again and reallocating all that memory could be to slow.

            delete[] this->elements;

            this->elements = new E[DEFAULT_CAPACITY];
            this->capacity = DEFAULT_CAPACITY;
            this->_size = 0;
        }

        virtual bool offer( const E& value ) {

            // TODO - Check for Null and throw exception

            increaseCapacity( _size + 1 );
            elements[_size++] = value;
            upHeap();
            return true;
        }

        virtual bool poll(E& result) {

            if (this->isEmpty()) {
                return false;
            }

            result = elements[0];
            removeAt(0);
            return true;
        }

        virtual bool peek(E& result) const {

            if (this->isEmpty()) {
                return false;
            }

            result = elements[0];
            return true;
        }

        virtual E remove() {

            if (!this->isEmpty()) {
                E result = elements[0];
                removeAt(0);
                return result;
            }

            throw decaf::util::NoSuchElementException(
                __FILE__, __LINE__, "Unable to remove specified element from the Queue.");
        }

        virtual bool remove(const E& value) {

            int targetIndex = 0;
            for (targetIndex = 0; targetIndex < _size; targetIndex++) {
                if (0 == _comparator->compare(value, elements[targetIndex])) {
                    break;
                }
            }

            if (_size == 0 || _size == targetIndex) {
                return false;
            }

            removeAt(targetIndex);
            return true;
        }

        virtual bool add(const E& value) {

            try {
                return offer(value);
            }
            DECAF_CATCH_RETHROW(lang::exceptions::UnsupportedOperationException)
            DECAF_CATCH_RETHROW(lang::exceptions::IllegalArgumentException)
            DECAF_CATCH_RETHROW(lang::exceptions::IllegalStateException)
            DECAF_CATCH_EXCEPTION_CONVERT(lang::exceptions::NullPointerException, lang::exceptions::UnsupportedOperationException)
            DECAF_CATCHALL_THROW(lang::exceptions::UnsupportedOperationException)
        }

        /**
         * obtains a Copy of the Pointer instance that this PriorityQueue is using to compare the
         * elements in the queue with.  The returned value is a copy, the caller cannot change the
         * value if the internal Pointer value.
         *
         * @return a copy of the Comparator Pointer being used by this Queue.
         */
        decaf::lang::Pointer<Comparator<E> > comparator() const {
            return this->_comparator;
        }

    private:

        void initQueue(int initialSize, Comparator<E>* comparator) {
            this->elements = new E[initialSize];
            this->capacity = initialSize;
            this->_size = 0;
            this->_comparator.reset(comparator);
        }

        void upHeap() {

            int current = _size - 1;
            int parent = (current - 1) / 2;

            while (current != 0 && _comparator->compare(elements[current], elements[parent]) < 0) {

                // swap the two
                E tmp = elements[current];
                elements[current] = elements[parent];
                elements[parent] = tmp;

                // update parent and current positions.
                current = parent;
                parent = (current - 1) / 2;
            }
        }

        void downHeap(int pos) {

            int current = pos;
            int child = 2 * current + 1;

            while (child < _size && !this->isEmpty()) {

                // compare the children if they exist
                if (child + 1 < _size && _comparator->compare(elements[child + 1], elements[child]) < 0) {
                    child++;
                }

                // compare selected child with parent
                if (_comparator->compare(elements[current], elements[child]) < 0) {
                    break;
                }

                // swap the two
                E tmp = elements[current];
                elements[current] = elements[child];
                elements[child] = tmp;

                // update child and current positions
                current = child;
                child = 2 * current + 1;
            }
        }

        void getFromPriorityQueue(const PriorityQueue<E>& c) {
            initCapacity(c);
            _comparator = c.comparator();

            for (int ix = 0; ix < c.size(); ++ix) {
                this->elements[ix] = c.elements[ix];
            }

            _size = c.size();
        }

        void getFromCollection(const Collection<E>& c) {
            initCapacity(c);
            _comparator.reset(new comparators::Less<E>());
            std::auto_ptr<Iterator<E> > iter(c.iterator());

            while (iter->hasNext()) {
                this->offer(iter->next());
            }
        }

        void removeAt(int index) {
            _size--;
            elements[index] = elements[_size];
            downHeap(index);
            elements[_size] = E();
        }

        void initCapacity(const Collection<E>& c) {

            delete[] elements;
            _size = 0;

            if (c.isEmpty()) {
                capacity = 1;
                elements = new E[capacity];
            } else {
                capacity = (int) lang::Math::ceil((double) c.size() * 1.1);
                elements = new E[capacity];
            }
        }

        void increaseCapacity(int size) {

            if (size > capacity) {
                E* newElements = new E[size * DEFAULT_CAPACITY_RATIO];

                for (int ix = 0; ix < capacity; ix++) {
                    newElements[ix] = elements[ix];
                }

                delete[] elements;

                elements = newElements;
                capacity = size * DEFAULT_CAPACITY_RATIO;
            }
        }
    };

}}

#endif /* _DECAF_UTIL_PRIORITYQUEUE_H_ */