Class ArrayDeque

classpath/java/util/ArrayDeque.java:13–364

package java.util;

public class ArrayDeque<T> extends AbstractDeque<T> 
                           implements Deque<T> {
  private Object[] dataArray;
  // both indexes are inclusive, except when size == 0
  private int startIndex;
  private int endIndex;
  private int size;
  private int modCount;
  
  public ArrayDeque() {
    this(16);
  }
  
  public ArrayDeque(int intialSize) {
    dataArray = new Object[intialSize];
    modCount = 0;
    clear();
  }
  
  public ArrayDeque(Collection<? extends T> c) {
    this(c.size());
    
    addAll(c);
  }
  
  private void copyInto(Object[] array) {
    if (startIndex <= endIndex) {
      // only one copy needed
      System.arraycopy(dataArray, startIndex, array, 0, size);
    } else {
      int firstCopyCount = dataArray.length - startIndex;
      System.arraycopy(dataArray, startIndex, array, 0, firstCopyCount);
      System.arraycopy(dataArray, 0, array, firstCopyCount, endIndex + 1);
    }
  }
  
  private void ensureCapacity(int newSize) {
    if (dataArray.length < newSize) {
      Object[] newArray = new Object[dataArray.length * 2];
      copyInto(newArray);
      
      dataArray = newArray;
      startIndex = 0;
      endIndex = size - 1;
    }
  }

  @Override
  public boolean offerFirst(T e) {
    ensureCapacity(size() + 1);
    modCount++;
    
    if (size > 0) {
      // we don't need to move the head index for the first one
      startIndex--;
      if (startIndex < 0) { // wrapping to the end of the array
        startIndex = dataArray.length - 1;
      }