15-121 SPRING 2010 [CORTINA]

LAB 3

In this lab, you will build a class to implement a special array list that stores its values in increasing order. First, you will do this using the Java ArrayList class. Then you will do this using a class that implements an array list directly using an array.

EXERCISES

Download the OrderedArrayList.zip project file. This project contains a CalendarDate class that models a calendar date with a month, day and year (e.g. 7/4/1776). A CalendarDate implements the Comparable interface which requires it to have a compareTo method.

Using the compareTo method: If we have two objects a and b that are Comparable, then the method call a.compareTo(b) returns a positive integer if a is "greater" than b, a negative integer if a is "less" than b, or 0 if they are the same. For dates, the comparison is based on chronological ordering.
Example: If a is the date 12/4/1967 and b is the date 6/29/1951, the expression a.compareTo(b) returns a positve integer since a comes after b chronologically. (That is, a is "greater" than b in time.)

Read through the compareTo method in the CalendarDate class and explain how it works to your lab partner.
Examine the Problem1Tester class. This class contains a main method that creates an ArrayList of CalendarDate objects. The goal is to add the dates so that the list is always sorted in chronological order after each insert. Complete the insert method to satisfy this goal.
HINT: Since the list should be sorted as you insert the next date, search for the correct insert point and then add the date there using the add method of the ArrayList class.
The OrderedArrayList class models an array list that always keeps its elements in sorted order without duplicates. The ordered array list is implemented using an array such that the entries in the list are stored in the array in increasing order in positions 0 to numData-1. Note that the class is defined such that the entries in the ordered array list must implement the Comparable interface so we can compare them using the compareTo method.
Complete the add method that inserts the new entry into the correct place in the array so that the entries in the array are stored in increasing order. If the new entry is inserted into the array, return true. If the new entry is already in the array, do not change the array and return false. The user of this list doesn't have to search for the correct insert point to add the entry; this method will do the work.
Test your code with the supplied testers (CalendarDateTester and StringTester). Your method should work for calendar dates and strings and for any other Comparable objects. (Why? Look at the OrderedArrayList class and see how its generic type is defined.)

HANDIN

If you worked with another student, put both of your names in a comment at the beginning of your program. At the end of lab, create a zip file of your program and submit it to the handin server http://handin.intro.cs.cmu.edu/v1. (If you worked together, you only have to submit one program.)

FUTURE WORK: FUN STUFF FOR LATER

Modify the constructor for the CalendarDate class so that if the parameters represent an invalid date, the constructor outputs an appropriate error message and does not create an instance of the class.
Try to create an ordered array list of entries that are not Comparable. What happens?
Create another version of the OrderedArrayList that has an array of Comparable objects without using generics. What else in your program has to be changed to adapt to this modification?