Assignment 3 Help

The Provided Files

I have given you the following java files. (Get them here.)

SortedList.java

This is the SortedList interface. You need to implement this interface and write the necessary methods. You should not change this file!

SortedListException.java

An exception thrown by SortedLists. You do not need to add anything more to this file (unless you want to).

Node.java

A pretty standard Node class, these Nodes will hold any kind of Object. You can use instances of this Node class to build your linked list. Again, no changes needed.
(I actually borrowed it from a textbook's code. Note that I did not document it (that's the author's job). But I did add a comment on where I got it from, so I don't get in trouble for plagiarism. The same rule goes for you in this class: you don't to document code you didn't write, but it should at least be clear where that code came from.)

OrderedList.java

This is an example of a starting implementation of SortedList. You can use this file as the beginning of your implementation if you want to. Feel free to delete the internal comments as you write the methods. It might help to start with a file that compiles, since you need all the methods of an implemented interface "written" before the implementation will compile.

SortedListTest.java

When you are done, this file will test your SortedList implementation. Change the class name near the top (it's commented) if you called your implementation something other than OrderedList.

(The a3files.zip contains all the .java files and this page, for easy downloading.)

There's More Than One Way to Do It

I chose to implement SortedList in a file called OrderedList.java. I will then call my applet file OrderedListApplet.java, and there I will do all my applet GUI stuff. OrderedListApplet will have an instance of OrderedList that I will use to store my sorted numbers.

You do not have to use these same names! You can call your two files whatever you want to; I don't care. You can even implement SortedList and your applet in the same file (though I really don't recommend it).

Comparable

SortedList takes Comparable objects. SortedList does not implement Comparable itself; it just sorts Comparable objects.

When an object is Comparable, it means that it has implemented the Comparable interface. And that means it has the method compareTo. (You can, as always, learn more of the technical details in the Java2 API.) All that compareTo does is compare two objects of the same class and tell you which object should come before the other in a sorted list. If you compare two Strings, you can tell which comes before the other alphabetically. If you compare two Integers, it will tell you which number is less than the other.

More specifically, when you call compareTo, it compares the object it was invoked on to the object given as an argument, and returns an int telling you which should come first in a list. Example:

obj1.compareTo(obj2);

If obj1 comes before obj2 in a list, compareTo will return a number < 0 (probably -1). If obj2 comes first, it turns a number > 0 (probably +1). If the two would share the same position, compareTo returns 0.

So, if you were comparing ints stored in Nodes, you might have the following code to iterate along the linked list, looking for where to insert a new item:

while (curr != null && curr.getItem() <= item){
  curr = curr.getNext();
}


Instead, you could do the same thing with this code:

while (curr != null &&
      ((Comparable) curr.getItem()).compareTo(item) <= 0){
  curr = curr.getNext();
}


This gets the Item out of curr, casts it to a Comparable object (see below for why you need to do this), and then compares it to the given item.

So why bother with this extra complexity? Because now your SortedList will sort and hold any kind of object that can be compared to another. It will still take ints if you wrap them an Integer object. (So to store the int 3 in the list, you can just write list.add(new Integer(3));) But now, without changing anything in SortedList, it will also sort many other kinds of Comparable objects: Dates, Floats, Strings, Characters, etc. You could make your Employees from assignment 1 implement Comparable by simply writing a compareTo method detailing when one Employee should come before another (perhaps based on their name or ID number). Then you could store and sort Employees without rewriting SortedList.

(Footnote: obj1.compareTo(obj2) == 0 does not necessarily mean obj1.equals(obj2), though it is usually true. As with the Employee example, if they both have the same ID or name, they might be "obj1.compareTo(obj2) == 0". But they're probably only "obj1.equals(obj2)" if every field--ID, name, payPerHour, hoursWorked--are the same. It really depends on how the equals and compareTo methods for those classes were written.)

Nodes

Whenever you get an item out of a Node (as with curr.getItem()), you get an Object back. This is because Node's getItem() method returns an Object. You will have to cast this back to Comparable before you can call compareTo on it:

Comparable item = (Comparable) curr.getItem();

This is just like Vectors. Vectors and Nodes will both store any kind of object, but you need to cast the Objects back to their specific class when you get them out. (You could change the Node to work only with Comparable objects, but that means you could not use those same Nodes for an unsorted linked list that stores Objects. So it's better to just cast a few times and have reusable code on many levels.)

Question?

Is something here unclear? Email me or Blanca.

FAQ

What happens when you compare two Comparable objects of different classes, such as an Integer and a String?

You get a runtime exception--specifically, a ClassCastException. This is because compareTo takes an Object. So, when you implement the compareTo method, the first thing you have to do is cast the given Object to an object of whatever class you are writing. If it fails that cast, an exception gets thrown. It's a runtime exception because normally you don't encounter it--when you use a list, just as when you use a Vector, you know what type of objects you are loading it with, and you only load it with one type of object at time.

My file won't compile/run, and the error messages are all about Comparable!

Comparable was added in Java 2. Be sure to compile with javac2 and run your program with java2. Also, most (older) browsers are still using Java 1.1 runtime environments. So you'll need to use appletviewer or a newer browser or a browser with a recent Java Runtime Environment plug-in for your applet to work.

Do I have to implement all the methods of SortedList, even though I don't need them all for my applet?

Yes. You can't partially implement an interface, since it would leave you with an incomplete ADT. (Also, you need to be able to pass SortedListTest.java's tests for your implementation of SortedList.)

SortedList has a remove and get method that each take a position. Does this position start at 0 or 1?

As stated in the documentation for get (on when an exception is thrown), positions start at 1. If you have 3 elements in a list, their positions are 1, 2, and 3. (This is different from array indexes, which would be 0, 1, and 2 for a list of 3 items.)

When I add a really long number to my applet, I get an error!

This is probably because you are using:

int num = Integer.parseInt(userEnteredString).

ints can only hold numbers up to 2^31 (about 2.1 billion). You can use longs instead, which are good up to 2^63. Better yet, when you catch the NumberFormatException for when the user enters something that is not a number, also mention that the number may be too long:

Error: Either you did not enter a number or your number is too large.

I disabled my list display TextArea so that the user can't try to change the contents of the list. But now the area won't scroll when the list gets long!

Instead of:

listDisplay.setEnabled(false);

use:

listDisplay.setEditable(false);

This will allow the area to still scoll, but the user won't be able to change the contents.

Can I write extra methods in OrderedList?

Yes, you can add extra methods that aren't declared in SortedList. For example, I wrote a toString() method in OrderedList that I could use to print the list (in my applet or elsewhere). I have added this method to the OrderedList file I gave you. You do not have to use it, but you can if you want to.

What's up with SortedListTest?

The checks are only looking to see whether the methods ran without generating an exception. Therefore, you can get a "passed" even though your method did not actually work. You need to make sure your list is actually changing. The values in [brackets] are what your list should be returning.

Also, there was a problem with first test of get. It said it was testing it, but didn't actually call the get method! You can download the fixed version now (19 Oct 2003).

Can I get a little help here? For instance, how do I use this add(item) method?

You use the add method in your applet to add items to the list like this:

OrderedList list = new OrderedList();
...
list.add(new Integer(num));

In OrderedList.java is where you implement the add method. To do so, you need to check three cases:
1) if the list is empty, the given item goes in a new Node at the head position
2) else if the item comes before head, add it there and update head to point to the new added Node.
3) else move cursor and precursor pointers along the list with a while loop until they point to either side of where the new item needs to go; then add the item there (after the while loop).

Remove works much the same way--find where the item is in the list and remove it, or else throw an exception because the item is not in the list to be removed.

In get, you are not looking for a certain item in the list. Instead, you are counting along the elements of the list until you find the stated position and then returning whatever item is found there.

Remove by position works just like get, but you are removing the item from the list rather than just returning it. (Note that, because the list is sorted, list.remove(1) will remove the first/smallest item in the list, and list.remove(list.size()) will return the last/largest item in the list.)