ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/PriorityQueue.java

Comparing jsr166/src/main/java/util/PriorityQueue.java (file contents):
Revision 1.77 by jsr166, Mon Dec 12 20:53:11 2011 UTC vs.
Revision 1.100 by jsr166, Fri Aug 29 21:42:37 2014 UTC

#	Line 1 | Line 1
1		/*
2	<	* Copyright (c) 2003, 2006, Oracle and/or its affiliates. All rights reserved.
2	>	* Copyright (c) 2003, 2012, Oracle and/or its affiliates. All rights reserved.
3		* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4		*
5		* This code is free software; you can redistribute it and/or modify it
6		* under the terms of the GNU General Public License version 2 only, as
7	<	* published by the Free Software Foundation.  Sun designates this
7	>	* published by the Free Software Foundation.  Oracle designates this
8		* particular file as subject to the "Classpath" exception as provided
9	<	* by Sun in the LICENSE file that accompanied this code.
9	>	* by Oracle in the LICENSE file that accompanied this code.
10		*
11		* This code is distributed in the hope that it will be useful, but WITHOUT
12		* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
#	Line 24 | Line 24
24		*/
25
26		package java.util;
27	+	import java.util.function.Consumer;
28	+	import java.util.stream.Stream;
29
30		/**
31		* An unbounded priority {@linkplain Queue queue} based on a priority heap.
#	Line 56 | Line 58 | package java.util;
58		* the priority queue in any particular order. If you need ordered
59		* traversal, consider using {@code Arrays.sort(pq.toArray())}.
60		*
61	<	* <p> <strong>Note that this implementation is not synchronized.</strong>
61	>	* <p><strong>Note that this implementation is not synchronized.</strong>
62		* Multiple threads should not access a {@code PriorityQueue}
63		* instance concurrently if any of the threads modifies the queue.
64		* Instead, use the thread-safe {@link
65		* java.util.concurrent.PriorityBlockingQueue} class.
66		*
67		* <p>Implementation note: this implementation provides
68	<	* O(log(n)) time for the enqueing and dequeing methods
68	>	* O(log(n)) time for the enqueuing and dequeuing methods
69		* ({@code offer}, {@code poll}, {@code remove()} and {@code add});
70		* linear time for the {@code remove(Object)} and {@code contains(Object)}
71		* methods; and constant time for the retrieval methods
#	Line 77 | Line 79 | package java.util;
79		* @author Josh Bloch, Doug Lea
80		* @param <E> the type of elements held in this collection
81		*/
80	–	@SuppressWarnings("unchecked")
82		public class PriorityQueue<E> extends AbstractQueue<E>
83		implements java.io.Serializable {
84
#	Line 93 | Line 94 | public class PriorityQueue<E> extends Ab
94		* heap and each descendant d of n, n <= d.  The element with the
95		* lowest value is in queue[0], assuming the queue is nonempty.
96		*/
97	<	private transient Object[] queue;
97	>	transient Object[] queue; // non-private to simplify nested class access
98
99		/**
100		* The number of elements in the priority queue.
101		*/
102	<	private int size = 0;
102	>	private int size;
103
104		/**
105		* The comparator, or null if priority queue uses elements'
#	Line 110 | Line 111 | public class PriorityQueue<E> extends Ab
111		* The number of times this priority queue has been
112		* <i>structurally modified</i>.  See AbstractList for gory details.
113		*/
114	<	private transient int modCount = 0;
114	>	transient int modCount = 0; // non-private to simplify nested class access
115
116		/**
117		* Creates a {@code PriorityQueue} with the default initial
#	Line 331 | Line 332 | public class PriorityQueue<E> extends Ab
332		return true;
333		}
334
335	+	@SuppressWarnings("unchecked")
336		public E peek() {
337		return (size == 0) ? null : (E) queue[0];
338		}
#	Line 391 | Line 393 | public class PriorityQueue<E> extends Ab
393		* @return {@code true} if this queue contains the specified element
394		*/
395		public boolean contains(Object o) {
396	<	return indexOf(o) != -1;
396	>	return indexOf(o) >= 0;
397		}
398
399		/**
#	Line 429 | Line 431 | public class PriorityQueue<E> extends Ab
431		* precise control over the runtime type of the output array, and may,
432		* under certain circumstances, be used to save allocation costs.
433		*
434	<	* <p>Suppose <tt>x</tt> is a queue known to contain only strings.
434	>	* <p>Suppose {@code x} is a queue known to contain only strings.
435		* The following code can be used to dump the queue into a newly
436	<	* allocated array of <tt>String</tt>:
436	>	* allocated array of {@code String}:
437		*
438		*  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
439		*
440	<	* Note that <tt>toArray(new Object[0])</tt> is identical in function to
441	<	* <tt>toArray()</tt>.
440	>	* Note that {@code toArray(new Object[0])} is identical in function to
441	>	* {@code toArray()}.
442		*
443		* @param a the array into which the elements of the queue are to
444		*          be stored, if it is big enough; otherwise, a new array of the
#	Line 447 | Line 449 | public class PriorityQueue<E> extends Ab
449		*         this queue
450		* @throws NullPointerException if the specified array is null
451		*/
452	+	@SuppressWarnings("unchecked")
453		public <T> T[] toArray(T[] a) {
454	+	final int size = this.size;
455		if (a.length < size)
456		// Make a new array of a's runtime type, but my contents:
457		return (T[]) Arrays.copyOf(queue, size, a.getClass());
#	Line 472 | Line 476 | public class PriorityQueue<E> extends Ab
476		* Index (into queue array) of element to be returned by
477		* subsequent call to next.
478		*/
479	<	private int cursor = 0;
479	>	private int cursor;
480
481		/**
482		* Index of element returned by most recent call to next,
#	Line 492 | Line 496 | public class PriorityQueue<E> extends Ab
496		* We expect that most iterations, even those involving removals,
497		* will not need to store elements in this field.
498		*/
499	<	private ArrayDeque<E> forgetMeNot = null;
499	>	private ArrayDeque<E> forgetMeNot;
500
501		/**
502		* Element returned by the most recent call to next iff that
503		* element was drawn from the forgetMeNot list.
504		*/
505	<	private E lastRetElt = null;
505	>	private E lastRetElt;
506
507		/**
508		* The modCount value that the iterator believes that the backing
#	Line 512 | Line 516 | public class PriorityQueue<E> extends Ab
516		(forgetMeNot != null && !forgetMeNot.isEmpty());
517		}
518
519	+	@SuppressWarnings("unchecked")
520		public E next() {
521		if (expectedModCount != modCount)
522		throw new ConcurrentModificationException();
#	Line 536 | Line 541 | public class PriorityQueue<E> extends Ab
541		cursor--;
542		else {
543		if (forgetMeNot == null)
544	<	forgetMeNot = new ArrayDeque<E>();
544	>	forgetMeNot = new ArrayDeque<>();
545		forgetMeNot.add(moved);
546		}
547		} else if (lastRetElt != null) {
#	Line 564 | Line 569 | public class PriorityQueue<E> extends Ab
569		size = 0;
570		}
571
572	+	@SuppressWarnings("unchecked")
573		public E poll() {
574		if (size == 0)
575		return null;
#	Line 589 | Line 595 | public class PriorityQueue<E> extends Ab
595		* position before i. This fact is used by iterator.remove so as to
596		* avoid missing traversing elements.
597		*/
598	+	@SuppressWarnings("unchecked")
599		private E removeAt(int i) {
600		// assert i >= 0 && i < size;
601		modCount++;
#	Line 627 | Line 634 | public class PriorityQueue<E> extends Ab
634		siftUpComparable(k, x);
635		}
636
637	+	@SuppressWarnings("unchecked")
638		private void siftUpComparable(int k, E x) {
639		Comparable<? super E> key = (Comparable<? super E>) x;
640		while (k > 0) {
#	Line 640 | Line 648 | public class PriorityQueue<E> extends Ab
648		queue[k] = key;
649		}
650
651	+	@SuppressWarnings("unchecked")
652		private void siftUpUsingComparator(int k, E x) {
653		while (k > 0) {
654		int parent = (k - 1) >>> 1;
#	Line 667 | Line 676 | public class PriorityQueue<E> extends Ab
676		siftDownComparable(k, x);
677		}
678
679	+	@SuppressWarnings("unchecked")
680		private void siftDownComparable(int k, E x) {
681		Comparable<? super E> key = (Comparable<? super E>)x;
682		int half = size >>> 1;        // loop while a non-leaf
#	Line 685 | Line 695 | public class PriorityQueue<E> extends Ab
695		queue[k] = key;
696		}
697
698	+	@SuppressWarnings("unchecked")
699		private void siftDownUsingComparator(int k, E x) {
700		int half = size >>> 1;
701		while (k < half) {
#	Line 706 | Line 717 | public class PriorityQueue<E> extends Ab
717		* Establishes the heap invariant (described above) in the entire tree,
718		* assuming nothing about the order of the elements prior to the call.
719		*/
720	+	@SuppressWarnings("unchecked")
721		private void heapify() {
722		for (int i = (size >>> 1) - 1; i >= 0; i--)
723		siftDown(i, (E) queue[i]);
#	Line 730 | Line 742 | public class PriorityQueue<E> extends Ab
742		* @serialData The length of the array backing the instance is
743		*             emitted (int), followed by all of its elements
744		*             (each an {@code Object}) in the proper order.
745	+	* @param s the stream
746	+	* @throws java.io.IOException if an I/O error occurs
747		*/
748		private void writeObject(java.io.ObjectOutputStream s)
749		throws java.io.IOException {
#	Line 745 | Line 759 | public class PriorityQueue<E> extends Ab
759		}
760
761		/**
762	<	* Reconstitutes this queue from a stream (that is, deserializes it).
762	>	* Reconstitutes the {@code PriorityQueue} instance from a stream
763	>	* (that is, deserializes it).
764	>	*
765	>	* @param s the stream
766	>	* @throws ClassNotFoundException if the class of a serialized object
767	>	*         could not be found
768	>	* @throws java.io.IOException if an I/O error occurs
769		*/
770		private void readObject(java.io.ObjectInputStream s)
771		throws java.io.IOException, ClassNotFoundException {
#	Line 765 | Line 785 | public class PriorityQueue<E> extends Ab
785		// spec has never explained what that might be.
786		heapify();
787		}
788	+
789	+	public Spliterator<E> spliterator() {
790	+	return new PriorityQueueSpliterator<E>(this, 0, -1, 0);
791	+	}
792	+
793	+	/**
794	+	* This is very similar to ArrayList Spliterator, except for extra
795	+	* null checks.
796	+	*/
797	+	static final class PriorityQueueSpliterator<E> implements Spliterator<E> {
798	+	private final PriorityQueue<E> pq;
799	+	private int index;            // current index, modified on advance/split
800	+	private int fence;            // -1 until first use
801	+	private int expectedModCount; // initialized when fence set
802	+
803	+	/** Creates new spliterator covering the given range */
804	+	PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence,
805	+	int expectedModCount) {
806	+	this.pq = pq;
807	+	this.index = origin;
808	+	this.fence = fence;
809	+	this.expectedModCount = expectedModCount;
810	+	}
811	+
812	+	private int getFence() { // initialize fence to size on first use
813	+	int hi;
814	+	if ((hi = fence) < 0) {
815	+	expectedModCount = pq.modCount;
816	+	hi = fence = pq.size;
817	+	}
818	+	return hi;
819	+	}
820	+
821	+	public Spliterator<E> trySplit() {
822	+	int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
823	+	return (lo >= mid) ? null :
824	+	new PriorityQueueSpliterator<E>(pq, lo, index = mid,
825	+	expectedModCount);
826	+	}
827	+
828	+	@SuppressWarnings("unchecked")
829	+	public void forEachRemaining(Consumer<? super E> action) {
830	+	int i, hi, mc; // hoist accesses and checks from loop
831	+	PriorityQueue<E> q; Object[] a;
832	+	if (action == null)
833	+	throw new NullPointerException();
834	+	if ((q = pq) != null && (a = q.queue) != null) {
835	+	if ((hi = fence) < 0) {
836	+	mc = q.modCount;
837	+	hi = q.size;
838	+	}
839	+	else
840	+	mc = expectedModCount;
841	+	if ((i = index) >= 0 && (index = hi) <= a.length) {
842	+	for (E e;; ++i) {
843	+	if (i < hi) {
844	+	if ((e = (E) a[i]) == null) // must be CME
845	+	break;
846	+	action.accept(e);
847	+	}
848	+	else if (q.modCount != mc)
849	+	break;
850	+	else
851	+	return;
852	+	}
853	+	}
854	+	}
855	+	throw new ConcurrentModificationException();
856	+	}
857	+
858	+	public boolean tryAdvance(Consumer<? super E> action) {
859	+	int hi = getFence(), lo = index;
860	+	if (lo >= 0 && lo < hi) {
861	+	index = lo + 1;
862	+	@SuppressWarnings("unchecked") E e = (E)pq.queue[lo];
863	+	if (e == null)
864	+	throw new ConcurrentModificationException();
865	+	action.accept(e);
866	+	if (pq.modCount != expectedModCount)
867	+	throw new ConcurrentModificationException();
868	+	return true;
869	+	}
870	+	return false;
871	+	}
872	+
873	+	public long estimateSize() {
874	+	return (long) (getFence() - index);
875	+	}
876	+
877	+	public int characteristics() {
878	+	return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL;
879	+	}
880	+	}
881		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines