1 /* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 3 * 4 * This code is free software; you can redistribute it and/or modify it 5 * under the terms of the GNU General Public License version 2 only, as 6 * published by the Free Software Foundation. Oracle designates this 7 * particular file as subject to the "Classpath" exception as provided 8 * by Oracle in the LICENSE file that accompanied this code. 9 * 10 * This code is distributed in the hope that it will be useful, but WITHOUT 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 13 * version 2 for more details (a copy is included in the LICENSE file that 14 * accompanied this code). 15 * 16 * You should have received a copy of the GNU General Public License version 17 * 2 along with this work; if not, write to the Free Software Foundation, 18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 19 * 20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 21 * or visit www.oracle.com if you need additional information or have any 22 * questions. 23 */ 24 25 /* 26 * This file is available under and governed by the GNU General Public 27 * License version 2 only, as published by the Free Software Foundation. 28 * However, the following notice accompanied the original version of this 29 * file: 30 * 31 * Written by Josh Bloch of Google Inc. and released to the public domain, 32 * as explained at http://creativecommons.org/publicdomain/zero/1.0/. 33 */ 34 35 package java.util; 36 37 import java.io.Serializable; 38 import java.util.function.Consumer; 39 import java.util.function.Predicate; 40 import java.util.function.UnaryOperator; 41 42 /** 43 * Resizable-array implementation of the {@link Deque} interface. Array 44 * deques have no capacity restrictions; they grow as necessary to support 45 * usage. They are not thread-safe; in the absence of external 46 * synchronization, they do not support concurrent access by multiple threads. 47 * Null elements are prohibited. This class is likely to be faster than 48 * {@link Stack} when used as a stack, and faster than {@link LinkedList} 49 * when used as a queue. 50 * 51 * <p>Most {@code ArrayDeque} operations run in amortized constant time. 52 * Exceptions include 53 * {@link #remove(Object) remove}, 54 * {@link #removeFirstOccurrence removeFirstOccurrence}, 55 * {@link #removeLastOccurrence removeLastOccurrence}, 56 * {@link #contains contains}, 57 * {@link #iterator iterator.remove()}, 58 * and the bulk operations, all of which run in linear time. 59 * 60 * <p>The iterators returned by this class's {@link #iterator() iterator} 61 * method are <em>fail-fast</em>: If the deque is modified at any time after 62 * the iterator is created, in any way except through the iterator's own 63 * {@code remove} method, the iterator will generally throw a {@link 64 * ConcurrentModificationException}. Thus, in the face of concurrent 65 * modification, the iterator fails quickly and cleanly, rather than risking 66 * arbitrary, non-deterministic behavior at an undetermined time in the 67 * future. 68 * 69 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed 70 * as it is, generally speaking, impossible to make any hard guarantees in the 71 * presence of unsynchronized concurrent modification. Fail-fast iterators 72 * throw {@code ConcurrentModificationException} on a best-effort basis. 73 * Therefore, it would be wrong to write a program that depended on this 74 * exception for its correctness: <i>the fail-fast behavior of iterators 75 * should be used only to detect bugs.</i> 76 * 77 * <p>This class and its iterator implement all of the 78 * <em>optional</em> methods of the {@link Collection} and {@link 79 * Iterator} interfaces. 80 * 81 * <p>This class is a member of the 82 * <a href="{@docRoot}/java/util/package-summary.html#CollectionsFramework"> 83 * Java Collections Framework</a>. 84 * 85 * @author Josh Bloch and Doug Lea 86 * @param <E> the type of elements held in this deque 87 * @since 1.6 88 */ 89 public class ArrayDeque<E> extends AbstractCollection<E> 90 implements Deque<E>, Cloneable, Serializable 91 { 92 /* 93 * VMs excel at optimizing simple array loops where indices are 94 * incrementing or decrementing over a valid slice, e.g. 95 * 96 * for (int i = start; i < end; i++) ... elements[i] 97 * 98 * Because in a circular array, elements are in general stored in 99 * two disjoint such slices, we help the VM by writing unusual 100 * nested loops for all traversals over the elements. Having only 101 * one hot inner loop body instead of two or three eases human 102 * maintenance and encourages VM loop inlining into the caller. 103 */ 104 105 /** 106 * The array in which the elements of the deque are stored. 107 * All array cells not holding deque elements are always null. 108 * The array always has at least one null slot (at tail). 109 */ 110 transient Object[] elements; 111 112 /** 113 * The index of the element at the head of the deque (which is the 114 * element that would be removed by remove() or pop()); or an 115 * arbitrary number 0 <= head < elements.length equal to tail if 116 * the deque is empty. 117 */ 118 transient int head; 119 120 /** 121 * The index at which the next element would be added to the tail 122 * of the deque (via addLast(E), add(E), or push(E)); 123 * elements[tail] is always null. 124 */ 125 transient int tail; 126 127 /** 128 * The maximum size of array to allocate. 129 * Some VMs reserve some header words in an array. 130 * Attempts to allocate larger arrays may result in 131 * OutOfMemoryError: Requested array size exceeds VM limit 132 */ 133 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 134 135 /** 136 * Increases the capacity of this deque by at least the given amount. 137 * 138 * @param needed the required minimum extra capacity; must be positive 139 */ 140 private void grow(int needed) { 141 // overflow-conscious code 142 final int oldCapacity = elements.length; 143 int newCapacity; 144 // Double capacity if small; else grow by 50% 145 int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1); 146 if (jump < needed 147 || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0) 148 newCapacity = newCapacity(needed, jump); 149 final Object[] es = elements = Arrays.copyOf(elements, newCapacity); 150 // Exceptionally, here tail == head needs to be disambiguated 151 if (tail < head || (tail == head && es[head] != null)) { 152 // wrap around; slide first leg forward to end of array 153 int newSpace = newCapacity - oldCapacity; 154 System.arraycopy(es, head, 155 es, head + newSpace, 156 oldCapacity - head); 157 for (int i = head, to = (head += newSpace); i < to; i++) 158 es[i] = null; 159 } 160 } 161 162 /** Capacity calculation for edge conditions, especially overflow. */ 163 private int newCapacity(int needed, int jump) { 164 final int oldCapacity = elements.length, minCapacity; 165 if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) { 166 if (minCapacity < 0) 167 throw new IllegalStateException("Sorry, deque too big"); 168 return Integer.MAX_VALUE; 169 } 170 if (needed > jump) 171 return minCapacity; 172 return (oldCapacity + jump - MAX_ARRAY_SIZE < 0) 173 ? oldCapacity + jump 174 : MAX_ARRAY_SIZE; 175 } 176 177 /** 178 * Constructs an empty array deque with an initial capacity 179 * sufficient to hold 16 elements. 180 */ 181 public ArrayDeque() { 182 elements = new Object[16]; 183 } 184 185 /** 186 * Constructs an empty array deque with an initial capacity 187 * sufficient to hold the specified number of elements. 188 * 189 * @param numElements lower bound on initial capacity of the deque 190 */ 191 public ArrayDeque(int numElements) { 192 elements = 193 new Object[(numElements < 1) ? 1 : 194 (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE : 195 numElements + 1]; 196 } 197 198 /** 199 * Constructs a deque containing the elements of the specified 200 * collection, in the order they are returned by the collection's 201 * iterator. (The first element returned by the collection's 202 * iterator becomes the first element, or <i>front</i> of the 203 * deque.) 204 * 205 * @param c the collection whose elements are to be placed into the deque 206 * @throws NullPointerException if the specified collection is null 207 */ 208 public ArrayDeque(Collection<? extends E> c) { 209 this(c.size()); 210 addAll(c); 211 } 212 213 /** 214 * Increments i, mod modulus. 215 * Precondition and postcondition: 0 <= i < modulus. 216 */ 217 static final int inc(int i, int modulus) { 218 if (++i >= modulus) i = 0; 219 return i; 220 } 221 222 /** 223 * Decrements i, mod modulus. 224 * Precondition and postcondition: 0 <= i < modulus. 225 */ 226 static final int dec(int i, int modulus) { 227 if (--i < 0) i = modulus - 1; 228 return i; 229 } 230 231 /** 232 * Circularly adds the given distance to index i, mod modulus. 233 * Precondition: 0 <= i < modulus, 0 <= distance <= modulus. 234 * @return index 0 <= i < modulus 235 */ 236 static final int add(int i, int distance, int modulus) { 237 if ((i += distance) - modulus >= 0) i -= modulus; 238 return i; 239 } 240 241 /** 242 * Subtracts j from i, mod modulus. 243 * Index i must be logically ahead of index j. 244 * Precondition: 0 <= i < modulus, 0 <= j < modulus. 245 * @return the "circular distance" from j to i; corner case i == j 246 * is disambiguated to "empty", returning 0. 247 */ 248 static final int sub(int i, int j, int modulus) { 249 if ((i -= j) < 0) i += modulus; 250 return i; 251 } 252 253 /** 254 * Returns element at array index i. 255 * This is a slight abuse of generics, accepted by javac. 256 */ 257 @SuppressWarnings("unchecked") 258 static final <E> E elementAt(Object[] es, int i) { 259 return (E) es[i]; 260 } 261 262 /** 263 * A version of elementAt that checks for null elements. 264 * This check doesn't catch all possible comodifications, 265 * but does catch ones that corrupt traversal. 266 */ 267 static final <E> E nonNullElementAt(Object[] es, int i) { 268 @SuppressWarnings("unchecked") E e = (E) es[i]; 269 if (e == null) 270 throw new ConcurrentModificationException(); 271 return e; 272 } 273 274 // The main insertion and extraction methods are addFirst, 275 // addLast, pollFirst, pollLast. The other methods are defined in 276 // terms of these. 277 278 /** 279 * Inserts the specified element at the front of this deque. 280 * 281 * @param e the element to add 282 * @throws NullPointerException if the specified element is null 283 */ 284 public void addFirst(E e) { 285 if (e == null) 286 throw new NullPointerException(); 287 final Object[] es = elements; 288 es[head = dec(head, es.length)] = e; 289 if (head == tail) 290 grow(1); 291 } 292 293 /** 294 * Inserts the specified element at the end of this deque. 295 * 296 * <p>This method is equivalent to {@link #add}. 297 * 298 * @param e the element to add 299 * @throws NullPointerException if the specified element is null 300 */ 301 public void addLast(E e) { 302 if (e == null) 303 throw new NullPointerException(); 304 final Object[] es = elements; 305 es[tail] = e; 306 if (head == (tail = inc(tail, es.length))) 307 grow(1); 308 } 309 310 /** 311 * Adds all of the elements in the specified collection at the end 312 * of this deque, as if by calling {@link #addLast} on each one, 313 * in the order that they are returned by the collection's iterator. 314 * 315 * @param c the elements to be inserted into this deque 316 * @return {@code true} if this deque changed as a result of the call 317 * @throws NullPointerException if the specified collection or any 318 * of its elements are null 319 */ 320 public boolean addAll(Collection<? extends E> c) { 321 final int s, needed; 322 if ((needed = (s = size()) + c.size() + 1 - elements.length) > 0) 323 grow(needed); 324 c.forEach(this::addLast); 325 return size() > s; 326 } 327 328 /** 329 * Inserts the specified element at the front of this deque. 330 * 331 * @param e the element to add 332 * @return {@code true} (as specified by {@link Deque#offerFirst}) 333 * @throws NullPointerException if the specified element is null 334 */ 335 public boolean offerFirst(E e) { 336 addFirst(e); 337 return true; 338 } 339 340 /** 341 * Inserts the specified element at the end of this deque. 342 * 343 * @param e the element to add 344 * @return {@code true} (as specified by {@link Deque#offerLast}) 345 * @throws NullPointerException if the specified element is null 346 */ 347 public boolean offerLast(E e) { 348 addLast(e); 349 return true; 350 } 351 352 /** 353 * @throws NoSuchElementException {@inheritDoc} 354 */ 355 public E removeFirst() { 356 E e = pollFirst(); 357 if (e == null) 358 throw new NoSuchElementException(); 359 return e; 360 } 361 362 /** 363 * @throws NoSuchElementException {@inheritDoc} 364 */ 365 public E removeLast() { 366 E e = pollLast(); 367 if (e == null) 368 throw new NoSuchElementException(); 369 return e; 370 } 371 372 public E pollFirst() { 373 final Object[] es; 374 final int h; 375 E e = elementAt(es = elements, h = head); 376 if (e != null) { 377 es[h] = null; 378 head = inc(h, es.length); 379 } 380 return e; 381 } 382 383 public E pollLast() { 384 final Object[] es; 385 final int t; 386 E e = elementAt(es = elements, t = dec(tail, es.length)); 387 if (e != null) 388 es[tail = t] = null; 389 return e; 390 } 391 392 /** 393 * @throws NoSuchElementException {@inheritDoc} 394 */ 395 public E getFirst() { 396 E e = elementAt(elements, head); 397 if (e == null) 398 throw new NoSuchElementException(); 399 return e; 400 } 401 402 /** 403 * @throws NoSuchElementException {@inheritDoc} 404 */ 405 public E getLast() { 406 final Object[] es = elements; 407 E e = elementAt(es, dec(tail, es.length)); 408 if (e == null) 409 throw new NoSuchElementException(); 410 return e; 411 } 412 413 public E peekFirst() { 414 return elementAt(elements, head); 415 } 416 417 public E peekLast() { 418 final Object[] es; 419 return elementAt(es = elements, dec(tail, es.length)); 420 } 421 422 /** 423 * Removes the first occurrence of the specified element in this 424 * deque (when traversing the deque from head to tail). 425 * If the deque does not contain the element, it is unchanged. 426 * More formally, removes the first element {@code e} such that 427 * {@code o.equals(e)} (if such an element exists). 428 * Returns {@code true} if this deque contained the specified element 429 * (or equivalently, if this deque changed as a result of the call). 430 * 431 * @param o element to be removed from this deque, if present 432 * @return {@code true} if the deque contained the specified element 433 */ 434 public boolean removeFirstOccurrence(Object o) { 435 if (o != null) { 436 final Object[] es = elements; 437 for (int i = head, end = tail, to = (i <= end) ? end : es.length; 438 ; i = 0, to = end) { 439 for (; i < to; i++) 440 if (o.equals(es[i])) { 441 delete(i); 442 return true; 443 } 444 if (to == end) break; 445 } 446 } 447 return false; 448 } 449 450 /** 451 * Removes the last occurrence of the specified element in this 452 * deque (when traversing the deque from head to tail). 453 * If the deque does not contain the element, it is unchanged. 454 * More formally, removes the last element {@code e} such that 455 * {@code o.equals(e)} (if such an element exists). 456 * Returns {@code true} if this deque contained the specified element 457 * (or equivalently, if this deque changed as a result of the call). 458 * 459 * @param o element to be removed from this deque, if present 460 * @return {@code true} if the deque contained the specified element 461 */ 462 public boolean removeLastOccurrence(Object o) { 463 if (o != null) { 464 final Object[] es = elements; 465 for (int i = tail, end = head, to = (i >= end) ? end : 0; 466 ; i = es.length, to = end) { 467 for (i--; i > to - 1; i--) 468 if (o.equals(es[i])) { 469 delete(i); 470 return true; 471 } 472 if (to == end) break; 473 } 474 } 475 return false; 476 } 477 478 // *** Queue methods *** 479 480 /** 481 * Inserts the specified element at the end of this deque. 482 * 483 * <p>This method is equivalent to {@link #addLast}. 484 * 485 * @param e the element to add 486 * @return {@code true} (as specified by {@link Collection#add}) 487 * @throws NullPointerException if the specified element is null 488 */ 489 public boolean add(E e) { 490 addLast(e); 491 return true; 492 } 493 494 /** 495 * Inserts the specified element at the end of this deque. 496 * 497 * <p>This method is equivalent to {@link #offerLast}. 498 * 499 * @param e the element to add 500 * @return {@code true} (as specified by {@link Queue#offer}) 501 * @throws NullPointerException if the specified element is null 502 */ 503 public boolean offer(E e) { 504 return offerLast(e); 505 } 506 507 /** 508 * Retrieves and removes the head of the queue represented by this deque. 509 * 510 * This method differs from {@link #poll() poll()} only in that it 511 * throws an exception if this deque is empty. 512 * 513 * <p>This method is equivalent to {@link #removeFirst}. 514 * 515 * @return the head of the queue represented by this deque 516 * @throws NoSuchElementException {@inheritDoc} 517 */ 518 public E remove() { 519 return removeFirst(); 520 } 521 522 /** 523 * Retrieves and removes the head of the queue represented by this deque 524 * (in other words, the first element of this deque), or returns 525 * {@code null} if this deque is empty. 526 * 527 * <p>This method is equivalent to {@link #pollFirst}. 528 * 529 * @return the head of the queue represented by this deque, or 530 * {@code null} if this deque is empty 531 */ 532 public E poll() { 533 return pollFirst(); 534 } 535 536 /** 537 * Retrieves, but does not remove, the head of the queue represented by 538 * this deque. This method differs from {@link #peek peek} only in 539 * that it throws an exception if this deque is empty. 540 * 541 * <p>This method is equivalent to {@link #getFirst}. 542 * 543 * @return the head of the queue represented by this deque 544 * @throws NoSuchElementException {@inheritDoc} 545 */ 546 public E element() { 547 return getFirst(); 548 } 549 550 /** 551 * Retrieves, but does not remove, the head of the queue represented by 552 * this deque, or returns {@code null} if this deque is empty. 553 * 554 * <p>This method is equivalent to {@link #peekFirst}. 555 * 556 * @return the head of the queue represented by this deque, or 557 * {@code null} if this deque is empty 558 */ 559 public E peek() { 560 return peekFirst(); 561 } 562 563 // *** Stack methods *** 564 565 /** 566 * Pushes an element onto the stack represented by this deque. In other 567 * words, inserts the element at the front of this deque. 568 * 569 * <p>This method is equivalent to {@link #addFirst}. 570 * 571 * @param e the element to push 572 * @throws NullPointerException if the specified element is null 573 */ 574 public void push(E e) { 575 addFirst(e); 576 } 577 578 /** 579 * Pops an element from the stack represented by this deque. In other 580 * words, removes and returns the first element of this deque. 581 * 582 * <p>This method is equivalent to {@link #removeFirst()}. 583 * 584 * @return the element at the front of this deque (which is the top 585 * of the stack represented by this deque) 586 * @throws NoSuchElementException {@inheritDoc} 587 */ 588 public E pop() { 589 return removeFirst(); 590 } 591 592 /** 593 * Removes the element at the specified position in the elements array. 594 * This can result in forward or backwards motion of array elements. 595 * We optimize for least element motion. 596 * 597 * <p>This method is called delete rather than remove to emphasize 598 * that its semantics differ from those of {@link List#remove(int)}. 599 * 600 * @return true if elements near tail moved backwards 601 */ 602 boolean delete(int i) { 603 final Object[] es = elements; 604 final int capacity = es.length; 605 final int h, t; 606 // number of elements before to-be-deleted elt 607 final int front = sub(i, h = head, capacity); 608 // number of elements after to-be-deleted elt 609 final int back = sub(t = tail, i, capacity) - 1; 610 if (front < back) { 611 // move front elements forwards 612 if (h <= i) { 613 System.arraycopy(es, h, es, h + 1, front); 614 } else { // Wrap around 615 System.arraycopy(es, 0, es, 1, i); 616 es[0] = es[capacity - 1]; 617 System.arraycopy(es, h, es, h + 1, front - (i + 1)); 618 } 619 es[h] = null; 620 head = inc(h, capacity); 621 return false; 622 } else { 623 // move back elements backwards 624 tail = dec(t, capacity); 625 if (i <= tail) { 626 System.arraycopy(es, i + 1, es, i, back); 627 } else { // Wrap around 628 System.arraycopy(es, i + 1, es, i, capacity - (i + 1)); 629 es[capacity - 1] = es[0]; 630 System.arraycopy(es, 1, es, 0, t - 1); 631 } 632 es[tail] = null; 633 return true; 634 } 635 } 636 637 // *** Collection Methods *** 638 639 /** 640 * Returns the number of elements in this deque. 641 * 642 * @return the number of elements in this deque 643 */ 644 public int size() { 645 return sub(tail, head, elements.length); 646 } 647 648 /** 649 * Returns {@code true} if this deque contains no elements. 650 * 651 * @return {@code true} if this deque contains no elements 652 */ 653 public boolean isEmpty() { 654 return head == tail; 655 } 656 657 /** 658 * Returns an iterator over the elements in this deque. The elements 659 * will be ordered from first (head) to last (tail). This is the same 660 * order that elements would be dequeued (via successive calls to 661 * {@link #remove} or popped (via successive calls to {@link #pop}). 662 * 663 * @return an iterator over the elements in this deque 664 */ 665 public Iterator<E> iterator() { 666 return new DeqIterator(); 667 } 668 669 public Iterator<E> descendingIterator() { 670 return new DescendingIterator(); 671 } 672 673 private class DeqIterator implements Iterator<E> { 674 /** Index of element to be returned by subsequent call to next. */ 675 int cursor; 676 677 /** Number of elements yet to be returned. */ 678 int remaining = size(); 679 680 /** 681 * Index of element returned by most recent call to next. 682 * Reset to -1 if element is deleted by a call to remove. 683 */ 684 int lastRet = -1; 685 686 DeqIterator() { cursor = head; } 687 688 public final boolean hasNext() { 689 return remaining > 0; 690 } 691 692 public E next() { 693 if (remaining <= 0) 694 throw new NoSuchElementException(); 695 final Object[] es = elements; 696 E e = nonNullElementAt(es, cursor); 697 cursor = inc(lastRet = cursor, es.length); 698 remaining--; 699 return e; 700 } 701 702 void postDelete(boolean leftShifted) { 703 if (leftShifted) 704 cursor = dec(cursor, elements.length); 705 } 706 707 public final void remove() { 708 if (lastRet < 0) 709 throw new IllegalStateException(); 710 postDelete(delete(lastRet)); 711 lastRet = -1; 712 } 713 714 public void forEachRemaining(Consumer<? super E> action) { 715 Objects.requireNonNull(action); 716 int r; 717 if ((r = remaining) <= 0) 718 return; 719 remaining = 0; 720 final Object[] es = elements; 721 if (es[cursor] == null || sub(tail, cursor, es.length) != r) 722 throw new ConcurrentModificationException(); 723 for (int i = cursor, end = tail, to = (i <= end) ? end : es.length; 724 ; i = 0, to = end) { 725 for (; i < to; i++) 726 action.accept(elementAt(es, i)); 727 if (to == end) { 728 if (end != tail) 729 throw new ConcurrentModificationException(); 730 lastRet = dec(end, es.length); 731 break; 732 } 733 } 734 } 735 } 736 737 private class DescendingIterator extends DeqIterator { 738 DescendingIterator() { cursor = dec(tail, elements.length); } 739 740 public final E next() { 741 if (remaining <= 0) 742 throw new NoSuchElementException(); 743 final Object[] es = elements; 744 E e = nonNullElementAt(es, cursor); 745 cursor = dec(lastRet = cursor, es.length); 746 remaining--; 747 return e; 748 } 749 750 void postDelete(boolean leftShifted) { 751 if (!leftShifted) 752 cursor = inc(cursor, elements.length); 753 } 754 755 public final void forEachRemaining(Consumer<? super E> action) { 756 Objects.requireNonNull(action); 757 int r; 758 if ((r = remaining) <= 0) 759 return; 760 remaining = 0; 761 final Object[] es = elements; 762 if (es[cursor] == null || sub(cursor, head, es.length) + 1 != r) 763 throw new ConcurrentModificationException(); 764 for (int i = cursor, end = head, to = (i >= end) ? end : 0; 765 ; i = es.length - 1, to = end) { 766 // hotspot generates faster code than for: i >= to ! 767 for (; i > to - 1; i--) 768 action.accept(elementAt(es, i)); 769 if (to == end) { 770 if (end != head) 771 throw new ConcurrentModificationException(); 772 lastRet = end; 773 break; 774 } 775 } 776 } 777 } 778 779 /** 780 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em> 781 * and <em>fail-fast</em> {@link Spliterator} over the elements in this 782 * deque. 783 * 784 * <p>The {@code Spliterator} reports {@link Spliterator#SIZED}, 785 * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and 786 * {@link Spliterator#NONNULL}. Overriding implementations should document 787 * the reporting of additional characteristic values. 788 * 789 * @return a {@code Spliterator} over the elements in this deque 790 * @since 1.8 791 */ 792 public Spliterator<E> spliterator() { 793 return new DeqSpliterator(); 794 } 795 796 final class DeqSpliterator implements Spliterator<E> { 797 private int fence; // -1 until first use 798 private int cursor; // current index, modified on traverse/split 799 800 /** Constructs late-binding spliterator over all elements. */ 801 DeqSpliterator() { 802 this.fence = -1; 803 } 804 805 /** Constructs spliterator over the given range. */ 806 DeqSpliterator(int origin, int fence) { 807 // assert 0 <= origin && origin < elements.length; 808 // assert 0 <= fence && fence < elements.length; 809 this.cursor = origin; 810 this.fence = fence; 811 } 812 813 /** Ensures late-binding initialization; then returns fence. */ 814 private int getFence() { // force initialization 815 int t; 816 if ((t = fence) < 0) { 817 t = fence = tail; 818 cursor = head; 819 } 820 return t; 821 } 822 823 public DeqSpliterator trySplit() { 824 final Object[] es = elements; 825 final int i, n; 826 return ((n = sub(getFence(), i = cursor, es.length) >> 1) <= 0) 827 ? null 828 : new DeqSpliterator(i, cursor = add(i, n, es.length)); 829 } 830 831 public void forEachRemaining(Consumer<? super E> action) { 832 if (action == null) 833 throw new NullPointerException(); 834 final int end = getFence(), cursor = this.cursor; 835 final Object[] es = elements; 836 if (cursor != end) { 837 this.cursor = end; 838 // null check at both ends of range is sufficient 839 if (es[cursor] == null || es[dec(end, es.length)] == null) 840 throw new ConcurrentModificationException(); 841 for (int i = cursor, to = (i <= end) ? end : es.length; 842 ; i = 0, to = end) { 843 for (; i < to; i++) 844 action.accept(elementAt(es, i)); 845 if (to == end) break; 846 } 847 } 848 } 849 850 public boolean tryAdvance(Consumer<? super E> action) { 851 Objects.requireNonNull(action); 852 final Object[] es = elements; 853 if (fence < 0) { fence = tail; cursor = head; } // late-binding 854 final int i; 855 if ((i = cursor) == fence) 856 return false; 857 E e = nonNullElementAt(es, i); 858 cursor = inc(i, es.length); 859 action.accept(e); 860 return true; 861 } 862 863 public long estimateSize() { 864 return sub(getFence(), cursor, elements.length); 865 } 866 867 public int characteristics() { 868 return Spliterator.NONNULL 869 | Spliterator.ORDERED 870 | Spliterator.SIZED 871 | Spliterator.SUBSIZED; 872 } 873 } 874 875 /** 876 * @throws NullPointerException {@inheritDoc} 877 */ 878 public void forEach(Consumer<? super E> action) { 879 Objects.requireNonNull(action); 880 final Object[] es = elements; 881 for (int i = head, end = tail, to = (i <= end) ? end : es.length; 882 ; i = 0, to = end) { 883 for (; i < to; i++) 884 action.accept(elementAt(es, i)); 885 if (to == end) { 886 if (end != tail) throw new ConcurrentModificationException(); 887 break; 888 } 889 } 890 } 891 892 /** 893 * @throws NullPointerException {@inheritDoc} 894 */ 895 public boolean removeIf(Predicate<? super E> filter) { 896 Objects.requireNonNull(filter); 897 return bulkRemove(filter); 898 } 899 900 /** 901 * @throws NullPointerException {@inheritDoc} 902 */ 903 public boolean removeAll(Collection<?> c) { 904 Objects.requireNonNull(c); 905 return bulkRemove(e -> c.contains(e)); 906 } 907 908 /** 909 * @throws NullPointerException {@inheritDoc} 910 */ 911 public boolean retainAll(Collection<?> c) { 912 Objects.requireNonNull(c); 913 return bulkRemove(e -> !c.contains(e)); 914 } 915 916 /** Implementation of bulk remove methods. */ 917 private boolean bulkRemove(Predicate<? super E> filter) { 918 final Object[] es = elements; 919 // Optimize for initial run of survivors 920 for (int i = head, end = tail, to = (i <= end) ? end : es.length; 921 ; i = 0, to = end) { 922 for (; i < to; i++) 923 if (filter.test(elementAt(es, i))) 924 return bulkRemoveModified(filter, i); 925 if (to == end) { 926 if (end != tail) throw new ConcurrentModificationException(); 927 break; 928 } 929 } 930 return false; 931 } 932 933 // A tiny bit set implementation 934 935 private static long[] nBits(int n) { 936 return new long[((n - 1) >> 6) + 1]; 937 } 938 private static void setBit(long[] bits, int i) { 939 bits[i >> 6] |= 1L << i; 940 } 941 private static boolean isClear(long[] bits, int i) { 942 return (bits[i >> 6] & (1L << i)) == 0; 943 } 944 945 /** 946 * Helper for bulkRemove, in case of at least one deletion. 947 * Tolerate predicates that reentrantly access the collection for 948 * read (but writers still get CME), so traverse once to find 949 * elements to delete, a second pass to physically expunge. 950 * 951 * @param beg valid index of first element to be deleted 952 */ 953 private boolean bulkRemoveModified( 954 Predicate<? super E> filter, final int beg) { 955 final Object[] es = elements; 956 final int capacity = es.length; 957 final int end = tail; 958 final long[] deathRow = nBits(sub(end, beg, capacity)); 959 deathRow[0] = 1L; // set bit 0 960 for (int i = beg + 1, to = (i <= end) ? end : es.length, k = beg; 961 ; i = 0, to = end, k -= capacity) { 962 for (; i < to; i++) 963 if (filter.test(elementAt(es, i))) 964 setBit(deathRow, i - k); 965 if (to == end) break; 966 } 967 // a two-finger traversal, with hare i reading, tortoise w writing 968 int w = beg; 969 for (int i = beg + 1, to = (i <= end) ? end : es.length, k = beg; 970 ; w = 0) { // w rejoins i on second leg 971 // In this loop, i and w are on the same leg, with i > w 972 for (; i < to; i++) 973 if (isClear(deathRow, i - k)) 974 es[w++] = es[i]; 975 if (to == end) break; 976 // In this loop, w is on the first leg, i on the second 977 for (i = 0, to = end, k -= capacity; i < to && w < capacity; i++) 978 if (isClear(deathRow, i - k)) 979 es[w++] = es[i]; 980 if (i >= to) { 981 if (w == capacity) w = 0; // "corner" case 982 break; 983 } 984 } 985 if (end != tail) throw new ConcurrentModificationException(); 986 circularClear(es, tail = w, end); 987 return true; 988 } 989 990 /** 991 * Returns {@code true} if this deque contains the specified element. 992 * More formally, returns {@code true} if and only if this deque contains 993 * at least one element {@code e} such that {@code o.equals(e)}. 994 * 995 * @param o object to be checked for containment in this deque 996 * @return {@code true} if this deque contains the specified element 997 */ 998 public boolean contains(Object o) { 999 if (o != null) { 1000 final Object[] es = elements; 1001 for (int i = head, end = tail, to = (i <= end) ? end : es.length; 1002 ; i = 0, to = end) { 1003 for (; i < to; i++) 1004 if (o.equals(es[i])) 1005 return true; 1006 if (to == end) break; 1007 } 1008 } 1009 return false; 1010 } 1011 1012 /** 1013 * Removes a single instance of the specified element from this deque. 1014 * If the deque does not contain the element, it is unchanged. 1015 * More formally, removes the first element {@code e} such that 1016 * {@code o.equals(e)} (if such an element exists). 1017 * Returns {@code true} if this deque contained the specified element 1018 * (or equivalently, if this deque changed as a result of the call). 1019 * 1020 * <p>This method is equivalent to {@link #removeFirstOccurrence(Object)}. 1021 * 1022 * @param o element to be removed from this deque, if present 1023 * @return {@code true} if this deque contained the specified element 1024 */ 1025 public boolean remove(Object o) { 1026 return removeFirstOccurrence(o); 1027 } 1028 1029 /** 1030 * Removes all of the elements from this deque. 1031 * The deque will be empty after this call returns. 1032 */ 1033 public void clear() { 1034 circularClear(elements, head, tail); 1035 head = tail = 0; 1036 } 1037 1038 /** 1039 * Nulls out slots starting at array index i, upto index end. 1040 * Condition i == end means "empty" - nothing to do. 1041 */ 1042 private static void circularClear(Object[] es, int i, int end) { 1043 // assert 0 <= i && i < es.length; 1044 // assert 0 <= end && end < es.length; 1045 for (int to = (i <= end) ? end : es.length; 1046 ; i = 0, to = end) { 1047 for (; i < to; i++) es[i] = null; 1048 if (to == end) break; 1049 } 1050 } 1051 1052 /** 1053 * Returns an array containing all of the elements in this deque 1054 * in proper sequence (from first to last element). 1055 * 1056 * <p>The returned array will be "safe" in that no references to it are 1057 * maintained by this deque. (In other words, this method must allocate 1058 * a new array). The caller is thus free to modify the returned array. 1059 * 1060 * <p>This method acts as bridge between array-based and collection-based 1061 * APIs. 1062 * 1063 * @return an array containing all of the elements in this deque 1064 */ 1065 public Object[] toArray() { 1066 return toArray(Object[].class); 1067 } 1068 1069 private <T> T[] toArray(Class<T[]> klazz) { 1070 final Object[] es = elements; 1071 final T[] a; 1072 final int head = this.head, tail = this.tail, end; 1073 if ((end = tail + ((head <= tail) ? 0 : es.length)) >= 0) { 1074 // Uses null extension feature of copyOfRange 1075 a = Arrays.copyOfRange(es, head, end, klazz); 1076 } else { 1077 // integer overflow! 1078 a = Arrays.copyOfRange(es, 0, end - head, klazz); 1079 System.arraycopy(es, head, a, 0, es.length - head); 1080 } 1081 if (end != tail) 1082 System.arraycopy(es, 0, a, es.length - head, tail); 1083 return a; 1084 } 1085 1086 /** 1087 * Returns an array containing all of the elements in this deque in 1088 * proper sequence (from first to last element); the runtime type of the 1089 * returned array is that of the specified array. If the deque fits in 1090 * the specified array, it is returned therein. Otherwise, a new array 1091 * is allocated with the runtime type of the specified array and the 1092 * size of this deque. 1093 * 1094 * <p>If this deque fits in the specified array with room to spare 1095 * (i.e., the array has more elements than this deque), the element in 1096 * the array immediately following the end of the deque is set to 1097 * {@code null}. 1098 * 1099 * <p>Like the {@link #toArray()} method, this method acts as bridge between 1100 * array-based and collection-based APIs. Further, this method allows 1101 * precise control over the runtime type of the output array, and may, 1102 * under certain circumstances, be used to save allocation costs. 1103 * 1104 * <p>Suppose {@code x} is a deque known to contain only strings. 1105 * The following code can be used to dump the deque into a newly 1106 * allocated array of {@code String}: 1107 * 1108 * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 1109 * 1110 * Note that {@code toArray(new Object[0])} is identical in function to 1111 * {@code toArray()}. 1112 * 1113 * @param a the array into which the elements of the deque are to 1114 * be stored, if it is big enough; otherwise, a new array of the 1115 * same runtime type is allocated for this purpose 1116 * @return an array containing all of the elements in this deque 1117 * @throws ArrayStoreException if the runtime type of the specified array 1118 * is not a supertype of the runtime type of every element in 1119 * this deque 1120 * @throws NullPointerException if the specified array is null 1121 */ 1122 @SuppressWarnings("unchecked") 1123 public <T> T[] toArray(T[] a) { 1124 final int size; 1125 if ((size = size()) > a.length) 1126 return toArray((Class<T[]>) a.getClass()); 1127 final Object[] es = elements; 1128 for (int i = head, j = 0, len = Math.min(size, es.length - i); 1129 ; i = 0, len = tail) { 1130 System.arraycopy(es, i, a, j, len); 1131 if ((j += len) == size) break; 1132 } 1133 if (size < a.length) 1134 a[size] = null; 1135 return a; 1136 } 1137 1138 // *** Object methods *** 1139 1140 /** 1141 * Returns a copy of this deque. 1142 * 1143 * @return a copy of this deque 1144 */ 1145 public ArrayDeque<E> clone() { 1146 try { 1147 @SuppressWarnings("unchecked") 1148 ArrayDeque<E> result = (ArrayDeque<E>) super.clone(); 1149 result.elements = Arrays.copyOf(elements, elements.length); 1150 return result; 1151 } catch (CloneNotSupportedException e) { 1152 throw new AssertionError(); 1153 } 1154 } 1155 1156 private static final long serialVersionUID = 2340985798034038923L; 1157 1158 /** 1159 * Saves this deque to a stream (that is, serializes it). 1160 * 1161 * @param s the stream 1162 * @throws java.io.IOException if an I/O error occurs 1163 * @serialData The current size ({@code int}) of the deque, 1164 * followed by all of its elements (each an object reference) in 1165 * first-to-last order. 1166 */ 1167 private void writeObject(java.io.ObjectOutputStream s) 1168 throws java.io.IOException { 1169 s.defaultWriteObject(); 1170 1171 // Write out size 1172 s.writeInt(size()); 1173 1174 // Write out elements in order. 1175 final Object[] es = elements; 1176 for (int i = head, end = tail, to = (i <= end) ? end : es.length; 1177 ; i = 0, to = end) { 1178 for (; i < to; i++) 1179 s.writeObject(es[i]); 1180 if (to == end) break; 1181 } 1182 } 1183 1184 /** 1185 * Reconstitutes this deque from a stream (that is, deserializes it). 1186 * @param s the stream 1187 * @throws ClassNotFoundException if the class of a serialized object 1188 * could not be found 1189 * @throws java.io.IOException if an I/O error occurs 1190 */ 1191 private void readObject(java.io.ObjectInputStream s) 1192 throws java.io.IOException, ClassNotFoundException { 1193 s.defaultReadObject(); 1194 1195 // Read in size and allocate array 1196 int size = s.readInt(); 1197 elements = new Object[size + 1]; 1198 this.tail = size; 1199 1200 // Read in all elements in the proper order. 1201 for (int i = 0; i < size; i++) 1202 elements[i] = s.readObject(); 1203 } 1204 1205 /** debugging */ 1206 void checkInvariants() { 1207 // Use head and tail fields with empty slot at tail strategy. 1208 // head == tail disambiguates to "empty". 1209 try { 1210 int capacity = elements.length; 1211 // assert 0 <= head && head < capacity; 1212 // assert 0 <= tail && tail < capacity; 1213 // assert capacity > 0; 1214 // assert size() < capacity; 1215 // assert head == tail || elements[head] != null; 1216 // assert elements[tail] == null; 1217 // assert head == tail || elements[dec(tail, capacity)] != null; 1218 } catch (Throwable t) { 1219 System.err.printf("head=%d tail=%d capacity=%d%n", 1220 head, tail, elements.length); 1221 System.err.printf("elements=%s%n", 1222 Arrays.toString(elements)); 1223 throw t; 1224 } 1225 } 1226 1227 }