Why am I getting an IndexOutOfBoundsException here?

Question

I'm getting an index out of bounds exception thrown and I don't know why, within my replaceValue method below.

[null, (10,4), (52,3), (39,9), (78,7), (63,8), (42,2), (50,411)]

replacement value test:411 size=7

[null, (10,4), (52,3), (39,9), (78,7), (63,8), (42,2), (50,101)]

removal test of :(10,4)

[null, (39,9), (52,3), (42,2), (78,7), (63,8), (50,101)]

size=6

I try to replace the value again here and get an error...

package heappriorityqueue;
import java.util.*;
public class HeapPriorityQueue<K,V> {
protected ArrayList<Entry<K,V>> heap;
protected Comparator<K> comp;
int size = 0;
protected static class MyEntry<K,V> implements Entry<K,V> {
    protected K key;
    protected V value;
    protected int loc;
    public MyEntry(K k, V v,int i) {key = k; value = v;loc =i;}
    public K getKey() {return key;}
    public V getValue() {return value;}
    public int getLoc(){return loc;}
    public String toString() {return "(" + key + "," + value + ")";}
    void setKey(K k1) {key = k1;}
    void setValue(V v1) {value = v1;}
    public void setLoc(int i) {loc = i;}
}
public HeapPriorityQueue() {
    heap = new ArrayList<Entry<K,V>>();
    heap.add(0,null);
    comp = new DefaultComparator<K>();
}
public HeapPriorityQueue(Comparator<K> c) {
    heap = new ArrayList<Entry<K,V>>();
    heap.add(0,null);
    comp = c;
}
public int size() {return size;}
public boolean isEmpty() {return size == 0; }
public Entry<K,V> min() throws EmptyPriorityQueueException {
    if (isEmpty())
        throw new EmptyPriorityQueueException("Priority Queue is Empty");
    return heap.get(1);
}
public Entry<K,V> insert(K k, V v) {
    size++;
    Entry<K,V> entry = new MyEntry<K,V>(k,v,size);
    heap.add(size,entry);
    upHeap(size);
    return entry;
}
public Entry<K,V> removeMin() throws EmptyPriorityQueueException {
    if (isEmpty())
        throw new EmptyPriorityQueueException("Priority Queue is Empty");
    if (size == 1)
        return heap.remove(1);
    Entry<K,V> min = heap.get(1);
    heap.set(1, heap.remove(size));
    size--;
    downHeap(1);
    return min;
}

public V replaceValue(Entry<K,V> e, V v) throws InvalidEntryException,
        EmptyPriorityQueueException {
// replace the value field of entry e in the priority
// queue with the given value v, and return the old value

This is where I am getting the IndexOutOfBounds exception, on heap.get(i);

if (isEmpty()){
        throw new EmptyPriorityQueueException("Priority Queue is Empty.");
    }
    checkEntry(e);
    int i = e.getLoc();
    Entry<K,V> entry=heap.get(((i)));
    V oldVal = entry.getValue();
    K key=entry.getKey();
    Entry<K,V> insert = new MyEntry<K,V>(key,v,i);
    heap.set(i, insert);
    return oldVal;
}

public K replaceKey(Entry<K,V> e, K k) throws InvalidEntryException,
        EmptyPriorityQueueException, InvalidKeyException {
    // replace the key field of entry e in the priority
    // queue with the given key k, and return the old key
    if (isEmpty()){
        throw new EmptyPriorityQueueException("Priority Queue is Empty.");
    }
    checkKey(k);
    checkEntry(e);
    K oldKey=e.getKey();
    int i = e.getLoc();
    Entry<K,V> entry = new MyEntry<K,V>(k,e.getValue(),i);
    heap.set(i,entry);
    downHeap(i);
    upHeap(i);
    return oldKey;
}

public Entry<K,V> remove(Entry<K,V> e) throws InvalidEntryException,
        EmptyPriorityQueueException{
    // remove entry e from priority queue and return it
    if (isEmpty()){
        throw new EmptyPriorityQueueException("Priority Queue is Empty.");
    }
    MyEntry<K,V> entry = checkEntry(e);
    if (size==1){
        return heap.remove(size--);
    }
    int i = e.getLoc();
    heap.set(i, heap.remove(size--));
    downHeap(i);
    return entry;
}

protected void upHeap(int i) {
    while (i > 1) {
        if (comp.compare(heap.get(i/2).getKey(), heap.get(i).getKey()) <= 0)
            break;
        swap(i/2,i);
        i = i/2;
    }
}
protected void downHeap(int i) {
    int smallerChild;
    while (size >= 2*i) {
        smallerChild = 2*i;
        if ( size >= 2*i + 1)
            if (comp.compare(heap.get(2*i + 1).getKey(), heap.get(2*i).getKey()) < 0)
                smallerChild = 2*i+1;
        if (comp.compare(heap.get(i).getKey(), heap.get(smallerChild).getKey()) <= 0)
            break;
        swap(i, smallerChild);
        i = smallerChild;
    }
}
protected void swap(int j, int i) {
    heap.get(j).setLoc(i);
    heap.get(i).setLoc(j);
    Entry<K,V> temp;
    temp = heap.get(j);
    heap.set(j, heap.get(i));
    heap.set(i, temp);

}
public String toString() {
    return heap.toString();
}
protected MyEntry<K,V> checkEntry(Entry<K,V> ent) 
    throws InvalidEntryException 
  {
    if(ent == null || !(ent instanceof MyEntry))
      throw new InvalidEntryException("Invalid entry.");
    return (MyEntry)ent;
  }
protected void checkKey(K key) throws InvalidKeyException{
    try{comp.compare(key,key);}
    catch(Exception e){throw new InvalidKeyException("Invalid key.");}
}

}

HeapPriorityQueue<Integer,Integer> testPQ = new HeapPriorityQueue<Integer,Integer>();
    System.out.print("[");
    int x;
    for (int i = 0; i < 10; i++) {
        x = (int) (100 * Math.random());
        System.out.print(" " + x);
        testPQ.insert(x,i);


    }
    System.out.println("]");

    System.out.println(testPQ);
    for (int i = 0; i < 5; i++) {
        System.out.println(testPQ.removeMin());
        System.out.println(testPQ);
    }

    Entry e = testPQ.insert(10, 4);
    System.out.println("insertion of "+e);
    System.out.println(testPQ);
    System.out.println("size="+testPQ.size);
    System.out.println(e.getKey());
    Entry r = testPQ.insert(50, 411);
    System.out.println("insertion of "+r);

    System.out.println("size="+testPQ.size);
    System.out.println(testPQ);
    System.out.println("replacement value test" + 
            testPQ.replaceValue(r, 101));

    System.out.println("size="+testPQ.size);
    System.out.println(testPQ);
    System.out.println("removal test:"+testPQ.remove(e));
    System.out.println(testPQ);
    System.out.println("replacement value test" + 
            testPQ.replaceValue(r, 201));
    System.out.println("replacement value test" + 
            testPQ.replaceValue(r, 301));
    System.out.println("replacement value test" + 
            testPQ.replaceValue(r, 401));
    System.out.println("size="+testPQ.size);
    System.out.println(testPQ);

    Entry k = testPQ.min();
    System.out.println("replacement key test:"+testPQ.replaceKey(k,77)
            +" w/77");
    System.out.println(testPQ);
    Entry v = testPQ.min();
    System.out.println("replacement key test:"+testPQ.replaceKey(v,6)+
            " w/6");
    System.out.println(testPQ);
    System.out.println("removal test:"+testPQ.remove(v));
    System.out.println(testPQ);

run:
[ 17 86 13 52 98 4 9 25 6 75]
[null, (4,5), (6,8), (9,6), (25,7), (75,9), (17,0), (13,2), (86,1), (52,3), (98,4)]
(4,5)
[null, (6,8), (25,7), (9,6), (52,3), (75,9), (17,0), (13,2), (86,1), (98,4)]
(6,8)
[null, (9,6), (25,7), (13,2), (52,3), (75,9), (17,0), (98,4), (86,1)]
(9,6)
[null, (13,2), (25,7), (17,0), (52,3), (75,9), (86,1), (98,4)]
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 7, Size: 7
(13,2)
[null, (17,0), (25,7), (86,1), (52,3), (75,9), (98,4)]
(17,0)
[null, (25,7), (52,3), (86,1), (98,4), (75,9)]
insertion of (10,4)
[null, (10,4), (52,3), (25,7), (98,4), (75,9), (86,1)]
size=6
10
insertion of (50,411)
size=7
[null, (10,4), (52,3), (25,7), (98,4), (75,9), (86,1), (50,411)]
replacement value test411
size=7
[null, (10,4), (52,3), (25,7), (98,4), (75,9), (86,1), (50,101)]
removal test:(10,4)
[null, (25,7), (52,3), (50,101), (98,4), (75,9), (86,1)]
at java.util.ArrayList.rangeCheck(ArrayList.java:604)
at java.util.ArrayList.get(ArrayList.java:382)
at heappriorityqueue.HeapPriorityQueue.replaceValue(HeapPriorityQueue.java:283)
at heappriorityqueue.Main.main(Main.java:55)

Java Result: 1 BUILD SUCCESSFUL (total time: 0 seconds)

Answer 1

You save the array index of the entry in the entry itself. But in your remove() method you don't change it. You have to change that index for all elements that change position or else you will remove the wrong elements on further remove calls.

In you example (50,101) has index 6 initially. This value stays after the remove, so if you try to replace it, it still tries to access index 6 (because of int i = e.getLoc();) which doesn't exist anymore.