Implementing Comparable, crafting compareTo with Set class

[Tom Brodhead]

I'm having to make an original "Set" ADT that employs single and doubly-linked lists, and one of the constraints is that the Set class must implement the Comparable interface.

The relevant code is in a different posting of mine: https://coderanch.com/t/530379/java/java/Null-Pointer-Exception-set-class

I can't get my head around the correct implementation of the compareTo() method, which is apparently required when Comparable is implemented on the Set class. The Set class initializes a list where data is stored; I don't understand how I'd implement a compareTo() on the list itself; it would seem that the compareTo() method would rightfully compare elements of the list *items* themselves, so I'm baffled at how to go about this.

Here is the code again:

public abstract class List {
	protected int size;
	public boolean isEmpty() {
		return size == 0;
	}
	public int length() {
		return size;
	}
	public abstract void insertFront(Object item);

	// Other methods omitted here for brevity
}


public class SList extends List {

	protected SListNode head;
	protected SListNode tail;

	protected SListNode newNode(Object item, SListNode next) {
		return new SListNode(item, this, next);
	}

	public SList() {
		head = null;
		tail = null;
		size = 0;
	}

	public void insertFront(Object item) {
		head = newNode(item, head);
		if (size == 0) {
			tail = head;
		}
		size++;
	}

                // subsequent definitions omitted for brevity...



}


public class SListNode extends ListNode {

	protected SListNode next;

	SListNode(Object i, SList l, SListNode n) {
		item = i;
		myList = l;
		next = n;
	}
	
	// subsequent definitions omitted for brevity...

}

// Inside my Main() method:
Set s = new Set();
s.insert(new Integer(5));


// The set class that it calls:
public class Set {
	
	protected static List mySet;
	protected static ListNode myNode;
	
	public Set() { 
		mySet = new SList();		
	}


	public void insert(Comparable c) {
		
		mySet.insertFront(c);
	}
}

[Joanne Neal]

Tom Brodhead wrote:I don't understand how I'd implement a compareTo() on the list itself; it would seem that the compareTo() method would rightfully compare elements of the list *items* themselves, so I'm baffled at how to go about this.

Well, it is up to whoever wrote the specification to decide exactly how the compareTo method should work, but your guess seems reasonable.

Although none of the standard Java Set implementations implement Comparable, they do override equals (which is more or less the same thing - comparing two instances) and the contract for that overridden method is

Returns true if the specified object is also a set, the two sets have the same size, and every member of the specified set is contained in this set

. So you could look at the source code for one of the standard Set implementations and see how it is done there.


Edit: having just read your other post I've realised what your actual doubt is now - when is a set greater than or less than another set. That's something you need to decide for yourself or ask whoever wrote the specification. If the two sets contain different numbers of elements then it's fairly easy, but if they contain the same number of elements then it's a bit more difficult. Personally I'd ask for some clarification of the specification.

[Campbell Ritchie]

Agree with you, Joanne, but are you not a bit over-optimistic? I am not convinced there is a "natural ordering" of Sets at all, so it seems very peculiar to me that a Set implement Comparable at all.

[Joanne Neal]

And I agree with you Campbell . When I said "I'd ask for some clarification of the specification", what I really should have said is - I don't want to discourage you but this requirement doesn't actually make much sense.

[Tom Brodhead]

Perhaps I've misstated the problem, or have misunderstood it. The spec says "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."

So the elements/nodes in each internal list of the Set should be of like type (i.e. Comparable). But if I'm implementing Comparable on the Set class itself, how would I use that to ensure that items inserted into the Set are comparable? The Set uses an internal single-linked list for storing the data (which should be switchable to a doubly-linked list just by modifying the constructor...to that end I'm instructed to declare variables List and ListNode as static type in Set, and then use the constructor to initialize them either as singly or doubly-linked lists [e.g. the SList/SListNode definition.])

So I'm very puzzled by this...it's not that I need to ensure that Set objects are Comparable one to the next, which is what the Comparable implementation would ensure, but rather that items inserted into a given Set are Comparable. But the Comparable implementation only affects the Set class itself and objects of that class. Right?

Many thanks in advance for your help,
~~Tom

[Matthew Brown]

You would only implement compareTo on the set if you wanted to be able to compare one set to another. As pointed out, it's pretty difficult to define a sensible ordering for that. But that requirement says you have to keep the contents of the set in order. That's completely different, and implementing compareTo on the set isn't necessary. All you have to do is assume that all the contents implement Comparable, and use that to keep them in order when elements are added.

If the interface isn't already defined, one way to make sure all the elements implement Comparable would be to have your methods take Comparables rather than Objects. If you can't do that, you'll have to follow the approach of TreeSet and throw exceptions whenever you add something that can't be sorted.

[Tom Brodhead]

Already the insert() method uses a Comparable as the object parameter, which surprised me because I thought we'd have to add "implements Comparable" in the Set class name to be able to use it. Eclipse does issue the warning:

Comparable is a raw type. References to generic type Comparable<T> should be parameterized

...on the line:

public void insert(Comparable c) {

But how do I ensure that the elements inserted into the Set using this method are in fact sorted? My spec says "...each Set uses a sorted representation..." and "Sets will contain only Comparable elements, and you will keep them sorted in order from least to greatest element." How would I achieve that?

~~Tom

[Matthew Brown]

You're getting the warning because Comparable is a generic type, but you're not using generics. You could genericise the whole thing:

public class Set<T extends Comparable> { ...}

but if you don't want/are required not to do that, just ignore the warnings.

What I'd expect the insert method to be doing is inserting the object into the right place in the list ("the right place" being found by using compareTo against the objects already in the list), which would guarantee it's kept in order at all times.

[Campbell Ritchie]

Surely it's

public class Set<T extends Comparable<? super T>>

[Tom Brodhead]

According to the Java specs, compareTo() returns one of 3 integers: -1, 1, 0: -1 if the item is less than the compared item, 1 if the item is greater than the compared item, and 0 if the items are equal. Apparently, you *must* write a compareTo() method in your class if you implement the Comparable interface. This is where I'm confused on fundamentals, because I'm unclear on how I should write such a method.

I'm not sure how I'd utilize the compareTo() method to ensure a sorted Set at all times...

compareTo() is used by the Collections.sort() method, which may be used on an object of the class itself, which doesn't actually help me insure that the inserted objects are in fact sorted as they go in.

I believe that the only purpose to having compareTo() is so that Collections.sort() can do its work for you. But that doesn't help me within an object of the Set class as defined here.

[Matthew Brown]

Campbell Ritchie wrote:Surely it's

public class Set<T extends Comparable<? super T>>

Sorry, yes, quite right! Didn't think it through.

[Matthew Brown]

Tom Brodhead wrote:This is where I'm confused on fundamentals, because I'm unclear on how I should write such a method.

If you're just writing the set, you don't need to write the method. It will already have been written for any object you put in the set. For instance, String already implements Comparable. What you need to do is use the method.

Tom Brodhead wrote:I'm not sure how I'd utilize the compareTo() method to ensure a sorted Set at all times...

Here's one way. In the insert() method, iterate through your list and use compareTo to compare your new item to those items already in the list. As soon as you find an existing item that should come after your new one, insert the new one just before it. Of course, you'd have to modify the list to allow insertions in the middle, not just at the front.

[Tom Brodhead]

Thanks, Matthew, although the problem is that I'm restricted to using the insertFront() method of the SList class...insert() will call it rather than implementing an original routine (this is so I can switch between a singly-linked list and doubly-linked list just be changing one line in the constructor for the Set class.) So all insertions into the SList will be at the front of the list.

My guess is that I should then be able to call the Collections.sort method on the resulting Set, but that really can only be done in the routine that instantiates a Set object...i.e. in some other Main() routine. So I'm still baffled.

~~Tom

[Matthew Brown]

I think I'm a little confused as to your requirements as well.

If you're planning to use Collections.sort, then your set needs to implement the full java.util.List interface, which is what Collections.sort acts on. Have a look at the Javadocs to see what you'd have to be able to implement. In that case, you could use it either after every addition, or just before you extract values (you could keep a flag indicating whether it had been updated since the last sort to prevent you sorting unnecessarily).

But failing that, I still think the easiest approach would be to insert values into the right place in the first place. One of the advantages of a linked list is that it's pretty straightforward to insert elements in the middle, so restricting it so you can only insert at the beginning doesn't make a lot of sense to me.

[There's also the additional factor that I'd expect a "set" to prevent duplicates, which you haven't factored in yet, but maybe it's best to wait till the sorting is sorted (sorry!) before worrying about that]

[Tom Brodhead]

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.