--- jsr166/src/main/java/util/ArrayDeque.java 2013/02/17 23:36:16 1.47
+++ jsr166/src/main/java/util/ArrayDeque.java 2013/02/20 12:39:06 1.51
@@ -19,16 +19,18 @@ import java.util.stream.Streams;
* when used as a queue.
*
*
Most {@code ArrayDeque} operations run in amortized constant time.
- * Exceptions include {@link #remove(Object) remove}, {@link
- * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
- * removeLastOccurrence}, {@link #contains contains}, {@link #iterator
- * iterator.remove()}, and the bulk operations, all of which run in linear
- * time.
+ * Exceptions include
+ * {@link #remove(Object) remove},
+ * {@link #removeFirstOccurrence removeFirstOccurrence},
+ * {@link #removeLastOccurrence removeLastOccurrence},
+ * {@link #contains contains},
+ * {@link #iterator iterator.remove()},
+ * and the bulk operations, all of which run in linear time.
*
- *
The iterators returned by this class's {@code iterator} method are
- * fail-fast: If the deque is modified at any time after the iterator
- * is created, in any way except through the iterator's own {@code remove}
- * method, the iterator will generally throw a {@link
+ *
The iterators returned by this class's {@link #iterator() iterator}
+ * method are fail-fast: If the deque is modified at any time after
+ * the iterator is created, in any way except through the iterator's own
+ * {@code remove} method, the iterator will generally throw a {@link
* ConcurrentModificationException}. Thus, in the face of concurrent
* modification, the iterator fails quickly and cleanly, rather than risking
* arbitrary, non-deterministic behavior at an undetermined time in the
@@ -135,24 +137,6 @@ public class ArrayDeque extends Abstr
}
/**
- * Copies the elements from our element array into the specified array,
- * in order (from first to last element in the deque). It is assumed
- * that the array is large enough to hold all elements in the deque.
- *
- * @return its argument
- */
- private T[] copyElements(T[] a) {
- if (head < tail) {
- System.arraycopy(elements, head, a, 0, size());
- } else if (head > tail) {
- int headPortionLen = elements.length - head;
- System.arraycopy(elements, head, a, 0, headPortionLen);
- System.arraycopy(elements, 0, a, headPortionLen, tail);
- }
- return a;
- }
-
- /**
* Constructs an empty array deque with an initial capacity
* sufficient to hold 16 elements.
*/
@@ -737,7 +721,14 @@ public class ArrayDeque extends Abstr
* @return an array containing all of the elements in this deque
*/
public Object[] toArray() {
- return copyElements(new Object[size()]);
+ final int head = this.head;
+ final int tail = this.tail;
+ boolean wrap = (tail < head);
+ int end = wrap ? tail + elements.length : tail;
+ Object[] a = Arrays.copyOfRange(elements, head, end);
+ if (wrap)
+ System.arraycopy(elements, 0, a, elements.length - head, tail);
+ return a;
}
/**
@@ -778,13 +769,22 @@ public class ArrayDeque extends Abstr
*/
@SuppressWarnings("unchecked")
public T[] toArray(T[] a) {
- int size = size();
- if (a.length < size)
- a = (T[])java.lang.reflect.Array.newInstance(
- a.getClass().getComponentType(), size);
- copyElements(a);
- if (a.length > size)
- a[size] = null;
+ final int head = this.head;
+ final int tail = this.tail;
+ boolean wrap = (tail < head);
+ int size = (tail - head) + (wrap ? elements.length : 0);
+ int firstLeg = size - (wrap ? tail : 0);
+ int len = a.length;
+ if (size > len) {
+ a = (T[]) Arrays.copyOfRange(elements, head, head + size,
+ a.getClass());
+ } else {
+ System.arraycopy(elements, head, a, 0, firstLeg);
+ if (size < len)
+ a[size] = null;
+ }
+ if (wrap)
+ System.arraycopy(elements, 0, a, firstLeg, tail);
return a;
}
@@ -862,8 +862,8 @@ public class ArrayDeque extends Abstr
private final ArrayDeque deq;
private int fence; // -1 until first use
private int index; // current index, modified on traverse/split
-
- /** Create new spliterator covering the given array and range */
+
+ /** Creates new spliterator covering the given array and range */
DeqSpliterator(ArrayDeque deq, int origin, int fence) {
this.deq = deq;
this.index = origin;
@@ -930,7 +930,7 @@ public class ArrayDeque extends Abstr
@Override
public int characteristics() {
- return Spliterator.ORDERED | Spliterator.SIZED |
+ return Spliterator.ORDERED | Spliterator.SIZED |
Spliterator.NONNULL | Spliterator.SUBSIZED;
}
}