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 !

There a many, many logic errors in this code. It also appears to be a HW assignment. Is that true? — troutinator
– troutinator, Commented Feb 8, 2011 at 17:47

Bert F · Accepted Answer · 2011-02-08 17:57:21Z

4

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.

edited Feb 8, 2011 at 17:57

answered Feb 8, 2011 at 17:47

Bert F

88k12 gold badges114 silver badges126 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

user476033 Over a year ago

Brilliant, thank you very much for the explanation. I always get confused with the .length operator ! :)

Bert F Over a year ago

@user476033 - what should happen when the deque is full and insertFirst is called? should the buffer always expand (in which case capacity is current capacity, not the capacity limit), should an item get dropped, or should the insertFirst fail (possibly fail silently, leaving nothing changed)?

user476033 Over a year ago

the buffer should always expand in this case, with the item in this case being appended onto deque in position [0]. This is not currently working, however! :(

Bert F Over a year ago

@user476033 then capacity is probably redundant with deque.length. when stuff isn't working how you expect, its good to have a good idea of what you want to happen in each method for each key case, and then walk through each method with a debugger during key cases (empty, partly full, full to capacity) and/or use printlns through the code to show/verify what the picture looks like before/after each method call.

Wipqozn · Accepted Answer · 2011-02-08 17:46:06Z

0

I don't have much experience in Java, so I could be off base here but...when you call InsertFirst, no values been set to capacity yet. So it defaults to either 0, or junk. Either way, when you call tempArray = (EltType[]) new Object[capacity+1]; the capacity will either be 1 or...some 'random' number. Hence why are getting outOfBounds. I'm guessing you meant to use CAPACITY?

answered Feb 8, 2011 at 17:46

Wipqozn

1,3442 gold badges17 silver badges32 bronze badges

Comments

troutinator · Accepted Answer · 2011-02-08 17:52:03Z

0

Here is the answer to that particular bug. You aren't updating the instance variable capacity so each time you call insertFirst the temp array array isn't actually growing. So the code should look like:

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

Still, the overal class is far from correct.

answered Feb 8, 2011 at 17:52

troutinator

1,1981 gold badge7 silver badges23 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related