ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/PriorityQueue.java
(Generate patch)

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.5 by dl, Tue May 27 18:20:06 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
# Line 51 | Line 45 | public class PriorityQueue<E> extends Ab
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)
# 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 161 | Line 159 | public class PriorityQueue<E> extends Ab
159       * or <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 183 | Line 181 | public class PriorityQueue<E> extends Ab
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
212 >     * first element returned by this iterator is the same element that
213       * would be returned by a call to <tt>peek</tt>.
214 <     *
214 >     *
215       * @return an <tt>Iterator</tt> over the elements in this priority queue.
216       */
217      public Iterator<E> iterator() {
218 <        return new Itr();
218 >        return new Itr();
219      }
220  
221      private class Itr implements Iterator<E> {
222 <        /**
223 <         * Index (into queue array) of element to be returned by
222 >        /**
223 >         * Index (into queue array) of element to be returned by
224           * subsequent call to next.
225 <         */
226 <        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;
225 >         */
226 >        int cursor = 1;
227  
228 <        public boolean hasNext() {
229 <            return cursor <= size;
230 <        }
228 >        /**
229 >         * Index of element returned by most recent call to next or
230 >         * previous.  Reset to 0 if this element is deleted by a call
231 >         * to remove.
232 >         */
233 >        int lastRet = 0;
234 >
235 >        /**
236 >         * The modCount value that the iterator believes that the backing
237 >         * List should have.  If this expectation is violated, the iterator
238 >         * has detected concurrent modification.
239 >         */
240 >        int expectedModCount = modCount;
241 >
242 >        public boolean hasNext() {
243 >            return cursor <= size;
244 >        }
245  
246 <        public E next() {
246 >        public E next() {
247              checkForComodification();
248              if (cursor > size)
249 <                throw new NoSuchElementException();
249 >                throw new NoSuchElementException();
250              E result = queue[cursor];
251              lastRet = cursor++;
252              return result;
253 <        }
253 >        }
254  
255 <        public void remove() {
256 <            if (lastRet == 0)
257 <                throw new IllegalStateException();
255 >        public void remove() {
256 >            if (lastRet == 0)
257 >                throw new IllegalStateException();
258              checkForComodification();
259  
260              PriorityQueue.this.remove(lastRet);
# Line 264 | Line 262 | public class PriorityQueue<E> extends Ab
262                  cursor--;
263              lastRet = 0;
264              expectedModCount = modCount;
265 <        }
265 >        }
266  
267 <        final void checkForComodification() {
268 <            if (modCount != expectedModCount)
269 <                throw new ConcurrentModificationException();
270 <        }
267 >        final void checkForComodification() {
268 >            if (modCount != expectedModCount)
269 >                throw new ConcurrentModificationException();
270 >        }
271      }
272  
273      /**
274       * Returns the number of elements in this priority queue.
275 <     *
275 >     *
276       * @return the number of elements in this priority queue.
277       */
278      public int size() {
# Line 287 | Line 285 | public class PriorityQueue<E> extends Ab
285       * @param element the element to add.
286       * @return true
287       * @throws ClassCastException if the specified element cannot be compared
288 <     *            with elements currently in the priority queue according
288 >     *            with elements currently in the priority queue according
289       *            to the priority queue's ordering.
290       * @throws NullPointerException if the specified element is null.
291       */
# Line 406 | Line 404 | public class PriorityQueue<E> extends Ab
404       * <tt>null</tt> if it uses its elements' natural ordering.
405       *
406       * @return the comparator associated with this priority queue, or
407 <     *         <tt>null</tt> if it uses its elements' natural ordering.
407 >     *         <tt>null</tt> if it uses its elements' natural ordering.
408       */
409 <    Comparator<E> comparator() {
409 >    Comparator comparator() {
410          return comparator;
411      }
412 +
413 +    /**
414 +     * Save the state of the instance to a stream (that
415 +     * is, serialize it).
416 +     *
417 +     * @serialData The length of the array backing the instance is
418 +     * emitted (int), followed by all of its elements (each an
419 +     * <tt>Object</tt>) in the proper order.
420 +     */
421 +    private synchronized void writeObject(java.io.ObjectOutputStream s)
422 +        throws java.io.IOException{
423 +        // Write out element count, and any hidden stuff
424 +        s.defaultWriteObject();
425 +
426 +        // Write out array length
427 +        s.writeInt(queue.length);
428 +
429 +        // Write out all elements in the proper order.
430 +        for (int i=0; i<size; i++)
431 +            s.writeObject(queue[i]);
432 +    }
433 +
434 +    /**
435 +     * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
436 +     * deserialize it).
437 +     */
438 +    private synchronized void readObject(java.io.ObjectInputStream s)
439 +        throws java.io.IOException, ClassNotFoundException {
440 +        // Read in size, and any hidden stuff
441 +        s.defaultReadObject();
442 +
443 +        // Read in array length and allocate array
444 +        int arrayLength = s.readInt();
445 +        queue = new E[arrayLength];
446 +
447 +        // Read in all elements in the proper order.
448 +        for (int i=0; i<size; i++)
449 +            queue[i] = (E)s.readObject();
450 +    }
451 +
452   }

Diff Legend

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