class Set
{

  /*
   * This exception is thrown by various methods
   * of the Set class. 
   *
   * The constructor takes a string that describes the specific 
   * situation
   */
  public class SetException extends Exception
  {
    public SetException (String s)
    { 
      super (s);
    }
  }


  /*
   * Declare any instance variables here
   */
  private LinkedList items;


  /*
   * This is the default constructor. 
   * It just creates an empty set.
   * Basically, it creates an empty linked list.
   */
  public Set()
  {
    items = new LinkedList();
  }


  /*
   * This is a copy constructor. It creates a new set from
   * an old set
   */
  public Set (Set original) throws SetException
  {
    items = new LinkedList();

    original.items.resetIndex();
    for (Object item = original.items.getIndexedNode();
         item != null;
         original.items.advanceIndex(), item = original.items.getIndexedNode() )
    {
      addItem(item);
    }
  }


  /*
   * Returns the items in the set as a string
   */
  public String toString()
  {
    return items.toString();
  }


  /*
   * Returns true if the item is in the set and false
   * otherwise
   */
  public boolean member(Object item)
  {
    return items.find (item);
  }


  /*
   * This method should add an item to the set. It should throw 
   * an exception if the item is already in the set.
   *
   * Specifically, you should define a SetException and throw
   * this exception. When you create a new instance of this 
   * exception, you should set its value to "Item already in set."
   */

  public void addItem (Object item) throws SetException
  {
    if (items.find (item))
      throw new SetException ("Item already in set");

    items.addHead(item);
  }


  /*
   * This method should remove an item from the set. It should throw 
   * an exception if the item is not in the set.
   *
   * Specifically, you should define a SetException and throw
   * this exception. When you create a new instance of this 
   * exception, you should set its value to "Item not already in set."
   */

  public void removeItem (Object item) throws SetException
  {
    if (!items.find (item))
      throw new SetException ("Item not already in set");

    items.remove(item);
  }


  /*
   * This returns a new set that contains every element in
   * the original set and the set provided by the user
   */
  public Set union (Set in_set) throws SetException
  {
    Set newSet = new Set();
   
    items.resetIndex();
    for (Object item = items.getIndexedNode();
         item != null;
         items.advanceIndex(), item = items.getIndexedNode() )
    {
      newSet.addItem(item);
    }
   
    in_set.items.resetIndex();
    for (Object item = in_set.items.getIndexedNode();
         item != null;
         in_set.items.advanceIndex(), item = in_set.items.getIndexedNode() )
    {
      try
      {
        newSet.addItem(item);
      }
      catch (SetException e) {}
    }

    return newSet;
  }


  /*
   * This returns a new set that contains only those elements
   * in the original set and the set provided by the user
   */
  public Set intersection (Set in_set) throws SetException
  {
    Set newSet = new Set();
   
    items.resetIndex();
    for (Object item = items.getIndexedNode();
         item != null;
         items.advanceIndex(), item = items.getIndexedNode() )
    {

      if (!in_set.member(item))
        continue;
      newSet.addItem(item);
    }

    return newSet;
  }


  /*
   * This returns a new set that contains only those elements
   * in the original set or the set provided by the user, but
   * not both.
   */
  public Set xor (Set in_set) throws SetException
  {
    Set newSet = new Set();
   
    items.resetIndex();
    for (Object item = items.getIndexedNode();
         item != null;
         items.advanceIndex(), item = items.getIndexedNode() )
    {

      if (in_set.member(item))
        continue;
      newSet.addItem(item);
    }
   
    in_set.items.resetIndex();
    for (Object item = in_set.items.getIndexedNode();
         item != null;
         in_set.items.advanceIndex(), item = in_set.items.getIndexedNode() )
    {

      if (member(item))
        continue;
      newSet.addItem(item);
    }


    return newSet;
  }

  public static void main (String []argv) throws SetException
  {
    Set set1 = new Set();

    set1.addItem ("one");
    set1.addItem ("two");
    set1.addItem ("three");

    Set set2 = new Set (set1);

    set2.addItem ("four");
    set2.addItem ("five");
    set2.addItem ("eight");
    
    set1.addItem ("six");
    set1.addItem ("seven");

    System.out.println ("Unions");
    System.out.println (set1.union(set2));
    System.out.println (set2.union(set1));

    System.out.println ("");

    System.out.println ("Intersections");
    System.out.println (set1.intersection(set2));
    System.out.println (set2.intersection(set1));

    System.out.println ("");

    System.out.println ("XORs");
    System.out.println (set1.xor(set2));
    System.out.println (set2.xor(set1));
  }
}