--- /dev/null
+/*
+ * Copyright (c) 2003, the JUNG Project and the Regents of the University
+ * of California
+ * All rights reserved.
+ *
+ * This software is open-source under the BSD license; see either
+ * "license.txt" or
+ * http://jung.sourceforge.net/license.txt for a description.
+ */
+/*
+ *
+ * Created on Oct 29, 2003
+ */
+package edu.uci.ics.jung.algorithms.util;
+
+import java.util.AbstractCollection;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.Queue;
+import java.util.Vector;
+
+import org.apache.commons.collections15.IteratorUtils;
+
+/**
+ * An array-based binary heap implementation of a priority queue,
+ * which also provides
+ * efficient <code>update()</code> and <code>contains</code> operations.
+ * It contains extra infrastructure (a hash table) to keep track of the
+ * position of each element in the array; thus, if the key value of an element
+ * changes, it may be "resubmitted" to the heap via <code>update</code>
+ * so that the heap can reposition it efficiently, as necessary.
+ *
+ * @author Joshua O'Madadhain
+ */
+public class MapBinaryHeap<T>
+ extends AbstractCollection<T>
+ implements Queue<T>
+{
+ private Vector<T> heap = new Vector<T>(); // holds the heap as an implicit binary tree
+ private Map<T,Integer> object_indices = new HashMap<T,Integer>(); // maps each object in the heap to its index in the heap
+ private Comparator<T> comp;
+ private final static int TOP = 0; // the index of the top of the heap
+
+ /**
+ * Creates a <code>MapBinaryHeap</code> whose heap ordering
+ * is based on the ordering of the elements specified by <code>c</code>.
+ */
+ public MapBinaryHeap(Comparator<T> comp)
+ {
+ initialize(comp);
+ }
+
+ /**
+ * Creates a <code>MapBinaryHeap</code> whose heap ordering
+ * will be based on the <i>natural ordering</i> of the elements,
+ * which must be <code>Comparable</code>.
+ */
+ public MapBinaryHeap()
+ {
+ initialize(new ComparableComparator());
+ }
+
+ /**
+ * Creates a <code>MapBinaryHeap</code> based on the specified
+ * collection whose heap ordering
+ * will be based on the <i>natural ordering</i> of the elements,
+ * which must be <code>Comparable</code>.
+ */
+ public MapBinaryHeap(Collection<T> c)
+ {
+ this();
+ addAll(c);
+ }
+
+ /**
+ * Creates a <code>MapBinaryHeap</code> based on the specified collection
+ * whose heap ordering
+ * is based on the ordering of the elements specified by <code>c</code>.
+ */
+ public MapBinaryHeap(Collection<T> c, Comparator<T> comp)
+ {
+ this(comp);
+ addAll(c);
+ }
+
+ private void initialize(Comparator<T> comp)
+ {
+ this.comp = comp;
+ clear();
+ }
+
+ /**
+ * @see Collection#clear()
+ */
+ @Override
+ public void clear()
+ {
+ object_indices.clear();
+ heap.clear();
+ }
+
+ /**
+ * Inserts <code>o</code> into this collection.
+ */
+ @Override
+ public boolean add(T o)
+ {
+ int i = heap.size(); // index 1 past the end of the heap
+ heap.setSize(i+1);
+ percolateUp(i, o);
+ return true;
+ }
+
+ /**
+ * Returns <code>true</code> if this collection contains no elements, and
+ * <code>false</code> otherwise.
+ */
+ @Override
+ public boolean isEmpty()
+ {
+ return heap.isEmpty();
+ }
+
+ /**
+ * Returns the element at the top of the heap; does not
+ * alter the heap.
+ */
+ public T peek()
+ {
+ if (heap.size() > 0)
+ return heap.elementAt(TOP);
+ else
+ return null;
+ }
+
+ /**
+ * Removes the element at the top of this heap, and returns it.
+ * @deprecated Use {@link MapBinaryHeap#poll()}
+ * or {@link MapBinaryHeap#remove()} instead.
+ */
+ @Deprecated
+ public T pop() throws NoSuchElementException
+ {
+ return this.remove();
+ }
+
+ /**
+ * Returns the size of this heap.
+ */
+ @Override
+ public int size()
+ {
+ return heap.size();
+ }
+
+ /**
+ * Informs the heap that this object's internal key value has been
+ * updated, and that its place in the heap may need to be shifted
+ * (up or down).
+ * @param o
+ */
+ public void update(T o)
+ {
+ // Since we don't know whether the key value increased or
+ // decreased, we just percolate up followed by percolating down;
+ // one of the two will have no effect.
+
+ int cur = object_indices.get(o).intValue(); // current index
+ int new_idx = percolateUp(cur, o);
+ percolateDown(new_idx);
+ }
+
+ /**
+ * @see Collection#contains(java.lang.Object)
+ */
+ @Override
+ public boolean contains(Object o)
+ {
+ return object_indices.containsKey(o);
+ }
+
+ /**
+ * Moves the element at position <code>cur</code> closer to
+ * the bottom of the heap, or returns if no further motion is
+ * necessary. Calls itself recursively if further motion is
+ * possible.
+ */
+ private void percolateDown(int cur)
+ {
+ int left = lChild(cur);
+ int right = rChild(cur);
+ int smallest;
+
+ if ((left < heap.size()) &&
+ (comp.compare(heap.elementAt(left), heap.elementAt(cur)) < 0)) {
+ smallest = left;
+ } else {
+ smallest = cur;
+ }
+
+ if ((right < heap.size()) &&
+ (comp.compare(heap.elementAt(right), heap.elementAt(smallest)) < 0)) {
+ smallest = right;
+ }
+
+ if (cur != smallest)
+ {
+ swap(cur, smallest);
+ percolateDown(smallest);
+ }
+ }
+
+ /**
+ * Moves the element <code>o</code> at position <code>cur</code>
+ * as high as it can go in the heap. Returns the new position of the
+ * element in the heap.
+ */
+ private int percolateUp(int cur, T o)
+ {
+ int i = cur;
+
+ while ((i > TOP) && (comp.compare(heap.elementAt(parent(i)), o) > 0))
+ {
+ T parentElt = heap.elementAt(parent(i));
+ heap.setElementAt(parentElt, i);
+ object_indices.put(parentElt, new Integer(i)); // reset index to i (new location)
+ i = parent(i);
+ }
+
+ // place object in heap at appropriate place
+ object_indices.put(o, new Integer(i));
+ heap.setElementAt(o, i);
+
+ return i;
+ }
+
+ /**
+ * Returns the index of the left child of the element at
+ * index <code>i</code> of the heap.
+ * @param i
+ * @return the index of the left child of the element at
+ * index <code>i</code> of the heap
+ */
+ private int lChild(int i)
+ {
+ return (i<<1) + 1;
+ }
+
+ /**
+ * Returns the index of the right child of the element at
+ * index <code>i</code> of the heap.
+ * @param i
+ * @return the index of the right child of the element at
+ * index <code>i</code> of the heap
+ */
+ private int rChild(int i)
+ {
+ return (i<<1) + 2;
+ }
+
+ /**
+ * Returns the index of the parent of the element at
+ * index <code>i</code> of the heap.
+ * @param i
+ * @return the index of the parent of the element at index i of the heap
+ */
+ private int parent(int i)
+ {
+ return (i-1)>>1;
+ }
+
+ /**
+ * Swaps the positions of the elements at indices <code>i</code>
+ * and <code>j</code> of the heap.
+ * @param i
+ * @param j
+ */
+ private void swap(int i, int j)
+ {
+ T iElt = heap.elementAt(i);
+ T jElt = heap.elementAt(j);
+
+ heap.setElementAt(jElt, i);
+ object_indices.put(jElt, new Integer(i));
+
+ heap.setElementAt(iElt, j);
+ object_indices.put(iElt, new Integer(j));
+ }
+
+ /**
+ * Comparator used if none is specified in the constructor.
+ * @author Joshua O'Madadhain
+ */
+ private class ComparableComparator implements Comparator<T>
+ {
+ /**
+ * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
+ */
+ @SuppressWarnings("unchecked")
+ public int compare(T arg0, T arg1)
+ {
+ if (!(arg0 instanceof Comparable) || !(arg1 instanceof Comparable))
+ throw new IllegalArgumentException("Arguments must be Comparable");
+
+ return ((Comparable<T>)arg0).compareTo(arg1);
+ }
+ }
+
+ /**
+ * Returns an <code>Iterator</code> that does not support modification
+ * of the heap.
+ */
+ @Override
+ public Iterator<T> iterator()
+ {
+ return IteratorUtils.<T>unmodifiableIterator(heap.iterator());
+ }
+
+ /**
+ * This data structure does not support the removal of arbitrary elements.
+ */
+ @Override
+ public boolean remove(Object o)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * This data structure does not support the removal of arbitrary elements.
+ */
+ @Override
+ public boolean removeAll(Collection<?> c)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * This data structure does not support the removal of arbitrary elements.
+ */
+ @Override
+ public boolean retainAll(Collection<?> c)
+ {
+ throw new UnsupportedOperationException();
+ }
+
+ public T element() throws NoSuchElementException
+ {
+ T top = this.peek();
+ if (top == null)
+ throw new NoSuchElementException();
+ return top;
+ }
+
+ public boolean offer(T o)
+ {
+ return add(o);
+ }
+
+ public T poll()
+ {
+ T top = this.peek();
+ if (top != null)
+ {
+ T bottom_elt = heap.lastElement();
+ heap.setElementAt(bottom_elt, TOP);
+ object_indices.put(bottom_elt, new Integer(TOP));
+
+ heap.setSize(heap.size() - 1); // remove the last element
+ if (heap.size() > 1)
+ percolateDown(TOP);
+
+ object_indices.remove(top);
+ }
+ return top;
+ }
+
+ public T remove()
+ {
+ T top = this.poll();
+ if (top == null)
+ throw new NoSuchElementException();
+ return top;
+ }
+
+}
Code Review / controller.git / blobdiff