16232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson/* 22f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Written by Josh Bloch of Google Inc. and released to the public domain, 3a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * as explained at http://creativecommons.org/publicdomain/zero/1.0/. 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 126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson/** 132f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Resizable-array implementation of the {@link Deque} interface. Array 142f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * deques have no capacity restrictions; they grow as necessary to support 152f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * usage. They are not thread-safe; in the absence of external 162f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * synchronization, they do not support concurrent access by multiple threads. 172f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Null elements are prohibited. This class is likely to be faster than 182f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * {@link Stack} when used as a stack, and faster than {@link LinkedList} 192f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * when used as a queue. 202f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time. 222f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Exceptions include {@link #remove(Object) remove}, {@link 232f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence 242f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * removeLastOccurrence}, {@link #contains contains}, {@link #iterator 252f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * iterator.remove()}, and the bulk operations, all of which run in linear 262f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * time. 276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 282f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>The iterators returned by this class's <tt>iterator</tt> method are 292f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <i>fail-fast</i>: If the deque is modified at any time after the iterator 302f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * is created, in any way except through the iterator's own <tt>remove</tt> 312f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * method, the iterator will generally throw a {@link 322f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * ConcurrentModificationException}. Thus, in the face of concurrent 332f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * modification, the iterator fails quickly and cleanly, rather than risking 342f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * arbitrary, non-deterministic behavior at an undetermined time in the 352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * future. 366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 372f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 382f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * as it is, generally speaking, impossible to make any hard guarantees in the 392f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * presence of unsynchronized concurrent modification. Fail-fast iterators 402f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 412f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Therefore, it would be wrong to write a program that depended on this 422f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * exception for its correctness: <i>the fail-fast behavior of iterators 432f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * should be used only to detect bugs.</i> 446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 452f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This class and its iterator implement all of the 462f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <em>optional</em> methods of the {@link Collection} and {@link 472f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Iterator} interfaces. 486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 492f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @author Josh Bloch and Doug Lea 502f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @since 1.6 512f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param <E> the type of elements held in this collection 526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 532f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilsonpublic class ArrayDeque<E> extends AbstractCollection<E> 54a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson implements Deque<E>, Cloneable, java.io.Serializable 552f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson{ 562f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 572f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * The array in which the elements of the deque are stored. 582f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * The capacity of the deque is the length of this array, which is 592f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * always a power of two. The array is never allowed to become 602f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * full, except transiently within an addX method where it is 612f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * resized (see doubleCapacity) immediately upon becoming full, 622f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * thus avoiding head and tail wrapping around to equal each 632f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * other. We also guarantee that all array cells not holding 642f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * deque elements are always null. 652f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 66a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private transient Object[] elements; 676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 682f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 692f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * The index of the element at the head of the deque (which is the 702f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * element that would be removed by remove() or pop()); or an 712f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * arbitrary number equal to tail if the deque is empty. 722f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 732f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private transient int head; 746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 752f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 762f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * The index at which the next element would be added to the tail 772f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * of the deque (via addLast(E), add(E), or push(E)). 782f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 792f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private transient int tail; 806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 812f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 822f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * The minimum capacity that we'll use for a newly created deque. 832f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Must be a power of 2. 842f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 852f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private static final int MIN_INITIAL_CAPACITY = 8; 866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 872f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // ****** Array allocation and resizing utilities ****** 886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 892f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 902f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Allocate empty array to hold the given number of elements. 912f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 922f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param numElements the number of elements to hold 932f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 942f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private void allocateElements(int numElements) { 952f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int initialCapacity = MIN_INITIAL_CAPACITY; 962f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // Find the best power of two to hold elements. 972f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // Tests "<=" because arrays aren't kept full. 982f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (numElements >= initialCapacity) { 992f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson initialCapacity = numElements; 1002f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson initialCapacity |= (initialCapacity >>> 1); 1012f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson initialCapacity |= (initialCapacity >>> 2); 1022f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson initialCapacity |= (initialCapacity >>> 4); 1032f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson initialCapacity |= (initialCapacity >>> 8); 1042f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson initialCapacity |= (initialCapacity >>> 16); 1052f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson initialCapacity++; 1066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1072f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (initialCapacity < 0) // Too many elements, must back off 1082f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements 1096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 110a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson elements = new Object[initialCapacity]; 1116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1132f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 1142f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Double the capacity of this deque. Call only when full, i.e., 1152f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * when head and tail have wrapped around to become equal. 1166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1172f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private void doubleCapacity() { 11867a368573213811c0037cb1b972a0d5fdb3eaf48Elliott Hughes // assert head == tail; 1192f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int p = head; 1202f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int n = elements.length; 1212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int r = n - p; // number of elements to the right of p 1222f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int newCapacity = n << 1; 1232f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (newCapacity < 0) 1242f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new IllegalStateException("Sorry, deque too big"); 1252f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson Object[] a = new Object[newCapacity]; 1262f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, p, a, 0, r); 1272f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, 0, a, r, p); 128a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson elements = a; 1292f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson head = 0; 1302f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson tail = n; 1312f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 1326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1332f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 1342f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Copies the elements from our element array into the specified array, 1352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * in order (from first to last element in the deque). It is assumed 1362f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * that the array is large enough to hold all elements in the deque. 1372f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 1382f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return its argument 1392f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 1402f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private <T> T[] copyElements(T[] a) { 1412f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (head < tail) { 1422f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, head, a, 0, size()); 1432f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } else if (head > tail) { 1442f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int headPortionLen = elements.length - head; 1452f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, head, a, 0, headPortionLen); 1462f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, 0, a, headPortionLen, tail); 1476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1482f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return a; 1496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1522f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Constructs an empty array deque with an initial capacity 1532f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * sufficient to hold 16 elements. 1546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public ArrayDeque() { 156a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson elements = new Object[16]; 1576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1602f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Constructs an empty array deque with an initial capacity 1612f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * sufficient to hold the specified number of elements. 1626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 1632f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param numElements lower bound on initial capacity of the deque 1646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1652f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public ArrayDeque(int numElements) { 1662f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson allocateElements(numElements); 1676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1702f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Constructs a deque containing the elements of the specified 1712f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * collection, in the order they are returned by the collection's 1722f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * iterator. (The first element returned by the collection's 1732f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * iterator becomes the first element, or <i>front</i> of the 1742f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * deque.) 1756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 1762f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param c the collection whose elements are to be placed into the deque 1772f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified collection is null 1786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public ArrayDeque(Collection<? extends E> c) { 1802f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson allocateElements(c.size()); 1812f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson addAll(c); 1826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1842f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // The main insertion and extraction methods are addFirst, 1852f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // addLast, pollFirst, pollLast. The other methods are defined in 1862f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // terms of these. 1872f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 1886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1892f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Inserts the specified element at the front of this deque. 1906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 1912f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param e the element to add 1922f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified element is null 1936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void addFirst(E e) { 1952f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (e == null) 196d43b9ef11a1095967a3396b246639b563e1a4128Kenny Root throw new NullPointerException("e == null"); 1972f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[head = (head - 1) & (elements.length - 1)] = e; 1982f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (head == tail) 1992f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson doubleCapacity(); 2006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2032f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Inserts the specified element at the end of this deque. 2042f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 2052f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #add}. 2066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 2072f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param e the element to add 2082f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified element is null 2096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void addLast(E e) { 2112f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (e == null) 212d43b9ef11a1095967a3396b246639b563e1a4128Kenny Root throw new NullPointerException("e == null"); 2132f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[tail] = e; 2142f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if ( (tail = (tail + 1) & (elements.length - 1)) == head) 2152f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson doubleCapacity(); 2166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2192f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Inserts the specified element at the front of this deque. 2206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 2212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param e the element to add 2222f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> (as specified by {@link Deque#offerFirst}) 2232f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified element is null 2246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2252f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean offerFirst(E e) { 2262f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson addFirst(e); 2276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 2286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2312f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Inserts the specified element at the end of this deque. 2326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 2332f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param e the element to add 2342f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> (as specified by {@link Deque#offerLast}) 2352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified element is null 2366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean offerLast(E e) { 2382f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson addLast(e); 2392f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return true; 2406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2432f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NoSuchElementException {@inheritDoc} 2446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2452f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E removeFirst() { 2462f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson E x = pollFirst(); 2472f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (x == null) 2482f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new NoSuchElementException(); 2492f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return x; 2506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2532f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NoSuchElementException {@inheritDoc} 2546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2552f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E removeLast() { 2562f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson E x = pollLast(); 2572f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (x == null) 2582f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new NoSuchElementException(); 2592f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return x; 2606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2622f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E pollFirst() { 2632f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int h = head; 264a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson @SuppressWarnings("unchecked") E result = (E) elements[h]; 265a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // Element is null if deque empty 2662f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (result == null) 2672f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return null; 2682f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[h] = null; // Must null out slot 2692f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson head = (h + 1) & (elements.length - 1); 2702f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return result; 2712f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 2722f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 2732f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E pollLast() { 2742f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int t = (tail - 1) & (elements.length - 1); 275a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson @SuppressWarnings("unchecked") E result = (E) elements[t]; 2762f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (result == null) 2772f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return null; 2782f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[t] = null; 2792f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson tail = t; 2802f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return result; 2816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2842f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NoSuchElementException {@inheritDoc} 2856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2862f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E getFirst() { 287a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson @SuppressWarnings("unchecked") E result = (E) elements[head]; 288a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (result == null) 2892f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new NoSuchElementException(); 290a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return result; 2916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2942f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NoSuchElementException {@inheritDoc} 2956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2962f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E getLast() { 297a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson @SuppressWarnings("unchecked") 298a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson E result = (E) elements[(tail - 1) & (elements.length - 1)]; 299a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (result == null) 3002f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new NoSuchElementException(); 301a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return result; 3022f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 3032f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 3042f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E peekFirst() { 305a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson @SuppressWarnings("unchecked") E result = (E) elements[head]; 306a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson // elements[head] is null if deque empty 307a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return result; 3082f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 3092f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 3102f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E peekLast() { 311a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson @SuppressWarnings("unchecked") 312a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson E result = (E) elements[(tail - 1) & (elements.length - 1)]; 313a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return result; 3146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3172f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Removes the first occurrence of the specified element in this 3182f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * deque (when traversing the deque from head to tail). 3192f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * If the deque does not contain the element, it is unchanged. 3202f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * More formally, removes the first element <tt>e</tt> such that 3212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>o.equals(e)</tt> (if such an element exists). 3222f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns <tt>true</tt> if this deque contained the specified element 3232f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * (or equivalently, if this deque changed as a result of the call). 3246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 3252f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param o element to be removed from this deque, if present 3262f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> if the deque contained the specified element 3276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3282f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean removeFirstOccurrence(Object o) { 3292f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (o == null) 3302f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return false; 3312f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int mask = elements.length - 1; 3322f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int i = head; 333a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Object x; 3342f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson while ( (x = elements[i]) != null) { 3352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (o.equals(x)) { 3362f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson delete(i); 3372f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return true; 3382f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 3392f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson i = (i + 1) & mask; 3402f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 3412f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return false; 3426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3452f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Removes the last occurrence of the specified element in this 3462f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * deque (when traversing the deque from head to tail). 3472f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * If the deque does not contain the element, it is unchanged. 3482f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * More formally, removes the last element <tt>e</tt> such that 3492f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>o.equals(e)</tt> (if such an element exists). 3502f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns <tt>true</tt> if this deque contained the specified element 3512f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * (or equivalently, if this deque changed as a result of the call). 3522f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 3532f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param o element to be removed from this deque, if present 3542f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> if the deque contained the specified element 3552f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 3562f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean removeLastOccurrence(Object o) { 3572f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (o == null) 3582f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return false; 3592f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int mask = elements.length - 1; 3602f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int i = (tail - 1) & mask; 361a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Object x; 3622f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson while ( (x = elements[i]) != null) { 3632f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (o.equals(x)) { 3642f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson delete(i); 3652f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return true; 3662f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 3672f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson i = (i - 1) & mask; 3682f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 3692f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return false; 3706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3722f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // *** Queue methods *** 3732f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 3746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3752f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Inserts the specified element at the end of this deque. 3766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 3772f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #addLast}. 3782f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 3792f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param e the element to add 3802f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> (as specified by {@link Collection#add}) 3812f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified element is null 3826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3832f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean add(E e) { 3842f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson addLast(e); 3852f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return true; 3866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3892f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Inserts the specified element at the end of this deque. 3902f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 3912f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #offerLast}. 3926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 3932f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param e the element to add 3942f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> (as specified by {@link Queue#offer}) 3952f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified element is null 3966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3972f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean offer(E e) { 3982f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return offerLast(e); 3996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 4022f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Retrieves and removes the head of the queue represented by this deque. 4032f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 4042f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * This method differs from {@link #poll poll} only in that it throws an 4052f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * exception if this deque is empty. 4062f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 4072f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #removeFirst}. 4086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 4092f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return the head of the queue represented by this deque 4102f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NoSuchElementException {@inheritDoc} 4116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4122f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E remove() { 4132f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return removeFirst(); 4146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 4172f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Retrieves and removes the head of the queue represented by this deque 4182f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * (in other words, the first element of this deque), or returns 4192f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>null</tt> if this deque is empty. 4202f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 4212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #pollFirst}. 4226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 4232f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return the head of the queue represented by this deque, or 4242f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>null</tt> if this deque is empty 4256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4262f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E poll() { 4272f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return pollFirst(); 4286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 4312f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Retrieves, but does not remove, the head of the queue represented by 4322f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * this deque. This method differs from {@link #peek peek} only in 4332f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * that it throws an exception if this deque is empty. 4346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 4352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #getFirst}. 4362f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 4372f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return the head of the queue represented by this deque 4382f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NoSuchElementException {@inheritDoc} 4396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E element() { 4416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return getFirst(); 4426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 4452f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Retrieves, but does not remove, the head of the queue represented by 4462f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * this deque, or returns <tt>null</tt> if this deque is empty. 4472f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 4482f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #peekFirst}. 4496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 4502f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return the head of the queue represented by this deque, or 4512f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>null</tt> if this deque is empty 4526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4532f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E peek() { 4542f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return peekFirst(); 4556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4572f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // *** Stack methods *** 4582f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 4596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 4602f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Pushes an element onto the stack represented by this deque. In other 4612f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * words, inserts the element at the front of this deque. 4622f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 4632f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #addFirst}. 4646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 4652f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param e the element to push 4662f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified element is null 4676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4682f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public void push(E e) { 4692f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson addFirst(e); 4706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 4732f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Pops an element from the stack represented by this deque. In other 4742f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * words, removes and returns the first element of this deque. 4752f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 4762f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #removeFirst()}. 4776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 4782f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return the element at the front of this deque (which is the top 4792f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * of the stack represented by this deque) 4802f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NoSuchElementException {@inheritDoc} 4816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4822f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E pop() { 4832f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return removeFirst(); 4842f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 4852f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 4862f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private void checkInvariants() { 48767a368573213811c0037cb1b972a0d5fdb3eaf48Elliott Hughes // assert elements[tail] == null; 48867a368573213811c0037cb1b972a0d5fdb3eaf48Elliott Hughes // assert head == tail ? elements[head] == null : 48967a368573213811c0037cb1b972a0d5fdb3eaf48Elliott Hughes // (elements[head] != null && 49067a368573213811c0037cb1b972a0d5fdb3eaf48Elliott Hughes // elements[(tail - 1) & (elements.length - 1)] != null); 49167a368573213811c0037cb1b972a0d5fdb3eaf48Elliott Hughes // assert elements[(head - 1) & (elements.length - 1)] == null; 4926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 4952f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Removes the element at the specified position in the elements array, 4962f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * adjusting head and tail as necessary. This can result in motion of 4972f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * elements backwards or forwards in the array. 4986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 4992f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is called delete rather than remove to emphasize 5002f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * that its semantics differ from those of {@link List#remove(int)}. 5012f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 5022f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return true if elements moved backwards 5036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 5042f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private boolean delete(int i) { 50567a368573213811c0037cb1b972a0d5fdb3eaf48Elliott Hughes //checkInvariants(); 506a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson final Object[] elements = this.elements; 5072f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson final int mask = elements.length - 1; 5082f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson final int h = head; 5092f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson final int t = tail; 5102f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson final int front = (i - h) & mask; 5112f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson final int back = (t - i) & mask; 5126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5132f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // Invariant: head <= i < tail mod circularity 5142f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (front >= ((t - h) & mask)) 5152f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new ConcurrentModificationException(); 5166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5172f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // Optimize for least element motion 5182f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (front < back) { 5192f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (h <= i) { 5202f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, h, elements, h + 1, front); 5212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } else { // Wrap around 5222f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, 0, elements, 1, i); 5232f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[0] = elements[mask]; 5242f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, h, elements, h + 1, mask - h); 5252f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 5262f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[h] = null; 5272f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson head = (h + 1) & mask; 5282f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return false; 5292f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } else { 5302f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (i < t) { // Copy the null tail as well 5312f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, i + 1, elements, i, back); 5322f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson tail = t - 1; 5332f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } else { // Wrap around 5342f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, i + 1, elements, i, mask - i); 5352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[mask] = elements[0]; 5362f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson System.arraycopy(elements, 1, elements, 0, t); 5372f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson tail = (t - 1) & mask; 5382f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 5392f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return true; 5406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5432f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // *** Collection Methods *** 5446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5452f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 5462f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns the number of elements in this deque. 5472f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 5482f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return the number of elements in this deque 5492f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 5502f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public int size() { 5512f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return (tail - head) & (elements.length - 1); 5526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5542f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 5552f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns <tt>true</tt> if this deque contains no elements. 5562f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 5572f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> if this deque contains no elements 5586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 5592f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean isEmpty() { 5602f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return head == tail; 5616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 5642f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns an iterator over the elements in this deque. The elements 5652f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * will be ordered from first (head) to last (tail). This is the same 5662f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * order that elements would be dequeued (via successive calls to 5672f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * {@link #remove} or popped (via successive calls to {@link #pop}). 5686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 5692f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return an iterator over the elements in this deque 5706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 5712f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public Iterator<E> iterator() { 5722f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return new DeqIterator(); 5736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5752f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public Iterator<E> descendingIterator() { 5762f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return new DescendingIterator(); 5776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5792f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private class DeqIterator implements Iterator<E> { 5802f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 5812f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Index of element to be returned by subsequent call to next. 5822f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 5832f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private int cursor = head; 5846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5852f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 5862f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Tail recorded at construction (also in remove), to stop 5872f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * iterator and also to check for comodification. 5882f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 5892f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private int fence = tail; 5906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5912f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 5922f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Index of element returned by most recent call to next. 5932f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Reset to -1 if element is deleted by a call to remove. 5942f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 5952f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private int lastRet = -1; 5966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5972f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean hasNext() { 5982f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return cursor != fence; 5992f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 6006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6012f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E next() { 6022f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (cursor == fence) 6032f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new NoSuchElementException(); 604a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson @SuppressWarnings("unchecked") E result = (E) elements[cursor]; 6052f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // This check doesn't catch all possible comodifications, 6062f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // but does catch the ones that corrupt traversal 6072f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (tail != fence || result == null) 6082f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new ConcurrentModificationException(); 6092f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson lastRet = cursor; 6102f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson cursor = (cursor + 1) & (elements.length - 1); 6112f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return result; 6126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6142f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public void remove() { 6152f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (lastRet < 0) 6162f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new IllegalStateException(); 6172f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (delete(lastRet)) { // if left-shifted, undo increment in next() 6182f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson cursor = (cursor - 1) & (elements.length - 1); 6192f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson fence = tail; 6206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson lastRet = -1; 6226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6252f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private class DescendingIterator implements Iterator<E> { 6262f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /* 6272f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * This class is nearly a mirror-image of DeqIterator, using 6282f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * tail instead of head for initial cursor, and head instead of 6292f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * tail for fence. 6302f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 6312f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private int cursor = tail; 6322f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private int fence = head; 6332f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private int lastRet = -1; 6342f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 6352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean hasNext() { 6362f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return cursor != fence; 6376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6392f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public E next() { 6402f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (cursor == fence) 6412f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new NoSuchElementException(); 6422f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson cursor = (cursor - 1) & (elements.length - 1); 643a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson @SuppressWarnings("unchecked") E result = (E) elements[cursor]; 6442f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (head != fence || result == null) 6452f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new ConcurrentModificationException(); 6462f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson lastRet = cursor; 6472f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return result; 6486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6502f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public void remove() { 6512f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (lastRet < 0) 6522f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new IllegalStateException(); 6532f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (!delete(lastRet)) { 6542f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson cursor = (cursor + 1) & (elements.length - 1); 6552f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson fence = head; 6562f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 6572f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson lastRet = -1; 6582f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 6596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6622f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns <tt>true</tt> if this deque contains the specified element. 6632f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * More formally, returns <tt>true</tt> if and only if this deque contains 6642f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>. 6656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 6662f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param o object to be checked for containment in this deque 6672f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> if this deque contains the specified element 6686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6692f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean contains(Object o) { 6702f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (o == null) 6712f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return false; 6722f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int mask = elements.length - 1; 6732f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int i = head; 674a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Object x; 6752f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson while ( (x = elements[i]) != null) { 6762f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (o.equals(x)) 6772f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return true; 6782f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson i = (i + 1) & mask; 6796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 6816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6842f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Removes a single instance of the specified element from this deque. 6852f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * If the deque does not contain the element, it is unchanged. 6862f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * More formally, removes the first element <tt>e</tt> such that 6872f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>o.equals(e)</tt> (if such an element exists). 6882f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns <tt>true</tt> if this deque contained the specified element 6892f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * (or equivalently, if this deque changed as a result of the call). 6906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 6912f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method is equivalent to {@link #removeFirstOccurrence}. 6922f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 6932f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param o element to be removed from this deque, if present 6942f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> if this deque contained the specified element 6956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6962f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean remove(Object o) { 6972f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return removeFirstOccurrence(o); 6986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7012f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Removes all of the elements from this deque. 7022f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * The deque will be empty after this call returns. 7036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7042f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public void clear() { 7052f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int h = head; 7062f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int t = tail; 7072f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (h != t) { // clear all cells 7082f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson head = tail = 0; 7092f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int i = h; 7102f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int mask = elements.length - 1; 7112f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson do { 7122f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson elements[i] = null; 7132f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson i = (i + 1) & mask; 7142f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } while (i != t); 7156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7192f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns an array containing all of the elements in this deque 7202f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * in proper sequence (from first to last element). 7212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 7222f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>The returned array will be "safe" in that no references to it are 7232f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * maintained by this deque. (In other words, this method must allocate 7242f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * a new array). The caller is thus free to modify the returned array. 7252f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 7262f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This method acts as bridge between array-based and collection-based 7272f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * APIs. 7286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 7292f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return an array containing all of the elements in this deque 7306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public Object[] toArray() { 7322f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return copyElements(new Object[size()]); 7336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7362f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns an array containing all of the elements in this deque in 7372f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * proper sequence (from first to last element); the runtime type of the 7382f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * returned array is that of the specified array. If the deque fits in 7392f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * the specified array, it is returned therein. Otherwise, a new array 7402f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * is allocated with the runtime type of the specified array and the 7412f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * size of this deque. 7426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 7432f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>If this deque fits in the specified array with room to spare 7442f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * (i.e., the array has more elements than this deque), the element in 7452f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * the array immediately following the end of the deque is set to 7462f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>null</tt>. 7472f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 7482f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>Like the {@link #toArray()} method, this method acts as bridge between 7492f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * array-based and collection-based APIs. Further, this method allows 7502f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * precise control over the runtime type of the output array, and may, 7512f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * under certain circumstances, be used to save allocation costs. 7522f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 7532f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>Suppose <tt>x</tt> is a deque known to contain only strings. 7542f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * The following code can be used to dump the deque into a newly 7552f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * allocated array of <tt>String</tt>: 7562f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 757a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 7582f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 7592f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Note that <tt>toArray(new Object[0])</tt> is identical in function to 7602f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>toArray()</tt>. 7612f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 7622f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param a the array into which the elements of the deque are to 7632f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * be stored, if it is big enough; otherwise, a new array of the 7642f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * same runtime type is allocated for this purpose 7652f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return an array containing all of the elements in this deque 7662f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws ArrayStoreException if the runtime type of the specified array 7672f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * is not a supertype of the runtime type of every element in 7682f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * this deque 7692f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified array is null 7706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 771a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson @SuppressWarnings("unchecked") 7722f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public <T> T[] toArray(T[] a) { 7736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson int size = size(); 7742f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (a.length < size) 7752f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson a = (T[])java.lang.reflect.Array.newInstance( 7762f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson a.getClass().getComponentType(), size); 7772f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson copyElements(a); 7782f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (a.length > size) 7792f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson a[size] = null; 7802f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return a; 7816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7832f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // *** Object methods *** 7842f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 7856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7862f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Returns a copy of this deque. 7876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 7882f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return a copy of this deque 7896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7902f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public ArrayDeque<E> clone() { 7912f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson try { 792a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson @SuppressWarnings("unchecked") 7932f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson ArrayDeque<E> result = (ArrayDeque<E>) super.clone(); 7942f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson result.elements = Arrays.copyOf(elements, elements.length); 7952f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return result; 7962f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 7972f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } catch (CloneNotSupportedException e) { 7982f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new AssertionError(); 7992f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 8006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 8016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 8026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 8032f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Appease the serialization gods. 8046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 8052f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson private static final long serialVersionUID = 2340985798034038923L; 8066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 8076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 8082f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Serialize this deque. 8096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 8102f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @serialData The current size (<tt>int</tt>) of the deque, 8112f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * followed by all of its elements (each an object reference) in 8122f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * first-to-last order. 8136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 814a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private void writeObject(java.io.ObjectOutputStream s) 815a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throws java.io.IOException { 8162f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson s.defaultWriteObject(); 8172f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 8182f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // Write out size 8192f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson s.writeInt(size()); 8202f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 8212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // Write out elements in order. 8222f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int mask = elements.length - 1; 8232f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson for (int i = head; i != tail; i = (i + 1) & mask) 8242f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson s.writeObject(elements[i]); 8256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 8266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 8276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 8282f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Deserialize this deque. 8296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 830a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private void readObject(java.io.ObjectInputStream s) 831a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson throws java.io.IOException, ClassNotFoundException { 8322f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson s.defaultReadObject(); 8332f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 8342f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // Read in size and allocate array 8352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson int size = s.readInt(); 8362f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson allocateElements(size); 8372f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson head = 0; 8382f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson tail = size; 8396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 8402f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson // Read in all elements in the proper order. 8412f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson for (int i = 0; i < size; i++) 842a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson elements[i] = s.readObject(); 8432f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 844bf87c56b39383f6b11c36c3cdc93df4b03fed914Brian Carlstrom} 845