| 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 | 4204 | int left = lChild(cur); |
| 196 | 4204 | int right = rChild(cur); |
| 197 | int smallest; | |
| 198 | ||
| 199 | 4204 | if ((left < heap.size()) && (comp.compare(heap.elementAt(left), heap.elementAt(cur)) < 0)) |
| 200 | 1282 | smallest = left; |
| 201 | else | |
| 202 | 2922 | smallest = cur; |
| 203 | ||
| 204 | 4204 | if ((right < heap.size()) && (comp.compare(heap.elementAt(right), heap.elementAt(smallest)) < 0)) |
| 205 | 295 | smallest = right; |
| 206 | ||
| 207 | 4204 | if (cur != smallest) |
| 208 | { | |
| 209 | 1372 | swap(cur, smallest); |
| 210 | 1372 | percolateDown(smallest); |
| 211 | } | |
| 212 | 4204 | } |
| 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 | 4204 | 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 | 4204 | 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 | 5989 | 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 | 1372 | Object iElt = heap.elementAt(i); |
| 280 | 1372 | Object jElt = heap.elementAt(j); |
| 281 | ||
| 282 | 1372 | heap.setElementAt(jElt, i); |
| 283 | 1372 | object_indices.put(jElt, new Integer(i)); |
| 284 | ||
| 285 | 1372 | heap.setElementAt(iElt, j); |
| 286 | 1372 | object_indices.put(iElt, new Integer(j)); |
| 287 | 1372 | } |
| 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. |