package DataStructures.Heaps;

import java.util.ArrayList;
import java.util.List;

/**
 * Heap tree where a node's key is higher than or equal to its parent's and lower than or equal to
 * its children's.
 *
 * @author Nicolas Renard
 */
public class MinHeap implements Heap {

  private final List minHeap;

  public MinHeap(List listElements) {
    minHeap = new ArrayList();
    for (HeapElement heapElement : listElements) {
      if (heapElement != null) insertElement(heapElement);
      else System.out.println("Null element. Not added to heap");
    }
    if (minHeap.size() == 0) System.out.println("No element has been added, empty heap.");
  }

  // Get the element at a given index. The key for the list is equal to index value - 1
  public HeapElement getElement(int elementIndex) {
    if ((elementIndex  minHeap.size()))
      throw new IndexOutOfBoundsException("Index out of heap range");
    return minHeap.get(elementIndex - 1);
  }

  // Get the key of the element at a given index
  private double getElementKey(int elementIndex) {
    return minHeap.get(elementIndex - 1).getKey();
  }

  // Swaps two elements in the heap
  private void swap(int index1, int index2) {
    HeapElement temporaryElement = minHeap.get(index1 - 1);
    minHeap.set(index1 - 1, minHeap.get(index2 - 1));
    minHeap.set(index2 - 1, temporaryElement);
  }

  // Toggle an element up to its right place as long as its key is lower than its parent's
  private void toggleUp(int elementIndex) {
    double key = minHeap.get(elementIndex - 1).getKey();
    while (getElementKey((int) Math.floor(elementIndex / 2.0)) > key) {
      swap(elementIndex, (int) Math.floor(elementIndex / 2.0));
      elementIndex = (int) Math.floor(elementIndex / 2.0);
    }
  }

  // Toggle an element down to its right place as long as its key is higher
  // than any of its children's
  private void toggleDown(int elementIndex) {
    double key = minHeap.get(elementIndex - 1).getKey();
    boolean wrongOrder =
        (key > getElementKey(elementIndex * 2))
            || (key > getElementKey(Math.min(elementIndex * 2, minHeap.size())));
    while ((2 * elementIndex  getElementKey(elementIndex * 2))
              || (key > getElementKey(Math.min(elementIndex * 2, minHeap.size())));
    }
  }

  private HeapElement extractMin() {
    HeapElement result = minHeap.get(0);
    deleteElement(0);
    return result;
  }

  @Override
  public void insertElement(HeapElement element) {
    minHeap.add(element);
    toggleUp(minHeap.size());
  }

  @Override
  public void deleteElement(int elementIndex) {
    if (minHeap.isEmpty())
      try {
        throw new EmptyHeapException("Attempt to delete an element from an empty heap");
      } catch (EmptyHeapException e) {
        e.printStackTrace();
      }
    if ((elementIndex > minHeap.size()) || (elementIndex  getElementKey(elementIndex * 2))))
      toggleDown(elementIndex);
  }

  @Override
  public HeapElement getElement() throws EmptyHeapException {
    try {
      return extractMin();
    } catch (Exception e) {
      throw new EmptyHeapException("Heap is empty. Error retrieving element");
    }
  }
}