With apologies for the length of the thing, here is the assignment. As you'll see, it only talks *around* the things that need to be done, leaving it as a puzzle of sorts to figure out what precisely is to be done. I'm constrained to using the classes posted above. The SList and DList have insertFront() and insertBack() methods, but no more. My guess is that the Collections.sort() method, which is method made possible by implementing Comparable, is the means to sort the resulting Set object as items are added to it, but that must be done as the items are added.
And, yes, there's the whole issue of non-duplicating items, but I'll cross that bridge once I've found the solution to the first and fundamental problem to this exercise.
Here's the assignment text--let me know if you have an "aha!" moment while reading it; that's not happening to me as I re-read it:
Your main assignment is to implement a Set ADT in Set.java. Your Set class
must use a List to store the elements of the set. Your Sets should behave like
mathematical sets, which means they should not contain duplicate items. To
make set union and intersection operations run quickly, your Sets will contain
only Comparable elements, and you will keep them sorted in order from least to
greatest element. (You will want to review the Comparable interface on the
Java API Web page.)
You will need to decide on fields and implement the following methods.
public Set() // Constructs an empty Set.
public int cardinality() // Number of elements in this Set.
public void insert(Comparable c) // Insert c into this Set.
public void union(Set s) // Assign this = (this union s).
public void intersect(Set s) // Assign this = (this intersect s).
public String toString() // Express this Set as a String.
Unlike in previous assignments, each method comes with prescribed time bounds
that you must meet when your Set uses DLists (but not when it uses SLists).
For example, union() and intersect() must run in time proportional to
this.cardinality() + s.cardinality(). This means you don’t have time to make a
pass through "this" list for every element of s; that would take time
proportional to this.cardinality() * s.cardinality(). You must take advantage
of the fact that Sets are sorted to achieve this time bound. This time bound
is one reason why Sets may not store duplicate items in their Lists.
On the other hand, insert() need not run in constant time. Since each Set uses
a sorted representation, insert() may need time proportional to the cardinality
of the Set to find the right place to insert a new element, and to ensure that
the new element doesn’t duplicate an old one.
Another constraint is that union() and intersect() may NOT change the Set s.
Furthermore, intersect() may not create any new ListNodes (it only needs to
remove ListNodes from "this" List), and union() should reuse all the ListNodes
in the Set "this", creating new nodes only for elements of s that "this" List
lacks. We will deduct points for failing to meet the time bounds or failing to
obey these constraints.
Be sure to declare variables of static type List and ListNode in Set.java, not
variables of type DList, DListNode, SList, or SListNode. Set.java should be
able to switch between using DLists and using SLists by changing one
constructor call in the Set() constructor. (In fact, you can use SList to help
you debug Set if you have trouble getting DList working. But be sure to use a
DList in your final submission unless you can’t get it working.)
Do not modify List.java, ListNode.java, SList.java, or SListNode.java. Do not
modify the prototypes in Set.Java, DList.java, or DListNode.java.