| package org.onlab.graph; |
| |
| import com.google.common.collect.ImmutableList; |
| |
| import java.util.Comparator; |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.Objects; |
| |
| import static com.google.common.base.MoreObjects.toStringHelper; |
| import static com.google.common.base.Preconditions.checkNotNull; |
| |
| /** |
| * Implementation of an array-backed heap structure whose sense of order is |
| * imposed by the provided comparator. |
| * <p/> |
| * While this provides similar functionality to {@link java.util.PriorityQueue} |
| * data structure, one key difference is that external entities can control |
| * when to restore the heap property, which is done through invocation of the |
| * {@link #heapify} method. |
| * <p/> |
| * This class is not thread-safe and care must be taken to prevent concurrent |
| * modifications. |
| * |
| * @param <T> type of the items on the heap |
| */ |
| public class Heap<T> { |
| |
| private final List<T> data; |
| private final Comparator<T> comparator; |
| |
| /** |
| * Creates a new heap backed by the specified list. In the interest of |
| * efficiency, the list should be array-backed. Also, for the same reason, |
| * the data is not copied and therefore, the caller must assure that the |
| * backing data is not altered in any way. |
| * |
| * @param data backing data list |
| * @param comparator comparator for ordering the heap items |
| */ |
| public Heap(List<T> data, Comparator<T> comparator) { |
| this.data = checkNotNull(data, "Data cannot be null"); |
| this.comparator = checkNotNull(comparator, "Comparator cannot be null"); |
| heapify(); |
| } |
| |
| /** |
| * Restores the heap property by re-arranging the elements in the backing |
| * array as necessary following any heap modifications. |
| */ |
| public void heapify() { |
| for (int i = data.size() / 2; i >= 0; i--) { |
| heapify(i); |
| } |
| } |
| |
| /** |
| * Returns the current size of the heap. |
| * |
| * @return number of items in the heap |
| */ |
| public int size() { |
| return data.size(); |
| } |
| |
| /** |
| * Returns true if there are no items in the heap. |
| * |
| * @return true if heap is empty |
| */ |
| public boolean isEmpty() { |
| return data.isEmpty(); |
| } |
| |
| /** |
| * Returns the most extreme item in the heap. |
| * |
| * @return heap extreme or null if the heap is empty |
| */ |
| public T extreme() { |
| return data.isEmpty() ? null : data.get(0); |
| } |
| |
| /** |
| * Extracts and returns the most extreme item from the heap. |
| * |
| * @return heap extreme or null if the heap is empty |
| */ |
| public T extractExtreme() { |
| if (!isEmpty()) { |
| T extreme = extreme(); |
| |
| data.set(0, data.get(data.size() - 1)); |
| data.remove(data.size() - 1); |
| heapify(); |
| return extreme; |
| } |
| return null; |
| } |
| |
| /** |
| * Inserts the specified item into the heap and returns the modified heap. |
| * |
| * @param item item to be inserted |
| * @return the heap self |
| * @throws IllegalArgumentException if the heap is already full |
| */ |
| public Heap<T> insert(T item) { |
| data.add(item); |
| bubbleUp(); |
| return this; |
| } |
| |
| /** |
| * Returns iterator to traverse the heap level-by-level. This iterator |
| * does not permit removal of items. |
| * |
| * @return non-destructive heap iterator |
| */ |
| public Iterator<T> iterator() { |
| return ImmutableList.copyOf(data).iterator(); |
| } |
| |
| // Bubbles up the last item in the heap to its proper position to restore |
| // the heap property. |
| private void bubbleUp() { |
| int child = data.size() - 1; |
| while (child > 0) { |
| int parent = child / 2; |
| if (comparator.compare(data.get(child), data.get(parent)) < 0) { |
| break; |
| } |
| swap(child, parent); |
| child = parent; |
| } |
| } |
| |
| // Restores the heap property of the specified heap layer. |
| private void heapify(int i) { |
| int left = 2 * i + 1; |
| int right = 2 * i; |
| int extreme = i; |
| |
| if (left < data.size() && |
| comparator.compare(data.get(extreme), data.get(left)) < 0) { |
| extreme = left; |
| } |
| |
| if (right < data.size() && |
| comparator.compare(data.get(extreme), data.get(right)) < 0) { |
| extreme = right; |
| } |
| |
| if (extreme != i) { |
| swap(i, extreme); |
| heapify(extreme); |
| } |
| } |
| |
| // Swaps two heap items identified by their respective indexes. |
| private void swap(int i, int k) { |
| T aux = data.get(i); |
| data.set(i, data.get(k)); |
| data.set(k, aux); |
| } |
| |
| @Override |
| public boolean equals(Object obj) { |
| if (this == obj) { |
| return true; |
| } |
| if (obj instanceof Heap) { |
| Heap that = (Heap) obj; |
| return this.getClass() == that.getClass() && |
| Objects.equals(this.comparator, that.comparator) && |
| Objects.deepEquals(this.data, that.data); |
| } |
| return false; |
| } |
| |
| @Override |
| public int hashCode() { |
| return Objects.hash(comparator, data); |
| } |
| |
| @Override |
| public String toString() { |
| return toStringHelper(this) |
| .add("data", data) |
| .add("comparator", comparator) |
| .toString(); |
| } |
| |
| } |