/*

  * 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.  Oracle designates this

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

  * by Oracle 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

  * or visit www.oracle.com if you need additional information or have any

  * questions.

  */

 /*

  * This file is available under and governed by the GNU General Public

  * License version 2 only, as published by the Free Software Foundation.

  * However, the following notice accompanied the original version of this

  * file:

  *

  * Written by Doug Lea with assistance from members of JCP JSR-166

  * Expert Group and released to the public domain, as explained at

  * http://creativecommons.org/publicdomain/zero/1.0/

  */

 package java.util.concurrent;

 import java.util.concurrent.locks.*;

 import java.util.*;

 /**

  * An unbounded {@linkplain BlockingQueue blocking queue} that uses

  * the same ordering rules as class {@link PriorityQueue} and supplies

  * blocking retrieval operations.  While this queue is logically

  * unbounded, attempted additions may fail due to resource exhaustion

  * (causing {@code OutOfMemoryError}). This class does not permit

  * {@code null} elements.  A priority queue relying on {@linkplain

  * Comparable natural ordering} also does not permit insertion of

  * non-comparable objects (doing so results in

  * {@code ClassCastException}).

  *

  * <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 PriorityBlockingQueue in any particular order. If you need

  * ordered traversal, consider using

  * {@code Arrays.sort(pq.toArray())}.  Also, method {@code drainTo}

  * can be used to <em>remove</em> some or all elements in priority

  * order and place them in another collection.

  *

  * <p>Operations on this class make no guarantees about the ordering

  * of elements with equal priority. If you need to enforce an

  * ordering, you can define custom classes or comparators that use a

  * secondary key to break ties in primary priority values.  For

  * example, here is a class that applies first-in-first-out

  * tie-breaking to comparable elements. To use it, you would insert a

  * {@code new FIFOEntry(anEntry)} instead of a plain entry object.

  *

  *  <pre> {@code

  * class FIFOEntry<E extends Comparable<? super E>>

  *     implements Comparable<FIFOEntry<E>> {

  *   static final AtomicLong seq = new AtomicLong(0);

  *   final long seqNum;

  *   final E entry;

  *   public FIFOEntry(E entry) {

  *     seqNum = seq.getAndIncrement();

  *     this.entry = entry;

  *   }

  *   public E getEntry() { return entry; }

  *   public int compareTo(FIFOEntry<E> other) {

  *     int res = entry.compareTo(other.entry);

  *     if (res == 0 && other.entry != this.entry)

  *       res = (seqNum < other.seqNum ? -1 : 1);

  *     return res;

  *   }

  * }}</pre>

  *

  * <p>This class is a member of the

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

  * Java Collections Framework</a>.

  *

  * @since 1.5

  * @author Doug Lea

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

  */

 public class PriorityBlockingQueue<E> extends AbstractQueue<E>

     implements BlockingQueue<E>, java.io.Serializable {

     private static final long serialVersionUID = 5595510919245408276L;

     /*

      * The implementation uses an array-based binary heap, with public

      * operations protected with a single lock. However, allocation

      * during resizing uses a simple spinlock (used only while not

      * holding main lock) in order to allow takes to operate

      * concurrently with allocation.  This avoids repeated

      * postponement of waiting consumers and consequent element

      * build-up. The need to back away from lock during allocation

      * makes it impossible to simply wrap delegated

      * java.util.PriorityQueue operations within a lock, as was done

      * in a previous version of this class. To maintain

      * interoperability, a plain PriorityQueue is still used during

      * serialization, which maintains compatibility at the espense of

      * transiently doubling overhead.

      */

     /**

      * Default array capacity.

      */

     private static final int DEFAULT_INITIAL_CAPACITY = 11;

     /**

      * The maximum size of array to allocate.

      * Some VMs reserve some header words in an array.

      * Attempts to allocate larger arrays may result in

      * OutOfMemoryError: Requested array size exceeds VM limit

      */

     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

     /**

      * 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 transient int size;

     /**

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

      * natural ordering.

      */

     private transient Comparator<? super E> comparator;

     /**

      * Lock used for all public operations

      */

     private final ReentrantLock lock;

     /**

      * Condition for blocking when empty

      */

     private final Condition notEmpty;

     /**

      * Spinlock for allocation, acquired via CAS.

      */

     private transient volatile int allocationSpinLock;

     /**

      * A plain PriorityQueue used only for serialization,

      * to maintain compatibility with previous versions

      * of this class. Non-null only during serialization/deserialization.

      */

     private PriorityQueue q;

     /**

      * Creates a {@code PriorityBlockingQueue} with the default

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

      * their {@linkplain Comparable natural ordering}.

      */

     public PriorityBlockingQueue() {

         this(DEFAULT_INITIAL_CAPACITY, null);

     }

     /**

      * Creates a {@code PriorityBlockingQueue} 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 PriorityBlockingQueue(int initialCapacity) {

         this(initialCapacity, null);

     }

     /**

      * Creates a {@code PriorityBlockingQueue} 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 PriorityBlockingQueue(int initialCapacity,

                                  Comparator<? super E> comparator) {

         if (initialCapacity < 1)

             throw new IllegalArgumentException();

         this.lock = new ReentrantLock();

         this.notEmpty = lock.newCondition();

         this.comparator = comparator;

         this.queue = new Object[initialCapacity];

     }

     /**

      * Creates a {@code PriorityBlockingQueue} containing the elements

      * in the specified collection.  If the specified collection is a

      * {@link SortedSet} or a {@link 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 PriorityBlockingQueue(Collection<? extends E> c) {

         this.lock = new ReentrantLock();

         this.notEmpty = lock.newCondition();

         boolean heapify = true; // true if not known to be in heap order

         boolean screen = true;  // true if must screen for nulls

         if (c instanceof SortedSet<?>) {

             SortedSet<? extends E> ss = (SortedSet<? extends E>) c;

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

             heapify = false;

         }

         else if (c instanceof PriorityBlockingQueue<?>) {

             PriorityBlockingQueue<? extends E> pq =

                 (PriorityBlockingQueue<? extends E>) c;

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

             screen = false;

             if (pq.getClass() == PriorityBlockingQueue.class) // exact match

                 heapify = false;

         }

         Object[] a = c.toArray();

         int n = a.length;

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

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

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

         if (screen && (n == 1 || this.comparator != null)) {

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

                 if (a[i] == null)

                     throw new NullPointerException();

         }

         this.queue = a;

         this.size = n;

         if (heapify)

             heapify();

     }

     /**

      * Tries to grow array to accommodate at least one more element

      * (but normally expand by about 50%), giving up (allowing retry)

      * on contention (which we expect to be rare). Call only while

      * holding lock.

      *

      * @param array the heap array

      * @param oldCap the length of the array

      */

     private void tryGrow(Object[] array, int oldCap) {

         lock.unlock(); // must release and then re-acquire main lock

         Object[] newArray = null;

         if (allocationSpinLock == 0 &&

             UNSAFE.compareAndSwapInt(this, allocationSpinLockOffset,

                                      0, 1)) {

             try {

                 int newCap = oldCap + ((oldCap < 64) ?

                                        (oldCap + 2) : // grow faster if small

                                        (oldCap >> 1));

                 if (newCap - MAX_ARRAY_SIZE > 0) {    // possible overflow

                     int minCap = oldCap + 1;

                     if (minCap < 0 || minCap > MAX_ARRAY_SIZE)

                         throw new OutOfMemoryError();

                     newCap = MAX_ARRAY_SIZE;

                 }

                 if (newCap > oldCap && queue == array)

                     newArray = new Object[newCap];

             } finally {

                 allocationSpinLock = 0;

             }

         }

         if (newArray == null) // back off if another thread is allocating

             Thread.yield();

         lock.lock();

         if (newArray != null && queue == array) {

             queue = newArray;

             System.arraycopy(array, 0, newArray, 0, oldCap);

         }

     }

     /**

      * Mechanics for poll().  Call only while holding lock.

      */

     private E extract() {

         E result;

         int n = size - 1;

         if (n < 0)

             result = null;

         else {

             Object[] array = queue;

             result = (E) array[0];

             E x = (E) array[n];

             array[n] = null;

             Comparator<? super E> cmp = comparator;

             if (cmp == null)

                 siftDownComparable(0, x, array, n);

             else

                 siftDownUsingComparator(0, x, array, n, cmp);

             size = n;

         }

         return result;

     }

     /**

      * Inserts item x at position k, maintaining heap invariant by

      * promoting x up the tree until it is greater than or equal to

      * its parent, or is the root.

      *

      * To simplify and speed up coercions and comparisons. the

      * Comparable and Comparator versions are separated into different

      * methods that are otherwise identical. (Similarly for siftDown.)

      * These methods are static, with heap state as arguments, to

      * simplify use in light of possible comparator exceptions.

      *

      * @param k the position to fill

      * @param x the item to insert

      * @param array the heap array

      * @param n heap size

      */

     private static <T> void siftUpComparable(int k, T x, Object[] array) {

         Comparable<? super T> key = (Comparable<? super T>) x;

         while (k > 0) {

             int parent = (k - 1) >>> 1;

             Object e = array[parent];

             if (key.compareTo((T) e) >= 0)

                 break;

             array[k] = e;

             k = parent;

         }

         array[k] = key;

     }

     private static <T> void siftUpUsingComparator(int k, T x, Object[] array,

                                        Comparator<? super T> cmp) {

         while (k > 0) {

             int parent = (k - 1) >>> 1;

             Object e = array[parent];

             if (cmp.compare(x, (T) e) >= 0)

                 break;

             array[k] = e;

             k = parent;

         }

         array[k] = x;

     }

     /**

      * Inserts item x at position k, maintaining heap invariant by

      * demoting x down the tree repeatedly until it is less than or

      * equal to its children or is a leaf.

      *

      * @param k the position to fill

      * @param x the item to insert

      * @param array the heap array

      * @param n heap size

      */

     private static <T> void siftDownComparable(int k, T x, Object[] array,

                                                int n) {

         Comparable<? super T> key = (Comparable<? super T>)x;

         int half = n >>> 1;           // loop while a non-leaf

         while (k < half) {

             int child = (k << 1) + 1; // assume left child is least

             Object c = array[child];

             int right = child + 1;

             if (right < n &&

                 ((Comparable<? super T>) c).compareTo((T) array[right]) > 0)

                 c = array[child = right];

             if (key.compareTo((T) c) <= 0)

                 break;

             array[k] = c;

             k = child;

         }

         array[k] = key;

     }

     private static <T> void siftDownUsingComparator(int k, T x, Object[] array,

                                                     int n,

                                                     Comparator<? super T> cmp) {

         int half = n >>> 1;

         while (k < half) {

             int child = (k << 1) + 1;

             Object c = array[child];

             int right = child + 1;

             if (right < n && cmp.compare((T) c, (T) array[right]) > 0)

                 c = array[child = right];

             if (cmp.compare(x, (T) c) <= 0)

                 break;

             array[k] = c;

             k = child;

         }

         array[k] = x;

     }

     /**

      * Establishes the heap invariant (described above) in the entire tree,

      * assuming nothing about the order of the elements prior to the call.

      */

     private void heapify() {

         Object[] array = queue;

         int n = size;

         int half = (n >>> 1) - 1;

         Comparator<? super E> cmp = comparator;

         if (cmp == null) {

             for (int i = half; i >= 0; i--)

                 siftDownComparable(i, (E) array[i], array, n);

         }

         else {

             for (int i = half; i >= 0; i--)

                 siftDownUsingComparator(i, (E) array[i], array, n, cmp);

         }

     }

     /**

      * Inserts the specified element into this priority queue.

      *

      * @param e the element to add

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

      * @throws ClassCastException if the specified element cannot be compared

      *         with elements currently in the 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.

      * As the queue is unbounded, this method will never return {@code false}.

      *

      * @param e the element to add

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

      * @throws ClassCastException if the specified element cannot be compared

      *         with elements currently in the 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();

         final ReentrantLock lock = this.lock;

         lock.lock();

         int n, cap;

         Object[] array;

         while ((n = size) >= (cap = (array = queue).length))

             tryGrow(array, cap);

         try {

             Comparator<? super E> cmp = comparator;

             if (cmp == null)

                 siftUpComparable(n, e, array);

             else

                 siftUpUsingComparator(n, e, array, cmp);

             size = n + 1;

             notEmpty.signal();

         } finally {

             lock.unlock();

         }

         return true;

     }

     /**

      * Inserts the specified element into this priority queue.

      * As the queue is unbounded, this method will never block.

      *

      * @param e the element to add

      * @throws ClassCastException if the specified element cannot be compared

      *         with elements currently in the priority queue according to the

      *         priority queue's ordering

      * @throws NullPointerException if the specified element is null

      */

     public void put(E e) {

         offer(e); // never need to block

     }

     /**

      * Inserts the specified element into this priority queue.

      * As the queue is unbounded, this method will never block or

      * return {@code false}.

      *

      * @param e the element to add

      * @param timeout This parameter is ignored as the method never blocks

      * @param unit This parameter is ignored as the method never blocks

      * @return {@code true} (as specified by

      *  {@link BlockingQueue#offer(Object,long,TimeUnit) BlockingQueue.offer})

      * @throws ClassCastException if the specified element cannot be compared

      *         with elements currently in the priority queue according to the

      *         priority queue's ordering

      * @throws NullPointerException if the specified element is null

      */

     public boolean offer(E e, long timeout, TimeUnit unit) {

         return offer(e); // never need to block

     }

     public E poll() {

         final ReentrantLock lock = this.lock;

         lock.lock();

         E result;

         try {

             result = extract();

         } finally {

             lock.unlock();

         }

         return result;

     }

     public E take() throws InterruptedException {

         final ReentrantLock lock = this.lock;

         lock.lockInterruptibly();

         E result;

         try {

             while ( (result = extract()) == null)

                 notEmpty.await();

         } finally {

             lock.unlock();

         }

         return result;

     }

     public E poll(long timeout, TimeUnit unit) throws InterruptedException {

         long nanos = unit.toNanos(timeout);

         final ReentrantLock lock = this.lock;

         lock.lockInterruptibly();

         E result;

         try {

             while ( (result = extract()) == null && nanos > 0)

                 nanos = notEmpty.awaitNanos(nanos);

         } finally {

             lock.unlock();

         }

         return result;

     }

     public E peek() {

         final ReentrantLock lock = this.lock;

         lock.lock();

         E result;

         try {

             result = size > 0 ? (E) queue[0] : null;

         } finally {

             lock.unlock();

         }

         return result;

     }

     /**

      * Returns the comparator used to order the elements in this queue,

      * or {@code null} if this queue uses the {@linkplain Comparable

      * natural ordering} of its elements.

      *

      * @return the comparator used to order the elements in this queue,

      *         or {@code null} if this queue uses the natural

      *         ordering of its elements

      */

     public Comparator<? super E> comparator() {

         return comparator;

     }

     public int size() {

         final ReentrantLock lock = this.lock;

         lock.lock();

         try {

             return size;

         } finally {

             lock.unlock();

         }

     }

     /**

      * Always returns {@code Integer.MAX_VALUE} because

      * a {@code PriorityBlockingQueue} is not capacity constrained.

      * @return {@code Integer.MAX_VALUE} always

      */

     public int remainingCapacity() {

         return Integer.MAX_VALUE;

     }

     private int indexOf(Object o) {

         if (o != null) {

             Object[] array = queue;

             int n = size;

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

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

                     return i;

         }

         return -1;

     }

     /**

      * Removes the ith element from queue.

      */

     private void removeAt(int i) {

         Object[] array = queue;

         int n = size - 1;

         if (n == i) // removed last element

             array[i] = null;

         else {

             E moved = (E) array[n];

             array[n] = null;

             Comparator<? super E> cmp = comparator;

             if (cmp == null)

                 siftDownComparable(i, moved, array, n);

             else

                 siftDownUsingComparator(i, moved, array, n, cmp);

             if (array[i] == moved) {

                 if (cmp == null)

                     siftUpComparable(i, moved, array);

                 else

                     siftUpUsingComparator(i, moved, array, cmp);

             }

         }

         size = n;

     }

     /**

      * 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) {

         boolean removed = false;

         final ReentrantLock lock = this.lock;

         lock.lock();

         try {

             int i = indexOf(o);

             if (i != -1) {

                 removeAt(i);

                 removed = true;

             }

         } finally {

             lock.unlock();

         }

         return removed;

     }

     /**

      * Identity-based version for use in Itr.remove

      */

     private void removeEQ(Object o) {

         final ReentrantLock lock = this.lock;

         lock.lock();

         try {

             Object[] array = queue;

             int n = size;

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

                 if (o == array[i]) {

                     removeAt(i);

                     break;

                 }

             }

         } finally {

             lock.unlock();

         }

     }

     /**

      * 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) {

         int index;

         final ReentrantLock lock = this.lock;

         lock.lock();

         try {

             index = indexOf(o);

         } finally {

             lock.unlock();

         }

         return index != -1;

     }

     /**

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

      * The returned array 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() {

         final ReentrantLock lock = this.lock;

         lock.lock();

         try {

             return Arrays.copyOf(queue, size);

         } finally {

             lock.unlock();

         }

     }

     public String toString() {

         final ReentrantLock lock = this.lock;

         lock.lock();

         try {

             int n = size;

             if (n == 0)

                 return "[]";

             StringBuilder sb = new StringBuilder();

             sb.append('[');

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

                 E e = (E)queue[i];

                 sb.append(e == this ? "(this Collection)" : e);

                 if (i != n - 1)

                     sb.append(',').append(' ');

             }

             return sb.append(']').toString();

         } finally {

             lock.unlock();

         }

     }

     /**

      * @throws UnsupportedOperationException {@inheritDoc}

      * @throws ClassCastException            {@inheritDoc}

      * @throws NullPointerException          {@inheritDoc}

      * @throws IllegalArgumentException      {@inheritDoc}

      */

     public int drainTo(Collection<? super E> c) {

         if (c == null)

             throw new NullPointerException();

         if (c == this)

             throw new IllegalArgumentException();

         final ReentrantLock lock = this.lock;

         lock.lock();

         try {

             int n = 0;

             E e;

             while ( (e = extract()) != null) {

                 c.add(e);

                 ++n;

             }

             return n;

         } finally {

             lock.unlock();

         }

     }

     /**

      * @throws UnsupportedOperationException {@inheritDoc}

      * @throws ClassCastException            {@inheritDoc}

      * @throws NullPointerException          {@inheritDoc}

      * @throws IllegalArgumentException      {@inheritDoc}

      */

     public int drainTo(Collection<? super E> c, int maxElements) {

         if (c == null)

             throw new NullPointerException();

         if (c == this)

             throw new IllegalArgumentException();

         if (maxElements <= 0)

             return 0;

         final ReentrantLock lock = this.lock;

         lock.lock();

         try {

             int n = 0;

             E e;

             while (n < maxElements && (e = extract()) != null) {

                 c.add(e);

                 ++n;

             }

             return n;

         } finally {

             lock.unlock();

         }

     }

     /**

      * Atomically removes all of the elements from this queue.

      * The queue will be empty after this call returns.

      */

     public void clear() {

         final ReentrantLock lock = this.lock;

         lock.lock();

         try {

             Object[] array = queue;

             int n = size;

             size = 0;

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

                 array[i] = null;

         } finally {

             lock.unlock();

         }

     }

     /**

      * 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 this queue fits in the specified array with room to spare

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

      * the array immediately following the end of the queue 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 {@code x} is a queue known to contain only strings.

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

      * allocated array of {@code String}:

      *

      * <pre>

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

      *

      * Note that {@code toArray(new Object[0])} is identical in function to

      * {@code toArray()}.

      *

      * @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) {

         final ReentrantLock lock = this.lock;

         lock.lock();

         try {

             int n = size;

             if (a.length < n)

                 // 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, n);

             if (a.length > n)

                 a[n] = null;

             return a;

         } finally {

             lock.unlock();

         }

     }

     /**

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

      * iterator does not return the elements in any particular order.

      *

      * <p>The returned iterator is a "weakly consistent" iterator that

      * will never throw {@link java.util.ConcurrentModificationException

      * ConcurrentModificationException}, and guarantees to traverse

      * elements as they existed upon construction of the iterator, and

      * may (but is not guaranteed to) reflect any modifications

      * subsequent to construction.

      *

      * @return an iterator over the elements in this queue

      */

     public Iterator<E> iterator() {

         return new Itr(toArray());

     }

     /**

      * Snapshot iterator that works off copy of underlying q array.

      */

     final class Itr implements Iterator<E> {

         final Object[] array; // Array of all elements

         int cursor;           // index of next element to return;

         int lastRet;          // index of last element, or -1 if no such

         Itr(Object[] array) {

             lastRet = -1;

             this.array = array;

         }

         public boolean hasNext() {

             return cursor < array.length;

         }

         public E next() {

             if (cursor >= array.length)

                 throw new NoSuchElementException();

             lastRet = cursor;

             return (E)array[cursor++];

         }

         public void remove() {

             if (lastRet < 0)

                 throw new IllegalStateException();

             removeEQ(array[lastRet]);

             lastRet = -1;

         }

     }

     /**

      * Saves the state to a stream (that is, serializes it).  For

      * compatibility with previous version of this class,

      * elements are first copied to a java.util.PriorityQueue,

      * which is then serialized.

      */

     private void writeObject(java.io.ObjectOutputStream s)

         throws java.io.IOException {

         lock.lock();

         try {

             int n = size; // avoid zero capacity argument

             q = new PriorityQueue<E>(n == 0 ? 1 : n, comparator);

             q.addAll(this);

             s.defaultWriteObject();

         } finally {

             q = null;

             lock.unlock();

         }

     }

     /**

      * Reconstitutes the {@code PriorityBlockingQueue} instance from a stream

      * (that is, deserializes it).

      *

      * @param s the stream

      */

     private void readObject(java.io.ObjectInputStream s)

         throws java.io.IOException, ClassNotFoundException {

         try {

             s.defaultReadObject();

             this.queue = new Object[q.size()];

             comparator = q.comparator();

             addAll(q);

         } finally {

             q = null;

         }

     }

     // Unsafe mechanics

     private static final sun.misc.Unsafe UNSAFE;

     private static final long allocationSpinLockOffset;

     static {

         try {

             UNSAFE = sun.misc.Unsafe.getUnsafe();

             Class k = PriorityBlockingQueue.class;

             allocationSpinLockOffset = UNSAFE.objectFieldOffset

                 (k.getDeclaredField("allocationSpinLock"));

         } catch (Exception e) {

             throw new Error(e);

         }

     }

 }