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.15 by dholmes, Thu Jul 31 07:18:02 2003 UTC vs.
Revision 1.16 by tim, Thu Jul 31 15:44:41 2003 UTC

# Line 55 | Line 55 | public class PriorityQueue<E> extends Ab
55       *
56       * queue.length must be >= 2, even if size == 0.
57       */
58 <    private transient E[] queue;
58 >    private transient Object[] queue;
59  
60      /**
61       * The number of elements in the priority queue.
# Line 66 | Line 66 | public class PriorityQueue<E> extends Ab
66       * The comparator, or null if priority queue uses elements'
67       * natural ordering.
68       */
69 <    private final Comparator<E> comparator;
69 >    private final Comparator<? super E> comparator;
70  
71      /**
72       * The number of times this priority queue has been
# Line 105 | Line 105 | public class PriorityQueue<E> extends Ab
105       * @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
106       * than 1
107       */
108 <    public PriorityQueue(int initialCapacity, Comparator<E> comparator) {
108 >    public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
109          if (initialCapacity < 1)
110              throw new IllegalArgumentException();
111 <        queue = (E[]) new Object[initialCapacity + 1];
111 >        this.queue = new Object[initialCapacity + 1];
112          this.comparator = comparator;
113      }
114  
115      /**
116       * Create a <tt>PriorityQueue</tt> containing the elements in the specified
117       * collection.  The priority queue has an initial capacity of 110% of the
118 <     * size of the specified collection; or 1 if the collection is empty.
118 >     * size of the specified collection; or 1 if the collection is empty.
119       * If the specified collection
120       * implements the {@link Sorted} interface, the priority queue will be
121       * sorted according to the same comparator, or according to its elements'
# Line 132 | Line 132 | public class PriorityQueue<E> extends Ab
132       * @throws NullPointerException if <tt>c</tt> or any element within it
133       * is <tt>null</tt>
134       */
135 <    public PriorityQueue(Collection<E> c) {
135 >    public PriorityQueue(Collection<? extends E> c) {
136          int sz = c.size();
137          int initialCapacity = (int)Math.min((sz * 110L) / 100,
138                                              Integer.MAX_VALUE - 1);
139          if (initialCapacity < 1)
140              initialCapacity = 1;
141  
142 <        queue = (E[]) new Object[initialCapacity + 1];
142 >        this.queue = new Object[initialCapacity + 1];
143  
144          if (c instanceof Sorted) {
145              // FIXME: this code assumes too much
146 <            comparator = ((Sorted)c).comparator();
147 <            for (Iterator<E> i = c.iterator(); i.hasNext(); )
146 >            this.comparator = (Comparator<? super E>) ((Sorted)c).comparator();
147 >            for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )
148                  queue[++size] = i.next();
149          } else {
150              comparator = null;
151 <            for (Iterator<E> i = c.iterator(); i.hasNext(); )
151 >            for (Iterator<? extends E> i = c.iterator(); i.hasNext(); )
152                  add(i.next());
153          }
154      }
# Line 173 | Line 173 | public class PriorityQueue<E> extends Ab
173  
174          // Grow backing store if necessary
175          while (size >= queue.length) {
176 <            E[] newQueue = (E[]) new Object[2 * queue.length];
176 >            Object[] newQueue = new Object[2 * queue.length];
177              System.arraycopy(queue, 0, newQueue, 0, queue.length);
178              queue = newQueue;
179          }
# Line 186 | Line 186 | public class PriorityQueue<E> extends Ab
186      public E poll() {
187          if (size == 0)
188              return null;
189 <        return remove(1);
189 >        return (E) remove(1);
190      }
191  
192      public E peek() {
193 <        return queue[1];
193 >        return (E) queue[1];
194      }
195  
196      // Collection Methods
# Line 223 | Line 223 | public class PriorityQueue<E> extends Ab
223  
224          if (comparator == null) {
225              for (int i = 1; i <= size; i++) {
226 <                if (((Comparable)queue[i]).compareTo(o) == 0) {
226 >                if (((Comparable<E>)queue[i]).compareTo((E)o) == 0) {
227                      remove(i);
228                      return true;
229                  }
230              }
231          } else {
232              for (int i = 1; i <= size; i++) {
233 <                if (comparator.compare(queue[i], (E)o) == 0) {
233 >                if (comparator.compare((E)queue[i], (E)o) == 0) {
234                      remove(i);
235                      return true;
236                  }
# Line 272 | Line 272 | public class PriorityQueue<E> extends Ab
272              checkForComodification();
273              if (cursor > size)
274                  throw new NoSuchElementException();
275 <            E result = queue[cursor];
275 >            E result = (E) queue[cursor];
276              lastRet = cursor++;
277              return result;
278          }
# Line 328 | Line 328 | public class PriorityQueue<E> extends Ab
328          assert i <= size;
329          modCount++;
330  
331 <        E result = queue[i];
331 >        E result = (E) queue[i];
332          queue[i] = queue[size];
333          queue[size--] = null;  // Drop extra ref to prevent memory leak
334          if (i <= size)
# Line 349 | Line 349 | public class PriorityQueue<E> extends Ab
349          if (comparator == null) {
350              while (k > 1) {
351                  int j = k >> 1;
352 <                if (((Comparable)queue[j]).compareTo(queue[k]) <= 0)
352 >                if (((Comparable<E>)queue[j]).compareTo((E)queue[k]) <= 0)
353                      break;
354 <                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
354 >                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
355                  k = j;
356              }
357          } else {
358              while (k > 1) {
359                  int j = k >> 1;
360 <                if (comparator.compare(queue[j], queue[k]) <= 0)
360 >                if (comparator.compare((E)queue[j], (E)queue[k]) <= 0)
361                      break;
362 <                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
362 >                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
363                  k = j;
364              }
365          }
# Line 378 | Line 378 | public class PriorityQueue<E> extends Ab
378          int j;
379          if (comparator == null) {
380              while ((j = k << 1) <= size) {
381 <                if (j<size && ((Comparable)queue[j]).compareTo(queue[j+1]) > 0)
381 >                if (j<size && ((Comparable<E>)queue[j]).compareTo((E)queue[j+1]) > 0)
382                      j++; // j indexes smallest kid
383 <                if (((Comparable)queue[k]).compareTo(queue[j]) <= 0)
383 >                if (((Comparable<E>)queue[k]).compareTo((E)queue[j]) <= 0)
384                      break;
385 <                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
385 >                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
386                  k = j;
387              }
388          } else {
389              while ((j = k << 1) <= size) {
390 <                if (j < size && comparator.compare(queue[j], queue[j+1]) > 0)
390 >                if (j < size && comparator.compare((E)queue[j], (E)queue[j+1]) > 0)
391                      j++; // j indexes smallest kid
392 <                if (comparator.compare(queue[k], queue[j]) <= 0)
392 >                if (comparator.compare((E)queue[k], (E)queue[j]) <= 0)
393                      break;
394 <                E tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
394 >                Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
395                  k = j;
396              }
397          }
398      }
399  
400 <    public Comparator comparator() {
400 >    public Comparator<? super E> comparator() {
401          return comparator;
402      }
403  
# Line 435 | Line 435 | public class PriorityQueue<E> extends Ab
435  
436          // Read in array length and allocate array
437          int arrayLength = s.readInt();
438 <        queue = (E[]) new Object[arrayLength];
438 >        queue = new Object[arrayLength];
439  
440          // Read in all elements in the proper order.
441          for (int i=0; i<size; i++)
442 <            queue[i] = (E)s.readObject();
442 >            queue[i] = s.readObject();
443      }
444  
445   }

Diff Legend

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