Line | Hits | Source |
---|---|---|
1 | /* | |
2 | * Copyright (c) 2003, the JUNG Project and the Regents of the University | |
3 | * of California | |
4 | * All rights reserved. | |
5 | * | |
6 | * This software is open-source under the BSD license; see either | |
7 | * "license.txt" or | |
8 | * http://jung.sourceforge.net/license.txt for a description. | |
9 | */ | |
10 | /* | |
11 | * | |
12 | * Created on Oct 29, 2003 | |
13 | */ | |
14 | package edu.uci.ics.jung.utils; | |
15 | ||
16 | import java.util.AbstractCollection; | |
17 | import java.util.Collection; | |
18 | import java.util.Comparator; | |
19 | import java.util.HashMap; | |
20 | import java.util.Iterator; | |
21 | import java.util.NoSuchElementException; | |
22 | import java.util.Vector; | |
23 | ||
24 | import org.apache.commons.collections.IteratorUtils; | |
25 | ||
26 | /** | |
27 | * An array-based binary heap implementation of a priority queue, | |
28 | * which also provides | |
29 | * efficient <code>update()</code> and <code>contains</code> operations. | |
30 | * It contains extra infrastructure (a hash table) to keep track of the | |
31 | * position of each element in the array; thus, if the key value of an element | |
32 | * changes, it may be "resubmitted" to the heap via <code>update</code> | |
33 | * so that the heap can reposition it efficiently, as necessary. | |
34 | * | |
35 | * @author Joshua O'Madadhain | |
36 | */ | |
37 | public class MapBinaryHeap | |
38 | extends AbstractCollection | |
39 | implements Collection | |
40 | { | |
41 | private Vector heap; // holds the heap as an implicit binary tree | |
42 | private HashMap object_indices; // maps each object in the heap to its index in the heap | |
43 | private Comparator comp; | |
44 | private final static int TOP = 0; // the index of the top of the heap | |
45 | ||
46 | /** | |
47 | * Creates a <code>MapBinaryHeap</code> whose heap ordering | |
48 | * is based on the ordering of the elements specified by <code>c</code>. | |
49 | */ | |
50 | public MapBinaryHeap(Comparator comp) | |
51 | 964 | { |
52 | 964 | initialize(comp); |
53 | 964 | } |
54 | ||
55 | /** | |
56 | * Creates a <code>MapBinaryHeap</code> whose heap ordering | |
57 | * will be based on the <i>natural ordering</i> of the elements, | |
58 | * which must be <code>Comparable</code>. | |
59 | */ | |
60 | public MapBinaryHeap() | |
61 | 2 | { |
62 | 2 | initialize(new ComparableComparator()); |
63 | 2 | } |
64 | ||
65 | /** | |
66 | * Creates a <code>MapBinaryHeap</code> based on the specified | |
67 | * collection whose heap ordering | |
68 | * will be based on the <i>natural ordering</i> of the elements, | |
69 | * which must be <code>Comparable</code>. | |
70 | */ | |
71 | public MapBinaryHeap(Collection c) | |
72 | { | |
73 | 0 | this(); |
74 | 0 | addAll(c); |
75 | 0 | } |
76 | ||
77 | /** | |
78 | * Creates a <code>MapBinaryHeap</code> based on the specified collection | |
79 | * whose heap ordering | |
80 | * is based on the ordering of the elements specified by <code>c</code>. | |
81 | */ | |
82 | public MapBinaryHeap(Collection c, Comparator comp) | |
83 | { | |
84 | 0 | this(comp); |
85 | 0 | addAll(c); |
86 | 0 | } |
87 | ||
88 | private void initialize(Comparator comp) | |
89 | { | |
90 | 966 | this.comp = comp; |
91 | 966 | object_indices = new HashMap(); |
92 | 966 | heap = new Vector(); |
93 | 966 | } |
94 | ||
95 | /** | |
96 | * @see Collection#clear() | |
97 | */ | |
98 | public void clear() | |
99 | { | |
100 | 2 | object_indices = new HashMap(); |
101 | 2 | heap = new Vector(); |
102 | 2 | } |
103 | ||
104 | /** | |
105 | * Inserts <code>o</code> into this collection. | |
106 | */ | |
107 | public boolean add(Object o) | |
108 | { | |
109 | 4847 | int i = heap.size(); // index 1 past the end of the heap |
110 | 4847 | heap.setSize(i+1); |
111 | 4847 | percolateUp(i, o); |
112 | 4847 | return true; |
113 | } | |
114 | ||
115 | /** | |
116 | * Returns <code>true</code> if this collection contains no elements, and | |
117 | * <code>false</code> otherwise. | |
118 | */ | |
119 | public boolean isEmpty() | |
120 | { | |
121 | 5956 | return heap.isEmpty(); |
122 | } | |
123 | ||
124 | /** | |
125 | * Returns the element at the top of the heap; does not | |
126 | * alter the heap. | |
127 | */ | |
128 | public Object peek() throws NoSuchElementException | |
129 | { | |
130 | 81 | return heap.elementAt(TOP); |
131 | } | |
132 | ||
133 | /** | |
134 | * Removes the element at the top of this heap, and returns it. | |
135 | */ | |
136 | public Object pop() throws NoSuchElementException | |
137 | { | |
138 | 4448 | Object top = heap.elementAt(TOP); |
139 | 4448 | if (top == null) |
140 | 0 | return top; |
141 | ||
142 | 4448 | Object bottom_elt = heap.lastElement(); |
143 | 4448 | heap.setElementAt(bottom_elt, TOP); |
144 | 4448 | object_indices.put(bottom_elt, new Integer(TOP)); |
145 | ||
146 | 4448 | heap.setSize(heap.size() - 1); // remove the last element |
147 | 4448 | if (heap.size() > 1) |
148 | 1751 | percolateDown(TOP); |
149 | ||
150 | 4448 | object_indices.remove(top); |
151 | 4448 | return top; |
152 | } | |
153 | ||
154 | /** | |
155 | * Returns the size of this heap. | |
156 | */ | |
157 | public int size() | |
158 | { | |
159 | 9 | return heap.size(); |
160 | } | |
161 | ||
162 | /** | |
163 | * Informs the heap that this object's internal key value has been | |
164 | * updated, and that its place in the heap may need to be shifted | |
165 | * (up or down). | |
166 | * @param o | |
167 | */ | |
168 | public void update(Object o) | |
169 | { | |
170 | // Since we don't know whether the key value increased or | |
171 | // decreased, we just percolate up followed by percolating down; | |
172 | // one of the two will have no effect. | |
173 | ||
174 | 1081 | int cur = ((Integer)object_indices.get(o)).intValue(); // current index |
175 | 1081 | int new_idx = percolateUp(cur, o); |
176 | 1081 | percolateDown(new_idx); |
177 | 1081 | } |
178 | ||
179 | /** | |
180 | * @see Collection#contains(java.lang.Object) | |
181 | */ | |
182 | public boolean contains(Object o) | |
183 | { | |
184 | 0 | return object_indices.containsKey(o); |
185 | } | |
186 | ||
187 | /** | |
188 | * Moves the element at position <code>cur</code> closer to | |
189 | * the bottom of the heap, or returns if no further motion is | |
190 | * necessary. Calls itself recursively if further motion is | |
191 | * possible. | |
192 | */ | |
193 | private void percolateDown(int cur) | |
194 | { | |
195 | 4206 | int left = lChild(cur); |
196 | 4206 | int right = rChild(cur); |
197 | int smallest; | |
198 | ||
199 | 4206 | if ((left < heap.size()) && (comp.compare(heap.elementAt(left), heap.elementAt(cur)) < 0)) |
200 | 1284 | smallest = left; |
201 | else | |
202 | 2922 | smallest = cur; |
203 | ||
204 | 4206 | if ((right < heap.size()) && (comp.compare(heap.elementAt(right), heap.elementAt(smallest)) < 0)) |
205 | 296 | smallest = right; |
206 | ||
207 | 4206 | if (cur != smallest) |
208 | { | |
209 | 1374 | swap(cur, smallest); |
210 | 1374 | percolateDown(smallest); |
211 | } | |
212 | 4206 | } |
213 | ||
214 | /** | |
215 | * Moves the element <code>o</code> at position <code>cur</code> | |
216 | * as high as it can go in the heap. Returns the new position of the | |
217 | * element in the heap. | |
218 | */ | |
219 | private int percolateUp(int cur, Object o) | |
220 | { | |
221 | 5928 | int i = cur; |
222 | ||
223 | 7071 | while ((i > TOP) && (comp.compare(heap.elementAt(parent(i)), o) > 0)) |
224 | { | |
225 | 1143 | Object parentElt = heap.elementAt(parent(i)); |
226 | 1143 | heap.setElementAt(parentElt, i); |
227 | 1143 | object_indices.put(parentElt, new Integer(i)); // reset index to i (new location) |
228 | 1143 | i = parent(i); |
229 | } | |
230 | ||
231 | // place object in heap at appropriate place | |
232 | 5928 | object_indices.put(o, new Integer(i)); |
233 | 5928 | heap.setElementAt(o, i); |
234 | ||
235 | 5928 | return i; |
236 | } | |
237 | ||
238 | /** | |
239 | * Returns the index of the left child of the element at | |
240 | * index <code>i</code> of the heap. | |
241 | * @param i | |
242 | * @return | |
243 | */ | |
244 | private int lChild(int i) | |
245 | { | |
246 | 4206 | return (i<<1) + 1; |
247 | } | |
248 | ||
249 | /** | |
250 | * Returns the index of the right child of the element at | |
251 | * index <code>i</code> of the heap. | |
252 | * @param i | |
253 | * @return | |
254 | */ | |
255 | private int rChild(int i) | |
256 | { | |
257 | 4206 | return (i<<1) + 2; |
258 | } | |
259 | ||
260 | /** | |
261 | * Returns the index of the parent of the element at | |
262 | * index <code>i</code> of the heap. | |
263 | * @param i | |
264 | * @return | |
265 | */ | |
266 | private int parent(int i) | |
267 | { | |
268 | 5986 | return (i-1)>>1; |
269 | } | |
270 | ||
271 | /** | |
272 | * Swaps the positions of the elements at indices <code>i</code> | |
273 | * and <code>j</code> of the heap. | |
274 | * @param i | |
275 | * @param j | |
276 | */ | |
277 | private void swap(int i, int j) | |
278 | { | |
279 | 1374 | Object iElt = heap.elementAt(i); |
280 | 1374 | Object jElt = heap.elementAt(j); |
281 | ||
282 | 1374 | heap.setElementAt(jElt, i); |
283 | 1374 | object_indices.put(jElt, new Integer(i)); |
284 | ||
285 | 1374 | heap.setElementAt(iElt, j); |
286 | 1374 | object_indices.put(iElt, new Integer(j)); |
287 | 1374 | } |
288 | ||
289 | /** | |
290 | * Comparator used if none is specified in the constructor. | |
291 | * @author Joshua O'Madadhain | |
292 | */ | |
293 | private class ComparableComparator implements Comparator | |
294 | { | |
295 | /** | |
296 | * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object) | |
297 | */ | |
298 | public int compare(Object arg0, Object arg1) | |
299 | { | |
300 | if (!(arg0 instanceof Comparable) || !(arg1 instanceof Comparable)) | |
301 | throw new IllegalArgumentException("Arguments must be Comparable"); | |
302 | Comparable i1 = (Comparable)arg0; | |
303 | Comparable i2 = (Comparable)arg1; | |
304 | ||
305 | return i1.compareTo(i2); | |
306 | } | |
307 | } | |
308 | ||
309 | /** | |
310 | * Returns an <code>Iterator</code> that does not support modification | |
311 | * of the heap. | |
312 | */ | |
313 | public Iterator iterator() | |
314 | { | |
315 | 0 | return IteratorUtils.unmodifiableIterator(heap.iterator()); |
316 | } | |
317 | ||
318 | /** | |
319 | * This data structure does not support the removal of arbitrary elements. | |
320 | */ | |
321 | public boolean remove(Object o) | |
322 | { | |
323 | 0 | throw new UnsupportedOperationException(); |
324 | } | |
325 | ||
326 | /** | |
327 | * This data structure does not support the removal of arbitrary elements. | |
328 | */ | |
329 | public boolean removeAll(Collection c) | |
330 | { | |
331 | 0 | throw new UnsupportedOperationException(); |
332 | } | |
333 | ||
334 | /** | |
335 | * This data structure does not support the removal of arbitrary elements. | |
336 | */ | |
337 | public boolean retainAll(Collection c) | |
338 | { | |
339 | 0 | throw new UnsupportedOperationException(); |
340 | } | |
341 | ||
342 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |