Array-Based Implementation of ADT SortedList Objectives To gain a better understanding of ADT by implementing the SortedList class using array. To gain a better understanding of Java exceptions. To become familiar with the Comparable interface. Description One of the most frequently performed computing tasks is the maintenance, in some specified order, of a collection of data. Such data are called sorted data, or a sorted list. The problem of maintaining sorted data requires more than simply sorting the data. Often you need to insert some new data item into its proper, sorted place. Similarly, you often need to delete some data item. The operations of the ADT SortedList is defined as follows: public boolean isEmpty(); // Determines whether a sorted list is empty. // Precondition: None. // Postcondition: Returns true if the sorted list is empty, otherwise returns false. public int size(); // Determines the length of a sorted list. // Precondition: None. // Postcondition: Returns the number of items that are currently in the sorted list. public void sortedAdd(Comparable newItem) throws ListException; // Adds an item to the sorted list. // Precondition: None. // Postcondition: The item is added to the sorted list in sorted order. public void sortedRemove(Comparable anItem) throws ListException; // Removes an item from the sorted list. // Precondition: None. // Postcondition: The item is removed from the sorted list and the sorted order maintained. public Object get(int index) throws ListException; // Retrieves a list item by position. // Precondition: index is the position of the item to be retrieved. // Postcondition: If 1 <= index <= size(), the item at position index in the sorted // list is returned. public void removeAll(); // Deletes all the items from the sorted list. // Precondition: None. // Postcondition: The sorted list is empty. public int locateIndex(Comparable anItem); // Finds an item in the sorted list. // Precondition: None. // Postcondition: If the item is in the sorted list, its index position in the sorted // list is returned. If the item is not in the sorted list, the index of where it belongs // in the sorted list is returned. The ADT SortedList differs from the ADT List in that a sorted list inserts and deletes items by their values and not by their positions. For example, sortedAdd determines the proper position for item according to its value. Also, locateIndex - which determines the position of any item, given its value - is a sorted list operation but not a list operation. The element of the sorted list have one more requirement: they must implement the interface java.lang.Comparable and have an implementation of the method compareTo, so that the sorted list can order the elements. For example, when we implement the method sortedAdd, if newItem.compareTo(item_X) > 0, where item_X is an item in the list, then newItem should be added after item_X; otherwise, newItem should be added before item_X. Note that, in this lab, the String class we use in the test class has already implemented the compareTo method, so you can compare two strings directly. For further reading about the Comparable interface, please refer to the article here. Exercises 1. Download the following code SortedListInterface.java SortedList.java ListException.java SortedListTester.java 2. Compile and run the program. It should print out the following message: ListException: get (index out of range): 99 The index of "dd" in the list is: 1 The index of "kk" in the list is: 1 4. Complete the following three methods in class SortedList: public void sortedAdd(Comparable newItem) throws ListException; public void sortedRemove(Comparable anItem) throws ListException; public int locateIndex(Comparable anItem) throws ListException; 5. Your program should print out exactly the following messages: aa, bb, cc, dd, ee. aa, bb, dd, ee, ff. ListException: sortedRemove (item not in the list): cc aa, bb, cat, dd, ee, ff. ListException: get (index out of range): 99 aa, bb, cat, dd, ee, ff. The index of "dd" in the list is: 4 The index of "kk" in the list is: 7 6.

public class ListException extends Exception {

public ListException(String s) { System.out.println("ListException: " + s); } }

public class SortedList implements SortedListInterface { private static final int MAX_LIST = 50; private Object items[]; // an array of list items private int numItems; // number of items in list

// default constructor public SortedList() { items = new Object[MAX_LIST]; numItems = 0; }

public boolean isEmpty() { return numItems == 0; }

public int size() { return numItems; }

public Object get(int index) throws ListException {

if (index >= 1 && index <= size()) { return items[index-1]; } else { // index out of range throw new ListException("get (index out of range): " + index); } }

public void removeAll() { items = new Object[MAX_LIST]; numItems = 0; }

// new operations: sortedAdd public void sortedAdd(Comparable newItem) throws ListException { int index = 1;

if (size() == MAX_LIST) throw new ListException("add (array is full)");

// ToDo

}

// new operation: sortedRemove public void sortedRemove(Comparable anItem) throws ListException { int index = 1;

// ToDo

}

// new operation: locateIndex public int locateIndex(Comparable anItem) { int index = 1;

// ToDo

return index; } }

public interface SortedListInterface {

public boolean isEmpty(); // Determines whether a sorted list is empty. // Precondition: None. // Postcondition: Returns true if the sorted list is empty, otherwise returns false.

public int size(); // Determines the length of a sorted list. // Precondition: None. // Postcondition: Returns the number of items that are currently in the sorted list.

public void sortedAdd(Comparable newItem) throws ListException; // Adds an item to the sorted list. // Precondition: None. // Postcondition: The item is added to the sorted list in sorted order.

public void sortedRemove(Comparable anItem) throws ListException; // Removes an item from the sorted list. // Precondition: None. // Postcondition: The item is removed from the sorted list and the sorted order maintained. // If the item is not in the list, a ListException is thrown.

public Object get(int index) throws ListException; // Retrieves a list item by position. // Precondition: index is the position of the item to be retrieved. // Postcondition: If 1 <= index <= size(), the item at position index in the sorted // list is returned; otherwise, a ListException is thrown.

public void removeAll(); // Deletes all the items from the sorted list. // Precondition: None. // Postcondition: The sorted list is empty.

public int locateIndex(Comparable anItem); // Finds an item in the sorted list. // Precondition: None. // Postcondition: If the item is in the sorted list, its index position in the sorted // list is returned. If the item is not in the sorted list, the index of where it belongs // in the sorted list is returned.

}

public class SortedListTester {

// displays the items on the list aList public static void displayList(SortedListInterface aList){ Object dataItem; try { for (int index = 1; index < aList.size(); index++){ dataItem = aList.get(index); System.out.print(dataItem + ", "); } if (aList.size() > 0) { dataItem = aList.get(aList.size()); System.out.println(dataItem + "."); } } catch(ListException e) {} }

public static void main(String[] args) { SortedList aList = new SortedList(); String dataItem; int index;

try { aList.sortedAdd("bb"); aList.sortedAdd("cc"); aList.sortedAdd("aa"); aList.sortedAdd("ee"); aList.sortedAdd("dd"); } catch(ListException e) {}

displayList(aList);

try{ aList.sortedRemove("cc"); aList.sortedAdd("ff"); } catch(ListException e) {}

displayList(aList);

try { aList.sortedRemove("cc"); } catch(ListException e) {}

try { aList.sortedAdd("cat"); } catch(ListException e) {}

displayList(aList);

try { dataItem = (String)aList.get(99); System.out.println("dataItem = " + dataItem); } catch(ListException e) {}

displayList(aList);

index = aList.locateIndex("dd"); System.out.println("The index of \"dd\" in the list is: " + index); index = aList.locateIndex("kk"); System.out.println("The index of \"kk\" in the list is: " + index);

} }