1.1 --- a/emul/compact/src/main/java/java/util/ArrayDeque.java Fri Mar 22 16:59:47 2013 +0100
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,830 +0,0 @@
1.4 -/*
1.5 - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.6 - *
1.7 - * This code is free software; you can redistribute it and/or modify it
1.8 - * under the terms of the GNU General Public License version 2 only, as
1.9 - * published by the Free Software Foundation. Oracle designates this
1.10 - * particular file as subject to the "Classpath" exception as provided
1.11 - * by Oracle in the LICENSE file that accompanied this code.
1.12 - *
1.13 - * This code is distributed in the hope that it will be useful, but WITHOUT
1.14 - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.15 - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.16 - * version 2 for more details (a copy is included in the LICENSE file that
1.17 - * accompanied this code).
1.18 - *
1.19 - * You should have received a copy of the GNU General Public License version
1.20 - * 2 along with this work; if not, write to the Free Software Foundation,
1.21 - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.22 - *
1.23 - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.24 - * or visit www.oracle.com if you need additional information or have any
1.25 - * questions.
1.26 - */
1.27 -
1.28 -/*
1.29 - * This file is available under and governed by the GNU General Public
1.30 - * License version 2 only, as published by the Free Software Foundation.
1.31 - * However, the following notice accompanied the original version of this
1.32 - * file:
1.33 - *
1.34 - * Written by Josh Bloch of Google Inc. and released to the public domain,
1.35 - * as explained at http://creativecommons.org/publicdomain/zero/1.0/.
1.36 - */
1.37 -
1.38 -package java.util;
1.39 -import java.io.*;
1.40 -
1.41 -/**
1.42 - * Resizable-array implementation of the {@link Deque} interface. Array
1.43 - * deques have no capacity restrictions; they grow as necessary to support
1.44 - * usage. They are not thread-safe; in the absence of external
1.45 - * synchronization, they do not support concurrent access by multiple threads.
1.46 - * Null elements are prohibited. This class is likely to be faster than
1.47 - * {@link Stack} when used as a stack, and faster than {@link LinkedList}
1.48 - * when used as a queue.
1.49 - *
1.50 - * <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time.
1.51 - * Exceptions include {@link #remove(Object) remove}, {@link
1.52 - * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
1.53 - * removeLastOccurrence}, {@link #contains contains}, {@link #iterator
1.54 - * iterator.remove()}, and the bulk operations, all of which run in linear
1.55 - * time.
1.56 - *
1.57 - * <p>The iterators returned by this class's <tt>iterator</tt> method are
1.58 - * <i>fail-fast</i>: If the deque is modified at any time after the iterator
1.59 - * is created, in any way except through the iterator's own <tt>remove</tt>
1.60 - * method, the iterator will generally throw a {@link
1.61 - * ConcurrentModificationException}. Thus, in the face of concurrent
1.62 - * modification, the iterator fails quickly and cleanly, rather than risking
1.63 - * arbitrary, non-deterministic behavior at an undetermined time in the
1.64 - * future.
1.65 - *
1.66 - * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
1.67 - * as it is, generally speaking, impossible to make any hard guarantees in the
1.68 - * presence of unsynchronized concurrent modification. Fail-fast iterators
1.69 - * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
1.70 - * Therefore, it would be wrong to write a program that depended on this
1.71 - * exception for its correctness: <i>the fail-fast behavior of iterators
1.72 - * should be used only to detect bugs.</i>
1.73 - *
1.74 - * <p>This class and its iterator implement all of the
1.75 - * <em>optional</em> methods of the {@link Collection} and {@link
1.76 - * Iterator} interfaces.
1.77 - *
1.78 - * <p>This class is a member of the
1.79 - * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.80 - * Java Collections Framework</a>.
1.81 - *
1.82 - * @author Josh Bloch and Doug Lea
1.83 - * @since 1.6
1.84 - * @param <E> the type of elements held in this collection
1.85 - */
1.86 -public class ArrayDeque<E> extends AbstractCollection<E>
1.87 - implements Deque<E>, Cloneable, Serializable
1.88 -{
1.89 - /**
1.90 - * The array in which the elements of the deque are stored.
1.91 - * The capacity of the deque is the length of this array, which is
1.92 - * always a power of two. The array is never allowed to become
1.93 - * full, except transiently within an addX method where it is
1.94 - * resized (see doubleCapacity) immediately upon becoming full,
1.95 - * thus avoiding head and tail wrapping around to equal each
1.96 - * other. We also guarantee that all array cells not holding
1.97 - * deque elements are always null.
1.98 - */
1.99 - private transient E[] elements;
1.100 -
1.101 - /**
1.102 - * The index of the element at the head of the deque (which is the
1.103 - * element that would be removed by remove() or pop()); or an
1.104 - * arbitrary number equal to tail if the deque is empty.
1.105 - */
1.106 - private transient int head;
1.107 -
1.108 - /**
1.109 - * The index at which the next element would be added to the tail
1.110 - * of the deque (via addLast(E), add(E), or push(E)).
1.111 - */
1.112 - private transient int tail;
1.113 -
1.114 - /**
1.115 - * The minimum capacity that we'll use for a newly created deque.
1.116 - * Must be a power of 2.
1.117 - */
1.118 - private static final int MIN_INITIAL_CAPACITY = 8;
1.119 -
1.120 - // ****** Array allocation and resizing utilities ******
1.121 -
1.122 - /**
1.123 - * Allocate empty array to hold the given number of elements.
1.124 - *
1.125 - * @param numElements the number of elements to hold
1.126 - */
1.127 - private void allocateElements(int numElements) {
1.128 - int initialCapacity = MIN_INITIAL_CAPACITY;
1.129 - // Find the best power of two to hold elements.
1.130 - // Tests "<=" because arrays aren't kept full.
1.131 - if (numElements >= initialCapacity) {
1.132 - initialCapacity = numElements;
1.133 - initialCapacity |= (initialCapacity >>> 1);
1.134 - initialCapacity |= (initialCapacity >>> 2);
1.135 - initialCapacity |= (initialCapacity >>> 4);
1.136 - initialCapacity |= (initialCapacity >>> 8);
1.137 - initialCapacity |= (initialCapacity >>> 16);
1.138 - initialCapacity++;
1.139 -
1.140 - if (initialCapacity < 0) // Too many elements, must back off
1.141 - initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
1.142 - }
1.143 - elements = (E[]) new Object[initialCapacity];
1.144 - }
1.145 -
1.146 - /**
1.147 - * Double the capacity of this deque. Call only when full, i.e.,
1.148 - * when head and tail have wrapped around to become equal.
1.149 - */
1.150 - private void doubleCapacity() {
1.151 - assert head == tail;
1.152 - int p = head;
1.153 - int n = elements.length;
1.154 - int r = n - p; // number of elements to the right of p
1.155 - int newCapacity = n << 1;
1.156 - if (newCapacity < 0)
1.157 - throw new IllegalStateException("Sorry, deque too big");
1.158 - Object[] a = new Object[newCapacity];
1.159 - System.arraycopy(elements, p, a, 0, r);
1.160 - System.arraycopy(elements, 0, a, r, p);
1.161 - elements = (E[])a;
1.162 - head = 0;
1.163 - tail = n;
1.164 - }
1.165 -
1.166 - /**
1.167 - * Copies the elements from our element array into the specified array,
1.168 - * in order (from first to last element in the deque). It is assumed
1.169 - * that the array is large enough to hold all elements in the deque.
1.170 - *
1.171 - * @return its argument
1.172 - */
1.173 - private <T> T[] copyElements(T[] a) {
1.174 - if (head < tail) {
1.175 - System.arraycopy(elements, head, a, 0, size());
1.176 - } else if (head > tail) {
1.177 - int headPortionLen = elements.length - head;
1.178 - System.arraycopy(elements, head, a, 0, headPortionLen);
1.179 - System.arraycopy(elements, 0, a, headPortionLen, tail);
1.180 - }
1.181 - return a;
1.182 - }
1.183 -
1.184 - /**
1.185 - * Constructs an empty array deque with an initial capacity
1.186 - * sufficient to hold 16 elements.
1.187 - */
1.188 - public ArrayDeque() {
1.189 - elements = (E[]) new Object[16];
1.190 - }
1.191 -
1.192 - /**
1.193 - * Constructs an empty array deque with an initial capacity
1.194 - * sufficient to hold the specified number of elements.
1.195 - *
1.196 - * @param numElements lower bound on initial capacity of the deque
1.197 - */
1.198 - public ArrayDeque(int numElements) {
1.199 - allocateElements(numElements);
1.200 - }
1.201 -
1.202 - /**
1.203 - * Constructs a deque containing the elements of the specified
1.204 - * collection, in the order they are returned by the collection's
1.205 - * iterator. (The first element returned by the collection's
1.206 - * iterator becomes the first element, or <i>front</i> of the
1.207 - * deque.)
1.208 - *
1.209 - * @param c the collection whose elements are to be placed into the deque
1.210 - * @throws NullPointerException if the specified collection is null
1.211 - */
1.212 - public ArrayDeque(Collection<? extends E> c) {
1.213 - allocateElements(c.size());
1.214 - addAll(c);
1.215 - }
1.216 -
1.217 - // The main insertion and extraction methods are addFirst,
1.218 - // addLast, pollFirst, pollLast. The other methods are defined in
1.219 - // terms of these.
1.220 -
1.221 - /**
1.222 - * Inserts the specified element at the front of this deque.
1.223 - *
1.224 - * @param e the element to add
1.225 - * @throws NullPointerException if the specified element is null
1.226 - */
1.227 - public void addFirst(E e) {
1.228 - if (e == null)
1.229 - throw new NullPointerException();
1.230 - elements[head = (head - 1) & (elements.length - 1)] = e;
1.231 - if (head == tail)
1.232 - doubleCapacity();
1.233 - }
1.234 -
1.235 - /**
1.236 - * Inserts the specified element at the end of this deque.
1.237 - *
1.238 - * <p>This method is equivalent to {@link #add}.
1.239 - *
1.240 - * @param e the element to add
1.241 - * @throws NullPointerException if the specified element is null
1.242 - */
1.243 - public void addLast(E e) {
1.244 - if (e == null)
1.245 - throw new NullPointerException();
1.246 - elements[tail] = e;
1.247 - if ( (tail = (tail + 1) & (elements.length - 1)) == head)
1.248 - doubleCapacity();
1.249 - }
1.250 -
1.251 - /**
1.252 - * Inserts the specified element at the front of this deque.
1.253 - *
1.254 - * @param e the element to add
1.255 - * @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
1.256 - * @throws NullPointerException if the specified element is null
1.257 - */
1.258 - public boolean offerFirst(E e) {
1.259 - addFirst(e);
1.260 - return true;
1.261 - }
1.262 -
1.263 - /**
1.264 - * Inserts the specified element at the end of this deque.
1.265 - *
1.266 - * @param e the element to add
1.267 - * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
1.268 - * @throws NullPointerException if the specified element is null
1.269 - */
1.270 - public boolean offerLast(E e) {
1.271 - addLast(e);
1.272 - return true;
1.273 - }
1.274 -
1.275 - /**
1.276 - * @throws NoSuchElementException {@inheritDoc}
1.277 - */
1.278 - public E removeFirst() {
1.279 - E x = pollFirst();
1.280 - if (x == null)
1.281 - throw new NoSuchElementException();
1.282 - return x;
1.283 - }
1.284 -
1.285 - /**
1.286 - * @throws NoSuchElementException {@inheritDoc}
1.287 - */
1.288 - public E removeLast() {
1.289 - E x = pollLast();
1.290 - if (x == null)
1.291 - throw new NoSuchElementException();
1.292 - return x;
1.293 - }
1.294 -
1.295 - public E pollFirst() {
1.296 - int h = head;
1.297 - E result = elements[h]; // Element is null if deque empty
1.298 - if (result == null)
1.299 - return null;
1.300 - elements[h] = null; // Must null out slot
1.301 - head = (h + 1) & (elements.length - 1);
1.302 - return result;
1.303 - }
1.304 -
1.305 - public E pollLast() {
1.306 - int t = (tail - 1) & (elements.length - 1);
1.307 - E result = elements[t];
1.308 - if (result == null)
1.309 - return null;
1.310 - elements[t] = null;
1.311 - tail = t;
1.312 - return result;
1.313 - }
1.314 -
1.315 - /**
1.316 - * @throws NoSuchElementException {@inheritDoc}
1.317 - */
1.318 - public E getFirst() {
1.319 - E x = elements[head];
1.320 - if (x == null)
1.321 - throw new NoSuchElementException();
1.322 - return x;
1.323 - }
1.324 -
1.325 - /**
1.326 - * @throws NoSuchElementException {@inheritDoc}
1.327 - */
1.328 - public E getLast() {
1.329 - E x = elements[(tail - 1) & (elements.length - 1)];
1.330 - if (x == null)
1.331 - throw new NoSuchElementException();
1.332 - return x;
1.333 - }
1.334 -
1.335 - public E peekFirst() {
1.336 - return elements[head]; // elements[head] is null if deque empty
1.337 - }
1.338 -
1.339 - public E peekLast() {
1.340 - return elements[(tail - 1) & (elements.length - 1)];
1.341 - }
1.342 -
1.343 - /**
1.344 - * Removes the first occurrence of the specified element in this
1.345 - * deque (when traversing the deque from head to tail).
1.346 - * If the deque does not contain the element, it is unchanged.
1.347 - * More formally, removes the first element <tt>e</tt> such that
1.348 - * <tt>o.equals(e)</tt> (if such an element exists).
1.349 - * Returns <tt>true</tt> if this deque contained the specified element
1.350 - * (or equivalently, if this deque changed as a result of the call).
1.351 - *
1.352 - * @param o element to be removed from this deque, if present
1.353 - * @return <tt>true</tt> if the deque contained the specified element
1.354 - */
1.355 - public boolean removeFirstOccurrence(Object o) {
1.356 - if (o == null)
1.357 - return false;
1.358 - int mask = elements.length - 1;
1.359 - int i = head;
1.360 - E x;
1.361 - while ( (x = elements[i]) != null) {
1.362 - if (o.equals(x)) {
1.363 - delete(i);
1.364 - return true;
1.365 - }
1.366 - i = (i + 1) & mask;
1.367 - }
1.368 - return false;
1.369 - }
1.370 -
1.371 - /**
1.372 - * Removes the last occurrence of the specified element in this
1.373 - * deque (when traversing the deque from head to tail).
1.374 - * If the deque does not contain the element, it is unchanged.
1.375 - * More formally, removes the last element <tt>e</tt> such that
1.376 - * <tt>o.equals(e)</tt> (if such an element exists).
1.377 - * Returns <tt>true</tt> if this deque contained the specified element
1.378 - * (or equivalently, if this deque changed as a result of the call).
1.379 - *
1.380 - * @param o element to be removed from this deque, if present
1.381 - * @return <tt>true</tt> if the deque contained the specified element
1.382 - */
1.383 - public boolean removeLastOccurrence(Object o) {
1.384 - if (o == null)
1.385 - return false;
1.386 - int mask = elements.length - 1;
1.387 - int i = (tail - 1) & mask;
1.388 - E x;
1.389 - while ( (x = elements[i]) != null) {
1.390 - if (o.equals(x)) {
1.391 - delete(i);
1.392 - return true;
1.393 - }
1.394 - i = (i - 1) & mask;
1.395 - }
1.396 - return false;
1.397 - }
1.398 -
1.399 - // *** Queue methods ***
1.400 -
1.401 - /**
1.402 - * Inserts the specified element at the end of this deque.
1.403 - *
1.404 - * <p>This method is equivalent to {@link #addLast}.
1.405 - *
1.406 - * @param e the element to add
1.407 - * @return <tt>true</tt> (as specified by {@link Collection#add})
1.408 - * @throws NullPointerException if the specified element is null
1.409 - */
1.410 - public boolean add(E e) {
1.411 - addLast(e);
1.412 - return true;
1.413 - }
1.414 -
1.415 - /**
1.416 - * Inserts the specified element at the end of this deque.
1.417 - *
1.418 - * <p>This method is equivalent to {@link #offerLast}.
1.419 - *
1.420 - * @param e the element to add
1.421 - * @return <tt>true</tt> (as specified by {@link Queue#offer})
1.422 - * @throws NullPointerException if the specified element is null
1.423 - */
1.424 - public boolean offer(E e) {
1.425 - return offerLast(e);
1.426 - }
1.427 -
1.428 - /**
1.429 - * Retrieves and removes the head of the queue represented by this deque.
1.430 - *
1.431 - * This method differs from {@link #poll poll} only in that it throws an
1.432 - * exception if this deque is empty.
1.433 - *
1.434 - * <p>This method is equivalent to {@link #removeFirst}.
1.435 - *
1.436 - * @return the head of the queue represented by this deque
1.437 - * @throws NoSuchElementException {@inheritDoc}
1.438 - */
1.439 - public E remove() {
1.440 - return removeFirst();
1.441 - }
1.442 -
1.443 - /**
1.444 - * Retrieves and removes the head of the queue represented by this deque
1.445 - * (in other words, the first element of this deque), or returns
1.446 - * <tt>null</tt> if this deque is empty.
1.447 - *
1.448 - * <p>This method is equivalent to {@link #pollFirst}.
1.449 - *
1.450 - * @return the head of the queue represented by this deque, or
1.451 - * <tt>null</tt> if this deque is empty
1.452 - */
1.453 - public E poll() {
1.454 - return pollFirst();
1.455 - }
1.456 -
1.457 - /**
1.458 - * Retrieves, but does not remove, the head of the queue represented by
1.459 - * this deque. This method differs from {@link #peek peek} only in
1.460 - * that it throws an exception if this deque is empty.
1.461 - *
1.462 - * <p>This method is equivalent to {@link #getFirst}.
1.463 - *
1.464 - * @return the head of the queue represented by this deque
1.465 - * @throws NoSuchElementException {@inheritDoc}
1.466 - */
1.467 - public E element() {
1.468 - return getFirst();
1.469 - }
1.470 -
1.471 - /**
1.472 - * Retrieves, but does not remove, the head of the queue represented by
1.473 - * this deque, or returns <tt>null</tt> if this deque is empty.
1.474 - *
1.475 - * <p>This method is equivalent to {@link #peekFirst}.
1.476 - *
1.477 - * @return the head of the queue represented by this deque, or
1.478 - * <tt>null</tt> if this deque is empty
1.479 - */
1.480 - public E peek() {
1.481 - return peekFirst();
1.482 - }
1.483 -
1.484 - // *** Stack methods ***
1.485 -
1.486 - /**
1.487 - * Pushes an element onto the stack represented by this deque. In other
1.488 - * words, inserts the element at the front of this deque.
1.489 - *
1.490 - * <p>This method is equivalent to {@link #addFirst}.
1.491 - *
1.492 - * @param e the element to push
1.493 - * @throws NullPointerException if the specified element is null
1.494 - */
1.495 - public void push(E e) {
1.496 - addFirst(e);
1.497 - }
1.498 -
1.499 - /**
1.500 - * Pops an element from the stack represented by this deque. In other
1.501 - * words, removes and returns the first element of this deque.
1.502 - *
1.503 - * <p>This method is equivalent to {@link #removeFirst()}.
1.504 - *
1.505 - * @return the element at the front of this deque (which is the top
1.506 - * of the stack represented by this deque)
1.507 - * @throws NoSuchElementException {@inheritDoc}
1.508 - */
1.509 - public E pop() {
1.510 - return removeFirst();
1.511 - }
1.512 -
1.513 - private void checkInvariants() {
1.514 - assert elements[tail] == null;
1.515 - assert head == tail ? elements[head] == null :
1.516 - (elements[head] != null &&
1.517 - elements[(tail - 1) & (elements.length - 1)] != null);
1.518 - assert elements[(head - 1) & (elements.length - 1)] == null;
1.519 - }
1.520 -
1.521 - /**
1.522 - * Removes the element at the specified position in the elements array,
1.523 - * adjusting head and tail as necessary. This can result in motion of
1.524 - * elements backwards or forwards in the array.
1.525 - *
1.526 - * <p>This method is called delete rather than remove to emphasize
1.527 - * that its semantics differ from those of {@link List#remove(int)}.
1.528 - *
1.529 - * @return true if elements moved backwards
1.530 - */
1.531 - private boolean delete(int i) {
1.532 - checkInvariants();
1.533 - final E[] elements = this.elements;
1.534 - final int mask = elements.length - 1;
1.535 - final int h = head;
1.536 - final int t = tail;
1.537 - final int front = (i - h) & mask;
1.538 - final int back = (t - i) & mask;
1.539 -
1.540 - // Invariant: head <= i < tail mod circularity
1.541 - if (front >= ((t - h) & mask))
1.542 - throw new ConcurrentModificationException();
1.543 -
1.544 - // Optimize for least element motion
1.545 - if (front < back) {
1.546 - if (h <= i) {
1.547 - System.arraycopy(elements, h, elements, h + 1, front);
1.548 - } else { // Wrap around
1.549 - System.arraycopy(elements, 0, elements, 1, i);
1.550 - elements[0] = elements[mask];
1.551 - System.arraycopy(elements, h, elements, h + 1, mask - h);
1.552 - }
1.553 - elements[h] = null;
1.554 - head = (h + 1) & mask;
1.555 - return false;
1.556 - } else {
1.557 - if (i < t) { // Copy the null tail as well
1.558 - System.arraycopy(elements, i + 1, elements, i, back);
1.559 - tail = t - 1;
1.560 - } else { // Wrap around
1.561 - System.arraycopy(elements, i + 1, elements, i, mask - i);
1.562 - elements[mask] = elements[0];
1.563 - System.arraycopy(elements, 1, elements, 0, t);
1.564 - tail = (t - 1) & mask;
1.565 - }
1.566 - return true;
1.567 - }
1.568 - }
1.569 -
1.570 - // *** Collection Methods ***
1.571 -
1.572 - /**
1.573 - * Returns the number of elements in this deque.
1.574 - *
1.575 - * @return the number of elements in this deque
1.576 - */
1.577 - public int size() {
1.578 - return (tail - head) & (elements.length - 1);
1.579 - }
1.580 -
1.581 - /**
1.582 - * Returns <tt>true</tt> if this deque contains no elements.
1.583 - *
1.584 - * @return <tt>true</tt> if this deque contains no elements
1.585 - */
1.586 - public boolean isEmpty() {
1.587 - return head == tail;
1.588 - }
1.589 -
1.590 - /**
1.591 - * Returns an iterator over the elements in this deque. The elements
1.592 - * will be ordered from first (head) to last (tail). This is the same
1.593 - * order that elements would be dequeued (via successive calls to
1.594 - * {@link #remove} or popped (via successive calls to {@link #pop}).
1.595 - *
1.596 - * @return an iterator over the elements in this deque
1.597 - */
1.598 - public Iterator<E> iterator() {
1.599 - return new DeqIterator();
1.600 - }
1.601 -
1.602 - public Iterator<E> descendingIterator() {
1.603 - return new DescendingIterator();
1.604 - }
1.605 -
1.606 - private class DeqIterator implements Iterator<E> {
1.607 - /**
1.608 - * Index of element to be returned by subsequent call to next.
1.609 - */
1.610 - private int cursor = head;
1.611 -
1.612 - /**
1.613 - * Tail recorded at construction (also in remove), to stop
1.614 - * iterator and also to check for comodification.
1.615 - */
1.616 - private int fence = tail;
1.617 -
1.618 - /**
1.619 - * Index of element returned by most recent call to next.
1.620 - * Reset to -1 if element is deleted by a call to remove.
1.621 - */
1.622 - private int lastRet = -1;
1.623 -
1.624 - public boolean hasNext() {
1.625 - return cursor != fence;
1.626 - }
1.627 -
1.628 - public E next() {
1.629 - if (cursor == fence)
1.630 - throw new NoSuchElementException();
1.631 - E result = elements[cursor];
1.632 - // This check doesn't catch all possible comodifications,
1.633 - // but does catch the ones that corrupt traversal
1.634 - if (tail != fence || result == null)
1.635 - throw new ConcurrentModificationException();
1.636 - lastRet = cursor;
1.637 - cursor = (cursor + 1) & (elements.length - 1);
1.638 - return result;
1.639 - }
1.640 -
1.641 - public void remove() {
1.642 - if (lastRet < 0)
1.643 - throw new IllegalStateException();
1.644 - if (delete(lastRet)) { // if left-shifted, undo increment in next()
1.645 - cursor = (cursor - 1) & (elements.length - 1);
1.646 - fence = tail;
1.647 - }
1.648 - lastRet = -1;
1.649 - }
1.650 - }
1.651 -
1.652 - private class DescendingIterator implements Iterator<E> {
1.653 - /*
1.654 - * This class is nearly a mirror-image of DeqIterator, using
1.655 - * tail instead of head for initial cursor, and head instead of
1.656 - * tail for fence.
1.657 - */
1.658 - private int cursor = tail;
1.659 - private int fence = head;
1.660 - private int lastRet = -1;
1.661 -
1.662 - public boolean hasNext() {
1.663 - return cursor != fence;
1.664 - }
1.665 -
1.666 - public E next() {
1.667 - if (cursor == fence)
1.668 - throw new NoSuchElementException();
1.669 - cursor = (cursor - 1) & (elements.length - 1);
1.670 - E result = elements[cursor];
1.671 - if (head != fence || result == null)
1.672 - throw new ConcurrentModificationException();
1.673 - lastRet = cursor;
1.674 - return result;
1.675 - }
1.676 -
1.677 - public void remove() {
1.678 - if (lastRet < 0)
1.679 - throw new IllegalStateException();
1.680 - if (!delete(lastRet)) {
1.681 - cursor = (cursor + 1) & (elements.length - 1);
1.682 - fence = head;
1.683 - }
1.684 - lastRet = -1;
1.685 - }
1.686 - }
1.687 -
1.688 - /**
1.689 - * Returns <tt>true</tt> if this deque contains the specified element.
1.690 - * More formally, returns <tt>true</tt> if and only if this deque contains
1.691 - * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
1.692 - *
1.693 - * @param o object to be checked for containment in this deque
1.694 - * @return <tt>true</tt> if this deque contains the specified element
1.695 - */
1.696 - public boolean contains(Object o) {
1.697 - if (o == null)
1.698 - return false;
1.699 - int mask = elements.length - 1;
1.700 - int i = head;
1.701 - E x;
1.702 - while ( (x = elements[i]) != null) {
1.703 - if (o.equals(x))
1.704 - return true;
1.705 - i = (i + 1) & mask;
1.706 - }
1.707 - return false;
1.708 - }
1.709 -
1.710 - /**
1.711 - * Removes a single instance of the specified element from this deque.
1.712 - * If the deque does not contain the element, it is unchanged.
1.713 - * More formally, removes the first element <tt>e</tt> such that
1.714 - * <tt>o.equals(e)</tt> (if such an element exists).
1.715 - * Returns <tt>true</tt> if this deque contained the specified element
1.716 - * (or equivalently, if this deque changed as a result of the call).
1.717 - *
1.718 - * <p>This method is equivalent to {@link #removeFirstOccurrence}.
1.719 - *
1.720 - * @param o element to be removed from this deque, if present
1.721 - * @return <tt>true</tt> if this deque contained the specified element
1.722 - */
1.723 - public boolean remove(Object o) {
1.724 - return removeFirstOccurrence(o);
1.725 - }
1.726 -
1.727 - /**
1.728 - * Removes all of the elements from this deque.
1.729 - * The deque will be empty after this call returns.
1.730 - */
1.731 - public void clear() {
1.732 - int h = head;
1.733 - int t = tail;
1.734 - if (h != t) { // clear all cells
1.735 - head = tail = 0;
1.736 - int i = h;
1.737 - int mask = elements.length - 1;
1.738 - do {
1.739 - elements[i] = null;
1.740 - i = (i + 1) & mask;
1.741 - } while (i != t);
1.742 - }
1.743 - }
1.744 -
1.745 - /**
1.746 - * Returns an array containing all of the elements in this deque
1.747 - * in proper sequence (from first to last element).
1.748 - *
1.749 - * <p>The returned array will be "safe" in that no references to it are
1.750 - * maintained by this deque. (In other words, this method must allocate
1.751 - * a new array). The caller is thus free to modify the returned array.
1.752 - *
1.753 - * <p>This method acts as bridge between array-based and collection-based
1.754 - * APIs.
1.755 - *
1.756 - * @return an array containing all of the elements in this deque
1.757 - */
1.758 - public Object[] toArray() {
1.759 - return copyElements(new Object[size()]);
1.760 - }
1.761 -
1.762 - /**
1.763 - * Returns an array containing all of the elements in this deque in
1.764 - * proper sequence (from first to last element); the runtime type of the
1.765 - * returned array is that of the specified array. If the deque fits in
1.766 - * the specified array, it is returned therein. Otherwise, a new array
1.767 - * is allocated with the runtime type of the specified array and the
1.768 - * size of this deque.
1.769 - *
1.770 - * <p>If this deque fits in the specified array with room to spare
1.771 - * (i.e., the array has more elements than this deque), the element in
1.772 - * the array immediately following the end of the deque is set to
1.773 - * <tt>null</tt>.
1.774 - *
1.775 - * <p>Like the {@link #toArray()} method, this method acts as bridge between
1.776 - * array-based and collection-based APIs. Further, this method allows
1.777 - * precise control over the runtime type of the output array, and may,
1.778 - * under certain circumstances, be used to save allocation costs.
1.779 - *
1.780 - * <p>Suppose <tt>x</tt> is a deque known to contain only strings.
1.781 - * The following code can be used to dump the deque into a newly
1.782 - * allocated array of <tt>String</tt>:
1.783 - *
1.784 - * <pre>
1.785 - * String[] y = x.toArray(new String[0]);</pre>
1.786 - *
1.787 - * Note that <tt>toArray(new Object[0])</tt> is identical in function to
1.788 - * <tt>toArray()</tt>.
1.789 - *
1.790 - * @param a the array into which the elements of the deque are to
1.791 - * be stored, if it is big enough; otherwise, a new array of the
1.792 - * same runtime type is allocated for this purpose
1.793 - * @return an array containing all of the elements in this deque
1.794 - * @throws ArrayStoreException if the runtime type of the specified array
1.795 - * is not a supertype of the runtime type of every element in
1.796 - * this deque
1.797 - * @throws NullPointerException if the specified array is null
1.798 - */
1.799 - public <T> T[] toArray(T[] a) {
1.800 - int size = size();
1.801 - if (a.length < size)
1.802 - a = (T[])java.lang.reflect.Array.newInstance(
1.803 - a.getClass().getComponentType(), size);
1.804 - copyElements(a);
1.805 - if (a.length > size)
1.806 - a[size] = null;
1.807 - return a;
1.808 - }
1.809 -
1.810 - // *** Object methods ***
1.811 -
1.812 - /**
1.813 - * Returns a copy of this deque.
1.814 - *
1.815 - * @return a copy of this deque
1.816 - */
1.817 - public ArrayDeque<E> clone() {
1.818 - try {
1.819 - ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
1.820 - result.elements = Arrays.copyOf(elements, elements.length);
1.821 - return result;
1.822 -
1.823 - } catch (CloneNotSupportedException e) {
1.824 - throw new AssertionError();
1.825 - }
1.826 - }
1.827 -
1.828 - /**
1.829 - * Appease the serialization gods.
1.830 - */
1.831 - private static final long serialVersionUID = 2340985798034038923L;
1.832 -
1.833 -}