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
40 /**
41 * Resizable-array implementation of the {@link Deque} interface. Array
42 * deques have no capacity restrictions; they grow as necessary to support
43 * usage. They are not thread-safe; in the absence of external
44 * synchronization, they do not support concurrent access by multiple threads.
45 * Null elements are prohibited. This class is likely to be faster than
46 * {@link Stack} when used as a stack, and faster than {@link LinkedList}
47 * when used as a queue.
48 *
49 * <p>Most {@code ArrayDeque} operations run in amortized constant time.
50 * Exceptions include {@link #remove(Object) remove}, {@link
51 * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
52 * removeLastOccurrence}, {@link #contains contains}, {@link #iterator
53 * iterator.remove()}, and the bulk operations, all of which run in linear
54 * time.
55 *
56 * <p>The iterators returned by this class's {@code iterator} method are
57 * <i>fail-fast</i>: If the deque is modified at any time after the iterator
58 * is created, in any way except through the iterator's own {@code remove}
101 * The index of the element at the head of the deque (which is the
102 * element that would be removed by remove() or pop()); or an
103 * arbitrary number equal to tail if the deque is empty.
104 */
105 transient int head;
106
107 /**
108 * The index at which the next element would be added to the tail
109 * of the deque (via addLast(E), add(E), or push(E)).
110 */
111 transient int tail;
112
113 /**
114 * The minimum capacity that we'll use for a newly created deque.
115 * Must be a power of 2.
116 */
117 private static final int MIN_INITIAL_CAPACITY = 8;
118
119 // ****** Array allocation and resizing utilities ******
120
121 /**
122 * Allocates empty array to hold the given number of elements.
123 *
124 * @param numElements the number of elements to hold
125 */
126 private void allocateElements(int numElements) {
127 int initialCapacity = MIN_INITIAL_CAPACITY;
128 // Find the best power of two to hold elements.
129 // Tests "<=" because arrays aren't kept full.
130 if (numElements >= initialCapacity) {
131 initialCapacity = numElements;
132 initialCapacity |= (initialCapacity >>> 1);
133 initialCapacity |= (initialCapacity >>> 2);
134 initialCapacity |= (initialCapacity >>> 4);
135 initialCapacity |= (initialCapacity >>> 8);
136 initialCapacity |= (initialCapacity >>> 16);
137 initialCapacity++;
138
139 if (initialCapacity < 0) // Too many elements, must back off
140 initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
141 }
142 elements = new Object[initialCapacity];
143 }
144
145 /**
146 * Doubles the capacity of this deque. Call only when full, i.e.,
147 * when head and tail have wrapped around to become equal.
148 */
149 private void doubleCapacity() {
150 assert head == tail;
151 int p = head;
152 int n = elements.length;
153 int r = n - p; // number of elements to the right of p
154 int newCapacity = n << 1;
155 if (newCapacity < 0)
156 throw new IllegalStateException("Sorry, deque too big");
157 Object[] a = new Object[newCapacity];
158 System.arraycopy(elements, p, a, 0, r);
159 System.arraycopy(elements, 0, a, r, p);
160 elements = a;
161 head = 0;
162 tail = n;
862 s.defaultWriteObject();
863
864 // Write out size
865 s.writeInt(size());
866
867 // Write out elements in order.
868 int mask = elements.length - 1;
869 for (int i = head; i != tail; i = (i + 1) & mask)
870 s.writeObject(elements[i]);
871 }
872
873 /**
874 * Reconstitutes this deque from a stream (that is, deserializes it).
875 */
876 private void readObject(java.io.ObjectInputStream s)
877 throws java.io.IOException, ClassNotFoundException {
878 s.defaultReadObject();
879
880 // Read in size and allocate array
881 int size = s.readInt();
882 allocateElements(size);
883 head = 0;
884 tail = size;
885
886 // Read in all elements in the proper order.
887 for (int i = 0; i < size; i++)
888 elements[i] = s.readObject();
889 }
890
891 /**
892 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
893 * and <em>fail-fast</em> {@link Spliterator} over the elements in this
894 * deque.
895 *
896 * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
897 * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and
898 * {@link Spliterator#NONNULL}. Overriding implementations should document
899 * the reporting of additional characteristic values.
900 *
901 * @return a {@code Spliterator} over the elements in this deque
|
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 sun.misc.SharedSecrets;
40
41 /**
42 * Resizable-array implementation of the {@link Deque} interface. Array
43 * deques have no capacity restrictions; they grow as necessary to support
44 * usage. They are not thread-safe; in the absence of external
45 * synchronization, they do not support concurrent access by multiple threads.
46 * Null elements are prohibited. This class is likely to be faster than
47 * {@link Stack} when used as a stack, and faster than {@link LinkedList}
48 * when used as a queue.
49 *
50 * <p>Most {@code ArrayDeque} operations run in amortized constant time.
51 * Exceptions include {@link #remove(Object) remove}, {@link
52 * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
53 * removeLastOccurrence}, {@link #contains contains}, {@link #iterator
54 * iterator.remove()}, and the bulk operations, all of which run in linear
55 * time.
56 *
57 * <p>The iterators returned by this class's {@code iterator} method are
58 * <i>fail-fast</i>: If the deque is modified at any time after the iterator
59 * is created, in any way except through the iterator's own {@code remove}
102 * The index of the element at the head of the deque (which is the
103 * element that would be removed by remove() or pop()); or an
104 * arbitrary number equal to tail if the deque is empty.
105 */
106 transient int head;
107
108 /**
109 * The index at which the next element would be added to the tail
110 * of the deque (via addLast(E), add(E), or push(E)).
111 */
112 transient int tail;
113
114 /**
115 * The minimum capacity that we'll use for a newly created deque.
116 * Must be a power of 2.
117 */
118 private static final int MIN_INITIAL_CAPACITY = 8;
119
120 // ****** Array allocation and resizing utilities ******
121
122 private static int calculateSize(int numElements) {
123 int initialCapacity = MIN_INITIAL_CAPACITY;
124 // Find the best power of two to hold elements.
125 // Tests "<=" because arrays aren't kept full.
126 if (numElements >= initialCapacity) {
127 initialCapacity = numElements;
128 initialCapacity |= (initialCapacity >>> 1);
129 initialCapacity |= (initialCapacity >>> 2);
130 initialCapacity |= (initialCapacity >>> 4);
131 initialCapacity |= (initialCapacity >>> 8);
132 initialCapacity |= (initialCapacity >>> 16);
133 initialCapacity++;
134
135 if (initialCapacity < 0) // Too many elements, must back off
136 initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
137 }
138 return initialCapacity;
139 }
140
141 /**
142 * Allocates empty array to hold the given number of elements.
143 *
144 * @param numElements the number of elements to hold
145 */
146 private void allocateElements(int numElements) {
147 elements = new Object[calculateSize(numElements)];
148 }
149
150 /**
151 * Doubles the capacity of this deque. Call only when full, i.e.,
152 * when head and tail have wrapped around to become equal.
153 */
154 private void doubleCapacity() {
155 assert head == tail;
156 int p = head;
157 int n = elements.length;
158 int r = n - p; // number of elements to the right of p
159 int newCapacity = n << 1;
160 if (newCapacity < 0)
161 throw new IllegalStateException("Sorry, deque too big");
162 Object[] a = new Object[newCapacity];
163 System.arraycopy(elements, p, a, 0, r);
164 System.arraycopy(elements, 0, a, r, p);
165 elements = a;
166 head = 0;
167 tail = n;
867 s.defaultWriteObject();
868
869 // Write out size
870 s.writeInt(size());
871
872 // Write out elements in order.
873 int mask = elements.length - 1;
874 for (int i = head; i != tail; i = (i + 1) & mask)
875 s.writeObject(elements[i]);
876 }
877
878 /**
879 * Reconstitutes this deque from a stream (that is, deserializes it).
880 */
881 private void readObject(java.io.ObjectInputStream s)
882 throws java.io.IOException, ClassNotFoundException {
883 s.defaultReadObject();
884
885 // Read in size and allocate array
886 int size = s.readInt();
887 int capacity = calculateSize(size);
888 SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
889 allocateElements(size);
890 head = 0;
891 tail = size;
892
893 // Read in all elements in the proper order.
894 for (int i = 0; i < size; i++)
895 elements[i] = s.readObject();
896 }
897
898 /**
899 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
900 * and <em>fail-fast</em> {@link Spliterator} over the elements in this
901 * deque.
902 *
903 * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
904 * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and
905 * {@link Spliterator#NONNULL}. Overriding implementations should document
906 * the reporting of additional characteristic values.
907 *
908 * @return a {@code Spliterator} over the elements in this deque
|