Implementing a Set:
WITH LINKS
The LinkedSet Class
//********************************************************************
// LinkedSet.java Authors: Lewis/Chase
//
// Represents a linked
implementation of a set.
//********************************************************************
package jss2;
import jss2.exceptions.*;
import java.util.*;
public class LinkedSet<T>
implements SetADT<T>, Iterable<T>
{
private static
Random rand = new Random();
private int count; // the
current number of elements in the set
private LinearNode<T> contents;
/******************************************************************
Creates an empty set.
******************************************************************/
public LinkedSet()
{
count = 0;
contents = null;
}
/******************************************************************
Adds the specified element to this set if
it is not already
present. Because
the elements of a set are not in any order, we can simply add the new
element to the front of the list.
******************************************************************/
public void add (T
element)
{
if
(!(contains(element)))
{
LinearNode<T>
node = new LinearNode<T> (element);
node.setNext(contents); //
the first time, contents is set to null
contents = node;
count++;
}
}
/******************************************************************
Adds the contents of the
parameter to this set.
******************************************************************/
public void addAll (SetADT<T> set)
{
}
/******************************************************************
Removes and returns a random element from
this set. Throws
an EmptySetException if the set contains no elements.
******************************************************************/
public T removeRandom() throws EmptySetException
{
LinearNode<T>
previous, current;
T result = null;
if (isEmpty())
throw new EmptySetException();
int
choice = rand.nextInt(count) + 1;
if (choice == 1)
{
result = contents.getElement();
contents = contents.getNext();
}
else
{
previous =
contents;
for (int skip=2; skip < choice; skip++)
previous = previous.getNext();
current = previous.getNext();
result = current.getElement();
previous.setNext(current.getNext());
}
count--;
return result;
}
/******************************************************************
Removes and returns the specified element
from this set.
Throws an EmptySetException
if the set is empty and a
NoSuchElemetnException
if the target is not in the set.
******************************************************************/
public T remove (T
target) throws EmptySetException,
NoSuchElementException
{
boolean
found = false;
LinearNode<T>
previous, current;
T result = null;
if (isEmpty())
throw new EmptySetException();
if (contents.getElement().equals(target))
{
result = contents.getElement();
contents = contents.getNext();
}
else
{
previous =
contents;
current = contents.getNext();
for (int look=0; look < count && !found; look++)
if (current.getElement().equals(target))
found =
true;
else
{
previous =
current;
current = current.getNext();
}
if (!found)
throw new NoSuchElementException();
result = current.getElement();
previous.setNext(current.getNext());
}
count--;
return result;
}
/******************************************************************
Returns a new set that is the union of this
set and the
parameter.
******************************************************************/
public SetADT<T> union (SetADT<T>
set)
{
}
/******************************************************************
Returns true if this set contains the
specified target
element.
******************************************************************/
public boolean contains (T target)
{
}
/******************************************************************
Returns true if this set contains exactly
the same elements
as the parameter.
******************************************************************/
public boolean equals (SetADT<T>
set)
{
}
/******************************************************************
Returns true if this set is empty and false
otherwise.
******************************************************************/
public boolean isEmpty()
{
}
/******************************************************************
Returns the number of
elements currently in this set.
******************************************************************/
public int size()
{
}
/******************************************************************
Returns an iterator for the elements currently in this set.
******************************************************************/
public Iterator<T> iterator()
{
return new LinkedIterator<T> (contents, count);
}
/******************************************************************
Returns a string
representation of this set.
******************************************************************/
public String toString()
{
}
}
//********************************************************************
// SetADT.java Authors:
Lewis/Chase
//
// Defines the
interface to a set collection.
//********************************************************************
package jss2;
import java.util.Iterator;
public interface SetADT<T>
{
/** Adds one element
to this set, ignoring duplicates. */
public void add (T
element);
/** Removes and returns a random element from
this set. */
public T removeRandom ();
/** Removes and returns the specified element
from this set. */
public T remove (T
element);
/** Returns the union of this set and the
parameter */
public SetADT<T> union (SetADT<T>
set);
/** Returns true if this set contains the
parameter */
public boolean contains (T target);
/** Returns true if this set and the
parameter contain exactly
the same elements */
public boolean equals (SetADT<T>
set);
/** Returns true if this set contains no
elements */
public boolean isEmpty();
/** Returns the number of elements in this
set */
public int size();
/** Returns an iterator
for the elements in this set */
public Iterator<T> iterator();
/** Returns a string representation of
this set */
public String toString();
}
//************************************************************
// LinearNode.java Authors: Lewis/Chase
// This
class is not tied to the implementation of a set collection
// Represents a node
in a linked list.
//************************************************************
package jss2;
public class LinearNode<T>
{
private LinearNode<T> next;
private T element;
/**********************************************************
Creates an empty node.
**********************************************************/
public LinearNode()
{
next = null;
element = null;
}
/**********************************************************
Creates a node storing
the specified element.
**********************************************************/
public LinearNode (T elem)
{
next = null;
element = elem;
}
/**********************************************************
Returns the node that
follows this one.
**********************************************************/
public LinearNode<T> getNext()
{
return next;
}
/**********************************************************
Sets the node that
follows this one.
**********************************************************/
public void setNext (LinearNode<T>
node)
{
next = node;
}
/**********************************************************
Returns the element stored in this node.
**********************************************************/
public T getElement()
{
return element;
}
/**********************************************************
Sets the element stored in this node.
**********************************************************/
public void setElement (T elem)
{
element = elem;
}
}
//****************************************************************
// LinkedIterator.java Authors: Lewis/Chase
//
// Represents an iterator for a linked list of linear nodes.
//****************************************************************
package jss2;
import jss2.exceptions.*;
import java.util.*;
public class LinkedIterator<T>
implements Iterator<T>
{
private int count; // the
number of elements in the collection
private LinearNode<T> current; // the current position
/*************************************************************
Sets up this iterator using the specified items.
*************************************************************/
public LinkedIterator (LinearNode<T>
collection, int size)
{
current =
collection;
count = size;
}
/*************************************************************
Returns true if this iterator
has at least one more element
to deliver in
the iteration.
*************************************************************/
public boolean hasNext()
{
return
(current!= null);
}
/*************************************************************
Returns the next
element in this iteration. Throws a
NoSuchElementException
if there are no more elements in
the iteration.
*************************************************************/
public T next()
throws NoSuchElementException
{
if (! hasNext())
throw new NoSuchElementException();
T result = current.getElement();
current = current.getNext();
return result;
}
/*************************************************************
The remove operation is not supported.
*************************************************************/
public void
remove() throws UnsupportedOperationException
{
throw new UnsupportedOperationException();
}
}