/**
 * CS 231 — Lab 1
 * Building an ArrayList
 *
 * Name:
 *
 * Purpose:
 * This class implements a generic, array-backed ArrayList.
 *
 * The starter code contains a combination of provided code, partially
 * implemented methods, and methods you will implement yourself. Follow
 * the TODO comments and hints as you work through each task.
 *
 * Your implementation must behave correctly because this ArrayList will
 * be used in Project 1 and will provide a foundation for future projects.
 *
 * @param <T> the type of elements stored in the ArrayList
 */
public class ArrayList<T> {

    // ============================================================
    // TASK 1 — Create Instance Variables and Constant
    // ============================================================


    // TODO:
    // Declare an integer constant named DEFAULT_CAPACITY that represents
    // the initial capacity of an ArrayList. Set its value to 10.
    // Be sure to give the constant appropriate access.
    //
    // If you don't know how to declare a constant, raise your hand!


    /** The underlying array that stores the elements. */
    private T[] arr;


    // TODO:
    // Declare an integer variable named size that will hold the number
    // of elements currently stored in the ArrayList.
    // Be sure to give the variable appropriate access.
    //
    // Size and capacity are not the same thing. Make sure you understand
    // this distinction and can explain it in your own words.


    // ============================================================
    // TASK 2 — Constructors and Size
    // ============================================================

    /**
     * Constructs an empty ArrayList with the default capacity.
     */
    public ArrayList() {
        // TODO:
        // Using the this operator to avoid duplicate initialization code,
        // call the one-argument constructor using the DEFAULT_CAPACITY constant.
    }


    /**
     * Constructs an empty ArrayList with the specified initial capacity.
     *
     * @param initialCapacity the starting capacity of the underlying array
     */
    public ArrayList(int initialCapacity) {
        // TODO:
        // Use the provided initializeArray(...) method to create the
        // underlying array with the requested initialCapacity.
        //
        // Then initialize size so that this new ArrayList is empty.
        //
        // Think about:
        //   - What argument should be passed to initializeArray(...)?
        //   - What should size be when an ArrayList is first created?
    }


    /**
     * Returns the number of elements currently stored in the ArrayList.
     *
     * Notice that size() is, in fact, a getter. Sometimes "get" can be
     * dropped from a getter's name when the method name is unambiguous.
     *
     * @return the number of elements in the list
     */
    public int size() {
        // TODO: Return the number of elements currently stored.
        return 0; // replace this line
    }


    // ============================================================
    // TASK 3 — Add Elements and Grow the Array
    // ============================================================

    /**
     * Adds item to the end of the ArrayList.
     *
     * If the underlying array is full, its capacity must be increased
     * before the new item is stored.
     *
     * @param item the item to add
     */
    public void add(T item) {
        // TODO:
        // 1. Decide whether there is room for another item.
        //
        // Hint: size tells you how many elements are currently stored.
        //       arr.length tells you the capacity of the underlying array.
        //
        // 2. If the array is full, increase its capacity.
        //
        // Hint: changeCapacity(...) can do the resizing work.
        //       A common strategy is to double the current capacity.
        //
        // 3. Store item in the next available position.
        //
        // 4. Update size.
    }


    /**
     * Changes the capacity of the underlying array while preserving
     * all elements currently stored in the ArrayList.
     *
     * @param newCapacity the new capacity of the underlying array
     */
    private void changeCapacity(int newCapacity) {

        // Save the current array before creating the new one.
        T[] oldArr = arr;

        // This creates a new underlying array with the requested capacity.
        initializeArray(newCapacity);

        // TODO:
        // Copy the elements that are currently part of the ArrayList
        // from oldArr into the new arr.
        //
        // Hint: How many elements actually belong to the list?
        //       Do you need to copy every position in oldArr?
    }

    // ============================================================
    // TASK 4 — Get and Set Elements
    // ============================================================

    /**
     * Returns the element stored at index.
     *
     * @param index the position of the element to retrieve
     * @return the element at index
     */
    public T get(int index) {
        // TODO: Return the element stored at index.
        return null; // replace this line
    }


    /**
     * Replaces the element at index with item.
     *
     * @param index the position to change
     * @param item the new item to store
     */
    public void set(int index, T item) {
        // TODO: Replace the element stored at index with item.
        //
        // Hint: Replacing an existing element does NOT change size.
    }


    // ============================================================
    // TASK 5 — Remove an Element
    // ============================================================

    /**
     * Removes and returns the element at index.
     *
     * @param index the position of the element to remove
     * @return the element that was removed
     */
    public T remove(int index) {

        // TODO 1:
        // Save the element being removed.
        // You will need to return it after changing the list.


        /*
         * TODO 2:
         * Removing an element leaves a gap in the underlying array.
         *
         * Example: remove(1)
         *
         * index:     0     1     2     3
         *          +-----+-----+-----+-----+
         * before:  |  A  |  B  |  C  |  D  |
         *          +-----+-----+-----+-----+
         *
         *          +-----+-----+-----+-----+
         * after:   |  A  |  C  |  D  |     |
         *          +-----+-----+-----+-----+
         *
         * Shift every element AFTER the removed element
         * one position to the left.
         *
         * Think carefully:
         *   - Where should the loop begin?
         *   - Where should it stop?
         *   - Which element should be copied into which position?
         */


        // TODO 3:
        // The list now contains one fewer element.


        // TODO 4:
        // Set the old location of the last element to null.
        // After shifting the elements to the left and decreasing size,
        // this position is no longer part of the ArrayList.


        // TODO 5:
        // Return the element that was removed.

        return null; // replace this line
    }


    /**
     * Creates the underlying generic array.
     *
     * Java does not allow us to directly write "new T[capacity]".
     * The cast and annotation below use Java features we have not covered yet,
     * so this method is provided for you.
     *
     * @param capacity the capacity of the new underlying array
     */
    @SuppressWarnings("unchecked")
    private void initializeArray(int capacity) {
        arr = (T[]) new Object[capacity];
    }


    // ============================================================
    // TASK 6 — Create a String Representation
    // ============================================================

    /**
     * Returns a String representation of the elements in the ArrayList.
     *
     * Examples:
     *   [] 
     *   [4]
     *   [4, 7, 2]
     *
     * @return a String representation of the ArrayList
     */
    @Override
    public String toString() {
        // TODO:
        // Build and return a String containing the elements in order,
        // enclosed in square brackets and separated by ", ".
        //
        // Think about:
        //   - How can you visit only the elements that are actually in the list?
        //   - How will you place ", " BETWEEN elements?
        //   - Make sure you do not leave an unnecessary comma after the last item.
        //   - What should an empty ArrayList return?

        return ""; // replace this line
    }
}