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.93 by jsr166, Thu Oct 27 02:12:21 2016 UTC vs.
Revision 1.99 by jsr166, Sun Oct 30 16:32:40 2016 UTC

# Line 183 | 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 <        size = elements.length;
190 <        if (elements.getClass() != Object[].class)
191 <            elements = Arrays.copyOf(elements, size, Object[].class);
192 <        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 <        this.elements = elements;
193 >        this.elements = es;
194 >        this.size = es.length;
195      }
196  
197      /**
# Line 243 | Line 243 | public class ArrayDeque<E> extends Abstr
243       * but does catch ones that corrupt traversal.  It's a little
244       * surprising that javac allows this abuse of generics.
245       */
246 <    static final <E> E nonNullElementAt(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 <        Object[] elements;
266 >        Object[] es;
267          int capacity, h;
268          final int s;
269 <        if ((s = size) == (capacity = (elements = this.elements).length)) {
269 >        if ((s = size) == (capacity = (es = elements).length)) {
270              grow(1);
271 <            capacity = (elements = this.elements).length;
271 >            capacity = (es = elements).length;
272          }
273          if ((h = head - 1) < 0) h = capacity - 1;
274 <        elements[head = h] = e;
274 >        es[head = h] = e;
275          size = s + 1;
276          // checkInvariants();
277      }
# Line 287 | Line 287 | public class ArrayDeque<E> extends Abstr
287      public void addLast(E e) {
288          // checkInvariants();
289          Objects.requireNonNull(e);
290 <        Object[] elements;
290 >        Object[] es;
291          int capacity;
292          final int s;
293 <        if ((s = size) == (capacity = (elements = this.elements).length)) {
293 >        if ((s = size) == (capacity = (es = elements).length)) {
294              grow(1);
295 <            capacity = (elements = this.elements).length;
295 >            capacity = (es = elements).length;
296          }
297 <        elements[add(head, s, capacity)] = e;
297 >        es[add(head, s, capacity)] = e;
298          size = s + 1;
299          // checkInvariants();
300      }
# Line 370 | Line 370 | public class ArrayDeque<E> extends Abstr
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 <        if (++h >= elements.length) h = 0;
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;
# Line 384 | Line 384 | public class ArrayDeque<E> extends Abstr
384          final int s, tail;
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 409 | Line 409 | public class ArrayDeque<E> extends Abstr
409          // checkInvariants();
410          final int s;
411          if ((s = size) <= 0) throw new NoSuchElementException();
412 <        final Object[] elements = this.elements;
413 <        return (E) elements[add(head, s - 1, elements.length)];
412 >        final Object[] es = elements;
413 >        return (E) es[add(head, s - 1, es.length)];
414      }
415  
416      public E peekFirst() {
# Line 423 | Line 423 | public class ArrayDeque<E> extends Abstr
423          // checkInvariants();
424          final int s;
425          if ((s = size) <= 0) return null;
426 <        final Object[] elements = this.elements;
427 <        return (E) elements[add(head, s - 1, elements.length)];
426 >        final Object[] es = elements;
427 >        return (E) es[add(head, s - 1, es.length)];
428      }
429  
430      /**
# Line 441 | Line 441 | public class ArrayDeque<E> extends Abstr
441       */
442      public boolean removeFirstOccurrence(Object o) {
443          if (o != null) {
444 <            final Object[] elements = this.elements;
445 <            final int capacity = elements.length;
444 >            final Object[] es = elements;
445              int i, end, to, todo;
446              todo = (end = (i = head) + size)
447 <                - (to = (capacity - end >= 0) ? end : capacity);
448 <            for (;; i = 0, to = todo, todo = 0) {
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(elements[i])) {
450 >                    if (o.equals(es[i])) {
451                          delete(i);
452                          return true;
453                      }
# Line 472 | 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;
476 <            final int capacity = elements.length;
474 >            final Object[] es = elements;
475              int i, to, end, todo;
476              todo = (to = ((end = (i = tail()) - size) >= -1) ? end : -1) - end;
477 <            for (;; i = capacity - 1, to = i - todo, todo = 0) {
477 >            for (;; to = (i = es.length - 1) - todo, todo = 0) {
478                  for (; i > to; i--)
479 <                    if (o.equals(elements[i])) {
479 >                    if (o.equals(es[i])) {
480                          delete(i);
481                          return true;
482                      }
# Line 614 | 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 623 | 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;
630 >            es[h] = null;
631              if ((head = (h + 1)) >= capacity) head = 0;
632              size--;
633              // checkInvariants();
# Line 638 | 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 708 | public class ArrayDeque<E> extends Abstr
708          public E next() {
709              if (remaining <= 0)
710                  throw new NoSuchElementException();
711 <            final Object[] elements = ArrayDeque.this.elements;
712 <            E e = nonNullElementAt(elements, cursor);
711 >            final Object[] es = elements;
712 >            E e = nonNullElementAt(es, cursor);
713              lastRet = cursor;
714 <            if (++cursor >= elements.length) cursor = 0;
714 >            if (++cursor >= es.length) cursor = 0;
715              remaining--;
716              return e;
717          }
# Line 731 | Line 729 | public class ArrayDeque<E> extends Abstr
729          }
730  
731          public void forEachRemaining(Consumer<? super E> action) {
732 +            Objects.requireNonNull(action);
733              final int k;
734              if ((k = remaining) > 0) {
735                  remaining = 0;
# Line 747 | Line 746 | public class ArrayDeque<E> extends Abstr
746          public final E next() {
747              if (remaining <= 0)
748                  throw new NoSuchElementException();
749 <            final Object[] elements = ArrayDeque.this.elements;
750 <            E e = nonNullElementAt(elements, cursor);
749 >            final Object[] es = elements;
750 >            E e = nonNullElementAt(es, cursor);
751              lastRet = cursor;
752 <            if (--cursor < 0) cursor = elements.length - 1;
752 >            if (--cursor < 0) cursor = es.length - 1;
753              remaining--;
754              return e;
755          }
# Line 761 | Line 760 | public class ArrayDeque<E> extends Abstr
760          }
761  
762          public final void forEachRemaining(Consumer<? super E> action) {
763 +            Objects.requireNonNull(action);
764              final int k;
765              if ((k = remaining) > 0) {
766                  remaining = 0;
767 <                forEachRemainingDescending(action, elements, cursor, k);
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 += elements.length;
776 >                    lastRet += es.length;
777              }
778          }
779      }
# Line 824 | Line 831 | public class ArrayDeque<E> extends Abstr
831          }
832  
833          public void forEachRemaining(Consumer<? super E> action) {
834 +            Objects.requireNonNull(action);
835              final int k = remaining(); // side effect!
836              remaining = 0;
837              ArrayDeque.forEachRemaining(action, elements, cursor, k);
# Line 855 | Line 863 | public class ArrayDeque<E> extends Abstr
863      @SuppressWarnings("unchecked")
864      public void forEach(Consumer<? super E> action) {
865          Objects.requireNonNull(action);
866 <        final Object[] elements = this.elements;
859 <        final int capacity = elements.length;
866 >        final Object[] es = elements;
867          int i, end, to, todo;
868          todo = (end = (i = head) + size)
869 <            - (to = (capacity - end >= 0) ? end : capacity);
870 <        for (;; i = 0, to = todo, todo = 0) {
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) elements[i]);
872 >                action.accept((E) es[i]);
873              if (todo == 0) break;
874          }
875          // checkInvariants();
# Line 874 | Line 881 | public class ArrayDeque<E> extends Abstr
881       * checks for concurrent modification, for use in iterators.
882       */
883      static <E> void forEachRemaining(
884 <        Consumer<? super E> action, Object[] elements, int i, int remaining) {
878 <        Objects.requireNonNull(action);
879 <        final int capacity = elements.length;
884 >        Consumer<? super E> action, Object[] es, int i, int remaining) {
885          int end, to, todo;
886          todo = (end = i + remaining)
887 <            - (to = (capacity - end >= 0) ? end : capacity);
888 <        for (;; i = 0, to = todo, todo = 0) {
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(elements, i));
886 <            if (todo == 0) break;
887 <        }
888 <    }
889 <
890 <    static <E> void forEachRemainingDescending(
891 <        Consumer<? super E> action, Object[] elements, int i, int remaining) {
892 <        Objects.requireNonNull(action);
893 <        final int capacity = elements.length;
894 <        int end, to, todo;
895 <        todo = (to = ((end = i - remaining) >= -1) ? end : -1) - end;
896 <        for (;; i = capacity - 1, to = i - todo, todo = 0) {
897 <            for (; i > to; i--)
898 <                action.accept(nonNullElementAt(elements, i));
890 >                action.accept(nonNullElementAt(es, i));
891              if (todo == 0) break;
892          }
893      }
# Line 907 | Line 899 | public class ArrayDeque<E> extends Abstr
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;
913 <        final int capacity = elements.length;
905 >        final Object[] es = elements;
906          int i, end, to, todo;
907          todo = (end = (i = head) + size)
908 <            - (to = (capacity - end >= 0) ? end : capacity);
909 <        for (;; i = 0, to = todo, todo = 0) {
908 >            - (to = (es.length - end >= 0) ? end : es.length);
909 >        for (;; to = todo, i = 0, todo = 0) {
910              for (; i < to; i++)
911 <                elements[i] = operator.apply(elementAt(i));
911 >                es[i] = operator.apply((E) es[i]);
912              if (todo == 0) break;
913          }
914          // checkInvariants();
# Line 949 | 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--) {
949 <                @SuppressWarnings("unchecked") E e = (E) elements[i];
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;
954 >                        es[j] = e;
955                      if (++j >= capacity) j = 0;
956                  }
957                  if (++i >= capacity) i = 0;
# Line 968 | Line 960 | public class ArrayDeque<E> extends Abstr
960          } catch (Throwable ex) {
961              if (deleted > 0)
962                  for (; remaining > 0; remaining--) {
963 <                    elements[j] = elements[i];
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 <            clearSlice(elements, j, deleted);
970 >            clearSlice(es, j, deleted);
971              // checkInvariants();
972          }
973      }
# Line 990 | 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;
994 <            final int capacity = elements.length;
985 >            final Object[] es = elements;
986              int i, end, to, todo;
987              todo = (end = (i = head) + size)
988 <                - (to = (capacity - end >= 0) ? end : capacity);
989 <            for (;; i = 0, to = todo, todo = 0) {
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(elements[i]))
991 >                    if (o.equals(es[i]))
992                          return true;
993                  if (todo == 0) break;
994              }
# Line 1033 | Line 1024 | public class ArrayDeque<E> extends Abstr
1024      }
1025  
1026      /**
1027 <     * Nulls out count elements, starting at array index from.
1027 >     * Nulls out count elements, starting at array index i.
1028       */
1029 <    private static void clearSlice(Object[] elements, int from, int count) {
1030 <        final int capacity = elements.length, end = from + count;
1031 <        final int leg = (capacity - end >= 0) ? end : capacity;
1032 <        Arrays.fill(elements, from, leg, null);
1033 <        if (leg != end)
1034 <            Arrays.fill(elements, 0, end - capacity, null);
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      /**
# Line 1061 | Line 1054 | public class ArrayDeque<E> extends Abstr
1054      }
1055  
1056      private <T> T[] toArray(Class<T[]> klazz) {
1057 <        final Object[] elements = this.elements;
1058 <        final int capacity = elements.length;
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(elements, head, end, klazz);
1062 >            a = Arrays.copyOfRange(es, head, end, klazz);
1063          } else {
1064              // integer overflow!
1065 <            a = Arrays.copyOfRange(elements, 0, size, klazz);
1066 <            System.arraycopy(elements, head, a, 0, capacity - head);
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(elements, 0, a, capacity - head, end - capacity);
1069 >            System.arraycopy(es, 0, a, capacity - head, end - capacity);
1070          return a;
1071      }
1072  
# Line 1115 | Line 1108 | public class ArrayDeque<E> extends Abstr
1108       */
1109      @SuppressWarnings("unchecked")
1110      public <T> T[] toArray(T[] a) {
1111 <        final int size = this.size;
1112 <        if (size > a.length)
1111 >        final int size;
1112 >        if ((size = this.size) > a.length)
1113              return toArray((Class<T[]>) a.getClass());
1114 <        final Object[] elements = this.elements;
1122 <        final int capacity = elements.length;
1114 >        final Object[] es = elements;
1115          final int head = this.head, end = head + size;
1116 <        final int front = (capacity - end >= 0) ? size : capacity - head;
1117 <        System.arraycopy(elements, head, a, 0, front);
1118 <        if (front != size)
1119 <            System.arraycopy(elements, 0, a, capacity - head, end - capacity);
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;
# Line 1167 | 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;
1171 <        final int capacity = elements.length;
1162 >        final Object[] es = elements;
1163          int i, end, to, todo;
1164          todo = (end = (i = head) + size)
1165 <            - (to = (capacity - end >= 0) ? end : capacity);
1166 <        for (;; i = 0, to = todo, todo = 0) {
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(elements[i]);
1168 >                s.writeObject(es[i]);
1169              if (todo == 0) break;
1170          }
1171      }

Diff Legend

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