[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.21, Tue Aug 5 06:49:51 2003 UTC revision 1.22, Tue Aug 5 12:11:08 2003 UTC
# Line 41  Line 41 
41   * @author Josh Bloch   * @author Josh Bloch
42   */   */
43  public class PriorityQueue<E> extends AbstractQueue<E>  public class PriorityQueue<E> extends AbstractQueue<E>
44      implements Sorted, Queue<E>, java.io.Serializable {      implements Queue<E>, java.io.Serializable {
45    
46      private static final int DEFAULT_INITIAL_CAPACITY = 11;      private static final int DEFAULT_INITIAL_CAPACITY = 11;
47    
# Line 116  Line 116 
116      }      }
117    
118      /**      /**
119         * Common code to initialize underlying queue array across
120         * constructors below.
121         */
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);
126            if (initialCapacity < 1)
127                initialCapacity = 1;
128    
129            this.queue = new Object[initialCapacity + 1];
130        }
131    
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    
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       * Creates a <tt>PriorityQueue</tt> containing the elements in the
155       * specified collection.       * specified collection.  The priority queue has an initial
156       * The priority queue has an initial capacity of 110% of the       * capacity of 110% of the size of the specified collection or 1
157       * size of the specified collection or 1 if the collection is empty.       * if the collection is empty.  If the specified collection is an
158       * If the specified collection       * instance of a {@link SortedSet} or is another
159       * implements the {@link Sorted} interface, the priority queue will be       * <tt>PriorityQueue</tt>, the priority queue will be sorted
160       * sorted according to the same comparator, or according to its elements'       * according to the same comparator, or according to its elements'
161       * natural order if the collection is sorted according to its elements'       * natural order if the collection is sorted according to its
162       * natural order.  If the specified collection does not implement       * elements' natural order.  Otherwise, the priority queue is
163       * <tt>Sorted</tt>, the priority queue is ordered according to       * ordered according to its elements' natural order.
      * its elements' natural order.  
164       *       *
165       * @param c the collection whose elements are to be placed       * @param c the collection whose elements are to be placed
166       *        into this priority queue.       *        into this priority queue.
# Line 137  Line 171 
171       * is <tt>null</tt>       * is <tt>null</tt>
172       */       */
173      public PriorityQueue(Collection<? extends E> c) {      public PriorityQueue(Collection<? extends E> c) {
174          int sz = c.size();          initializeArray(c);
175          int initialCapacity = (int)Math.min((sz * 110L) / 100,          if (c instanceof SortedSet<? extends E>) {
176                                              Integer.MAX_VALUE - 1);              SortedSet<? extends E> s = (SortedSet<? extends E>) c;
177          if (initialCapacity < 1)              comparator = (Comparator<? super E>)s.comparator();
178              initialCapacity = 1;              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          this.queue = new Object[initialCapacity + 1];      /**
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          if (c instanceof Sorted) {      /**
215              comparator = (Comparator<? super E>)((Sorted)c).comparator();       * Creates a <tt>PriorityQueue</tt> containing the elements in the
216          } else {       * specified collection.  The priority queue has an initial
217              comparator = null;       * 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          for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )      /**
238              add(i.next());       * 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      // Queue Methods
# Line 173  Line 272 
272          ++size;          ++size;
273    
274          // Grow backing store if necessary          // Grow backing store if necessary
275          while (size >= queue.length) {          if (size >= queue.length)
276              Object[] newQueue = new Object[2 * queue.length];              grow(size);
             System.arraycopy(queue, 0, newQueue, 0, queue.length);  
             queue = newQueue;  
         }  
277    
278          queue[size] = o;          queue[size] = o;
279          fixUp(size);          fixUp(size);
# Line 412  Line 508 
508       * <tt>Object</tt>) in the proper order.       * <tt>Object</tt>) in the proper order.
509       * @param s the stream       * @param s the stream
510       */       */
511      private synchronized void writeObject(java.io.ObjectOutputStream s)      private void writeObject(java.io.ObjectOutputStream s)
512          throws java.io.IOException{          throws java.io.IOException{
513          // Write out element count, and any hidden stuff          // Write out element count, and any hidden stuff
514          s.defaultWriteObject();          s.defaultWriteObject();
# Line 430  Line 526 
526       * deserialize it).       * deserialize it).
527       * @param s the stream       * @param s the stream
528       */       */
529      private synchronized void readObject(java.io.ObjectInputStream s)      private void readObject(java.io.ObjectInputStream s)
530          throws java.io.IOException, ClassNotFoundException {          throws java.io.IOException, ClassNotFoundException {
531          // Read in size, and any hidden stuff          // Read in size, and any hidden stuff
532          s.defaultReadObject();          s.defaultReadObject();

Legend:
Removed from v.1.21  
changed lines
  Added in v.1.22

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8