/* Copyright 2008 Wry Research, Inc. */
package com.wryresearch.containers;

import java.util.Arrays;

import com.wryresearch.algorithms.SortOrder;
import com.wryresearch.algorithms.Swapper;

/**
 * This is a simple implementation of a binary heap data structure, with a
 * collection of Object items that parallel the position of the values
 * in the heap.
 *
 * Basically, this class allows key/value pairs (where the key's type depends on
 * the specific implementation class, but the value is always a double) to be added
 * to the collection and then retrieved in either ascending or descending order
 * (though descending order is the default).
 *
 * Heap objects are instantiated with a specific fixed capacity, and when the size
 * of the Heap exceeds the capacity, the lowest-valued objects are silently dropped
 * from the collection.
 *
 * For more details about the overall concept of a binary heap, there's a great
 * article on the wikipedia, here:
 *
 *    http://en.wikipedia.org/wiki/Binary_heap
 *
 * For improved cache locality, this implementation refrains from using a literal
 * binary tree representation under the hood. Instead, all values are stored in an
 * array, and the tree structure is synthesized by calculating tree-like array
 * index values.
 *
 * @author Benji Smith <benji@benjismith.net>
 */
public class BinaryHeap<T> {

   private static final String violatedContractMessage =
      "Heap contract violated. Item at index %s has value %s, which is " +
      "greater than the value of its parent %s, at index %s.";

   private static final String nullSortOrderMessage =
      "Can't create a BinaryHeap object with a null SortOrder argument";

   private static final String emptyHeapRemoveMessage = "Empty heap. Can't retrieve top item.";

   private static final int MAX_INITIAL_SIZE = 1024;

   // By default, the heap is organized in descending order (with the highest-
   // valued items at the top of the heap and lesser items below it).
   private boolean descending = true;

   private int capacity;
   private Object[] items;

   private double[] values;

   // This variable helps reduce the number of times that an exhaustive search
   // needs to be conducted for smallest values. Since the exhaustive search
   // scales linearly (and is the most expensive operation in the entire class),
   // any reduction is helpful.
   private double previousInsignificantValue;

   private int size;

   /**
    * Creates a new BinaryHeap object with enough memory to store the
    * given number of items. Once the heap is full, adding more items will cause
    * it to drop those items with a low corresponding value.
    *
    * Items will be stored in the default sort ordering, with the largest values at the top and
    * smaller values toward the bottom (commonly referred to as a "max heap").
    *
    * @param capacity The maximum number of items to retain in the BinaryHeap
    * before the lowest-priority items begin to silently fall off the bottom of
    * the heap.
    */
   public BinaryHeap(int capacity) {
      this(capacity, SortOrder.DESCENDING);
   }

   /**
    * Creates a new BinaryHeap object with enough memory to store the
    * given number of items. Once the heap is full, adding more items will cause
    * it to drop those items with a low corresponding value.
    *
    * @param capacity The maximum number of items to retain in the BinaryHeap
    * before the lowest-priority items begin to silently fall off the bottom of
    * the heap.
    *
    * @param order The comparison order that should be used for determining
    * the ordering of items within the heap. Using SortOrder.DESCENDING will
    * result in a standard "max heap", with the largest values at the top and
    * smaller values toward the bottom. Using SortOrder.ASCENDING will have the
    * opposite effect.
    */
   public BinaryHeap(int capacity, SortOrder order) {

      if (order == null) {
         throw new IllegalArgumentException(nullSortOrderMessage);
      }

      this.capacity = capacity;
      this.descending = order.equals(SortOrder.DESCENDING);
      this.previousInsignificantValue = descending ? Double.MAX_VALUE : - Double.MAX_VALUE;
      if (capacity <= MAX_INITIAL_SIZE) {
         // The heap is small. Allocate only the amount of memory necessary.
         this.items = new Object[capacity];
         this.values = new double[capacity];
      } else {
         // The heap is large. Only allocate the first 1024 elements. Reallocate
         // later, to grow the heap as necessary.
         this.items = new Object[MAX_INITIAL_SIZE];
         this.values = new double[MAX_INITIAL_SIZE];
      }
      this.size = 0;
   }

   public void addItem(Pair<T, Double> itemAndValue) {
      addItem(itemAndValue.getKey(), itemAndValue.getValue());
   }

   public void addItem(T item, double value) {
      if (size < capacity) {

         // Allocate more memory, to keep up with the growing size of the heap,
         // if necessary.
         if (values.length < capacity) grow();

         // Add the item and its value to the item & value lists
         items[size] = item;
         values[size] = value;

         // Move the value up the heap, to its correct location.
         bubbleUp(size);

         // Keep track of how many items have been added to the heap.
         size++;

         // Deprecate the previously cached least-value, since the value
         // being added in this method could be less than the previous
         // least-value.
         previousInsignificantValue = descending ? Double.MAX_VALUE : - Double.MAX_VALUE;

      } else if (capacity > 0) {

         int indexOfInsignificantValue = findInsignificantValue();
         double insignificantValue = values[indexOfInsignificantValue];
         if ((descending && value > insignificantValue) || (!descending && value < insignificantValue)) {

            // Add this item in the place of the most insignificant item
            items[indexOfInsignificantValue] = item;
            values[indexOfInsignificantValue] = value;

            // Since this item is more important than the most insignificant item, it may
            // also be more signficant than many other values, requiring it to bubble up.
            bubbleUp(indexOfInsignificantValue);
         }
      }
   }

   public Pair<T, Double> removeItemAndValue() {
      double value = getTopValue();
      return new Pair<T, Double>(removeItem(), value);
   }

   @SuppressWarnings("unchecked")
   public T removeItem() {

      if (size == 0) {
         throw new IllegalStateException(emptyHeapRemoveMessage);
      }

      T returnValue = (T) items[0];

      // Move the final item to the top, and then let it trickle down.
      int lastIndex = size - 1;
      items[0] = items[lastIndex];
      values[0] = values[lastIndex];

      // Remove the final item.
      size--;
      items[size] = null;

      // Correct the position of the new topmost item (which probably doesn't have
      // the highest value in the data structure.
      trickleDown();

      // Return the appropriate item.
      return returnValue;
   }

   public double getTopValue() {

      if (size == 0) {
         throw new IllegalStateException(emptyHeapRemoveMessage);
      }

      return values[0];
   }

   public int size() {
      return size;
   }

   public int capacity() {
      return capacity;
   }

   public void clear() {
      size = 0;
      Arrays.fill(items, null);
      previousInsignificantValue = descending ? Double.MAX_VALUE : - Double.MAX_VALUE;
   }

   /**
    * This method recurses through the tree structure of the Heap, checking
    * to make sure that it always fulfills its contract where each parent
    * has a value greater than the value of its children.
    *
    * If any nodes in the Heap violate the contract, then this method throws
    * a RuntimeException pointing out the location of the problem nodes.
    */
   public void checkValid() {
      for (int i = 0; i < size; i++) {
         double parentValue = values[i];
         int firstChildIndex = (2 * i) + 1;
         int secondChildIndex = firstChildIndex + 1;
         if (firstChildIndex < size) {
            double firstChildValue = values[firstChildIndex];
            if ((descending && parentValue < firstChildValue) || (!descending && parentValue > firstChildValue)) {
               String message = String.format(violatedContractMessage, firstChildIndex, firstChildValue, parentValue, i);
               throw new RuntimeException(message);
            }
         }
         if (secondChildIndex < size) {
            double secondChildValue = values[secondChildIndex];
            if ((descending && parentValue < secondChildValue) || (!descending && parentValue > secondChildValue)) {
               String message = String.format(violatedContractMessage, secondChildIndex, secondChildValue, parentValue, i);
               throw new RuntimeException(message);
            }
         }
      }
   }

   /* Finds the smallest value in the heap. This is an expensive calculation because
    * it requires performing a linear search through the values array. Conveniently,
    * though, the Heap logic prevents the lowest value from ever occurring within
    * the first (n / 2) elements, so the search space is slightly reduced.
    */
   private int findInsignificantValue() {

      if (capacity == 1) {
         return 0;
      } else {

         boolean hasPreviousInsignificantValue =
            (descending && previousInsignificantValue != Double.MAX_VALUE) ||
            (!descending && previousInsignificantValue != Double.MIN_VALUE);


         int lastIndex = size - 1;
         int firstChildless = ((lastIndex - 1) / 2) + 1;
         int insignificantIndex = -1;
         double insignificantValue = descending ? Double.MAX_VALUE : Double.MIN_VALUE;

         for (int i = firstChildless; i <= lastIndex; i++) {
            double value = values[i];

            // In cases where the previous insignificant value still exists (because of duplicate
            // entries), there's no need to continue searching for less significant values, since
            // none can possibly exist.
            if (hasPreviousInsignificantValue && value == previousInsignificantValue) {
               return i;
            }
            if ((descending && value < insignificantValue) || (!descending && value > insignificantValue)) {
               insignificantIndex = i;
               insignificantValue = value;
            }
         }

         // Save this smallest value for the next iteration, so that repeat values can
         // be easily found, short-circuiting the linear search when a duplicate is found.
         previousInsignificantValue = insignificantValue;

         return insignificantIndex;
      }
   }

   /*
    * After placing a new item at the tail-end of the values array, it needs to be
    * moved to its appropriate place in the order of the array. This method moves
    * the item to its correct location, potentially up to the head of the heap, if
    * the item at the given index has the highest value in the heap.
    */
   private void bubbleUp(int index) {
      while (index > 0) {
         int parent = ((index - 1) / 2);
         double thisValue = values[index];
         double parentValue = values[parent];
         if (descending && thisValue > parentValue || !descending && thisValue < parentValue) {
            Swapper.parallelSwap(items, values, index, parent);
            index = parent;
         } else {
            break;
         }
      }
   }

   /* After removing an item from the head of the heap (and moving the tail item
    * into the head position), it needs to be moved down to the appropriate place
    * in the order of the array. This method moves the item to its correct locaion,
    * potentially to one of the leaf-nodes of the heap, if the item at the head
    * location has one of the lowest values in the heap.
    */
   private void trickleDown() {
      int lastIndex = size - 1;
      int index = 0;
      while (index < lastIndex) {
         int firstChildIndex = (2 * index) + 1;
         int secondChildIndex = firstChildIndex + 1;
         int swapIndex;
         if (firstChildIndex > lastIndex && secondChildIndex > lastIndex) {
            break;
         }
         if (secondChildIndex > lastIndex ||
               (descending && values[firstChildIndex] > values[secondChildIndex]) ||
               (!descending && values[firstChildIndex] < values[secondChildIndex])) {
            swapIndex = firstChildIndex;
         } else {
            swapIndex = secondChildIndex;
         }
         if ((descending && values[index] < values[swapIndex]) || (!descending && values[index] > values[swapIndex])) {
            Swapper.parallelSwap(items, values, index, swapIndex);
            index = swapIndex;
         } else {
            break;
         }
      }
   }

   /* Doubles the size of the values array (up to, but not exceeding the heap capacity)
    * and copies the old values to the new array. The implementation of this method
    * allows the heap to defer allocation of memory until the heap actually needs to
    * fill those values. Once allocation, the extra memory is never recovered (since
    * there is no 'compact' method).
    */
   private void grow() {

      // Allocate a new array, of the appropriate size.
      int oldSize = values.length;
      int newSize = Math.min(oldSize * 2, capacity);
      double[] newValues = new double[newSize];
      Object[] newItems = new Object[newSize];

      // Copy values from the old array to the new array.
      System.arraycopy(values, 0, newValues, 0, oldSize);
      System.arraycopy(items, 0, newItems, 0, oldSize);

      // Set the member variable reference to point to the new array.
      values = newValues;
      items = newItems;
   }


}