import java.util.ArrayList;

/**
 * K_ALCompleteBinTree<T> implements a Complete Binary Tree using an
 * ArrayList.  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 17 November 2025
 *
 * @param <T> The type of data stored.
 * 
 */
public class K_ALCompleteBinTree<T> implements K_BinaryTree<T>
{
    protected ArrayList<T> theList;

    /** Creates an empty binary tree with no data and no children.
     */
    public K_ALCompleteBinTree()
    {
        theList = new ArrayList<T>();
    }

    /** {@inheritDoc}
     */
    public boolean isEmpty()
    {
        return theList.isEmpty();
    }

    /** Gets the index for the left child.
     *      @return The index of the left child.
     */
    public int leftChild(int parentIndex)
    {
        return 2 * parentIndex + 1;
    }

    /** Gets the index for the right child.
     *      @return The index of the right child.
     */
    public int rightChild(int parentIndex)
    {
        return 2 * parentIndex + 2;
    }

    /** Gets the index for the parent.
     *      @return The index of the parent node.
     */
    public int parent(int childIndex)
    {
        return (childIndex - 1) / 2;  // Truncates to floor((i-1)/2).
    }

    /** {@inheritDoc}
     *  This implementation adds data in breadth-first (top-down,
     *  left-to-right) order, creating a complete binary tree.
     */
    public void add(T value)
    {
        // This implementation adds the data to the end of the ArrayList,
        // simulating breadth-first (top-down, left-to-right) order,
        // creating a complete binary tree.
        theList.add(value);
    }

    /** {@inheritDoc}
     *  The node being removed is replaced with the last node in the tree.
     *  The original breadth-first traversal order is not preserved, but
     *  the tree is still a complete binary tree (the invariant is
     *  preserved).
     */
    public T remove(T itemToFind)
    {
        // Initialize the itemToReturn to be null.
        T itemToReturn = null;

        // Find the index of the item to remove.  Will be -1 if not found;
        int index = findItem(itemToFind);
        if ( index == -1 )
            return null;

        // Move the last item to here, then delete it from the end.
        itemToReturn = theList.get(index);
        theList.set(index, theList.get(theList.size() - 1));
        theList.remove(theList.size() - 1);

        return itemToReturn;
    }

    /** Finds the given item and returns the index indicating its location
     *  in the ArrayList implementation.
     *    @param itemToFind  The data value to find in the tree.
     *    @return The index of the found item, or -1 if not found.
     */
    protected int findItem(T itemToFind)
    {
        for ( int index = 0; index < theList.size(); index++ )
        {
            if ( theList.get(index).equals(itemToFind) )
            {
                return index;
            }
        }

        return -1;
    }

    /** {@inheritDoc}
     */
    public void preOrderTraversal(NodeVisitor<T> visitor)
    {
        if ( isEmpty() )
            return;

        preOrderHelper(visitor, 0);
    }    

    /** Recursive helper function implementing pre-order functionality.
     */
    private void preOrderHelper(NodeVisitor<T> visitor, int index)
    {
        if ( index >= theList.size() )
            return;

        visitor.visit(theList.get(index));
        preOrderHelper(visitor, leftChild(index));
        preOrderHelper(visitor, rightChild(index));
    }    

    /** {@inheritDoc}
     */
    public void inOrderTraversal(NodeVisitor<T> visitor)
    {
        if ( isEmpty() )
            return;

        inOrderHelper(visitor, 0);
    }    

    /** Recursive helper function implementing in-order functionality.
     */
    public void inOrderHelper(NodeVisitor<T> visitor, int index)
    {
        // NEED CODE HERE !!!
        if ( index >= theList.size() )
            return;

        inOrderHelper(visitor, leftChild(index));
        visitor.visit(theList.get(index));
        inOrderHelper(visitor, rightChild(index));
    }    

    /** {@inheritDoc}
     */
    public void postOrderTraversal(NodeVisitor<T> visitor)
    {
        // NEED CODE HERE !!!
    }    

    /** {@inheritDoc}
     */
    public void breadthFirstTraversal(NodeVisitor<T> visitor)
    {
        // NEED CODE HERE !!!
        for ( T item : theList )
            visitor.visit(item);
    }

    /** {@inheritDoc}
     */
    public int height()
    {
        if ( isEmpty() )
            return 0;

        // The height of this tree is log(theList.size()).
        // NEED CODE HERE !!!
        return 0;                        // stub place-holder
    }

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

        // 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_ALCompleteBinTree<>();
        K_BinaryTree<Integer> singleNodeTree = new K_ALCompleteBinTree<>();
        K_BinaryTree<Integer> biggerTree = new K_ALCompleteBinTree<>();

        // 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.
        biggerTree.add(12);
        biggerTree.add(7);
        biggerTree.add(3);
        biggerTree.add(4);
        biggerTree.add(8);
        biggerTree.add(25);
        biggerTree.add(0);
        biggerTree.add(142);
        biggerTree.add(17);
        biggerTree.add(26);

        // 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: 12, 7, 3, 4, 8, 25, 0, 142, 17, 26 (on separate lines)");
        biggerTree.breadthFirstTraversal(printer);
        System.out.println();
        System.out.println("******Pre-Order Traversal******");
        System.out.println("Expected: 12, 7, 4, 142, 17, 8, 26, 3, 25, 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 7.");
        biggerTree.remove(7);
        System.out.println();
        System.out.println("******Breadth-First Traversal******");
        System.out.println("Expected: 12, 26, 3, 4, 8, 25, 0, 142, 17 (on separate lines)");
        biggerTree.breadthFirstTraversal(printer);
        System.out.println();
        System.out.println("******Pre-Order Traversal******");
        System.out.println("Expected: 12, 26, 4, 142, 17, 8, 3, 25, 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: 12, 26, 3, 4, 8, 25, 0, 142");
        biggerTree.breadthFirstTraversal(printer);
        System.out.println();
        System.out.println("******Pre-Order Traversal******");
        System.out.println("Expected: 12, 26, 4, 142, 8, 3, 25, 0");
        biggerTree.preOrderTraversal(printer);
        System.out.println();

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

    }


}    //end class K_ALCompleteBinTree<T>