Why am I getting an IndexOutOfBoundsException here?
- by Berzerker
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.");}
}
}
