import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Objects;

/**
 * An implementation of the Bag interface that uses an array to hold its 
 * elements. This version has incomplete implementations of {@code iterator},
 * {@code addAll}, {@code containsAll}, {@code removeAll} and {@code retainAll}
 * (each of which throws an {@code UnsupportedOperationException}).
 *
 * @author Mark Young (A00000000)
 *
 * @param <T> Base type of this Bag
 */
public class ArrayBag<T> implements Bag<T> {

    // ---------- capacity constants -------------------------------------- //
    // Capacity for a Bag when the user declines to provide one
    private static final int DEFAULT_SIZE = 11;

    // Maximum capacity we allow -- hoping to avoid OutOfMemoryError
    private static final int MAX_SIZE = Integer.MAX_VALUE - 8;

    // ---------- instance variables -------------------------------------- //
    // Array to hold the Bag's contents
    private T[] contents;

    // Count of items in Bag
    private int numInBag;

    // ---------- constructors -------------------------------------------- //

    /**
     * Create an array-based Bag.
     *
     * @param capacity the maximum capacity of the Bag.
     */
    @SuppressWarnings("unchecked")
    public ArrayBag(int capacity) {
        if (0 <= capacity && capacity <= MAX_SIZE) {
            contents = (T[]) new Object[capacity];
            numInBag = 0;
        } else {
            throw new IllegalArgumentException("Invalid capacity: " + capacity);
        }
    }

    /**
     * Create an array-based Bag with default capacity.
     */
    public ArrayBag() {
        this(DEFAULT_SIZE);
    }

    // ---------- Bag interface methods ----------------------------------- //

    /**
     * Gets the current number of entries in this bag. That is, the count of 
     * items that have been added minus the items that have been removed.
     *
     * @return The integer number of entries currently in the bag.
     */
    @Override
    public int size() {
        return numInBag;
    }

    /**
     * Sees whether this bag is empty. That is, the count of items in this bag 
     * is zero.
     *
     * @return True if the bag is empty, or false if not.
     */
    @Override
    public boolean isEmpty() {
        return numInBag == 0;
    }

    /**
     * Adds a new entry to this bag. The add method will fail if the bag is 
     * full and cannot be made larger.
     *
     * @param newEntry The object to be added as a new entry.
     * @return True if the addition is successful, or false if not.
     */
    @Override
    public boolean add(T newEntry) {
        if (numInBag == contents.length && !resize()) {
            return false;
        } else {
            // add new entry at first available location in array
            contents[numInBag] = newEntry;
            ++numInBag;
            return true;
        }
    }

    @Override
    public String toString() {
        return Arrays.toString(toArray());
    }

    /**
     * Removes one occurrence of a given entry from this bag. If anything 
     * equals to anEntry is already in the bag, the bag will afterwards 
     * contain one fewer copies of that element.
     *
     * @param anItem The entry to be removed.
     * @return True if the removal was successful, or false if not.
     */
    @Override
    public boolean remove(Object anItem) {
        int posn = findPosn(anItem);
        if (posn < 0) {
            return false;
        } else {
            removeItemAt(posn);
            return true;
        }
    }

    /**
     * Removes one unspecified entry from this bag, if possible. Throws a
     * NoSuchElementException if the bag was already empty.
     *
     * @return the removed entry
     * @throws NoSuchElementException if the bag was already empty
     */
    @Override
    public T remove() {
        if (numInBag == 0) {
            throw new NoSuchElementException();
        } else {
            T result = removeItemAt(numInBag - 1);
            return result;
        }
    }

    /**
     * Removes all entries from this bag. Makes the bag empty.
     */
    @Override
    public void clear() {
        for (int i = 0; i < numInBag; ++i) {
            contents[i] = null;
        }
        numInBag = 0;
    }

    /**
     * Tests whether this bag contains a given entry. Any entry that claims to 
     * be equals to anItem will cause the method to return true.
     *
     * @param anItem The entry to locate.
     * @return True if the bag contains anItem, or false if not.
     */
    @Override
    public boolean contains(Object anItem) {
        return findPosn(anItem) >= 0;
    }

    /**
     * Counts the number of times a given entry appears in this bag. All 
     * entries that say they are equals to anItem will be counted.
     *
     * @param anItem The entry to be counted.
     * @return The number of times anItem appears in the bag.
     */
    @Override
    public int getFrequency(T anItem) {
        int count = 0;
        for (int i = 0; i < numInBag; ++i) {
            if (Objects.equals(contents[i], anItem)) {
                ++count;
            }
        }
        return count;
    }

    /**
     * Retrieves all entries that are in this bag. The result is an array that 
     * is exactly the correct size for the number of elements in the bag (for 
     * example, the array will have length zero if the bag is empty). The 
     * array contains as many copies of each element as the bag itself does.
     *
     * @return A newly allocated array of all the entries in the bag. Note: If
     *         the bag is empty, the returned array is empty.
     */
    @Override
    public Object[] toArray() {
        return Arrays.copyOf(contents, numInBag);
    }

    /**
     * Retrieves all entries that are in this bag, placing them in the given 
     * array, if it has enuf space. Otherwise a new array of exactly the 
     * required size is created and returned.
     *
     * @param a the array to put the elements into
     * @return The given array, if it was large enuf to hold all the elements
     * from this Bag; otherwise a newly allocated array of all the entries in 
     * the bag.
     */
    @SuppressWarnings("unchecked")
    @Override
    public <T> T[] toArray(T[] a) {
        // check if the given array is large enuf
        if (a.length < numInBag) {
            a = Arrays.copyOf(a, numInBag);
        }

        // copy elements into the return array
        for (int i = 0; i < numInBag; ++i) {
            a[i] = (T)contents[i];
        }

        // add a null afterwards, if there's space
        if (a.length > numInBag) {
            a[numInBag] = null;
        }

        // return the filled-in array
        return a;
    }

    // ---------- unimplemented methods ----------------------------------- //
    @Override
    public Iterator<T> iterator() {
        throw new UnsupportedOperationException("Not implemented yet");
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        throw new UnsupportedOperationException("Not implemented yet");
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        throw new UnsupportedOperationException("Not implemented yet");
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        throw new UnsupportedOperationException("Not implemented yet");
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        throw new UnsupportedOperationException("Not implemented yet");
    }


    // ---------- helper methods ------------------------------------------ //

    /**
     * Get the array index of an item in the Bag. Any location will do (if 
     * there's more than one), and return an invalid value if there's none.
     *
     * @param anItem the item to locate
     * @return the location of one such item in the array, or -1 if there are
     *         no such elements.
     */
    private int findPosn(Object anItem) {
        for (int posn = 0; posn < numInBag; ++posn) {
            if (Objects.equals(contents[posn], anItem)) {
                return posn;
            }
        }
        return -1;
    }

    /**
     * Deal with the details of removing one item from the array. Move the last
     * item up into the emptied space and null out the link from that location.
     *
     * @param posn the position of the item to be removed.
     * @return the item removed.
     */
    private T removeItemAt(int posn) {
        T result = contents[posn];
        contents[posn] = contents[numInBag - 1];
        contents[numInBag - 1] = null;
        --numInBag;
        return result;
    }

    /**
     * Make the array bigger, if possible.
     *
     * @return true if the array could be made bigger; false otherwise
     */
    private boolean resize() {
        int oldSize = contents.length;
        int newSize = (oldSize > MAX_SIZE / 2) ? MAX_SIZE : 2 * oldSize;
        if (newSize > oldSize) {
            contents = Arrays.copyOf(contents, newSize);
            return true;	// resized successsfully
        } else {
            return false;	// failed to resize
        }
    }

}