/**
 * Heap.java
 * Started by Jeff Ondich, 24 Feb 2014
 *
 * For use in lab for Carleton's CS 201 Data Structures.
 */

import java.util.ArrayList;

public class Heap {
    private ArrayList<Integer> theHeap;

    public Heap() {
        // For this exercise, we're going to keep our heaps small,
        // so let's just make sure theHeap has enough space to hold
        // all our examples.
        this.theHeap = new ArrayList<Integer>(100);
    }


    /**
     * Set up a hard-coded max heap.
     */
    public void initialize1() {
        this.theHeap.add(20); // Why does this work? Shouldn't int be turned into Integer first?
        this.theHeap.add(10);
        this.theHeap.add(15);
        this.theHeap.add(9);
        this.theHeap.add(8);
        this.theHeap.add(14);
        this.theHeap.add(6);
        this.theHeap.add(3);
        this.theHeap.add(7);
        this.theHeap.add(2);
        this.theHeap.add(5);
        this.theHeap.add(13);
    }

    public boolean isMaxHeap() {
        int heapSize = this.theHeap.size();
        for (int k = 0; k < heapSize; ++k) {
            int currentInt = this.theHeap.get(k);
            if (2 * k + 1 < heapSize) {
                int leftChild = this.theHeap.get(2 * k + 1);
                if (leftChild >= currentInt) {
                    System.out.format("Uh-oh: parent=%d, leftChild=%d%n", currentInt, leftChild);
                    return false;
                }
            }

            if (2 * k + 2 < heapSize) {
                int rightChild = this.theHeap.get(2 * k + 2);
                if (rightChild >= currentInt) {
                    System.out.format("Uh-oh: parent=%d, rightChild=%d%n", currentInt, rightChild);
                    return false;
                }
            }
        }
        return true;
    }

    public void add(Integer k) {
    }

    public Integer remove() {
        return null;
    }

    public int peek() {
        return this.theHeap.get(0);
    }

    public void print() {
        this.print(0, "");
    }

    public void print(int startingIndex, String indent) {
        if (startingIndex < this.theHeap.size()) {
            System.out.print(indent);
            System.out.println(this.theHeap.get(startingIndex));
            this.print(2 * startingIndex + 1, indent + "|---");
            this.print(2 * startingIndex + 2, indent + "|---");
        }
    }

    public static void main(String[] args) {
        Heap heap = new Heap();
        heap.initialize1();
        heap.print();
        System.out.println("Valid max heap? " + heap.isMaxHeap());
        System.out.println("Max item: " + heap.peek());
    }
}