Bag.java

import java.util.*;
 
public class Bag extends AbstractCollection 
{
  private Object[] objects;
  private int size = 0; 
  private static final int CAPACITY = 16;
 
  private void resize() 
  {
    Object[] temp=objects;
    objects = new Object[temp.length+CAPACITY];
    for(int i=0; i<size; i++)
      objects[i]=temp[i];
  }
 
  public Bag() 
  {
    objects = new Object[CAPACITY];
  }
 
  public Bag(Object[] objects) 
  {
    this.objects = new Object[objects.length+CAPACITY];
    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 (Collection collection) 
  {
    for (Iterator it=collection.iterator(); it.hasNext(); )
      if (!this.contains(it.next())) 
        return false;
    return true;    
  }
 
  public boolean isEmpty() 
  {
    return size==0;
  }
 
  private class BagIterator implements Iterator 
  {
    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 Iterator iterator() 
  {
    return new BagIterator();
  }
 
 
/*
  public Iterator iterator() 
  {
    return new Iterator() 
    {
      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];
        objects[size]=null;
        return true;
      }
    return false;
  }
 
  public boolean removeAll(Object object) 
  {   boolean modified=false;
    for(int i=0; i<size; i++)
      if (object.equals(objects[i])) 
      {
        objects[i--] = objects[--size];
        objects[size]=null;
        modified=true;
      }
    return modified;
  }
 
  public boolean removeAll(Collection collection) 
  {
    boolean modified = false;
    for(Iterator it = collection.iterator(); it.hasNext();)
      if (this.removeAll(it.next())) // ali remove()
           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 String toString() 
  {
    String s = "{ ";
    if (size>0)
      s+=this.objects[0];
    for (int i=1; i<size; i++)
      s+=", "+this.objects[i];
    return s+" }";
  }
}