import java.util.ArrayList;

/**
 * K_MaxHeap<T> extends K_ALCompleteBinTree<T>,
 * overriding the <code>add</code> and <code>remove</code> methods to
 * preserve the characteristics of a MaxHeap.
 *
 * MaxHeap Invariant: The tree is a complete binary tree in which the
 * data value in every node is greater than or equal to the data in
 * its children).  A complete binary tree is a binary tree that has 2^k
 * nodes at every level k (in other words, every level is completely
 * filled) except perhaps the deepest level, whose nodes are as far left as
 * possible.
 *
 * @author Alyce Brady
 * @version 18 November 2025
 *
 * @param <T> The type of data stored.
 * 
 */
public class K_MaxHeap<T extends Comparable<T>> extends K_ALCompleteBinTree<T>
{
    /** Creates an empty binary tree with no data and no children.
     */
    public K_MaxHeap()
    {
        super();
    }

    /** {@inheritDoc}
     *  This implementation adds data in the last location of the complete
     *  binary tree, and then "heapifies" the tree to preserve the heap
     *  invariant.
     */
    @Override
    public void add(T value)
    {
        // This implementation adds the data to the end of the ArrayList,
        // creating a complete binary tree, and then percolates the new
        // value up as necessary.
        super.add(value);
        maxPercolateUp(theList.size() - 1);
    }

    /** {@inheritDoc}
     *  This implementation moves the last node in the complete binary tree
     *  to the location of the removed node, and then "heapifies" the tree
     *  to preserve the heap invariant.
     */
    @Override
    public T remove(T itemToFind)
    {
        // Find the item to remove.
        int removalIndex = findItem(itemToFind);
        T itemToReturn = theList.get(removalIndex);

        // Move the last item in the complete tree to here and then
        // percolate it back down the tree as necessary.
        int lastIndex = theList.size() - 1;
        theList.set(removalIndex, theList.get(lastIndex));
        theList.remove(lastIndex);
        maxPercolateDown(removalIndex);

        return itemToReturn;
    }

    /** Heapifies the tree, or percolates up, by repeatedly comparing the
     *  new node's value with its parent's value, swapping the two values
     *  if the new node is bigger, and continuing up the tree comparing the
     *  new node with its new parent, until either it comes to a parent
     *  with a bigger value or it hits the root of the tree.
     *  @param newNodeIndex  The index of the most recently added node in
     *                       the tree; it starts out as the last index in
     *                       the complete tree but changes as the new node
     *                       percolates up through the heap.
     */
    private void maxPercolateUp(int newNodeIndex)
    {
        // Compare this value to its parent.  If this node is bigger, swap
        // them and keep going.  As soon as the new node is smaller than
        // or equal to its parent (or less than 0), stop.
        while ( newNodeIndex > 0 )
        {
            T thisValue = theList.get(newNodeIndex);
            int parentIndex = parent(newNodeIndex);

            // NEED CODE HERE !!!

        }
    }

    /** Heapifies the tree, or percolates down, by repeatedly comparing the
     *  a node's value with the values in its two children, swapping the
     *  node with its larger child if the child is larger than the parent,
     *  and continuing down the tree comparing the nodes with their
     *  children until either a node is larger than both children OR the
     *  method gets to the bottom of the tree.
     *    @param index  The index of the node that may need to be
     *                  percolated down.
     */
    private void maxPercolateDown(int index)
    {
        // Loop through nodes to travel down the tree until we get to a
        // leaf (a node with no left child).  Since this is a complete
        // tree, if the left child is empty, the right child will be also.
        int leftIndex;
        while ( (leftIndex = leftChild(index)) < theList.size() )
        {
            // Determine whether the value at this index is larger than the
            // value at either the left child or right child (whichever is
            // larger).  Start by considering the left child.
            T thisValue = theList.get(index);
            T leftChildValue = theList.get(leftIndex);
            int indexOfLarger = leftIndex;

            // Is there a right child too?  Is it larger than left child?

            // NEED CODE HERE !!!

            // Is the larger child larger than the current node?
            T largerValue = theList.get(indexOfLarger);

            // NEED CODE HERE !!!

            index = indexOfLarger;
        }
    }

    // Test driver.
    public static void main(String args[])
    {
        System.out.println("Testing K_MaxHeap.");

        // Construct several trees for testing purposes: one will stay
        // empty, one will have a single data element, and one will have
        // multiple data items.  (All start out empty, though.)
        K_BinaryTree<Integer> emptyTree = new K_MaxHeap<>();
        K_BinaryTree<Integer> singleNodeTree = new K_MaxHeap<>();
        K_BinaryTree<Integer> biggerTree = new K_MaxHeap<>();

        // Construct a print visitor to use with any style of traversal.
        NodeVisitor<Integer> printer = new PrintAction<>();

        // Add one data item to singleNodeTree.
        singleNodeTree.add(100);

        // Add multiple elements to biggerTree.
        System.out.println("Add 12, 7, 3.");
        biggerTree.add(12);
        biggerTree.add(7);
        biggerTree.add(3);
        System.out.println("******Breadth-First Traversal******");
        System.out.println("Expected: 12, 7, 3 (on separate lines)");
        biggerTree.breadthFirstTraversal(printer);
        System.out.println();
        System.out.println("Add 4, 8, 25, 0.");
        biggerTree.add(4);
        biggerTree.add(8);
        biggerTree.add(25);
        biggerTree.add(0);
        System.out.println("******Breadth-First Traversal******");
        System.out.println("Expected: 25, 8, 12, 4, 7, 3, 0 (on separate lines)");
        biggerTree.breadthFirstTraversal(printer);
        System.out.println();
        System.out.println("Add 142.");
        biggerTree.add(142);
        System.out.println("******Breadth-First Traversal******");
        System.out.println("Expected: 142, 25, 12, 8, 7, 3, 0, 4 (on separate lines)");
        biggerTree.breadthFirstTraversal(printer);
        System.out.println();
        System.out.println("Add 17, 26.");
        biggerTree.add(17);
        biggerTree.add(26);
        System.out.println("******Breadth-First Traversal******");
        System.out.println("Expected: 142, 26, 12, 17, 25, 3, 0, 4, 8, 7 (on separate lines)");
        biggerTree.breadthFirstTraversal(printer);
        System.out.println();

        // Print the height of an empty tree, a single-node tree, and a
        // non-empty tree (the bigger tree constructed above).
        System.out.println("Height of an empty tree: " +
                emptyTree.height() + "  (Expected: 0)");
        System.out.println("Height of a single-node tree: " +
                singleNodeTree.height() + "  (Expected: 1)");
        System.out.println("Height of the bigger tree: " +
                biggerTree.height() + "  (Expected: 4)");
        System.out.println();

        // Print the values in the bigger tree.
        System.out.println("******Breadth-First Traversal******");
        System.out.println("Expected: 142, 26, 12, 17, 25, 3, 0, 4, 8, 7 (on separate lines)");
        biggerTree.breadthFirstTraversal(printer);
        System.out.println();
        System.out.println("******Pre-Order Traversal******");
        System.out.println("Expected: 142, 26, 17, 4, 8, 25, 7, 12, 3, 0 (on separate lines)");
        biggerTree.preOrderTraversal(printer);
        System.out.println();

        // Remove an item from the bigger tree.  Print the modified tree.
        System.out.println("Remove 26.");
        biggerTree.remove(26);
        System.out.println();
        System.out.println("******Breadth-First Traversal******");
        System.out.println("Expected: 142, 25, 12, 17, 7, 3, 0, 4, 8 (on separate lines)");
        biggerTree.breadthFirstTraversal(printer);
        System.out.println();
        System.out.println("******Pre-Order Traversal******");
        System.out.println("Expected: 142, 25, 17, 4, 8, 7, 12, 3, 0 (on separate lines)");
        biggerTree.preOrderTraversal(printer);
        System.out.println();

        // Remove an item from the bigger tree.  Print the modified tree.
        System.out.println("Remove 8.");
        biggerTree.remove(8);
        System.out.println();
        System.out.println("******Breadth-First Traversal******");
        System.out.println("Expected: 142, 25, 12, 17, 7, 3, 0, 4 (on separate lines)");
        biggerTree.breadthFirstTraversal(printer);
        System.out.println();
        System.out.println("******Pre-Order Traversal******");
        System.out.println("Expected: 142, 25, 17, 4, 7, 12, 3, 0 (on separate lines)");
        biggerTree.preOrderTraversal(printer);
        System.out.println();

        // Remove an item from the bigger tree.  Print the modified tree.
        System.out.println("Remove 142.");
        biggerTree.remove(142);
        System.out.println();
        System.out.println("******Breadth-First Traversal******");
        System.out.println("Expected: 25, 17, 12, 4, 7, 3, 0 (on separate lines)");
        biggerTree.breadthFirstTraversal(printer);
        System.out.println();
        System.out.println("******Pre-Order Traversal******");
        System.out.println("Expected: 25, 17, 4, 7, 12, 3, 0 (on separate lines)");
        biggerTree.preOrderTraversal(printer);
        System.out.println();

        // Remove an item from the bigger tree.  Print the modified tree.
        System.out.println("Remove 17.");
        biggerTree.remove(17);
        System.out.println();
        System.out.println("******Breadth-First Traversal******");
        System.out.println("Expected: 25, 7, 12, 4, 0, 3 (on separate lines)");
        biggerTree.breadthFirstTraversal(printer);
        System.out.println();
        System.out.println("******Pre-Order Traversal******");
        System.out.println("Expected: 25, 7, 4, 0, 12, 3 (on separate lines)");
        biggerTree.preOrderTraversal(printer);
        System.out.println();

    }


}    //end class K_MaxHeap<T>