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.4 by tim, Mon May 19 02:45:07 2003 UTC vs.
Revision 1.6 by brian, Mon Jun 23 02:26:15 2003 UTC

#	Line 1 | Line 1
1		package java.util;
2
3	–	/*
4	–	* Todo
5	–	*
6	–	*   1) Make it serializable.
7	–	*/
8	–
3		/**
4		* An unbounded priority queue based on a priority heap.  This queue orders
5	<	* elements according to the order specified at creation time.  This order is
6	<	* specified as for {@link TreeSet} and {@link TreeMap}: Elements are ordered
5	>	* elements according to an order specified at construction time, which is
6	>	* specified in the same manner as {@link TreeSet} and {@link TreeMap}: elements are ordered
7		* either according to their <i>natural order</i> (see {@link Comparable}), or
8		* according to a {@link Comparator}, depending on which constructor is used.
9		* The {@link #peek}, {@link #poll}, and {@link #remove} methods return the
10		* minimal element with respect to the specified ordering.  If multiple
11	<	* these elements are tied for least value, no guarantees are made as to
12	<	* which of elements is returned.
11	>	* elements are tied for least value, no guarantees are made as to
12	>	* which of these elements is returned.
13		*
14	<	* <p>Each priority queue has a <i>capacity</i>.  The capacity is the size of
15	<	* the array used to store the elements on the queue.  It is always at least
16	<	* as large as the queue size.  As elements are added to a priority list,
14	>	* <p>A priority queue has a <i>capacity</i>.  The capacity is the size of
15	>	* the array used internally to store the elements on the queue.  It is always at least
16	>	* as large as the queue size.  As elements are added to a priority queue,
17		* its capacity grows automatically.  The details of the growth policy are not
18		* specified.
19		*
20		*<p>Implementation note: this implementation provides O(log(n)) time for
21	<	* the <tt>offer</tt>, <tt>poll</tt>, <tt>remove()</tt> and <tt>add</tt>
21	>	* the insertion methods (<tt>offer</tt>, <tt>poll</tt>, <tt>remove()</tt> and <tt>add</tt>)
22		* methods; linear time for the <tt>remove(Object)</tt> and
23	<	* <tt>contains</tt> methods; and constant time for the <tt>peek</tt>,
24	<	* <tt>element</tt>, and <tt>size</tt> methods.
23	>	* <tt>contains(Object)</tt> methods; and constant time for the retrieval methods (<tt>peek</tt>,
24	>	* <tt>element</tt>, and <tt>size</tt>).
25		*
26		* <p>This class is a member of the
27		* <a href="{@docRoot}/../guide/collections/index.html">
#	Line 42 | Line 36 | public class PriorityQueue<E> extends Ab
36		* Priority queue represented as a balanced binary heap: the two children
37		* of queue[n] are queue[2*n] and queue[2*n + 1].  The priority queue is
38		* ordered by comparator, or by the elements' natural ordering, if
39	<	* comparator is null:  For each node n in the heap, and each descendant
40	<	* of n, d, n <= d.
39	>	* comparator is null:  For each node n in the heap and each descendant d
40	>	* of n, n <= d.
41		*
42	<	* The element with the lowest value is in queue[1] (assuming the queue is
43	<	* nonempty). A one-based array is used in preference to the traditional
44	<	* zero-based array to simplify parent and child calculations.
42	>	* The element with the lowest value is in queue[1], assuming the queue is
43	>	* nonempty.  (A one-based array is used in preference to the traditional
44	>	* zero-based array to simplify parent and child calculations.)
45		*
46		* queue.length must be >= 2, even if size == 0.
47		*/
48	<	private E[] queue;
48	>	private transient E[] queue;
49
50		/**
51		* The number of elements in the priority queue.
#	Line 68 | Line 62 | public class PriorityQueue<E> extends Ab
62		* The number of times this priority queue has been
63		* <i>structurally modified</i>.  See AbstractList for gory details.
64		*/
65	<	private int modCount = 0;
65	>	private transient int modCount = 0;
66
67		/**
68		* Create a new priority queue with the default initial capacity (11)
69	<	* that orders its elements according to their natural ordering.
69	>	* that orders its elements according to their natural ordering (using <tt>Comparable</tt>.)
70		*/
71		public PriorityQueue() {
72		this(DEFAULT_INITIAL_CAPACITY);
#	Line 80 | Line 74 | public class PriorityQueue<E> extends Ab
74
75		/**
76		* Create a new priority queue with the specified initial capacity
77	<	* that orders its elements according to their natural ordering.
77	>	* that orders its elements according to their natural ordering (using <tt>Comparable</tt>.)
78		*
79		* @param initialCapacity the initial capacity for this priority queue.
80		*/
#	Line 109 | Line 103 | public class PriorityQueue<E> extends Ab
103		* implements the {@link Sorted} interface, the priority queue will be
104		* sorted according to the same comparator, or according to its elements'
105		* natural order if the collection is sorted according to its elements'
106	<	* natural order.  If the specified collection does not implement the
107	<	* <tt>Sorted</tt> interface, the priority queue is ordered according to
106	>	* natural order.  If the specified collection does not implement
107	>	* <tt>Sorted</tt>, the priority queue is ordered according to
108		* its elements' natural order.
109		*
110		* @param initialElements the collection whose elements are to be placed
#	Line 129 | Line 123 | public class PriorityQueue<E> extends Ab
123		initialCapacity = 1;
124		queue = new E[initialCapacity + 1];
125
126	+	/* Commented out to compile with generics compiler
127	+
128		if (initialElements instanceof Sorted) {
129		comparator = ((Sorted)initialElements).comparator();
130		for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
131		queue[++size] = i.next();
132		} else {
133	+	*/
134	+	{
135		comparator = null;
136		for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
137		add(i.next());
#	Line 144 | Line 142 | public class PriorityQueue<E> extends Ab
142
143		/**
144		* Remove and return the minimal element from this priority queue if
145	<	* it contains one or more elements, otherwise <tt>null</tt>.  The term
145	>	* it contains one or more elements, otherwise return <tt>null</tt>.  The term
146		* <i>minimal</i> is defined according to this priority queue's order.
147		*
148		* @return the minimal element from this priority queue if it contains
#	Line 158 | Line 156 | public class PriorityQueue<E> extends Ab
156
157		/**
158		* Return, but do not remove, the minimal element from the priority queue,
159	<	* or <tt>null</tt> if the queue is empty.  The term <i>minimal</i> is
159	>	* or return <tt>null</tt> if the queue is empty.  The term <i>minimal</i> is
160		* defined according to this priority queue's order.  This method returns
161		* the same object reference that would be returned by by the
162	<	* <tt>poll</tt> method.  The two methods differ in that this method
162	>	* <tt>poll</tt> method.  The two methods differ in that this method
163		* does not remove the element from the priority queue.
164		*
165		* @return the minimal element from this priority queue if it contains
#	Line 179 | Line 177 | public class PriorityQueue<E> extends Ab
177		* specified element (or equivalently, if this collection changed as a
178		* result of the call).
179		*
180	<	* @param o element to be removed from this collection, if present.
180	>	* @param element the element to be removed from this collection, if present.
181		* @return <tt>true</tt> if this collection changed as a result of the
182		*         call
183		* @throws ClassCastException if the specified element cannot be compared
184	<	*            with elements currently in the priority queue according
184	>	*            with elements currently in the priority queue according
185		*            to the priority queue's ordering.
186		* @throws NullPointerException if the specified element is null.
187		*/
#	Line 211 | Line 209 | public class PriorityQueue<E> extends Ab
209
210		/**
211		* Returns an iterator over the elements in this priority queue.  The
212	<	* first element returned by this iterator is the same element that
213	<	* would be returned by a call to <tt>peek</tt>.
214	<	*
212	>	* elements of the priority queue will be returned by this iterator in the
213	>	* order specified by the queue, which is to say the order they would be
214	>	* returned by repeated calls to <tt>poll</tt>.
215	>	*
216		* @return an <tt>Iterator</tt> over the elements in this priority queue.
217		*/
218		public Iterator<E> iterator() {
219	<	return new Itr();
219	>	return new Itr();
220		}
221
222		private class Itr implements Iterator<E> {
223	<	/**
224	<	* Index (into queue array) of element to be returned by
223	>	/**
224	>	* Index (into queue array) of element to be returned by
225		* subsequent call to next.
226	<	*/
227	<	int cursor = 1;
229	<
230	<	/**
231	<	* Index of element returned by most recent call to next or
232	<	* previous.  Reset to 0 if this element is deleted by a call
233	<	* to remove.
234	<	*/
235	<	int lastRet = 0;
236	<
237	<	/**
238	<	* The modCount value that the iterator believes that the backing
239	<	* List should have.  If this expectation is violated, the iterator
240	<	* has detected concurrent modification.
241	<	*/
242	<	int expectedModCount = modCount;
226	>	*/
227	>	int cursor = 1;
228
229	<	public boolean hasNext() {
230	<	return cursor <= size;
231	<	}
229	>	/**
230	>	* Index of element returned by most recent call to next or
231	>	* previous.  Reset to 0 if this element is deleted by a call
232	>	* to remove.
233	>	*/
234	>	int lastRet = 0;
235	>
236	>	/**
237	>	* The modCount value that the iterator believes that the backing
238	>	* List should have.  If this expectation is violated, the iterator
239	>	* has detected concurrent modification.
240	>	*/
241	>	int expectedModCount = modCount;
242	>
243	>	public boolean hasNext() {
244	>	return cursor <= size;
245	>	}
246
247	<	public E next() {
247	>	public E next() {
248		checkForComodification();
249		if (cursor > size)
250	<	throw new NoSuchElementException();
250	>	throw new NoSuchElementException();
251		E result = queue[cursor];
252		lastRet = cursor++;
253		return result;
254	<	}
254	>	}
255
256	<	public void remove() {
257	<	if (lastRet == 0)
258	<	throw new IllegalStateException();
256	>	public void remove() {
257	>	if (lastRet == 0)
258	>	throw new IllegalStateException();
259		checkForComodification();
260
261		PriorityQueue.this.remove(lastRet);
#	Line 264 | Line 263 | public class PriorityQueue<E> extends Ab
263		cursor--;
264		lastRet = 0;
265		expectedModCount = modCount;
266	<	}
266	>	}
267
268	<	final void checkForComodification() {
269	<	if (modCount != expectedModCount)
270	<	throw new ConcurrentModificationException();
271	<	}
268	>	final void checkForComodification() {
269	>	if (modCount != expectedModCount)
270	>	throw new ConcurrentModificationException();
271	>	}
272		}
273
274		/**
275		* Returns the number of elements in this priority queue.
276	<	*
276	>	*
277		* @return the number of elements in this priority queue.
278		*/
279		public int size() {
#	Line 287 | Line 286 | public class PriorityQueue<E> extends Ab
286		* @param element the element to add.
287		* @return true
288		* @throws ClassCastException if the specified element cannot be compared
289	<	*            with elements currently in the priority queue according
289	>	*            with elements currently in the priority queue according
290		*            to the priority queue's ordering.
291		* @throws NullPointerException if the specified element is null.
292		*/
#	Line 406 | Line 405 | public class PriorityQueue<E> extends Ab
405		* <tt>null</tt> if it uses its elements' natural ordering.
406		*
407		* @return the comparator associated with this priority queue, or
408	<	*         <tt>null</tt> if it uses its elements' natural ordering.
408	>	*         <tt>null</tt> if it uses its elements' natural ordering.
409		*/
410	<	Comparator<E> comparator() {
410	>	Comparator comparator() {
411		return comparator;
412		}
413	+
414	+	/**
415	+	* Save the state of the instance to a stream (that
416	+	* is, serialize it).
417	+	*
418	+	* @serialData The length of the array backing the instance is
419	+	* emitted (int), followed by all of its elements (each an
420	+	* <tt>Object</tt>) in the proper order.
421	+	*/
422	+	private synchronized void writeObject(java.io.ObjectOutputStream s)
423	+	throws java.io.IOException{
424	+	// Write out element count, and any hidden stuff
425	+	s.defaultWriteObject();
426	+
427	+	// Write out array length
428	+	s.writeInt(queue.length);
429	+
430	+	// Write out all elements in the proper order.
431	+	for (int i=0; i<size; i++)
432	+	s.writeObject(queue[i]);
433	+	}
434	+
435	+	/**
436	+	* Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
437	+	* deserialize it).
438	+	*/
439	+	private synchronized void readObject(java.io.ObjectInputStream s)
440	+	throws java.io.IOException, ClassNotFoundException {
441	+	// Read in size, and any hidden stuff
442	+	s.defaultReadObject();
443	+
444	+	// Read in array length and allocate array
445	+	int arrayLength = s.readInt();
446	+	queue = new E[arrayLength];
447	+
448	+	// Read in all elements in the proper order.
449	+	for (int i=0; i<size; i++)
450	+	queue[i] = (E)s.readObject();
451	+	}
452	+
453		}

Diff Legend

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