/** Let's implement a bag using an ArrayList.  Some operations are rather
 *  straightforward because an ArrayList already has certain operations
 *  built-in.  This bag class needs a base type, so let's just say it's
 *  a bag of Item objects.  We'll assume that Item class has its own equals()
 *  and toString().
 *  Even though we're specifying the representation and other implementation
 *  details of a bag, we don't specify what the bag is useful for -- we just
 *  know it contains an ArrayList of Item objects.  The Item class is
 *  defined elsewhere.  So this class can be used for a variety of programs
 *  without modification.  Each new application just needs an Item class
 *  and an ItemComparator class.
 */
import java.util.*;

public class BagArrayList implements BagInterface
{
  private ArrayList list;

  // Although the interface didn't say so, we really need
  // a constructor.
  public BagArrayList()
  {
    list = new ArrayList();
  }

  public void add(Object o)
  {
    list.add(o);
  }

  // This remove() function, that takes no parameter, is supposed to
  // remove a random element from the bag.  So we need to pick a random
  // number, and then call the ArrayList remove function.
  public Object remove()
  {
    Random gen = new Random();
    int index = gen.nextInt(list.size());
    return list.remove(index);
  }

  // The ArrayList remove function needs to know the index, so we have
  // to find it in the bag first.  This adds complexity to the operation.
  // It will be linear instead of constant time.
  public Object remove(Object o)
  {
    int index = indexOf(o);
    if (index == -1)
      return null;
    else
      return list.remove(indexOf(o));
  }

  // This function is private because only here do we care that
  // the underlying implementation is an ArrayList.
  // As in the String indexOf, we'll return -1 if not found.
  // For this function to work, we need some way of determining
  // if two objects are equal.
  private int indexOf(Object o)
  {
    for (int i = 0; i < list.size(); ++i)
      if (((Item)list.get(i)).equals((Item) o))
        return i;
    return -1;
  }

  // To combine means to create a new bag and put into it the combined
  // contents of my bag and some other bag.  The original 2 bags are unchanged.
  public BagInterface combine(BagInterface b)
  {
    BagArrayList newBag = new BagArrayList();
    for (int i = 0; i < this.size(); ++i)
      newBag.add(list.get(i));
    for (int i = 0; i < ((BagArrayList) b).size(); ++i)
      newBag.add(((BagArrayList) b).list.get(i));
    return newBag;
  }

  // Need to sort the bags and then compare them by corresponding elements
  // one by one until we see a pair that doesn't match or we've seen them all.
  public boolean equals(BagInterface b)
  {
    if (this.size() != b.size())
      return false;

    sort();
    ((BagArrayList) b).sort();

    for (int i = 0; i < list.size(); ++i)
      if (! list.get(i).equals(((BagArrayList) b).list.get(i)))
        return false;

    return true;
  }

  // We don't expect anyone outside of this file to be interested
  // in sorting the bag, so it's a private function.
  // Since we are using Collections.sort, we need a comparator.
  private void sort() 
  {
    Collections.sort(list, new ItemComparator());
  }

  public void give(Object o, BagInterface b)
  {
    this.remove(o);
    b.add(o);
  }

  public int size()
  {
    return list.size();
  }

  public String toString() 
  {
    String build = "";
    for (int i = 0; i < list.size(); ++i)
      build += "\t" + list.get(i) + "\n";
    return build;
  }
}