package Question2;

import java.util.ArrayList;

/**
 * Heap class to store any type of objects and their associated priorities.
 */
public class ArrayHeap<T> {

    private ArrayList<Node> contents;        ///An ArrayList to store nodes

    /*
   * Constructor to initializes an empty ArrayHeap.
     */
    public ArrayHeap() {
        contents = new ArrayList<>();
        contents.add(null);
    }

    /*
   * Returns the index of the left child node
     */
    private int getLeft(int i) {
        return i * 2;
    }

    /*
   * Returns the index of the right clild node
     */
    private int getRight(int i) {
        return 2 * i + 1;
    }

    /*
   * Returns the index of the parent node
     */
    private int getParent(int i) {
        return i / 2;
    }

    /**
     * Returns the index of the node with smaller priority. Assumption: not both
     * nodes are null.
     */
    private int min(int index1, int index2) {
        Node node1 = getNode(index1);
        Node node2 = getNode(index2);
        if (node1 == null) {
            return index2;
        } else if (node2 == null) {
            return index1;
        } else if (node1.getPriority() < node2.getPriority()) {
            return index1;
        } else {
            return index2;
        }
    }

    /*
   * Returns the Node with the smallest priority value without removing it
     */
    public Node peek() {
        return contents.get(1);
    }

    /*
   * Bubbles up the node currently at the given index.
     */
    private void bubbleUp(int index) {
        // YOUR CODE HERE// completed
        while (index > 1 && min(index, getParent(index)) == index) {
            swap(index, getParent(index));
            index = getParent(index);
        }
    }

    /*
   * Bubbles down the node currently at the given index.
     */
    private void bubbleDown(int index) {
        // YOUR CODE HERE// completed
        if (index == contents.size()) {
            return;
        }
        int minI = min(index, min(getLeft(index), getRight(index)));
        if (index != minI) {
            swap(index, minI);
            bubbleDown(minI);
        }
    }

    /*
   * Inserts an item to the heap with a given priority value
     */
    public void insert(T item, double priority) {
        // YOUR CODE HERE // completed
        if (contents.size() == 0) {
            contents.add(null);
        } else {
            contents.add(new Node(item, priority));
            bubbleUp(contents.size() - 1);
        }

    }

    /*
   * Returns the Node with the smallest priority value,
   * and removes it from the heap.
     */
    public Node removeMin() {
        // YOUR CODE HERE// completed
        if (contents.size() < 2) {
            return null;
        } else if (contents.size() == 2) {
            return contents.remove(1);
        } else {
            Node minVal = contents.get(1);
            Node maxVal = contents.remove(contents.size() - 1);
            contents.set(1, maxVal);
            bubbleDown(1);
            return minVal;
        }

    }

    /*
   * Update a node in the heap (that matches with the given item) to have the given priority.
   * Assumption: we will not have two nodes with the same item.
   * Suggestions: Check for equality of items with .equals(), not ==
     */
    public void changePriority(T item, double priority) {
        // YOUR CODE HERE

        for (int i = 1; i < contents.size(); i++) {
            if (getNode(i).getItem().equals(item)) {
                double old = getNode(i).getPriority();
                getNode(i).setPriority(priority);
                if (old < priority) {
                    bubbleDown(i);
                } else {
                    bubbleUp(i);
                }
            }
            break;
        }

    }

    /*
  * Returns the node at index INDEX.
     */
    private Node getNode(int index) {
        if (index >= contents.size()) {
            return null;
        } else {
            return contents.get(index);
        }
    }

    /*
   * Swap the nodes at the two indices.
     */
    private void swap(int index1, int index2) {
        Node node1 = getNode(index1);
        Node node2 = getNode(index2);
        this.contents.set(index1, node2);
        this.contents.set(index2, node1);
    }

    int height(int index) {
        int result = 0;
        while (index > 0) {
            result++;
            index /= 2;
        }
        return result;
    }


    /*
   * Prints out the heap sideways.
   * We use this method for debugging.
     */
    @Override
    public String toString() {
        return customToStringHelper();
    }

    private String customToStringHelper() {
        String ret = "";

        boolean[] visited = new boolean[contents.size() + 1];
        for (int i = 0; i <= contents.size(); i++) {
            visited[i] = false;
        }

        for (int i = 1, n = contents.size(); i < n; i++) {
            int h = height(i);
            if (!visited[h]) {
                ret += "\n";
                visited[h] = true;
            }

            if (i % 2 == 0 && i != 1) {
                ret += "(";
            }
            if (i % 2 == 1 && i != 1) {
                ret += ", ";
            }
            ret += contents.get(i);
            if ((i % 2 == 1 && i != 1) || i == (n - 1)) {
                ret += ")";
            }
        }

        return ret;
    }

    /*
   * Recursive helper method for toString.
     */
    private String toStringHelper(int index, String soFar) {
        if (getNode(index) == null) {
            return "";
        } else {
            String toReturn = "";
            int rightChild = getRight(index);
            toReturn += toStringHelper(rightChild, "        " + soFar);
            if (getNode(rightChild) != null) {
                toReturn += soFar + "    /";
            }
            toReturn += "\n" + soFar + getNode(index) + "\n";
            int leftChild = getLeft(index);
            if (getNode(leftChild) != null) {
                toReturn += soFar + "    \\";
            }
            toReturn += toStringHelper(leftChild, "        " + soFar);
            return toReturn;
        }
    }

}