Computer Science 15-100 (Sections T & U), Fall 2007
Homework 8
Due: Fri 16-Nov-2007 at 8:30am (email) and in recitation (physical copies)
Exercise #1: IntList
In class, we discussed the very useful ArrayList class. Here, you will write your own version of a very similar class: IntList. This class is much like an ArrayList, only it is restricted to holding int values. As with ArrayList, the class constructs an internal array (initially of size 1, unless otherwise specified) and then resizes that internal array as needed. This makes it very easy for the user of the class to read variable-sized data sets.
As a matter of vocabulary: an IntList has both a size and a capacity. The size is the number of elements in the array that are currently "in use". The capacity is the total length of the internal array, including the unused elements.
The following code includes a fairly complete "check" method written for you. Your task is to write all the methods in IntList that are required to make the check code work properly. Of course, your methods must work in general, as our robot grader will include other checks besides these for all the required methods.
Your required methods must be public, but your instance variables must be private. Also, feel free to add as many other private helper methods as you require.
This class behaves almost identically to the ArrayList class, so if you have questions regarding how a certain method should work, a good first step is to read the online description of ArrayList. Note that this description is from Java 1.4.2, rather than 1.5 or 1.6, so that it does not use generics, and so is easier to read.
Hint: comment out all the check code, then bit-by-bit add some and make it work correctly before adding more check code.
Another hint: if a check fails, carefully read the stack trace -- it will tell you (if you look closely) the line of your code where the failure occurred.
Here is the code to start with. Don't be daunted by its size -- the check code is actually longer than the solution it is checking!
class IntList {
// call this from your main method!
public static void check() {
System.out.print("\nCreate an IntList: ");
IntList ints = new IntList();
check(ints.getCapacity() == 1);
check(ints.size() == 0);
check(ints.isEmpty() == true);
check(ints.toString().equals("IntList[]"));
System.out.print("\nAdd an element: ");
ints.add(5);
check(ints.getCapacity() == 1);
check(ints.size() == 1);
check(ints.isEmpty() == false);
check(ints.toString().equals("IntList[5]"));
System.out.print("\nAdd another element: ");
ints.add(3);
check(ints.getCapacity() == 2);
check(ints.size() == 2);
check(ints.toString().equals("IntList[5,3]"));
System.out.print("\nAdd a third element: ");
ints.add(4);
check(ints.getCapacity() == 4);
check(ints.size() == 3);
check(ints.toString().equals("IntList[5,3,4]"));
System.out.print("\nAdd an array of elements: ");
int[] a = { 1, 6 };
ints.addAll(a);
check(ints.getCapacity() == 8);
check(ints.size() == 5);
check(ints.toString().equals("IntList[5,3,4,1,6]"));
System.out.print("\nAdd a variable # of elements: ");
ints.add(8,2,9,7); // use variable-length args!
check(ints.getCapacity() == 16);
check(ints.size() == 9);
check(ints.toString().equals("IntList[5,3,4,1,6,8,2,9,7]"));
System.out.print("\nGet and set values: ");
check(ints.get(0) == 5);
check(ints.get(1) == 3);
ints.set(0,3);
ints.set(1,5);
check(ints.get(0) == 3);
check(ints.get(1) == 5);
check(ints.toString().equals("IntList[3,5,4,1,6,8,2,9,7]"));
System.out.print("\nContains, indexOf, and lastIndexOf: ");
ints.set(2,3);
ints.set(3,3);
check(ints.toString().equals("IntList[3,5,3,3,6,8,2,9,7]"));
check(ints.contains(3) == true);
check(ints.contains(0) == false);
check(ints.indexOf(3) == 0);
check(ints.indexOf(5) == 1);
check(ints.indexOf(0) == -1);
check(ints.lastIndexOf(3) == 3);
check(ints.lastIndexOf(5) == 1);
check(ints.lastIndexOf(0) == -1);
System.out.print("\nRemove: ");
ints.remove(0);
check(ints.getCapacity() == 16);
check(ints.size() == 8);
check(ints.toString().equals("IntList[5,3,3,6,8,2,9,7]"));
check(ints.contains(7) == true);
ints.remove(ints.size()-1);
check(ints.contains(7) == false);
check(ints.getCapacity() == 16);
check(ints.size() == 7);
check(ints.toString().equals("IntList[5,3,3,6,8,2,9]"));
check(ints.contains(6) == true);
ints.remove(3);
check(ints.contains(6) == false);
check(ints.getCapacity() == 16);
check(ints.size() == 6);
check(ints.toString().equals("IntList[5,3,3,8,2,9]"));
System.out.print("\nClear: ");
check(ints.contains(3) == true);
ints.clear();
check(ints.contains(3) == false);
check(ints.getCapacity() == 16);
check(ints.size() == 0);
check(ints.isEmpty() == true);
check(ints.toString().equals("IntList[]"));
System.out.print("\nSpecify Initial Capacity: ");
ints = new IntList(3); // 3 is the initial capacity
check(ints.getCapacity() == 3);
check(ints.size() == 0);
check(ints.isEmpty() == true);
check(ints.toString().equals("IntList[]"));
ints.add(5,4,3,2);
check(ints.getCapacity() == 6);
check(ints.size() == 4);
check(ints.isEmpty() == false);
check(ints.toString().equals("IntList[5,4,3,2]"));
System.out.print("\nEnsure Capacity: ");
check(ints.getCapacity() == 6);
check(ints.size() == 4);
check(ints.toString().equals("IntList[5,4,3,2]"));
ints.ensureCapacity(5); // capacity must be at least 5
check(ints.getCapacity() == 6);
check(ints.size() == 4);
check(ints.toString().equals("IntList[5,4,3,2]"));
ints.ensureCapacity(9); // capacity must be at least 9
check(ints.getCapacity() == 9);
check(ints.size() == 4);
check(ints.toString().equals("IntList[5,4,3,2]"));
System.out.print("\nTrim to size: ");
check(ints.getCapacity() == 9);
check(ints.size() == 4);
check(ints.toString().equals("IntList[5,4,3,2]"));
ints.trimToSize();
check(ints.getCapacity() == 4);
check(ints.size() == 4);
check(ints.toString().equals("IntList[5,4,3,2]"));
ints.clear();
check(ints.getCapacity() == 4);
check(ints.size() == 0);
check(ints.toString().equals("IntList[]"));
ints.trimToSize();
check(ints.getCapacity() == 0);
check(ints.size() == 0);
check(ints.toString().equals("IntList[]"));
System.out.print("\nSpecify Initial Array: ");
int[] b = { 2, 4, 6, 8 };
ints = new IntList(b);
check(ints.getCapacity() == 6); // make this 1.5x initial array's size
check(ints.size() == 4);
check(ints.toString().equals("IntList[2,4,6,8]"));
ints.set(0,1);
check(ints.toString().equals("IntList[1,4,6,8]"));
check(b[0] == 2); // do not change b!
System.out.print("\nSort: ");
int[] c = { 3, 2, 5, 8, 1};
ints = new IntList(c);
check(ints.toString().equals("IntList[3,2,5,8,1]"));
ints.sort();
check(ints.toString().equals("IntList[1,2,3,5,8]"));
ints.clear();
ints.sort();
check(ints.toString().equals("IntList[]"));
System.out.println("\nPASSED ALL CHECKS!");
}
public static void check(boolean b) {
if (!b) throw new RuntimeException("Failed check!");
System.out.print("ok.");
}
/////////////////// ADD YOUR CODE HERE!!!!! /////////////////
}
Exercise #2: Comparable (A Natural Ordering for IntLists)
Here, we extend our IntList implementation so that we can sort a collection
of IntLists using Java's built-in sorting. Say we have an ArrayList (or an
array, for that matter) of IntLists. How might we wish to sort this
ArrayList? That is, how do we compare two IntLists to decide which one
should be sorted before the other one? Probably the most natural way would
be analogous to how we sort strings (that is, how we sort words in the
dictionary). For words, we sort basically like this:
1. Find the first character where two words differ, and the word with the
smaller character there should go before the other word.
2. If two words do not differ anywhere, shorter words ("prefixes") go
before longer words.
3. For words of the same length and all the same elements, it does not
matter -- they are "equal".
We can edit this description to fit IntLists simply by changing "word" to
"IntList" and "character" to "int", as such:
1. Find the first int where two IntLists differ, and the IntList with the
smaller int there should go before the other IntList.
2. If two IntLists do not differ anywhere, shorter IntLists ("prefixes")
go before longer IntLists.
3. For IntLists of the same length and all the same elements, it does not
matter -- they are "equal".
We will call this the "natural ordering" of IntLists. Now, how do we write
this in Java? To make our IntList sortable, we must implement the
Comparable interface, as we discussed in class. And to do that, we must:
1. Implement this method in IntList:
public int compareTo(Object obj)
As shown in class, on the first line of this method, we usually cast "obj" to an
instance of our class (IntList here), and it is convenient to call the instance
"that", as such:
public int compareTo(Object obj) {
IntList that = (IntList) obj;
// your code here...
}
The rest of this method compares "this" and "that" using the "natural ordering"
algorithm we just described above. The method should return a negative
number (any negative number) if "this < that". It should return a
positive number (any positive number) if "this > that". And it
should return 0 if "this == that".
2. Let Java know your class implements Comparable
It's not enough to implement the "compareTo" method -- you must also declare
that you did this in order to implement the Comparable interface (otherwise, it
might be a coincidence that you happened to name a method "compareTo" when it
has no actual relation to the "compareTo" method described in the Comparable
interface). To do this, you change your class declaration from:
class IntList {
to:
class IntList implements Comparable {
Now we can use the class as a Comparable!
3. Turn off the compiler warnings
As we saw in class, now that Java uses generics (which you are not expected to
know in much detail), the compiler often complains when you use methods that do
not use generics. The "compareTo" method is one such case. The
easiest way to deal with this is simply to turn off these warnings. And
the easiest way to do that is to precede your class with the so-called compiler
annotation as such:
@SuppressWarnings("unchecked")
class IntList implements Comparable {
Note that this only turns off warnings for that class. If more than
one class has such warnings, each must be preceded by a SuppressWarnings
annotation.
4. Import the appropriate classes
We do not have to import Comparable, because that is in the java.lang package,
which is imported by default. However, we will be using ArrayLists and the
sort method from the Collections class, so we need to import these two classes.
To do this, place these import statements at the top of your file (the
only place you may place import statements!):
import java.util.ArrayList;
import java.util.Collections;
5. Use the following check code
Use this check code to test that your IntLists indeed have a natural ordering.
public static void checkComparable() {
System.out.println("checkComparable:");
System.out.print("\nCreate several IntLists: ");
IntList i1 = new IntList();
IntList i2 = new IntList();
IntList i3 = new IntList();
IntList i4 = new IntList();
i1.add(1,3);
i2.add(1,2);
i3.add(1,2,4);
i4.add(1,3);
check(i1.toString().equals("IntList[1,3]"));
check(i2.toString().equals("IntList[1,2]"));
check(i3.toString().equals("IntList[1,2,4]"));
check(i4.toString().equals("IntList[1,3]"));
System.out.print("\nCompareTo: ");
check(i1.compareTo(i2) > 0);
check(i1.compareTo(i3) > 0);
check(i1.compareTo(i4) == 0);
check(i2.compareTo(i1) < 0);
check(i2.compareTo(i3) < 0);
check(i2.compareTo(i4) < 0);
check(i3.compareTo(i1) < 0);
check(i3.compareTo(i2) > 0);
check(i3.compareTo(i4) < 0);
System.out.print("\nCreate an ArrayList of the IntLists: ");
ArrayList al = new ArrayList();
al.add(i1);
al.add(i2);
al.add(i3);
check(al.toString().equals("[IntList[1,3], IntList[1,2], IntList[1,2,4]]"));
System.out.print("\nSort the ArrayList by IntList's natural Comparable ordering: ");
Collections.sort(al);
check(al.toString().equals("[IntList[1,2], IntList[1,2,4], IntList[1,3]]"));
System.out.println("\nPASSED ALL CHECKS!");
}
Exercise #3: Comparator (Unnatural Orderings for IntLists)
Now that we can use Collections.sort to sort an ArrayList of IntLists by their natural ordering, an obvious question arises: can we use other orderings (which we might call unnatural orderings, though that term is not commonly used). Yes, we can, and in fact we shall!
When Collections.sort goes about sorting an ArrayList, it eventually must compare two elements in that list. To do this, it calls the compareTo method of one of those elements, providing the other element as the argument. This is why our previous solution worked: in Exercise #2, we implemented a compareTo method for IntLists, and this allowed ArrayLists of IntLists to be sorted.
If we are to use a different ordering, we must tell Collections.sort not to use the default compareTo method on the objects in the list. Instead, we must provide a second argument to the sort method -- a so-called Comparator (notice that is Comparator, not Comparable). A Comparator takes two objects and compares them in a manner not unlike how Comparable works. However, Comparable takes only one object (the other being "this"), and a Comparator takes two objects. As a minor difference, Comparable's method is named "compareTo", whereas Comparator's method is named "compare".
Let's see this in action. Let's create an ArrayList of Strings. Then we'll sort the Strings using their natural order. Finally, we'll sort the Strings by comparing each word as though it were in reverse -- so if are comparing, say, "bug" with "zag", we would proceed as if we were comparing "gub" with "gaz", thus finding that "bug" > "zag" . Here is the code that demonstrates this:
// This is NOT the code for Exercise #3
// This simply demonstrates how to use a Comparator to provide a custom (unnatural) ordering.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
@SuppressWarnings("unchecked")
class ComparatorDemo {
public static void main(String[] args) {
ArrayList al = new ArrayList();
al.add("ab");
al.add("ba");
al.add("ac");
al.add("ca");
al.add("bc");
al.add("cb");
al.add("cba");
al.add("abc");
System.out.println("Original:");
System.out.println(" " + al);
System.out.println("Natural sorted order:");
Collections.sort(al);
System.out.println(" " + al);
System.out.println("Sorted comparing words in reverse:");
MyStringComparator comp = new MyStringComparator();
Collections.sort(al,comp);
System.out.println(" " + al);
}
}
class MyStringComparator implements Comparator {
public int compare(Object obj1, Object obj2) {
String s1 = (String)obj1;
String s2 = (String)obj2;
return reverse(s1).compareTo(reverse(s2));
}
public static String reverse(String s) {
String result = "";
for (int i=0; i<s.length(); i++)
result = s.charAt(i) + result;
return result;
}
}
Compile and run this code. Play with it a bit, change it this way and
that. Make sure you understand it!
Now we are ready to sort our ArrayList of IntLists in interesting ways.
But how? One interesting order would be to sort by the sum of the
elements in the list. Another order would be to simply use the
reverse of the natural order. Here, you will create a single
Comparator that can perform either of these sorts. Proceed in these steps:
1. Create a new Comparator class (similar to MyStringComparator from the
example above, only here it will compare IntLists)
class
IntListComparator implements Comparator {
2. Implement this method in your Comparator::
public int compare(Object obj1, Object obj2)
As with compareTo, we first cast the arguments to be instances of a specific
class (IntList here). As for naming, we cannot use "this" as a name,
because it is a reserved keyword in Java. So we'll go with "list2"
and "list2", as such:
public int compare(Object obj1, Object obj2) {
IntList list1 = (IntList) obj1;
IntList list2 = (IntList) obj2;
// your code here...
}
The rest of this method compares "list1" and "list2" using the any
ordering you so choose. The method should return a negative number (any
negative number) if "list1 < list2". It should return a positive number (any
positive number) if "list1 > list2". And it should return 0 if "list2 ==
list2".
3. Import the appropriate class
Now we are using the Comparator class, so we need to import it (in addition to
the classes you have already imported):
import java.util.Comparator;
4. Use the following check code
Use this check code to test that your IntListComparator indeed can sort IntLists
by their sums and by the reverse of their natural ordering:
public static void checkComparator() {
System.out.println("checkComparator:");
System.out.print("\nCreate several IntLists: ");
IntList i1 = new IntList();
IntList i2 = new IntList();
IntList i3 = new IntList();
IntList i4 = new IntList();
i1.add(1,3);
i2.add(1,2);
i3.add(1,2,4);
i4.add(1,3);
System.out.print("\nSum: ");
check(i1.sum() == 4); // sum of the elements in the IntList
check(i2.sum() == 3);
check(i3.sum() == 7);
check(i4.sum() == 4);
System.out.print("\nCreate an ArrayList of the IntLists: ");
ArrayList al = new ArrayList();
al.add(i1);
al.add(i2);
al.add(i3);
check(al.toString().equals("[IntList[1,3], IntList[1,2], IntList[1,2,4]]"));
System.out.print("\nSort the ArrayList by their sums using a Comparator: ");
IntListComparator comp = new IntListComparator();
comp.sortBySum();
Collections.sort(al,comp);
check(al.toString().equals("[IntList[1,2], IntList[1,3], IntList[1,2,4]]"));
System.out.print("\nSort the ArrayList in reverse using a Comparator: ");
comp.sortInReverse();
Collections.sort(al,comp);
check(al.toString().equals("[IntList[1,3], IntList[1,2,4], IntList[1,2]]"));
System.out.println("\nPASSED ALL CHECKS!");
}
Carpe diem!