Introduction
This assignment asks you to implement a Set class using a LinkedList. We have provided a skeleton for the Set and most, but not all, of the LinkedList's implementation. 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
- Remove - remove an item from the set
- Intersection - return a set containing those items that are in both sets
- Union - return a set with one copy of any item that appears in either or both sets.
- Exclusive-or - return a set with one copy of any item that appears in either set, but not both sets.
This assignment is substantially longer and more complex than the prior assignment. Please start early and remember -- we're here to help.
Completing the Provided Skeletons
You should find the LinkedList very, very familiar. It is basically the same class that we implemented in class. In order to complete this assignment, you should implement the find() and remove() methods for this class. We have provided the skeletons for these methods, but no implementation.You should then use the linked list as the primary internal data structure for the Set. We have again provided a skeleton for this class. Please implement each method we have provided.
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 provided skeletons have 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.
Submission Requirements
For this assignment, you should hand in only the LinkedList.java file and the Set.java file which contain 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.You will hand in your program at:
/afs/andrew/course/15/200/handin/lab1/{userid}
The LinkedList Class ( LinkedList.java )
/*
* This is LinkedList is very similar to the one
* we defined in class. I added a toString() method
* for your convenience.
*
* You should implement the find() method.
*/
class LinkedList
{
/*
* This class defines an Exception which can be
* thrown in the case of an error involving the
* "index" reference. It is a public subclass,
* so that other classes can catch it, but have
* to explicitly recognize its scope by referring
* to it by LinkedList.IndexException
*/
public class IndexException extends Exception
{
/*
* This method creates a String representation
* of the Exception which has occurred
*/
public String toString()
{
return ("Bad index in Linked List");
}
}
/*
* This class defines one piece of the linked list.
* It contains an Object which represents the data
* stored at the current spot, and a reference to
* the next Node in the list
*/
private class Node
{
private Object data;
private Node next;
/*
* Constructor. Initializes instance variables
* to specified values
*/
public Node (Object data, Node next)
{
this.data = data;
this.next = next;
}
/*
* Constructor. Initializes data to the
* specified value, and the next reference
* to null
*/
public Node (Object data)
{
this.data = data;
this.next = null;
}
/*
* Returns the data
*/
public Object getData()
{
return data;
}
/*
* Returns reference to next node
*/
public Node getNext()
{
return next;
}
/*
* Sets the next reference to the specified value
*/
public void setNext(Node next)
{
this.next = next;
}
/*
* Sets the data to the specified value
*
* We could have chosen not to implement this
* method, and instead force users to create
* new Node objects when they want to change
* the data.
*/
public void setData(Object data)
{
this.data = data;
}
}
private Node head;
private Node tail;
private Node index;
/*
* Constructor. By default, set all the references
* to null
*/
public LinkedList()
{
head = tail = index = null;
}
public void addHead(Object data)
{
// Create new node w/data
Node newNode;
newNode = new Node(data);
// Set new node to point to the old head
newNode.setNext(head);
// Reset head of list
head = newNode;
// Special case: empty list
if (null == tail)
{
tail = head = index = newNode;
}
}
public void addTail(Object data)
{
// Create new node w/data
Node newNode = new Node(data);
// special case: Empty list
// can test either head or tail == null
if (null == head)
{
head = tail = index = newNode;
return; // all done
}
// Common case: list is not empty
tail.setNext(newNode);
tail = newNode;
}
/*
* This is pretty straight-forward. It resets the index
* to the head of the list. This is particularly important,
* because index cannot move backwards.
*/
public void resetIndex()
{
index = head;
}
/*
* This returns the datum from the node referenced by index.
* It returns null if index is null.
*/
public Object getIndexedNode()
{
// special case: null index
if (null == index)
{
return null;
}
// Common case: return indexed value
return index.getData();
}
/*
* This moves index ahead by one node. It follows the
* next reference within the linked list.
*/
public void advanceIndex()
{
// special case: null index
if (null == index)
{
return;
}
// Common case: move forward
index = index.getNext();
}
/*
* This adds a piece of data to the linked list
* after the current index. It throws an exception
* if index is currently null
*/
public void insertAfterIndex(Object data)
throws IndexException
{
// special case: null index
if (null == index)
{
throw new IndexException();
}
// Common case
Node newNode = new Node(data);
newNode.setNext(index.getNext());
index.setNext(newNode);
}
/*
* This deletes the node after the indexed node. It silently fails
* if index is null.
*/
public void deleteAfterIndex()
{
// special case 1: null index
if (null == index)
{
return;
}
// special case 2: null index.next
if (null == index.getNext())
{
return;
}
// special case 3: removing the tail
if (tail == index.getNext())
{
index.setNext(null);
tail = index;
return;
}
// common case
index.setNext(index.getNext().getNext());
return;
}
/*
* This is method converts the list to a string by
* relying on the toString() method of the data element
* within each node.
*
* This method is important, because it is called by
* System.out.println(), &c.
*/
public String toString()
{
String ret = new String();
for (Node current=head;
(null != current);
current = current.getNext())
ret += current.getData().toString() + "\n";
return ret;
}
/*
* You should implement this method. It should
* return true if the data item is found in the list and
* false otherwise. It should rely on the ".equals()"
* method of the data item's class to do the comparison
*/
public boolean find (Object find_me)
{
/*
* Your code here
*/
}
/*
* You should implement this method. It should
* remove the first instance of the specified item
* from the list. If the item is not in the list,
* it should fail silently
*/
public void remove (Object remove_me)
{
/*
* Your code here
*/
}
}
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()
{
return items.toString();
}
/*
* 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 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 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 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
*/
}
}