1 /*
2 * Hunt - A refined core library for D programming language.
3 *
4 * Copyright (C) 2018-2019 HuntLabs
5 *
6 * Website: https://www.huntlabs.net/
7 *
8 * Licensed under the Apache-2.0 License.
9 *
10 */11 12 modulehunt.collection.ArrayDeque;
13 14 /**
15 * Resizable-array implementation of the {@link Deque} interface. Array
16 * deques have no capacity restrictions; they grow as necessary to support
17 * usage. They are not thread-safe; in the absence of external
18 * synchronization, they do not support concurrent access by multiple threads.
19 * Null elements are prohibited. This class is likely to be faster than
20 * {@link Stack} when used as a stack, and faster than {@link LinkedList}
21 * when used as a queue.
22 *
23 * <p>Most {@code ArrayDeque} operations run in amortized constant time.
24 * Exceptions include {@link #remove(Object) remove}, {@link
25 * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
26 * removeLastOccurrence}, {@link #contains contains}, {@link #iterator
27 * iterator.remove()}, and the bulk operations, all of which run in linear
28 * time.
29 *
30 * <p>The iterators returned by this class's {@code iterator} method are
31 * <i>fail-fast</i>: If the deque is modified at any time after the iterator
32 * is created, in any way except through the iterator's own {@code remove}
33 * method, the iterator will generally throw a {@link
34 * ConcurrentModificationException}. Thus, in the face of concurrent
35 * modification, the iterator fails quickly and cleanly, rather than risking
36 * arbitrary, non-deterministic behavior at an undetermined time in the
37 * future.
38 *
39 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
40 * as it is, generally speaking, impossible to make any hard guarantees in the
41 * presence of unsynchronized concurrent modification. Fail-fast iterators
42 * throw {@code ConcurrentModificationException} on a best-effort basis.
43 * Therefore, it would be wrong to write a program that depended on this
44 * exception for its correctness: <i>the fail-fast behavior of iterators
45 * should be used only to detect bugs.</i>
46 *
47 * <p>This class and its iterator implement all of the
48 * <em>optional</em> methods of the {@link Collection} and {@link
49 * Iterator} interfaces.
50 *
51 * <p>This class is a member of the
52 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
53 * Java Collections Framework</a>.
54 *
55 * @author Josh Bloch and Doug Lea
56 * @param !E the type of elements held in this collection
57 */58 // class ArrayDeque(E) : AbstractCollection!E59 // , Deque!E, Cloneable, Serializable60 // {61 // /**62 // * The array in which the elements of the deque are stored.63 // * The capacity of the deque is the length of this array, which is64 // * always a power of two. The array is never allowed to become65 // * full, except transiently within an addX method where it is66 // * resized (see doubleCapacity) immediately upon becoming full,67 // * thus avoiding head and tail wrapping around to equal each68 // * other. We also guarantee that all array cells not holding69 // * deque elements are always null.70 // */71 // Object[] elements; // non-private to simplify nested class access72 73 // /**74 // * The index of the element at the head of the deque (which is the75 // * element that would be removed by remove() or pop()); or an76 // * arbitrary number equal to tail if the deque is empty.77 // */78 // int head;79 80 // /**81 // * The index at which the next element would be added to the tail82 // * of the deque (via addLast(E), add(E), or push(E)).83 // */84 // int tail;85 86 // /**87 // * The minimum capacity that we'll use for a newly created deque.88 // * Must be a power of 2.89 // */90 // private static final int MIN_INITIAL_CAPACITY = 8;91 92 // // ****** Array allocation and resizing utilities ******93 94 // /**95 // * Allocates empty array to hold the given number of elements.96 // *97 // * @param numElements the number of elements to hold98 // */99 // private void allocateElements(int numElements) {100 // int initialCapacity = MIN_INITIAL_CAPACITY;101 // // Find the best power of two to hold elements.102 // // Tests "<=" because arrays aren't kept full.103 // if (numElements >= initialCapacity) {104 // initialCapacity = numElements;105 // initialCapacity |= (initialCapacity >>> 1);106 // initialCapacity |= (initialCapacity >>> 2);107 // initialCapacity |= (initialCapacity >>> 4);108 // initialCapacity |= (initialCapacity >>> 8);109 // initialCapacity |= (initialCapacity >>> 16);110 // initialCapacity++;111 112 // if (initialCapacity < 0) // Too many elements, must back off113 // initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements114 // }115 // elements = new Object[initialCapacity];116 // }117 118 // /**119 // * Doubles the capacity of this deque. Call only when full, i.e.,120 // * when head and tail have wrapped around to become equal.121 // */122 // private void doubleCapacity() {123 // assert head == tail;124 // int p = head;125 // int n = elements.length;126 // int r = n - p; // number of elements to the right of p127 // int newCapacity = n << 1;128 // if (newCapacity < 0)129 // throw new IllegalStateException("Sorry, deque too big");130 // Object[] a = new Object[newCapacity];131 // System.arraycopy(elements, p, a, 0, r);132 // System.arraycopy(elements, 0, a, r, p);133 // elements = a;134 // head = 0;135 // tail = n;136 // }137 138 // /**139 // * Copies the elements from our element array into the specified array,140 // * in order (from first to last element in the deque). It is assumed141 // * that the array is large enough to hold all elements in the deque.142 // *143 // * @return its argument144 // */145 // private !(T) T[] copyElements(T[] a) {146 // if (head < tail) {147 // System.arraycopy(elements, head, a, 0, size());148 // } else if (head > tail) {149 // int headPortionLen = elements.length - head;150 // System.arraycopy(elements, head, a, 0, headPortionLen);151 // System.arraycopy(elements, 0, a, headPortionLen, tail);152 // }153 // return a;154 // }155 156 // /**157 // * Constructs an empty array deque with an initial capacity158 // * sufficient to hold 16 elements.159 // */160 // ArrayDeque() {161 // elements = new Object[16];162 // }163 164 // /**165 // * Constructs an empty array deque with an initial capacity166 // * sufficient to hold the specified number of elements.167 // *168 // * @param numElements lower bound on initial capacity of the deque169 // */170 // ArrayDeque(int numElements) {171 // allocateElements(numElements);172 // }173 174 // /**175 // * Constructs a deque containing the elements of the specified176 // * collection, in the order they are returned by the collection's177 // * iterator. (The first element returned by the collection's178 // * iterator becomes the first element, or <i>front</i> of the179 // * deque.)180 // *181 // * @param c the collection whose elements are to be placed into the deque182 // * @throws NullPointerException if the specified collection is null183 // */184 // ArrayDeque(Collection<E> c) {185 // allocateElements(c.size());186 // addAll(c);187 // }188 189 // // The main insertion and extraction methods are addFirst,190 // // addLast, pollFirst, pollLast. The other methods are defined in191 // // terms of these.192 193 // /**194 // * Inserts the specified element at the front of this deque.195 // *196 // * @param e the element to add197 // * @throws NullPointerException if the specified element is null198 // */199 // void addFirst(E e) {200 // if (e is null)201 // throw new NullPointerException();202 // elements[head = (head - 1) & (elements.length - 1)] = e;203 // if (head == tail)204 // doubleCapacity();205 // }206 207 // /**208 // * Inserts the specified element at the end of this deque.209 // *210 // * <p>This method is equivalent to {@link #add}.211 // *212 // * @param e the element to add213 // * @throws NullPointerException if the specified element is null214 // */215 // void addLast(E e) {216 // if (e is null)217 // throw new NullPointerException();218 // elements[tail] = e;219 // if ( (tail = (tail + 1) & (elements.length - 1)) == head)220 // doubleCapacity();221 // }222 223 // /**224 // * Inserts the specified element at the front of this deque.225 // *226 // * @param e the element to add227 // * @return {@code true} (as specified by {@link Deque#offerFirst})228 // * @throws NullPointerException if the specified element is null229 // */230 // bool offerFirst(E e) {231 // addFirst(e);232 // return true;233 // }234 235 // /**236 // * Inserts the specified element at the end of this deque.237 // *238 // * @param e the element to add239 // * @return {@code true} (as specified by {@link Deque#offerLast})240 // * @throws NullPointerException if the specified element is null241 // */242 // bool offerLast(E e) {243 // addLast(e);244 // return true;245 // }246 247 // /**248 // * @throws NoSuchElementException {@inheritDoc}249 // */250 // E removeFirst() {251 // E x = pollFirst();252 // if (x is null)253 // throw new NoSuchElementException();254 // return x;255 // }256 257 // /**258 // * @throws NoSuchElementException {@inheritDoc}259 // */260 // E removeLast() {261 // E x = pollLast();262 // if (x is null)263 // throw new NoSuchElementException();264 // return x;265 // }266 267 // E pollFirst() {268 // int h = head;269 // 270 // E result = (E) elements[h];271 // // Element is null if deque empty272 // if (result is null)273 // return null;274 // elements[h] = null; // Must null out slot275 // head = (h + 1) & (elements.length - 1);276 // return result;277 // }278 279 // E pollLast() {280 // int t = (tail - 1) & (elements.length - 1);281 // 282 // E result = (E) elements[t];283 // if (result is null)284 // return null;285 // elements[t] = null;286 // tail = t;287 // return result;288 // }289 290 // /**291 // * @throws NoSuchElementException {@inheritDoc}292 // */293 // E getFirst() {294 // 295 // E result = (E) elements[head];296 // if (result is null)297 // throw new NoSuchElementException();298 // return result;299 // }300 301 // /**302 // * @throws NoSuchElementException {@inheritDoc}303 // */304 // E getLast() {305 // 306 // E result = (E) elements[(tail - 1) & (elements.length - 1)];307 // if (result is null)308 // throw new NoSuchElementException();309 // return result;310 // }311 312 // 313 // E peekFirst() {314 // // elements[head] is null if deque empty315 // return (E) elements[head];316 // }317 318 // 319 // E peekLast() {320 // return (E) elements[(tail - 1) & (elements.length - 1)];321 // }322 323 // /**324 // * Removes the first occurrence of the specified element in this325 // * deque (when traversing the deque from head to tail).326 // * If the deque does not contain the element, it is unchanged.327 // * More formally, removes the first element {@code e} such that328 // * {@code o.equals(e)} (if such an element exists).329 // * Returns {@code true} if this deque contained the specified element330 // * (or equivalently, if this deque changed as a result of the call).331 // *332 // * @param o element to be removed from this deque, if present333 // * @return {@code true} if the deque contained the specified element334 // */335 // bool removeFirstOccurrence(Object o) {336 // if (o is null)337 // return false;338 // int mask = elements.length - 1;339 // int i = head;340 // Object x;341 // while ( (x = elements[i]) !is null) {342 // if (o.equals(x)) {343 // delete(i);344 // return true;345 // }346 // i = (i + 1) & mask;347 // }348 // return false;349 // }350 351 // /**352 // * Removes the last occurrence of the specified element in this353 // * deque (when traversing the deque from head to tail).354 // * If the deque does not contain the element, it is unchanged.355 // * More formally, removes the last element {@code e} such that356 // * {@code o.equals(e)} (if such an element exists).357 // * Returns {@code true} if this deque contained the specified element358 // * (or equivalently, if this deque changed as a result of the call).359 // *360 // * @param o element to be removed from this deque, if present361 // * @return {@code true} if the deque contained the specified element362 // */363 // bool removeLastOccurrence(Object o) {364 // if (o is null)365 // return false;366 // int mask = elements.length - 1;367 // int i = (tail - 1) & mask;368 // Object x;369 // while ( (x = elements[i]) !is null) {370 // if (o.equals(x)) {371 // delete(i);372 // return true;373 // }374 // i = (i - 1) & mask;375 // }376 // return false;377 // }378 379 // // *** Queue methods ***380 381 // /**382 // * Inserts the specified element at the end of this deque.383 // *384 // * <p>This method is equivalent to {@link #addLast}.385 // *386 // * @param e the element to add387 // * @return {@code true} (as specified by {@link Collection#add})388 // * @throws NullPointerException if the specified element is null389 // */390 // bool add(E e) {391 // addLast(e);392 // return true;393 // }394 395 // /**396 // * Inserts the specified element at the end of this deque.397 // *398 // * <p>This method is equivalent to {@link #offerLast}.399 // *400 // * @param e the element to add401 // * @return {@code true} (as specified by {@link Queue#offer})402 // * @throws NullPointerException if the specified element is null403 // */404 // bool offer(E e) {405 // return offerLast(e);406 // }407 408 // /**409 // * Retrieves and removes the head of the queue represented by this deque.410 // *411 // * This method differs from {@link #poll poll} only in that it throws an412 // * exception if this deque is empty.413 // *414 // * <p>This method is equivalent to {@link #removeFirst}.415 // *416 // * @return the head of the queue represented by this deque417 // * @throws NoSuchElementException {@inheritDoc}418 // */419 // E remove() {420 // return removeFirst();421 // }422 423 // /**424 // * Retrieves and removes the head of the queue represented by this deque425 // * (in other words, the first element of this deque), or returns426 // * {@code null} if this deque is empty.427 // *428 // * <p>This method is equivalent to {@link #pollFirst}.429 // *430 // * @return the head of the queue represented by this deque, or431 // * {@code null} if this deque is empty432 // */433 // E poll() {434 // return pollFirst();435 // }436 437 // /**438 // * Retrieves, but does not remove, the head of the queue represented by439 // * this deque. This method differs from {@link #peek peek} only in440 // * that it throws an exception if this deque is empty.441 // *442 // * <p>This method is equivalent to {@link #getFirst}.443 // *444 // * @return the head of the queue represented by this deque445 // * @throws NoSuchElementException {@inheritDoc}446 // */447 // E element() {448 // return getFirst();449 // }450 451 // /**452 // * Retrieves, but does not remove, the head of the queue represented by453 // * this deque, or returns {@code null} if this deque is empty.454 // *455 // * <p>This method is equivalent to {@link #peekFirst}.456 // *457 // * @return the head of the queue represented by this deque, or458 // * {@code null} if this deque is empty459 // */460 // E peek() {461 // return peekFirst();462 // }463 464 // // *** Stack methods ***465 466 // /**467 // * Pushes an element onto the stack represented by this deque. In other468 // * words, inserts the element at the front of this deque.469 // *470 // * <p>This method is equivalent to {@link #addFirst}.471 // *472 // * @param e the element to push473 // * @throws NullPointerException if the specified element is null474 // */475 // void push(E e) {476 // addFirst(e);477 // }478 479 // /**480 // * Pops an element from the stack represented by this deque. In other481 // * words, removes and returns the first element of this deque.482 // *483 // * <p>This method is equivalent to {@link #removeFirst()}.484 // *485 // * @return the element at the front of this deque (which is the top486 // * of the stack represented by this deque)487 // * @throws NoSuchElementException {@inheritDoc}488 // */489 // E pop() {490 // return removeFirst();491 // }492 493 // private void checkInvariants() {494 // assert elements[tail] is null;495 // assert head == tail ? elements[head] is null :496 // (elements[head] !is null &&497 // elements[(tail - 1) & (elements.length - 1)] !is null);498 // assert elements[(head - 1) & (elements.length - 1)] is null;499 // }500 501 // /**502 // * Removes the element at the specified position in the elements array,503 // * adjusting head and tail as necessary. This can result in motion of504 // * elements backwards or forwards in the array.505 // *506 // * <p>This method is called delete rather than remove to emphasize507 // * that its semantics differ from those of {@link List#remove(int)}.508 // *509 // * @return true if elements moved backwards510 // */511 // private bool delete(int i) {512 // checkInvariants();513 // final Object[] elements = this.elements;514 // final int mask = elements.length - 1;515 // final int h = head;516 // final int t = tail;517 // final int front = (i - h) & mask;518 // final int back = (t - i) & mask;519 520 // // Invariant: head <= i < tail mod circularity521 // if (front >= ((t - h) & mask))522 // throw new ConcurrentModificationException();523 524 // // Optimize for least element motion525 // if (front < back) {526 // if (h <= i) {527 // System.arraycopy(elements, h, elements, h + 1, front);528 // } else { // Wrap around529 // System.arraycopy(elements, 0, elements, 1, i);530 // elements[0] = elements[mask];531 // System.arraycopy(elements, h, elements, h + 1, mask - h);532 // }533 // elements[h] = null;534 // head = (h + 1) & mask;535 // return false;536 // } else {537 // if (i < t) { // Copy the null tail as well538 // System.arraycopy(elements, i + 1, elements, i, back);539 // tail = t - 1;540 // } else { // Wrap around541 // System.arraycopy(elements, i + 1, elements, i, mask - i);542 // elements[mask] = elements[0];543 // System.arraycopy(elements, 1, elements, 0, t);544 // tail = (t - 1) & mask;545 // }546 // return true;547 // }548 // }549 550 // // *** Collection Methods ***551 552 // /**553 // * Returns the number of elements in this deque.554 // *555 // * @return the number of elements in this deque556 // */557 // int size() {558 // return (tail - head) & (elements.length - 1);559 // }560 561 // /**562 // * Returns {@code true} if this deque contains no elements.563 // *564 // * @return {@code true} if this deque contains no elements565 // */566 // bool isEmpty() {567 // return head == tail;568 // }569 570 // /**571 // * Returns an iterator over the elements in this deque. The elements572 // * will be ordered from first (head) to last (tail). This is the same573 // * order that elements would be dequeued (via successive calls to574 // * {@link #remove} or popped (via successive calls to {@link #pop}).575 // *576 // * @return an iterator over the elements in this deque577 // */578 // Iterator!E iterator() {579 // return new DeqIterator();580 // }581 582 // Iterator!E descendingIterator() {583 // return new DescendingIterator();584 // }585 586 // private class DeqIterator implements Iterator!E {587 // /**588 // * Index of element to be returned by subsequent call to next.589 // */590 // private int cursor = head;591 592 // /**593 // * Tail recorded at construction (also in remove), to stop594 // * iterator and also to check for comodification.595 // */596 // private int fence = tail;597 598 // /**599 // * Index of element returned by most recent call to next.600 // * Reset to -1 if element is deleted by a call to remove.601 // */602 // private int lastRet = -1;603 604 // bool hasNext() {605 // return cursor != fence;606 // }607 608 // E next() {609 // if (cursor == fence)610 // throw new NoSuchElementException();611 // 612 // E result = (E) elements[cursor];613 // // This check doesn't catch all possible comodifications,614 // // but does catch the ones that corrupt traversal615 // if (tail != fence || result is null)616 // throw new ConcurrentModificationException();617 // lastRet = cursor;618 // cursor = (cursor + 1) & (elements.length - 1);619 // return result;620 // }621 622 // void remove() {623 // if (lastRet < 0)624 // throw new IllegalStateException();625 // if (delete(lastRet)) { // if left-shifted, undo increment in next()626 // cursor = (cursor - 1) & (elements.length - 1);627 // fence = tail;628 // }629 // lastRet = -1;630 // }631 632 // void forEachRemaining(Consumer<E> action) {633 // Objects.requireNonNull(action);634 // Object[] a = elements;635 // int m = a.length - 1, f = fence, i = cursor;636 // cursor = f;637 // while (i != f) {638 // E e = (E)a[i];639 // i = (i + 1) & m;640 // if (e is null)641 // throw new ConcurrentModificationException();642 // action.accept(e);643 // }644 // }645 // }646 647 // private class DescendingIterator implements Iterator!E {648 // /*649 // * This class is nearly a mirror-image of DeqIterator, using650 // * tail instead of head for initial cursor, and head instead of651 // * tail for fence.652 // */653 // private int cursor = tail;654 // private int fence = head;655 // private int lastRet = -1;656 657 // bool hasNext() {658 // return cursor != fence;659 // }660 661 // E next() {662 // if (cursor == fence)663 // throw new NoSuchElementException();664 // cursor = (cursor - 1) & (elements.length - 1);665 // 666 // E result = (E) elements[cursor];667 // if (head != fence || result is null)668 // throw new ConcurrentModificationException();669 // lastRet = cursor;670 // return result;671 // }672 673 // void remove() {674 // if (lastRet < 0)675 // throw new IllegalStateException();676 // if (!delete(lastRet)) {677 // cursor = (cursor + 1) & (elements.length - 1);678 // fence = head;679 // }680 // lastRet = -1;681 // }682 // }683 684 // /**685 // * Returns {@code true} if this deque contains the specified element.686 // * More formally, returns {@code true} if and only if this deque contains687 // * at least one element {@code e} such that {@code o.equals(e)}.688 // *689 // * @param o object to be checked for containment in this deque690 // * @return {@code true} if this deque contains the specified element691 // */692 // bool contains(Object o) {693 // if (o is null)694 // return false;695 // int mask = elements.length - 1;696 // int i = head;697 // Object x;698 // while ( (x = elements[i]) !is null) {699 // if (o.equals(x))700 // return true;701 // i = (i + 1) & mask;702 // }703 // return false;704 // }705 706 // /**707 // * Removes a single instance of the specified element from this deque.708 // * If the deque does not contain the element, it is unchanged.709 // * More formally, removes the first element {@code e} such that710 // * {@code o.equals(e)} (if such an element exists).711 // * Returns {@code true} if this deque contained the specified element712 // * (or equivalently, if this deque changed as a result of the call).713 // *714 // * <p>This method is equivalent to {@link #removeFirstOccurrence(Object)}.715 // *716 // * @param o element to be removed from this deque, if present717 // * @return {@code true} if this deque contained the specified element718 // */719 // bool remove(Object o) {720 // return removeFirstOccurrence(o);721 // }722 723 // /**724 // * Removes all of the elements from this deque.725 // * The deque will be empty after this call returns.726 // */727 // void clear() {728 // int h = head;729 // int t = tail;730 // if (h != t) { // clear all cells731 // head = tail = 0;732 // int i = h;733 // int mask = elements.length - 1;734 // do {735 // elements[i] = null;736 // i = (i + 1) & mask;737 // } while (i != t);738 // }739 // }740 741 // /**742 // * Returns an array containing all of the elements in this deque743 // * in proper sequence (from first to last element).744 // *745 // * <p>The returned array will be "safe" in that no references to it are746 // * maintained by this deque. (In other words, this method must allocate747 // * a new array). The caller is thus free to modify the returned array.748 // *749 // * <p>This method acts as bridge between array-based and collection-based750 // * APIs.751 // *752 // * @return an array containing all of the elements in this deque753 // */754 // Object[] toArray() {755 // return copyElements(new Object[size()]);756 // }757 758 // /**759 // * Returns an array containing all of the elements in this deque in760 // * proper sequence (from first to last element); the runtime type of the761 // * returned array is that of the specified array. If the deque fits in762 // * the specified array, it is returned therein. Otherwise, a new array763 // * is allocated with the runtime type of the specified array and the764 // * size of this deque.765 // *766 // * <p>If this deque fits in the specified array with room to spare767 // * (i.e., the array has more elements than this deque), the element in768 // * the array immediately following the end of the deque is set to769 // * {@code null}.770 // *771 // * <p>Like the {@link #toArray()} method, this method acts as bridge between772 // * array-based and collection-based APIs. Further, this method allows773 // * precise control over the runtime type of the output array, and may,774 // * under certain circumstances, be used to save allocation costs.775 // *776 // * <p>Suppose {@code x} is a deque known to contain only strings.777 // * The following code can be used to dump the deque into a newly778 // * allocated array of {@code string}:779 // *780 // * <pre> {@code string[] y = x.toArray(new string[0]);}</pre>781 // *782 // * Note that {@code toArray(new Object[0])} is identical in function to783 // * {@code toArray()}.784 // *785 // * @param a the array into which the elements of the deque are to786 // * be stored, if it is big enough; otherwise, a new array of the787 // * same runtime type is allocated for this purpose788 // * @return an array containing all of the elements in this deque789 // * @throws ArrayStoreException if the runtime type of the specified array790 // * is not a supertype of the runtime type of every element in791 // * this deque792 // * @throws NullPointerException if the specified array is null793 // */794 // 795 // !(T) T[] toArray(T[] a) {796 // int size = size();797 // if (a.length < size)798 // a = (T[])java.lang.reflect.Array.newInstance(799 // a.getClass().getComponentType(), size);800 // copyElements(a);801 // if (a.length > size)802 // a[size] = null;803 // return a;804 // }805 806 // // *** Object methods ***807 808 // /**809 // * Returns a copy of this deque.810 // *811 // * @return a copy of this deque812 // */813 // ArrayDeque!E clone() {814 // try {815 // 816 // ArrayDeque!E result = (ArrayDeque!E) super.clone();817 // result.elements = Arrays.copyOf(elements, elements.length);818 // return result;819 // } catch (CloneNotSupportedException e) {820 // throw new AssertionError();821 // }822 // }823 824 // private static final long serialVersionUID = 2340985798034038923L;825 826 // /**827 // * Saves this deque to a stream (that is, serializes it).828 // *829 // * @serialData The current size ({@code int}) of the deque,830 // * followed by all of its elements (each an object reference) in831 // * first-to-last order.832 // */833 // private void writeObject(java.io.ObjectOutputStream s)834 // throws java.io.IOException {835 // s.defaultWriteObject();836 837 // // Write out size838 // s.writeInt(size());839 840 // // Write out elements in order.841 // int mask = elements.length - 1;842 // for (int i = head; i != tail; i = (i + 1) & mask)843 // s.writeObject(elements[i]);844 // }845 846 // /**847 // * Reconstitutes this deque from a stream (that is, deserializes it).848 // */849 // private void readObject(java.io.ObjectInputStream s)850 // throws java.io.IOException, ClassNotFoundException {851 // s.defaultReadObject();852 853 // // Read in size and allocate array854 // int size = s.readInt();855 // allocateElements(size);856 // head = 0;857 // tail = size;858 859 // // Read in all elements in the proper order.860 // for (int i = 0; i < size; i++)861 // elements[i] = s.readObject();862 // }863 864 // /**865 // * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>866 // * and <em>fail-fast</em> {@link Spliterator} over the elements in this867 // * deque.868 // *869 // * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},870 // * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and871 // * {@link Spliterator#NONNULL}. Overriding implementations should document872 // * the reporting of additional characteristic values.873 // *874 // * @return a {@code Spliterator} over the elements in this deque875 // * @since 1.8876 // */877 // Spliterator!E spliterator() {878 // return new DeqSpliterator!E(this, -1, -1);879 // }880 881 // static final class DeqSpliterator!E implements Spliterator!E {882 // private final ArrayDeque!E deq;883 // private int fence; // -1 until first use884 // private int index; // current index, modified on traverse/split885 886 // /** Creates new spliterator covering the given array and range */887 // DeqSpliterator(ArrayDeque!E deq, int origin, int fence) {888 // this.deq = deq;889 // this.index = origin;890 // this.fence = fence;891 // }892 893 // private int getFence() { // force initialization894 // int t;895 // if ((t = fence) < 0) {896 // t = fence = deq.tail;897 // index = deq.head;898 // }899 // return t;900 // }901 902 // DeqSpliterator!E trySplit() {903 // int t = getFence(), h = index, n = deq.elements.length;904 // if (h != t && ((h + 1) & (n - 1)) != t) {905 // if (h > t)906 // t += n;907 // int m = ((h + t) >>> 1) & (n - 1);908 // return new DeqSpliterator<>(deq, h, index = m);909 // }910 // return null;911 // }912 913 // void forEachRemaining(Consumer<E> consumer) {914 // if (consumer is null)915 // throw new NullPointerException();916 // Object[] a = deq.elements;917 // int m = a.length - 1, f = getFence(), i = index;918 // index = f;919 // while (i != f) {920 // E e = (E)a[i];921 // i = (i + 1) & m;922 // if (e is null)923 // throw new ConcurrentModificationException();924 // consumer.accept(e);925 // }926 // }927 928 // bool tryAdvance(Consumer<E> consumer) {929 // if (consumer is null)930 // throw new NullPointerException();931 // Object[] a = deq.elements;932 // int m = a.length - 1, f = getFence(), i = index;933 // if (i != fence) {934 // E e = (E)a[i];935 // index = (i + 1) & m;936 // if (e is null)937 // throw new ConcurrentModificationException();938 // consumer.accept(e);939 // return true;940 // }941 // return false;942 // }943 944 // long estimateSize() {945 // int n = getFence() - index;946 // if (n < 0)947 // n += deq.elements.length;948 // return (long) n;949 // }950 951 // override952 // int characteristics() {953 // return Spliterator.ORDERED | Spliterator.SIZED |954 // Spliterator.NONNULL | Spliterator.SUBSIZED;955 // }956 // }957 958 // }