# Coverage details for edu.uci.ics.jung.utils.MapBinaryHeap

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. visit www.jcoverage.com for updates. | copyright © 2003, jcoverage ltd. all rights reserved. Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.