1 pnkfelix 1.1.2.1 // BinHeapPriorityQueue.java, created Tue Jun 1 15:08:45 1999 by pnkfelix
2 cananian 1.1.2.10 // Copyright (C) 1999 Felix S. Klock II <pnkfelix@mit.edu>
3 pnkfelix 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 pnkfelix 1.1.2.1 package harpoon.Util;
5 pnkfelix 1.1.2.1
6 ovy 1.5 import java.util.Arrays;
7 pnkfelix 1.1.2.1 import java.util.AbstractCollection;
8 ovy 1.5 import java.util.HashMap;
9 pnkfelix 1.1.2.1 import java.util.Iterator;
10 ovy 1.5 import java.util.Map;
11 ovy 1.5 import java.util.NoSuchElementException;
12 pnkfelix 1.1.2.1
13 pnkfelix 1.1.2.1 /**
14 pnkfelix 1.1.2.1 * <code>BinHeapPriorityQueue</code> is an implementation of the
15 pnkfelix 1.1.2.1 * <code>PriorityQueue</code> interface. It supports O(1) time
16 pnkfelix 1.1.2.1 * <code>peekMax</code> and O(lg n) time <code>insert</code> and
17 pnkfelix 1.1.2.1 * <code>removeMax</code> operations, assuming that
18 cananian 1.1.2.7 * <code>ArrayList</code> is implemented in a reasonable manner. The
19 pnkfelix 1.1.2.1 * <code>remove</code> operation is probably slow however.
20 pnkfelix 1.1.2.1 *
21 pnkfelix 1.1.2.1 * Look into implementing a FibinocciHeap-based representation if
22 pnkfelix 1.1.2.1 * speed becomes an issue.
23 pnkfelix 1.1.2.1 *
24 cananian 1.1.2.10 * @author Felix S. Klock II <pnkfelix@mit.edu>
25 ovy 1.6 * @version $Id: BinHeapPriorityQueue.java,v 1.6 2002/04/25 00:39:51 ovy Exp $
26 pnkfelix 1.1.2.1 */
27 pnkfelix 1.1.2.1 public class BinHeapPriorityQueue extends AbstractCollection implements MaxPriorityQueue {
28 ovy 1.5 private HashMap item2entry;
29 ovy 1.5 private Entry[] heap;
30 ovy 1.5 private int size;
31 pnkfelix 1.1.2.1
32 ovy 1.5 private final static int DEFAULT_SIZE=16;
33 pnkfelix 1.1.2.1
34 pnkfelix 1.1.2.1 public BinHeapPriorityQueue() {
35 ovy 1.5 this(DEFAULT_SIZE);
36 ovy 1.5 }
37 ovy 1.5
38 ovy 1.5 public BinHeapPriorityQueue(int size) {
39 ovy 1.5 item2entry = new HashMap(size);
40 ovy 1.5 heap = new Entry[size];
41 ovy 1.5 size = 0;
42 ovy 1.5 }
43 ovy 1.5
44 ovy 1.5
45 ovy 1.5 public boolean insert(Object item, int priority) {
46 ovy 1.5
47 ovy 1.5 // already exists? then simply set priority
48 ovy 1.5 if (item2entry.containsKey(item)) {
49 ovy 1.5 return setPriority(item, priority) != priority;
50 ovy 1.5 }
51 ovy 1.5
52 ovy 1.5 ensureCapacity(size+1);
53 ovy 1.5
54 ovy 1.5 Entry entry = new Entry();
55 ovy 1.5 entry.item = item;
56 ovy 1.5 entry.priority = priority;
57 ovy 1.5
58 ovy 1.5 // insert at last position in heap
59 ovy 1.5 entry.heapIndex = size;
60 ovy 1.5 heap[size] = entry;
61 ovy 1.5 size++;
62 ovy 1.5
63 ovy 1.5 // now percolate to go up the hierarchy
64 ovy 1.5 percolate(entry);
65 ovy 1.5
66 ovy 1.5 // the collection has changed
67 ovy 1.5 return true;
68 ovy 1.5 }
69 ovy 1.5
70 ovy 1.5 public int getPriority(Object item) {
71 ovy 1.5 Entry entry = (Entry) item2entry.get(item);
72 ovy 1.5
73 ovy 1.5 if (entry == null) {
74 ovy 1.5 throw new NoSuchElementException(item.toString());
75 ovy 1.5 }
76 ovy 1.5
77 ovy 1.5 return entry.priority;
78 pnkfelix 1.1.2.1 }
79 pnkfelix 1.1.2.1
80 ovy 1.5
81 ovy 1.5 public int setPriority(Object item, int priority) {
82 ovy 1.5 Entry entry = (Entry) item2entry.get(item);
83 ovy 1.5
84 ovy 1.5 if (entry == null) {
85 ovy 1.5 throw new NoSuchElementException(item.toString());
86 ovy 1.5 }
87 ovy 1.5
88 ovy 1.5 int oldPriority = entry.priority;
89 ovy 1.5 entry.priority = priority;
90 ovy 1.5
91 ovy 1.5 priorityChanged(entry, priority - oldPriority);
92 ovy 1.5
93 ovy 1.5 return oldPriority;
94 ovy 1.5 }
95 ovy 1.5
96 ovy 1.5 public void changePriority(Object item, int delta) {
97 ovy 1.5 Entry entry = (Entry) item2entry.get(item);
98 ovy 1.5
99 ovy 1.5 if (entry == null) {
100 ovy 1.5 throw new NoSuchElementException(item.toString());
101 ovy 1.5 }
102 ovy 1.5
103 ovy 1.5 entry.priority += delta;
104 ovy 1.5 priorityChanged(entry, delta);
105 pnkfelix 1.1.2.1 }
106 pnkfelix 1.1.2.1
107 pnkfelix 1.1.2.1 public Object peekMax() {
108 ovy 1.5 return heap[0].item;
109 pnkfelix 1.1.2.1 }
110 ovy 1.5
111 ovy 1.5 public Object deleteMax() {
112 ovy 1.5 if (size == 0) {
113 ovy 1.5 throw new NoSuchElementException("Heap is empty");
114 ovy 1.5 }
115 ovy 1.5
116 ovy 1.5 Object item = heap[0].item;
117 pnkfelix 1.1.2.1
118 ovy 1.5 removeEntry(heap[0]);
119 ovy 1.5
120 ovy 1.5 return item;
121 ovy 1.5 }
122 ovy 1.5
123 ovy 1.5
124 ovy 1.5 public boolean remove(Object item) {
125 ovy 1.5 Entry entry = (Entry) item2entry.get(item);
126 ovy 1.5
127 ovy 1.5 if (entry == null) return false;
128 ovy 1.5
129 ovy 1.5 removeEntry(entry);
130 ovy 1.5
131 ovy 1.5 return true;
132 ovy 1.5 }
133 ovy 1.5
134 ovy 1.5 public boolean contains(Object item) {
135 ovy 1.5 return item2entry.containsKey(item);
136 ovy 1.5 }
137 pnkfelix 1.1.2.2
138 ovy 1.5 public Iterator iterator() {
139 ovy 1.5 return new HeapIterator();
140 pnkfelix 1.1.2.1 }
141 pnkfelix 1.1.2.1
142 pnkfelix 1.1.2.1 public void clear() {
143 ovy 1.5 item2entry.clear();
144 ovy 1.5 Arrays.fill(heap, null);
145 ovy 1.5 size = 0;
146 pnkfelix 1.1.2.1 }
147 ovy 1.5
148 ovy 1.5 public int size() {
149 ovy 1.5 return size;
150 pnkfelix 1.1.2.1 }
151 pnkfelix 1.1.2.1
152 ovy 1.6 public String toString() {
153 ovy 1.6 StringBuffer sb = new StringBuffer("[");
154 ovy 1.6
155 ovy 1.6 for (int i = 0; i<size; i++) {
156 ovy 1.6 sb.append(" (").append(heap[i].item).append(", ")
157 ovy 1.6 .append(heap[i].priority).append(")");
158 ovy 1.6 }
159 ovy 1.6
160 ovy 1.6 return sb.append(" ]").toString();
161 ovy 1.6 }
162 ovy 1.6
163 ovy 1.5 private void removeEntry(Entry entry) {
164 ovy 1.5 Entry last = heap[size - 1];
165 ovy 1.5
166 ovy 1.5 swap(entry, last);
167 ovy 1.6
168 ovy 1.5 heap[size - 1] = null;
169 ovy 1.5 size--;
170 ovy 1.5
171 ovy 1.6 priorityChanged(last, last.priority - entry.priority);
172 ovy 1.6
173 ovy 1.5 item2entry.remove(entry.item);
174 pnkfelix 1.1.2.1 }
175 pnkfelix 1.1.2.1
176 ovy 1.5 private void ensureCapacity(int size) {
177 ovy 1.5 if (heap.length >= size) return;
178 ovy 1.5
179 ovy 1.5 Entry[] newHeap = new Entry[ Math.max(size, heap.length*2) ];
180 ovy 1.5
181 ovy 1.5 System.arraycopy(heap, 0, newHeap, 0, heap.length);
182 ovy 1.5
183 ovy 1.5 heap = newHeap;
184 pnkfelix 1.1.2.1 }
185 ovy 1.5
186 ovy 1.5 private void priorityChanged(Entry entry, int delta) {
187 ovy 1.5 if (delta > 0) {
188 ovy 1.5 // priority has grown, move up
189 ovy 1.5 percolate(entry);
190 ovy 1.5 } else if (delta < 0) {
191 ovy 1.5 // priority has decreased, move down
192 ovy 1.5 siftDown(entry);
193 ovy 1.5 }
194 ovy 1.5 }
195 ovy 1.5
196 ovy 1.5 private void percolate(Entry entry) {
197 ovy 1.5 while (entry.heapIndex > 0) {
198 ovy 1.5 Entry parent = heap[ (entry.heapIndex-1) / 2 ];
199 pnkfelix 1.1.2.1
200 ovy 1.5 // are we better than parent? if not, we're in the right place
201 ovy 1.5 if (entry.priority <= parent.priority) {
202 ovy 1.5 break;
203 ovy 1.5 }
204 ovy 1.5
205 ovy 1.5 swap(parent, entry);
206 ovy 1.5 }
207 pnkfelix 1.1.2.1 }
208 pnkfelix 1.1.2.1
209 ovy 1.5 private void siftDown(Entry entry) {
210 ovy 1.5 while (entry.heapIndex*2 + 1 < size) {
211 ovy 1.5 Entry leftSon = heap[entry.heapIndex*2 + 1];
212 ovy 1.5 Entry rightSon = entry.heapIndex*2 + 2 < size ?
213 ovy 1.5 heap[entry.heapIndex*2 + 2] : null;
214 ovy 1.5
215 ovy 1.5 Entry maxSon =
216 ovy 1.5 (rightSon == null || leftSon.priority > rightSon.priority) ?
217 ovy 1.5 leftSon : rightSon;
218 ovy 1.5
219 ovy 1.5 // are we better than our best son? if so, we're in the right place
220 ovy 1.5 if (entry.priority >= maxSon.priority) {
221 ovy 1.5 break;
222 ovy 1.5 }
223 ovy 1.5
224 ovy 1.5 swap(entry, maxSon);
225 ovy 1.5 }
226 pnkfelix 1.1.2.1 }
227 pnkfelix 1.1.2.1
228 ovy 1.5
229 ovy 1.5 private void swap(Entry e1, Entry e2) {
230 ovy 1.5 int e1_index = e1.heapIndex;
231 ovy 1.5 int e2_index = e2.heapIndex;
232 ovy 1.5
233 ovy 1.5 e1.heapIndex = e2_index;
234 ovy 1.5 heap[e2_index] = e1;
235 ovy 1.5
236 ovy 1.5 e2.heapIndex = e1_index;
237 ovy 1.5 heap[e1_index] = e2;
238 pnkfelix 1.1.2.1 }
239 pnkfelix 1.1.2.1
240 ovy 1.5
241 pnkfelix 1.1.2.1
242 ovy 1.5 class Entry {
243 ovy 1.5 int priority;
244 ovy 1.5 int heapIndex;
245 ovy 1.5 Object item;
246 ovy 1.5 }
247 ovy 1.5
248 ovy 1.5 // wrapper around the hashMap's entry iterator
249 ovy 1.5 class HeapIterator implements Iterator {
250 ovy 1.5 Iterator hashIterator;
251 ovy 1.5 Entry current;
252 ovy 1.5
253 ovy 1.5 HeapIterator() {
254 ovy 1.5 hashIterator = item2entry.entrySet().iterator();
255 ovy 1.5 }
256 ovy 1.5
257 ovy 1.5 public boolean hasNext() {
258 ovy 1.5 return hashIterator.hasNext();
259 ovy 1.5 }
260 ovy 1.5
261 ovy 1.5 public Object next() {
262 ovy 1.5 Map.Entry hashEntry = ((Map.Entry) hashIterator.next());
263 ovy 1.5 current = (Entry) hashEntry.getValue();
264 ovy 1.5 return hashEntry.getKey();
265 ovy 1.5 }
266 ovy 1.5
267 ovy 1.5 public void remove() {
268 ovy 1.5 hashIterator.remove();
269 ovy 1.5 removeEntry(current);
270 ovy 1.5 }
271 pnkfelix 1.1.2.1 }
272 cananian 1.2 }