}
private void checkInvariants() {
- assert elements[tail] == null;
- assert head == tail ? elements[head] == null :
- (elements[head] != null &&
- elements[(tail - 1) & (elements.length - 1)] != null);
- assert elements[(head - 1) & (elements.length - 1)] == null;
+ assert elements[tail] == null;
+ assert head == tail ? elements[head] == null :
+ (elements[head] != null &&
+ elements[(tail - 1) & (elements.length - 1)] != null);
+ assert elements[(head - 1) & (elements.length - 1)] == null;
}
/**
* @return true if elements moved backwards
*/
private boolean delete(int i) {
- checkInvariants();
- final E[] elements = this.elements;
- final int mask = elements.length - 1;
- final int h = head;
- final int t = tail;
- final int front = (i - h) & mask;
- final int back = (t - i) & mask;
-
- // Invariant: head <= i < tail mod circularity
- if (front >= ((t - h) & mask))
- throw new ConcurrentModificationException();
-
- // Optimize for least element motion
- if (front < back) {
- if (h <= i) {
- System.arraycopy(elements, h, elements, h + 1, front);
- } else { // Wrap around
- System.arraycopy(elements, 0, elements, 1, i);
- elements[0] = elements[mask];
- System.arraycopy(elements, h, elements, h + 1, mask - h);
- }
- elements[h] = null;
- head = (h + 1) & mask;
- return false;
- } else {
- if (i < t) { // Copy the null tail as well
- System.arraycopy(elements, i + 1, elements, i, back);
- tail = t - 1;
- } else { // Wrap around
- System.arraycopy(elements, i + 1, elements, i, mask - i);
- elements[mask] = elements[0];
- System.arraycopy(elements, 1, elements, 0, t);
- tail = (t - 1) & mask;
- }
- return true;
- }
+ checkInvariants();
+ final E[] elements = this.elements;
+ final int mask = elements.length - 1;
+ final int h = head;
+ final int t = tail;
+ final int front = (i - h) & mask;
+ final int back = (t - i) & mask;
+
+ // Invariant: head <= i < tail mod circularity
+ if (front >= ((t - h) & mask))
+ throw new ConcurrentModificationException();
+
+ // Optimize for least element motion
+ if (front < back) {
+ if (h <= i) {
+ System.arraycopy(elements, h, elements, h + 1, front);
+ } else { // Wrap around
+ System.arraycopy(elements, 0, elements, 1, i);
+ elements[0] = elements[mask];
+ System.arraycopy(elements, h, elements, h + 1, mask - h);
+ }
+ elements[h] = null;
+ head = (h + 1) & mask;
+ return false;
+ } else {
+ if (i < t) { // Copy the null tail as well
+ System.arraycopy(elements, i + 1, elements, i, back);
+ tail = t - 1;
+ } else { // Wrap around
+ System.arraycopy(elements, i + 1, elements, i, mask - i);
+ elements[mask] = elements[0];
+ System.arraycopy(elements, 1, elements, 0, t);
+ tail = (t - 1) & mask;
+ }
+ return true;
+ }
}
// *** Collection Methods ***
throw new IllegalStateException();
if (delete(lastRet)) { // if left-shifted, undo increment in next()
cursor = (cursor - 1) & (elements.length - 1);
- fence = tail;
- }
+ fence = tail;
+ }
lastRet = -1;
}
}
if (cursor == fence)
throw new NoSuchElementException();
cursor = (cursor - 1) & (elements.length - 1);
- E result = elements[cursor];
+ E result = elements[cursor];
if (head != fence || result == null)
throw new ConcurrentModificationException();
lastRet = cursor;
throw new IllegalStateException();
if (!delete(lastRet)) {
cursor = (cursor + 1) & (elements.length - 1);
- fence = head;
- }
+ fence = head;
+ }
lastRet = -1;
}
}
* @return an array containing all of the elements in this deque
*/
public Object[] toArray() {
- return copyElements(new Object[size()]);
+ return copyElements(new Object[size()]);
}
/**
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
- copyElements(a);
+ copyElements(a);
if (a.length > size)
a[size] = null;
return a;