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.19 by tim, Mon Aug 4 16:14:48 2003 UTC vs.
Revision 1.22 by dl, Tue Aug 5 12:11:08 2003 UTC

#	Line 1 | Line 1
1		package java.util;
2
3		/**
4	<	* A priority queue based on a priority heap.  This queue orders
4	>	* An unbounded priority queue based on a priority heap.  This queue orders
5		* elements according to an order specified at construction time, which is
6		* specified in the same manner as {@link java.util.TreeSet} and
7		* {@link java.util.TreeMap}: elements are ordered
#	Line 22 | Line 22
22		*
23		* <p>A priority queue has a <i>capacity</i>.  The capacity is the
24		* size of the array used internally to store the elements on the
25	<	* queue, and is limited to <tt>Integer.MAX_VALUE-1</tt>.
25	>	* queue.
26		* It is always at least as large as the queue size.  As
27		* elements are added to a priority queue, its capacity grows
28		* automatically.  The details of the growth policy are not specified.
#	Line 41 | Line 41
41		* @author Josh Bloch
42		*/
43		public class PriorityQueue<E> extends AbstractQueue<E>
44	<	implements Sorted, Queue<E>, java.io.Serializable {
44	>	implements Queue<E>, java.io.Serializable {
45
46		private static final int DEFAULT_INITIAL_CAPACITY = 11;
47
#	Line 78 | Line 78 | public class PriorityQueue<E> extends Ab
78		private transient int modCount = 0;
79
80		/**
81	<	* Create a <tt>PriorityQueue</tt> with the default initial capacity
81	>	* Creates a <tt>PriorityQueue</tt> with the default initial capacity
82		* (11) that orders its elements according to their natural
83		* ordering (using <tt>Comparable</tt>.)
84		*/
#	Line 87 | Line 87 | public class PriorityQueue<E> extends Ab
87		}
88
89		/**
90	<	* Create a <tt>PriorityQueue</tt> with the specified initial capacity
90	>	* Creates a <tt>PriorityQueue</tt> with the specified initial capacity
91		* that orders its elements according to their natural ordering
92		* (using <tt>Comparable</tt>.)
93		*
#	Line 98 | Line 98 | public class PriorityQueue<E> extends Ab
98		}
99
100		/**
101	<	* Create a <tt>PriorityQueue</tt> with the specified initial capacity
101	>	* Creates a <tt>PriorityQueue</tt> with the specified initial capacity
102		* that orders its elements according to the specified comparator.
103		*
104		* @param initialCapacity the initial capacity for this priority queue.
#	Line 116 | Line 116 | public class PriorityQueue<E> extends Ab
116		}
117
118		/**
119	<	* Create a <tt>PriorityQueue</tt> containing the elements in the specified
120	<	* collection.  The priority queue has an initial capacity of 110% of the
121	<	* size of the specified collection (bounded by
122	<	* <tt>Integer.MAX_VALUE-1</tt>); or 1 if the collection is empty.
123	<	* If the specified collection
124	<	* implements the {@link Sorted} interface, the priority queue will be
125	<	* sorted according to the same comparator, or according to its elements'
126	<	* natural order if the collection is sorted according to its elements'
127	<	* natural order.  If the specified collection does not implement
128	<	* <tt>Sorted</tt>, the priority queue is ordered according to
129	<	* its elements' natural order.
130	<	*
131	<	* @param c the collection whose elements are to be placed
132	<	*        into this priority queue.
133	<	* @throws ClassCastException if elements of the specified collection
134	<	*         cannot be compared to one another according to the priority
135	<	*         queue's ordering.
136	<	* @throws NullPointerException if <tt>c</tt> or any element within it
137	<	* is <tt>null</tt>
119	>	* Common code to initialize underlying queue array across
120	>	* constructors below.
121		*/
122	<	public PriorityQueue(Collection<? extends E> c) {
122	>	private void initializeArray(Collection<? extends E> c) {
123		int sz = c.size();
124		int initialCapacity = (int)Math.min((sz * 110L) / 100,
125		Integer.MAX_VALUE - 1);
#	Line 144 | Line 127 | public class PriorityQueue<E> extends Ab
127		initialCapacity = 1;
128
129		this.queue = new Object[initialCapacity + 1];
130	+	}
131
132	<	// FIXME: if c is larger than Integer.MAX_VALUE we'll
133	<	// overflow the array
132	>	/**
133	>	* Initially fill elements of the queue array under the
134	>	* knowledge that it is sorted or is another PQ, in which
135	>	* case we can just place the elements without fixups.
136	>	*/
137	>	private void fillFromSorted(Collection<? extends E> c) {
138	>	for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )
139	>	queue[++size] = i.next();
140	>	}
141
151	–	if (c instanceof Sorted) {
152	–	comparator = (Comparator<? super E>)((Sorted)c).comparator();
153	–	} else {
154	–	comparator = null;
155	–	}
142
143	+	/**
144	+	* Initially fill elements of the queue array that is
145	+	* not to our knowledge sorted, so we must add them
146	+	* one by one.
147	+	*/
148	+	private void fillFromUnsorted(Collection<? extends E> c) {
149		for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )
150		add(i.next());
151		}
152
153	+	/**
154	+	* Creates a <tt>PriorityQueue</tt> containing the elements in the
155	+	* specified collection.  The priority queue has an initial
156	+	* capacity of 110% of the size of the specified collection or 1
157	+	* if the collection is empty.  If the specified collection is an
158	+	* instance of a {@link SortedSet} or is another
159	+	* <tt>PriorityQueue</tt>, the priority queue will be sorted
160	+	* according to the same comparator, or according to its elements'
161	+	* natural order if the collection is sorted according to its
162	+	* elements' natural order.  Otherwise, the priority queue is
163	+	* ordered according to its elements' natural order.
164	+	*
165	+	* @param c the collection whose elements are to be placed
166	+	*        into this priority queue.
167	+	* @throws ClassCastException if elements of the specified collection
168	+	*         cannot be compared to one another according to the priority
169	+	*         queue's ordering.
170	+	* @throws NullPointerException if <tt>c</tt> or any element within it
171	+	* is <tt>null</tt>
172	+	*/
173	+	public PriorityQueue(Collection<? extends E> c) {
174	+	initializeArray(c);
175	+	if (c instanceof SortedSet<? extends E>) {
176	+	SortedSet<? extends E> s = (SortedSet<? extends E>) c;
177	+	comparator = (Comparator<? super E>)s.comparator();
178	+	fillFromSorted(s);
179	+	}
180	+	else if (c instanceof PriorityQueue<? extends E>) {
181	+	PriorityQueue<? extends E> s = (PriorityQueue<? extends E>) c;
182	+	comparator = (Comparator<? super E>)s.comparator();
183	+	fillFromSorted(s);
184	+	}
185	+	else {
186	+	comparator = null;
187	+	fillFromUnsorted(c);
188	+	}
189	+	}
190	+
191	+	/**
192	+	* Creates a <tt>PriorityQueue</tt> containing the elements in the
193	+	* specified collection.  The priority queue has an initial
194	+	* capacity of 110% of the size of the specified collection or 1
195	+	* if the collection is empty.  This priority queue will be sorted
196	+	* according to the same comparator as the given collection, or
197	+	* according to its elements' natural order if the collection is
198	+	* sorted according to its elements' natural order.
199	+	*
200	+	* @param c the collection whose elements are to be placed
201	+	*        into this priority queue.
202	+	* @throws ClassCastException if elements of the specified collection
203	+	*         cannot be compared to one another according to the priority
204	+	*         queue's ordering.
205	+	* @throws NullPointerException if <tt>c</tt> or any element within it
206	+	* is <tt>null</tt>
207	+	*/
208	+	public PriorityQueue(PriorityQueue<? extends E> c) {
209	+	initializeArray(c);
210	+	comparator = (Comparator<? super E>)c.comparator();
211	+	fillFromSorted(c);
212	+	}
213	+
214	+	/**
215	+	* Creates a <tt>PriorityQueue</tt> containing the elements in the
216	+	* specified collection.  The priority queue has an initial
217	+	* capacity of 110% of the size of the specified collection or 1
218	+	* if the collection is empty.  This priority queue will be sorted
219	+	* according to the same comparator as the given collection, or
220	+	* according to its elements' natural order if the collection is
221	+	* sorted according to its elements' natural order.
222	+	*
223	+	* @param c the collection whose elements are to be placed
224	+	*        into this priority queue.
225	+	* @throws ClassCastException if elements of the specified collection
226	+	*         cannot be compared to one another according to the priority
227	+	*         queue's ordering.
228	+	* @throws NullPointerException if <tt>c</tt> or any element within it
229	+	* is <tt>null</tt>
230	+	*/
231	+	public PriorityQueue(SortedSet<? extends E> c) {
232	+	initializeArray(c);
233	+	comparator = (Comparator<? super E>)c.comparator();
234	+	fillFromSorted(c);
235	+	}
236	+
237	+	/**
238	+	* Resize array, if necessary, to be able to hold given index
239	+	*/
240	+	private void grow(int index) {
241	+	int newlen = queue.length;
242	+	if (index < newlen) // don't need to grow
243	+	return;
244	+	if (index == Integer.MAX_VALUE)
245	+	throw new OutOfMemoryError();
246	+	while (newlen <= index) {
247	+	if (newlen >= Integer.MAX_VALUE / 2)  // avoid overflow
248	+	newlen = Integer.MAX_VALUE;
249	+	else
250	+	newlen <<= 2;
251	+	}
252	+	Object[] newQueue = new Object[newlen];
253	+	System.arraycopy(queue, 0, newQueue, 0, queue.length);
254	+	queue = newQueue;
255	+	}
256	+
257		// Queue Methods
258
259		/**
#	Line 176 | Line 272 | public class PriorityQueue<E> extends Ab
272		++size;
273
274		// Grow backing store if necessary
275	<	// FIXME: watch for overflow
276	<	// FIXME: what if we're full?
181	<	while (size >= queue.length) {
182	<	Object[] newQueue = new Object[2 * queue.length];
183	<	System.arraycopy(queue, 0, newQueue, 0, queue.length);
184	<	queue = newQueue;
185	<	}
275	>	if (size >= queue.length)
276	>	grow(size);
277
278		queue[size] = o;
279		fixUp(size);
#	Line 417 | Line 508 | public class PriorityQueue<E> extends Ab
508		* <tt>Object</tt>) in the proper order.
509		* @param s the stream
510		*/
511	<	private synchronized void writeObject(java.io.ObjectOutputStream s)
511	>	private void writeObject(java.io.ObjectOutputStream s)
512		throws java.io.IOException{
513		// Write out element count, and any hidden stuff
514		s.defaultWriteObject();
#	Line 435 | Line 526 | public class PriorityQueue<E> extends Ab
526		* deserialize it).
527		* @param s the stream
528		*/
529	<	private synchronized void readObject(java.io.ObjectInputStream s)
529	>	private void readObject(java.io.ObjectInputStream s)
530		throws java.io.IOException, ClassNotFoundException {
531		// Read in size, and any hidden stuff
532		s.defaultReadObject();

Diff Legend

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