import java.util.ArrayList;

/**
 * K_CompleteALBinTree<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 18 November 2025
 *
 * @param <T> The type of data stored.
 * 
 */
public class K_CompleteALBinTree<T> implements K_BinaryTree<T>
{
    protected ArrayList<T> theList;

    /** Creates an empty binary tree with no data and no children.
     */
    public K_CompleteALBinTree()
    {
        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 leftChildIndex(int parentIndex)
    {
        return 2 * parentIndex + 1;
    }

    /** Gets the index for the right child.
     *      @return The index of the right child.
     */
    public int rightChildIndex(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,
        // creating a complete binary tree.
        theList.add(value);
    }

    /** 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}
     *  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;
    }

    /** {@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)
    {
        // Base case: try to go to a node beyond the end of the array.
        if ( index >= theList.size() )
            return;

        visitor.visit(theList.get(index));
        preOrderHelper(visitor, leftChildIndex(index));
        preOrderHelper(visitor, rightChildIndex(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)
    {
        // Base case: try to go to a node beyond the end of the array.
        if ( index >= theList.size() )
            return;

        // NEED CODE HERE !!!
    }    

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

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

    /** {@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
    }

    /** Returns true if the index is the index of a leaf node in the tree.
     *    @param index  The index of the node to check.
     *    @return True if the node at the given index is a leaf node;
     *            false otherwise.
     */
    protected boolean isLeaf(int index)
    {
        // Since this is a complete binary tree, the node indicated by the
        // given index is a leaf if and only it has no left child; no
        // node in a complete binary tree can have a right child if it has
        // no left child.
        return leftChildIndex(index) >= theList.size();
    }

}    // end class K_CompleteALBinTree<T>