[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.54, Thu Nov 24 03:44:57 2005 UTC revision 1.55, Sun Nov 27 20:41:02 2005 UTC
# Line 68  Line 68 
68      private static final int DEFAULT_INITIAL_CAPACITY = 11;      private static final int DEFAULT_INITIAL_CAPACITY = 11;
69    
70      /**      /**
71       * Priority queue represented as a balanced binary heap: the two children       * Priority queue represented as a balanced binary heap: the two
72       * of queue[n] are queue[2*n] and queue[2*n + 1].  The priority queue is       * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
73       * ordered by comparator, or by the elements' natural ordering, if       * priority queue is ordered by comparator, or by the elements'
74       * comparator is null:  For each node n in the heap and each descendant d       * natural ordering, if comparator is null: For each node n in the
75       * of n, n <= d.       * heap and each descendant d of n, n <= d.  The element with the
76       *       * lowest value is in queue[0], assuming the queue is nonempty.
      * The element with the lowest value is in queue[1], assuming the queue is  
      * nonempty.  (A one-based array is used in preference to the traditional  
      * zero-based array to simplify parent and child calculations.)  
      *  
      * queue.length must be >= 2, even if size == 0.  
77       */       */
78      private transient Object[] queue;      private transient Object[] queue;
79    
# Line 134  Line 129 
129       */       */
130      public PriorityQueue(int initialCapacity,      public PriorityQueue(int initialCapacity,
131                           Comparator<? super E> comparator) {                           Comparator<? super E> comparator) {
132            // Note: This restriction of at least one is not actually needed,
133            // but continues for 1.5 compatibility
134          if (initialCapacity < 1)          if (initialCapacity < 1)
135              throw new IllegalArgumentException();              throw new IllegalArgumentException();
136          this.queue = new Object[initialCapacity + 1];          this.queue = new Object[initialCapacity];
137          this.comparator = comparator;          this.comparator = comparator;
138      }      }
139    
140      /**      /**
      * Common code to initialize underlying queue array across  
      * constructors below.  
      */  
     private void initializeArray(Collection<? extends E> c) {  
         int sz = c.size();  
         int initialCapacity = (int)Math.min((sz * 110L) / 100,  
                                             Integer.MAX_VALUE - 1);  
         if (initialCapacity < 1)  
             initialCapacity = 1;  
   
         this.queue = new Object[initialCapacity + 1];  
     }  
   
     /**  
      * Initially fill elements of the queue array under the  
      * knowledge that it is sorted or is another PQ, in which  
      * case we can just place the elements in the order presented.  
      */  
     private void fillFromSorted(Collection<? extends E> c) {  
         for (Iterator<? extends E> i = c.iterator(); i.hasNext(); ) {  
             int k = ++size;  
             if (k >= queue.length)  
                 grow(k);  
             queue[k] = i.next();  
         }  
     }  
   
     /**  
      * Initially fill elements of the queue array that is not to our knowledge  
      * sorted, so we must rearrange the elements to guarantee the heap  
      * invariant.  
      */  
     private void fillFromUnsorted(Collection<? extends E> c) {  
         for (Iterator<? extends E> i = c.iterator(); i.hasNext(); ) {  
             int k = ++size;  
             if (k >= queue.length)  
                 grow(k);  
             queue[k] = i.next();  
         }  
         heapify();  
     }  
   
     /**  
141       * Creates a <tt>PriorityQueue</tt> containing the elements in the       * Creates a <tt>PriorityQueue</tt> containing the elements in the
142       * specified collection.  The priority queue has an initial       * specified collection.   If the specified collection is an
      * capacity of 110% of the size of the specified collection or 1  
      * if the collection is empty.  If the specified collection is an  
143       * instance of a {@link java.util.SortedSet} or is another       * instance of a {@link java.util.SortedSet} or is another
144       * <tt>PriorityQueue</tt>, the priority queue will be ordered       * <tt>PriorityQueue</tt>, the priority queue will be ordered
145       * according to the same ordering.  Otherwise, this priority queue       * according to the same ordering.  Otherwise, this priority queue
# Line 202  Line 154 
154       *         of its elements are null       *         of its elements are null
155       */       */
156      public PriorityQueue(Collection<? extends E> c) {      public PriorityQueue(Collection<? extends E> c) {
157          initializeArray(c);          initFromCollection(c);
158          if (c instanceof SortedSet) {          if (c instanceof SortedSet)
159              SortedSet<? extends E> s = (SortedSet<? extends E>)c;              comparator = (Comparator<? super E>)
160              comparator = (Comparator<? super E>)s.comparator();                  ((SortedSet<? extends E>)c).comparator();
161              fillFromSorted(s);          else if (c instanceof PriorityQueue)
162          } else if (c instanceof PriorityQueue) {              comparator = (Comparator<? super E>)
163              PriorityQueue<? extends E> s = (PriorityQueue<? extends E>) c;                  ((PriorityQueue<? extends E>)c).comparator();
164              comparator = (Comparator<? super E>)s.comparator();          else {
             fillFromSorted(s);  
         } else {  
165              comparator = null;              comparator = null;
166              fillFromUnsorted(c);              heapify();
167          }          }
168      }      }
169    
170      /**      /**
171       * Creates a <tt>PriorityQueue</tt> containing the elements in the       * Creates a <tt>PriorityQueue</tt> containing the elements in the
172       * specified priority queue.  The priority queue has an initial       * specified priority queue.  This priority queue will be
      * capacity of 110% of the size of the specified priority queue or  
      * 1 if the priority queue is empty.  This priority queue will be  
173       * ordered according to the same ordering as the given priority       * ordered according to the same ordering as the given priority
174       * queue.       * queue.
175       *       *
# Line 234  Line 182 
182       *         of its elements are null       *         of its elements are null
183       */       */
184      public PriorityQueue(PriorityQueue<? extends E> c) {      public PriorityQueue(PriorityQueue<? extends E> c) {
         initializeArray(c);  
185          comparator = (Comparator<? super E>)c.comparator();          comparator = (Comparator<? super E>)c.comparator();
186          fillFromSorted(c);          initFromCollection(c);
187      }      }
188    
189      /**      /**
190       * Creates a <tt>PriorityQueue</tt> containing the elements in the       * Creates a <tt>PriorityQueue</tt> containing the elements in the
191       * specified sorted set.  The priority queue has an initial       * specified sorted set.  This priority queue will be ordered
      * capacity of 110% of the size of the specified sorted set or 1  
      * if the sorted set is empty.  This priority queue will be ordered  
192       * according to the same ordering as the given sorted set.       * according to the same ordering as the given sorted set.
193       *       *
194       * @param  c the sorted set whose elements are to be placed       * @param  c the sorted set whose elements are to be placed
# Line 255  Line 200 
200       *         of its elements are null       *         of its elements are null
201       */       */
202      public PriorityQueue(SortedSet<? extends E> c) {      public PriorityQueue(SortedSet<? extends E> c) {
         initializeArray(c);  
203          comparator = (Comparator<? super E>)c.comparator();          comparator = (Comparator<? super E>)c.comparator();
204          fillFromSorted(c);          initFromCollection(c);
205      }      }
206    
207      /**      /**
208       * Resize array, if necessary, to be able to hold given index.       * Initialize queue array with elements from the given Collection.
209         * @param c the collection
210       */       */
211      private void grow(int index) {      private void initFromCollection(Collection<? extends E> c) {
212          int newlen = queue.length;          Object[] a = c.toArray();
213          if (index < newlen) // don't need to grow          // If c.toArray incorrectly doesn't return Object[], copy it.
214              return;          if (a.getClass() != Object[].class)
215          if (index == Integer.MAX_VALUE)              a = Arrays.copyOf(a, a.length, Object[].class);
216              throw new OutOfMemoryError();          queue = a;
217          while (newlen <= index) {          size = a.length;
             if (newlen >= Integer.MAX_VALUE / 2)  // avoid overflow  
                 newlen = Integer.MAX_VALUE;  
             else  
                 newlen <<= 1;  
218          }          }
219          queue = Arrays.copyOf(queue, newlen);  
220        /**
221         * Increases the capacity of the array.
222         *
223         * @param minCapacity the desired minimum capacity
224         */
225        private void grow(int minCapacity) {
226            if (minCapacity < 0) // overflow
227                throw new OutOfMemoryError();
228            int oldCapacity = queue.length;
229            // Double size if small; else grow by 50%
230            int newCapacity = ((oldCapacity < 64)?
231                               ((oldCapacity + 1) * 2):
232                               ((oldCapacity * 3) / 2));
233            if (newCapacity < minCapacity)
234                newCapacity = minCapacity;
235            queue = Arrays.copyOf(queue, newCapacity);
236      }      }
237    
238      /**      /**
# Line 304  Line 261 
261          if (e == null)          if (e == null)
262              throw new NullPointerException();              throw new NullPointerException();
263          modCount++;          modCount++;
264          ++size;          int i = size;
265            if (i >= queue.length)
266          // Grow backing store if necessary              grow(i + 1);
267          if (size >= queue.length)          size = i + 1;
268              grow(size);          if (i == 0)
269                queue[0] = e;
270          queue[size] = e;          else
271          fixUp(size);              siftUp(i, e);
272          return true;          return true;
273      }      }
274    
275      public E peek() {      public E peek() {
276          if (size == 0)          if (size == 0)
277              return null;              return null;
278          return (E) queue[1];          return (E) queue[0];
279      }      }
280    
281      private int indexOf(Object o) {      private int indexOf(Object o) {
282          if (o == null)          if (o != null) {
283              return -1;              for (int i = 0; i < size; i++)
         for (int i = 1; i <= size; i++)  
284              if (o.equals(queue[i]))              if (o.equals(queue[i]))
285                  return i;                  return i;
286            }
287          return -1;          return -1;
288      }      }
289    
# Line 351  Line 308 
308      }      }
309    
310      /**      /**
311         * Version of remove using reference equality, not equals.
312         * Needed by iterator.remove
313         *
314         * @param o element to be removed from this queue, if present
315         * @return <tt>true</tt> if removed.
316         */
317        boolean removeEq(Object o) {
318            for (int i = 0; i < size; i++) {
319                if (o == queue[i]) {
320                    removeAt(i);
321                    return true;
322                }
323            }
324            return false;
325        }
326    
327        /**
328       * Returns <tt>true</tt> if this queue contains the specified element.       * Returns <tt>true</tt> if this queue contains the specified element.
329       * More formally, returns <tt>true</tt> if and only if this queue contains       * More formally, returns <tt>true</tt> if and only if this queue contains
330       * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.       * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
# Line 373  Line 347 
347       * @return an array containing all of the elements in this queue.       * @return an array containing all of the elements in this queue.
348       */       */
349      public Object[] toArray() {      public Object[] toArray() {
350          return Arrays.copyOfRange(queue, 1, size+1);          return Arrays.copyOf(queue, size);
351      }      }
352    
353      /**      /**
# Line 403  Line 377 
377      public <T> T[] toArray(T[] a) {      public <T> T[] toArray(T[] a) {
378          if (a.length < size)          if (a.length < size)
379              // Make a new array of a's runtime type, but my contents:              // Make a new array of a's runtime type, but my contents:
380              return (T[]) Arrays.copyOfRange(queue, 1, size+1, a.getClass());              return (T[]) Arrays.copyOf(queue, size, a.getClass());
381          System.arraycopy(queue, 1, a, 0, size);          System.arraycopy(queue, 0, a, 0, size);
382          if (a.length > size)          if (a.length > size)
383              a[size] = null;              a[size] = null;
384          return a;          return a;
# Line 420  Line 394 
394          return new Itr();          return new Itr();
395      }      }
396    
397      private class Itr implements Iterator<E> {      private final class Itr implements Iterator<E> {
   
398          /**          /**
399           * Index (into queue array) of element to be returned by           * Index (into queue array) of element to be returned by
400           * subsequent call to next.           * subsequent call to next.
401           */           */
402          private int cursor = 1;          private int cursor = 0;
403    
404          /**          /**
405           * Index of element returned by most recent call to next,           * Index of element returned by most recent call to next,
406           * unless that element came from the forgetMeNot list.           * unless that element came from the forgetMeNot list.
407           * Reset to 0 if element is deleted by a call to remove.           * Set to -1 if element is deleted by a call to remove.
          */  
         private int lastRet = 0;  
   
         /**  
          * The modCount value that the iterator believes that the backing  
          * List should have.  If this expectation is violated, the iterator  
          * has detected concurrent modification.  
408           */           */
409          private int expectedModCount = modCount;          private int lastRet = -1;
410    
411          /**          /**
412           * A list of elements that were moved from the unvisited portion of           * A queue of elements that were moved from the unvisited portion of
413           * the heap into the visited portion as a result of "unlucky" element           * the heap into the visited portion as a result of "unlucky" element
414           * removals during the iteration.  (Unlucky element removals are those           * removals during the iteration.  (Unlucky element removals are those
415           * that require a fixup instead of a fixdown.)  We must visit all of           * that require a siftup instead of a siftdown.)  We must visit all of
416           * the elements in this list to complete the iteration.  We do this           * the elements in this list to complete the iteration.  We do this
417           * after we've completed the "normal" iteration.           * after we've completed the "normal" iteration.
418           *           *
419           * We expect that most iterations, even those involving removals,           * We expect that most iterations, even those involving removals,
420           * will not use need to store elements in this field.           * will not use need to store elements in this field.
421           */           */
422          private ArrayList<E> forgetMeNot = null;          private ArrayDeque<E> forgetMeNot = null;
423    
424          /**          /**
425           * Element returned by the most recent call to next iff that           * Element returned by the most recent call to next iff that
426           * element was drawn from the forgetMeNot list.           * element was drawn from the forgetMeNot list.
427           */           */
428          private Object lastRetElt = null;          private E lastRetElt = null;
429    
430            /**
431             * The modCount value that the iterator believes that the backing
432             * List should have.  If this expectation is violated, the iterator
433             * has detected concurrent modification.
434             */
435            private int expectedModCount = modCount;
436    
437          public boolean hasNext() {          public boolean hasNext() {
438              return cursor <= size || forgetMeNot != null;              return cursor < size ||
439                    (forgetMeNot != null && !forgetMeNot.isEmpty());
440          }          }
441    
442          public E next() {          public E next() {
443              checkForComodification();              if (expectedModCount != modCount)
444              E result;                  throw new ConcurrentModificationException();
445              if (cursor <= size) {              if (cursor < size)
446                  result = (E) queue[cursor];                  return (E) queue[lastRet = cursor++];
447                  lastRet = cursor++;              if (forgetMeNot != null) {
448                    lastRet = -1;
449                    lastRetElt = forgetMeNot.poll();
450                    if (lastRetElt != null)
451                        return lastRetElt;
452              }              }
             else if (forgetMeNot == null)  
453                  throw new NoSuchElementException();                  throw new NoSuchElementException();
             else {  
                 int remaining = forgetMeNot.size();  
                 result = forgetMeNot.remove(remaining - 1);  
                 if (remaining == 1)  
                     forgetMeNot = null;  
                 lastRet = 0;  
                 lastRetElt = result;  
             }  
             return result;  
454          }          }
455    
456          public void remove() {          public void remove() {
457              checkForComodification();              if (expectedModCount != modCount)
458                    throw new ConcurrentModificationException();
459              if (lastRet != 0) {              if (lastRet == -1 && lastRetElt == null)
460                    throw new IllegalStateException();
461                if (lastRet != -1) {
462                  E moved = PriorityQueue.this.removeAt(lastRet);                  E moved = PriorityQueue.this.removeAt(lastRet);
463                  lastRet = 0;                  lastRet = -1;
464                  if (moved == null) {                  if (moved == null)
465                      cursor--;                      cursor--;
466                  } else {                  else {
467                      if (forgetMeNot == null)                      if (forgetMeNot == null)
468                          forgetMeNot = new ArrayList<E>();                          forgetMeNot = new ArrayDeque<E>();
469                      forgetMeNot.add(moved);                      forgetMeNot.add(moved);
470                  }                  }
             } else if (lastRetElt != null) {  
                 PriorityQueue.this.remove(lastRetElt);  
                 lastRetElt = null;  
471              } else {              } else {
472                  throw new IllegalStateException();                  PriorityQueue.this.removeEq(lastRetElt);
473                    lastRetElt = null;
474              }              }
   
475              expectedModCount = modCount;              expectedModCount = modCount;
476          }          }
477    
         final void checkForComodification() {  
             if (modCount != expectedModCount)  
                 throw new ConcurrentModificationException();  
         }  
478      }      }
479    
480      public int size() {      public int size() {
# Line 524  Line 487 
487       */       */
488      public void clear() {      public void clear() {
489          modCount++;          modCount++;
490            for (int i = 0; i < size; i++)
         // Null out element references to prevent memory leak  
         for (int i=1; i<=size; i++)  
491              queue[i] = null;              queue[i] = null;
   
492          size = 0;          size = 0;
493      }      }
494    
495      public E poll() {      public E poll() {
496          if (size == 0)          if (size == 0)
497              return null;              return null;
498            int s = --size;
499          modCount++;          modCount++;
500            E result = (E)queue[0];
501          E result = (E) queue[1];          E x = (E)queue[s];
502          queue[1] = queue[size];          queue[s] = null;
503          queue[size--] = null;  // Drop extra ref to prevent memory leak          if (s != 0)
504          if (size > 1)              siftDown(0, x);
             fixDown(1);  
   
505          return result;          return result;
506      }      }
507    
508      /**      /**
509       * Removes and returns the ith element from queue.  (Recall that queue       * Removes the ith element from queue.
      * is one-based, so 1 <= i <= size.)  
510       *       *
511       * Normally this method leaves the elements at positions from 1 up to i-1,       * Normally this method leaves the elements at up to i-1,
512       * inclusive, untouched.  Under these circumstances, it returns null.       * inclusive, untouched.  Under these circumstances, it returns
513       * Occasionally, in order to maintain the heap invariant, it must move       * null.  Occasionally, in order to maintain the heap invariant,
514       * the last element of the list to some index in the range [2, i-1],       * it must swap a later element of the list with one earlier than
515       * and move the element previously at position (i/2) to position i.       * i.  Under these circumstances, this method returns the element
516       * Under these circumstances, this method returns the element that was       * that was previously at the end of the list and is now at some
517       * previously at the end of the list and is now at some position between       * position before i. This fact is used by iterator.remove so as to
518       * 2 and i-1 inclusive.       * avoid missing traverseing elements.
519       */       */
520      private E removeAt(int i) {      private E removeAt(int i) {
521          assert i > 0 && i <= size;          assert i >= 0 && i < size;
522          modCount++;          modCount++;
523            int s = --size;
524          E moved = (E) queue[size];          if (s == i) // removed last element
525          queue[i] = moved;              queue[i] = null;
526          queue[size--] = null;  // Drop extra ref to prevent memory leak          else {
527          if (i <= size) {              E moved = (E) queue[s];
528              fixDown(i);              queue[s] = null;
529                siftDown(i, moved);
530              if (queue[i] == moved) {              if (queue[i] == moved) {
531                  fixUp(i);                  siftUp(i, moved);
532                  if (queue[i] != moved)                  if (queue[i] != moved)
533                      return moved;                      return moved;
534              }              }
# Line 578  Line 537 
537      }      }
538    
539      /**      /**
540       * Establishes the heap invariant (described above) assuming the heap       * Inserts item x at position k, maintaining heap invariant by
541       * satisfies the invariant except possibly for the leaf-node indexed by k       * promoting x up the tree until it is greater than or equal to
542       * (which may have a nextExecutionTime less than its parent's).       * its parent, or is the root.
543       *       *
544       * This method functions by "promoting" queue[k] up the hierarchy       * To simplify and speed up coercions and comparisons. the
545       * (by swapping it with its parent) repeatedly until queue[k]       * Comparable and Comparator versions are separated into different
546       * is greater than or equal to its parent.       * methods that are otherwise identical. (Similarly for siftDown.)
547       */       *
548      private void fixUp(int k) {       * @param k the position to fill
549          if (comparator == null) {       * @param x the item to insert
550              while (k > 1) {       */
551                  int j = k >> 1;      private void siftUp(int k, E x) {
552                  if (((Comparable<? super E>)queue[j]).compareTo((E)queue[k]) <= 0)          if (comparator != null)
553                      break;              siftUpUsingComparator(k, x);
554                  Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;          else
555                  k = j;              siftUpComparable(k, x);
556              }              }
557          } else {  
558              while (k > 1) {      private void siftUpComparable(int k, E x) {
559                  int j = k >>> 1;          Comparable<? super E> key = (Comparable<? super E>) x;
560                  if (comparator.compare((E)queue[j], (E)queue[k]) <= 0)          while (k > 0) {
561                int parent = (k - 1) >>> 1;
562                Object e = queue[parent];
563                if (key.compareTo((E)e) >= 0)
564                      break;                      break;
565                  Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;              queue[k] = e;
566                  k = j;              k = parent;
567            }
568            queue[k] = key;
569              }              }
570    
571        private void siftUpUsingComparator(int k, E x) {
572            while (k > 0) {
573                int parent = (k - 1) >>> 1;
574                Object e = queue[parent];
575                if (comparator.compare(x, (E)e) >= 0)
576                    break;
577                queue[k] = e;
578                k = parent;
579          }          }
580            queue[k] = x;
581      }      }
582    
583      /**      /**
584       * Establishes the heap invariant (described above) in the subtree       * Inserts item x at position k, maintaining heap invariant by
585       * rooted at k, which is assumed to satisfy the heap invariant except       * demoting x down the tree repeatedly until it is less than or
586       * possibly for node k itself (which may be greater than its children).       * equal to its children or is a leaf.
587       *       *
588       * This method functions by "demoting" queue[k] down the hierarchy       * @param k the position to fill
589       * (by swapping it with its smaller child) repeatedly until queue[k]       * @param x the item to insert
      * is less than or equal to its children.  
590       */       */
591      private void fixDown(int k) {      private void siftDown(int k, E x) {
592          int j;          if (comparator != null)
593          if (comparator == null) {              siftDownUsingComparator(k, x);
594              while ((j = k << 1) <= size && (j > 0)) {          else
595                  if (j<size &&              siftDownComparable(k, x);
596                      ((Comparable<? super E>)queue[j]).compareTo((E)queue[j+1]) > 0)      }
                     j++; // j indexes smallest kid  
597    
598                  if (((Comparable<? super E>)queue[k]).compareTo((E)queue[j]) <= 0)      private void siftDownComparable(int k, E x) {
599            Comparable<? super E> key = (Comparable<? super E>)x;
600            int half = size >>> 1;        // loop while a non-leaf
601            while (k < half) {
602                int child = (k << 1) + 1; // assume left child is least
603                Object c = queue[child];
604                int right = child + 1;
605                if (right < size &&
606                    ((Comparable<? super E>)c).compareTo((E)queue[right]) > 0)
607                    c = queue[child = right];
608                if (key.compareTo((E)c) <= 0)
609                      break;                      break;
610                  Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;              queue[k] = c;
611                  k = j;              k = child;
612              }              }
613          } else {          queue[k] = key;
             while ((j = k << 1) <= size && (j > 0)) {  
                 if (j<size &&  
                     comparator.compare((E)queue[j], (E)queue[j+1]) > 0)  
                     j++; // j indexes smallest kid  
                 if (comparator.compare((E)queue[k], (E)queue[j]) <= 0)  
                     break;  
                 Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;  
                 k = j;  
614              }              }
615    
616        private void siftDownUsingComparator(int k, E x) {
617            int half = size >>> 1;
618            while (k < half) {
619                int child = (k << 1) + 1;
620                Object c = queue[child];
621                int right = child + 1;
622                if (right < size &&
623                    comparator.compare((E)c, (E)queue[right]) > 0)
624                    c = queue[child = right];
625                if (comparator.compare(x, (E)c) <= 0)
626                    break;
627                queue[k] = c;
628                k = child;
629          }          }
630            queue[k] = x;
631      }      }
632    
633      /**      /**
# Line 646  Line 635 
635       * assuming nothing about the order of the elements prior to the call.       * assuming nothing about the order of the elements prior to the call.
636       */       */
637      private void heapify() {      private void heapify() {
638          for (int i = size/2; i >= 1; i--)          for (int i = (size >>> 1) - 1; i >= 0; i--)
639              fixDown(i);              siftDown(i, (E)queue[i]);
640      }      }
641    
642      /**      /**
# Line 678  Line 667 
667          s.defaultWriteObject();          s.defaultWriteObject();
668    
669          // Write out array length          // Write out array length
670          s.writeInt(queue.length);          // For compatibility with 1.5 version, must be at least 2.
671            s.writeInt(Math.max(2, queue.length));
672    
673          // Write out all elements in the proper order.          // Write out all elements in the proper order.
674          for (int i=1; i<=size; i++)          for (int i=0; i<size; i++)
675              s.writeObject(queue[i]);              s.writeObject(queue[i]);
676      }      }
677    
# Line 700  Line 690 
690          queue = new Object[arrayLength];          queue = new Object[arrayLength];
691    
692          // Read in all elements in the proper order.          // Read in all elements in the proper order.
693          for (int i=1; i<=size; i++)          for (int i=0; i<size; i++)
694              queue[i] = (E) s.readObject();              queue[i] = (E) s.readObject();
695      }      }
696    

Legend:
Removed from v.1.54  
changed lines
  Added in v.1.55

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8