ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/ArrayDeque.java
(Generate patch)

Comparing jsr166/src/main/java/util/ArrayDeque.java (file contents):
Revision 1.17 by dl, Thu Sep 15 16:55:24 2005 UTC vs.
Revision 1.26 by jsr166, Mon Sep 19 13:42:19 2005 UTC

# Line 479 | Line 479 | public class ArrayDeque<E> extends Abstr
479          return removeFirst();
480      }
481  
482 +    private void checkInvariants() {
483 +        assert elements[tail] == null;
484 +        assert head == tail ? elements[head] == null :
485 +            (elements[head] != null &&
486 +             elements[(tail - 1) & (elements.length - 1)] != null);
487 +        assert elements[(head - 1) & (elements.length - 1)] == null;
488 +    }
489 +
490      /**
491       * Removes the element at the specified position in the elements array,
492       * adjusting head and tail as necessary.  This can result in motion of
# Line 490 | Line 498 | public class ArrayDeque<E> extends Abstr
498       * @return true if elements moved backwards
499       */
500      private boolean delete(int i) {
501 <        int mask = elements.length - 1;
501 >        checkInvariants();
502 >        final E[] elements = this.elements;
503 >        final int mask = elements.length - 1;
504 >        final int h = head;
505 >        final int t = tail;
506 >        final int front = (i - h) & mask;
507 >        final int back  = (t - i) & mask;
508  
509          // Invariant: head <= i < tail mod circularity
510 <        if (((i - head) & mask) >= ((tail - head) & mask))
510 >        if (front >= ((t - h) & mask))
511              throw new ConcurrentModificationException();
512  
513 <        // Case 1: Deque doesn't wrap
514 <        // Case 2: Deque does wrap and removed element is in the head portion
515 <        if (i >= head) {
516 <            System.arraycopy(elements, head, elements, head + 1, i - head);
517 <            elements[head] = null;
518 <            head = (head + 1) & mask;
519 <            return false;
520 <        }
521 <
522 <        // Case 3: Deque wraps and removed element is in the tail portion
523 <        tail--;
524 <        System.arraycopy(elements, i + 1, elements, i, tail - i);
525 <        elements[tail] = null;
526 <        return true;
513 >        // Optimize for least element motion
514 >        if (front < back) {
515 >            if (h <= i) {
516 >                System.arraycopy(elements, h, elements, h + 1, front);
517 >            } else { // Wrap around
518 >                System.arraycopy(elements, 0, elements, 1, i);
519 >                elements[0] = elements[mask];
520 >                System.arraycopy(elements, h, elements, h + 1, mask - h);
521 >            }
522 >            elements[h] = null;
523 >            head = (h + 1) & mask;
524 >            return false;
525 >        } else {
526 >            if (i < t) { // Copy the null tail as well
527 >                System.arraycopy(elements, i + 1, elements, i, back);
528 >                tail = t - 1;
529 >            } else { // Wrap around
530 >                System.arraycopy(elements, i + 1, elements, i, mask - i);
531 >                elements[mask] = elements[0];
532 >                System.arraycopy(elements, 1, elements, 0, t);
533 >                tail = (t - 1) & mask;
534 >            }
535 >            return true;
536 >        }
537      }
538  
539      // *** Collection Methods ***
# Line 538 | Line 562 | public class ArrayDeque<E> extends Abstr
562       * order that elements would be dequeued (via successive calls to
563       * {@link #remove} or popped (via successive calls to {@link #pop}).
564       *
565 <     * @return an <tt>Iterator</tt> over the elements in this deque
565 >     * @return an iterator over the elements in this deque
566       */
567      public Iterator<E> iterator() {
568          return new DeqIterator();
569      }
570  
547 –    /**
548 –     * Returns an iterator over the elements in this deque in reverse
549 –     * sequential order.  The elements will be returned in order from
550 –     * last (tail) to first (head).
551 –     *
552 –     * @return an iterator over the elements in this deque in reverse
553 –     * sequence
554 –     */
571      public Iterator<E> descendingIterator() {
572          return new DescendingIterator();
573      }
# Line 579 | Line 595 | public class ArrayDeque<E> extends Abstr
595          }
596  
597          public E next() {
582 –            E result;
598              if (cursor == fence)
599                  throw new NoSuchElementException();
600 +            E result = elements[cursor];
601              // This check doesn't catch all possible comodifications,
602              // but does catch the ones that corrupt traversal
603 <            if (tail != fence || (result = elements[cursor]) == null)
603 >            if (tail != fence || result == null)
604                  throw new ConcurrentModificationException();
605              lastRet = cursor;
606              cursor = (cursor + 1) & (elements.length - 1);
# Line 594 | Line 610 | public class ArrayDeque<E> extends Abstr
610          public void remove() {
611              if (lastRet < 0)
612                  throw new IllegalStateException();
613 <            if (delete(lastRet)) // if left-shifted, undo increment in next()
613 >            if (delete(lastRet)) { // if left-shifted, undo increment in next()
614                  cursor = (cursor - 1) & (elements.length - 1);
615 +                fence = tail;
616 +            }
617              lastRet = -1;
600 –            fence = tail;
618          }
619      }
620  
604 –
621      private class DescendingIterator implements Iterator<E> {
622 <        /*
622 >        /*
623           * This class is nearly a mirror-image of DeqIterator, using
624 <         * (tail-1) instead of head for initial cursor, (head-1)
625 <         * instead of tail for fence, and elements.length instead of -1
610 <         * for sentinel. It shares the same structure, but not many
611 <         * actual lines of code.
624 >         * tail instead of head for initial cursor, and head instead of
625 >         * tail for fence.
626           */
627 <        private int cursor = (tail - 1) & (elements.length - 1);
628 <        private int fence =  (head - 1) & (elements.length - 1);
629 <        private int lastRet = elements.length;
627 >        private int cursor = tail;
628 >        private int fence = head;
629 >        private int lastRet = -1;
630  
631          public boolean hasNext() {
632              return cursor != fence;
633          }
634  
635          public E next() {
622 –            E result;
636              if (cursor == fence)
637                  throw new NoSuchElementException();
638 <            if (((head - 1) & (elements.length - 1)) != fence ||
639 <                (result = elements[cursor]) == null)
638 >            cursor = (cursor - 1) & (elements.length - 1);
639 >            E result = elements[cursor];
640 >            if (head != fence || result == null)
641                  throw new ConcurrentModificationException();
642              lastRet = cursor;
629 –            cursor = (cursor - 1) & (elements.length - 1);
643              return result;
644          }
645  
646          public void remove() {
647 <            if (lastRet >= elements.length)
647 >            if (lastRet < 0)
648                  throw new IllegalStateException();
649 <            if (!delete(lastRet))
649 >            if (!delete(lastRet)) {
650                  cursor = (cursor + 1) & (elements.length - 1);
651 <            lastRet = elements.length;
652 <            fence = (head - 1) & (elements.length - 1);
651 >                fence = head;
652 >            }
653 >            lastRet = -1;
654          }
655      }
656  
# Line 798 | Line 812 | public class ArrayDeque<E> extends Abstr
812          s.defaultWriteObject();
813  
814          // Write out size
815 <        int size = size();
802 <        s.writeInt(size);
815 >        s.writeInt(size());
816  
817          // Write out elements in order.
805 –        int i = head;
818          int mask = elements.length - 1;
819 <        for (int j = 0; j < size; j++) {
819 >        for (int i = head; i != tail; i = (i + 1) & mask)
820              s.writeObject(elements[i]);
809 –            i = (i + 1) & mask;
810 –        }
821      }
822  
823      /**
# Line 826 | Line 836 | public class ArrayDeque<E> extends Abstr
836          // Read in all elements in the proper order.
837          for (int i = 0; i < size; i++)
838              elements[i] = (E)s.readObject();
829 –
839      }
840   }

Diff Legend

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