1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/ArrayDeque.java Tue Feb 26 16:54:16 2013 +0100
1.3 @@ -0,0 +1,830 @@
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 +}