package dataStructures;

import java.util.Arrays;

/**
 * @author myleslamb char min heap to be used for the construction of a huffman
 *         tree
 */

public class Heap<T extends Comparable<T>> {

    private T[] arr;
    private int size;
    private Order order;

    public Heap(Order type, int initsize, T[] arg) {

        this.order = type;
        this.arr = arg;
        this.arr = Arrays.copyOf(arg, initsize); // dont leak reference

        for (int i = 0; i < arg.length; i++)
            arr[i] = arg[i];

        size = arg.length;
        System.out.println(size);
        this.buildHeap();
    }

    public Heap(Order type, T[] arg) {
        this(type, arg.length, arg);
    }

    /**
     * O(n) build method using sift down approach
     */
    public void buildHeap() {

        // from first node with child to root push down
        for (int i = (size - 1) / 2; i >= 0; i--) {
            impose(i);
        }

    }

    /**
     * return the index of the max child given teh index of teh input node
     *
     * returns -1 if the node is a leaf (no children)
     *
     * @param i index of the node
     * @return the index of the greatest child
     */
    private int getMaxChild(int i) {
        int lchild = (2 * i) + 1;
        int rchild = lchild + 1;

        // we dont have any children
        if (lchild > this.size - 1)
            return -1;

        //we only have a left child
        if (rchild > this.size - 1)
            return lchild;

        //we have both
        return (arr[lchild].compareTo(arr[rchild]) * this.order.ordinal > 0) ? lchild : rchild;

    }

    private void realloc(int newSize) {

        this.arr = Arrays.copyOf(this.arr, newSize);

    }

    public void insert(T val) {

        if (size == arr.length) {
            realloc(2 * size);
        }

        int insert = size++;
        int parent = (insert - 1) / 2;
        // push up till no longer greater than parent

        while (parent >= 0) {

            if (val.compareTo(arr[parent]) * this.order.ordinal > 0) {
                arr[insert] = arr[parent];
                insert = parent;

            } else {

                break;

            }

            parent = (insert - 1) / 2;

        }

        arr[insert] = val;

    }

    /**
     * swaps with the largest child until the heap property is satisfied
     *
     * @param i the index of the node to impose the heap property on
     */
    private void impose(int i) {

        T cursor = arr[i];
        int index = i;

        while (true) {

            int maxChild = getMaxChild(index);

            // we dont have any children
            if (maxChild == -1)
                break;

            // if the max child is greater we should swap and continue
            if (cursor.compareTo(arr[maxChild]) * this.order.ordinal < 0) {
                arr[index] = arr[maxChild];
                index = maxChild;
            } else
                break;
        }

        arr[index] = cursor;

    }

    public T getMax() {
        T ret = arr[0];
        arr[0] = arr[--size];
        impose(0);
        return ret;

    }

    // assistant classes from here

    /*
     * order enum used to allow for both min and max heaps from teh same class by
     * multiplying with post compareTo we can
     */
    public static enum Order {
        MIN(-1), MAX(1);

        int ordinal;

        private Order(int arg) {

            this.ordinal = arg;

        }

    };

    public String toString() {
        return Arrays.toString(Arrays.copyOfRange(arr, 0, size));

    }

}