1adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/* 2adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Written by Doug Lea with assistance from members of JCP JSR-166 3adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Expert Group and released to the public domain, as explained at 4a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * http://creativecommons.org/publicdomain/zero/1.0/ 5adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 6adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 7adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.util.concurrent; 8adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 9e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.AbstractQueue; 10e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.Arrays; 11e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.Collection; 12e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.Comparator; 13e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.Iterator; 14e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.NoSuchElementException; 15e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.PriorityQueue; 16e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.Queue; 17e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.SortedSet; 18e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.Spliterator; 1991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravleimport java.util.concurrent.locks.Condition; 2091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravleimport java.util.concurrent.locks.ReentrantLock; 21e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.function.Consumer; 22adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 23adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project// BEGIN android-note 24adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project// removed link to collections framework docs 25adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project// END android-note 26adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 27adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 28adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * An unbounded {@linkplain BlockingQueue blocking queue} that uses 29adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the same ordering rules as class {@link PriorityQueue} and supplies 30adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * blocking retrieval operations. While this queue is logically 31adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * unbounded, attempted additions may fail due to resource exhaustion 328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * (causing {@code OutOfMemoryError}). This class does not permit 338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code null} elements. A priority queue relying on {@linkplain 34bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Comparable natural ordering} also does not permit insertion of 35bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * non-comparable objects (doing so results in 368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code ClassCastException}). 37adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 38bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>This class and its iterator implement all of the 39bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <em>optional</em> methods of the {@link Collection} and {@link 40bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Iterator} interfaces. The Iterator provided in method {@link 41bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * #iterator()} is <em>not</em> guaranteed to traverse the elements of 42bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the PriorityBlockingQueue in any particular order. If you need 43bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * ordered traversal, consider using 448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code Arrays.sort(pq.toArray())}. Also, method {@code drainTo} 45bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * can be used to <em>remove</em> some or all elements in priority 46bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * order and place them in another collection. 47bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 48bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Operations on this class make no guarantees about the ordering 49bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * of elements with equal priority. If you need to enforce an 50bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * ordering, you can define custom classes or comparators that use a 51bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * secondary key to break ties in primary priority values. For 52bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * example, here is a class that applies first-in-first-out 53bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * tie-breaking to comparable elements. To use it, you would insert a 548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code new FIFOEntry(anEntry)} instead of a plain entry object. 55bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 56e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <pre> {@code 578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * class FIFOEntry<E extends Comparable<? super E>> 588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * implements Comparable<FIFOEntry<E>> { 598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * static final AtomicLong seq = new AtomicLong(0); 60bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * final long seqNum; 61bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * final E entry; 62bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * public FIFOEntry(E entry) { 63bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * seqNum = seq.getAndIncrement(); 64bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * this.entry = entry; 65bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } 66bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * public E getEntry() { return entry; } 678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * public int compareTo(FIFOEntry<E> other) { 68bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * int res = entry.compareTo(other.entry); 698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * if (res == 0 && other.entry != this.entry) 708eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * res = (seqNum < other.seqNum ? -1 : 1); 71bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * return res; 72bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * } 738eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * }}</pre> 74adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 75adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @since 1.5 76adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @author Doug Lea 77e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param <E> the type of elements held in this queue 78adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 7991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle@SuppressWarnings("unchecked") 80adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpublic class PriorityBlockingQueue<E> extends AbstractQueue<E> 81adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project implements BlockingQueue<E>, java.io.Serializable { 82adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final long serialVersionUID = 5595510919245408276L; 83adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 848eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /* 858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * The implementation uses an array-based binary heap, with public 868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * operations protected with a single lock. However, allocation 878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * during resizing uses a simple spinlock (used only while not 888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * holding main lock) in order to allow takes to operate 898eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * concurrently with allocation. This avoids repeated 908eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * postponement of waiting consumers and consequent element 918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * build-up. The need to back away from lock during allocation 928eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * makes it impossible to simply wrap delegated 938eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * java.util.PriorityQueue operations within a lock, as was done 948eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * in a previous version of this class. To maintain 958eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * interoperability, a plain PriorityQueue is still used during 96a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * serialization, which maintains compatibility at the expense of 978eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * transiently doubling overhead. 988eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 998eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Default array capacity. 1028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static final int DEFAULT_INITIAL_CAPACITY = 11; 1048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * The maximum size of array to allocate. 1078eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Some VMs reserve some header words in an array. 1088eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Attempts to allocate larger arrays may result in 1098eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * OutOfMemoryError: Requested array size exceeds VM limit 1108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1118eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 1128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Priority queue represented as a balanced binary heap: the two 1158eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The 1168eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * priority queue is ordered by comparator, or by the elements' 1178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * natural ordering, if comparator is null: For each node n in the 1188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * heap and each descendant d of n, n <= d. The element with the 1198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * lowest value is in queue[0], assuming the queue is nonempty. 1208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private transient Object[] queue; 1228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1248eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * The number of elements in the priority queue. 1258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private transient int size; 1278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1288eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * The comparator, or null if priority queue uses elements' 1308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * natural ordering. 1318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private transient Comparator<? super E> comparator; 133adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 134adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 135e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Lock used for all public operations. 1368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private final ReentrantLock lock; 1388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 140e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Condition for blocking when empty. 1418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private final Condition notEmpty; 1438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Spinlock for allocation, acquired via CAS. 1468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 1478eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private transient volatile int allocationSpinLock; 1488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * A plain PriorityQueue used only for serialization, 1518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * to maintain compatibility with previous versions 1528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * of this class. Non-null only during serialization/deserialization. 1538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 154a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private PriorityQueue<E> q; 1558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 1578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Creates a {@code PriorityBlockingQueue} with the default 158bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * initial capacity (11) that orders its elements according to 159bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * their {@linkplain Comparable natural ordering}. 160adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public PriorityBlockingQueue() { 1628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this(DEFAULT_INITIAL_CAPACITY, null); 163adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 164adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 165adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1668eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Creates a {@code PriorityBlockingQueue} with the specified 167bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * initial capacity that orders its elements according to their 168bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@linkplain Comparable natural ordering}. 169adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 170bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param initialCapacity the initial capacity for this priority queue 1718eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @throws IllegalArgumentException if {@code initialCapacity} is less 172bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * than 1 173adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 174adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public PriorityBlockingQueue(int initialCapacity) { 1758eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this(initialCapacity, null); 176adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 177adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 178adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1798eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Creates a {@code PriorityBlockingQueue} with the specified initial 180bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * capacity that orders its elements according to the specified 181bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * comparator. 182adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 183bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param initialCapacity the initial capacity for this priority queue 184bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param comparator the comparator that will be used to order this 185bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * priority queue. If {@code null}, the {@linkplain Comparable 186bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * natural ordering} of the elements will be used. 1878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @throws IllegalArgumentException if {@code initialCapacity} is less 188bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * than 1 189adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 190adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public PriorityBlockingQueue(int initialCapacity, 191adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project Comparator<? super E> comparator) { 1928eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (initialCapacity < 1) 1938eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throw new IllegalArgumentException(); 1948eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.lock = new ReentrantLock(); 1958eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.notEmpty = lock.newCondition(); 1968eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.comparator = comparator; 1978eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.queue = new Object[initialCapacity]; 198adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 199adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 200adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 2018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Creates a {@code PriorityBlockingQueue} containing the elements 202bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * in the specified collection. If the specified collection is a 203edf43d27e240d82106f39ae91404963c23987234Narayan Kamath * {@link SortedSet} or a {@link PriorityQueue}, this 204bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * priority queue will be ordered according to the same ordering. 205bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Otherwise, this priority queue will be ordered according to the 206bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@linkplain Comparable natural ordering} of its elements. 207adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 208bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param c the collection whose elements are to be placed 209bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * into this priority queue 210adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws ClassCastException if elements of the specified collection 211adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * cannot be compared to one another according to the priority 212bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * queue's ordering 213bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified collection or any 214bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * of its elements are null 215adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 216adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public PriorityBlockingQueue(Collection<? extends E> c) { 2178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.lock = new ReentrantLock(); 2188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.notEmpty = lock.newCondition(); 2198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson boolean heapify = true; // true if not known to be in heap order 2208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson boolean screen = true; // true if must screen for nulls 2218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (c instanceof SortedSet<?>) { 2228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson SortedSet<? extends E> ss = (SortedSet<? extends E>) c; 2238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.comparator = (Comparator<? super E>) ss.comparator(); 2248eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson heapify = false; 2258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if (c instanceof PriorityBlockingQueue<?>) { 2278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson PriorityBlockingQueue<? extends E> pq = 2288eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson (PriorityBlockingQueue<? extends E>) c; 2298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.comparator = (Comparator<? super E>) pq.comparator(); 2308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson screen = false; 2318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (pq.getClass() == PriorityBlockingQueue.class) // exact match 2328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson heapify = false; 2338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] a = c.toArray(); 2358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n = a.length; 2368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // If c.toArray incorrectly doesn't return Object[], copy it. 2378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (a.getClass() != Object[].class) 2388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson a = Arrays.copyOf(a, n, Object[].class); 2398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (screen && (n == 1 || this.comparator != null)) { 2408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (int i = 0; i < n; ++i) 2418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (a[i] == null) 2428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throw new NullPointerException(); 2438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.queue = a; 2458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.size = n; 2468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (heapify) 2478eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson heapify(); 2488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 2508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 2518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Tries to grow array to accommodate at least one more element 2528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * (but normally expand by about 50%), giving up (allowing retry) 2538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * on contention (which we expect to be rare). Call only while 2548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * holding lock. 2558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 2568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param array the heap array 2578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param oldCap the length of the array 2588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 2598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private void tryGrow(Object[] array, int oldCap) { 2608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson lock.unlock(); // must release and then re-acquire main lock 2618eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] newArray = null; 2628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (allocationSpinLock == 0 && 263e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.compareAndSwapInt(this, ALLOCATIONSPINLOCK, 0, 1)) { 2648eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 2658eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int newCap = oldCap + ((oldCap < 64) ? 2668eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson (oldCap + 2) : // grow faster if small 2678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson (oldCap >> 1)); 2688eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (newCap - MAX_ARRAY_SIZE > 0) { // possible overflow 2698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int minCap = oldCap + 1; 2708eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (minCap < 0 || minCap > MAX_ARRAY_SIZE) 2718eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throw new OutOfMemoryError(); 2728eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson newCap = MAX_ARRAY_SIZE; 2738eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2748eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (newCap > oldCap && queue == array) 2758eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson newArray = new Object[newCap]; 2768eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } finally { 2778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson allocationSpinLock = 0; 2788eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2798eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (newArray == null) // back off if another thread is allocating 2818eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Thread.yield(); 2828eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson lock.lock(); 2838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (newArray != null && queue == array) { 2848eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson queue = newArray; 2858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson System.arraycopy(array, 0, newArray, 0, oldCap); 2868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 2888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 2898eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 2908eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Mechanics for poll(). Call only while holding lock. 2918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 292a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private E dequeue() { 2938eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n = size - 1; 2948eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (n < 0) 295a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return null; 2968eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else { 2978eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] array = queue; 298a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson E result = (E) array[0]; 2998eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E x = (E) array[n]; 3008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[n] = null; 3018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Comparator<? super E> cmp = comparator; 3028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (cmp == null) 3038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftDownComparable(0, x, array, n); 3048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 3058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftDownUsingComparator(0, x, array, n, cmp); 3068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson size = n; 307a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return result; 3088eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3098eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 3118eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 3128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Inserts item x at position k, maintaining heap invariant by 3138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * promoting x up the tree until it is greater than or equal to 3148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * its parent, or is the root. 3158eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 3168eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * To simplify and speed up coercions and comparisons. the 3178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Comparable and Comparator versions are separated into different 3188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * methods that are otherwise identical. (Similarly for siftDown.) 3198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * These methods are static, with heap state as arguments, to 3208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * simplify use in light of possible comparator exceptions. 3218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 3228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param k the position to fill 3238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param x the item to insert 3248eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param array the heap array 3258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 3268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static <T> void siftUpComparable(int k, T x, Object[] array) { 3278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Comparable<? super T> key = (Comparable<? super T>) x; 3288eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (k > 0) { 3298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int parent = (k - 1) >>> 1; 3308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object e = array[parent]; 3318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (key.compareTo((T) e) >= 0) 3328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson break; 3338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[k] = e; 3348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson k = parent; 3358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[k] = key; 3378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 3398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static <T> void siftUpUsingComparator(int k, T x, Object[] array, 3408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Comparator<? super T> cmp) { 3418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (k > 0) { 3428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int parent = (k - 1) >>> 1; 3438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object e = array[parent]; 3448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (cmp.compare(x, (T) e) >= 0) 3458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson break; 3468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[k] = e; 3478eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson k = parent; 3488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[k] = x; 3508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 3528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 3538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Inserts item x at position k, maintaining heap invariant by 3548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * demoting x down the tree repeatedly until it is less than or 3558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * equal to its children or is a leaf. 3568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 3578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param k the position to fill 3588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param x the item to insert 3598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param array the heap array 3608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @param n heap size 3618eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 3628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static <T> void siftDownComparable(int k, T x, Object[] array, 3638eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n) { 36491770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle if (n > 0) { 36591770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle Comparable<? super T> key = (Comparable<? super T>)x; 36691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle int half = n >>> 1; // loop while a non-leaf 36791770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle while (k < half) { 36891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle int child = (k << 1) + 1; // assume left child is least 36991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle Object c = array[child]; 37091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle int right = child + 1; 37191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle if (right < n && 37291770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle ((Comparable<? super T>) c).compareTo((T) array[right]) > 0) 37391770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle c = array[child = right]; 37491770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle if (key.compareTo((T) c) <= 0) 37591770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle break; 37691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle array[k] = c; 37791770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle k = child; 37891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle } 37991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle array[k] = key; 3808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3818eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 3828eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 3838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static <T> void siftDownUsingComparator(int k, T x, Object[] array, 3848eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n, 3858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Comparator<? super T> cmp) { 38691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle if (n > 0) { 38791770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle int half = n >>> 1; 38891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle while (k < half) { 38991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle int child = (k << 1) + 1; 39091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle Object c = array[child]; 39191770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle int right = child + 1; 39291770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle if (right < n && cmp.compare((T) c, (T) array[right]) > 0) 39391770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle c = array[child = right]; 39491770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle if (cmp.compare(x, (T) c) <= 0) 39591770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle break; 39691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle array[k] = c; 39791770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle k = child; 39891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle } 39991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle array[k] = x; 4008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 4018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 4028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 4038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 4048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Establishes the heap invariant (described above) in the entire tree, 4058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * assuming nothing about the order of the elements prior to the call. 4068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 4078eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private void heapify() { 4088eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] array = queue; 4098eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n = size; 4108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int half = (n >>> 1) - 1; 4118eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Comparator<? super E> cmp = comparator; 4128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (cmp == null) { 4138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (int i = half; i >= 0; i--) 4148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftDownComparable(i, (E) array[i], array, n); 4158eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 4168eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else { 4178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (int i = half; i >= 0; i--) 4188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftDownUsingComparator(i, (E) array[i], array, n, cmp); 4198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 420adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 421adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 422adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 423bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Inserts the specified element into this priority queue. 424adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 425bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param e the element to add 4268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} (as specified by {@link Collection#add}) 427adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws ClassCastException if the specified element cannot be compared 428bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * with elements currently in the priority queue according to the 429bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * priority queue's ordering 430bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 431adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 432bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean add(E e) { 433bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return offer(e); 434adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 435adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 436adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 437adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Inserts the specified element into this priority queue. 4388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * As the queue is unbounded, this method will never return {@code false}. 439adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 440bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param e the element to add 4418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} (as specified by {@link Queue#offer}) 442adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @throws ClassCastException if the specified element cannot be compared 443bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * with elements currently in the priority queue according to the 444bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * priority queue's ordering 445bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 446adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 447bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean offer(E e) { 4488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (e == null) 4498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throw new NullPointerException(); 450adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 451adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 4528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n, cap; 4538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] array; 4548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while ((n = size) >= (cap = (array = queue).length)) 4558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson tryGrow(array, cap); 456adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 4578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Comparator<? super E> cmp = comparator; 4588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (cmp == null) 4598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftUpComparable(n, e, array); 4608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 4618eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftUpUsingComparator(n, e, array, cmp); 4628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson size = n + 1; 463adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project notEmpty.signal(); 464adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 465adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 466adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 4678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return true; 468adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 469adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 470adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 4718eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Inserts the specified element into this priority queue. 4728eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * As the queue is unbounded, this method will never block. 473bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 474bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param e the element to add 475bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ClassCastException if the specified element cannot be compared 476bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * with elements currently in the priority queue according to the 477bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * priority queue's ordering 478bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 479adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 480bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public void put(E e) { 481bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson offer(e); // never need to block 482adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 483adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 484adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 4858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Inserts the specified element into this priority queue. 4868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * As the queue is unbounded, this method will never block or 4878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * return {@code false}. 488bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 489bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param e the element to add 490adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param timeout This parameter is ignored as the method never blocks 491adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param unit This parameter is ignored as the method never blocks 4928eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} (as specified by 493a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * {@link BlockingQueue#offer(Object,long,TimeUnit) BlockingQueue.offer}) 494bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ClassCastException if the specified element cannot be compared 495bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * with elements currently in the priority queue according to the 496bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * priority queue's ordering 497bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified element is null 498adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 499bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public boolean offer(E e, long timeout, TimeUnit unit) { 500bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return offer(e); // never need to block 501bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 502bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 503bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public E poll() { 504bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson final ReentrantLock lock = this.lock; 505bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lock.lock(); 506bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson try { 507a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return dequeue(); 508bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } finally { 509bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lock.unlock(); 510bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 511adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 512adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 513adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E take() throws InterruptedException { 514adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 515adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lockInterruptibly(); 5168eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E result; 517adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 518a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson while ( (result = dequeue()) == null) 5198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson notEmpty.await(); 520adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 521adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 522adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 5238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return result; 524adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 525adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 526adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E poll(long timeout, TimeUnit unit) throws InterruptedException { 527adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project long nanos = unit.toNanos(timeout); 528adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 529adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lockInterruptibly(); 5308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E result; 531adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 532a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson while ( (result = dequeue()) == null && nanos > 0) 5338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson nanos = notEmpty.awaitNanos(nanos); 534adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 535adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 536adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 5378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return result; 538adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 539adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 540adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E peek() { 541adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 542adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 543adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 544a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return (size == 0) ? null : (E) queue[0]; 545adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 546adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 547adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 548adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 549adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 550bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 551bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns the comparator used to order the elements in this queue, 5528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * or {@code null} if this queue uses the {@linkplain Comparable 553bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * natural ordering} of its elements. 554bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 555bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return the comparator used to order the elements in this queue, 5568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * or {@code null} if this queue uses the natural 557bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * ordering of its elements 558bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 559bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson public Comparator<? super E> comparator() { 5608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return comparator; 561bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson } 562bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 563adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int size() { 564adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 565adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 566adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 5678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return size; 568adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 569adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 570adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 571adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 572adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 573adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 5748eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Always returns {@code Integer.MAX_VALUE} because 5758eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * a {@code PriorityBlockingQueue} is not capacity constrained. 5768eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code Integer.MAX_VALUE} always 577adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 578adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int remainingCapacity() { 579adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return Integer.MAX_VALUE; 580adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 581adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 5828eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private int indexOf(Object o) { 5838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (o != null) { 5848eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] array = queue; 5858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n = size; 5868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (int i = 0; i < n; i++) 5878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (o.equals(array[i])) 5888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return i; 5898eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5908eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return -1; 5918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 5928eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 5938eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 5948eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Removes the ith element from queue. 5958eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 5968eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private void removeAt(int i) { 5978eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] array = queue; 5988eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n = size - 1; 5998eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (n == i) // removed last element 6008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[i] = null; 6018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else { 6028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E moved = (E) array[n]; 6038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[n] = null; 6048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Comparator<? super E> cmp = comparator; 6058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (cmp == null) 6068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftDownComparable(i, moved, array, n); 6078eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 6088eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftDownUsingComparator(i, moved, array, n, cmp); 6098eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (array[i] == moved) { 6108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (cmp == null) 6118eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftUpComparable(i, moved, array); 6128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 6138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson siftUpUsingComparator(i, moved, array, cmp); 6148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 6158eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 6168eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson size = n; 6178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 6188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 619bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 620bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Removes a single instance of the specified element from this queue, 621bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * if it is present. More formally, removes an element {@code e} such 622bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * that {@code o.equals(e)}, if this queue contains one or more such 623bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * elements. Returns {@code true} if and only if this queue contained 624bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the specified element (or equivalently, if this queue changed as a 625bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * result of the call). 626bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 627bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param o element to be removed from this queue, if present 6288eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} if this queue changed as a result of the call 629bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 630adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean remove(Object o) { 631adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 632adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 633adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 6348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int i = indexOf(o); 635a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (i == -1) 636a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return false; 637a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson removeAt(i); 638a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return true; 6398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } finally { 6408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson lock.unlock(); 6418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 6428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 6438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 6448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 645e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Identity-based version for use in Itr.remove. 6468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 647a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson void removeEQ(Object o) { 6488eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final ReentrantLock lock = this.lock; 6498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson lock.lock(); 6508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 6518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] array = queue; 652a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (int i = 0, n = size; i < n; i++) { 6538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (o == array[i]) { 6548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson removeAt(i); 6558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson break; 6568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 6578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 658adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 659adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 660adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 661adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 662adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 663bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 664bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns {@code true} if this queue contains the specified element. 665bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * More formally, returns {@code true} if and only if this queue contains 666bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * at least one element {@code e} such that {@code o.equals(e)}. 667bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 668bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param o object to be checked for containment in this queue 6698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return {@code true} if this queue contains the specified element 670bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 671adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean contains(Object o) { 672adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 673adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 674adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 675a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return indexOf(o) != -1; 676adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 677adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 678adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 679adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 680adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 681adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public String toString() { 682e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return Helpers.collectionToString(this); 683adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 684adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 685bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 686bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws UnsupportedOperationException {@inheritDoc} 687bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ClassCastException {@inheritDoc} 688bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 689bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalArgumentException {@inheritDoc} 690bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 691adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int drainTo(Collection<? super E> c) { 692a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return drainTo(c, Integer.MAX_VALUE); 693adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 694adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 695bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 696bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws UnsupportedOperationException {@inheritDoc} 697bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ClassCastException {@inheritDoc} 698bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException {@inheritDoc} 699bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws IllegalArgumentException {@inheritDoc} 700bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 701adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int drainTo(Collection<? super E> c, int maxElements) { 702adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == null) 703adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NullPointerException(); 704adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (c == this) 705adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new IllegalArgumentException(); 706adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (maxElements <= 0) 707adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return 0; 708adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 709adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 710adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 711a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int n = Math.min(size, maxElements); 712a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson for (int i = 0; i < n; i++) { 713a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson c.add((E) queue[0]); // In this order, in case add() throws. 714a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson dequeue(); 715adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 716adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return n; 717adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 718adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 719adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 720adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 721adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 722adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 723bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Atomically removes all of the elements from this queue. 724adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The queue will be empty after this call returns. 725adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 726adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void clear() { 727adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 728adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 729adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 7308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Object[] array = queue; 7318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n = size; 7328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson size = 0; 7338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (int i = 0; i < n; i++) 7348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson array[i] = null; 735adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 736adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 737adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 738adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 739adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 740bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 741e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Returns an array containing all of the elements in this queue. 742e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * The returned array elements are in no particular order. 743e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 744e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <p>The returned array will be "safe" in that no references to it are 745e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * maintained by this queue. (In other words, this method must allocate 746e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * a new array). The caller is thus free to modify the returned array. 747e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 748e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <p>This method acts as bridge between array-based and collection-based 749e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * APIs. 750e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 751e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return an array containing all of the elements in this queue 752e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 753e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public Object[] toArray() { 754e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final ReentrantLock lock = this.lock; 755e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak lock.lock(); 756e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak try { 757e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return Arrays.copyOf(queue, size); 758e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } finally { 759e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak lock.unlock(); 760e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 761e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 762e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 763e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 764bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Returns an array containing all of the elements in this queue; the 765bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * runtime type of the returned array is that of the specified array. 766bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The returned array elements are in no particular order. 767bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * If the queue fits in the specified array, it is returned therein. 768bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Otherwise, a new array is allocated with the runtime type of the 769bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * specified array and the size of this queue. 770bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 771bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>If this queue fits in the specified array with room to spare 772bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (i.e., the array has more elements than this queue), the element in 773bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * the array immediately following the end of the queue is set to 7748eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code null}. 775bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 776bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * <p>Like the {@link #toArray()} method, this method acts as bridge between 777bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * array-based and collection-based APIs. Further, this method allows 778bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * precise control over the runtime type of the output array, and may, 779bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * under certain circumstances, be used to save allocation costs. 780bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 7818eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>Suppose {@code x} is a queue known to contain only strings. 782bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * The following code can be used to dump the queue into a newly 7838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * allocated array of {@code String}: 784bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 785e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 786bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 7878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Note that {@code toArray(new Object[0])} is identical in function to 7888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * {@code toArray()}. 789bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 790bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @param a the array into which the elements of the queue are to 791bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * be stored, if it is big enough; otherwise, a new array of the 792bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * same runtime type is allocated for this purpose 793bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an array containing all of the elements in this queue 794bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws ArrayStoreException if the runtime type of the specified array 795bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * is not a supertype of the runtime type of every element in 796bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * this queue 797bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @throws NullPointerException if the specified array is null 798bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 799adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public <T> T[] toArray(T[] a) { 800adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project final ReentrantLock lock = this.lock; 801adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 802adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 8038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson int n = size; 8048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (a.length < n) 8058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Make a new array of a's runtime type, but my contents: 8068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return (T[]) Arrays.copyOf(queue, size, a.getClass()); 8078eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson System.arraycopy(queue, 0, a, 0, n); 8088eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (a.length > n) 8098eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson a[n] = null; 8108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return a; 811adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 812adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 813adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 814adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 815adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 816adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 817adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns an iterator over the elements in this queue. The 818adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * iterator does not return the elements in any particular order. 8198eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 820e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <p>The returned iterator is 821e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 822adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 823bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * @return an iterator over the elements in this queue 824adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 825adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Iterator<E> iterator() { 826bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return new Itr(toArray()); 827adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 828adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 829bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson /** 830bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Snapshot iterator that works off copy of underlying q array. 831bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson */ 8328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final class Itr implements Iterator<E> { 833bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson final Object[] array; // Array of all elements 834a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson int cursor; // index of next element to return 835bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson int lastRet; // index of last element, or -1 if no such 836bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson 837bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson Itr(Object[] array) { 838bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lastRet = -1; 839bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson this.array = array; 840adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 841adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 842adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean hasNext() { 843bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return cursor < array.length; 844adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 845adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 846adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E next() { 847bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (cursor >= array.length) 848bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson throw new NoSuchElementException(); 849bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lastRet = cursor; 850bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson return (E)array[cursor++]; 851adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 852adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 853adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void remove() { 854bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson if (lastRet < 0) 855bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson throw new IllegalStateException(); 8568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson removeEQ(array[lastRet]); 857bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson lastRet = -1; 858adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 859adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 860adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 861adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 86291770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Saves this queue to a stream (that is, serializes it). 86391770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * 86491770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * For compatibility with previous version of this class, elements 86591770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * are first copied to a java.util.PriorityQueue, which is then 86691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * serialized. 867e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 868e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param s the stream 869e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws java.io.IOException if an I/O error occurs 870adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 871adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void writeObject(java.io.ObjectOutputStream s) 872adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws java.io.IOException { 873adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.lock(); 874adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 875a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // avoid zero capacity argument 876a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson q = new PriorityQueue<E>(Math.max(size, 1), comparator); 8778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson q.addAll(this); 878adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project s.defaultWriteObject(); 879adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } finally { 8808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson q = null; 881adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project lock.unlock(); 882adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 883adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 884adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 8858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 88691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Reconstitutes this queue from a stream (that is, deserializes it). 887e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param s the stream 888e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws ClassNotFoundException if the class of a serialized object 889e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * could not be found 890e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws java.io.IOException if an I/O error occurs 8918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 8928eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private void readObject(java.io.ObjectInputStream s) 8938eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throws java.io.IOException, ClassNotFoundException { 8948eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 8958eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson s.defaultReadObject(); 8968eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.queue = new Object[q.size()]; 8978eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson comparator = q.comparator(); 8988eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson addAll(q); 8998eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } finally { 9008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson q = null; 9018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 9028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 9038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 904e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // Similar to Collections.ArraySnapshotSpliterator but avoids 905e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // commitment to toArray until needed 906e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak static final class PBQSpliterator<E> implements Spliterator<E> { 907e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final PriorityBlockingQueue<E> queue; 908e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Object[] array; 909e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak int index; 910e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak int fence; 911e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 912e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak PBQSpliterator(PriorityBlockingQueue<E> queue, Object[] array, 913e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak int index, int fence) { 914e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak this.queue = queue; 915e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak this.array = array; 916e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak this.index = index; 917e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak this.fence = fence; 918e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 919e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 920e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final int getFence() { 921e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak int hi; 922e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((hi = fence) < 0) 923e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak hi = fence = (array = queue.toArray()).length; 924e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return hi; 925e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 926e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 927e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public PBQSpliterator<E> trySplit() { 928e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; 929e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return (lo >= mid) ? null : 930e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak new PBQSpliterator<E>(queue, array, lo, index = mid); 931e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 932e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 933e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak @SuppressWarnings("unchecked") 934e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public void forEachRemaining(Consumer<? super E> action) { 935e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Object[] a; int i, hi; // hoist accesses and checks from loop 936e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (action == null) 937e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throw new NullPointerException(); 938e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((a = array) == null) 939e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak fence = (a = queue.toArray()).length; 940e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((hi = fence) <= a.length && 941e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (i = index) >= 0 && i < (index = hi)) { 942e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak do { action.accept((E)a[i]); } while (++i < hi); 943e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 944e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 945e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 946e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public boolean tryAdvance(Consumer<? super E> action) { 947e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (action == null) 948e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throw new NullPointerException(); 949e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (getFence() > index && index >= 0) { 950e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak @SuppressWarnings("unchecked") E e = (E) array[index++]; 951e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak action.accept(e); 952e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return true; 953e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 954e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return false; 955e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 956e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 957e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public long estimateSize() { return (long)(getFence() - index); } 958e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 959e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public int characteristics() { 960e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return Spliterator.NONNULL | Spliterator.SIZED | Spliterator.SUBSIZED; 961e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 962e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 963e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 964e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 965e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Returns a {@link Spliterator} over the elements in this queue. 966e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 967e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <p>The returned spliterator is 968e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 969e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 970e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and 971e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * {@link Spliterator#NONNULL}. 972e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 973e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @implNote 974e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * The {@code Spliterator} additionally reports {@link Spliterator#SUBSIZED}. 975e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 976e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return a {@code Spliterator} over the elements in this queue 977e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @since 1.8 978e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 979e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public Spliterator<E> spliterator() { 980e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return new PBQSpliterator<E>(this, null, 0, -1); 981e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 982e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 9838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Unsafe mechanics 984e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 985e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final long ALLOCATIONSPINLOCK; 986a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson static { 9878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 988e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak ALLOCATIONSPINLOCK = U.objectFieldOffset 989e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (PriorityBlockingQueue.class.getDeclaredField("allocationSpinLock")); 990e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } catch (ReflectiveOperationException e) { 991a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throw new Error(e); 9928eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 9938eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 994adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 995