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.67 by jsr166, Sun May 20 07:54:01 2007 UTC vs.
Revision 1.79 by jsr166, Sat Dec 15 22:26:29 2012 UTC

#	Line 1 | Line 1
1		/*
2	<	* Copyright 2003-2006 Sun Microsystems, Inc.  All Rights Reserved.
2	>	* Copyright (c) 2003, 2006, 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
#	Line 18 | Line 18
18		* 2 along with this work; if not, write to the Free Software Foundation,
19		* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20		*
21	<	* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22	<	* CA 95054 USA or visit www.sun.com if you need additional information or
23	<	* have any questions.
21	>	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22	>	* or visit www.oracle.com if you need additional information or have any
23	>	* questions.
24		*/
25
26		package java.util;
#	Line 56 | Line 56 | package java.util;
56		* the priority queue in any particular order. If you need ordered
57		* traversal, consider using {@code Arrays.sort(pq.toArray())}.
58		*
59	<	* <p> <strong>Note that this implementation is not synchronized.</strong>
59	>	* <p><strong>Note that this implementation is not synchronized.</strong>
60		* Multiple threads should not access a {@code PriorityQueue}
61		* instance concurrently if any of the threads modifies the queue.
62		* Instead, use the thread-safe {@link
63		* java.util.concurrent.PriorityBlockingQueue} class.
64		*
65		* <p>Implementation note: this implementation provides
66	<	* O(log(n)) time for the enqueing and dequeing methods
66	>	* O(log(n)) time for the enqueuing and dequeuing methods
67		* ({@code offer}, {@code poll}, {@code remove()} and {@code add});
68		* linear time for the {@code remove(Object)} and {@code contains(Object)}
69		* methods; and constant time for the retrieval methods
#	Line 74 | Line 74 | package java.util;
74		* Java Collections Framework</a>.
75		*
76		* @since 1.5
77	–	* @version %I%, %G%
77		* @author Josh Bloch, Doug Lea
78		* @param <E> the type of elements held in this collection
79		*/
80	+	@SuppressWarnings("unchecked")
81		public class PriorityQueue<E> extends AbstractQueue<E>
82		implements java.io.Serializable {
83
#	Line 171 | Line 171 | public class PriorityQueue<E> extends Ab
171		* @throws NullPointerException if the specified collection or any
172		*         of its elements are null
173		*/
174	+	@SuppressWarnings("unchecked")
175		public PriorityQueue(Collection<? extends E> c) {
176	<	initFromCollection(c);
177	<	if (c instanceof SortedSet)
178	<	comparator = (Comparator<? super E>)
179	<	((SortedSet<? extends E>)c).comparator();
180	<	else if (c instanceof PriorityQueue)
181	<	comparator = (Comparator<? super E>)
182	<	((PriorityQueue<? extends E>)c).comparator();
176	>	if (c instanceof SortedSet<?>) {
177	>	SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
178	>	this.comparator = (Comparator<? super E>) ss.comparator();
179	>	initElementsFromCollection(ss);
180	>	}
181	>	else if (c instanceof PriorityQueue<?>) {
182	>	PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
183	>	this.comparator = (Comparator<? super E>) pq.comparator();
184	>	initFromPriorityQueue(pq);
185	>	}
186		else {
187	<	comparator = null;
188	<	heapify();
187	>	this.comparator = null;
188	>	initFromCollection(c);
189		}
190		}
191
#	Line 199 | Line 203 | public class PriorityQueue<E> extends Ab
203		* @throws NullPointerException if the specified priority queue or any
204		*         of its elements are null
205		*/
206	+	@SuppressWarnings("unchecked")
207		public PriorityQueue(PriorityQueue<? extends E> c) {
208	<	comparator = (Comparator<? super E>)c.comparator();
209	<	initFromCollection(c);
208	>	this.comparator = (Comparator<? super E>) c.comparator();
209	>	initFromPriorityQueue(c);
210		}
211
212		/**
#	Line 217 | Line 222 | public class PriorityQueue<E> extends Ab
222		* @throws NullPointerException if the specified sorted set or any
223		*         of its elements are null
224		*/
225	+	@SuppressWarnings("unchecked")
226		public PriorityQueue(SortedSet<? extends E> c) {
227	<	comparator = (Comparator<? super E>)c.comparator();
228	<	initFromCollection(c);
227	>	this.comparator = (Comparator<? super E>) c.comparator();
228	>	initElementsFromCollection(c);
229	>	}
230	>
231	>	private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
232	>	if (c.getClass() == PriorityQueue.class) {
233	>	this.queue = c.toArray();
234	>	this.size = c.size();
235	>	} else {
236	>	initFromCollection(c);
237	>	}
238	>	}
239	>
240	>	private void initElementsFromCollection(Collection<? extends E> c) {
241	>	Object[] a = c.toArray();
242	>	// If c.toArray incorrectly doesn't return Object[], copy it.
243	>	if (a.getClass() != Object[].class)
244	>	a = Arrays.copyOf(a, a.length, Object[].class);
245	>	int len = a.length;
246	>	if (len == 1 || this.comparator != null)
247	>	for (int i = 0; i < len; i++)
248	>	if (a[i] == null)
249	>	throw new NullPointerException();
250	>	this.queue = a;
251	>	this.size = a.length;
252		}
253
254		/**
#	Line 228 | Line 257 | public class PriorityQueue<E> extends Ab
257		* @param c the collection
258		*/
259		private void initFromCollection(Collection<? extends E> c) {
260	<	Object[] a = c.toArray();
261	<	// If c.toArray incorrectly doesn't return Object[], copy it.
233	<	if (a.getClass() != Object[].class)
234	<	a = Arrays.copyOf(a, a.length, Object[].class);
235	<	queue = a;
236	<	size = a.length;
260	>	initElementsFromCollection(c);
261	>	heapify();
262		}
263
264		/**
265	+	* The maximum size of array to allocate.
266	+	* Some VMs reserve some header words in an array.
267	+	* Attempts to allocate larger arrays may result in
268	+	* OutOfMemoryError: Requested array size exceeds VM limit
269	+	*/
270	+	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
271	+
272	+	/**
273		* Increases the capacity of the array.
274		*
275		* @param minCapacity the desired minimum capacity
276		*/
277		private void grow(int minCapacity) {
278	<	if (minCapacity < 0) // overflow
246	<	throw new OutOfMemoryError();
247	<	int oldCapacity = queue.length;
278	>	int oldCapacity = queue.length;
279		// Double size if small; else grow by 50%
280	<	int newCapacity = ((oldCapacity < 64)?
281	<	((oldCapacity + 1) * 2):
282	<	((oldCapacity / 2) * 3));
283	<	if (newCapacity < 0) // overflow
284	<	newCapacity = Integer.MAX_VALUE;
285	<	if (newCapacity < minCapacity)
255	<	newCapacity = minCapacity;
280	>	int newCapacity = oldCapacity + ((oldCapacity < 64) ?
281	>	(oldCapacity + 2) :
282	>	(oldCapacity >> 1));
283	>	// overflow-conscious code
284	>	if (newCapacity - MAX_ARRAY_SIZE > 0)
285	>	newCapacity = hugeCapacity(minCapacity);
286		queue = Arrays.copyOf(queue, newCapacity);
287		}
288
289	+	private static int hugeCapacity(int minCapacity) {
290	+	if (minCapacity < 0) // overflow
291	+	throw new OutOfMemoryError();
292	+	return (minCapacity > MAX_ARRAY_SIZE) ?
293	+	Integer.MAX_VALUE :
294	+	MAX_ARRAY_SIZE;
295	+	}
296	+
297		/**
298		* Inserts the specified element into this priority queue.
299		*
#	Line 294 | Line 332 | public class PriorityQueue<E> extends Ab
332		}
333
334		public E peek() {
335	<	if (size == 0)
298	<	return null;
299	<	return (E) queue[0];
335	>	return (size == 0) ? null : (E) queue[0];
336		}
337
338		private int indexOf(Object o) {
339	<	if (o != null) {
339	>	if (o != null) {
340		for (int i = 0; i < size; i++)
341		if (o.equals(queue[i]))
342		return i;
#	Line 320 | Line 356 | public class PriorityQueue<E> extends Ab
356		* @return {@code true} if this queue changed as a result of the call
357		*/
358		public boolean remove(Object o) {
359	<	int i = indexOf(o);
360	<	if (i == -1)
361	<	return false;
362	<	else {
363	<	removeAt(i);
364	<	return true;
365	<	}
359	>	int i = indexOf(o);
360	>	if (i == -1)
361	>	return false;
362	>	else {
363	>	removeAt(i);
364	>	return true;
365	>	}
366		}
367
368		/**
#	Line 337 | Line 373 | public class PriorityQueue<E> extends Ab
373		* @return {@code true} if removed
374		*/
375		boolean removeEq(Object o) {
376	<	for (int i = 0; i < size; i++) {
377	<	if (o == queue[i]) {
376	>	for (int i = 0; i < size; i++) {
377	>	if (o == queue[i]) {
378		removeAt(i);
379		return true;
380		}
#	Line 355 | Line 391 | public class PriorityQueue<E> extends Ab
391		* @return {@code true} if this queue contains the specified element
392		*/
393		public boolean contains(Object o) {
394	<	return indexOf(o) != -1;
394	>	return indexOf(o) != -1;
395		}
396
397		/**
#	Line 397 | Line 433 | public class PriorityQueue<E> extends Ab
433		* The following code can be used to dump the queue into a newly
434		* allocated array of <tt>String</tt>:
435		*
436	<	* <pre>
401	<	*     String[] y = x.toArray(new String[0]);</pre>
436	>	*  <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
437		*
438		* Note that <tt>toArray(new Object[0])</tt> is identical in function to
439		* <tt>toArray()</tt>.
#	Line 416 | Line 451 | public class PriorityQueue<E> extends Ab
451		if (a.length < size)
452		// Make a new array of a's runtime type, but my contents:
453		return (T[]) Arrays.copyOf(queue, size, a.getClass());
454	<	System.arraycopy(queue, 0, a, 0, size);
454	>	System.arraycopy(queue, 0, a, 0, size);
455		if (a.length > size)
456		a[size] = null;
457		return a;
#	Line 509 | Line 544 | public class PriorityQueue<E> extends Ab
544		lastRetElt = null;
545		} else {
546		throw new IllegalStateException();
547	<	}
547	>	}
548		expectedModCount = modCount;
549		}
550		}
#	Line 555 | Line 590 | public class PriorityQueue<E> extends Ab
590		* avoid missing traversing elements.
591		*/
592		private E removeAt(int i) {
593	<	assert i >= 0 && i < size;
593	>	// assert i >= 0 && i < size;
594		modCount++;
595		int s = --size;
596		if (s == i) // removed last element
#	Line 690 | Line 725 | public class PriorityQueue<E> extends Ab
725		}
726
727		/**
728	<	* Saves the state of the instance to a stream (that
694	<	* is, serializes it).
728	>	* Saves this queue to a stream (that is, serializes it).
729		*
730		* @serialData The length of the array backing the instance is
731		*             emitted (int), followed by all of its elements
732		*             (each an {@code Object}) in the proper order.
699	–	* @param s the stream
733		*/
734		private void writeObject(java.io.ObjectOutputStream s)
735	<	throws java.io.IOException{
735	>	throws java.io.IOException {
736		// Write out element count, and any hidden stuff
737		s.defaultWriteObject();
738
#	Line 712 | Line 745 | public class PriorityQueue<E> extends Ab
745		}
746
747		/**
748	<	* Reconstitutes the {@code PriorityQueue} instance from a stream
716	<	* (that is, deserializes it).
717	<	*
718	<	* @param s the stream
748	>	* Reconstitutes this queue from a stream (that is, deserializes it).
749		*/
750		private void readObject(java.io.ObjectInputStream s)
751		throws java.io.IOException, ClassNotFoundException {
#	Line 725 | Line 755 | public class PriorityQueue<E> extends Ab
755		// Read in (and discard) array length
756		s.readInt();
757
758	<	queue = new Object[size];
758	>	queue = new Object[size];
759
760		// Read in all elements.
761		for (int i = 0; i < size; i++)
762		queue[i] = s.readObject();
763
764	<	// Elements are guaranteed to be in "proper order", but the
765	<	// spec has never explained what that might be.
766	<	heapify();
764	>	// Elements are guaranteed to be in "proper order", but the
765	>	// spec has never explained what that might be.
766	>	heapify();
767		}
768		}

Diff Legend

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