[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.34, Wed Aug 27 01:33:50 2003 UTC revision 1.35, Wed Aug 27 10:27:07 2003 UTC
# Line 392  Line 392 
392      }      }
393    
394      private class Itr implements Iterator<E> {      private class Itr implements Iterator<E> {
395    
396          /**          /**
397           * Index (into queue array) of element to be returned by           * Index (into queue array) of element to be returned by
398           * subsequent call to next.           * subsequent call to next.
# Line 412  Line 413 
413           */           */
414          private int expectedModCount = modCount;          private int expectedModCount = modCount;
415    
416            // Workarounds until version that better handles remove() installed.
417            // These are used to copy-on-write the array upon first remove
418            private Object[] q = queue;
419            private int qsize = size;
420    
421          public boolean hasNext() {          public boolean hasNext() {
422              return cursor <= size;              return cursor <= qsize;
423          }          }
424    
425          public E next() {          public E next() {
426              checkForComodification();              checkForComodification();
427              if (cursor > size)              if (cursor > qsize)
428                  throw new NoSuchElementException();                  throw new NoSuchElementException();
429              E result = (E) queue[cursor];              E result = (E) q[cursor];
430              lastRet = cursor++;              lastRet = cursor++;
431              return result;              return result;
432          }          }
# Line 430  Line 436 
436                  throw new IllegalStateException();                  throw new IllegalStateException();
437              checkForComodification();              checkForComodification();
438    
439              PriorityQueue.this.remove(lastRet);              // Copy on first remove
440              cursor--;              if (q == queue) {
441                    q = new Object[queue.length];
442                    System.arraycopy(queue, 0, q, 0, queue.length);
443                }
444                PriorityQueue.this.remove(q[lastRet]);
445    
446              lastRet = 0;              lastRet = 0;
447              expectedModCount = modCount;              expectedModCount = modCount;
448          }          }
# Line 471  Line 482 
482          E result = (E) queue[i];          E result = (E) queue[i];
483          queue[i] = queue[size];          queue[i] = queue[size];
484          queue[size--] = null;  // Drop extra ref to prevent memory leak          queue[size--] = null;  // Drop extra ref to prevent memory leak
485          if (i <= size)          if (i <= size) {
486              fixDown(i);              fixDown(i);
487                fixUp(i);
488            }
489    
490          return result;          return result;
491      }      }
492    
# Line 496  Line 510 
510              }              }
511          } else {          } else {
512              while (k > 1) {              while (k > 1) {
513                  int j = k >> 1;                  int j = k >>> 1;
514                  if (comparator.compare((E)queue[j], (E)queue[k]) <= 0)                  if (comparator.compare((E)queue[j], (E)queue[k]) <= 0)
515                      break;                      break;
516                  Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;                  Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
# Line 518  Line 532 
532          int j;          int j;
533          if (comparator == null) {          if (comparator == null) {
534              while ((j = k << 1) <= size && (j > 0)) {              while ((j = k << 1) <= size && (j > 0)) {
535                  if (j<size && ((Comparable<E>)queue[j]).compareTo((E)queue[j+1]) > 0)                  if (j<size &&
536                        ((Comparable<E>)queue[j]).compareTo((E)queue[j+1]) > 0)
537                      j++; // j indexes smallest kid                      j++; // j indexes smallest kid
538    
539                  if (((Comparable<E>)queue[k]).compareTo((E)queue[j]) <= 0)                  if (((Comparable<E>)queue[k]).compareTo((E)queue[j]) <= 0)
540                      break;                      break;
541                  Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;                  Object tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
# Line 527  Line 543 
543              }              }
544          } else {          } else {
545              while ((j = k << 1) <= size && (j > 0)) {              while ((j = k << 1) <= size && (j > 0)) {
546                  if (j < size && comparator.compare((E)queue[j], (E)queue[j+1]) > 0)                  if (j<size &&
547                        comparator.compare((E)queue[j], (E)queue[j+1]) > 0)
548                      j++; // j indexes smallest kid                      j++; // j indexes smallest kid
549                  if (comparator.compare((E)queue[k], (E)queue[j]) <= 0)                  if (comparator.compare((E)queue[k], (E)queue[j]) <= 0)
550                      break;                      break;
# Line 535  Line 552 
552                  k = j;                  k = j;
553              }              }
554          }          }
555    
556      }      }
557    
558    

Legend:
Removed from v.1.34  
changed lines
  Added in v.1.35

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8