/**
 * 
 */
package heaps;

/**
 * @author Nicolas Renard
 * Exception to be thrown if the getElement method is used on an empty heap.
 *
 */
@SuppressWarnings("serial")
public class EmptyHeapException extends Exception {

    public EmptyHeapException(String message) {
        super(message);
    }

}

package heaps;

/**
 * Interface common to heap data structures.<br>
 * <p>Heaps are tree-like data structures that allow storing elements in a specific
 * way. Each node corresponds to an element and has one parent node (except for the root) and
 * at most two children nodes. Every element contains a key, and those keys
 * indicate how the tree shall be built. For instance, for a min-heap, the key of a node shall
 * be greater than or equal to its parent's and lower than or equal to its children's (the opposite rule applies to a
 * max-heap).</p>
 * <p>All heap-related operations (inserting or deleting an element, extracting the min or max) are performed in
 * O(log n) time.</p>
 * @author Nicolas Renard
 * 
 * 
 */
public interface Heap {

    /**
     * 
     * @return the top element in the heap, the one with lowest key for min-heap or with
     * the highest key for max-heap
     * @throws Exception if heap is empty
     */
    public abstract HeapElement getElement() throws EmptyHeapException;
    /**
     * Inserts an element in the heap. Adds it to then end and toggle it until it finds its
     * right position.
     * 
     * @param element an instance of the HeapElement class.
     */
    public abstract void insertElement(HeapElement element);

    /**
     * Delete an element in the heap.
     * 
     * @param elementIndex int containing the position in the heap of the element to be deleted.
     */
    public abstract void deleteElement(int elementIndex);

}

/**
 * 
 */
package heaps;

import java.lang.Double;
import java.lang.Object;

/**
 * Class for heap elements.<br>
 * <p>A heap element contains two attributes: a key which will be used to build the tree (int
 * or double, either primitive type or object) and any kind of IMMUTABLE object the user sees fit
 * to carry any information he/she likes. Be aware that the use of a mutable object might
 * jeopardize the integrity of this information. </p>
 * @author Nicolas Renard
 *
 */
public class HeapElement {
    private final double key;
    private final Object additionalInfo;

    // Constructors

    /**
     * 
     * @param key : a number of primitive type 'double'
     * @param info : any kind of IMMUTABLE object. May be null, since the purpose is only to carry
     * additional information of use for the user
     */
    public HeapElement(double key, Object info) {
        this.key = key;
        this.additionalInfo = info;
    }

    /**
     * 
     * @param key : a number of primitive type 'int'
     * @param info : any kind of IMMUTABLE object. May be null, since the purpose is only to carry
     * additional information of use for the user
     */
    public HeapElement(int key, Object info) {
        this.key = key;
        this.additionalInfo = info;
    }

    /**
     * 
     * @param key : a number of object type 'Integer'
     * @param info : any kind of IMMUTABLE object. May be null, since the purpose is only to carry
     * additional information of use for the user
     */
    public HeapElement(Integer key, Object info) {
        this.key = key;
        this.additionalInfo = info;
    }

    /**
     * 
     * @param key : a number of object type 'Double'
     * @param info : any kind of IMMUTABLE object. May be null, since the purpose is only to carry
     * additional information of use for the user
     */
    public HeapElement(Double key, Object info) {
        this.key = key;
        this.additionalInfo = info;
    }

    /**
     * 
     * @param key : a number of primitive type 'double'
     */
    public HeapElement(double key) {
        this.key = key;
        this.additionalInfo = null;
    }

    /**
     * 
     * @param key : a number of primitive type 'int'
     */
    public HeapElement(int key) {
        this.key = key;
        this.additionalInfo = null;
    }

    /**
     * 
     * @param key : a number of object type 'Integer'
     */
    public HeapElement(Integer key) {
        this.key = key;
        this.additionalInfo = null;
    }

    /**
     * 
     * @param key : a number of object type 'Double'
     */
    public HeapElement(Double key) {
        this.key = key;
        this.additionalInfo = null;
    }

    // Getters
    /**
     * @return the object containing the additional info provided by the user.
     */
    public Object getInfo() {
        return additionalInfo;
    }
    /**
     * @return the key value of the element
     */
    public double getKey() {
        return key;
    }

    // Overridden object methods

    public String toString() {
        return "Key: " + key + " - " +additionalInfo.toString();
    }
    /**
     * 
     * @param otherHeapElement
     * @return true if the keys on both elements are identical and the additional info objects
     * are identical.
     */
    public boolean equals(HeapElement otherHeapElement) {
        return (this.key == otherHeapElement.key) && (this.additionalInfo.equals(otherHeapElement.additionalInfo));
    }
}

/**
 * 
 */
package 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<HeapElement> minHeap;

    public MinHeap(List<HeapElement> listElements) throws Exception {
        minHeap = new ArrayList<HeapElement>();
        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 <= 0) && (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)) > key) {
            swap(elementIndex, (int) Math.floor(elementIndex/2));
            elementIndex = (int) Math.floor(elementIndex/2);
        }
    }

    // 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 <= minHeap.size()) && wrongOrder) {
            // Check whether it shall swap the element with its left child or its right one if any.
            if ((2*elementIndex < minHeap.size()) && (getElementKey(elementIndex*2 + 1) < getElementKey(elementIndex*2))) {
                swap(elementIndex, 2*elementIndex + 1);
                elementIndex = 2*elementIndex + 1;
            }
            else {
                swap(elementIndex, 2*elementIndex);
                elementIndex = 2*elementIndex;
            }
            wrongOrder = (key > 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 <= 0)) throw new IndexOutOfBoundsException("Index out of heap range");
        // The last element in heap replaces the one to be deleted
        minHeap.set(elementIndex - 1, getElement(minHeap.size()));
        minHeap.remove(minHeap.size());
        // Shall the new element be moved up...
        if (getElementKey(elementIndex) < getElementKey((int) Math.floor(elementIndex/2))) toggleUp(elementIndex);
        // ... or down ?
        else if (((2*elementIndex <= minHeap.size()) && (getElementKey(elementIndex) > getElementKey(elementIndex*2))) ||
                ((2*elementIndex < minHeap.size()) && (getElementKey(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");
        }
    }
}

package 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 MaxHeap implements Heap {

    private final List<HeapElement> maxHeap;

    public MaxHeap(List<HeapElement> listElements) throws Exception {
        maxHeap = new ArrayList<HeapElement>();
        for (HeapElement heapElement : listElements) {
            if (heapElement != null) insertElement(heapElement);
            else System.out.println("Null element. Not added to heap");
        }
        if (maxHeap.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 <= 0) && (elementIndex > maxHeap.size())) throw new IndexOutOfBoundsException("Index out of heap range");
        return maxHeap.get(elementIndex - 1);
    }

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

    // Swaps two elements in the heap
    private void swap(int index1, int index2) {
        HeapElement temporaryElement = maxHeap.get(index1 - 1);
        maxHeap.set(index1 - 1, maxHeap.get(index2 - 1));
        maxHeap.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 = maxHeap.get(elementIndex - 1).getKey();
        while (getElementKey((int) Math.floor(elementIndex/2)) < key) {
            swap(elementIndex, (int) Math.floor(elementIndex/2));
            elementIndex = (int) Math.floor(elementIndex/2);
        }
    }

    // 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 = maxHeap.get(elementIndex - 1).getKey();
        boolean wrongOrder = (key < getElementKey(elementIndex*2)) || (key < getElementKey(Math.min(elementIndex*2, maxHeap.size())));
        while ((2*elementIndex <= maxHeap.size()) && wrongOrder) {
            // Check whether it shall swap the element with its left child or its right one if any.
            if ((2*elementIndex < maxHeap.size()) && (getElementKey(elementIndex*2 + 1) > getElementKey(elementIndex*2))) {
                swap(elementIndex, 2*elementIndex + 1);
                elementIndex = 2*elementIndex + 1;
            }
            else {
                swap(elementIndex, 2*elementIndex);
                elementIndex = 2*elementIndex;
            }
            wrongOrder = (key < getElementKey(elementIndex*2)) || (key < getElementKey(Math.min(elementIndex*2, maxHeap.size())));

        }
    }

    private HeapElement extractMax() {
        HeapElement result = maxHeap.get(0);
        deleteElement(0);
        return result;
    }

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

    }

    @Override
    public void deleteElement(int elementIndex) {
        if (maxHeap.isEmpty())
            try {
                throw new EmptyHeapException("Attempt to delete an element from an empty heap");
            } catch (EmptyHeapException e) {
                e.printStackTrace();
            }
        if ((elementIndex > maxHeap.size()) && (elementIndex <= 0)) throw new IndexOutOfBoundsException("Index out of heap range");
        // The last element in heap replaces the one to be deleted
        maxHeap.set(elementIndex - 1, getElement(maxHeap.size()));
        maxHeap.remove(maxHeap.size());
        // Shall the new element be moved up...
        if (getElementKey(elementIndex) > getElementKey((int) Math.floor(elementIndex/2))) toggleUp(elementIndex);
        // ... or down ?
        else if (((2*elementIndex <= maxHeap.size()) && (getElementKey(elementIndex) < getElementKey(elementIndex*2))) ||
                ((2*elementIndex < maxHeap.size()) && (getElementKey(elementIndex) < getElementKey(elementIndex*2)))) toggleDown(elementIndex);
    }

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

}