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.77 by jsr166, Tue Oct 18 00:33:05 2016 UTC vs.
Revision 1.85 by jsr166, Sun Oct 23 19:30:54 2016 UTC

# Line 134 | Line 134 | public class ArrayDeque<E> extends Abstr
134       * to ensure that it can hold at least the given number of elements.
135       *
136       * @param minCapacity the desired minimum capacity
137 <     * @since 9
137 >     * @since TBD
138       */
139 <    public void ensureCapacity(int minCapacity) {
139 >    /* public */ void ensureCapacity(int minCapacity) {
140          if (minCapacity > elements.length)
141              grow(minCapacity - elements.length);
142          // checkInvariants();
# Line 145 | Line 145 | public class ArrayDeque<E> extends Abstr
145      /**
146       * Minimizes the internal storage of this collection.
147       *
148 <     * @since 9
148 >     * @since TBD
149       */
150 <    public void trimToSize() {
150 >    /* public */ void trimToSize() {
151          if (size < elements.length) {
152              elements = toArray();
153              head = 0;
# 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  
198      /**
199 –     * Returns the array index of the last element.
200 –     * May return invalid index -1 if there are no elements.
201 –     */
202 –    final int tail() {
203 –        return add(head, size - 1, elements.length);
204 –    }
205 –
206 –    /**
207 –     * Adds i and j, mod modulus.
208 –     * Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
209 –     */
210 –    static final int add(int i, int j, int modulus) {
211 –        if ((i += j) - modulus >= 0) i -= modulus;
212 –        return i;
213 –    }
214 –
215 –    /**
199       * Increments i, mod modulus.
200       * Precondition and postcondition: 0 <= i < modulus.
201       */
# Line 231 | Line 214 | public class ArrayDeque<E> extends Abstr
214      }
215  
216      /**
217 +     * Adds i and j, mod modulus.
218 +     * Precondition and postcondition: 0 <= i < modulus, 0 <= j <= modulus.
219 +     */
220 +    static final int add(int i, int j, int modulus) {
221 +        if ((i += j) - modulus >= 0) i -= modulus;
222 +        return i;
223 +    }
224 +
225 +    /**
226 +     * Returns the array index of the last element.
227 +     * May return invalid index -1 if there are no elements.
228 +     */
229 +    final int tail() {
230 +        return add(head, size - 1, elements.length);
231 +    }
232 +
233 +    /**
234       * Returns element at array index i.
235       */
236      @SuppressWarnings("unchecked")
# 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 305 | Line 321 | public class ArrayDeque<E> extends Abstr
321      public boolean addAll(Collection<? extends E> c) {
322          // checkInvariants();
323          Object[] a, elements;
324 <        int len, capacity, s = size;
325 <        if ((len = (a = c.toArray()).length) == 0)
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 < len)
328 <            grow(len - (capacity - s));
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);
# Line 349 | Line 365 | public class ArrayDeque<E> extends Abstr
365       */
366      public E removeFirst() {
367          // checkInvariants();
368 <        E x = pollFirst();
369 <        if (x == null)
368 >        E e = pollFirst();
369 >        if (e == null)
370              throw new NoSuchElementException();
371 <        return x;
371 >        return e;
372      }
373  
374      /**
# Line 360 | Line 376 | public class ArrayDeque<E> extends Abstr
376       */
377      public E removeLast() {
378          // checkInvariants();
379 <        E x = pollLast();
380 <        if (x == null)
379 >        E e = pollLast();
380 >        if (e == null)
381              throw new NoSuchElementException();
382 <        return x;
382 >        return e;
383      }
384  
385      public E pollFirst() {
# Line 689 | Line 705 | public class ArrayDeque<E> extends Abstr
705  
706          DeqIterator() { cursor = head; }
707  
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 –
708          public final boolean hasNext() {
709              return remaining > 0;
710          }
711  
712 <        public final E next() {
712 >        public E next() {
713              if (remaining == 0)
714                  throw new NoSuchElementException();
715              E e = checkedElementAt(elements, cursor);
716              lastRet = cursor;
717 <            cursor = advance(cursor, elements.length);
717 >            cursor = inc(cursor, elements.length);
718              remaining--;
719              return e;
720          }
721  
722 +        void postDelete(boolean leftShifted) {
723 +            if (leftShifted)
724 +                cursor = dec(cursor, elements.length); // undo inc in next
725 +        }
726 +
727          public final void remove() {
728              if (lastRet < 0)
729                  throw new IllegalStateException();
730 <            doRemove();
730 >            postDelete(delete(lastRet));
731              lastRet = -1;
732          }
733  
734 <        public final void forEachRemaining(Consumer<? super E> action) {
734 >        public void forEachRemaining(Consumer<? super E> action) {
735              Objects.requireNonNull(action);
736              final Object[] elements = ArrayDeque.this.elements;
737              final int capacity = elements.length;
738              int k = remaining;
739              remaining = 0;
740 <            for (int i = cursor; --k >= 0; i = advance(i, capacity))
740 >            for (int i = cursor; --k >= 0; i = inc(i, capacity))
741                  action.accept(checkedElementAt(elements, i));
742          }
743      }
# Line 734 | Line 745 | public class ArrayDeque<E> extends Abstr
745      private class DescendingIterator extends DeqIterator {
746          DescendingIterator() { cursor = tail(); }
747  
748 <        @Override int advance(int i, int modulus) {
749 <            return dec(i, modulus);
748 >        public final E next() {
749 >            if (remaining == 0)
750 >                throw new NoSuchElementException();
751 >            E e = checkedElementAt(elements, cursor);
752 >            lastRet = cursor;
753 >            cursor = dec(cursor, elements.length);
754 >            remaining--;
755 >            return e;
756 >        }
757 >
758 >        void postDelete(boolean leftShifted) {
759 >            if (!leftShifted)
760 >                cursor = inc(cursor, elements.length); // undo dec in next
761          }
762  
763 <        @Override void doRemove() {
764 <            if (!delete(lastRet))
765 <                // if right-shifted, undo advance in next
766 <                cursor = inc(cursor, elements.length);
763 >        public final void forEachRemaining(Consumer<? super E> action) {
764 >            Objects.requireNonNull(action);
765 >            final Object[] elements = ArrayDeque.this.elements;
766 >            final int capacity = elements.length;
767 >            int k = remaining;
768 >            remaining = 0;
769 >            for (int i = cursor; --k >= 0; i = dec(i, capacity))
770 >                action.accept(checkedElementAt(elements, i));
771          }
772      }
773  
# Line 845 | Line 871 | public class ArrayDeque<E> extends Abstr
871       * operator to that element, as specified by {@link List#replaceAll}.
872       *
873       * @param operator the operator to apply to each element
874 <     * @since 9
874 >     * @since TBD
875       */
876 <    public void replaceAll(UnaryOperator<E> operator) {
876 >    /* public */ void replaceAll(UnaryOperator<E> operator) {
877          Objects.requireNonNull(operator);
878          final Object[] elements = this.elements;
879          final int capacity = elements.length;
# Line 902 | Line 928 | public class ArrayDeque<E> extends Abstr
928              }
929              return deleted > 0;
930          } catch (Throwable ex) {
931 <            for (; remaining > 0;
932 <                 remaining--, i = inc(i, capacity), j = inc(j, capacity))
933 <                elements[j] = elements[i];
931 >            if (deleted > 0)
932 >                for (; remaining > 0;
933 >                     remaining--, i = inc(i, capacity), j = inc(j, capacity))
934 >                    elements[j] = elements[i];
935              throw ex;
936          } finally {
937              size -= deleted;

Diff Legend

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