PriorityQueue.h

Go to the documentation of this file.

/*
 * 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() {}
    };

    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:

        PriorityQueue() : AbstractQueue<E>(), _size( 0 ), capacity( 0 ), elements( NULL ), _comparator() {
            this->initQueue( DEFAULT_CAPACITY, new comparators::Less<E>() );
        }

        PriorityQueue( int initialCapacity ) :
            AbstractQueue<E>(), _size( 0 ), capacity( 0 ), elements( NULL ), _comparator() {

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

        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 );
        }

        PriorityQueue( const Collection<E>& source ) :
            AbstractQueue<E>(), _size( 0 ), capacity( 0 ), elements( NULL ), _comparator() {

            this->getFromCollection( source );
        }

        PriorityQueue( const PriorityQueue<E>& source ) :
            AbstractQueue<E>(), _size( 0 ), capacity( 0 ), elements( NULL ), _comparator() {

            this->getFromPriorityQueue( source );
        }

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

        PriorityQueue<E>& operator= ( const Collection<E>& source ) {
            this->getFromCollection( source );
            return *this;
        }

        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 )
        }

        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_ */