equal
deleted
inserted
replaced
447 * @throws ArrayStoreException if the runtime type of the specified array |
447 * @throws ArrayStoreException if the runtime type of the specified array |
448 * is not a supertype of the runtime type of every element in |
448 * is not a supertype of the runtime type of every element in |
449 * this queue |
449 * this queue |
450 * @throws NullPointerException if the specified array is null |
450 * @throws NullPointerException if the specified array is null |
451 */ |
451 */ |
|
452 @SuppressWarnings("unchecked") |
452 public <T> T[] toArray(T[] a) { |
453 public <T> T[] toArray(T[] a) { |
453 if (a.length < size) |
454 if (a.length < size) |
454 // Make a new array of a's runtime type, but my contents: |
455 // Make a new array of a's runtime type, but my contents: |
455 return (T[]) Arrays.copyOf(queue, size, a.getClass()); |
456 return (T[]) Arrays.copyOf(queue, size, a.getClass()); |
456 System.arraycopy(queue, 0, a, 0, size); |
457 System.arraycopy(queue, 0, a, 0, size); |
512 public boolean hasNext() { |
513 public boolean hasNext() { |
513 return cursor < size || |
514 return cursor < size || |
514 (forgetMeNot != null && !forgetMeNot.isEmpty()); |
515 (forgetMeNot != null && !forgetMeNot.isEmpty()); |
515 } |
516 } |
516 |
517 |
|
518 @SuppressWarnings("unchecked") |
517 public E next() { |
519 public E next() { |
518 if (expectedModCount != modCount) |
520 if (expectedModCount != modCount) |
519 throw new ConcurrentModificationException(); |
521 throw new ConcurrentModificationException(); |
520 if (cursor < size) |
522 if (cursor < size) |
521 return (E) queue[lastRet = cursor++]; |
523 return (E) queue[lastRet = cursor++]; |
569 public E poll() { |
571 public E poll() { |
570 if (size == 0) |
572 if (size == 0) |
571 return null; |
573 return null; |
572 int s = --size; |
574 int s = --size; |
573 modCount++; |
575 modCount++; |
574 E result = (E) queue[0]; |
576 @SuppressWarnings("unchecked") |
575 E x = (E) queue[s]; |
577 E result = (E) queue[0]; |
|
578 @SuppressWarnings("unchecked") |
|
579 E x = (E) queue[s]; |
576 queue[s] = null; |
580 queue[s] = null; |
577 if (s != 0) |
581 if (s != 0) |
578 siftDown(0, x); |
582 siftDown(0, x); |
579 return result; |
583 return result; |
580 } |
584 } |
596 modCount++; |
600 modCount++; |
597 int s = --size; |
601 int s = --size; |
598 if (s == i) // removed last element |
602 if (s == i) // removed last element |
599 queue[i] = null; |
603 queue[i] = null; |
600 else { |
604 else { |
601 E moved = (E) queue[s]; |
605 @SuppressWarnings("unchecked") |
|
606 E moved = (E) queue[s]; |
602 queue[s] = null; |
607 queue[s] = null; |
603 siftDown(i, moved); |
608 siftDown(i, moved); |
604 if (queue[i] == moved) { |
609 if (queue[i] == moved) { |
605 siftUp(i, moved); |
610 siftUp(i, moved); |
606 if (queue[i] != moved) |
611 if (queue[i] != moved) |
627 siftUpUsingComparator(k, x); |
632 siftUpUsingComparator(k, x); |
628 else |
633 else |
629 siftUpComparable(k, x); |
634 siftUpComparable(k, x); |
630 } |
635 } |
631 |
636 |
|
637 @SuppressWarnings("unchecked") |
632 private void siftUpComparable(int k, E x) { |
638 private void siftUpComparable(int k, E x) { |
633 Comparable<? super E> key = (Comparable<? super E>) x; |
639 Comparable<? super E> key = (Comparable<? super E>) x; |
634 while (k > 0) { |
640 while (k > 0) { |
635 int parent = (k - 1) >>> 1; |
641 int parent = (k - 1) >>> 1; |
636 Object e = queue[parent]; |
642 Object e = queue[parent]; |
643 } |
649 } |
644 |
650 |
645 private void siftUpUsingComparator(int k, E x) { |
651 private void siftUpUsingComparator(int k, E x) { |
646 while (k > 0) { |
652 while (k > 0) { |
647 int parent = (k - 1) >>> 1; |
653 int parent = (k - 1) >>> 1; |
648 Object e = queue[parent]; |
654 @SuppressWarnings("unchecked") |
649 if (comparator.compare(x, (E) e) >= 0) |
655 E e = (E) queue[parent]; |
|
656 if (comparator.compare(x, e) >= 0) |
650 break; |
657 break; |
651 queue[k] = e; |
658 queue[k] = e; |
652 k = parent; |
659 k = parent; |
653 } |
660 } |
654 queue[k] = x; |
661 queue[k] = x; |
667 siftDownUsingComparator(k, x); |
674 siftDownUsingComparator(k, x); |
668 else |
675 else |
669 siftDownComparable(k, x); |
676 siftDownComparable(k, x); |
670 } |
677 } |
671 |
678 |
|
679 @SuppressWarnings("unchecked") |
672 private void siftDownComparable(int k, E x) { |
680 private void siftDownComparable(int k, E x) { |
673 Comparable<? super E> key = (Comparable<? super E>)x; |
681 Comparable<? super E> key = (Comparable<? super E>)x; |
674 int half = size >>> 1; // loop while a non-leaf |
682 int half = size >>> 1; // loop while a non-leaf |
675 while (k < half) { |
683 while (k < half) { |
676 int child = (k << 1) + 1; // assume left child is least |
684 int child = (k << 1) + 1; // assume left child is least |
685 k = child; |
693 k = child; |
686 } |
694 } |
687 queue[k] = key; |
695 queue[k] = key; |
688 } |
696 } |
689 |
697 |
|
698 @SuppressWarnings("unchecked") |
690 private void siftDownUsingComparator(int k, E x) { |
699 private void siftDownUsingComparator(int k, E x) { |
691 int half = size >>> 1; |
700 int half = size >>> 1; |
692 while (k < half) { |
701 while (k < half) { |
693 int child = (k << 1) + 1; |
702 int child = (k << 1) + 1; |
694 Object c = queue[child]; |
703 Object c = queue[child]; |
706 |
715 |
707 /** |
716 /** |
708 * Establishes the heap invariant (described above) in the entire tree, |
717 * Establishes the heap invariant (described above) in the entire tree, |
709 * assuming nothing about the order of the elements prior to the call. |
718 * assuming nothing about the order of the elements prior to the call. |
710 */ |
719 */ |
|
720 @SuppressWarnings("unchecked") |
711 private void heapify() { |
721 private void heapify() { |
712 for (int i = (size >>> 1) - 1; i >= 0; i--) |
722 for (int i = (size >>> 1) - 1; i >= 0; i--) |
713 siftDown(i, (E) queue[i]); |
723 siftDown(i, (E) queue[i]); |
714 } |
724 } |
715 |
725 |