import java.util.Arrays;

public class IntArrayMultiSet implements IntMultiSet, Cloneable {

	private int[] data;
	private int manyItems;

	private static final int INITIAL_CAPACITY = 10;

	public IntArrayMultiSet() {
		this(INITIAL_CAPACITY);
	}

	public IntArrayMultiSet(int initialCapacity) {
		if (initialCapacity < 0) {
			throw new IllegalArgumentException("Capacity cannot be negative");
		}
		this.manyItems = 0;
		this.data = new int[initialCapacity];
	}

	public void add(int element) {
		if (manyItems == data.length) {
			ensureCapacity(2 * manyItems);
		}
		data[manyItems] = element;
		++manyItems;
	}

	public void addMany(int... elements) {
		ensureCapacity(manyItems + elements.length);
		System.arraycopy(elements, 0, data, manyItems, elements.length);
		manyItems += elements.length;
	}

	public void addAll(IntMultiSet o) {
		IntArrayMultiSet other = (IntArrayMultiSet) o;
		ensureCapacity(manyItems + other.manyItems);
		System.arraycopy(other.data, 0, data, manyItems, other.manyItems);
		manyItems += other.manyItems;
	}

	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;
	}

	public int size() {
		return manyItems;
	}

	public int countOccurrences(int target) {
		int count = 0;
		for (int i = 0; i < manyItems; ++i) {
			if (data[i] == target) {
				++count;
			}
		}
		return count;
	}

	public int getCapacity() {
		return data.length;
	}

	public void ensureCapacity(int minimumCapacity) {
		if (minimumCapacity < this.data.length) {
			data = Arrays.copyOf(data, minimumCapacity);
		}
	}

	public void trimToSize() {
		if (manyItems != data.length) {
			data = Arrays.copyOf(data, manyItems);
		}
	}

	public IntMultiSet 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;
	}
}