151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski/* 24c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * Copyright (c) 2003, 2013, Oracle and/or its affiliates. All rights reserved. 351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This code is free software; you can redistribute it and/or modify it 651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * under the terms of the GNU General Public License version 2 only, as 751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * published by the Free Software Foundation. Oracle designates this 851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * particular file as subject to the "Classpath" exception as provided 951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * by Oracle in the LICENSE file that accompanied this code. 1051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 1151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This code is distributed in the hope that it will be useful, but WITHOUT 1251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * version 2 for more details (a copy is included in the LICENSE file that 1551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * accompanied this code). 1651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 1751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * You should have received a copy of the GNU General Public License version 1851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 2 along with this work; if not, write to the Free Software Foundation, 1951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 2151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * or visit www.oracle.com if you need additional information or have any 2351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * questions. 2451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 2551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 2651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskipackage java.util; 2751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 284c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamathimport java.util.function.Consumer; 294c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath 3051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski/** 3151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * An unbounded priority {@linkplain Queue queue} based on a priority heap. 3251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The elements of the priority queue are ordered according to their 3351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@linkplain Comparable natural ordering}, or by a {@link Comparator} 3451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * provided at queue construction time, depending on which constructor is 3551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * used. A priority queue does not permit {@code null} elements. 3651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * A priority queue relying on natural ordering also does not permit 3751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * insertion of non-comparable objects (doing so may result in 3851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code ClassCastException}). 3951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 4051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>The <em>head</em> of this queue is the <em>least</em> element 4151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * with respect to the specified ordering. If multiple elements are 4251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * tied for least value, the head is one of those elements -- ties are 4351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * broken arbitrarily. The queue retrieval operations {@code poll}, 4451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code remove}, {@code peek}, and {@code element} access the 4551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * element at the head of the queue. 4651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 4751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>A priority queue is unbounded, but has an internal 4851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <i>capacity</i> governing the size of an array used to store the 4951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * elements on the queue. It is always at least as large as the queue 5051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * size. As elements are added to a priority queue, its capacity 5151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * grows automatically. The details of the growth policy are not 5251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * specified. 5351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 5451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This class and its iterator implement all of the 5551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <em>optional</em> methods of the {@link Collection} and {@link 5651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Iterator} interfaces. The Iterator provided in method {@link 5751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * #iterator()} is <em>not</em> guaranteed to traverse the elements of 5851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the priority queue in any particular order. If you need ordered 5951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * traversal, consider using {@code Arrays.sort(pq.toArray())}. 6051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 614c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * <p><strong>Note that this implementation is not synchronized.</strong> 6251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Multiple threads should not access a {@code PriorityQueue} 6351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * instance concurrently if any of the threads modifies the queue. 6451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Instead, use the thread-safe {@link 6551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * java.util.concurrent.PriorityBlockingQueue} class. 6651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 6751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>Implementation note: this implementation provides 684c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * O(log(n)) time for the enqueuing and dequeuing methods 6951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ({@code offer}, {@code poll}, {@code remove()} and {@code add}); 7051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * linear time for the {@code remove(Object)} and {@code contains(Object)} 7151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * methods; and constant time for the retrieval methods 7251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ({@code peek}, {@code element}, and {@code size}). 7351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 7451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This class is a member of the 75d2449bb576ad1e3a3877364e5e1ae28625f69e35Yi Kong * <a href="{@docRoot}openjdk-redirect.html?v=8&path=/technotes/guides/collections/index.html"> 7651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Java Collections Framework</a>. 7751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 7851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @since 1.5 7951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @author Josh Bloch, Doug Lea 80e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param <E> the type of elements held in this queue 8151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 8251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskipublic class PriorityQueue<E> extends AbstractQueue<E> 8351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski implements java.io.Serializable { 8451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 8551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final long serialVersionUID = -7720805057305804111L; 8651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 8751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final int DEFAULT_INITIAL_CAPACITY = 11; 8851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 8951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 9051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Priority queue represented as a balanced binary heap: the two 9151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The 9251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * priority queue is ordered by comparator, or by the elements' 9351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * natural ordering, if comparator is null: For each node n in the 9451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * heap and each descendant d of n, n <= d. The element with the 9551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * lowest value is in queue[0], assuming the queue is nonempty. 9651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 974c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath transient Object[] queue; // non-private to simplify nested class access 9851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 9951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 10051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The number of elements in the priority queue. 10151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 102e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak int size; 10351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 10451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 10551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The comparator, or null if priority queue uses elements' 10651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * natural ordering. 10751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 10851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private final Comparator<? super E> comparator; 10951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 11051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 11151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The number of times this priority queue has been 11251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <i>structurally modified</i>. See AbstractList for gory details. 11351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 114e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak transient int modCount; // non-private to simplify nested class access 11551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 11651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 11751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Creates a {@code PriorityQueue} with the default initial 11851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * capacity (11) that orders its elements according to their 11951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@linkplain Comparable natural ordering}. 12051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 12151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public PriorityQueue() { 12251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this(DEFAULT_INITIAL_CAPACITY, null); 12351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 12451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 12551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 12651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Creates a {@code PriorityQueue} with the specified initial 12751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * capacity that orders its elements according to their 12851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@linkplain Comparable natural ordering}. 12951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 13051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param initialCapacity the initial capacity for this priority queue 13151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if {@code initialCapacity} is less 13251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * than 1 13351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 13451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public PriorityQueue(int initialCapacity) { 13551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this(initialCapacity, null); 13651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 13751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 13851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 1394c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * Creates a {@code PriorityQueue} with the default initial capacity and 1404c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * whose elements are ordered according to the specified comparator. 1414c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * 1424c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * @param comparator the comparator that will be used to order this 1434c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * priority queue. If {@code null}, the {@linkplain Comparable 1444c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * natural ordering} of the elements will be used. 1454c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * @since 1.8 1464c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath */ 1474c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath public PriorityQueue(Comparator<? super E> comparator) { 1484c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath this(DEFAULT_INITIAL_CAPACITY, comparator); 1494c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath } 1504c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath 1514c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath /** 15251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Creates a {@code PriorityQueue} with the specified initial capacity 15351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * that orders its elements according to the specified comparator. 15451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 15551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param initialCapacity the initial capacity for this priority queue 15651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param comparator the comparator that will be used to order this 15751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * priority queue. If {@code null}, the {@linkplain Comparable 15851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * natural ordering} of the elements will be used. 15951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if {@code initialCapacity} is 16051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * less than 1 16151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 16251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public PriorityQueue(int initialCapacity, 16351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Comparator<? super E> comparator) { 16451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Note: This restriction of at least one is not actually needed, 16551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // but continues for 1.5 compatibility 16651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (initialCapacity < 1) 16751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new IllegalArgumentException(); 16851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.queue = new Object[initialCapacity]; 16951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.comparator = comparator; 17051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 17151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 17251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 17351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Creates a {@code PriorityQueue} containing the elements in the 17451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * specified collection. If the specified collection is an instance of 17551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * a {@link SortedSet} or is another {@code PriorityQueue}, this 17651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * priority queue will be ordered according to the same ordering. 17751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Otherwise, this priority queue will be ordered according to the 17851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@linkplain Comparable natural ordering} of its elements. 17951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 18051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param c the collection whose elements are to be placed 18151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * into this priority queue 18251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if elements of the specified collection 18351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * cannot be compared to one another according to the priority 18451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * queue's ordering 18551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified collection or any 18651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of its elements are null 18751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 18851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski @SuppressWarnings("unchecked") 18951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public PriorityQueue(Collection<? extends E> c) { 19051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (c instanceof SortedSet<?>) { 19151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski SortedSet<? extends E> ss = (SortedSet<? extends E>) c; 19251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.comparator = (Comparator<? super E>) ss.comparator(); 19351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski initElementsFromCollection(ss); 19451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 19551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else if (c instanceof PriorityQueue<?>) { 19651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c; 19751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.comparator = (Comparator<? super E>) pq.comparator(); 19851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski initFromPriorityQueue(pq); 19951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 20051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else { 20151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.comparator = null; 20251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski initFromCollection(c); 20351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 20451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 20551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 20651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 20751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Creates a {@code PriorityQueue} containing the elements in the 20851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * specified priority queue. This priority queue will be 20951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ordered according to the same ordering as the given priority 21051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * queue. 21151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 21251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param c the priority queue whose elements are to be placed 21351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * into this priority queue 21451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if elements of {@code c} cannot be 21551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * compared to one another according to {@code c}'s 21651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ordering 21751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified priority queue or any 21851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of its elements are null 21951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 22051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski @SuppressWarnings("unchecked") 22151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public PriorityQueue(PriorityQueue<? extends E> c) { 22251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.comparator = (Comparator<? super E>) c.comparator(); 22351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski initFromPriorityQueue(c); 22451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 22551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 22651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 22751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Creates a {@code PriorityQueue} containing the elements in the 22851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * specified sorted set. This priority queue will be ordered 22951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * according to the same ordering as the given sorted set. 23051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 23151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param c the sorted set whose elements are to be placed 23251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * into this priority queue 23351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if elements of the specified sorted 23451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * set cannot be compared to one another according to the 23551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * sorted set's ordering 23651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified sorted set or any 23751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of its elements are null 23851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 23951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski @SuppressWarnings("unchecked") 24051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public PriorityQueue(SortedSet<? extends E> c) { 24151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.comparator = (Comparator<? super E>) c.comparator(); 24251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski initElementsFromCollection(c); 24351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 24451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 24551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void initFromPriorityQueue(PriorityQueue<? extends E> c) { 24651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (c.getClass() == PriorityQueue.class) { 24751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.queue = c.toArray(); 24851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.size = c.size(); 24951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { 25051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski initFromCollection(c); 25151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 25251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 25351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 25451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void initElementsFromCollection(Collection<? extends E> c) { 25551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Object[] a = c.toArray(); 25651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // If c.toArray incorrectly doesn't return Object[], copy it. 25751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (a.getClass() != Object[].class) 25851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a = Arrays.copyOf(a, a.length, Object[].class); 25951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int len = a.length; 26051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (len == 1 || this.comparator != null) 261e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (Object e : a) 262e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (e == null) 26351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new NullPointerException(); 26451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.queue = a; 26551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.size = a.length; 26651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 26751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 26851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 26951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Initializes queue array with elements from the given Collection. 27051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 27151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param c the collection 27251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 27351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void initFromCollection(Collection<? extends E> c) { 27451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski initElementsFromCollection(c); 27551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski heapify(); 27651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 27751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 27851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 27951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The maximum size of array to allocate. 28051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Some VMs reserve some header words in an array. 28151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Attempts to allocate larger arrays may result in 28251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * OutOfMemoryError: Requested array size exceeds VM limit 28351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 28451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 28551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 28651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 28751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Increases the capacity of the array. 28851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 28951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param minCapacity the desired minimum capacity 29051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 29151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void grow(int minCapacity) { 29251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int oldCapacity = queue.length; 29351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Double size if small; else grow by 50% 29451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int newCapacity = oldCapacity + ((oldCapacity < 64) ? 29551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski (oldCapacity + 2) : 29651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski (oldCapacity >> 1)); 29751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // overflow-conscious code 29851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (newCapacity - MAX_ARRAY_SIZE > 0) 29951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski newCapacity = hugeCapacity(minCapacity); 30051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski queue = Arrays.copyOf(queue, newCapacity); 30151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 30251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 30351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private static int hugeCapacity(int minCapacity) { 30451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (minCapacity < 0) // overflow 30551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new OutOfMemoryError(); 30651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return (minCapacity > MAX_ARRAY_SIZE) ? 30751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Integer.MAX_VALUE : 30851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski MAX_ARRAY_SIZE; 30951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 31051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 31151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 31251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inserts the specified element into this priority queue. 31351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 31451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return {@code true} (as specified by {@link Collection#add}) 31551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the specified element cannot be 31651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * compared with elements currently in this priority queue 31751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * according to the priority queue's ordering 31851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null 31951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 32051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean add(E e) { 32151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return offer(e); 32251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 32351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 32451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 32551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inserts the specified element into this priority queue. 32651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 32751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return {@code true} (as specified by {@link Queue#offer}) 32851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the specified element cannot be 32951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * compared with elements currently in this priority queue 33051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * according to the priority queue's ordering 33151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null 33251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 33351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean offer(E e) { 33451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (e == null) 33551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new NullPointerException(); 33651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski modCount++; 33751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int i = size; 33851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (i >= queue.length) 33951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski grow(i + 1); 34051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size = i + 1; 34151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (i == 0) 34251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski queue[0] = e; 34351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 34451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski siftUp(i, e); 34551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return true; 34651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 34751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 3484c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath @SuppressWarnings("unchecked") 34951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public E peek() { 3504c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath return (size == 0) ? null : (E) queue[0]; 35151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 35251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 35351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private int indexOf(Object o) { 35451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (o != null) { 35551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = 0; i < size; i++) 35651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (o.equals(queue[i])) 35751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return i; 35851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 35951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return -1; 36051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 36151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 36251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 36351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Removes a single instance of the specified element from this queue, 36451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * if it is present. More formally, removes an element {@code e} such 36551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * that {@code o.equals(e)}, if this queue contains one or more such 36651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * elements. Returns {@code true} if and only if this queue contained 36751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the specified element (or equivalently, if this queue changed as a 36851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * result of the call). 36951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 37051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param o element to be removed from this queue, if present 37151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return {@code true} if this queue changed as a result of the call 37251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 37351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean remove(Object o) { 37451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int i = indexOf(o); 37551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (i == -1) 37651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return false; 37751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else { 37851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski removeAt(i); 37951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return true; 38051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 38151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 38251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 38351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 38451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Version of remove using reference equality, not equals. 38551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Needed by iterator.remove. 38651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 38751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param o element to be removed from this queue, if present 38851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return {@code true} if removed 38951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 39051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean removeEq(Object o) { 39151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = 0; i < size; i++) { 39251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (o == queue[i]) { 39351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski removeAt(i); 39451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return true; 39551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 39651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 39751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return false; 39851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 39951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 40051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 40151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns {@code true} if this queue contains the specified element. 40251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * More formally, returns {@code true} if and only if this queue contains 40351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * at least one element {@code e} such that {@code o.equals(e)}. 40451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 40551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param o object to be checked for containment in this queue 40651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return {@code true} if this queue contains the specified element 40751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 40851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean contains(Object o) { 409e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return indexOf(o) >= 0; 41051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 41151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 41251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 41351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns an array containing all of the elements in this queue. 41451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The elements are in no particular order. 41551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 41651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>The returned array will be "safe" in that no references to it are 41751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * maintained by this queue. (In other words, this method must allocate 41851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * a new array). The caller is thus free to modify the returned array. 41951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 42051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method acts as bridge between array-based and collection-based 42151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * APIs. 42251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 42351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return an array containing all of the elements in this queue 42451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 42551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public Object[] toArray() { 42651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return Arrays.copyOf(queue, size); 42751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 42851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 42951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 43051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns an array containing all of the elements in this queue; the 43151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * runtime type of the returned array is that of the specified array. 43251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The returned array elements are in no particular order. 43351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * If the queue fits in the specified array, it is returned therein. 43451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Otherwise, a new array is allocated with the runtime type of the 43551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * specified array and the size of this queue. 43651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 43751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>If the queue fits in the specified array with room to spare 43851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (i.e., the array has more elements than the queue), the element in 43951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the array immediately following the end of the collection is set to 44051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code null}. 44151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 44251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>Like the {@link #toArray()} method, this method acts as bridge between 44351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * array-based and collection-based APIs. Further, this method allows 44451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * precise control over the runtime type of the output array, and may, 44551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * under certain circumstances, be used to save allocation costs. 44651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 4474c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * <p>Suppose {@code x} is a queue known to contain only strings. 44851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The following code can be used to dump the queue into a newly 4494c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * allocated array of {@code String}: 45051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 451e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 45251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 4534c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * Note that {@code toArray(new Object[0])} is identical in function to 4544c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * {@code toArray()}. 45551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 45651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param a the array into which the elements of the queue are to 45751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * be stored, if it is big enough; otherwise, a new array of the 45851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * same runtime type is allocated for this purpose. 45951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return an array containing all of the elements in this queue 46051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ArrayStoreException if the runtime type of the specified array 46151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * is not a supertype of the runtime type of every element in 46251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * this queue 46351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified array is null 46451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 4654c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath @SuppressWarnings("unchecked") 46651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public <T> T[] toArray(T[] a) { 4674c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath final int size = this.size; 46851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (a.length < size) 46951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Make a new array of a's runtime type, but my contents: 47051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return (T[]) Arrays.copyOf(queue, size, a.getClass()); 47151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski System.arraycopy(queue, 0, a, 0, size); 47251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (a.length > size) 47351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski a[size] = null; 47451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return a; 47551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 47651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 47751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 47851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns an iterator over the elements in this queue. The iterator 47951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * does not return the elements in any particular order. 48051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 48151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return an iterator over the elements in this queue 48251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 48351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public Iterator<E> iterator() { 48451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return new Itr(); 48551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 48651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 48751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private final class Itr implements Iterator<E> { 48851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 48951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Index (into queue array) of element to be returned by 49051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * subsequent call to next. 49151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 492e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private int cursor; 49351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 49451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 49551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Index of element returned by most recent call to next, 49651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * unless that element came from the forgetMeNot list. 49751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Set to -1 if element is deleted by a call to remove. 49851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 49951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private int lastRet = -1; 50051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 50151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 50251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * A queue of elements that were moved from the unvisited portion of 50351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the heap into the visited portion as a result of "unlucky" element 50451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * removals during the iteration. (Unlucky element removals are those 50551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * that require a siftup instead of a siftdown.) We must visit all of 50651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the elements in this list to complete the iteration. We do this 50751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * after we've completed the "normal" iteration. 50851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 50951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * We expect that most iterations, even those involving removals, 51051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * will not need to store elements in this field. 51151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 512e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private ArrayDeque<E> forgetMeNot; 51351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 51451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 51551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Element returned by the most recent call to next iff that 51651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * element was drawn from the forgetMeNot list. 51751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 518e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private E lastRetElt; 51951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 52051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 52151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The modCount value that the iterator believes that the backing 52251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Queue should have. If this expectation is violated, the iterator 52351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * has detected concurrent modification. 52451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 52551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private int expectedModCount = modCount; 52651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 52751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean hasNext() { 52851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return cursor < size || 52951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski (forgetMeNot != null && !forgetMeNot.isEmpty()); 53051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 53151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 5324c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath @SuppressWarnings("unchecked") 53351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public E next() { 53451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (expectedModCount != modCount) 53551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new ConcurrentModificationException(); 53651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (cursor < size) 53751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return (E) queue[lastRet = cursor++]; 53851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (forgetMeNot != null) { 53951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastRet = -1; 54051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastRetElt = forgetMeNot.poll(); 54151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (lastRetElt != null) 54251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return lastRetElt; 54351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 54451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new NoSuchElementException(); 54551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 54651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 54751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void remove() { 54851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (expectedModCount != modCount) 54951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new ConcurrentModificationException(); 55051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (lastRet != -1) { 55151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E moved = PriorityQueue.this.removeAt(lastRet); 55251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastRet = -1; 55351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (moved == null) 55451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski cursor--; 55551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else { 55651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (forgetMeNot == null) 55751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski forgetMeNot = new ArrayDeque<>(); 55851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski forgetMeNot.add(moved); 55951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 56051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else if (lastRetElt != null) { 56151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski PriorityQueue.this.removeEq(lastRetElt); 56251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastRetElt = null; 56351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { 56451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new IllegalStateException(); 56551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 56651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski expectedModCount = modCount; 56751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 56851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 56951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 57051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public int size() { 57151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return size; 57251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 57351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 57451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 57551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Removes all of the elements from this priority queue. 57651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The queue will be empty after this call returns. 57751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 57851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void clear() { 57951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski modCount++; 58051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = 0; i < size; i++) 58151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski queue[i] = null; 58251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size = 0; 58351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 58451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 5854c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath @SuppressWarnings("unchecked") 58651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public E poll() { 58751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (size == 0) 58851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return null; 58951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int s = --size; 59051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski modCount++; 59151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E result = (E) queue[0]; 59251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E x = (E) queue[s]; 59351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski queue[s] = null; 59451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (s != 0) 59551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski siftDown(0, x); 59651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return result; 59751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 59851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 59951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 60051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Removes the ith element from queue. 60151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 60251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Normally this method leaves the elements at up to i-1, 60351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * inclusive, untouched. Under these circumstances, it returns 60451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * null. Occasionally, in order to maintain the heap invariant, 60551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * it must swap a later element of the list with one earlier than 60651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * i. Under these circumstances, this method returns the element 60751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * that was previously at the end of the list and is now at some 60851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * position before i. This fact is used by iterator.remove so as to 60951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * avoid missing traversing elements. 61051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 6114c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath @SuppressWarnings("unchecked") 612e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak E removeAt(int i) { 613e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // assert i >= 0 && i < size; 61451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski modCount++; 61551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int s = --size; 61651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (s == i) // removed last element 61751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski queue[i] = null; 61851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else { 61951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E moved = (E) queue[s]; 62051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski queue[s] = null; 62151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski siftDown(i, moved); 62251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (queue[i] == moved) { 62351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski siftUp(i, moved); 62451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (queue[i] != moved) 62551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return moved; 62651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 62751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 62851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return null; 62951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 63051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 63151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 63251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inserts item x at position k, maintaining heap invariant by 63351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * promoting x up the tree until it is greater than or equal to 63451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * its parent, or is the root. 63551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 63651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * To simplify and speed up coercions and comparisons. the 63751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Comparable and Comparator versions are separated into different 63851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * methods that are otherwise identical. (Similarly for siftDown.) 63951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 64051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param k the position to fill 64151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param x the item to insert 64251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 64351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void siftUp(int k, E x) { 64451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (comparator != null) 64551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski siftUpUsingComparator(k, x); 64651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 64751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski siftUpComparable(k, x); 64851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 64951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 6504c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath @SuppressWarnings("unchecked") 65151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void siftUpComparable(int k, E x) { 65251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Comparable<? super E> key = (Comparable<? super E>) x; 65351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (k > 0) { 65451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int parent = (k - 1) >>> 1; 65551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Object e = queue[parent]; 65651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (key.compareTo((E) e) >= 0) 65751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 65851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski queue[k] = e; 65951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski k = parent; 66051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 66151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski queue[k] = key; 66251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 66351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 6644c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath @SuppressWarnings("unchecked") 66551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void siftUpUsingComparator(int k, E x) { 66651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (k > 0) { 66751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int parent = (k - 1) >>> 1; 66851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Object e = queue[parent]; 66951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (comparator.compare(x, (E) e) >= 0) 67051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 67151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski queue[k] = e; 67251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski k = parent; 67351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 67451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski queue[k] = x; 67551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 67651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 67751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 67851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inserts item x at position k, maintaining heap invariant by 67951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * demoting x down the tree repeatedly until it is less than or 68051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * equal to its children or is a leaf. 68151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 68251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param k the position to fill 68351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param x the item to insert 68451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 68551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void siftDown(int k, E x) { 68651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (comparator != null) 68751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski siftDownUsingComparator(k, x); 68851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 68951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski siftDownComparable(k, x); 69051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 69151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 6924c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath @SuppressWarnings("unchecked") 69351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void siftDownComparable(int k, E x) { 69451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Comparable<? super E> key = (Comparable<? super E>)x; 69551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int half = size >>> 1; // loop while a non-leaf 69651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (k < half) { 69751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int child = (k << 1) + 1; // assume left child is least 69851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Object c = queue[child]; 69951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int right = child + 1; 70051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (right < size && 70151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) 70251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski c = queue[child = right]; 70351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (key.compareTo((E) c) <= 0) 70451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 70551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski queue[k] = c; 70651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski k = child; 70751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 70851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski queue[k] = key; 70951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 71051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 7114c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath @SuppressWarnings("unchecked") 71251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void siftDownUsingComparator(int k, E x) { 71351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int half = size >>> 1; 71451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (k < half) { 71551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int child = (k << 1) + 1; 71651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Object c = queue[child]; 71751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int right = child + 1; 71851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (right < size && 71951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski comparator.compare((E) c, (E) queue[right]) > 0) 72051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski c = queue[child = right]; 72151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (comparator.compare(x, (E) c) <= 0) 72251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski break; 72351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski queue[k] = c; 72451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski k = child; 72551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 72651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski queue[k] = x; 72751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 72851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 72951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 73051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Establishes the heap invariant (described above) in the entire tree, 73151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * assuming nothing about the order of the elements prior to the call. 73251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 7334c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath @SuppressWarnings("unchecked") 73451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void heapify() { 73551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = (size >>> 1) - 1; i >= 0; i--) 73651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski siftDown(i, (E) queue[i]); 73751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 73851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 73951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 74051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns the comparator used to order the elements in this 74151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * queue, or {@code null} if this queue is sorted according to 74251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the {@linkplain Comparable natural ordering} of its elements. 74351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 74451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the comparator used to order this queue, or 74551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code null} if this queue is sorted according to the 74651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * natural ordering of its elements 74751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 74851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public Comparator<? super E> comparator() { 74951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return comparator; 75051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 75151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 75251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 7534c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * Saves this queue to a stream (that is, serializes it). 75451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 75551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @serialData The length of the array backing the instance is 75651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * emitted (int), followed by all of its elements 75751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (each an {@code Object}) in the proper order. 75851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param s the stream 759e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws java.io.IOException if an I/O error occurs 76051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 76151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void writeObject(java.io.ObjectOutputStream s) 7624c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath throws java.io.IOException { 76351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Write out element count, and any hidden stuff 76451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski s.defaultWriteObject(); 76551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 76651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Write out array length, for compatibility with 1.5 version 76751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski s.writeInt(Math.max(2, size + 1)); 76851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 76951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Write out all elements in the "proper order". 77051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = 0; i < size; i++) 77151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski s.writeObject(queue[i]); 77251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 77351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 77451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 77551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Reconstitutes the {@code PriorityQueue} instance from a stream 77651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (that is, deserializes it). 77751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 77851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param s the stream 779e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws ClassNotFoundException if the class of a serialized object 780e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * could not be found 781e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws java.io.IOException if an I/O error occurs 78251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 78351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void readObject(java.io.ObjectInputStream s) 78451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throws java.io.IOException, ClassNotFoundException { 78551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Read in size, and any hidden stuff 78651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski s.defaultReadObject(); 78751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 78851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Read in (and discard) array length 78951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski s.readInt(); 79051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 79151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski queue = new Object[size]; 79251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 79351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Read in all elements. 79451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i = 0; i < size; i++) 79551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski queue[i] = s.readObject(); 79651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 79751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Elements are guaranteed to be in "proper order", but the 79851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // spec has never explained what that might be. 79951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski heapify(); 80051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 8014c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath 8024c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath /** 8034c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em> 8044c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * and <em>fail-fast</em> {@link Spliterator} over the elements in this 8054c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * queue. 8064c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * 8074c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * <p>The {@code Spliterator} reports {@link Spliterator#SIZED}, 8084c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * {@link Spliterator#SUBSIZED}, and {@link Spliterator#NONNULL}. 8094c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * Overriding implementations should document the reporting of additional 8104c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * characteristic values. 8114c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * 8124c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * @return a {@code Spliterator} over the elements in this queue 8134c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * @since 1.8 8144c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath */ 8154c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath public final Spliterator<E> spliterator() { 816e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return new PriorityQueueSpliterator<>(this, 0, -1, 0); 8174c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath } 8184c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath 8194c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath static final class PriorityQueueSpliterator<E> implements Spliterator<E> { 8204c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath /* 8214c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * This is very similar to ArrayList Spliterator, except for 8224c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath * extra null checks. 8234c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath */ 8244c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath private final PriorityQueue<E> pq; 8254c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath private int index; // current index, modified on advance/split 8264c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath private int fence; // -1 until first use 8274c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath private int expectedModCount; // initialized when fence set 8284c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath 829e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** Creates new spliterator covering the given range. */ 8304c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence, 831e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak int expectedModCount) { 8324c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath this.pq = pq; 8334c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath this.index = origin; 8344c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath this.fence = fence; 8354c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath this.expectedModCount = expectedModCount; 8364c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath } 8374c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath 8384c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath private int getFence() { // initialize fence to size on first use 8394c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath int hi; 8404c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath if ((hi = fence) < 0) { 8414c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath expectedModCount = pq.modCount; 8424c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath hi = fence = pq.size; 8434c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath } 8444c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath return hi; 8454c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath } 8464c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath 8474c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath public PriorityQueueSpliterator<E> trySplit() { 8484c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; 8494c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath return (lo >= mid) ? null : 850e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak new PriorityQueueSpliterator<>(pq, lo, index = mid, 851e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak expectedModCount); 8524c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath } 8534c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath 8544c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath @SuppressWarnings("unchecked") 8554c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath public void forEachRemaining(Consumer<? super E> action) { 8564c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath int i, hi, mc; // hoist accesses and checks from loop 8574c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath PriorityQueue<E> q; Object[] a; 8584c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath if (action == null) 8594c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath throw new NullPointerException(); 8604c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath if ((q = pq) != null && (a = q.queue) != null) { 8614c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath if ((hi = fence) < 0) { 8624c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath mc = q.modCount; 8634c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath hi = q.size; 8644c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath } 8654c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath else 8664c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath mc = expectedModCount; 8674c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath if ((i = index) >= 0 && (index = hi) <= a.length) { 8684c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath for (E e;; ++i) { 8694c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath if (i < hi) { 8704c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath if ((e = (E) a[i]) == null) // must be CME 8714c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath break; 8724c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath action.accept(e); 8734c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath } 8744c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath else if (q.modCount != mc) 8754c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath break; 8764c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath else 8774c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath return; 8784c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath } 8794c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath } 8804c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath } 8814c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath throw new ConcurrentModificationException(); 8824c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath } 8834c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath 8844c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath public boolean tryAdvance(Consumer<? super E> action) { 8854c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath if (action == null) 8864c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath throw new NullPointerException(); 8874c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath int hi = getFence(), lo = index; 8884c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath if (lo >= 0 && lo < hi) { 8894c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath index = lo + 1; 8904c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath @SuppressWarnings("unchecked") E e = (E)pq.queue[lo]; 8914c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath if (e == null) 8924c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath throw new ConcurrentModificationException(); 8934c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath action.accept(e); 8944c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath if (pq.modCount != expectedModCount) 8954c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath throw new ConcurrentModificationException(); 8964c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath return true; 8974c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath } 8984c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath return false; 8994c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath } 9004c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath 9014c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath public long estimateSize() { 9024c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath return (long) (getFence() - index); 9034c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath } 9044c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath 9054c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath public int characteristics() { 9064c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL; 9074c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath } 9084c89023ef86f29fa9add7db2574f2169fe842577Narayan Kamath } 90951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski} 910