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.21 by dholmes, Tue Aug 5 06:49:51 2003 UTC vs.
Revision 1.22 by dl, Tue Aug 5 12:11:08 2003 UTC

# 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 116 | Line 116 | public class PriorityQueue<E> extends Ab
116      }
117  
118      /**
119 <     * Creates a <tt>PriorityQueue</tt> containing the elements in the
120 <     * specified collection.  
121 <     * The priority queue has an initial capacity of 110% of the
122 <     * size of the specified collection 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.
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
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.
# Line 137 | Line 171 | public class PriorityQueue<E> extends Ab
171       * is <tt>null</tt>
172       */
173      public PriorityQueue(Collection<? extends E> c) {
174 <        int sz = c.size();
175 <        int initialCapacity = (int)Math.min((sz * 110L) / 100,
176 <                                            Integer.MAX_VALUE - 1);
177 <        if (initialCapacity < 1)
178 <            initialCapacity = 1;
179 <
180 <        this.queue = new Object[initialCapacity + 1];
181 <
182 <        if (c instanceof Sorted) {
183 <            comparator = (Comparator<? super E>)((Sorted)c).comparator();
184 <        } else {
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 <        for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )
192 <            add(i.next());
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 173 | Line 272 | public class PriorityQueue<E> extends Ab
272          ++size;
273  
274          // Grow backing store if necessary
275 <        while (size >= queue.length) {
276 <            Object[] newQueue = new Object[2 * queue.length];
178 <            System.arraycopy(queue, 0, newQueue, 0, queue.length);
179 <            queue = newQueue;
180 <        }
275 >        if (size >= queue.length)
276 >            grow(size);
277  
278          queue[size] = o;
279          fixUp(size);
# Line 412 | 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 430 | 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