Overview

Upon completion of this lab, you should be able to understand the use of an Ordered List, and how it compares objects in order to have them inserted in the proper place in the Ordered List.

Exercise 1

Download ArrayList.java. It is a completed version; the ArrayList.java on the Sample Code webpage is incomplete.

Download the following java classes from the List ADT section of the sample code link: ArrayOrderedList, OrderedListADT, ListADT, EmptyCollectionException, ElementNotFoundException, ArrayIterator.

Download the file Phone.java. The Phone class is a simple class that represents a telephone listing: the attributes are a name and a phone number.

Add to the Phone class a header such that it implements the Comparable interface (so you will change the header to public class Phone implements Comparable; instead of Tyou need to specify the type of objects that will be compared, in this exercise objects of class Phone.

Add a int compareTo(Phone obj) method to the Phone class , such that the Phone entries are compared by name. Method compareTo compares this object with the specified object obj for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object. Hint: you will need to use the compareTo method of the String class in your code.

Check that your Phone class compiles.

ArrayList.java

//******************************************************************** // ArrayList.java Authors: Lewis/Chase // Mods : JCD // Represents an array implementation of a list. The front of // the list is kept at array index 0. This class will be extended // to create a specific kind of list. //******************************************************************** import java.util.Iterator; public class ArrayList implements ListADT { protected final int DEFAULT_CAPACITY = 100; private final int NOT_FOUND = -1; protected int rear; protected T[] list; //----------------------------------------------------------------- // Creates an empty list using the default capacity. //----------------------------------------------------------------- public ArrayList() { rear = 0; list = (T[])(new Object[DEFAULT_CAPACITY]); } //----------------------------------------------------------------- // Creates an empty list using the specified capacity. //----------------------------------------------------------------- public ArrayList (int initialCapacity) { rear = 0; list = (T[])(new Object[initialCapacity]); } //----------------------------------------------------------------- // Removes and returns the last element in the list. //----------------------------------------------------------------- public T removeLast () throws EmptyCollectionException { T result; if (isEmpty()) throw new EmptyCollectionException ("list"); rear--; result = list[rear]; list[rear] = null; return result; } //----------------------------------------------------------------- // Removes and returns the first element in the list. //----------------------------------------------------------------- public T removeFirst() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException ("list"); T result = list[0]; rear--; // shift the elements for (int scan=0; scan < rear; scan++) list[scan] = list[scan+1]; list[rear] = null; return result; } //----------------------------------------------------------------- // Removes and returns the specified element. //----------------------------------------------------------------- public T remove (T element) { T result; int index = find (element); if (index == NOT_FOUND) throw new ElementNotFoundException ("list"); result = list[index]; rear--; // shift the appropriate elements for (int scan=index; scan < rear; scan++) list[scan] = list[scan+1]; list[rear] = null; return result; } //----------------------------------------------------------------- // Returns a reference to the element at the front of the list. // The element is not removed from the list. Throws an // EmptyCollectionException if the list is empty. //----------------------------------------------------------------- public T first() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException ("list"); return list[0]; } //----------------------------------------------------------------- // Returns a reference to the element at the rear of the list. // The element is not removed from the list. Throws an // EmptyCollectionException if the list is empty. //----------------------------------------------------------------- public T last() throws EmptyCollectionException { if (isEmpty()) throw new EmptyCollectionException ("list"); return list[rear-1]; } //----------------------------------------------------------------- // Returns true if this list contains the specified element. //----------------------------------------------------------------- public boolean contains (T target) { return (find(target) != NOT_FOUND); } //----------------------------------------------------------------- // Returns the array index of the specified element, or the // constant NOT_FOUND if it is not found. //----------------------------------------------------------------- private int find (T target) { int scan = 0, result = NOT_FOUND; boolean found = false; if (! isEmpty()) while (! found && scan < rear) if (target.equals(list[scan])) found = true; else scan++; if (found) result = scan; return result; } //----------------------------------------------------------------- // Returns true if this list is empty and false otherwise. //----------------------------------------------------------------- public boolean isEmpty() { return (rear == 0); } //----------------------------------------------------------------- // Returns the number of elements currently in this list. //----------------------------------------------------------------- public int size() { return rear; } //----------------------------------------------------------------- // Returns an iterator for the elements currently in this list. //----------------------------------------------------------------- public Iterator iterator() { return new ArrayIterator (list, rear); } //----------------------------------------------------------------- // Returns a string representation of this list. //----------------------------------------------------------------- public String toString() { String result = ""; for (int scan=0; scan < rear; scan++) result = result + list[scan].toString() + " "; return result; } //----------------------------------------------------------------- // Creates a new array to store the contents of the list with // twice the capacity of the old one. //----------------------------------------------------------------- protected void expandCapacity() { T[] larger = (T[])(new Object[list.length*2]); for (int scan=0; scan < list.length; scan++) larger[scan] = list[scan]; list = larger; } }

ArrayOrderedList.java

/** * ArrayOrderedList represents an array implementation of an ordered list. * * @author Dr. Lewis * @author Dr. Chase * @version 1.0, 08/12/08 */ public class ArrayOrderedList extends ArrayList implements OrderedListADT { /** * Creates an empty list using the default capacity. */ public ArrayOrderedList() { super(); } /** * Creates an empty list using the specified capacity. * * @param initialCapacity the integer initial size of the list */ public ArrayOrderedList (int initialCapacity) { super(initialCapacity); } /** * Adds the specified Comparable element to this list, keeping * the elements in sorted order. * * @param element the element to be added to this list */ public void add (T element) { if (size() == list.length) expandCapacity(); Comparable temp = (Comparable)element; int scan = 0; while (scan < rear && temp.compareTo(list[scan]) > 0) scan++; for (int scan2=rear; scan2 > scan; scan2--) list[scan2] = list[scan2-1]; list[scan] = element; rear++; } }

OrderedListADT.java

/** * OrderedListADT defines the interface to an ordered list collection. Only * Comparable elements are stored, kept in the order determined by * the inherent relationship among the elements. * @author Dr. Lewis * @author Dr. Chase * @version 1.0, 08/13/08 */ public interface OrderedListADT extends ListADT { /** * Adds the specified element to this list at the proper location * * @param element the element to be added to this list */ public void add (T element); }

EmptyCollectionException.java

/** * @author Lewis and Chase * * Represents the situation in which a collection is empty. */ public class EmptyCollectionException extends RuntimeException { /** * Sets up this exception with an appropriate message. * @param collection String representing the name of the collection */ public EmptyCollectionException (String collection) { super ("The " + collection + " is empty."); } }