package ISet;
import ConsList.*; // holds classes ConsList, Cons, and Nil
/** Set models a set---a collection of objects such that each object appears
at most once in the collection. */
public class Set
{ private ConsList elements; // remembers the address of a ConsList
// that holds the elements of the set.
// Invariant: all elements are distinct.
/** Constructor Set constructs a new, empty set */
public Set()
{ elements = new Nil(); }
/** Constructor Set constructs a set from an already constructed
* ConsList.
* @param list - the ConsList of elements. If the list contains
* duplicate elements, then an exception is thrown!
* @throw RuntimeException if list has duplicate elements */
public Set(ConsList list)
{ if ( thereAreDuplicatesIn(list) )
{ throw new RuntimeException("Set constructor error: duplicates!"); }
else { elements = list; }
}
/** thereAreDuplicatesIn systematically decomposes list to see
* if its head elements are duplicated later in its sublists. */
private boolean thereAreDuplicatesIn(ConsList list)
{ boolean answer;
if ( list.isEmpty() )
{ answer = false; } // no duplicates in an empty list
else { Element h = (Element)(list.head());
ConsList t = list.tail();
answer = memberOf(h, t) // see if h is found in sublist t;
// memberOf is a private method; see below
|| thereAreDuplicatesIn(t); // if not, then
// check for duplicates in sublist t
}
return answer;
}
/** memberOf checks if e is found within list.
* @param e - the element to be found
* @param list - the list checked for e
* @return true, if e is found in list; return false, otherwise */
private boolean memberOf(Element e, ConsList list)
{ ... } // please write this
/** insert inserts v into the set, if it is not already present.
* @param v - the element to insert into this set object. */
public void insert(Element v)
{ ... }
/** delete removes v from the set, if it is present. (If it is
* not present, then no action at all is taken.)
public void delete(Element v)
{ ... } // hint: assign to elements a new ConsList you construct
// by recursively processing the existing elements list.
// Your solution will do partial sharing of the old list of
// elements by the new list.
/** member checks to see if an element is a member of this set
* @param e - the object checked
* @return true, if v is in this set; return false, otherwise */
public boolean member(Element e)
{ return memberOf(e, elements); } // see memberOf, above
/** isEmpty checks if this set is empty
* @return true, if the set is empty; return false, otherwise */
public boolean isEmpty()
{ ... }
/** getElements copies the elements in this set into an _iterator object_
* @return the iterator object that knows the elements of this set */
public Iterator getElements()
{ return new ConsListIterator(elements); // see below for the code for
// class ConsListIterator,
// which exploits safe sharing
}
/** cloneSet constructs a new set object that is an exact copy of
* this one.
* @return the cloned set object; */
public Set cloneSet()
{ return new Set(elements); // here, we exploit safe sharing
}
}
Because the clone method is renamed cloneSet, the union method in class SetOperations changes at one statement:
/** union constructs a set that is the union of its two arguments
* @param s - the first set
* @param t - the second set
* @return the set that is the union of s and t. */
public Set union(Set s, Set t)
{ Iterator s_elements = s.getElements();
Set answer = t.cloneSet(); // THE CHANGE IS HERE.
// copy s's elements into answer:
while ( !s_elements.isEmpty() )
{ answer.insert(s_elements.next()); }
return answer;
}
The complete package, ISet, is found at
http://www.cis.ksu.edu/~schmidt/300s01/Assign/ISet.
I apologize for the two errors, which arose due to my preparing the
assignment within a too-tight schedule.