//  Data Structures with Java by John R. Hubbard
//  Copyright McGraw-Hill, 2001
//  Example 5.3 on page 97
//  A Bag class

public class Bag extends AbstractCollection
{ private Object[] objects;
  private int size=0;  // number of objects in the bag
  private static final int CAPACITY=16;  // default capacity
  
  private void resize(int capacity)
  // increases the length of objects[] to the given capacity
  // See Example 5.4 on page 99.

  public Bag()
  { // constructs an empty bag with the default capacity
    objects = new Object[CAPACITY];
  }
  
  public Bag(int capacity)
  // constructs an empty bag with the given capacity
  // See Problem 5.1 on page 104.
  
  public Bag(Collection collection)
  // constructs a bag containing the objects in the
  // given collection and with twice the capacity
  // See Example 5.5 on page 99.
  
  public Bag(Object[] objects)
  // constructs a bag containing the objects in the
  // given array and with twice the capacity
  // See Problem 5.2 on page 104.

  public boolean add(Object object)
  // adds the given object to this bag
  // See Example 5.6 on page 100.
  
  public boolean addAll(Collection collection)
  // adds all the objects in the given collection
  // to this bag
  // See Problem 5.3 on page 104.

  public void clear()
  // removes all the objects from this bag
  // See Problem 5.4 on page 105.
  
  public boolean contains(Object object)
  // returns true iff the given object
  // is equal to some object in this bag
  // See Example 5.7 on page 100.
  
  public boolean containsAll(Collection collection)
  // returns true iff every object in the given collection
  // is equal to some object in this bag; that is,
  // iff the the given collection is a subset of this bag;
  // See Problem 5.5 on page 105.

  private static int frequency(Collection x, Object object)
  // returns the number of objects in the given collection
  // that are equal to the given object
  // See Problem 5.6 on page 105.
  
  public boolean equals(Object object)
  // returns true iff the given object is a Bag
  // and has the same content as this bag
  // See Example 5.8 on page 101.
  
  public int hashCode()
  // returns a hash code for this bag that is the sum
  // of the hash codes of its elements
  // See Problem 5.7 on page 105.
  
  public boolean isEmpty()
  { // returns true iff this bag is empty
    return size == 0;
  }
  
  public Iterator iterator()
  // returns an iterator on this bag
  // See Example 5.12 on page 104.
  
  public boolean remove(Object object)
  // removes one of the given object from this bag;
  // returns true iff this bag was modified;
  // See Problem 5.8 on page 105.
  
  public boolean removeAll(Object object)
  // removes all of the given object from this bag;
  // returns true iff this bag was modified;
  // See Example 5.9 on page 101.
  
  public boolean removeAll(Collection collection)
  // removes from this bag all of the object that are also in
  // the given collection, thereby reducing this bag to its
  // set-theoretic intersection with that collection;
  // returns true iff this bag was modified;
  // See Problem 5.9 on page 105.
  
  public boolean retainAll(Collection collection)
  // removes from this bag all of the object that are not in
  // the given collection, thereby reducing this bag to its
  // set-theoretic complement relative to that collection;
  // returns true iff this bag was modified;
  // See Problem 5.10 on page 105.

  public int size()
  { // returns the number of objects in this bag;
    return size;
  }
  
  public Object[] toArray()
  // returns an array whose elements are in this bag;
  // See Example 5.10 on page 101.
  
  public Object[] toArray(Object[] objects)
  // returns an array whose elements are in this bag
  // if it is longer than the given object[] array;
  // otherwise, the given array is returned after removing
  // all of its elements and then loading it with the elements
  // of this bag, and padding the rest of it with nulls;
  // See Problem 5.11 on page 105.

  public String toString()
  // returns a String that shows the contents of this bag
  // See Problem 5.12 on page 105.
}