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