/*

 * Copyright 2003-2006 Sun Microsystems, Inc.  All Rights Reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Sun designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Sun in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 */

package java.util;

/**

 * An unbounded priority {@linkplain Queue queue} based on a priority heap.

 * The elements of the priority queue are ordered according to their

 * {@linkplain Comparable natural ordering}, or by a {@link Comparator}

 * provided at queue construction time, depending on which constructor is

 * used.  A priority queue does not permit {@code null} elements.

 * A priority queue relying on natural ordering also does not permit

 * insertion of non-comparable objects (doing so may result in

 * {@code ClassCastException}).

 *

 * <p>The <em>head</em> of this queue is the <em>least</em> 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 {@code poll},

 * {@code remove}, {@code peek}, and {@code element} access the

 * element at the head of the queue.

 *

 * <p>A priority queue is unbounded, but has an internal

 * <i>capacity</i> 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.

 *

 * <p>This class and its iterator implement all of the

 * <em>optional</em> methods of the {@link Collection} and {@link

 * Iterator} interfaces.  The Iterator provided in method {@link

 * #iterator()} is <em>not</em> 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())}.

 *

 * <p> <strong>Note that this implementation is not synchronized.</strong>

 * Multiple threads should not access a {@code PriorityQueue}

 * instance concurrently if any of the threads modifies the queue.

 * Instead, use the thread-safe {@link

 * java.util.concurrent.PriorityBlockingQueue} class.

 *

 * <p>Implementation note: this implementation provides

 * O(log(n)) time for the enqueing and dequeing methods

 * ({@code offer}, {@code poll}, {@code remove()} and {@code add});

 * linear time for the {@code remove(Object)} and {@code contains(Object)}

 * methods; and constant time for the retrieval methods

 * ({@code peek}, {@code element}, and {@code size}).

 *

 * <p>This class is a member of the

 * <a href="{@docRoot}/../technotes/guides/collections/index.html">

 * Java Collections Framework</a>.

 *

 * @since 1.5

 * @author Josh Bloch, Doug Lea

 * @param <E> the type of elements held in this collection

 */

public class PriorityQueue<E> extends AbstractQueue<E>

    implements java.io.Serializable {

    private static final long serialVersionUID = -7720805057305804111L;

    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    /**

     * Priority queue represented as a balanced binary heap: the two

     * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The

     * priority queue is ordered by comparator, or by the elements'

     * natural ordering, if comparator is null: For each node n in the

     * heap and each descendant d of n, n <= d.  The element with the

     * lowest value is in queue[0], assuming the queue is nonempty.

     */

    private transient Object[] queue;

    /**

     * The number of elements in the priority queue.

     */

    private int size = 0;

    /**

     * The comparator, or null if priority queue uses elements'

     * natural ordering.

     */

    private final Comparator<? super E> comparator;

    /**

     * The number of times this priority queue has been

     * <i>structurally modified</i>.  See AbstractList for gory details.

     */

    private transient int modCount = 0;

    /**

     * Creates a {@code PriorityQueue} with the default initial

     * capacity (11) that orders its elements according to their

     * {@linkplain Comparable natural ordering}.

     */

    public PriorityQueue() {

        this(DEFAULT_INITIAL_CAPACITY, null);

    }

    /**

     * Creates a {@code PriorityQueue} with the specified initial

     * capacity that orders its elements according to their

     * {@linkplain Comparable natural ordering}.

     *

     * @param initialCapacity the initial capacity for this priority queue

     * @throws IllegalArgumentException if {@code initialCapacity} is less

     *         than 1

     */

    public PriorityQueue(int initialCapacity) {

        this(initialCapacity, null);

    }

    /**

     * Creates a {@code PriorityQueue} with the specified initial capacity

     * that orders its elements according to the specified comparator.

     *

     * @param  initialCapacity the initial capacity for this priority queue

     * @param  comparator the comparator that will be used to order this

     *         priority queue.  If {@code null}, the {@linkplain Comparable

     *         natural ordering} of the elements will be used.

     * @throws IllegalArgumentException if {@code initialCapacity} is

     *         less than 1

     */

    public PriorityQueue(int initialCapacity,

                         Comparator<? super E> comparator) {

        // Note: This restriction of at least one is not actually needed,

        // but continues for 1.5 compatibility

        if (initialCapacity < 1)

            throw new IllegalArgumentException();

        this.queue = new Object[initialCapacity];

        this.comparator = comparator;

    }

    /**

     * Creates a {@code PriorityQueue} containing the elements in the

     * specified collection.  If the specified collection is an instance of

     * a {@link SortedSet} or is another {@code PriorityQueue}, this

     * priority queue will be ordered according to the same ordering.

     * Otherwise, this priority queue will be ordered according to the

     * {@linkplain Comparable natural ordering} of its elements.

     *

     * @param  c the collection whose elements are to be placed

     *         into this priority queue

     * @throws ClassCastException if elements of the specified collection

     *         cannot be compared to one another according to the priority

     *         queue's ordering

     * @throws NullPointerException if the specified collection or any

     *         of its elements are null

     */

    public PriorityQueue(Collection<? extends E> c) {

        initFromCollection(c);

        if (c instanceof SortedSet)

            comparator = (Comparator<? super E>)

                ((SortedSet<? extends E>)c).comparator();

        else if (c instanceof PriorityQueue)

            comparator = (Comparator<? super E>)

                ((PriorityQueue<? extends E>)c).comparator();

        else {

            comparator = null;

            heapify();

        }

    }

    /**

     * Creates a {@code 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  c the priority queue whose elements are to be placed

     *         into this priority queue

     * @throws ClassCastException if elements of {@code c} cannot be

     *         compared to one another according to {@code c}'s

     *         ordering

     * @throws NullPointerException if the specified priority queue or any

     *         of its elements are null

     */

    public PriorityQueue(PriorityQueue<? extends E> c) {

        comparator = (Comparator<? super E>)c.comparator();

        initFromCollection(c);

    }

    /**

     * Creates a {@code PriorityQueue} containing the elements in the

     * specified sorted set.   This priority queue will be ordered

     * according to the same ordering as the given sorted set.

     *

     * @param  c the sorted set whose elements are to be placed

     *         into this priority queue

     * @throws ClassCastException if elements of the specified sorted

     *         set cannot be compared to one another according to the

     *         sorted set's ordering

     * @throws NullPointerException if the specified sorted set or any

     *         of its elements are null

     */

    public PriorityQueue(SortedSet<? extends E> c) {

        comparator = (Comparator<? super E>)c.comparator();

        initFromCollection(c);

    }

    /**

     * Initializes queue array with elements from the given Collection.

     *

     * @param c the collection

     */

    private void initFromCollection(Collection<? extends E> c) {

        Object[] a = c.toArray();

        // If c.toArray incorrectly doesn't return Object[], copy it.

        if (a.getClass() != Object[].class)

            a = Arrays.copyOf(a, a.length, Object[].class);

        queue = a;

        size = a.length;

    }

    /**

     * Increases the capacity of the array.

     *

     * @param minCapacity the desired minimum capacity

     */

    private void grow(int minCapacity) {

        if (minCapacity < 0) // overflow

            throw new OutOfMemoryError();

        int oldCapacity = queue.length;

        // Double size if small; else grow by 50%

        int newCapacity = ((oldCapacity < 64)?

                           ((oldCapacity + 1) * 2):

                           ((oldCapacity / 2) * 3));

        if (newCapacity < 0) // overflow

            newCapacity = Integer.MAX_VALUE;

        if (newCapacity < minCapacity)

            newCapacity = minCapacity;

        queue = Arrays.copyOf(queue, newCapacity);

    }

    /**

     * Inserts the specified element into this priority queue.

     *

     * @return {@code true} (as specified by {@link Collection#add})

     * @throws ClassCastException if the specified element cannot be

     *         compared with elements currently in this priority queue

     *         according to the priority queue's ordering

     * @throws NullPointerException if the specified element is null

     */

    public boolean add(E e) {

        return offer(e);

    }

    /**

     * Inserts the specified element into this priority queue.

     *

     * @return {@code true} (as specified by {@link Queue#offer})

     * @throws ClassCastException if the specified element cannot be

     *         compared with elements currently in this priority queue

     *         according to the priority queue's ordering

     * @throws NullPointerException if the specified element is null

     */

    public boolean offer(E e) {

        if (e == null)

            throw new NullPointerException();

        modCount++;

        int i = size;

        if (i >= queue.length)

            grow(i + 1);

        size = i + 1;

        if (i == 0)

            queue[0] = e;

        else

            siftUp(i, e);

        return true;

    }

    public E peek() {

        if (size == 0)

            return null;

        return (E) queue[0];

    }

    private int indexOf(Object o) {

        if (o != null) {

            for (int i = 0; i < size; i++)

                if (o.equals(queue[i]))

                    return i;

        }

        return -1;

    }

    /**

     * Removes a single instance of the specified element from this queue,

     * if it is present.  More formally, removes an element {@code e} such

     * that {@code o.equals(e)}, if this queue contains one or more such

     * elements.  Returns {@code true} if and only if this queue contained

     * the specified element (or equivalently, if this queue changed as a

     * result of the call).

     *

     * @param o element to be removed from this queue, if present

     * @return {@code true} if this queue changed as a result of the call

     */

    public boolean remove(Object o) {

        int i = indexOf(o);

        if (i == -1)

            return false;

        else {

            removeAt(i);

            return true;

        }

    }

    /**

     * Version of remove using reference equality, not equals.

     * Needed by iterator.remove.

     *

     * @param o element to be removed from this queue, if present

     * @return {@code true} if removed

     */

    boolean removeEq(Object o) {

        for (int i = 0; i < size; i++) {

            if (o == queue[i]) {

                removeAt(i);

                return true;

            }

        }

        return false;

    }

    /**

     * Returns {@code true} if this queue contains the specified element.

     * More formally, returns {@code true} if and only if this queue contains

     * at least one element {@code e} such that {@code o.equals(e)}.

     *

     * @param o object to be checked for containment in this queue

     * @return {@code true} if this queue contains the specified element

     */

    public boolean contains(Object o) {

        return indexOf(o) != -1;

    }

    /**

     * Returns an array containing all of the elements in this queue.

     * The elements are in no particular order.

     *

     * <p>The returned array will be "safe" in that no references to it are

     * maintained by this queue.  (In other words, this method must allocate

     * a new array).  The caller is thus free to modify the returned array.

     *

     * <p>This method acts as bridge between array-based and collection-based

     * APIs.

     *

     * @return an array containing all of the elements in this queue

     */

    public Object[] toArray() {

        return Arrays.copyOf(queue, size);

    }

    /**

     * Returns an array containing all of the elements in this queue; the

     * runtime type of the returned array is that of the specified array.

     * The returned array elements are in no particular order.

     * If the queue fits in the specified array, it is returned therein.

     * Otherwise, a new array is allocated with the runtime type of the

     * specified array and the size of this queue.

     *

     * <p>If the queue fits in the specified array with room to spare

     * (i.e., the array has more elements than the queue), the element in

     * the array immediately following the end of the collection is set to

     * {@code null}.

     *

     * <p>Like the {@link #toArray()} method, this method acts as bridge between

     * array-based and collection-based APIs.  Further, this method allows

     * precise control over the runtime type of the output array, and may,

     * under certain circumstances, be used to save allocation costs.

     *

     * <p>Suppose <tt>x</tt> is a queue known to contain only strings.

     * The following code can be used to dump the queue into a newly

     * allocated array of <tt>String</tt>:

     *

     * <pre>

     *     String[] y = x.toArray(new String[0]);</pre>

     *

     * Note that <tt>toArray(new Object[0])</tt> is identical in function to

     * <tt>toArray()</tt>.

     *

     * @param a the array into which the elements of the queue are to

     *          be stored, if it is big enough; otherwise, a new array of the

     *          same runtime type is allocated for this purpose.

     * @return an array containing all of the elements in this queue

     * @throws ArrayStoreException if the runtime type of the specified array

     *         is not a supertype of the runtime type of every element in

     *         this queue

     * @throws NullPointerException if the specified array is null

     */

    public <T> T[] toArray(T[] a) {

        if (a.length < size)

            // Make a new array of a's runtime type, but my contents:

            return (T[]) Arrays.copyOf(queue, size, a.getClass());

        System.arraycopy(queue, 0, a, 0, size);

        if (a.length > size)

            a[size] = null;

        return a;

    }

    /**

     * Returns an iterator over the elements in this queue. The iterator

     * does not return the elements in any particular order.

     *

     * @return an iterator over the elements in this queue

     */

    public Iterator<E> iterator() {

        return new Itr();

    }

    private final class Itr implements Iterator<E> {

        /**

         * Index (into queue array) of element to be returned by

         * subsequent call to next.

         */

        private int cursor = 0;

        /**

         * Index of element returned by most recent call to next,

         * unless that element came from the forgetMeNot list.

         * Set to -1 if element is deleted by a call to remove.

         */

        private int lastRet = -1;

        /**

         * A queue of elements that were moved from the unvisited portion of

         * the heap into the visited portion as a result of "unlucky" element

         * removals during the iteration.  (Unlucky element removals are those

         * that require a siftup instead of a siftdown.)  We must visit all of

         * the elements in this list to complete the iteration.  We do this

         * after we've completed the "normal" iteration.

         *

         * We expect that most iterations, even those involving removals,

         * will not need to store elements in this field.

         */

        private ArrayDeque<E> forgetMeNot = null;

        /**

         * Element returned by the most recent call to next iff that

         * element was drawn from the forgetMeNot list.

         */

        private E lastRetElt = null;

        /**

         * The modCount value that the iterator believes that the backing

         * Queue should have.  If this expectation is violated, the iterator

         * has detected concurrent modification.

         */

        private int expectedModCount = modCount;

        public boolean hasNext() {

            return cursor < size ||

                (forgetMeNot != null && !forgetMeNot.isEmpty());

        }

        public E next() {

            if (expectedModCount != modCount)

                throw new ConcurrentModificationException();

            if (cursor < size)

                return (E) queue[lastRet = cursor++];

            if (forgetMeNot != null) {

                lastRet = -1;

                lastRetElt = forgetMeNot.poll();

                if (lastRetElt != null)

                    return lastRetElt;

            }

            throw new NoSuchElementException();

        }

        public void remove() {

            if (expectedModCount != modCount)

                throw new ConcurrentModificationException();

            if (lastRet != -1) {

                E moved = PriorityQueue.this.removeAt(lastRet);

                lastRet = -1;

                if (moved == null)

                    cursor--;

                else {

                    if (forgetMeNot == null)

                        forgetMeNot = new ArrayDeque<E>();

                    forgetMeNot.add(moved);

                }

            } else if (lastRetElt != null) {

                PriorityQueue.this.removeEq(lastRetElt);

                lastRetElt = null;

            } else {

                throw new IllegalStateException();

            }

            expectedModCount = modCount;

        }

    }

    public int size() {

        return size;

    }

    /**

     * Removes all of the elements from this priority queue.

     * The queue will be empty after this call returns.

     */

    public void clear() {

        modCount++;

        for (int i = 0; i < size; i++)

            queue[i] = null;

        size = 0;