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

LineHitsSource
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)
51964    {
52964        initialize(comp);
53964    }
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()
612    {
622        initialize(new ComparableComparator());
632    }
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     {
730        this();
740        addAll(c);
750    }
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     {
840        this(comp);
850        addAll(c);
860    }
87     
88     private void initialize(Comparator comp)
89     {
90966        this.comp = comp;
91966        object_indices = new HashMap();
92966        heap = new Vector();
93966    }
94     
95     /**
96      * @see Collection#clear()
97      */
98     public void clear()
99     {
1002        object_indices = new HashMap();
1012        heap = new Vector();
1022    }
103  
104     /**
105      * Inserts <code>o</code> into this collection.
106      */
107     public boolean add(Object o)
108     {
1094847        int i = heap.size(); // index 1 past the end of the heap
1104847        heap.setSize(i+1);
1114847        percolateUp(i, o);
1124847        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     {
1215956        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     {
13081        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     {
1384448        Object top = heap.elementAt(TOP);
1394448        if (top == null)
1400            return top;
141         
1424448        Object bottom_elt = heap.lastElement();
1434448        heap.setElementAt(bottom_elt, TOP);
1444448        object_indices.put(bottom_elt, new Integer(TOP));
145         
1464448        heap.setSize(heap.size() - 1); // remove the last element
1474448        if (heap.size() > 1)
1481751            percolateDown(TOP);
149  
1504448        object_indices.remove(top);
1514448        return top;
152     }
153  
154     /**
155      * Returns the size of this heap.
156      */
157     public int size()
158     {
1599        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         
1741081        int cur = ((Integer)object_indices.get(o)).intValue(); // current index
1751081        int new_idx = percolateUp(cur, o);
1761081        percolateDown(new_idx);
1771081    }
178  
179     /**
180      * @see Collection#contains(java.lang.Object)
181      */
182     public boolean contains(Object o)
183     {
1840        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     {
1954204        int left = lChild(cur);
1964204        int right = rChild(cur);
197         int smallest;
198  
1994204        if ((left < heap.size()) && (comp.compare(heap.elementAt(left), heap.elementAt(cur)) < 0))
2001282            smallest = left;
201         else
2022922            smallest = cur;
203  
2044204        if ((right < heap.size()) && (comp.compare(heap.elementAt(right), heap.elementAt(smallest)) < 0))
205295            smallest = right;
206  
2074204        if (cur != smallest)
208         {
2091372            swap(cur, smallest);
2101372            percolateDown(smallest);
211         }
2124204    }
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     {
2215928        int i = cur;
222         
2237071        while ((i > TOP) && (comp.compare(heap.elementAt(parent(i)), o) > 0))
224         {
2251143            Object parentElt = heap.elementAt(parent(i));
2261143            heap.setElementAt(parentElt, i);
2271143            object_indices.put(parentElt, new Integer(i)); // reset index to i (new location)
2281143            i = parent(i);
229         }
230         
231         // place object in heap at appropriate place
2325928        object_indices.put(o, new Integer(i));
2335928        heap.setElementAt(o, i);
234  
2355928        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     {
2464204        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     {
2574204        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     {
2685989        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     {
2791372        Object iElt = heap.elementAt(i);
2801372        Object jElt = heap.elementAt(j);
281  
2821372        heap.setElementAt(jElt, i);
2831372        object_indices.put(jElt, new Integer(i));
284  
2851372        heap.setElementAt(iElt, j);
2861372        object_indices.put(iElt, new Integer(j));
2871372    }
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     {
3150        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     {
3230        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     {
3310        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     {
3390        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.