[cvs] / jsr166 / src / main / java / util / PriorityQueue.java Repository:
ViewVC logotype

Diff of /jsr166/src/main/java/util/PriorityQueue.java

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1.51, Sun Nov 21 01:40:39 2004 UTC revision 1.52, Tue Nov 22 11:44:47 2005 UTC
# Line 1  Line 1 
1  /*  /*
2   * %W% %E%   * @(#)PriorityQueue.java       1.8 05/08/27
3   *   *
4   * Copyright 2004 Sun Microsystems, Inc. All rights reserved.   * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
5   * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.   * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6   */   */
7    
8  package java.util;  package java.util;
9    import java.util.*; // for javadoc (till 6280605 is fixed)
10    
11  /**  /**
12   * An unbounded priority {@linkplain Queue queue} based on a priority   * An unbounded priority {@linkplain Queue queue} based on a priority
13   * heap.  This queue orders elements according to an order specified   * heap.  The elements of the priority queue are ordered according to
14   * at construction time, which is specified either according to their   * their {@linkplain Comparable natural ordering}, or by a {@link
15   * <i>natural order</i> (see {@link Comparable}), or according to a   * Comparator} provided at queue construction time, depending on which
16   * {@link java.util.Comparator}, depending on which constructor is   * constructor is used.  A priority queue does not permit
17   * used. A priority queue does not permit <tt>null</tt> elements.   * <tt>null</tt> elements.  A priority queue relying on natural
18   * A priority queue relying on natural ordering also does not   * ordering also does not permit insertion of non-comparable objects
19   * permit insertion of non-comparable objects (doing so may result   * (doing so may result in <tt>ClassCastException</tt>).
  * in <tt>ClassCastException</tt>).  
20   *   *
21   * <p>The <em>head</em> of this queue is the <em>least</em> element   * <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   * with respect to the specified ordering.  If multiple elements are
# Line 34  Line 34 
34   *   *
35   * <p>This class and its iterator implement all of the   * <p>This class and its iterator implement all of the
36   * <em>optional</em> methods of the {@link Collection} and {@link   * <em>optional</em> methods of the {@link Collection} and {@link
37   * Iterator} interfaces.   * Iterator} interfaces.  The Iterator provided in method {@link
38   * The   * #iterator()} is <em>not</em> guaranteed to traverse the elements of
39   * Iterator provided in method {@link #iterator()} is <em>not</em>   * the priority queue in any particular order. If you need ordered
40   * guaranteed to traverse the elements of the PriorityQueue in any   * traversal, consider using <tt>Arrays.sort(pq.toArray())</tt>.
  * particular order. If you need ordered traversal, consider using  
  * <tt>Arrays.sort(pq.toArray())</tt>.  
41   *   *
42   * <p> <strong>Note that this implementation is not synchronized.</strong>   * <p> <strong>Note that this implementation is not synchronized.</strong>
43   * Multiple threads should not access a <tt>PriorityQueue</tt>   * Multiple threads should not access a <tt>PriorityQueue</tt>
# Line 47  Line 45 
45   * structurally. Instead, use the thread-safe {@link   * structurally. Instead, use the thread-safe {@link
46   * java.util.concurrent.PriorityBlockingQueue} class.   * java.util.concurrent.PriorityBlockingQueue} class.
47   *   *
  *  
48   * <p>Implementation note: this implementation provides O(log(n)) time   * <p>Implementation note: this implementation provides O(log(n)) time
49   * for the insertion methods (<tt>offer</tt>, <tt>poll</tt>,   * for the insertion methods (<tt>offer</tt>, <tt>poll</tt>,
50   * <tt>remove()</tt> and <tt>add</tt>) methods; linear time for the   * <tt>remove()</tt> and <tt>add</tt>) methods; linear time for the
# Line 59  Line 56 
56   * <a href="{@docRoot}/../guide/collections/index.html">   * <a href="{@docRoot}/../guide/collections/index.html">
57   * Java Collections Framework</a>.   * Java Collections Framework</a>.
58   * @since 1.5   * @since 1.5
59   * @version %I%, %G%   * @version 1.8, 08/27/05
60   * @author Josh Bloch   * @author Josh Bloch
61   * @param <E> the type of elements held in this collection   * @param <E> the type of elements held in this collection
62   */   */
# Line 103  Line 100 
100      private transient int modCount = 0;      private transient int modCount = 0;
101    
102      /**      /**
103       * Creates a <tt>PriorityQueue</tt> with the default initial capacity       * Creates a <tt>PriorityQueue</tt> with the default initial
104       * (11) that orders its elements according to their natural       * capacity (11) that orders its elements according to their
105       * ordering (using <tt>Comparable</tt>).       * {@linkplain Comparable natural ordering}.
106       */       */
107      public PriorityQueue() {      public PriorityQueue() {
108          this(DEFAULT_INITIAL_CAPACITY, null);          this(DEFAULT_INITIAL_CAPACITY, null);
109      }      }
110    
111      /**      /**
112       * Creates a <tt>PriorityQueue</tt> with the specified initial capacity       * Creates a <tt>PriorityQueue</tt> with the specified initial
113       * that orders its elements according to their natural ordering       * capacity that orders its elements according to their
114       * (using <tt>Comparable</tt>).       * {@linkplain Comparable natural ordering}.
115       *       *
116       * @param initialCapacity the initial capacity for this priority queue.       * @param initialCapacity the initial capacity for this priority queue
117       * @throws IllegalArgumentException if <tt>initialCapacity</tt> is less       * @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
118       * than 1       * than 1
119       */       */
# Line 128  Line 125 
125       * Creates a <tt>PriorityQueue</tt> with the specified initial capacity       * Creates a <tt>PriorityQueue</tt> with the specified initial capacity
126       * that orders its elements according to the specified comparator.       * that orders its elements according to the specified comparator.
127       *       *
128       * @param initialCapacity the initial capacity for this priority queue.       * @param  initialCapacity the initial capacity for this priority queue
129       * @param comparator the comparator used to order this priority queue.       * @param  comparator the comparator that will be used to order
130       * If <tt>null</tt> then the order depends on the elements' natural       *         this priority queue.  If <tt>null</tt>, the <i>natural
131       * ordering.       *         ordering</i> of the elements will be used.
132       * @throws IllegalArgumentException if <tt>initialCapacity</tt> is less       * @throws IllegalArgumentException if <tt>initialCapacity</tt> is
133       * than 1       *         less than 1
134       */       */
135      public PriorityQueue(int initialCapacity,      public PriorityQueue(int initialCapacity,
136                           Comparator<? super E> comparator) {                           Comparator<? super E> comparator) {
# Line 163  Line 160 
160       * case we can just place the elements in the order presented.       * case we can just place the elements in the order presented.
161       */       */
162      private void fillFromSorted(Collection<? extends E> c) {      private void fillFromSorted(Collection<? extends E> c) {
163          for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )          for (Iterator<? extends E> i = c.iterator(); i.hasNext(); ) {
164              queue[++size] = i.next();              int k = ++size;
165                if (k >= queue.length)
166                    grow(k);
167                queue[k] = i.next();
168            }
169      }      }
170    
171      /**      /**
# Line 173  Line 174 
174       * invariant.       * invariant.
175       */       */
176      private void fillFromUnsorted(Collection<? extends E> c) {      private void fillFromUnsorted(Collection<? extends E> c) {
177          for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )          for (Iterator<? extends E> i = c.iterator(); i.hasNext(); ) {
178              queue[++size] = i.next();              int k = ++size;
179                if (k >= queue.length)
180                    grow(k);
181                queue[k] = i.next();
182            }
183          heapify();          heapify();
184      }      }
185    
# Line 184  Line 189 
189       * capacity of 110% of the size of the specified collection or 1       * capacity of 110% of the size of the specified collection or 1
190       * if the collection is empty.  If the specified collection is an       * if the collection is empty.  If the specified collection is an
191       * instance of a {@link java.util.SortedSet} or is another       * instance of a {@link java.util.SortedSet} or is another
192       * <tt>PriorityQueue</tt>, the priority queue will be sorted       * <tt>PriorityQueue</tt>, the priority queue will be ordered
193       * according to the same comparator, or according to its elements'       * according to the same ordering.  Otherwise, this priority queue
194       * natural order if the collection is sorted according to its       * will be ordered according to the natural ordering of its elements.
      * elements' natural order.  Otherwise, the priority queue is  
      * ordered according to its elements' natural order.  
195       *       *
196       * @param c the collection whose elements are to be placed       * @param c the collection whose elements are to be placed
197       *        into this priority queue.       *         into this priority queue
198       * @throws ClassCastException if elements of the specified collection       * @throws ClassCastException if elements of the specified collection
199       *         cannot be compared to one another according to the priority       *         cannot be compared to one another according to the priority
200       *         queue's ordering.       *         queue's ordering
201       * @throws NullPointerException if <tt>c</tt> or any element within it       * @throws NullPointerException if the specified collection or any
202       * is <tt>null</tt>       *         of its elements are null
203       */       */
204      public PriorityQueue(Collection<? extends E> c) {      public PriorityQueue(Collection<? extends E> c) {
205          initializeArray(c);          initializeArray(c);
# Line 216  Line 219 
219    
220      /**      /**
221       * Creates a <tt>PriorityQueue</tt> containing the elements in the       * Creates a <tt>PriorityQueue</tt> containing the elements in the
222       * specified collection.  The priority queue has an initial       * specified priority queue.  The priority queue has an initial
223       * capacity of 110% of the size of the specified collection or 1       * capacity of 110% of the size of the specified priority queue or
224       * if the collection is empty.  This priority queue will be sorted       * 1 if the priority queue is empty.  This priority queue will be
225       * according to the same comparator as the given collection, or       * ordered according to the same ordering as the given priority
226       * according to its elements' natural order if the collection is       * queue.
227       * sorted according to its elements' natural order.       *
228       *       * @param  c the priority queue whose elements are to be placed
229       * @param c the collection whose elements are to be placed       *         into this priority queue
230       *        into this priority queue.       * @throws ClassCastException if elements of <tt>c</tt> cannot be
231       * @throws ClassCastException if elements of the specified collection       *         compared to one another according to <tt>c</tt>'s
232       *         cannot be compared to one another according to the priority       *         ordering
233       *         queue's ordering.       * @throws NullPointerException if the specified priority queue or any
234       * @throws NullPointerException if <tt>c</tt> or any element within it       *         of its elements are null
      * is <tt>null</tt>  
235       */       */
236      public PriorityQueue(PriorityQueue<? extends E> c) {      public PriorityQueue(PriorityQueue<? extends E> c) {
237          initializeArray(c);          initializeArray(c);
# Line 239  Line 241 
241    
242      /**      /**
243       * Creates a <tt>PriorityQueue</tt> containing the elements in the       * Creates a <tt>PriorityQueue</tt> containing the elements in the
244       * specified collection.  The priority queue has an initial       * specified sorted set.  The priority queue has an initial
245       * capacity of 110% of the size of the specified collection or 1       * capacity of 110% of the size of the specified sorted set or 1
246       * if the collection is empty.  This priority queue will be sorted       * if the sorted set is empty.  This priority queue will be ordered
247       * according to the same comparator as the given collection, or       * according to the same ordering as the given sorted set.
      * according to its elements' natural order if the collection is  
      * sorted according to its elements' natural order.  
248       *       *
249       * @param c the collection whose elements are to be placed       * @param  c the sorted set whose elements are to be placed
250       *        into this priority queue.       *        into this priority queue.
251       * @throws ClassCastException if elements of the specified collection       * @throws ClassCastException if elements of the specified sorted
252       *         cannot be compared to one another according to the priority       *         set cannot be compared to one another according to the
253       *         queue's ordering.       *         sorted set's ordering
254       * @throws NullPointerException if <tt>c</tt> or any element within it       * @throws NullPointerException if the specified sorted set or any
255       * is <tt>null</tt>       *         of its elements are null
256       */       */
257      public PriorityQueue(SortedSet<? extends E> c) {      public PriorityQueue(SortedSet<? extends E> c) {
258          initializeArray(c);          initializeArray(c);
# Line 261  Line 261 
261      }      }
262    
263      /**      /**
264       * Resize array, if necessary, to be able to hold given index       * Resize array, if necessary, to be able to hold given index.
265       */       */
266      private void grow(int index) {      private void grow(int index) {
267          int newlen = queue.length;          int newlen = queue.length;
# Line 275  Line 275 
275              else              else
276                  newlen <<= 2;                  newlen <<= 2;
277          }          }
278          Object[] newQueue = new Object[newlen];          queue = Arrays.copyOf(queue, newlen);
         System.arraycopy(queue, 0, newQueue, 0, queue.length);  
         queue = newQueue;  
279      }      }
280    
281        /**
282         * Inserts the specified element into this priority queue.
283         *
284         * @return <tt>true</tt> (as specified by {@link Collection#add})
285         * @throws ClassCastException if the specified element cannot be
286         *         compared with elements currently in this priority queue
287         *         according to the priority queue's ordering
288         * @throws NullPointerException if the specified element is null
289         */
290        public boolean add(E e) {
291            return offer(e);
292        }
293    
294      /**      /**
295       * Inserts the specified element into this priority queue.       * Inserts the specified element into this priority queue.
296       *       *
297       * @return <tt>true</tt>       * @return <tt>true</tt> (as specified by {@link Queue#offer})
298       * @throws ClassCastException if the specified element cannot be compared       * @throws ClassCastException if the specified element cannot be
299       * with elements currently in the priority queue according       *         compared with elements currently in this priority queue
300       * to the priority queue's ordering.       *         according to the priority queue's ordering
301       * @throws NullPointerException if the specified element is <tt>null</tt>.       * @throws NullPointerException if the specified element is null
302       */       */
303      public boolean offer(E o) {      public boolean offer(E e) {
304          if (o == null)          if (e == null)
305              throw new NullPointerException();              throw new NullPointerException();
306          modCount++;          modCount++;
307          ++size;          ++size;
# Line 300  Line 310 
310          if (size >= queue.length)          if (size >= queue.length)
311              grow(size);              grow(size);
312    
313          queue[size] = o;          queue[size] = e;
314          fixUp(size);          fixUp(size);
315          return true;          return true;
316      }      }
# Line 311  Line 321 
321          return (E) queue[1];          return (E) queue[1];
322      }      }
323    
324      // Collection Methods - the first two override to update docs      private int indexOf(Object o) {
325            if (o == null)
326      /**              return -1;
327       * Adds the specified element to this queue.          for (int i = 1; i <= size; i++)
328       * @return <tt>true</tt> (as per the general contract of              if (o.equals(queue[i]))
329       * <tt>Collection.add</tt>).                  return i;
330       *          return -1;
      * @throws NullPointerException if the specified element is <tt>null</tt>.  
      * @throws ClassCastException if the specified element cannot be compared  
      * with elements currently in the priority queue according  
      * to the priority queue's ordering.  
      */  
     public boolean add(E o) {  
         return offer(o);  
331      }      }
332    
333      /**      /**
334       * Removes a single instance of the specified element from this       * Removes a single instance of the specified element from this queue,
335       * queue, if it is present.       * if it is present.  More formally, removes an element <tt>e</tt> such
336         * that <tt>o.equals(e)</tt>, if this queue contains one or more such
337         * elements.  Returns true if this queue contained the specified element
338         * (or equivalently, if this queue changed as a result of the call).
339         *
340         * @param o element to be removed from this queue, if present
341         * @return <tt>true</tt> if this queue changed as a result of the call
342       */       */
343      public boolean remove(Object o) {      public boolean remove(Object o) {
344          if (o == null)          int i = indexOf(o);
345            if (i == -1)
346              return false;              return false;
347            else {
         if (comparator == null) {  
             for (int i = 1; i <= size; i++) {  
                 if (((Comparable<E>)queue[i]).compareTo((E)o) == 0) {  
348                      removeAt(i);                      removeAt(i);
349                      return true;                      return true;
350                  }                  }
351              }              }
352          } else {  
353              for (int i = 1; i <= size; i++) {      /**
354                  if (comparator.compare((E)queue[i], (E)o) == 0) {       * Returns <tt>true</tt> if this queue contains the specified element.
355                      removeAt(i);       * More formally, returns <tt>true</tt> if and only if this queue contains
356                      return true;       * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
357                  }       *
358         * @param o object to be checked for containment in this queue
359         * @return <tt>true</tt> if this queue contains the specified element
360         */
361        public boolean contains(Object o) {
362            return indexOf(o) != -1;
363              }              }
364    
365        /**
366         * Returns an array containing all of the elements in this queue,
367         * The elements are in no particular order.
368         *
369         * <p>The returned array will be "safe" in that no references to it are
370         * maintained by this list.  (In other words, this method must allocate
371         * a new array).  The caller is thus free to modify the returned array.
372         *
373         * @return an array containing all of the elements in this queue.
374         */
375        public Object[] toArray() {
376            return Arrays.copyOfRange(queue, 1, size+1);
377          }          }
378          return false;  
379        /**
380         * Returns an array containing all of the elements in this queue.
381         * The elements are in no particular order.  The runtime type of
382         * the returned array is that of the specified array.  If the queue
383         * fits in the specified array, it is returned therein.
384         * Otherwise, a new array is allocated with the runtime type of
385         * the specified array and the size of this queue.
386         *
387         * <p>If the queue fits in the specified array with room to spare
388         * (i.e., the array has more elements than the queue), the element in
389         * the array immediately following the end of the collection is set to
390         * <tt>null</tt>.  (This is useful in determining the length of the
391         * queue <i>only</i> if the caller knows that the queue does not contain
392         * any null elements.)
393         *
394         * @param a the array into which the elements of the queue are to
395         *          be stored, if it is big enough; otherwise, a new array of the
396         *          same runtime type is allocated for this purpose.
397         * @return an array containing the elements of the queue
398         * @throws ArrayStoreException if the runtime type of the specified array
399         *         is not a supertype of the runtime type of every element in
400         *         this queue
401         * @throws NullPointerException if the specified array is null
402         */
403        public <T> T[] toArray(T[] a) {
404            if (a.length < size)
405                // Make a new array of a's runtime type, but my contents:
406                return (T[]) Arrays.copyOfRange(queue, 1, size+1, a.getClass());
407            System.arraycopy(queue, 1, a, 0, size);
408            if (a.length > size)
409                a[size] = null;
410            return a;
411      }      }
412    
413      /**      /**
414       * Returns an iterator over the elements in this queue. The iterator       * Returns an iterator over the elements in this queue. The iterator
415       * does not return the elements in any particular order.       * does not return the elements in any particular order.
416       *       *
417       * @return an iterator over the elements in this queue.       * @return an iterator over the elements in this queue
418       */       */
419      public Iterator<E> iterator() {      public Iterator<E> iterator() {
420          return new Itr();          return new Itr();
# Line 462  Line 519 
519      }      }
520    
521      /**      /**
522       * Removes all elements from the priority queue.       * Removes all of the elements from this priority queue.
523       * The queue will be empty after this call returns.       * The queue will be empty after this call returns.
524       */       */
525      public void clear() {      public void clear() {
# Line 533  Line 590 
590          if (comparator == null) {          if (comparator == null) {
591              while (k > 1) {              while (k > 1) {
592                  int j = k >> 1;                  int j = k >> 1;
593                  if (((Comparable<E>)queue[j]).compareTo((E)queue[k]) <= 0)                  if (((Comparable<? super E>)queue[j]).compareTo((E)queue[k]) <= 0)
594                      break;                      break;
595                  Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;                  Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
596                  k = j;                  k = j;
# Line 563  Line 620 
620          if (comparator == null) {          if (comparator == null) {
621              while ((j = k << 1) <= size && (j > 0)) {              while ((j = k << 1) <= size && (j > 0)) {
622                  if (j<size &&                  if (j<size &&
623                      ((Comparable<E>)queue[j]).compareTo((E)queue[j+1]) > 0)                      ((Comparable<? super E>)queue[j]).compareTo((E)queue[j+1]) > 0)
624                      j++; // j indexes smallest kid                      j++; // j indexes smallest kid
625    
626                  if (((Comparable<E>)queue[k]).compareTo((E)queue[j]) <= 0)                  if (((Comparable<? super E>)queue[k]).compareTo((E)queue[j]) <= 0)
627                      break;                      break;
628                  Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;                  Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
629                  k = j;                  k = j;
# Line 594  Line 651 
651      }      }
652    
653      /**      /**
654       * Returns the comparator used to order this collection, or <tt>null</tt>       * Returns the comparator used to order the elements in this
655       * if this collection is sorted according to its elements natural ordering       * queue, or <tt>null</tt> if this queue is sorted according to
656       * (using <tt>Comparable</tt>).       * the {@linkplain Comparable natural ordering} of its elements.
657       *       *
658       * @return the comparator used to order this collection, or <tt>null</tt>       * @return the comparator used to order this queue, or
659       * if this collection is sorted according to its elements natural ordering.       *         <tt>null</tt> if this queue is sorted according to the
660         *         natural ordering of its elements.
661       */       */
662      public Comparator<? super E> comparator() {      public Comparator<? super E> comparator() {
663          return comparator;          return comparator;
# Line 628  Line 686 
686      }      }
687    
688      /**      /**
689       * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,       * Reconstitute the <tt>PriorityQueue</tt> instance from a stream
690       * deserialize it).       * (that is, deserialize it).
691       * @param s the stream       * @param s the stream
692       */       */
693      private void readObject(java.io.ObjectInputStream s)      private void readObject(java.io.ObjectInputStream s)

Legend:
Removed from v.1.51  
changed lines
  Added in v.1.52

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8