import java.util.Arrays;

public class IntArrayBag implements Cloneable
{
  // Class invariant
  //   "size" is the number of elements in the bag, 
  //     and 0 <= size <= data.length
  //   "data" holds the elements in the bag in 
  //     the index range [0, size)
  private int size;
  private int[] data;
  private static final int DEFAULT_CAPACITY = 10;
  
  public IntArrayBag ()
  {
    this (DEFAULT_CAPACITY);
  }
  
  public IntArrayBag (int capacity)
  {
    this.size = 0;
    if (capacity < 0)
      throw new IllegalArgumentException ("capacity is negative: " + capacity);
    this.data = new int[capacity];
  }

  public void add (int e)
  {
    if (size == data.length)
    {
      ensureCapacity (size * 2 + 1);
    }
    data[size++] = e;
  }
  
  public void addMany (int... elements)
  {
    ensureCapacity (size + elements.length);
    System.arraycopy (elements, 0, data, size, elements.length);
    size += elements.length;    
  }
  
  public void addAll (IntArrayBag addend)
  {
    ensureCapacity (size + addend.size);
    System.arraycopy (addend.data, 0, data, size, addend.size);
    size += addend.size;
  }

  public IntArrayBag clone ()
  {
    try
    {
      IntArrayBag bag = (IntArrayBag) super.clone ();
      bag.data = data.clone (); 
      return bag;
    }
    catch (CloneNotSupportedException e)
    {
      throw new RuntimeException ("Cloneable not implemented");
    }
  }
  
  public int countOccurrences (int e)
  {
    int count = 0;
    for (int i = 0; i < size; ++i)
      if (data[i] == e)
        ++count;
    return count;
  }

  // Exercise
  public int grab ()
  {
    return 0;
  }

  public void ensureCapacity (int minimumCapacity)
  {
    if (minimumCapacity <= data.length)
      return;

    data = Arrays.copyOf (data, minimumCapacity);
  }
  
  public int capacity ()
  {
    return data.length;
  }
  
  public boolean remove (int e)
  {
    for (int i = 0; i < size; ++i)
      if (data[i] == e)
      {
        --size;
        data[i] = data[size];
        return true;
      }
    return false;
  }
  
  public int size ()
  {
    return size;
  }
  
  public boolean empty ()
  {
    return size == 0;
  }
  
  public void trimToSize ()
  {
    data = Arrays.copyOf (data, size);
  }
  
  public static IntArrayBag union (IntArrayBag b1, IntArrayBag b2)
  {
    IntArrayBag result = new IntArrayBag (b1.size + b2.size);
    result.addAll (b1);
    result.addAll (b2);
    
    return result;
  }

  // Exercise
  public boolean equals (Object obj)
  {

  }
  
  // Exercise
  public String toString ()
  {

  }
}