import java.util.*;

public class Bag extends AbstractCollection
{ private Object[] objects;
  private int size=0;
  private static final int CAPACITY=16;

  private void resize()  // doubles the capacity
  { Object[] temp = objects;
    objects = new Object[2*temp.length];
    for (int i=0; i<size; i++)
      objects[i] = temp[i];
  }

  public Bag(int capacity)
  { objects = new Object[capacity];
  }

  public Bag()
  { objects = new Object[CAPACITY];
  }

  public Bag(Collection collection)
  { objects = new Object[2*collection.size()];
    for (Iterator it = collection.iterator(); it.hasNext(); )
      objects[size++] = it.next();
  }

  public Bag(Object[] objects)
  { this.objects = new Object[2*objects.length];
    for (int i=0; i<objects.length; i++)
      this.objects[size++] = objects[i];
  }

//////////////////////////////////////////////////////////////

  public boolean add(Object object)
  { if (size == objects.length) resize();
    objects[size++] = object;
    return true;
  }

  public boolean  addAll(Collection collection)
  { while (size+collection.size() >= objects.length)
      resize();
    for (Iterator it = collection.iterator(); it.hasNext(); )
      objects[size++] = it.next();
    return true;
  }

  public void clear()
  { for (int i=0; i<size; i++)
      objects[i] = null;
    size = 0;
  }

  public boolean contains(Object object)
  { for (int i=0; i<size; i++)
      if (object.equals(objects[i])) return true;
    return false;
  }

  public boolean containsAll(Bag bag)
  { for (Iterator it = bag.iterator(); it.hasNext(); )
      if (!this.contains(it.next())) return false;
    return true;
  }

  private static int frequency(Collection x, Object object)
  { int count=0;
    for (Iterator it = x.iterator(); it.hasNext(); )
      if (object.equals(it.next())) ++count;
    return count;
  }

  public boolean equals(Object object)
  { if (object == this) return true;
    if (object.hashCode() != this.hashCode()) return false;
    if (object.getClass() != this.getClass()) return false;
    Collection collection = (Collection)object;
    if (collection.size() != this.size()) return false;
    if (!collection.containsAll(this)) return false;
    if (!this.containsAll(collection)) return false;
    for (int i=0; i<size; i++)
    { Object x = objects[i];
      if (frequency(collection,x) != frequency(this,x)) return false;
    }
    return true;
  }

  public int hashCode()
  { int code=0;
    for (int i=0; i<size; i++)
      code += objects[i].hashCode();
    return code;
  }

  public boolean isEmpty()
  { return size == 0;
  }

  public Iterator iterator()
  { return new Iterator()  // anonymous inner class:
    { private int cursor=0;
      public boolean hasNext()
      { return cursor<size;
      }
      public Object next()
      { if (cursor>=size) return null;
        return objects[cursor++];
      }
      public void remove()
      { objects[--cursor] = objects[--size];
        objects[size] = null;
      }
    };
  }

  public boolean remove(Object object)
  { for (int i=0; i<size; i++)
      if (object.equals(objects[i]))
      { objects[i] = objects[--size];
        return true;
      }
    return false;
  }

  public boolean removeAll(Collection collection)
  { boolean modified=false;
    for (Iterator it = collection.iterator(); it.hasNext(); )
      if (this.remove(it.next())) modified = true;
    return modified;
  }

  public boolean retainAll(Collection collection)
  { boolean modified=false;
    for (int i=0; i<size; i++)
      if (!collection.contains(objects[i]))
      { remove(objects[i]);
        modified = true;
      }
    return modified;
  }

  public int size()
  { return size;
  }

  public Object[] toArray()
  { Object[] objects = new Object[size];
    for (int i=0; i<size; i++)
      objects[i] = this.objects[i];
    return objects;
  }

  public Object[] toArray(Object[] objects)
  { if (size > objects.length) objects = this.toArray();
    else
    { for (int i=0; i<size; i++)
        objects[i] = this.objects[i];
      for (int i=size; i<objects.length; i++)
        objects[i] = null;
    }
    return objects;
  }

  public String toString()
  { String s="{ ";
    if (size>0) s += this.objects[0];
    for (int i=1; i<size; i++)
      s += ", " + this.objects[i];
    return s + " }";
  }

}