The next exercise is based on this implemetation for an OrderedArrayList of integers: //Interface: ArrayListADT public interface ArrayListADT { //same as above, you already have it! }

//Class: ArrayListClass implements //Interface: ArrayListADT public abstract class ArrayListClass implements ArrayListADT { //same as above, you already have it! }

//Class: OrderedArrayList extends //Super class: ArrayListClass public class OrderedArrayList extends ArrayListClass{ public OrderedArrayList() { super(); }

public OrderedArrayList(int size) { super(size); }

//implementation for abstract methods defined in ArrayListClass

//ordered list --> binary search public int search(int item) { int first = 0; int last = length - 1; int middle = -1;

while (first <= last) { middle = (first + last) / 2; if (list[middle] == item) return middle; else if (list[middle] > item) last = middle - 1; else first = middle + 1; } return -1; }

public void insert(int item) { int loc; boolean found = false; if (length == 0) //list is empty list[length++] = item; //insert item and increment length else if (length == maxSize) //list is full System.err.println("Cannot insert in a full list."); else { for (loc = 0; loc < length; loc++) { if (list[loc] >= item) { found = true; break; } } //starting at the end, shift right for (int i = length; i > loc; i--) list[i] = list[i - 1]; list[loc] = item; //insert in place length++; } }

/* Another version for insert: public void insert(int item) { int loc; boolean found = false; if (length == 0) //list is empty list[length++] = item; //insert item and increment length else if (length == maxSize) //list is full System.err.println("Cannot insert in a full list."); else { int i = length - 1; while (i >= 0 && list[i] > item) { list[i + 1] = list[i]; i--; } list[i + 1] = item; // Insert item length++; } } */

public void insertAt(int location, int item) { if (location < 0 || location >= maxSize) System.err.println("The position of the item to be inserted is out of range."); else if (length == maxSize) //the list is full System.err.println("Cannot insert in a full list."); else { System.out.println("Cannot do it, this is a sorted list. Doing insert in place (call to insert)."); insert(item); } }

public void insertEnd(int item) { if (length == maxSize) //the list is full System.err.println("Cannot insert in a full list."); else { System.out.println("Cannot do it, this is a sorted list. Doing insert in place (call to insert)."); insert(item); } }

public void replaceAt(int location, int item) { //the list is sorted! //is actually removing the element at location and inserting item in place if (location < 0 || location >= length) System.err.println("The position of the item to be replaced is out of range."); else { removeAt(location);//method in ArrayListClass insert(item); } }

public void remove(int item) { int loc; if (length == 0) System.err.println("Cannot delete from an empty list."); else { loc = search(item); if (loc != -1) removeAt(loc);//method in ArrayListClass else System.out.println("The item to be deleted is not in the list."); } }

/*Another version for remove: public void remove(T item) { int loc; if (length == 0) System.err.println("Cannot delete from an empty list."); else { loc = search(item); if (loc != -1) { for(int i = loc; i < length - 1; i++) list[i] = list[i + 1]; //shift left length--; } else System.out.println("The item to be deleted is not in the list."); } } */ }

2.1. Add to class OrderedArrayList a new method called removeDuplicates that should eliminate any duplicates from a sorted list. For example, if the list is: [2, 2, 2, 2, 5, 5, 8, 9, 9, 9 ] before the method is invoked, it should be [2, 5, 8, 9 ] after the method executes. Test the method using this client:

//Testing the method removeDuplicates added to the user created OrderedArrayList class

public class Lab8_3 { public static void main(String[] args) { OrderedArrayList list = new OrderedArrayList(); list.insert(8); list.insert(2); list.insert(2); list.insert(9); list.insert(5); list.insert(9); list.insert(2); list.insert(9); list.insert(2); list.insert(5); System.out.println("The original list is: "); list.print(); System.out.println("The list after method call is: "); list.removeDuplicates(); list.print(); } }

2.2. Same problem. This time use the ArrayList class in Java. Write removeDuplicates as a client method and use the print method provided.

//Testing the method removeDuplicates using the Java ArrayList class import java.util.ArrayList; public class Lab8_4 { public static void main(String[] args) { ArrayList list = new ArrayList (); list.add(2); list.add(2); list.add(2); list.add(5); list.add(5); list.add(8); list.add(9); list.add(9); System.out.println("The original list is: "); print(list); System.out.println("The list after method call is: "); removeDuplicates(list); print(list); }

public static void removeDuplicates(ArrayList list) { ...

}

public static void print(ArrayList someList) { for(Integer i:someList) System.out.print(i + " "); System.out.println(); } }