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.80 by jsr166, Thu Oct 20 01:43:31 2016 UTC vs.
Revision 1.88 by jsr166, Mon Oct 24 16:01:25 2016 UTC

# Line 187 | Line 187 | public class ArrayDeque<E> extends Abstr
187          Object[] elements = c.toArray();
188          // defend against c.toArray (incorrectly) not returning Object[]
189          // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
190 +        size = elements.length;
191          if (elements.getClass() != Object[].class)
192              elements = Arrays.copyOf(elements, size, Object[].class);
193          for (Object obj : elements)
194              Objects.requireNonNull(obj);
194 –        size = elements.length;
195          this.elements = elements;
196      }
197  
# Line 234 | Line 234 | public class ArrayDeque<E> extends Abstr
234       * Returns element at array index i.
235       */
236      @SuppressWarnings("unchecked")
237 <    final E elementAt(int i) {
237 >    private E elementAt(int i) {
238          return (E) elements[i];
239      }
240  
# 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;
267 <        int capacity, s = size;
268 <        while (s == (capacity = (elements = this.elements).length))
269 <            grow(1);
270 <        elements[head = dec(head, capacity)] = 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;
272          size = s + 1;
273 +        // checkInvariants();
274 +    }
275 +
276 +    private void addFirstSlowPath(E e) {
277 +        grow(1);
278 +        final Object[] elements = this.elements;
279 +        elements[head = dec(head, elements.length)] = e;
280      }
281  
282      /**
# Line 282 | Line 290 | public class ArrayDeque<E> extends Abstr
290      public void addLast(E e) {
291          // checkInvariants();
292          Objects.requireNonNull(e);
293 <        Object[] elements;
294 <        int capacity, s = size;
295 <        while (s == (capacity = (elements = this.elements).length))
296 <            grow(1);
297 <        elements[add(head, s, capacity)] = e;
293 >        final Object[] elements;
294 >        final int capacity, s;
295 >        if ((s = size) == (capacity = (elements = this.elements).length))
296 >            addLastSlowPath(e);
297 >        else
298 >            elements[add(head, s, capacity)] = e;
299          size = s + 1;
300 +        // checkInvariants();
301 +    }
302 +
303 +    private void addLastSlowPath(E e) {
304 +        grow(1);
305 +        final Object[] elements = this.elements;
306 +        elements[add(head, size, elements.length)] = e;
307      }
308  
309      /**
# Line 301 | Line 317 | public class ArrayDeque<E> extends Abstr
317       * @throws NullPointerException if the specified collection or any
318       *         of its elements are null
319       */
304 –    @Override
320      public boolean addAll(Collection<? extends E> c) {
321 +        final int s = size, needed = c.size() - (elements.length - s);
322 +        if (needed > 0)
323 +            grow(needed);
324 +        c.forEach((e) -> addLast(e));
325          // checkInvariants();
326 <        Object[] a, elements;
308 <        int newcomers, capacity, s = size;
309 <        if ((newcomers = (a = c.toArray()).length) == 0)
310 <            return false;
311 <        while ((capacity = (elements = this.elements).length) - s < newcomers)
312 <            grow(newcomers - (capacity - s));
313 <        int i = add(head, s, capacity);
314 <        for (Object x : a) {
315 <            Objects.requireNonNull(x);
316 <            elements[i] = x;
317 <            i = inc(i, capacity);
318 <            size++;
319 <        }
320 <        return true;
326 >        return size > s;
327      }
328  
329      /**
# Line 349 | Line 355 | public class ArrayDeque<E> extends Abstr
355       */
356      public E removeFirst() {
357          // checkInvariants();
358 <        E x = pollFirst();
359 <        if (x == null)
358 >        E e = pollFirst();
359 >        if (e == null)
360              throw new NoSuchElementException();
361 <        return x;
361 >        return e;
362      }
363  
364      /**
# Line 360 | Line 366 | public class ArrayDeque<E> extends Abstr
366       */
367      public E removeLast() {
368          // checkInvariants();
369 <        E x = pollLast();
370 <        if (x == null)
369 >        E e = pollLast();
370 >        if (e == null)
371              throw new NoSuchElementException();
372 <        return x;
372 >        return e;
373      }
374  
375      public E pollFirst() {
# Line 689 | Line 695 | public class ArrayDeque<E> extends Abstr
695  
696          DeqIterator() { cursor = head; }
697  
692 –        int advance(int i, int modulus) {
693 –            return inc(i, modulus);
694 –        }
695 –
696 –        void doRemove() {
697 –            if (delete(lastRet))
698 –                // if left-shifted, undo advance in next()
699 –                cursor = dec(cursor, elements.length);
700 –        }
701 –
698          public final boolean hasNext() {
699              return remaining > 0;
700          }
701  
702 <        public final E next() {
702 >        public E next() {
703              if (remaining == 0)
704                  throw new NoSuchElementException();
705              E e = checkedElementAt(elements, cursor);
706              lastRet = cursor;
707 <            cursor = advance(cursor, elements.length);
707 >            cursor = inc(cursor, elements.length);
708              remaining--;
709              return e;
710          }
711  
712 +        void postDelete(boolean leftShifted) {
713 +            if (leftShifted)
714 +                cursor = dec(cursor, elements.length); // undo inc in next
715 +        }
716 +
717          public final void remove() {
718              if (lastRet < 0)
719                  throw new IllegalStateException();
720 <            doRemove();
720 >            postDelete(delete(lastRet));
721              lastRet = -1;
722          }
723  
724 <        public final void forEachRemaining(Consumer<? super E> action) {
724 >        public void forEachRemaining(Consumer<? super E> action) {
725              Objects.requireNonNull(action);
726              final Object[] elements = ArrayDeque.this.elements;
727              final int capacity = elements.length;
728              int k = remaining;
729              remaining = 0;
730 <            for (int i = cursor; --k >= 0; i = advance(i, capacity))
730 >            for (int i = cursor; --k >= 0; i = inc(i, capacity))
731                  action.accept(checkedElementAt(elements, i));
732          }
733      }
# Line 734 | Line 735 | public class ArrayDeque<E> extends Abstr
735      private class DescendingIterator extends DeqIterator {
736          DescendingIterator() { cursor = tail(); }
737  
738 <        @Override int advance(int i, int modulus) {
739 <            return dec(i, modulus);
738 >        public final E next() {
739 >            if (remaining == 0)
740 >                throw new NoSuchElementException();
741 >            E e = checkedElementAt(elements, cursor);
742 >            lastRet = cursor;
743 >            cursor = dec(cursor, elements.length);
744 >            remaining--;
745 >            return e;
746          }
747  
748 <        @Override void doRemove() {
749 <            if (!delete(lastRet))
750 <                // if right-shifted, undo advance in next
751 <                cursor = inc(cursor, elements.length);
748 >        void postDelete(boolean leftShifted) {
749 >            if (!leftShifted)
750 >                cursor = inc(cursor, elements.length); // undo dec in next
751 >        }
752 >
753 >        public final void forEachRemaining(Consumer<? super E> action) {
754 >            Objects.requireNonNull(action);
755 >            final Object[] elements = ArrayDeque.this.elements;
756 >            final int capacity = elements.length;
757 >            int k = remaining;
758 >            remaining = 0;
759 >            for (int i = cursor; --k >= 0; i = dec(i, capacity))
760 >                action.accept(checkedElementAt(elements, i));
761          }
762      }
763  
# Line 829 | Line 845 | public class ArrayDeque<E> extends Abstr
845          }
846      }
847  
832 –    @Override
848      public void forEach(Consumer<? super E> action) {
849          // checkInvariants();
850          Objects.requireNonNull(action);
# Line 859 | Line 874 | public class ArrayDeque<E> extends Abstr
874      /**
875       * @throws NullPointerException {@inheritDoc}
876       */
862 –    @Override
877      public boolean removeIf(Predicate<? super E> filter) {
878          Objects.requireNonNull(filter);
879          return bulkRemove(filter);
# Line 868 | Line 882 | public class ArrayDeque<E> extends Abstr
882      /**
883       * @throws NullPointerException {@inheritDoc}
884       */
871 –    @Override
885      public boolean removeAll(Collection<?> c) {
886          Objects.requireNonNull(c);
887          return bulkRemove(e -> c.contains(e));
# Line 877 | Line 890 | public class ArrayDeque<E> extends Abstr
890      /**
891       * @throws NullPointerException {@inheritDoc}
892       */
880 –    @Override
893      public boolean retainAll(Collection<?> c) {
894          Objects.requireNonNull(c);
895          return bulkRemove(e -> !c.contains(e));
# Line 957 | Line 969 | public class ArrayDeque<E> extends Abstr
969       */
970      public void clear() {
971          final Object[] elements = this.elements;
972 <        final int capacity = elements.length;
973 <        final int h = this.head;
974 <        final int s = size;
963 <        if (capacity - h >= s)
964 <            Arrays.fill(elements, h, h + s, null);
972 >        final int capacity = elements.length, tail = head + size;
973 >        if (capacity - tail >= 0)
974 >            Arrays.fill(elements, head, tail, null);
975          else {
976 <            Arrays.fill(elements, h, capacity, null);
977 <            Arrays.fill(elements, 0, s - capacity + h, null);
976 >            Arrays.fill(elements, head, capacity, null);
977 >            Arrays.fill(elements, 0, tail - capacity, null);
978          }
979          size = head = 0;
980          // checkInvariants();
# Line 984 | Line 994 | public class ArrayDeque<E> extends Abstr
994       * @return an array containing all of the elements in this deque
995       */
996      public Object[] toArray() {
997 <        final int head = this.head;
998 <        final int firstLeg;
999 <        Object[] a = Arrays.copyOfRange(elements, head, head + size);
1000 <        if ((firstLeg = elements.length - head) < size)
1001 <            System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
997 >        return toArray(Object[].class);
998 >    }
999 >
1000 >    private <T> T[] toArray(Class<T[]> klazz) {
1001 >        final Object[] elements = this.elements;
1002 >        final int capacity = elements.length;
1003 >        final int head = this.head, tail = head + size;
1004 >        final T[] a;
1005 >        if (tail >= 0) {
1006 >            a = Arrays.copyOfRange(elements, head, tail, klazz);
1007 >        } else {
1008 >            // integer overflow!
1009 >            a = Arrays.copyOfRange(elements, 0, size, klazz);
1010 >            System.arraycopy(elements, head, a, 0, capacity - head);
1011 >        }
1012 >        if (tail - capacity > 0)
1013 >            System.arraycopy(elements, 0, a, capacity - head, tail - capacity);
1014          return a;
1015      }
1016  
# Line 1030 | Line 1052 | public class ArrayDeque<E> extends Abstr
1052       */
1053      @SuppressWarnings("unchecked")
1054      public <T> T[] toArray(T[] a) {
1055 +        final int size = this.size;
1056 +        if (size > a.length)
1057 +            return toArray((Class<T[]>) a.getClass());
1058          final Object[] elements = this.elements;
1059 <        final int head = this.head;
1060 <        final int firstLeg;
1061 <        boolean wrap = (firstLeg = elements.length - head) < size;
1062 <        if (size > a.length) {
1063 <            a = (T[]) Arrays.copyOfRange(elements, head, head + size,
1064 <                                         a.getClass());
1065 <        } else {
1041 <            System.arraycopy(elements, head, a, 0, wrap ? firstLeg : size);
1042 <            if (size < a.length)
1043 <                a[size] = null;
1059 >        final int capacity = elements.length;
1060 >        final int head = this.head, tail = head + size;
1061 >        if (capacity - tail >= 0)
1062 >            System.arraycopy(elements, head, a, 0, size);
1063 >        else {
1064 >            System.arraycopy(elements, head, a, 0, capacity - head);
1065 >            System.arraycopy(elements, 0, a, capacity - head, tail - capacity);
1066          }
1067 <        if (wrap)
1068 <            System.arraycopy(elements, 0, a, firstLeg, size - firstLeg);
1067 >        if (size < a.length)
1068 >            a[size] = null;
1069          return a;
1070      }
1071  

Diff Legend

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