[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.10, Sat Jul 26 13:17:51 2003 UTC revision 1.11, Mon Jul 28 04:11:54 2003 UTC
# Line 3  Line 3 
3  /**  /**
4   * An unbounded priority queue based on a priority heap.  This queue orders   * An unbounded priority queue based on a priority heap.  This queue orders
5   * elements according to an order specified at construction time, which is   * 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   * specified in the same manner as {@link TreeSet} and {@link TreeMap}:
7     * elements are ordered
8   * either according to their <i>natural order</i> (see {@link Comparable}), or   * either according to their <i>natural order</i> (see {@link Comparable}), or
9   * according to a {@link Comparator}, depending on which constructor is used.   * according to a {@link Comparator}, depending on which constructor is used.
10   * The {@link #peek}, {@link #poll}, and {@link #remove} methods return the   * The <em>head</em> of this queue is the least element with respect to the
11   * minimal element with respect to the specified ordering.  If multiple   * specified ordering. If multiple elements are tied for least value, the
12   * elements are tied for least value, no guarantees are made as to   * head is one of those elements. A priority queue does not permit
13   * which of these elements is returned.   * <tt>null</tt> elements.
14     *
15     * <p>The {@link #remove()} and {@link #poll()} methods remove and
16     * return the head of the queue.
17     *
18     * <p>The {@link #element()} and {@link #peek()} methods return, but do
19     * not delete, the head of the queue.
20   *   *
21   * <p>A priority queue has a <i>capacity</i>.  The capacity is the   * <p>A priority queue has a <i>capacity</i>.  The capacity is the
22   * size of the array used internally to store the elements on the   * size of the array used internally to store the elements on the
# Line 31  Line 38 
38   * @author Josh Bloch   * @author Josh Bloch
39   */   */
40  public class PriorityQueue<E> extends AbstractQueue<E>  public class PriorityQueue<E> extends AbstractQueue<E>
41                                implements Queue<E>,      implements Queue<E>, Sorted, java.io.Serializable {
42                                           java.io.Serializable {  
43      private static final int DEFAULT_INITIAL_CAPACITY = 11;      private static final int DEFAULT_INITIAL_CAPACITY = 11;
44    
45      /**      /**
# Line 68  Line 75 
75      private transient int modCount = 0;      private transient int modCount = 0;
76    
77      /**      /**
78       * Create a new priority queue with the default initial capacity       * Create a <tt>PriorityQueue</tt> with the default initial capacity
79       * (11) that orders its elements according to their natural       * (11) that orders its elements according to their natural
80       * ordering (using <tt>Comparable</tt>.)       * ordering (using <tt>Comparable</tt>.)
81       */       */
82      public PriorityQueue() {      public PriorityQueue() {
83          this(DEFAULT_INITIAL_CAPACITY);          this(DEFAULT_INITIAL_CAPACITY, null);
84      }      }
85    
86      /**      /**
87       * Create a new priority queue with the specified initial capacity       * Create a <tt>PriorityQueue</tt> with the specified initial capacity
88       * that orders its elements according to their natural ordering       * that orders its elements according to their natural ordering
89       * (using <tt>Comparable</tt>.)       * (using <tt>Comparable</tt>.)
90       *       *
# Line 88  Line 95 
95      }      }
96    
97      /**      /**
98       * Create a new priority queue with the specified initial capacity (11)       * Create a <tt>PriorityQueue</tt> with the specified initial capacity
99       * that orders its elements according to the specified comparator.       * that orders its elements according to the specified comparator.
100       *       *
101       * @param initialCapacity the initial capacity for this priority queue.       * @param initialCapacity the initial capacity for this priority queue.
102       * @param comparator the comparator used to order this priority queue.       * @param comparator the comparator used to order this priority queue.
103         * If <tt>null</tt> then the order depends on the elements' natural
104         * ordering.
105       */       */
106      public PriorityQueue(int initialCapacity, Comparator<E> comparator) {      public PriorityQueue(int initialCapacity, Comparator<E> comparator) {
107          if (initialCapacity < 1)          if (initialCapacity < 1)
# Line 102  Line 111 
111      }      }
112    
113      /**      /**
114       * Create a new priority queue containing the elements in the specified       * Create a <tt>PriorityQueue</tt> containing the elements in the specified
115       * collection.  The priority queue has an initial capacity of 110% of the       * collection.  The priority queue has an initial capacity of 110% of the
116       * size of the specified collection. If the specified collection       * size of the specified collection. If the specified collection
117       * implements the {@link Sorted} interface, the priority queue will be       * implements the {@link Sorted} interface, the priority queue will be
# Line 128  Line 137 
137              initialCapacity = 1;              initialCapacity = 1;
138          queue = (E[]) new Object[initialCapacity + 1];          queue = (E[]) new Object[initialCapacity + 1];
139    
   
140          if (initialElements instanceof Sorted) {          if (initialElements instanceof Sorted) {
141              comparator = ((Sorted)initialElements).comparator();              comparator = ((Sorted)initialElements).comparator();
142              for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )              for (Iterator<E> i = initialElements.iterator(); i.hasNext(); )
# Line 143  Line 151 
151      // Queue Methods      // Queue Methods
152    
153      /**      /**
154       * Remove and return the minimal element from this priority queue       * Add the specified element to this priority queue.
      * if it contains one or more elements, otherwise return  
      * <tt>null</tt>.  The term <i>minimal</i> is defined according to  
      * this priority queue's order.  
155       *       *
156       * @return the minimal element from this priority queue if it contains       * @param element the element to add.
157       *         one or more elements, otherwise <tt>null</tt>.       * @return <tt>true</tt>
158         * @throws ClassCastException if the specified element cannot be compared
159         * with elements currently in the priority queue according
160         * to the priority queue's ordering.
161         * @throws NullPointerException if the specified element is null.
162       */       */
163        public boolean offer(E element) {
164            if (element == null)
165                throw new NullPointerException();
166            modCount++;
167            ++size;
168    
169            // Grow backing store if necessary
170            while (size >= queue.length) {
171                E[] newQueue = (E[]) new Object[2 * queue.length];
172                System.arraycopy(queue, 0, newQueue, 0, queue.length);
173                queue = newQueue;
174            }
175    
176            queue[size] = element;
177            fixUp(size);
178            return true;
179        }
180    
181      public E poll() {      public E poll() {
182          if (size == 0)          if (size == 0)
183              return null;              return null;
184          return remove(1);          return remove(1);
185      }      }
186    
     /**  
      * Return, but do not remove, the minimal element from the  
      * priority queue, or return <tt>null</tt> if the queue is empty.  
      * The term <i>minimal</i> is defined according to this priority  
      * queue's order.  This method returns the same object reference  
      * that would be returned by by the <tt>poll</tt> method.  The two  
      * methods differ in that this method does not remove the element  
      * from the priority queue.  
      *  
      * @return the minimal element from this priority queue if it contains  
      *         one or more elements, otherwise <tt>null</tt>.  
      */  
187      public E peek() {      public E peek() {
188          return queue[1];          return queue[1];
189      }      }
190    
191      // Collection Methods      // Collection Methods
192    
193        // these first two override just to get the throws docs
194    
195      /**      /**
196       * Removes a single instance of the specified element from this priority       * @throws NullPointerException if the specified element is <tt>null</tt>.
      * queue, if it is present.  Returns true if this collection contained the  
      * specified element (or equivalently, if this collection changed as a  
      * result of the call).  
      *  
      * @param element the element to be removed from this collection,  
      * if present.  
      * @return <tt>true</tt> if this collection changed as a result of the  
      *         call  
      * @throws ClassCastException if the specified element cannot be compared  
      *            with elements currently in the priority queue according  
      *            to the priority queue's ordering.  
      * @throws NullPointerException if the specified element is null.  
197       */       */
198      public boolean remove(Object element) {      public boolean add(E element) {
199          if (element == null)          return super.add(element);
200        }
201    
202        /**
203         * @throws NullPointerException if any element is <tt>null</tt>.
204         */
205        public boolean addAll(Collection c) {
206            return super.addAll(c);
207        }
208    
209        /**
210         * @throws NullPointerException if the specified element is <tt>null</tt>.
211         */
212        public boolean remove(E o) {
213            if (o == null)
214              throw new NullPointerException();              throw new NullPointerException();
215    
216          if (comparator == null) {          if (comparator == null) {
217              for (int i = 1; i <= size; i++) {              for (int i = 1; i <= size; i++) {
218                  if (((Comparable)queue[i]).compareTo(element) == 0) {                  if (((Comparable)queue[i]).compareTo(o) == 0) {
219                      remove(i);                      remove(i);
220                      return true;                      return true;
221                  }                  }
222              }              }
223          } else {          } else {
224              for (int i = 1; i <= size; i++) {              for (int i = 1; i <= size; i++) {
225                  if (comparator.compare(queue[i], (E) element) == 0) {                  if (comparator.compare(queue[i], o) == 0) {
226                      remove(i);                      remove(i);
227                      return true;                      return true;
228                  }                  }
# Line 286  Line 305 
305      }      }
306    
307      /**      /**
      * Add the specified element to this priority queue.  
      *  
      * @param element the element to add.  
      * @return true  
      * @throws ClassCastException if the specified element cannot be compared  
      *            with elements currently in the priority queue according  
      *            to the priority queue's ordering.  
      * @throws NullPointerException if the specified element is null.  
      */  
     public boolean offer(E element) {  
         if (element == null)  
             throw new NullPointerException();  
         modCount++;  
         ++size;  
   
         // Grow backing store if necessary  
         while (size >= queue.length) {  
             E[] newQueue = (E[]) new Object[2 * queue.length];  
             System.arraycopy(queue, 0, newQueue, 0, queue.length);  
             queue = newQueue;  
         }  
   
         queue[size] = element;  
         fixUp(size);  
         return true;  
     }  
   
     /**  
308       * Remove all elements from the priority queue.       * Remove all elements from the priority queue.
309       */       */
310      public void clear() {      public void clear() {
# Line 406  Line 397 
397          }          }
398      }      }
399    
     /**  
      * Returns the comparator associated with this priority queue, or  
      * <tt>null</tt> if it uses its elements' natural ordering.  
      *  
      * @return the comparator associated with this priority queue, or  
      *         <tt>null</tt> if it uses its elements' natural ordering.  
      */  
400      public Comparator comparator() {      public Comparator comparator() {
401          return comparator;          return comparator;
402      }      }
# Line 459  Line 443 
443      }      }
444    
445  }  }
446    

Legend:
Removed from v.1.10  
changed lines
  Added in v.1.11

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8