third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/MapBinaryHeap.java

   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.algorithms.util;
  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.Map;
  22 import java.util.NoSuchElementException;
  23 import java.util.Queue;
  24 import java.util.Vector;
  25
  26 import org.apache.commons.collections15.IteratorUtils;
  27
  28 /**
  29  * An array-based binary heap implementation of a priority queue,
  30  * which also provides
  31  * efficient <code>update()</code> and <code>contains</code> operations.
  32  * It contains extra infrastructure (a hash table) to keep track of the
  33  * position of each element in the array; thus, if the key value of an element
  34  * changes, it may be "resubmitted" to the heap via <code>update</code>
  35  * so that the heap can reposition it efficiently, as necessary.
  36  *
  37  * @author Joshua O'Madadhain
  38  */
  39 public class MapBinaryHeap<T>
  40     extends AbstractCollection<T>
  41     implements Queue<T>
  42 {
  43         private Vector<T> heap = new Vector<T>();            // holds the heap as an implicit binary tree
  44     private Map<T,Integer> object_indices = new HashMap<T,Integer>(); // maps each object in the heap to its index in the heap
  45     private Comparator<T> comp;
  46     private final static int TOP = 0;   // the index of the top of the heap
  47
  48     /**
  49      * Creates a <code>MapBinaryHeap</code> whose heap ordering
  50      * is based on the ordering of the elements specified by <code>c</code>.
  51      */
  52     public MapBinaryHeap(Comparator<T> comp)
  53     {
  54         initialize(comp);
  55     }
  56
  57     /**
  58      * Creates a <code>MapBinaryHeap</code> whose heap ordering
  59      * will be based on the <i>natural ordering</i> of the elements,
  60      * which must be <code>Comparable</code>.
  61      */
  62     public MapBinaryHeap()
  63     {
  64         initialize(new ComparableComparator());
  65     }
  66
  67     /**
  68      * Creates a <code>MapBinaryHeap</code> based on the specified
  69      * collection whose heap ordering
  70      * will be based on the <i>natural ordering</i> of the elements,
  71      * which must be <code>Comparable</code>.
  72      */
  73     public MapBinaryHeap(Collection<T> c)
  74     {
  75         this();
  76         addAll(c);
  77     }
  78
  79     /**
  80      * Creates a <code>MapBinaryHeap</code> based on the specified collection
  81      * whose heap ordering
  82      * is based on the ordering of the elements specified by <code>c</code>.
  83      */
  84     public MapBinaryHeap(Collection<T> c, Comparator<T> comp)
  85     {
  86         this(comp);
  87         addAll(c);
  88     }
  89
  90     private void initialize(Comparator<T> comp)
  91     {
  92         this.comp = comp;
  93         clear();
  94     }
  95
  96         /**
  97          * @see Collection#clear()
  98          */
  99         @Override
 100         public void clear()
 101         {
 102         object_indices.clear();
 103         heap.clear();
 104         }
 105
 106         /**
 107          * Inserts <code>o</code> into this collection.
 108          */
 109         @Override
 110         public boolean add(T o)
 111         {
 112         int i = heap.size();  // index 1 past the end of the heap
 113         heap.setSize(i+1);
 114         percolateUp(i, o);
 115         return true;
 116         }
 117
 118         /**
 119          * Returns <code>true</code> if this collection contains no elements, and
 120      * <code>false</code> otherwise.
 121          */
 122         @Override
 123         public boolean isEmpty()
 124         {
 125         return heap.isEmpty();
 126         }
 127
 128         /**
 129          * Returns the element at the top of the heap; does not
 130      * alter the heap.
 131          */
 132         public T peek()
 133         {
 134                 if (heap.size() > 0)
 135                         return heap.elementAt(TOP);
 136                 else
 137                         return null;
 138         }
 139
 140         /**
 141          * Removes the element at the top of this heap, and returns it.
 142          * @deprecated Use {@link MapBinaryHeap#poll()}
 143          * or {@link MapBinaryHeap#remove()} instead.
 144          */
 145         @Deprecated
 146     public T pop() throws NoSuchElementException
 147         {
 148                 return this.remove();
 149         }
 150
 151     /**
 152      * Returns the size of this heap.
 153      */
 154     @Override
 155     public int size()
 156     {
 157         return heap.size();
 158     }
 159
 160     /**
 161      * Informs the heap that this object's internal key value has been
 162      * updated, and that its place in the heap may need to be shifted
 163      * (up or down).
 164      * @param o
 165      */
 166     public void update(T o)
 167     {
 168         // Since we don't know whether the key value increased or
 169         // decreased, we just percolate up followed by percolating down;
 170         // one of the two will have no effect.
 171
 172         int cur = object_indices.get(o).intValue(); // current index
 173         int new_idx = percolateUp(cur, o);
 174         percolateDown(new_idx);
 175     }
 176
 177     /**
 178      * @see Collection#contains(java.lang.Object)
 179      */
 180     @Override
 181     public boolean contains(Object o)
 182     {
 183         return object_indices.containsKey(o);
 184     }
 185
 186     /**
 187      * Moves the element at position <code>cur</code> closer to
 188      * the bottom of the heap, or returns if no further motion is
 189      * necessary.  Calls itself recursively if further motion is
 190      * possible.
 191      */
 192     private void percolateDown(int cur)
 193     {
 194         int left = lChild(cur);
 195         int right = rChild(cur);
 196         int smallest;
 197
 198         if ((left < heap.size()) &&
 199                         (comp.compare(heap.elementAt(left), heap.elementAt(cur)) < 0)) {
 200                         smallest = left;
 201                 } else {
 202                         smallest = cur;
 203                 }
 204
 205         if ((right < heap.size()) &&
 206                         (comp.compare(heap.elementAt(right), heap.elementAt(smallest)) < 0)) {
 207                         smallest = right;
 208                 }
 209
 210         if (cur != smallest)
 211         {
 212             swap(cur, smallest);
 213             percolateDown(smallest);
 214         }
 215     }
 216
 217     /**
 218      * Moves the element <code>o</code> at position <code>cur</code>
 219      * as high as it can go in the heap.  Returns the new position of the
 220      * element in the heap.
 221      */
 222     private int percolateUp(int cur, T o)
 223     {
 224         int i = cur;
 225
 226         while ((i > TOP) && (comp.compare(heap.elementAt(parent(i)), o) > 0))
 227         {
 228             T parentElt = heap.elementAt(parent(i));
 229             heap.setElementAt(parentElt, i);
 230             object_indices.put(parentElt, new Integer(i));  // reset index to i (new location)
 231             i = parent(i);
 232         }
 233
 234         // place object in heap at appropriate place
 235         object_indices.put(o, new Integer(i));
 236         heap.setElementAt(o, i);
 237
 238         return i;
 239     }
 240
 241     /**
 242      * Returns the index of the left child of the element at
 243      * index <code>i</code> of the heap.
 244      * @param i
 245      * @return the index of the left child of the element at
 246      * index <code>i</code> of the heap
 247      */
 248     private int lChild(int i)
 249     {
 250         return (i<<1) + 1;
 251     }
 252
 253     /**
 254      * Returns the index of the right child of the element at
 255      * index <code>i</code> of the heap.
 256      * @param i
 257      * @return the index of the right child of the element at
 258      * index <code>i</code> of the heap
 259      */
 260     private int rChild(int i)
 261     {
 262         return (i<<1) + 2;
 263     }
 264
 265     /**
 266      * Returns the index of the parent of the element at
 267      * index <code>i</code> of the heap.
 268      * @param i
 269      * @return the index of the parent of the element at index i of the heap
 270      */
 271     private int parent(int i)
 272     {
 273         return (i-1)>>1;
 274     }
 275
 276     /**
 277      * Swaps the positions of the elements at indices <code>i</code>
 278      * and <code>j</code> of the heap.
 279      * @param i
 280      * @param j
 281      */
 282     private void swap(int i, int j)
 283     {
 284         T iElt = heap.elementAt(i);
 285         T jElt = heap.elementAt(j);
 286
 287         heap.setElementAt(jElt, i);
 288         object_indices.put(jElt, new Integer(i));
 289
 290         heap.setElementAt(iElt, j);
 291         object_indices.put(iElt, new Integer(j));
 292     }
 293
 294     /**
 295      * Comparator used if none is specified in the constructor.
 296      * @author Joshua O'Madadhain
 297      */
 298     private class ComparableComparator implements Comparator<T>
 299     {
 300         /**
 301          * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
 302          */
 303         @SuppressWarnings("unchecked")
 304         public int compare(T arg0, T arg1)
 305         {
 306             if (!(arg0 instanceof Comparable) || !(arg1 instanceof Comparable))
 307                 throw new IllegalArgumentException("Arguments must be Comparable");
 308
 309             return ((Comparable<T>)arg0).compareTo(arg1);
 310         }
 311     }
 312
 313     /**
 314      * Returns an <code>Iterator</code> that does not support modification
 315      * of the heap.
 316      */
 317     @Override
 318     public Iterator<T> iterator()
 319     {
 320         return IteratorUtils.<T>unmodifiableIterator(heap.iterator());
 321     }
 322
 323     /**
 324      * This data structure does not support the removal of arbitrary elements.
 325      */
 326     @Override
 327     public boolean remove(Object o)
 328     {
 329         throw new UnsupportedOperationException();
 330     }
 331
 332     /**
 333      * This data structure does not support the removal of arbitrary elements.
 334      */
 335     @Override
 336     public boolean removeAll(Collection<?> c)
 337     {
 338         throw new UnsupportedOperationException();
 339     }
 340
 341     /**
 342      * This data structure does not support the removal of arbitrary elements.
 343      */
 344     @Override
 345     public boolean retainAll(Collection<?> c)
 346     {
 347         throw new UnsupportedOperationException();
 348     }
 349
 350         public T element() throws NoSuchElementException
 351         {
 352                 T top = this.peek();
 353                 if (top == null)
 354                         throw new NoSuchElementException();
 355                 return top;
 356         }
 357
 358         public boolean offer(T o)
 359         {
 360                 return add(o);
 361         }
 362
 363         public T poll()
 364         {
 365         T top = this.peek();
 366         if (top != null)
 367         {
 368                 T bottom_elt = heap.lastElement();
 369                 heap.setElementAt(bottom_elt, TOP);
 370                 object_indices.put(bottom_elt, new Integer(TOP));
 371
 372                 heap.setSize(heap.size() - 1);  // remove the last element
 373                 if (heap.size() > 1)
 374                         percolateDown(TOP);
 375
 376                 object_indices.remove(top);
 377         }
 378         return top;
 379         }
 380
 381         public T remove()
 382         {
 383                 T top = this.poll();
 384                 if (top == null)
 385                         throw new NoSuchElementException();
 386                 return top;
 387         }
 388
 389 }