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.37 by dl, Sat Aug 30 11:44:53 2003 UTC vs.
Revision 1.44 by dl, Sat Oct 18 12:29:27 2003 UTC

#	Line 1 | Line 1
1	<	package java.util;
1	>	/*
2	>	* %W% %E%
3	>	*
4	>	* Copyright 2003 Sun Microsystems, Inc. All rights reserved.
5	>	* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6	>	*/
7	>
8	>	package java.util;
9
10		/**
11	<	* An unbounded priority {@linkplain Queue queue} based on a priority heap.
12	<	* This queue orders elements according to an order specified at construction
13	<	* time, which is specified in the same manner as {@link java.util.TreeSet}
14	<	* and {@link java.util.TreeMap}: elements are ordered either according to
15	<	* their <i>natural order</i> (see {@link Comparable}), or according to a
16	<	* {@link java.util.Comparator}, depending on which constructor is used.
17	<	* <p>The <em>head</em> of this queue is the <em>least</em> element with
18	<	* respect to the specified ordering.  If multiple elements are tied for least
19	<	* value, the head is one of those elements. A priority queue does not permit
13	<	* <tt>null</tt> elements.
14	<	*
15	<	* <p>The {@link #remove()} and {@link #poll()} methods remove and
16	<	* return the head of the queue.
11	>	* An unbounded priority {@linkplain Queue queue} based on a priority
12	>	* heap.  This queue orders elements according to an order specified
13	>	* at construction time, which is specified either according to their
14	>	* <i>natural order</i> (see {@link Comparable}), or according to a
15	>	* {@link java.util.Comparator}, depending on which constructor is
16	>	* used. A priority queue does not permit <tt>null</tt> elements.
17	>	* A priority queue relying on natural ordering also does not
18	>	* permit insertion of non-comparable objects (doing so may result
19	>	* in <tt>ClassCastException</tt>).
20		*
21	<	* <p>The {@link #element()} and {@link #peek()} methods return, but do
22	<	* not delete, the head of the queue.
21	>	* <p>The <em>head</em> of this queue is the <em>least</em> element
22	>	* with respect to the specified ordering.  If multiple elements are
23	>	* tied for least value, the head is one of those elements -- ties are
24	>	* broken arbitrarily.  The queue retrieval operations <tt>poll</tt>,
25	>	* <tt>remove</tt>, <tt>peek</tt>, and <tt>element</tt> access the
26	>	* element at the head of the queue.
27		*
28	<	* <p>A priority queue has a <i>capacity</i>.  The capacity is the
29	<	* size of the array used internally to store the elements on the
30	<	* queue.
31	<	* It is always at least as large as the queue size.  As
32	<	* elements are added to a priority queue, its capacity grows
33	<	* automatically.  The details of the growth policy are not specified.
28	>	* <p>A priority queue is unbounded, but has an internal
29	>	* <i>capacity</i> governing the size of an array used to store the
30	>	* elements on the queue.  It is always at least as large as the queue
31	>	* size.  As elements are added to a priority queue, its capacity
32	>	* grows automatically.  The details of the growth policy are not
33	>	* specified.
34		*
35	<	* <p>The Iterator provided in method {@link #iterator()} is <em>not</em>
35	>	* <p>This class implements all of the <em>optional</em> methods of
36	>	* the {@link Collection} and {@link Iterator} interfaces.  The
37	>	* Iterator provided in method {@link #iterator()} is <em>not</em>
38		* guaranteed to traverse the elements of the PriorityQueue in any
39		* particular order. If you need ordered traversal, consider using
40		* <tt>Arrays.sort(pq.toArray())</tt>.
#	Line 48 | Line 57
57		* <a href="{@docRoot}/../guide/collections/index.html">
58		* Java Collections Framework</a>.
59		* @since 1.5
60	+	* @version %I%, %G%
61		* @author Josh Bloch
62	+	* @param <E> the base class of all elements held in this collection
63		*/
64		public class PriorityQueue<E> extends AbstractQueue<E>
65		implements Queue<E>, java.io.Serializable {
#	Line 269 | Line 280 | public class PriorityQueue<E> extends Ab
280		}
281
282
272	–	// Queue Methods
273	–
283		/**
284	<	* Add the specified element to this priority queue.
284	>	* Inserts the specified element into this priority queue.
285		*
286		* @return <tt>true</tt>
287		* @throws ClassCastException if the specified element cannot be compared
#	Line 295 | Line 304 | public class PriorityQueue<E> extends Ab
304		return true;
305		}
306
307	<	public E poll() {
307	>	public E peek() {
308		if (size == 0)
309		return null;
301	–	return remove();
302	–	}
303	–
304	–	public E peek() {
310		return (E) queue[1];
311		}
312
#	Line 312 | Line 317 | public class PriorityQueue<E> extends Ab
317		* @return <tt>true</tt> (as per the general contract of
318		* <tt>Collection.add</tt>).
319		*
320	<	* @throws NullPointerException {@inheritDoc}
320	>	* @throws NullPointerException if the specified element is <tt>null</tt>.
321		* @throws ClassCastException if the specified element cannot be compared
322		* with elements currently in the priority queue according
323		* to the priority queue's ordering.
324		*/
325		public boolean add(E o) {
326	<	return super.add(o);
322	<	}
323	<
324	<
325	<	/**
326	<	* Adds all of the elements in the specified collection to this queue.
327	<	* The behavior of this operation is undefined if
328	<	* the specified collection is modified while the operation is in
329	<	* progress.  (This implies that the behavior of this call is undefined if
330	<	* the specified collection is this queue, and this queue is nonempty.)
331	<	* <p>
332	<	* This implementation iterates over the specified collection, and adds
333	<	* each object returned by the iterator to this collection, in turn.
334	<	* @throws NullPointerException {@inheritDoc}
335	<	* @throws ClassCastException if any element cannot be compared
336	<	* with elements currently in the priority queue according
337	<	* to the priority queue's ordering.
338	<	*/
339	<	public boolean addAll(Collection<? extends E> c) {
340	<	return super.addAll(c);
326	>	return offer(o);
327		}
328
343	–
344	–	/**
345	–	* Removes a single instance of the specified element from this
346	–	* queue, if it is present.  More formally,
347	–	* removes an element <tt>e</tt> such that <tt>(o==null ? e==null :
348	–	* o.equals(e))</tt>, if the queue contains one or more such
349	–	* elements.  Returns <tt>true</tt> if the queue contained the
350	–	* specified element (or equivalently, if the queue changed as a
351	–	* result of the call).
352	–	*
353	–	* <p>This implementation iterates over the queue looking for the
354	–	* specified element.  If it finds the element, it removes the element
355	–	* from the queue using the iterator's remove method.<p>
356	–	*
357	–	*/
329		public boolean remove(Object o) {
330		if (o == null)
331		return false;
#	Line 498 | Line 469 | public class PriorityQueue<E> extends Ab
469		size = 0;
470		}
471
472	<	/**
502	<	* Removes and returns the first element from queue.
503	<	*/
504	<	public E remove() {
472	>	public E poll() {
473		if (size == 0)
474	<	throw new NoSuchElementException();
474	>	return null;
475		modCount++;
476
477		E result = (E) queue[1];
#	Line 649 | Line 617 | public class PriorityQueue<E> extends Ab
617		s.writeInt(queue.length);
618
619		// Write out all elements in the proper order.
620	<	for (int i=0; i<size; i++)
620	>	for (int i=1; i<=size; i++)
621		s.writeObject(queue[i]);
622		}
623
#	Line 668 | Line 636 | public class PriorityQueue<E> extends Ab
636		queue = new Object[arrayLength];
637
638		// Read in all elements in the proper order.
639	<	for (int i=0; i<size; i++)
639	>	for (int i=1; i<=size; i++)
640		queue[i] = (E) s.readObject();
641		}
642

Diff Legend

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