Homework 7 - Extending the Java Collections Framework CS 2102 - Bterm 09 Homework 7: Extending the Java Collections Framework; Working with ArrayList, Loops, and Library Classes Due: Tuesday, December 15 at 5pm Assignment Goals To be able to extend the Java Collections Framework To be able to read and use the documentation for the Java Collections Framework To design programs that use ArrayLists and loops To learn how to implement selection sort and non-recursive insertion sort To learn how to implement a priority queue The Assignment The problems in this assignment test a variety of concepts you have learned in CS 2102, including abstraction over the datatype, behavior, and structure of data. The problem that has you implement sorting algorithms gives you practice not only with basics like looping and programming over ArrayLists, but also with the details of how to construct your own user library of useful methods. Not every detail is spelled out for you in the problem descriptions. You will need to read the Java Documentation to fill in some of the details. You will need to be able to apply the various ways we managed abstraction, as discussed over several lectures. You will have two main tasks in this assignment. The first is to create an Algorithms class of sorting methods, described below. The second is to provide an implementation of a Priority Queue (subject to the restrictions outlined below) that extends the Java Collections Framework. For the second task you should make a concerted effort to write as little original code as possible, but still satisfy the restrictions given for the design of the Priority Queue. Remember, the idea of the Java Collections Framework is to provide you with a set of already-written (and tested!) methods that you may use as is (or override if necessary). Problems I. Design an Algorithms class Design a class called Algorithms. Your Algorithms class must provide the following methods: Selection Sort Selection Sort works as follows: When the program processes the list of data for the first time, it finds the location of the smallest item in the list. It then swaps the first item in the list with the smallest one (even if the smallest one is already in the first spot). Next time around, it does the same, but only with the rest of the list, i.e. all items beyond the first one. The third time around, it starts with the third item, because the first two are already in the correct places, and so on. This is hard to do with recursively constructed lists, but is much easier when we can directly swap two items at specific locations, as is the case when the data is stored in an ArrayList. In the Algorithms class design a method called SelectionSort that consumes an ArrayList and an instance of a class that implements Comparator and mutates the ArrayList so that it is sorted in the order given by the Comparator. It is possible to combine all parts of the Selection Sort algorithm into one method, but that is not a good way to design programs. Your program should use the following helper methods: swap() that swaps the elements at the two given index positions in the given ArrayList findMinLoc() that finds in the given ArrayList the index of the minimum element among all elements, at the index greater than or equal to the given index. Of course, it also consumes the Comparator. Insertion Sort - version 1 We have seen a recursively-defined insertion sort algorithm. Here we design a version of insertion sort that works on an ArrayList, using loops. First define a void method called insertIntoSortedList(). This method consumes an ArrayList that is already sorted (according to the given Comparator), an element of type T to insert into the ArrayList, and a Comparator. The method inserts the new element into the ArrayList in the proper position, maintaining the list in sorted order. (You may use this method when implementing your Priority Queue, in Part 2). Now use insertIntoSortedList() as a helper for the method insertionSort() that consumes an arbitrary (unsorted) ArrayList and a Comparator and produces a new sorted ArrayList. It accomplishes this by starting with an empty (sorted) list and inserting into it one by one all the elements of the given ArrayList. Insertion Sort - version 2 Define a second version of insertion sort so that it mutates the existing ArrayList in place. Name your method insertionSortInPlace(). It consumes an arbitrary (unsorted) ArrayList and a Comparator and uses mutation to sort the given arraylist. Use helper methods (don't try to implement the entire algorithm in one method). Of course, you need to test all methods, including helpers. Make a simple class of data, such as Book or Song - but come up with something different - and define two different Comparators for your class. Then, in an Examples class make examples of ArrayLists of these data items and make sure your tests use both of the Comparators. II. Implement a Priority Queue and add it to the Java Collections Framework In class we talked about the Priority Queue data structure that models situations like patients waiting to be seen in a hospital emergency room. In an emergency room, the triage nurse assigns a priority to each patient as he or she arrives. Patients are seen in order according to priority; in this case, the more severe the injury or illness, the higher the patient's priority. Design a class called PriorityQueue. Your PriorityQueue class must directly implement AbstractCollection. The underlying data structure for your Priority Queue should be an ArrayList (i.e. the elements of the Priority Queue should be stored in an ArrayList). The ArrayList should be maintained in sorted order so that the item with the highest priority will always be the first (zeroth) item in the ArrayList. The Priority Queue should provide the following methods:
/**
* retrieve and remove the item at the head of this priority queue
* (i.e. the item with the highest priority)
*
* @throws NoSuchElementException if the priority queue is empty
*/
T remove();
/**
* add the given element to this priority queue
*
* @param t the element to add
* @return true
*/
boolean add (T t);
/**
* retrieve, but do not remove, the item at the head of this priority queue
* (the item retrieved will be the item with the highest priority)
*
* @throws NoSuchElementException if the priority queue is empty
*/
T peek();
/**
* is this priority queue empty?
*
* @return true if this priority queue is empty
*/
boolean isEmpty();
Of course, the Priority Queue class must also provide implementations for all of the obligations it inherits. Provide in the Examples class tests that demonstrate the functionality of your PriorityQueue class. What to Turn In Create an archive of your Eclipse project (see "Saving your work" in Lab 4 if you forgot how to do this). Using web-based turnin, turn in a single zip file containing all code and documentation for this assignment. Follow the naming conventions when naming your file.
