ViewVC Help

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

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

Comparing jsr166/src/jdk7/java/util/PriorityQueue.java (file contents):
Revision 1.4 by jsr166, Fri Apr 11 21:15:44 2014 UTC vs.
Revision 1.5 by jsr166, Sat Oct 15 18:41:31 2016 UTC

#	Line 1 | Line 1
1		/*
2	<	* Copyright (c) 2003, 2006, Oracle and/or its affiliates. All rights reserved.
2	>	* Copyright (c) 2003, 2013, 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 75 | Line 75 | package java.util;
75		*
76		* @since 1.5
77		* @author Josh Bloch, Doug Lea
78	<	* @param <E> the type of elements held in this collection
78	>	* @param <E> the type of elements held in this queue
79		*/
80	–	@SuppressWarnings("unchecked")
80		public class PriorityQueue<E> extends AbstractQueue<E>
81		implements java.io.Serializable {
82
#	Line 93 | Line 92 | public class PriorityQueue<E> extends Ab
92		* heap and each descendant d of n, n <= d.  The element with the
93		* lowest value is in queue[0], assuming the queue is nonempty.
94		*/
95	<	private transient Object[] queue;
95	>	transient Object[] queue; // non-private to simplify nested class access
96
97		/**
98		* The number of elements in the priority queue.
99		*/
100	<	private int size;
100	>	int size;
101
102		/**
103		* The comparator, or null if priority queue uses elements'
#	Line 110 | Line 109 | public class PriorityQueue<E> extends Ab
109		* The number of times this priority queue has been
110		* <i>structurally modified</i>.  See AbstractList for gory details.
111		*/
112	<	private transient int modCount;
112	>	transient int modCount;     // non-private to simplify nested class access
113
114		/**
115		* Creates a {@code PriorityQueue} with the default initial
#	Line 135 | Line 134 | public class PriorityQueue<E> extends Ab
134		}
135
136		/**
137	+	* Creates a {@code PriorityQueue} with the default initial capacity and
138	+	* whose elements are ordered according to the specified comparator.
139	+	*
140	+	* @param  comparator the comparator that will be used to order this
141	+	*         priority queue.  If {@code null}, the {@linkplain Comparable
142	+	*         natural ordering} of the elements will be used.
143	+	* @since 1.8
144	+	*/
145	+	public PriorityQueue(Comparator<? super E> comparator) {
146	+	this(DEFAULT_INITIAL_CAPACITY, comparator);
147	+	}
148	+
149	+	/**
150		* Creates a {@code PriorityQueue} with the specified initial capacity
151		* that orders its elements according to the specified comparator.
152		*
#	Line 244 | Line 256 | public class PriorityQueue<E> extends Ab
256		a = Arrays.copyOf(a, a.length, Object[].class);
257		int len = a.length;
258		if (len == 1 || this.comparator != null)
259	<	for (int i = 0; i < len; i++)
260	<	if (a[i] == null)
259	>	for (Object e : a)
260	>	if (e == null)
261		throw new NullPointerException();
262		this.queue = a;
263		this.size = a.length;
#	Line 323 | Line 335 | public class PriorityQueue<E> extends Ab
335		int i = size;
336		if (i >= queue.length)
337		grow(i + 1);
338	+	siftUp(i, e);
339		size = i + 1;
327	–	if (i == 0)
328	–	queue[0] = e;
329	–	else
330	–	siftUp(i, e);
340		return true;
341		}
342
343	+	@SuppressWarnings("unchecked")
344		public E peek() {
345		return (size == 0) ? null : (E) queue[0];
346		}
#	Line 391 | Line 401 | public class PriorityQueue<E> extends Ab
401		* @return {@code true} if this queue contains the specified element
402		*/
403		public boolean contains(Object o) {
404	<	return indexOf(o) != -1;
404	>	return indexOf(o) >= 0;
405		}
406
407		/**
#	Line 433 | Line 443 | public class PriorityQueue<E> extends Ab
443		* The following code can be used to dump the queue into a newly
444		* allocated array of {@code String}:
445		*
446	<	*  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
446	>	* <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
447		*
448		* Note that {@code toArray(new Object[0])} is identical in function to
449		* {@code toArray()}.
#	Line 447 | Line 457 | public class PriorityQueue<E> extends Ab
457		*         this queue
458		* @throws NullPointerException if the specified array is null
459		*/
460	+	@SuppressWarnings("unchecked")
461		public <T> T[] toArray(T[] a) {
462		final int size = this.size;
463		if (a.length < size)
#	Line 513 | Line 524 | public class PriorityQueue<E> extends Ab
524		(forgetMeNot != null && !forgetMeNot.isEmpty());
525		}
526
527	+	@SuppressWarnings("unchecked")
528		public E next() {
529		if (expectedModCount != modCount)
530		throw new ConcurrentModificationException();
#	Line 565 | Line 577 | public class PriorityQueue<E> extends Ab
577		size = 0;
578		}
579
580	+	@SuppressWarnings("unchecked")
581		public E poll() {
582		if (size == 0)
583		return null;
#	Line 590 | Line 603 | public class PriorityQueue<E> extends Ab
603		* position before i. This fact is used by iterator.remove so as to
604		* avoid missing traversing elements.
605		*/
606	<	private E removeAt(int i) {
606	>	@SuppressWarnings("unchecked")
607	>	E removeAt(int i) {
608		// assert i >= 0 && i < size;
609		modCount++;
610		int s = --size;
#	Line 628 | Line 642 | public class PriorityQueue<E> extends Ab
642		siftUpComparable(k, x);
643		}
644
645	+	@SuppressWarnings("unchecked")
646		private void siftUpComparable(int k, E x) {
647		Comparable<? super E> key = (Comparable<? super E>) x;
648		while (k > 0) {
#	Line 641 | Line 656 | public class PriorityQueue<E> extends Ab
656		queue[k] = key;
657		}
658
659	+	@SuppressWarnings("unchecked")
660		private void siftUpUsingComparator(int k, E x) {
661		while (k > 0) {
662		int parent = (k - 1) >>> 1;
#	Line 668 | Line 684 | public class PriorityQueue<E> extends Ab
684		siftDownComparable(k, x);
685		}
686
687	+	@SuppressWarnings("unchecked")
688		private void siftDownComparable(int k, E x) {
689		Comparable<? super E> key = (Comparable<? super E>)x;
690		int half = size >>> 1;        // loop while a non-leaf
#	Line 686 | Line 703 | public class PriorityQueue<E> extends Ab
703		queue[k] = key;
704		}
705
706	+	@SuppressWarnings("unchecked")
707		private void siftDownUsingComparator(int k, E x) {
708		int half = size >>> 1;
709		while (k < half) {
#	Line 707 | Line 725 | public class PriorityQueue<E> extends Ab
725		* Establishes the heap invariant (described above) in the entire tree,
726		* assuming nothing about the order of the elements prior to the call.
727		*/
728	+	@SuppressWarnings("unchecked")
729		private void heapify() {
730		for (int i = (size >>> 1) - 1; i >= 0; i--)
731		siftDown(i, (E) queue[i]);
#	Line 728 | Line 747 | public class PriorityQueue<E> extends Ab
747		/**
748		* Saves this queue to a stream (that is, serializes it).
749		*
750	+	* @param s the stream
751	+	* @throws java.io.IOException if an I/O error occurs
752		* @serialData The length of the array backing the instance is
753		*             emitted (int), followed by all of its elements
754		*             (each an {@code Object}) in the proper order.
#	Line 746 | Line 767 | public class PriorityQueue<E> extends Ab
767		}
768
769		/**
770	<	* Reconstitutes this queue from a stream (that is, deserializes it).
770	>	* Reconstitutes the {@code PriorityQueue} instance from a stream
771	>	* (that is, deserializes it).
772	>	*
773	>	* @param s the stream
774	>	* @throws ClassNotFoundException if the class of a serialized object
775	>	*         could not be found
776	>	* @throws java.io.IOException if an I/O error occurs
777		*/
778		private void readObject(java.io.ObjectInputStream s)
779		throws java.io.IOException, ClassNotFoundException {

Diff Legend

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