/**
 * Represents a recursively-defined linked list, containing a reference to
 * a list element and a reference to a sublist representing the rest of the
 * list.  An empty list has a null reference for both the list element and
 * the sublist.
 *
 * @Author Started by Alyce Brady (modified most recently on December 5, 2025)
 * @Author Your Name
 * @version The Date
 */
public class K_RecList<T>
{
    private T element; 
    private K_RecList<T> next;

    /**
     * Creates an empty list.
     */
    public K_RecList()
    {
        this.element = null;
        this.next = null;
    }

    /**
     * Creates a list with a single element.
     * @param element - the element that the list will contain
     */
    public K_RecList(T element)
    {
        this.element = element;
        this.next = new K_RecList<>();
    }

    /**
     * Creates a list composed of an element and a list.
     * @param element - the element that the list will have at the head
     */
    public K_RecList(T element, K_RecList<T> list)
    {
        this.element = element;
        this.next = list;
    }

    /**
     * Returns the head of the list.
     */
    public T head()
    {
        return this.element;
    }

    /**
     * Returns the tail of the list (the list following the head).
     */
    public K_RecList<T> tail()
    {
        // If the list is empty, return the empty list.
        // Otherwise return the list following the head.
        return isEmpty() ? this : this.next;
    }

    /**
     * Returns true if the list is empty; false otherwise.
     * An empty list has a null reference for both the list element and
     * the sublist.
     */
    public boolean isEmpty()
    {
        return this.element == null && this.next == null;
    }

    /**
     * Returns the number of elements in the list.
     * (This method uses the ?: if expression rather than an if statement
     *  to make it more functional in nature.)
     */
    public int size()
    {
        return isEmpty() ? 0 : tail().size() + 1;
    }

    /**
     * Returns a string of space-separated elements in the list.
     * 
     * @return a string representing the elements in the list
     */
    @Override
    public String toString()
    {
        // Treat an empty list and a list with a single element as special
        // cases.
        if ( isEmpty() )            // empty list
            return "[ ]";
        if ( tail().isEmpty() )     // list with only a single element
            return "[ " + head() + " ]";

        // build string using head and tail, but strip "[" from tail.
        String strippedTail = tail().toString().substring(1);
        return "[ " + head().toString() + "," + strippedTail;
    }

    /**
     * Adds a new element AT THE BEGINNING of the list. 
     * @param newElement - The element to add
     */
    public void addFirst(T newElement) 
    {
        // Move the first element to a new node that will be the second
        // element (the head of a new, longer tail).
        this.next = new K_RecList(this.element, this.next);
        this.element = newElement;
    }

    /**
     * Adds a new element AT THE END of the list. 
     * @param newElement - The element to add
     */
    public void addLast(T newElement) 
    {
        // This is a recursive function, so check the base case first.
        // If we hit an empty list, add the element and add a new empty
        // list as the tail.
        // YOU NEED TO ADD CODE HERE!

        // Not at the end; recurse to get there.
        // YOU NEED TO ADD CODE HERE!
    }

    /**
     * Returns the element at the specified index. Throws
     * an IndexOutOfBoundsException if the index is out of bounds.
     *  
     * @param index - position of the element to get
     * @return the element at the specified index
     * @throws IndexOutOfBoundsException
     */
    public T get(int index) throws IndexOutOfBoundsException
    {
        // Make sure index was not out of range.
        if ( isEmpty() )
        {
            throw new IndexOutOfBoundsException("There is no element at index "
                    + index);
        }

        // Is the current head the one we're looking for? (index == 0)
        if ( index == 0 )
            return head();

        // Recurse through the list, but index in tail will be one less.
        return tail().get(index - 1);
    }

    /**
     * Replaces the element at the specified position in this list with the
     * specified new element. Throws an IndexOutOfBoundsException if the
     * index is out of bounds.
     *  
     * @param index - position of the element to replace
     * @param newElement - the element to be stored at the specified position
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException
     */
    public T set(int index, T element) throws IndexOutOfBoundsException
    {
        // YOU NEED TO ADD CODE HERE!
        return head();  // dummy stub code so it will compile
    }

    /**
     * Removes and returns the element at the specified index. Throws
     * an IndexOutOfBoundsException if the index is out of bounds.
     *  
     * @param index - position of the element to remove
     * @return the element that was removed
     * @throws IndexOutOfBoundsException
     */
    public T remove(int index) throws IndexOutOfBoundsException
    {
        // YOU NEED TO ADD CODE HERE!
        return head();  // dummy stub code so it will compile
    }

}