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

Legend:
Removed from v.1.15  
changed lines
  Added in v.1.16

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8