Homework 7 - Extending the Java Collections Framework

CS 2102 - Bterm 08

Homework 7: Extending the Java Collections Framework; Working with ArrayList, Loops, and Library Classes

Due: Tuesday, December 16 at 11:59pm

Assignment Goals

To be able to extend the Java Collections Framework
To take advantage of the functionality provided by the Java Collections Framework
To gain practice using the ArrayList
To gain practice using Java's looping structures
To learn how to implement a priority queue
To be able to test class methods using JUnit

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 a sorting algorithm is independent of the rest of the assignment, but 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 useful 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 methods for doing a Selection Sort on an ArrayList. The Algorithms class will also provide a method for inserting an item into a sorted ArrayList.

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<T> and an instance of a class that implements Comparator<T> and mutates the ArrayList<T> so that it is sorted in the order given by the Comparator<T>.
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<T>
- findMinLoc() that finds in the given ArrayList<T> 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<T>.
- selectionSort() that implements the algorithm that is described above
Insertion into a sorted ArrayList Add to your Algorithms class a void method called insertIntoSortedList(). This method consumes an ArrayList<T> that is already sorted (according to the given Comparator<T>), an element of type T to insert into the ArrayList, and a Comparator<T>. 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).

Of course, you need to test your methods. Construct JUnit tests for each individual method in the Algorithms class. Make a simple class of data, such as a Book or Song or something of your own choosing. Define two different Comparators for this class. Then make examples of ArrayLists of these data items and make sure your JUnit 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<T>. Your PriorityQueue class must directly implement AbstractCollection<T>.

The underlying data structure for your Priority Queue should be an ArrayList<T> (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)
    //     throw NoSuchElementException if the priority queue is empty
    T remove();

    // add the given element to this priority queue
    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)
    //     throw NoSuchElementException if the priority queue is empty
    T peek();

    // returns 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.

Construct JUnit tests for each method defined in your PriorityQueue class.

Provide an Examples class that defines a main method that demonstrates the functionality of your PriorityQueue class. You should create examples of priority queues composed of Books, Songs, or whatever your favorite class is. Create at least two different priority queues, each prioritized according to different Comparators. Your main method should produce neatly-labelled output that shows the contents of the priority queues after adding elements, removing elements, etc.

What to Turn In

Using web-based turnin, turn in a single file hw7.username.zip containing all code and documentation for this assignment. Both partners' names and wpi login names should appear in a comment at the top of the file.