ArrayDeque.java revision 2f03027aaa09158ac70ebf9c6b53f7bb8c495541
16232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson/* 22f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Written by Josh Bloch of Google Inc. and released to the public domain, 32f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * as explained at http://creativecommons.org/licenses/publicdomain. 46232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 56232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 66232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonpackage java.util; 76232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 82f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson// BEGIN android-note 92f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson// removed link to collections framework docs 102f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson// END android-note 112f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 122f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilsonimport java.io.*; 136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson/** 152f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Resizable-array implementation of the {@link Deque} interface. Array 162f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * deques have no capacity restrictions; they grow as necessary to support 172f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * usage. They are not thread-safe; in the absence of external 182f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * synchronization, they do not support concurrent access by multiple threads. 192f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Null elements are prohibited. This class is likely to be faster than 202f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * {@link Stack} when used as a stack, and faster than {@link LinkedList} 212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * when used as a queue. 222f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 232f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time. 242f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Exceptions include {@link #remove(Object) remove}, {@link 252f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence 262f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * removeLastOccurrence}, {@link #contains contains}, {@link #iterator 272f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * iterator.remove()}, and the bulk operations, all of which run in linear 282f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * time. 296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 302f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>The iterators returned by this class's <tt>iterator</tt> method are 312f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <i>fail-fast</i>: If the deque is modified at any time after the iterator 322f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * is created, in any way except through the iterator's own <tt>remove</tt> 332f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * method, the iterator will generally throw a {@link 342f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * ConcurrentModificationException}. Thus, in the face of concurrent 352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * modification, the iterator fails quickly and cleanly, rather than risking 362f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * arbitrary, non-deterministic behavior at an undetermined time in the 372f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * future. 386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 392f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 402f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * as it is, generally speaking, impossible to make any hard guarantees in the 412f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * presence of unsynchronized concurrent modification. Fail-fast iterators 422f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 432f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Therefore, it would be wrong to write a program that depended on this 442f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * exception for its correctness: <i>the fail-fast behavior of iterators 452f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * should be used only to detect bugs.</i> 466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 472f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This class and its iterator implement all of the 482f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <em>optional</em> methods of the {@link Collection} and {@link 492f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Iterator} interfaces. 506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 512f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @author Josh Bloch and Doug Lea 522f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @since 1.6 532f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param <E> the type of elements held in this collection 546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 552f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilsonpublic class ArrayDeque<E> extends AbstractCollection<E> 562f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson implements Deque<E>, Cloneable, Serializable 572f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson{ 582f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 592f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * The array in which the elements of the deque are stored. 602f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * The capacity of the deque is the length of this array, which is 612f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * always a power of two. The array is never allowed to become 622f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * full, except transiently within an addX method where it is 632f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * resized (see doubleCapacity) immediately upon becoming full, 642f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * thus avoiding head and tail wrapping around to equal each 652f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * other. We also guarantee that all array cells not holding 662f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * deque elements are always null. 672f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private transient E[] elements; 696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 702f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 712f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * The index of the element at the head of the deque (which is the 722f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * element that would be removed by remove() or pop()); or an 732f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * arbitrary number equal to tail if the deque is empty. 742f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 752f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private transient int head; 766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 772f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 782f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * The index at which the next element would be added to the tail 792f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * of the deque (via addLast(E), add(E), or push(E)). 802f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 812f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private transient int tail; 826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 832f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 842f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * The minimum capacity that we'll use for a newly created deque. 852f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Must be a power of 2. 862f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 872f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private static final int MIN_INITIAL_CAPACITY = 8; 886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 892f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // ****** Array allocation and resizing utilities ****** 906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 912f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 922f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Allocate empty array to hold the given number of elements. 932f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 942f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param numElements the number of elements to hold 952f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 962f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private void allocateElements(int numElements) { 972f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int initialCapacity = MIN_INITIAL_CAPACITY; 982f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // Find the best power of two to hold elements. 992f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // Tests "<=" because arrays aren't kept full. 1002f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (numElements >= initialCapacity) { 1012f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson initialCapacity = numElements; 1022f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson initialCapacity |= (initialCapacity >>> 1); 1032f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson initialCapacity |= (initialCapacity >>> 2); 1042f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson initialCapacity |= (initialCapacity >>> 4); 1052f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson initialCapacity |= (initialCapacity >>> 8); 1062f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson initialCapacity |= (initialCapacity >>> 16); 1072f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson initialCapacity++; 1086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1092f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (initialCapacity < 0) // Too many elements, must back off 1102f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements 1116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1122f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements = (E[]) new Object[initialCapacity]; 1136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1152f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 1162f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Double the capacity of this deque. Call only when full, i.e., 1172f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * when head and tail have wrapped around to become equal. 1186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1192f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private void doubleCapacity() { 1202f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson assert head == tail; 1212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int p = head; 1222f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int n = elements.length; 1232f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int r = n - p; // number of elements to the right of p 1242f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int newCapacity = n << 1; 1252f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (newCapacity < 0) 1262f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new IllegalStateException("Sorry, deque too big"); 1272f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson Object[] a = new Object[newCapacity]; 1282f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, p, a, 0, r); 1292f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, 0, a, r, p); 1302f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements = (E[])a; 1312f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson head = 0; 1322f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson tail = n; 1332f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 1346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 1362f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Copies the elements from our element array into the specified array, 1372f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * in order (from first to last element in the deque). It is assumed 1382f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * that the array is large enough to hold all elements in the deque. 1392f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 1402f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return its argument 1412f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 1422f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private <T> T[] copyElements(T[] a) { 1432f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (head < tail) { 1442f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, head, a, 0, size()); 1452f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } else if (head > tail) { 1462f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int headPortionLen = elements.length - head; 1472f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, head, a, 0, headPortionLen); 1482f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, 0, a, headPortionLen, tail); 1496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1502f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return a; 1516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1542f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Constructs an empty array deque with an initial capacity 1552f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * sufficient to hold 16 elements. 1566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public ArrayDeque() { 1582f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements = (E[]) new Object[16]; 1596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1622f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Constructs an empty array deque with an initial capacity 1632f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * sufficient to hold the specified number of elements. 1646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 1652f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param numElements lower bound on initial capacity of the deque 1666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1672f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public ArrayDeque(int numElements) { 1682f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson allocateElements(numElements); 1696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1722f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Constructs a deque containing the elements of the specified 1732f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * collection, in the order they are returned by the collection's 1742f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * iterator. (The first element returned by the collection's 1752f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * iterator becomes the first element, or <i>front</i> of the 1762f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * deque.) 1776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 1782f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param c the collection whose elements are to be placed into the deque 1792f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified collection is null 1806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public ArrayDeque(Collection<? extends E> c) { 1822f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson allocateElements(c.size()); 1832f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson addAll(c); 1846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1862f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // The main insertion and extraction methods are addFirst, 1872f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // addLast, pollFirst, pollLast. The other methods are defined in 1882f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // terms of these. 1892f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 1906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1912f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Inserts the specified element at the front of this deque. 1926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 1932f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param e the element to add 1942f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified element is null 1956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void addFirst(E e) { 1972f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (e == null) 1982f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new NullPointerException(); 1992f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[head = (head - 1) & (elements.length - 1)] = e; 2002f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (head == tail) 2012f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson doubleCapacity(); 2026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2052f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Inserts the specified element at the end of this deque. 2062f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 2072f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #add}. 2086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 2092f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param e the element to add 2102f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified element is null 2116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void addLast(E e) { 2132f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (e == null) 2142f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new NullPointerException(); 2152f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[tail] = e; 2162f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if ( (tail = (tail + 1) & (elements.length - 1)) == head) 2172f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson doubleCapacity(); 2186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Inserts the specified element at the front of this deque. 2226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 2232f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param e the element to add 2242f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> (as specified by {@link Deque#offerFirst}) 2252f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified element is null 2266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2272f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean offerFirst(E e) { 2282f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson addFirst(e); 2296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 2306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2332f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Inserts the specified element at the end of this deque. 2346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 2352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param e the element to add 2362f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> (as specified by {@link Deque#offerLast}) 2372f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified element is null 2386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean offerLast(E e) { 2402f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson addLast(e); 2412f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return true; 2426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2452f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NoSuchElementException {@inheritDoc} 2466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2472f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E removeFirst() { 2482f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson E x = pollFirst(); 2492f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (x == null) 2502f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new NoSuchElementException(); 2512f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return x; 2526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2552f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NoSuchElementException {@inheritDoc} 2566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2572f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E removeLast() { 2582f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson E x = pollLast(); 2592f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (x == null) 2602f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new NoSuchElementException(); 2612f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return x; 2626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2642f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E pollFirst() { 2652f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int h = head; 2662f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson E result = elements[h]; // Element is null if deque empty 2672f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (result == null) 2682f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return null; 2692f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[h] = null; // Must null out slot 2702f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson head = (h + 1) & (elements.length - 1); 2712f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return result; 2722f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 2732f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 2742f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E pollLast() { 2752f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int t = (tail - 1) & (elements.length - 1); 2762f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson E result = elements[t]; 2772f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (result == null) 2782f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return null; 2792f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[t] = null; 2802f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson tail = t; 2812f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return result; 2826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2852f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NoSuchElementException {@inheritDoc} 2866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2872f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E getFirst() { 2882f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson E x = elements[head]; 2892f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (x == null) 2902f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new NoSuchElementException(); 2912f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return x; 2926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2952f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NoSuchElementException {@inheritDoc} 2966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2972f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E getLast() { 2982f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson E x = elements[(tail - 1) & (elements.length - 1)]; 2992f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (x == null) 3002f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new NoSuchElementException(); 3012f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return x; 3022f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 3032f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 3042f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E peekFirst() { 3052f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return elements[head]; // elements[head] is null if deque empty 3062f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 3072f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 3082f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E peekLast() { 3092f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return elements[(tail - 1) & (elements.length - 1)]; 3106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3132f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Removes the first occurrence of the specified element in this 3142f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * deque (when traversing the deque from head to tail). 3152f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * If the deque does not contain the element, it is unchanged. 3162f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * More formally, removes the first element <tt>e</tt> such that 3172f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>o.equals(e)</tt> (if such an element exists). 3182f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns <tt>true</tt> if this deque contained the specified element 3192f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * (or equivalently, if this deque changed as a result of the call). 3206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 3212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param o element to be removed from this deque, if present 3222f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> if the deque contained the specified element 3236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3242f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean removeFirstOccurrence(Object o) { 3252f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (o == null) 3262f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return false; 3272f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int mask = elements.length - 1; 3282f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int i = head; 3292f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson E x; 3302f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson while ( (x = elements[i]) != null) { 3312f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (o.equals(x)) { 3322f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson delete(i); 3332f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return true; 3342f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 3352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson i = (i + 1) & mask; 3362f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 3372f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return false; 3386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3412f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Removes the last occurrence of the specified element in this 3422f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * deque (when traversing the deque from head to tail). 3432f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * If the deque does not contain the element, it is unchanged. 3442f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * More formally, removes the last element <tt>e</tt> such that 3452f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>o.equals(e)</tt> (if such an element exists). 3462f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns <tt>true</tt> if this deque contained the specified element 3472f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * (or equivalently, if this deque changed as a result of the call). 3482f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 3492f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param o element to be removed from this deque, if present 3502f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> if the deque contained the specified element 3512f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 3522f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean removeLastOccurrence(Object o) { 3532f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (o == null) 3542f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return false; 3552f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int mask = elements.length - 1; 3562f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int i = (tail - 1) & mask; 3572f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson E x; 3582f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson while ( (x = elements[i]) != null) { 3592f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (o.equals(x)) { 3602f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson delete(i); 3612f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return true; 3622f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 3632f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson i = (i - 1) & mask; 3642f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 3652f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return false; 3666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3682f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // *** Queue methods *** 3692f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 3706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3712f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Inserts the specified element at the end of this deque. 3726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 3732f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #addLast}. 3742f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 3752f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param e the element to add 3762f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> (as specified by {@link Collection#add}) 3772f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified element is null 3786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3792f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean add(E e) { 3802f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson addLast(e); 3812f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return true; 3826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3852f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Inserts the specified element at the end of this deque. 3862f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 3872f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #offerLast}. 3886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 3892f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param e the element to add 3902f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> (as specified by {@link Queue#offer}) 3912f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified element is null 3926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3932f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean offer(E e) { 3942f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return offerLast(e); 3956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3982f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Retrieves and removes the head of the queue represented by this deque. 3992f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 4002f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * This method differs from {@link #poll poll} only in that it throws an 4012f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * exception if this deque is empty. 4022f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 4032f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #removeFirst}. 4046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 4052f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return the head of the queue represented by this deque 4062f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NoSuchElementException {@inheritDoc} 4076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4082f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E remove() { 4092f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return removeFirst(); 4106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 4132f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Retrieves and removes the head of the queue represented by this deque 4142f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * (in other words, the first element of this deque), or returns 4152f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>null</tt> if this deque is empty. 4162f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 4172f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #pollFirst}. 4186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 4192f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return the head of the queue represented by this deque, or 4202f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>null</tt> if this deque is empty 4216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4222f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E poll() { 4232f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return pollFirst(); 4246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 4272f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Retrieves, but does not remove, the head of the queue represented by 4282f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * this deque. This method differs from {@link #peek peek} only in 4292f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * that it throws an exception if this deque is empty. 4306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 4312f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #getFirst}. 4322f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 4332f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return the head of the queue represented by this deque 4342f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NoSuchElementException {@inheritDoc} 4356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E element() { 4376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return getFirst(); 4386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 4412f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Retrieves, but does not remove, the head of the queue represented by 4422f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * this deque, or returns <tt>null</tt> if this deque is empty. 4432f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 4442f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #peekFirst}. 4456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 4462f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return the head of the queue represented by this deque, or 4472f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>null</tt> if this deque is empty 4486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4492f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E peek() { 4502f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return peekFirst(); 4516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4532f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // *** Stack methods *** 4542f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 4556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 4562f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Pushes an element onto the stack represented by this deque. In other 4572f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * words, inserts the element at the front of this deque. 4582f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 4592f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #addFirst}. 4606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 4612f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param e the element to push 4622f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified element is null 4636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4642f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public void push(E e) { 4652f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson addFirst(e); 4666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 4692f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Pops an element from the stack represented by this deque. In other 4702f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * words, removes and returns the first element of this deque. 4712f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 4722f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #removeFirst()}. 4736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 4742f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return the element at the front of this deque (which is the top 4752f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * of the stack represented by this deque) 4762f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NoSuchElementException {@inheritDoc} 4776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4782f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E pop() { 4792f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return removeFirst(); 4802f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 4812f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 4822f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private void checkInvariants() { 4832f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson assert elements[tail] == null; 4842f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson assert head == tail ? elements[head] == null : 4852f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson (elements[head] != null && 4862f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[(tail - 1) & (elements.length - 1)] != null); 4872f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson assert elements[(head - 1) & (elements.length - 1)] == null; 4886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 4912f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Removes the element at the specified position in the elements array, 4922f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * adjusting head and tail as necessary. This can result in motion of 4932f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * elements backwards or forwards in the array. 4946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 4952f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is called delete rather than remove to emphasize 4962f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * that its semantics differ from those of {@link List#remove(int)}. 4972f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 4982f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return true if elements moved backwards 4996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 5002f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private boolean delete(int i) { 5012f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson checkInvariants(); 5022f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson final E[] elements = this.elements; 5032f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson final int mask = elements.length - 1; 5042f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson final int h = head; 5052f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson final int t = tail; 5062f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson final int front = (i - h) & mask; 5072f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson final int back = (t - i) & mask; 5086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5092f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // Invariant: head <= i < tail mod circularity 5102f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (front >= ((t - h) & mask)) 5112f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new ConcurrentModificationException(); 5126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5132f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // Optimize for least element motion 5142f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (front < back) { 5152f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (h <= i) { 5162f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, h, elements, h + 1, front); 5172f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } else { // Wrap around 5182f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, 0, elements, 1, i); 5192f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[0] = elements[mask]; 5202f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, h, elements, h + 1, mask - h); 5212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 5222f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[h] = null; 5232f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson head = (h + 1) & mask; 5242f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return false; 5252f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } else { 5262f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (i < t) { // Copy the null tail as well 5272f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, i + 1, elements, i, back); 5282f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson tail = t - 1; 5292f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } else { // Wrap around 5302f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, i + 1, elements, i, mask - i); 5312f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[mask] = elements[0]; 5322f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, 1, elements, 0, t); 5332f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson tail = (t - 1) & mask; 5342f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 5352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return true; 5366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5392f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // *** Collection Methods *** 5406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5412f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 5422f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns the number of elements in this deque. 5432f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 5442f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return the number of elements in this deque 5452f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 5462f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public int size() { 5472f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return (tail - head) & (elements.length - 1); 5486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5502f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 5512f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns <tt>true</tt> if this deque contains no elements. 5522f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 5532f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> if this deque contains no elements 5546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 5552f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean isEmpty() { 5562f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return head == tail; 5576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 5602f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns an iterator over the elements in this deque. The elements 5612f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * will be ordered from first (head) to last (tail). This is the same 5622f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * order that elements would be dequeued (via successive calls to 5632f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * {@link #remove} or popped (via successive calls to {@link #pop}). 5646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 5652f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return an iterator over the elements in this deque 5666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 5672f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public Iterator<E> iterator() { 5682f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return new DeqIterator(); 5696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5712f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public Iterator<E> descendingIterator() { 5722f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return new DescendingIterator(); 5736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5752f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private class DeqIterator implements Iterator<E> { 5762f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 5772f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Index of element to be returned by subsequent call to next. 5782f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 5792f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private int cursor = head; 5806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5812f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 5822f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Tail recorded at construction (also in remove), to stop 5832f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * iterator and also to check for comodification. 5842f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 5852f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private int fence = tail; 5866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5872f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 5882f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Index of element returned by most recent call to next. 5892f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Reset to -1 if element is deleted by a call to remove. 5902f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 5912f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private int lastRet = -1; 5926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5932f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean hasNext() { 5942f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return cursor != fence; 5952f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 5966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5972f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E next() { 5982f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (cursor == fence) 5992f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new NoSuchElementException(); 6002f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson E result = elements[cursor]; 6012f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // This check doesn't catch all possible comodifications, 6022f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // but does catch the ones that corrupt traversal 6032f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (tail != fence || result == null) 6042f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new ConcurrentModificationException(); 6052f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson lastRet = cursor; 6062f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson cursor = (cursor + 1) & (elements.length - 1); 6072f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return result; 6086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6102f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public void remove() { 6112f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (lastRet < 0) 6122f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new IllegalStateException(); 6132f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (delete(lastRet)) { // if left-shifted, undo increment in next() 6142f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson cursor = (cursor - 1) & (elements.length - 1); 6152f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson fence = tail; 6166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6172f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson lastRet = -1; 6186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private class DescendingIterator implements Iterator<E> { 6222f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /* 6232f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * This class is nearly a mirror-image of DeqIterator, using 6242f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * tail instead of head for initial cursor, and head instead of 6252f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * tail for fence. 6262f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 6272f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private int cursor = tail; 6282f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private int fence = head; 6292f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private int lastRet = -1; 6302f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 6312f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean hasNext() { 6322f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return cursor != fence; 6336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E next() { 6362f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (cursor == fence) 6372f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new NoSuchElementException(); 6382f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson cursor = (cursor - 1) & (elements.length - 1); 6392f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson E result = elements[cursor]; 6402f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (head != fence || result == null) 6412f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new ConcurrentModificationException(); 6422f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson lastRet = cursor; 6432f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return result; 6446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6462f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public void remove() { 6472f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (lastRet < 0) 6482f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new IllegalStateException(); 6492f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (!delete(lastRet)) { 6502f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson cursor = (cursor + 1) & (elements.length - 1); 6512f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson fence = head; 6522f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 6532f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson lastRet = -1; 6542f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 6556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6582f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns <tt>true</tt> if this deque contains the specified element. 6592f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * More formally, returns <tt>true</tt> if and only if this deque contains 6602f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>. 6616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 6622f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param o object to be checked for containment in this deque 6632f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> if this deque contains the specified element 6646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6652f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean contains(Object o) { 6662f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (o == null) 6672f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return false; 6682f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int mask = elements.length - 1; 6692f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int i = head; 6702f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson E x; 6712f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson while ( (x = elements[i]) != null) { 6722f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (o.equals(x)) 6732f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return true; 6742f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson i = (i + 1) & mask; 6756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 6776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6802f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Removes a single instance of the specified element from this deque. 6812f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * If the deque does not contain the element, it is unchanged. 6822f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * More formally, removes the first element <tt>e</tt> such that 6832f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>o.equals(e)</tt> (if such an element exists). 6842f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns <tt>true</tt> if this deque contained the specified element 6852f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * (or equivalently, if this deque changed as a result of the call). 6866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 6872f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #removeFirstOccurrence}. 6882f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 6892f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param o element to be removed from this deque, if present 6902f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> if this deque contained the specified element 6916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6922f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean remove(Object o) { 6932f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return removeFirstOccurrence(o); 6946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6972f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Removes all of the elements from this deque. 6982f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * The deque will be empty after this call returns. 6996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7002f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public void clear() { 7012f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int h = head; 7022f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int t = tail; 7032f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (h != t) { // clear all cells 7042f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson head = tail = 0; 7052f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int i = h; 7062f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int mask = elements.length - 1; 7072f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson do { 7082f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[i] = null; 7092f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson i = (i + 1) & mask; 7102f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } while (i != t); 7116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7152f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns an array containing all of the elements in this deque 7162f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * in proper sequence (from first to last element). 7172f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 7182f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>The returned array will be "safe" in that no references to it are 7192f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * maintained by this deque. (In other words, this method must allocate 7202f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * a new array). The caller is thus free to modify the returned array. 7212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 7222f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method acts as bridge between array-based and collection-based 7232f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * APIs. 7246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 7252f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return an array containing all of the elements in this deque 7266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public Object[] toArray() { 7282f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return copyElements(new Object[size()]); 7296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7322f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns an array containing all of the elements in this deque in 7332f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * proper sequence (from first to last element); the runtime type of the 7342f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * returned array is that of the specified array. If the deque fits in 7352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * the specified array, it is returned therein. Otherwise, a new array 7362f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * is allocated with the runtime type of the specified array and the 7372f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * size of this deque. 7386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 7392f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>If this deque fits in the specified array with room to spare 7402f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * (i.e., the array has more elements than this deque), the element in 7412f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * the array immediately following the end of the deque is set to 7422f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>null</tt>. 7432f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 7442f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>Like the {@link #toArray()} method, this method acts as bridge between 7452f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * array-based and collection-based APIs. Further, this method allows 7462f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * precise control over the runtime type of the output array, and may, 7472f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * under certain circumstances, be used to save allocation costs. 7482f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 7492f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>Suppose <tt>x</tt> is a deque known to contain only strings. 7502f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * The following code can be used to dump the deque into a newly 7512f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * allocated array of <tt>String</tt>: 7522f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 7532f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <pre> 7542f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * String[] y = x.toArray(new String[0]);</pre> 7552f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 7562f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Note that <tt>toArray(new Object[0])</tt> is identical in function to 7572f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>toArray()</tt>. 7582f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 7592f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param a the array into which the elements of the deque are to 7602f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * be stored, if it is big enough; otherwise, a new array of the 7612f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * same runtime type is allocated for this purpose 7622f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return an array containing all of the elements in this deque 7632f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws ArrayStoreException if the runtime type of the specified array 7642f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * is not a supertype of the runtime type of every element in 7652f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * this deque 7662f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified array is null 7676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7682f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public <T> T[] toArray(T[] a) { 7696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson int size = size(); 7702f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (a.length < size) 7712f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson a = (T[])java.lang.reflect.Array.newInstance( 7722f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson a.getClass().getComponentType(), size); 7732f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson copyElements(a); 7742f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (a.length > size) 7752f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson a[size] = null; 7762f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return a; 7776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7792f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // *** Object methods *** 7802f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 7816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7822f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns a copy of this deque. 7836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 7842f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return a copy of this deque 7856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7862f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public ArrayDeque<E> clone() { 7872f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson try { 7882f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson ArrayDeque<E> result = (ArrayDeque<E>) super.clone(); 7892f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson result.elements = Arrays.copyOf(elements, elements.length); 7902f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return result; 7912f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 7922f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } catch (CloneNotSupportedException e) { 7932f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new AssertionError(); 7942f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 7956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7982f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Appease the serialization gods. 7996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 8002f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private static final long serialVersionUID = 2340985798034038923L; 8016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 8026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 8032f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Serialize this deque. 8046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 8052f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @serialData The current size (<tt>int</tt>) of the deque, 8062f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * followed by all of its elements (each an object reference) in 8072f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * first-to-last order. 8086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 8092f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private void writeObject(ObjectOutputStream s) throws IOException { 8102f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson s.defaultWriteObject(); 8112f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 8122f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // Write out size 8132f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson s.writeInt(size()); 8142f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 8152f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // Write out elements in order. 8162f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int mask = elements.length - 1; 8172f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson for (int i = head; i != tail; i = (i + 1) & mask) 8182f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson s.writeObject(elements[i]); 8196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 8206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 8216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 8222f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Deserialize this deque. 8236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 8242f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private void readObject(ObjectInputStream s) 8252f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throws IOException, ClassNotFoundException { 8262f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson s.defaultReadObject(); 8272f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 8282f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // Read in size and allocate array 8292f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int size = s.readInt(); 8302f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson allocateElements(size); 8312f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson head = 0; 8322f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson tail = size; 8336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 8342f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // Read in all elements in the proper order. 8352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson for (int i = 0; i < size; i++) 8362f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[i] = (E)s.readObject(); 8372f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 838bf87c56b39383f6b11c36c3cdc93df4b03fed914Brian Carlstrom} 839