Cannot find problems with array based deque, but getting outOfBounds exception

Question

I have been trying to figure this out for an age, but to no avail. I think I must have several problems with my code that I just can't see. I have implemented this using a slightly more complex way before, and was writing it in a simpler form to help a friend in the year below me who is struggling, but I've just ended up getting myself in a muddle!

The code is as follows :

 public class ArrayBasedDeque<EltType> implements Deque<EltType> {

  private final int CAPACITY = 10;
  private int capacity;
  private int end;
  private EltType deque[];  

  public ArrayBasedDeque() {
    this.capacity = CAPACITY;
    deque = (EltType[]) (new Object[capacity]);  
  }
  public EltType first() {
    return  deque[0];
  }
  public EltType last() {
    return deque[end];
  }

  public boolean isEmpty() {
    return end == 0;
  }

  public int size() {
   return deque.length;
  }

  public boolean isFull() {
   int curSize = size();
   return curSize >= capacity;
  }

  public void insertFirst(EltType first) {
    if(!isEmpty()) {
    EltType[] tempArray;
    tempArray = (EltType[]) new Object[capacity+1];
    for (int i=0;i<deque.length;i++) {
      tempArray[i+1] = deque[i]; 
    }
    deque = tempArray; 
    }
   deque[0] = first;
   end++;
  }

  public void insertLast(EltType last) {
    if (isFull()){
          EltType[] tempArray;
      tempArray = (EltType[]) new Object[CAPACITY+1];
      for (int i=0;i<deque.length;i++) {
        tempArray[i] = deque[i]; 
      }
    }
    deque[end] = last;   
    end++;
  }

  public EltType removeFirst() {
    EltType[] tempArray;
    EltType returned = deque[0];
    tempArray = (EltType[]) new Object[capacity];
      for (int i=1;i<capacity;i++) {
        tempArray[i-1] = deque[i]; 
      }
      deque = tempArray;
      end--;
    return returned;
  }

  public EltType removeLast() {
    EltType[] tempArray;
        System.out.println(end);
    EltType returned = deque[end];

    tempArray = (EltType[]) new Object[capacity];
      for (int i=0;i<deque.length;i++) {
        tempArray[i] = deque[i]; 
      }
      deque = tempArray;
    return returned;
  }
}

The problem is that when I call

abd.insertFirst( 3 );
abd.insertFirst( 3 );
abd.insertFirst( 3 );

this, it returns an error.

java.lang.ArrayIndexOutOfBoundsException: 11
    at ArrayBasedDeque.insertFirst(ArrayBasedDeque.java:37)
    at TestABD.main(TestABD.java:7)
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
    at sun.reflect.NativeMethodAccessorImpl.invoke(Unknown Source)
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
    at java.lang.reflect.Method.invoke(Unknown Source)
    at edu.rice.cs.drjava.model.compiler.JavacCompiler.runCommand(JavacCompiler.java:271)

the same is true for the insertLast method. I can't figure it out, and was hoping the scrutinizing gaze of stackOverflow could help me. Thanks a lot !

Answer 1

tempArray = (EltType[]) new Object[capacity+1];
for (int i=0;i<deque.length;i++) {
  tempArray[i+1] = deque[i]; 
}
deque = tempArray; 

After the first method call, deque is an array of length 11 (deque == tempArray == new Object[capacity+1] == new Object[11]. The next time the method is called, you allocate tempArray for capacity+1 == 11 slots, but traverse the for-loop from 0 to deque.length which is 0 to 10 on the second method call. The last pass of the loop ends up being:

tempArray[11] = ...

which is past the end of tempArray which only has 11 slots ([0] to [10]).

---

The naive fix is to have the for-loop go from 0 to capacity instead of from 0 to deque.length, but I'm unsure if this implements the actual behavior you want. Another approach is to allocate tempArray = new Object[deque.length+1], but then capacity doesn't really mean capacity and it still may not reflect conceptually what you think is the "correct" behavior in that situation.