/** FixedSizeArrayBag.java
    A class of bags whose entries are stored in a fixed-size array.
    @author Frank M. Carrano
    @version 4.0
*/
public final class FixedSizeArrayBag<T> implements BagInterface<T>
{
    private final T[] bag;
    private int numberOfEntries;
    private boolean initialized = false;
    private static final int DEFAULT_CAPACITY = 25;
    private static final int MAX_CAPACITY = 10000;

    //********************************************************************
    //This section contains two constructors and two public core methods.
    //********************************************************************
    /**
        Create an empty bag whose initial capacity is 25.
    */
    public FixedSizeArrayBag()
    {
        this(DEFAULT_CAPACITY);
    }

    /**
        Create an empty bag having a given capacity.
        @param desiredCapacity The integer capacity desired.
    */
    public FixedSizeArrayBag(int desiredCapacity)
    {
        if (desiredCapacity <= MAX_CAPACITY)
        {
            //Notes:
            //1. bag = new T[desiredCapacity]; //syntax error
            //   Cannot create array of generic type
            //2. bag = new Object[desiredCapacity]; //syntax error
            //   Incompatible types
            //3. bag = (T[]) new Object[desiredCapacity];
            //   Gives a compiler warning about an "unchecked cast"
            //We can tell the compiler that the cast is safe because the new
            //array contains null entries, which we do with the following
            //annotation:
            @SuppressWarnings("unchecked")
            //But this annotation can only be placed in front of a method
            //definition or a variable declaration, and since bag has already
            //been declared we have to do this:
            T[] tempBag = (T[]) new Object[desiredCapacity]; //Unchecked cast
            bag = tempBag;
            numberOfEntries = 0;
            initialized = true;
        }
        else
        {
            throw new IllegalStateException
            (
                "Attempt to create a bag "
                + "whose capacity exceeds allowed maximum."
            );
        }
    }

    /**
        Add a new entry to this bag.
        @param newEntry The object to be added as a new entry.
        @return true if the addition is successful, or false if not.
    */
    public boolean add(T newEntry)
    {
        checkInitialization();
        boolean result = true;
        if (isArrayFull())
        {
            result = false;
        }
        else
        {
            //Assertion: result is true here
            bag[numberOfEntries] = newEntry;
            numberOfEntries++;
        }
        return result;
    }

    /**
        Retrieve all entries that are in this bag and put them into an array.
        @return A newly allocated array of all the entries in this bag.
    */
    //public <T> T[] toArray() //Also OK
    public T[] toArray()
    {
        checkInitialization();

        //The cast is safe because the new array contains null entries.
        @SuppressWarnings("unchecked")
        T[] result = (T[]) new Object[numberOfEntries]; // Unchecked cast

        for (int index = 0; index < numberOfEntries; index++)
        {
            result[index] = bag[index];
        }
        return result;
        //Note that we could have made the body of this method
        //much shorter by using the Arrays.copyOf() method.
    }

    //********************************************************************
    //This section contains seven additional public methods.
    //********************************************************************
    /**
        Test whether this bag is empty.
        @return True if this bag is empty, or false if not.
    */
    public boolean isEmpty()
    {
        return numberOfEntries == 0;
    }

    /**
        Get the current number of entries in this bag.
        @return The integer number of entries currently in this bag.
    */
    public int getCurrentSize()
    {
        return numberOfEntries;
    }

    /**
        Count the number of times a given entry appears in this bag.
        @param anEntry The entry to be counted.
        @return The number of times anEntry appears in this bag.
    */
    public int getFrequencyOf(T anEntry)
    {
        checkInitialization();
        int counter = 0;
        for (int index = 0; index < numberOfEntries; index++)
        {
            if (anEntry.equals(bag[index]))
            {
                counter++;
            }
        }
        return counter;
    }

    /**
        Test whether this bag contains a given entry.
        @param anEntry The entry to locate.
        @return true if this bag contains anEntry, or false otherwise.
    */
    public boolean contains(T anEntry)
    {
        checkInitialization();
        return getIndexOf(anEntry) > -1; // or >= 0
    }

    /**
        Remove all entries from this bag.
    */
    public void clear()
    {
        while (!isEmpty())
        {
            remove();
        }
    }

    /**
        Remove one unspecified entry from this bag, if possible.
        @return Either the removed entry, if removal was successful, or null.
    */
    public T remove()
    {
        checkInitialization();
        T result = removeEntry(numberOfEntries - 1);
        return result;
    }

    /**
        Remove one occurrence of a given entry from this bag.
        @param anEntry The entry to be removed.
        @return true if the removal was successful, or false if not.
    */
    public boolean remove(T anEntry)
    {
        checkInitialization();
        int index = getIndexOf(anEntry);
        T result = removeEntry(index);
        return anEntry.equals(result);
    }

    //********************************************************************
    //This section contains four private helper methods.
    //********************************************************************
    //Return true if the array bag is full, or false if not.
    private boolean isArrayFull()
    {
        return numberOfEntries >= bag.length;
    }

    //Locate a given entry within the array bag.
    //Return the index of the entry if located, -1 otherwise.
    //Pre-condition: checkInitialization() has been called.
    private int getIndexOf(T anEntry)
    {
        int where = -1;
        boolean found = false;
        int index = 0;
        while (!found && (index < numberOfEntries))
        {
            if (anEntry.equals(bag[index]))
            {
                found = true;
                where = index;
            }
            index++;
        }
        //Assertion: If where > -1, anEntry is in the array bag, and it
        //equals bag[where]; otherwise, anEntry is not in the array.

        return where;
    }

    //Remove and return the entry at a given index within the array.
    //If no such entry exists, return null.
    //Pre-condition: 0 <= givenIndex < numberOfEntries.
    //Pre-condition: checkInitialization() has been called.
    private T removeEntry(int givenIndex)
    {
        T result = null;

        if (!isEmpty() && (givenIndex >= 0))
        {
            result = bag[givenIndex]; //Entry to remove
            int lastIndex = numberOfEntries - 1;

            //Replace entry to remove with last entry, then
            //remove reference to last entry and adjust numberOfEntries.
            bag[givenIndex] = bag[lastIndex];
            bag[lastIndex] = null;
            numberOfEntries--;
        }
        return result;
    }

    //Throw an exception if this object is not initialized.
    private void checkInitialization()
    {
        if (!initialized)
        {
            throw new SecurityException
            (
                "FixedSizeArrayBag object is not "
                + "initialized properly."
            );
        }
    }
}