Introduction

This assignment asks you to implement a Set class using a LinkedList. Remember from a prior math class that a set is really nothing more than an unordered collection of items.

We have provided a skeleton for the Set and would like you to use the LinkedList class provided within the Java library.

The Set class will do all of the typical set things:

• Membership - test if an item is in the set
• Add - add an item to the set
• Add - add all of the items from one set into another set.
• Remove - remove an item from the set
• Remove - remove all items in one set from another set
• Intersection - return a set containing those items that are in both sets

This assignment is substantially longer and more complex than the prior assignment. Please start early and remember -- we're here to help.

Getting Started

We have provided a skeleton for the Set class. All you need to do is to implement each of the incomplete methods within this class.

The skeleton provides comments that describe the desired behavior of each method. Please be sure to follow this part of the specification. If you have any questions, please ask -- we're here to help.

You may implement additional private helper methods, as convenient. But, please do not change the interface to either of the classes -- implement exactly what we have asked.

The linked list should be the primary internal data structure for the Set. Please use the LinkedList provided by the Java API.

Your main() method, the test driver, is important. You will be graded, in part, based on the thoroughness of your test set.

Submission Requirements

For this assignment, you should hand in only the Set.java file which contains your solutions. Please note that the test driver (the main() method) is part of the Set class. The test program should not use any I/O.

The Set Class ( Set.java )

/*
 * Please note: The set operations should not make deep copies
 * of elements. Instead, sets should be viewed as containing references
 * to objects, not objects themselves.
 */
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
   */


  /*
   * This is the default constructor. 
   * It just creates an empty set.
   * Basically, it creates an empty linked list.
   */
  public Set()
  {
    /*
     * Your code here
     */
  }


  /*
   * This is a copy constructor. It creates a new set from
   * an old set. The new set includes one every item in
   * the original.
   */
  public Set (Set original) throws SetException
  {
    /*
     * Your code here
     */
  }


  /*
   * Returns the items in the set as a string
   */
  public String toString()
  {
    /*
     * Your code here
     */
  }


  /*
   * Returns true if the item is in the set and false
   * otherwise
   */
  public boolean member(Object item)
  {
    /*
     * Your code here
     */
  }


  /*
   * 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
  {
    /*
     * Your code here
     */
  }


  /*
   * This method should add all of the items from the newItems set
   * into the original set. It should throw an exception
   * upon discovering that any requested 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 addItems (Set newItems) throws SetException
  {
    /*
     * Your code here
     */
  }


  /*
   * 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
  {
    /*
     * Your code here
     */
  }


  /*
   * This method should remove all of the items in the "items" Set
   * from the current set. It should throw an exception 
   * upon discovering that any of the specified items is not in the
   * target 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 removeItems (Set items) throws SetException
  {
    /*
     * Your code here
     */
  }


  /*
   * This returns a new set that contains every element in
   * the original set and every element in the set provided by the user
   * No element should be in the returned set more than once.
   */
  public Set union (Set in_set) throws SetException
  {
    /*
     * Your code here
     */
  }


  /*
   * This returns a new set that contains only those elements
   * in the original set and the set provided by the user
   * No element should be in the returned set more than once.
   */
  public Set intersection (Set in_set) throws SetException
  {
    /*
     * Your code here
     */
  }


  /*
   * This returns a new set that contains only those elements
   * in the original set or the set provided by the user, but
   * not both. No element should be in the returned set more 
   * than once.
   */
  public Set xor (Set in_set) throws SetException
  {
    /*
     * Your code here
     */
  }


  /*
   * This returns true if the specified set is a proper subset of the target
   * set and false otherwise.
   */
  public boolean subset (Set subset) throws SetException
  {
    /*
     * Your code here
     */
  }

  
  /*
   * This should be a test driver.
   * It should perform no user or file I/O whatsoever.
   * Instead, it should be a static test set that convinces 
   * us that your Set class works. It should test all of the
   * special cases, all of the boundary cases, and the common
   * cases.
   */
  public static void main (String []argv) throws SetException
  {
    /*
     * Your code here
     */
  }
}