import java.util.Arrays;

/******************************************************************************
 * An IntArrayMultiSet is a collection of int numbers. The same number may
 * appear multiple times in a set.
 *
 * @note (1) The capacity of one of these sets can change after it's created,
 *       but the maximum capacity is limited by the amount of free memory on the
 *       machine. The constructor, addItem, clone, and union will result in an
 *       OutOfMemoryError when free memory is exhausted.
 *       <p>
 *       (2) A set's capacity cannot exceed the maximum integer 2,147,483,647
 *       (Integer.MAX_VALUE). Any attempt to create a larger capacity results in
 *       a failure due to an arithmetic overflow.
 *       <p>
 *       (3) Because of the slow linear algorithms of this class, large sets
 *       will have poor performance.
 *
 *
 * @author Michael Main, William Killian, CSCI 162.01 Fall 2018
 *
 * @version September 17, 2018
 *
 ******************************************************************************/
public class IntArrayMultiSet implements Cloneable {

        // Invariant of the IntArrayMultiSet class:
        //
        // 1. The number of elements in the set is in the instance variable
        // manyItems, which is no more than data.length.
        //
        // 2. For an empty set, we do not care what is stored in any of data;
        // for a non-empty set, the elements in the set are stored in data[0]
        // through data[manyItems-1], and we don't care what's in the
        // rest of data.

        private int[] data;
        private int manyItems;

        private static final int INITIAL_CAPACITY = 10;

        /**
         * Initialize an empty set with an initial capacity of 10. Note that the addItem
         * method works efficiently (without needing more memory) until this capacity is
         * reached.
         *
         * @postcondition This set is empty and has an initial capacity of 10.
         * @exception OutOfMemoryError
         *                Indicates insufficient memory for: new int[10].
         **/
        public IntArrayMultiSet() {
                this (INITIAL_CAPACITY);
        }

        /**
         * Initialize an empty set with a specified initial capacity. Note that the
         * addItem method works efficiently (without needing more memory) until this
         * capacity is reached.
         *
         * @param initialCapacity
         *            the initial capacity of this set
         * @precondition initialCapacity is non-negative.
         * @postcondition This set is empty and has the given initial capacity.
         * @exception IllegalArgumentException
         *                Indicates that initialCapacity is negative.
         * @exception OutOfMemoryError
         *                Indicates insufficient memory for: new int[initialCapacity].
         **/
        public IntArrayMultiSet(int initialCapacity) {
                if (initialCapacity < 0) {
                        throw new IllegalArgumentException("Capacity cannot be negative");
                }
                this.manyItems = 0;
                this.data = new int [initialCapacity];
        }

        /**
         * Add a new element to this set. If the new element would take this set beyond
         * its current capacity, then the capacity is increased before adding the new
         * element.
         *
         * @param element
         *            the new element that is being inserted
         * @postcondition A new copy of the element has been added to this set.
         * @exception OutOfMemoryError
         *                Indicates insufficient memory for increasing the set's
         *                capacity.
         * @note An attempt to increase the capacity beyond Integer.MAX_VALUE will cause
         *       the set to fail with an arithmetic overflow.
         **/
        public void add(int element) {
                if (manyItems == data.length) {
                        ensureCapacity(2 * manyItems);
                }
                data[manyItems] = element;
                ++manyItems;
        }

        /**
         * Add new elements to this set. If the new elements would take this set beyond
         * its current capacity, then the capacity is increased before adding the new
         * elements.
         *
         * @param elements
         *            (a variable-arity argument) one or more new elements that are
         *            being inserted
         * @postcondition A new copy of the element has been added to this set.
         * @exception OutOfMemoryError
         *                Indicates insufficient memory for increasing the set's
         *                capacity.
         * @note An attempt to increase the capacity beyond Integer.MAX_VALUE will cause
         *       the set to fail with an arithmetic overflow.
         **/
        public void addMany(int... elements) {
                ensureCapacity(manyItems + elements.length);
                System.arraycopy(
                                /* source */
                                elements, 0,
                                /* destination */
                                data, manyItems,
                                /* number of elements to copy */
                                elements.length);
                manyItems += elements.length;
        }

        /**
         * Add the contents of another set to this set.
         *
         * @param other
         *            a set whose contents will be added to this set
         * @precondition The parameter, other, is not null.
         * @postcondition The elements from other have been added to this set.
         * @exception NullPointerException
         *                Indicates that other is null.
         * @exception OutOfMemoryError
         *                Indicates insufficient memory to increase the size of the set.
         * @note An attempt to increase the capacity beyond Integer.MAX_VALUE will cause
         *       an arithmetic overflow that will cause the set to fail. Such large
         *       collections should use a different set implementation.
         **/
        public void addAll(IntArrayMultiSet other) {
                ensureCapacity(manyItems + other.manyItems);
                System.arraycopy(
                                /* source */
                                other.data, 0,
                                /* destination */
                                data, manyItems,
                                /* number of elements to copy */
                                other.manyItems);
                manyItems += other.manyItems;
        }

        /**
         * Generate a copy of this set.
         *
         * @return The return value is a copy of this set. Subsequent changes to the
         *         copy will not affect the original, nor vice versa.
         * @exception OutOfMemoryError
         *                Indicates insufficient memory for creating the clone.
         **/
        public IntArrayMultiSet clone() {

                IntArrayMultiSet copy = null;
                try {
                        copy = (IntArrayMultiSet)super.clone();
                        copy.data = data.clone();
                } catch (CloneNotSupportedException e) {
                        throw new RuntimeException("IntArrayMultiSet isn't Cloneable");
                }
                return copy;
        }

        /**
         * Accessor method to count the number of occurrences of a particular element in
         * this set.
         *
         * @param target
         *            the element that needs to be counted
         * @return the number of times that target occurs in this set
         **/
        public int countOccurrences(int target) {
                int count = 0;
                for (int i = 0; i < manyItems; ++i) {
                        if (data[i] == target) {
                                ++count;
                        }
                }
                return count;
        }

        /**
         * Change the current capacity of this set.
         *
         * @param minimumCapacity
         *            the new capacity for this set
         * @postcondition This set's capacity has been changed to at least
         *                minimumCapacity. If the capacity was already at or greater
         *                than minimumCapacity, then the capacity is left unchanged.
         * @exception OutOfMemoryError
         *                Indicates insufficient memory for: new int[minimumCapacity].
         **/
        public void ensureCapacity(int minimumCapacity) {
                if (minimumCapacity < data.length) {
                        return;
                }

                // Version 1: simple for-loop
                int[] newData = new int[minimumCapacity];
                for (int i = 0; i < manyItems; ++i) {
                        newData[i] = data[i];
                }
                data = newData;

                // Version 2: System.arraycopy
                int[] newData = new int[minimumCapacity];
                System.arraycopy (data, 0, newData, 0, manyItems);
                data = newData;

                // Version 3: Arrays.copyOf
                data = Arrays.copyOf (data, minimumCapacity);
        }

        /**
         * Accessor method to get the current capacity of this set. The add method works
         * efficiently (without needing more memory) until this capacity is reached.
         *
         * @return the current capacity of this set
         **/
        public int getCapacity() {
                return data.length;
        }

        /**
         * Remove one copy of a specified element from this set.
         *
         * @param target
         *            the element to remove from the set
         * @return If target was found in the set, then one copy of target has been
         *         removed and the method returns true. Otherwise the set remains
         *         unchanged and the method returns false.
         **/
        public boolean remove(int target) {
                for (int i = 0; i < manyItems; ++i) {
                        if (data[i] == target) {
                                --manyItems;
                                data[i] = data[manyItems];
                                return true;
                        }
                }
                return false;
        }

        /**
         * Determine the number of elements in this set.
         *
         * @return the number of elements in this set
         **/
        public int size() {
                return manyItems;
        }

        /**
         * Reduce the current capacity of this set to its actual size (i.e., the number
         * of elements it contains).
         *
         * @postcondition This set's capacity has been changed to its current size.
         * @exception OutOfMemoryError
         *                Indicates insufficient memory for altering the capacity.
         **/
        public void trimToSize() {
                if (manyItems != data.length) {
                        data = Arrays.copyOf(data, manyItems);
                }
        }

        /**
         * Create a new set that contains all the elements from two other sets.
         *
         * @param b1
         *            the first of two sets
         * @param b2
         *            the second of two sets
         * @precondition Neither b1 nor b2 is null, and b1.getCapacity( ) +
         *               b2.getCapacity( ) &lt;= Integer.MAX_VALUE.
         * @return the union of b1 and b2
         * @exception NullPointerException
         *                Indicates that one of the arguments is null.
         * @exception OutOfMemoryError
         *                Indicates insufficient memory for the new set.
         * @note An attempt to create a set with a capacity beyond Integer.MAX_VALUE
         *       will cause an arithmetic overflow that will cause the set to fail. Such
         *       large collections should use a different set implementation.
         **/
        public static IntArrayMultiSet union(IntArrayMultiSet b1, IntArrayMultiSet b2) {
                IntArrayMultiSet add = new IntArrayMultiSet(b1.size() + b2.size());
                add.addAll(b1);
                add.addAll(b2);
                return add;
        }

}