<![CDATA[
::::::::::::::
WrappedObj.java
::::::::::::::
// Gary Yngve 10/20/05
public class WrappedObj {
public Object obj;
public int loc;
public WrappedObj(Object obj) {
this.obj = obj;
loc = -1;
}
}
::::::::::::::
LocationAwarePriorityQueue.java
::::::::::::::
// Gary Yngve 10/20/05
public interface LocationAwarePriorityQueue {
public void insert(WrappedObj o, int key);
public WrappedObj removeMin();
public WrappedObj min();
public int size();
public void remove(WrappedObj o);
public void replaceKey(WrappedObj o, int newKey);
public void replaceValue(WrappedObj o, WrappedObj n);
}
::::::::::::::
HeapLocAwarePQ.java
::::::::::::::
// Gary Yngve 10/20/2005
import java.util.*;
public class HeapLocAwarePQ implements LocationAwarePriorityQueue {
private static class PQElement {
WrappedObj obj;
int key;
public PQElement(WrappedObj obj, int key) {
this.obj = obj;
this.key = key;
}
}
private static final int DEFAULT_CAPACITY = 100;
// capacity-growing not implemented right now
private PQElement[] data;
private int size = 0;
public HeapLocAwarePQ() {
data = new PQElement[DEFAULT_CAPACITY];
}
public int size() {
return size;
}
public void insert(WrappedObj o, int key) {
size++;
data[size] = new PQElement(o,key);
o.loc = size;
percolateUp(size);
}
public WrappedObj min() {
if (size < 1)
throw new NoSuchElementException("No elements in the heap");
return data[1].obj;
}
public WrappedObj removeMin() {
if (size < 1)
throw new NoSuchElementException("No elements in the heap");
WrappedObj wanted = data[1].obj;
wanted.loc = -1;
data[1] = data[size];
size--;
percolateDown(1);
return wanted;
}
public void remove(WrappedObj o) {
WrappedObj w = data[o.loc].obj;
if (o != w) throw new IllegalStateException("Location incorrect");
data[o.loc] = data[size];
size--;
percolateUp(o.loc);
percolateDown(o.loc);
o.loc = -1;
}
public void replaceKey(WrappedObj o, int key) {
WrappedObj w = data[o.loc].obj;
if (o != w) throw new IllegalStateException("Location incorrect");
data[o.loc].key = key;
percolateUp(o.loc);
percolateDown(o.loc);
}
public void replaceValue(WrappedObj o, WrappedObj n) {
WrappedObj w = data[o.loc].obj;
if (o != w) throw new IllegalStateException("Location incorrect");
n.loc = o.loc;
data[o.loc].obj = n;
w.loc = -1;
}
private void percolateUp(int index) {
while (index/2 > 0 && data[index].key < data[index/2].key) {
swap (index,index/2);
index = index/2;
}
}
private void percolateDown(int index) {
while (index*2 <= size) {
int smallerChildIndex = index*2;
if (index*2+1 <= size &&
data[index*2].key > data[index*2+1].key)
smallerChildIndex = index*2+1;
if (data[index].key > data[smallerChildIndex].key) {
swap(index,smallerChildIndex);
}
index = smallerChildIndex;
}
}
private void swap(int index1, int index2) {
PQElement temp = data[index1];
data[index1] = data[index2];
data[index2] = temp;
data[index1].obj.loc = index1;
data[index2].obj.loc = index2;
}
}
::::::::::::::
LocAwareTest.java
::::::::::::::
// Gary Yngve 10/20/05
import java.util.*;
public class LocAwareTest {
public static void main(String[] args) {
String[] arr = {"Alaska", "Bavaria", "Karakoram", "London",
"New Zealand", "Paris", "Patagonia"};
LocationAwarePriorityQueue pq = new HeapLocAwarePQ();
Map m = new TreeMap();
for(int i=0;i<arr.length;i++)
m.put(arr[i],new WrappedObj(arr[i]));
pq.insert((WrappedObj)m.get("Bavaria"),6);
pq.insert((WrappedObj)m.get("London"),5);
pq.insert((WrappedObj)m.get("Karakoram"),9);
pq.insert((WrappedObj)m.get("Paris"),7);
pq.insert((WrappedObj)m.get("Patagonia"),10);
pq.insert((WrappedObj)m.get("New Zealand"),12);
pq.replaceKey((WrappedObj)m.get("Karakoram"),14);
pq.insert((WrappedObj)m.get("Alaska"),6);
pq.replaceKey((WrappedObj)m.get("Paris"),1);
pq.remove((WrappedObj)m.get("London"));
System.out.println(pq.removeMin().obj);
System.out.println(pq.removeMin().obj);
System.out.println(pq.removeMin().obj);
System.out.println(pq.removeMin().obj);
}
}
]]>