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.82 by jsr166, Sat Oct 22 19:42:42 2016 UTC vs.
Revision 1.99 by jsr166, Sun Oct 30 16:32:40 2016 UTC

# Line 93 | Line 93 | public class ArrayDeque<E> extends Abstr
93      private void grow(int needed) {
94          // overflow-conscious code
95          // checkInvariants();
96 <        int oldCapacity = elements.length;
96 >        final int oldCapacity = elements.length;
97          int newCapacity;
98          // Double size if small; else grow by 50%
99          int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
# Line 115 | Line 115 | public class ArrayDeque<E> extends Abstr
115  
116      /** Capacity calculation for edge conditions, especially overflow. */
117      private int newCapacity(int needed, int jump) {
118 <        int oldCapacity = elements.length;
119 <        int minCapacity;
118 >        final int oldCapacity = elements.length, minCapacity;
119          if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
120              if (minCapacity < 0)
121                  throw new IllegalStateException("Sorry, deque too big");
# Line 184 | Line 183 | public class ArrayDeque<E> extends Abstr
183       * @throws NullPointerException if the specified collection is null
184       */
185      public ArrayDeque(Collection<? extends E> c) {
186 <        Object[] elements = c.toArray();
186 >        Object[] es = c.toArray();
187          // defend against c.toArray (incorrectly) not returning Object[]
188          // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
189 <        if (elements.getClass() != Object[].class)
190 <            elements = Arrays.copyOf(elements, size, Object[].class);
191 <        for (Object obj : elements)
189 >        if (es.getClass() != Object[].class)
190 >            es = Arrays.copyOf(es, es.length, Object[].class);
191 >        for (Object obj : es)
192              Objects.requireNonNull(obj);
193 <        size = elements.length;
194 <        this.elements = elements;
193 >        this.elements = es;
194 >        this.size = es.length;
195      }
196  
197      /**
# Line 200 | Line 199 | public class ArrayDeque<E> extends Abstr
199       * Precondition and postcondition: 0 <= i < modulus.
200       */
201      static final int inc(int i, int modulus) {
202 <        if (++i == modulus) i = 0;
202 >        if (++i >= modulus) i = 0;
203          return i;
204      }
205  
# Line 209 | Line 208 | public class ArrayDeque<E> extends Abstr
208       * Precondition and postcondition: 0 <= i < modulus.
209       */
210      static final int dec(int i, int modulus) {
211 <        if (--i < 0) i += modulus;
211 >        if (--i < 0) i = modulus - 1;
212          return i;
213      }
214  
# Line 234 | Line 233 | public class ArrayDeque<E> extends Abstr
233       * Returns element at array index i.
234       */
235      @SuppressWarnings("unchecked")
236 <    final E elementAt(int i) {
236 >    private E elementAt(int i) {
237          return (E) elements[i];
238      }
239  
240      /**
241       * A version of elementAt that checks for null elements.
242       * This check doesn't catch all possible comodifications,
243 <     * but does catch ones that corrupt traversal.
243 >     * but does catch ones that corrupt traversal.  It's a little
244 >     * surprising that javac allows this abuse of generics.
245       */
246 <    E checkedElementAt(Object[] elements, int i) {
247 <        @SuppressWarnings("unchecked") E e = (E) elements[i];
246 >    static final <E> E nonNullElementAt(Object[] es, int i) {
247 >        @SuppressWarnings("unchecked") E e = (E) es[i];
248          if (e == null)
249              throw new ConcurrentModificationException();
250          return e;
# Line 263 | Line 263 | public class ArrayDeque<E> extends Abstr
263      public void addFirst(E e) {
264          // checkInvariants();
265          Objects.requireNonNull(e);
266 <        final Object[] elements;
267 <        final int capacity, s;
268 <        if ((s = size) == (capacity = (elements = this.elements).length))
269 <            addFirstSlowPath(e);
270 <        else
271 <            elements[head = dec(head, capacity)] = e;
266 >        Object[] es;
267 >        int capacity, h;
268 >        final int s;
269 >        if ((s = size) == (capacity = (es = elements).length)) {
270 >            grow(1);
271 >            capacity = (es = elements).length;
272 >        }
273 >        if ((h = head - 1) < 0) h = capacity - 1;
274 >        es[head = h] = e;
275          size = s + 1;
273    }
274
275    private void addFirstSlowPath(E e) {
276        grow(1);
277        final Object[] elements = this.elements;
278        elements[head = dec(head, elements.length)] = e;
276          // checkInvariants();
277      }
278  
# Line 290 | Line 287 | public class ArrayDeque<E> extends Abstr
287      public void addLast(E e) {
288          // checkInvariants();
289          Objects.requireNonNull(e);
290 <        final Object[] elements;
291 <        final int capacity, s;
292 <        if ((s = size) == (capacity = (elements = this.elements).length))
293 <            addLastSlowPath(e);
294 <        else
295 <            elements[add(head, s, capacity)] = e;
290 >        Object[] es;
291 >        int capacity;
292 >        final int s;
293 >        if ((s = size) == (capacity = (es = elements).length)) {
294 >            grow(1);
295 >            capacity = (es = elements).length;
296 >        }
297 >        es[add(head, s, capacity)] = e;
298          size = s + 1;
300    }
301
302    private void addLastSlowPath(E e) {
303        grow(1);
304        final Object[] elements = this.elements;
305        elements[add(head, size, elements.length)] = e;
299          // checkInvariants();
300      }
301  
# Line 317 | Line 310 | public class ArrayDeque<E> extends Abstr
310       * @throws NullPointerException if the specified collection or any
311       *         of its elements are null
312       */
320    @Override
313      public boolean addAll(Collection<? extends E> c) {
314 +        final int s = size, needed = c.size() - (elements.length - s);
315 +        if (needed > 0)
316 +            grow(needed);
317 +        c.forEach((e) -> addLast(e));
318          // checkInvariants();
319 <        Object[] a, elements;
324 <        int newcomers, capacity, s = size;
325 <        if ((newcomers = (a = c.toArray()).length) == 0)
326 <            return false;
327 <        while ((capacity = (elements = this.elements).length) - s < newcomers)
328 <            grow(newcomers - (capacity - s));
329 <        int i = add(head, s, capacity);
330 <        for (Object x : a) {
331 <            Objects.requireNonNull(x);
332 <            elements[i] = x;
333 <            i = inc(i, capacity);
334 <            size++;
335 <        }
336 <        return true;
319 >        return size > s;
320      }
321  
322      /**
# Line 365 | Line 348 | public class ArrayDeque<E> extends Abstr
348       */
349      public E removeFirst() {
350          // checkInvariants();
351 <        E x = pollFirst();
352 <        if (x == null)
351 >        E e = pollFirst();
352 >        if (e == null)
353              throw new NoSuchElementException();
354 <        return x;
354 >        return e;
355      }
356  
357      /**
# Line 376 | Line 359 | public class ArrayDeque<E> extends Abstr
359       */
360      public E removeLast() {
361          // checkInvariants();
362 <        E x = pollLast();
363 <        if (x == null)
362 >        E e = pollLast();
363 >        if (e == null)
364              throw new NoSuchElementException();
365 <        return x;
365 >        return e;
366      }
367  
368      public E pollFirst() {
369          // checkInvariants();
370 <        final int s, h;
371 <        if ((s = size) == 0)
370 >        int s, h;
371 >        if ((s = size) <= 0)
372              return null;
373 <        final Object[] elements = this.elements;
374 <        @SuppressWarnings("unchecked") E e = (E) elements[h = head];
375 <        elements[h] = null;
376 <        head = inc(h, elements.length);
373 >        final Object[] es = elements;
374 >        @SuppressWarnings("unchecked") E e = (E) es[h = head];
375 >        es[h] = null;
376 >        if (++h >= es.length) h = 0;
377 >        head = h;
378          size = s - 1;
379          return e;
380      }
# Line 398 | Line 382 | public class ArrayDeque<E> extends Abstr
382      public E pollLast() {
383          // checkInvariants();
384          final int s, tail;
385 <        if ((s = size) == 0)
385 >        if ((s = size) <= 0)
386              return null;
387 <        final Object[] elements = this.elements;
387 >        final Object[] es = elements;
388          @SuppressWarnings("unchecked")
389 <        E e = (E) elements[tail = add(head, s - 1, elements.length)];
390 <        elements[tail] = null;
389 >        E e = (E) es[tail = add(head, s - 1, es.length)];
390 >        es[tail] = null;
391          size = s - 1;
392          return e;
393      }
# Line 413 | Line 397 | public class ArrayDeque<E> extends Abstr
397       */
398      public E getFirst() {
399          // checkInvariants();
400 <        if (size == 0) throw new NoSuchElementException();
400 >        if (size <= 0) throw new NoSuchElementException();
401          return elementAt(head);
402      }
403  
404      /**
405       * @throws NoSuchElementException {@inheritDoc}
406       */
407 +    @SuppressWarnings("unchecked")
408      public E getLast() {
409          // checkInvariants();
410 <        if (size == 0) throw new NoSuchElementException();
411 <        return elementAt(tail());
410 >        final int s;
411 >        if ((s = size) <= 0) throw new NoSuchElementException();
412 >        final Object[] es = elements;
413 >        return (E) es[add(head, s - 1, es.length)];
414      }
415  
416      public E peekFirst() {
417          // checkInvariants();
418 <        return (size == 0) ? null : elementAt(head);
418 >        return (size <= 0) ? null : elementAt(head);
419      }
420  
421 +    @SuppressWarnings("unchecked")
422      public E peekLast() {
423          // checkInvariants();
424 <        return (size == 0) ? null : elementAt(tail());
424 >        final int s;
425 >        if ((s = size) <= 0) return null;
426 >        final Object[] es = elements;
427 >        return (E) es[add(head, s - 1, es.length)];
428      }
429  
430      /**
# Line 449 | Line 440 | public class ArrayDeque<E> extends Abstr
440       * @return {@code true} if the deque contained the specified element
441       */
442      public boolean removeFirstOccurrence(Object o) {
452        // checkInvariants();
443          if (o != null) {
444 <            final Object[] elements = this.elements;
445 <            final int capacity = elements.length;
446 <            for (int k = size, i = head; --k >= 0; i = inc(i, capacity)) {
447 <                if (o.equals(elements[i])) {
448 <                    delete(i);
449 <                    return true;
450 <                }
444 >            final Object[] es = elements;
445 >            int i, end, to, todo;
446 >            todo = (end = (i = head) + size)
447 >                - (to = (es.length - end >= 0) ? end : es.length);
448 >            for (;; to = todo, i = 0, todo = 0) {
449 >                for (; i < to; i++)
450 >                    if (o.equals(es[i])) {
451 >                        delete(i);
452 >                        return true;
453 >                    }
454 >                if (todo == 0) break;
455              }
456          }
457          return false;
# Line 477 | Line 471 | public class ArrayDeque<E> extends Abstr
471       */
472      public boolean removeLastOccurrence(Object o) {
473          if (o != null) {
474 <            final Object[] elements = this.elements;
475 <            final int capacity = elements.length;
476 <            for (int k = size, i = add(head, k - 1, capacity);
477 <                 --k >= 0; i = dec(i, capacity)) {
478 <                if (o.equals(elements[i])) {
479 <                    delete(i);
480 <                    return true;
481 <                }
474 >            final Object[] es = elements;
475 >            int i, to, end, todo;
476 >            todo = (to = ((end = (i = tail()) - size) >= -1) ? end : -1) - end;
477 >            for (;; to = (i = es.length - 1) - todo, todo = 0) {
478 >                for (; i > to; i--)
479 >                    if (o.equals(es[i])) {
480 >                        delete(i);
481 >                        return true;
482 >                    }
483 >                if (todo == 0) break;
484              }
485          }
486          return false;
# Line 616 | Line 612 | public class ArrayDeque<E> extends Abstr
612       */
613      boolean delete(int i) {
614          // checkInvariants();
615 <        final Object[] elements = this.elements;
616 <        final int capacity = elements.length;
615 >        final Object[] es = elements;
616 >        final int capacity = es.length;
617          final int h = head;
618          int front;              // number of elements before to-be-deleted elt
619          if ((front = i - h) < 0) front += capacity;
# Line 625 | Line 621 | public class ArrayDeque<E> extends Abstr
621          if (front < back) {
622              // move front elements forwards
623              if (h <= i) {
624 <                System.arraycopy(elements, h, elements, h + 1, front);
624 >                System.arraycopy(es, h, es, h + 1, front);
625              } else { // Wrap around
626 <                System.arraycopy(elements, 0, elements, 1, i);
627 <                elements[0] = elements[capacity - 1];
628 <                System.arraycopy(elements, h, elements, h + 1, front - (i + 1));
626 >                System.arraycopy(es, 0, es, 1, i);
627 >                es[0] = es[capacity - 1];
628 >                System.arraycopy(es, h, es, h + 1, front - (i + 1));
629              }
630 <            elements[h] = null;
631 <            head = inc(h, capacity);
630 >            es[h] = null;
631 >            if ((head = (h + 1)) >= capacity) head = 0;
632              size--;
633              // checkInvariants();
634              return false;
# Line 640 | Line 636 | public class ArrayDeque<E> extends Abstr
636              // move back elements backwards
637              int tail = tail();
638              if (i <= tail) {
639 <                System.arraycopy(elements, i + 1, elements, i, back);
639 >                System.arraycopy(es, i + 1, es, i, back);
640              } else { // Wrap around
641                  int firstLeg = capacity - (i + 1);
642 <                System.arraycopy(elements, i + 1, elements, i, firstLeg);
643 <                elements[capacity - 1] = elements[0];
644 <                System.arraycopy(elements, 1, elements, 0, back - firstLeg - 1);
642 >                System.arraycopy(es, i + 1, es, i, firstLeg);
643 >                es[capacity - 1] = es[0];
644 >                System.arraycopy(es, 1, es, 0, back - firstLeg - 1);
645              }
646 <            elements[tail] = null;
646 >            es[tail] = null;
647              size--;
648              // checkInvariants();
649              return true;
# Line 710 | Line 706 | public class ArrayDeque<E> extends Abstr
706          }
707  
708          public E next() {
709 <            if (remaining == 0)
709 >            if (remaining <= 0)
710                  throw new NoSuchElementException();
711 <            E e = checkedElementAt(elements, cursor);
711 >            final Object[] es = elements;
712 >            E e = nonNullElementAt(es, cursor);
713              lastRet = cursor;
714 <            cursor = inc(cursor, elements.length);
714 >            if (++cursor >= es.length) cursor = 0;
715              remaining--;
716              return e;
717          }
718  
719          void postDelete(boolean leftShifted) {
720              if (leftShifted)
721 <                cursor = dec(cursor, elements.length); // undo inc in next
721 >                if (--cursor < 0) cursor = elements.length - 1;
722          }
723  
724          public final void remove() {
# Line 733 | Line 730 | public class ArrayDeque<E> extends Abstr
730  
731          public void forEachRemaining(Consumer<? super E> action) {
732              Objects.requireNonNull(action);
733 <            final Object[] elements = ArrayDeque.this.elements;
734 <            final int capacity = elements.length;
735 <            int k = remaining;
736 <            remaining = 0;
737 <            for (int i = cursor; --k >= 0; i = inc(i, capacity))
738 <                action.accept(checkedElementAt(elements, i));
733 >            final int k;
734 >            if ((k = remaining) > 0) {
735 >                remaining = 0;
736 >                ArrayDeque.forEachRemaining(action, elements, cursor, k);
737 >                if ((lastRet = cursor + k - 1) >= elements.length)
738 >                    lastRet -= elements.length;
739 >            }
740          }
741      }
742  
# Line 746 | Line 744 | public class ArrayDeque<E> extends Abstr
744          DescendingIterator() { cursor = tail(); }
745  
746          public final E next() {
747 <            if (remaining == 0)
747 >            if (remaining <= 0)
748                  throw new NoSuchElementException();
749 <            E e = checkedElementAt(elements, cursor);
749 >            final Object[] es = elements;
750 >            E e = nonNullElementAt(es, cursor);
751              lastRet = cursor;
752 <            cursor = dec(cursor, elements.length);
752 >            if (--cursor < 0) cursor = es.length - 1;
753              remaining--;
754              return e;
755          }
756  
757          void postDelete(boolean leftShifted) {
758              if (!leftShifted)
759 <                cursor = inc(cursor, elements.length); // undo dec in next
759 >                if (++cursor >= elements.length) cursor = 0;
760          }
761  
762          public final void forEachRemaining(Consumer<? super E> action) {
763              Objects.requireNonNull(action);
764 <            final Object[] elements = ArrayDeque.this.elements;
765 <            final int capacity = elements.length;
766 <            int k = remaining;
767 <            remaining = 0;
768 <            for (int i = cursor; --k >= 0; i = dec(i, capacity))
769 <                action.accept(checkedElementAt(elements, i));
764 >            final int k;
765 >            if ((k = remaining) > 0) {
766 >                remaining = 0;
767 >                final Object[] es = elements;
768 >                int i, end, to, todo;
769 >                todo = (to = ((end = (i = cursor) - k) >= -1) ? end : -1) - end;
770 >                for (;; to = (i = es.length - 1) - todo, todo = 0) {
771 >                    for (; i > to; i--)
772 >                        action.accept(nonNullElementAt(es, i));
773 >                    if (todo == 0) break;
774 >                }
775 >                if ((lastRet = cursor - (k - 1)) < 0)
776 >                    lastRet += es.length;
777 >            }
778          }
779      }
780  
# Line 825 | Line 832 | public class ArrayDeque<E> extends Abstr
832  
833          public void forEachRemaining(Consumer<? super E> action) {
834              Objects.requireNonNull(action);
835 <            final Object[] elements = ArrayDeque.this.elements;
829 <            final int capacity = elements.length;
830 <            int k = remaining();
835 >            final int k = remaining(); // side effect!
836              remaining = 0;
837 <            for (int i = cursor; --k >= 0; i = inc(i, capacity))
833 <                action.accept(checkedElementAt(elements, i));
837 >            ArrayDeque.forEachRemaining(action, elements, cursor, k);
838          }
839  
840          public boolean tryAdvance(Consumer<? super E> action) {
841              Objects.requireNonNull(action);
842 <            if (remaining() == 0)
842 >            final int k;
843 >            if ((k = remaining()) <= 0)
844                  return false;
845 <            action.accept(checkedElementAt(elements, cursor));
846 <            cursor = inc(cursor, elements.length);
847 <            remaining--;
845 >            action.accept(nonNullElementAt(elements, cursor));
846 >            if (++cursor >= elements.length) cursor = 0;
847 >            remaining = k - 1;
848              return true;
849          }
850  
# Line 855 | Line 860 | public class ArrayDeque<E> extends Abstr
860          }
861      }
862  
863 <    @Override
863 >    @SuppressWarnings("unchecked")
864      public void forEach(Consumer<? super E> action) {
860        // checkInvariants();
865          Objects.requireNonNull(action);
866 <        final Object[] elements = this.elements;
867 <        final int capacity = elements.length;
868 <        for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
869 <            action.accept(elementAt(i));
866 >        final Object[] es = elements;
867 >        int i, end, to, todo;
868 >        todo = (end = (i = head) + size)
869 >            - (to = (es.length - end >= 0) ? end : es.length);
870 >        for (;; to = todo, i = 0, todo = 0) {
871 >            for (; i < to; i++)
872 >                action.accept((E) es[i]);
873 >            if (todo == 0) break;
874 >        }
875          // checkInvariants();
876      }
877  
878      /**
879 +     * Calls action on remaining elements, starting at index i and
880 +     * traversing in ascending order.  A variant of forEach that also
881 +     * checks for concurrent modification, for use in iterators.
882 +     */
883 +    static <E> void forEachRemaining(
884 +        Consumer<? super E> action, Object[] es, int i, int remaining) {
885 +        int end, to, todo;
886 +        todo = (end = i + remaining)
887 +            - (to = (es.length - end >= 0) ? end : es.length);
888 +        for (;; to = todo, i = 0, todo = 0) {
889 +            for (; i < to; i++)
890 +                action.accept(nonNullElementAt(es, i));
891 +            if (todo == 0) break;
892 +        }
893 +    }
894 +
895 +    /**
896       * Replaces each element of this deque with the result of applying the
897       * operator to that element, as specified by {@link List#replaceAll}.
898       *
899       * @param operator the operator to apply to each element
900       * @since TBD
901       */
902 +    @SuppressWarnings("unchecked")
903      /* public */ void replaceAll(UnaryOperator<E> operator) {
904          Objects.requireNonNull(operator);
905 <        final Object[] elements = this.elements;
906 <        final int capacity = elements.length;
907 <        for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
908 <            elements[i] = operator.apply(elementAt(i));
905 >        final Object[] es = elements;
906 >        int i, end, to, todo;
907 >        todo = (end = (i = head) + size)
908 >            - (to = (es.length - end >= 0) ? end : es.length);
909 >        for (;; to = todo, i = 0, todo = 0) {
910 >            for (; i < to; i++)
911 >                es[i] = operator.apply((E) es[i]);
912 >            if (todo == 0) break;
913 >        }
914          // checkInvariants();
915      }
916  
917      /**
918       * @throws NullPointerException {@inheritDoc}
919       */
888    @Override
920      public boolean removeIf(Predicate<? super E> filter) {
921          Objects.requireNonNull(filter);
922          return bulkRemove(filter);
# Line 894 | Line 925 | public class ArrayDeque<E> extends Abstr
925      /**
926       * @throws NullPointerException {@inheritDoc}
927       */
897    @Override
928      public boolean removeAll(Collection<?> c) {
929          Objects.requireNonNull(c);
930          return bulkRemove(e -> c.contains(e));
# Line 903 | Line 933 | public class ArrayDeque<E> extends Abstr
933      /**
934       * @throws NullPointerException {@inheritDoc}
935       */
906    @Override
936      public boolean retainAll(Collection<?> c) {
937          Objects.requireNonNull(c);
938          return bulkRemove(e -> !c.contains(e));
# Line 912 | Line 941 | public class ArrayDeque<E> extends Abstr
941      /** Implementation of bulk remove methods. */
942      private boolean bulkRemove(Predicate<? super E> filter) {
943          // checkInvariants();
944 <        final Object[] elements = this.elements;
945 <        final int capacity = elements.length;
944 >        final Object[] es = elements;
945 >        final int capacity = es.length;
946          int i = head, j = i, remaining = size, deleted = 0;
947          try {
948 <            for (; remaining > 0; remaining--, i = inc(i, capacity)) {
949 <                @SuppressWarnings("unchecked") E e = (E) elements[i];
948 >            for (; remaining > 0; remaining--) {
949 >                @SuppressWarnings("unchecked") E e = (E) es[i];
950                  if (filter.test(e))
951                      deleted++;
952                  else {
953                      if (j != i)
954 <                        elements[j] = e;
955 <                    j = inc(j, capacity);
954 >                        es[j] = e;
955 >                    if (++j >= capacity) j = 0;
956                  }
957 +                if (++i >= capacity) i = 0;
958              }
959              return deleted > 0;
960          } catch (Throwable ex) {
961              if (deleted > 0)
962 <                for (; remaining > 0;
963 <                     remaining--, i = inc(i, capacity), j = inc(j, capacity))
964 <                    elements[j] = elements[i];
962 >                for (; remaining > 0; remaining--) {
963 >                    es[j] = es[i];
964 >                    if (++i >= capacity) i = 0;
965 >                    if (++j >= capacity) j = 0;
966 >                }
967              throw ex;
968          } finally {
969              size -= deleted;
970 <            for (; --deleted >= 0; j = inc(j, capacity))
939 <                elements[j] = null;
970 >            clearSlice(es, j, deleted);
971              // checkInvariants();
972          }
973      }
# Line 951 | Line 982 | public class ArrayDeque<E> extends Abstr
982       */
983      public boolean contains(Object o) {
984          if (o != null) {
985 <            final Object[] elements = this.elements;
986 <            final int capacity = elements.length;
987 <            for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
988 <                if (o.equals(elements[i]))
989 <                    return true;
985 >            final Object[] es = elements;
986 >            int i, end, to, todo;
987 >            todo = (end = (i = head) + size)
988 >                - (to = (es.length - end >= 0) ? end : es.length);
989 >            for (;; to = todo, i = 0, todo = 0) {
990 >                for (; i < to; i++)
991 >                    if (o.equals(es[i]))
992 >                        return true;
993 >                if (todo == 0) break;
994 >            }
995          }
996          return false;
997      }
# Line 982 | Line 1018 | public class ArrayDeque<E> extends Abstr
1018       * The deque will be empty after this call returns.
1019       */
1020      public void clear() {
1021 <        final Object[] elements = this.elements;
986 <        final int capacity = elements.length;
987 <        final int h = this.head;
988 <        final int s = size;
989 <        if (capacity - h >= s)
990 <            Arrays.fill(elements, h, h + s, null);
991 <        else {
992 <            Arrays.fill(elements, h, capacity, null);
993 <            Arrays.fill(elements, 0, s - capacity + h, null);
994 <        }
1021 >        clearSlice(elements, head, size);
1022          size = head = 0;
1023          // checkInvariants();
1024      }
1025  
1026      /**
1027 +     * Nulls out count elements, starting at array index i.
1028 +     */
1029 +    private static void clearSlice(Object[] es, int i, int count) {
1030 +        int end, to, todo;
1031 +        todo = (end = i + count)
1032 +            - (to = (es.length - end >= 0) ? end : es.length);
1033 +        for (;; to = todo, i = 0, todo = 0) {
1034 +            Arrays.fill(es, i, to, null);
1035 +            if (todo == 0) break;
1036 +        }
1037 +    }
1038 +
1039 +    /**
1040       * Returns an array containing all of the elements in this deque
1041       * in proper sequence (from first to last element).
1042       *
# Line 1010 | Line 1050 | public class ArrayDeque<E> extends Abstr
1050       * @return an array containing all of the elements in this deque
1051       */
1052      public Object[] toArray() {
1053 <        final int head = this.head;
1054 <        final int firstLeg;
1055 <        Object[] a = Arrays.copyOfRange(elements, head, head + size);
1056 <        if ((firstLeg = elements.length - head) < size)
1057 <            System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1053 >        return toArray(Object[].class);
1054 >    }
1055 >
1056 >    private <T> T[] toArray(Class<T[]> klazz) {
1057 >        final Object[] es = elements;
1058 >        final int capacity = es.length;
1059 >        final int head = this.head, end = head + size;
1060 >        final T[] a;
1061 >        if (end >= 0) {
1062 >            a = Arrays.copyOfRange(es, head, end, klazz);
1063 >        } else {
1064 >            // integer overflow!
1065 >            a = Arrays.copyOfRange(es, 0, size, klazz);
1066 >            System.arraycopy(es, head, a, 0, capacity - head);
1067 >        }
1068 >        if (end - capacity > 0)
1069 >            System.arraycopy(es, 0, a, capacity - head, end - capacity);
1070          return a;
1071      }
1072  
# Line 1056 | Line 1108 | public class ArrayDeque<E> extends Abstr
1108       */
1109      @SuppressWarnings("unchecked")
1110      public <T> T[] toArray(T[] a) {
1111 <        final Object[] elements = this.elements;
1112 <        final int head = this.head;
1113 <        final int firstLeg;
1114 <        boolean wrap = (firstLeg = elements.length - head) < size;
1115 <        if (size > a.length) {
1116 <            a = (T[]) Arrays.copyOfRange(elements, head, head + size,
1117 <                                         a.getClass());
1118 <        } else {
1119 <            System.arraycopy(elements, head, a, 0, wrap ? firstLeg : size);
1120 <            if (size < a.length)
1121 <                a[size] = null;
1070 <        }
1071 <        if (wrap)
1072 <            System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1111 >        final int size;
1112 >        if ((size = this.size) > a.length)
1113 >            return toArray((Class<T[]>) a.getClass());
1114 >        final Object[] es = elements;
1115 >        final int head = this.head, end = head + size;
1116 >        final int front = (es.length - end >= 0) ? size : es.length - head;
1117 >        System.arraycopy(es, head, a, 0, front);
1118 >        if (front < size)
1119 >            System.arraycopy(es, 0, a, front, size - front);
1120 >        if (size < a.length)
1121 >            a[size] = null;
1122          return a;
1123      }
1124  
# Line 1110 | Line 1159 | public class ArrayDeque<E> extends Abstr
1159          s.writeInt(size);
1160  
1161          // Write out elements in order.
1162 <        final Object[] elements = this.elements;
1163 <        final int capacity = elements.length;
1164 <        for (int k = size, i = head; --k >= 0; i = inc(i, capacity))
1165 <            s.writeObject(elements[i]);
1162 >        final Object[] es = elements;
1163 >        int i, end, to, todo;
1164 >        todo = (end = (i = head) + size)
1165 >            - (to = (es.length - end >= 0) ? end : es.length);
1166 >        for (;; to = todo, i = 0, todo = 0) {
1167 >            for (; i < to; i++)
1168 >                s.writeObject(es[i]);
1169 >            if (todo == 0) break;
1170 >        }
1171      }
1172  
1173      /**
# Line 1136 | Line 1190 | public class ArrayDeque<E> extends Abstr
1190      }
1191  
1192      /** debugging */
1193 <    private void checkInvariants() {
1193 >    void checkInvariants() {
1194          try {
1195              int capacity = elements.length;
1196 <            assert size >= 0 && size <= capacity;
1197 <            assert head >= 0 && ((capacity == 0 && head == 0 && size == 0)
1198 <                                 || head < capacity);
1199 <            assert size == 0
1200 <                || (elements[head] != null && elements[tail()] != null);
1201 <            assert size == capacity
1202 <                || (elements[dec(head, capacity)] == null
1149 <                    && elements[inc(tail(), capacity)] == null);
1196 >            // assert size >= 0 && size <= capacity;
1197 >            // assert head >= 0;
1198 >            // assert capacity == 0 || head < capacity;
1199 >            // assert size == 0 || elements[head] != null;
1200 >            // assert size == 0 || elements[tail()] != null;
1201 >            // assert size == capacity || elements[dec(head, capacity)] == null;
1202 >            // assert size == capacity || elements[inc(tail(), capacity)] == null;
1203          } catch (Throwable t) {
1204              System.err.printf("head=%d size=%d capacity=%d%n",
1205                                head, size, elements.length);

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines