Objective

Implement and manipulate an ORDERED LIST collection class using a linked list implementation.

Problem Description

You will be writing a program to manage an ordered list of "things" where you get to choose the "things" in the list.

Start by choosing what sort of list you would like to keep. For example:

To-do list

Vacation and travel information

Pets

Real estate properties

pretty much any sort of list

You can be creative about your list. However, it is prohibited to use books, points, lines, circles, grocery items, students, persons, bank accounts, menu items, cars, pets or songs. You may re-use the class you created for program #2.

IMPORTANT: You may not use the LinkedList class from the Java library. Instead, you must implement your own linked list as explained below.

Thing Class (same requirements as Program #2)

Your Thing class must have the following characteristics:

a meaningful name (not "Thing")

exactly 3 instance variables such that:

the first instance variable must be of type String and this variable will be used as a search key

the second instance variable must be integer (i.e., int) and this variable will be used to find aggregate information about Things that are stored in a collection class as will be explained later

the third variable must be of type boolean

All instance variables must be private

Implement a three-arguments constructor for your Thing class. The arguments must be in the order (String, int, boolean).

Implement getters and setters for all the attributes of your Thing. (Note that Eclipse will automagically create them for you with Source | Generate Getters and Setters)

Implement a toString() method that returns a String representation of your Thing where all the instance variables are in one line and separated by tabs (Eclipse will automagically create a toString() method for you with Source | Generate toString(). However, the format will not be correct.)

Implement the equals() method for your Thing where two Things are considered equal when they have the same search key. Note that, the equality of String attributes should be case insensitive. For example, MATH, math and Math match each other. In order to compare strings in Java use the String's equalsIgnoreCase() method. For example, the following code should print true:

String str1 = "Hello";

String str2 = "hello";

System.out.println(str1.equalsIgnoreCase(str2));

(Again, Eclipse will automagically create an equals() method for you with Source | Generate hashcode() and equals(). However, you may have to make changes to it to meet this program specification.)

Implement the Comparable interface and the compareTo() method for your Thing. compareTo() returns

a negative number when the invoking object's search key is less than the parameter's search key

0 when the two search keys are equal

a positive number when the invoking object's search key is greater than the parameter's search key

For example, "ant".compareTo("bat") will return a negative number.

Your compareTo() method must compare two Things.

Note that the comparison of String attributes should be case insensitive. For example, MATH, math and Math must match each other.

ThingNode class

This class represents a node in the linked list. Name it after the Thing you implemented (e.g., StudentNode). Your node class should include the following:

Two private instance variables:

data of type "Thing". The data part must be of type "Thing". Do not use a generic node.

link of type "ThingNode"

A constructor that takes two input parameters and uses them to initialize the two instance variables.

The following instance methods which are the same as in the IntNode class that we discussed in class and also are discussed in the text book (Chapter 4, Section 4.2). Change the methods as appropriate to reflect your new type of data.

getData(), getLink(), setData(), setLink()

ThingLinkedCollection Class

This class is used to manage a collection of things where the things are stored in a linked list (not an array). This is discussed in Section 4.4 of the text book. The requirements for this class are as follows:

Implement a collection class of your things using a linked list.

You may NOT use the Java library classes LinkedList, ArrayList or Vector or any other java collection class.

You must create a linked list in the same way as discussed in class.

The name of your collection class should include the name of your Thing. For example, if your Thing is called Student, then your collection class could be called StudentLinkedCollection.

Two instance variables:

head of type ThingNode: this represents the head of the linked list that stores your collection.

manyItems of type int: this represent the size of the linked list.

Implement a no arguments constructor for your collection class that initializes the collection class instance variables.

Implement add()- a method that takes one input parameter matching the type of your Thing and then adds it to the collection class without trying to maintain any specific order. Duplicates are permitted. Use this method to help you get started.

Your collection class should implement the DataCollection interface which has been provided in D2L with the programming assignment. The interface file is named DataCollection.java. This is the same file you used for program #2.

Implement the following methods in your collection class, as defined in the DataCollection interface:

void insert(Thing oneThing): a method that takes one input parameter matching the type of your Thing and then inserts it in the collection class IN DESCENDING ORDER according to the search key instance variable. Simply add any duplicate Things.

Do not attempt to sort the list or use a sorting algorithm. You must maintain the list in order by inserting the new element in the proper position.

Note that maintaining an ordered list is more difficult than adding to an unordered list, so implement the simple add() method first to get started. Once you have enough of the program working, go back and work on the insert() method. This is the most important part of the assignment. One version of a test program can either use the add() method or it can use the insert() method but the insert() method will not work properly if you start with an unordered list which has been created using add().

size(): a method that returns the number of objects in the collection.

toString(): a method that returns a String representation of the collection that includes all elements that are stored in the collection. The output string must be nicely formatted in a tabular format, one Thing per line. For example, a list of students (in descending order by name) could be displayed as follows:

Name Age CS?

---------------------------

Reem 27 true

Mohammed 25 false

Maria 20 true

Hanna 30 false

Thing find(String s): this method depends on the search key attribute of your Thing class. The method takes as input a String value and returns the first object with a search key that matches the input search value. Use the compareTo() method from your Thing class. Return null if no matching object is found.

int countOccurrences(boolean): this method depends on the boolean attribute of your Thing class. The method takes as input a boolean value and returns as output the number of objects in the collection that have a boolean attribute that matches the input parameter.

boolean contains(Thing): this method takes one input parameter matching the type of your Thing. The method returns true or false based on whether the collection contains at least one Thing that is equal to the input parameter. Use the equals() method from your Thing class to determine if two objects are equal.

int total(): this method uses the int instance variable of your Thing class. The method calculates and returns the sum of the int instance variable of all objects stored in the collection. For example, in the student collection, this method finds the sum of age of all students in the list. This sum could be used, for example, along with the output of the size() method to find the average student age.

double average(): this method returns the average of the int instance variables of all objects stored in the collection.

int countRange(int low, int high): this method depends on the int instance variable of your Thing class. The method takes as input two int values and counts how many objects in the list have a value that lies in the given range including the endpoints. For example, in the student collection class that is displayed above, countRange(25,30) returns 3 because there are 3 students with age values that fall in the range between 25 and 30 inclusive. Note that if the first input parameter is greater than the second input parameter then the method always returns 0 (i.e., countRange(30,25) returns 0).

Write an iterator class for your collection that iterates through your collection and returns the items in the list in the order in which they are stored. The results will be similar to toString() except that the iterator returns one Thing at a time. Your iterator will have constructor, hasNext() and next() methods. Implement your iterator as an embedded class as shown in class. Add an iterator() method to your collection class.

EXTRA CREDIT: void delete(Thing): similar to the contains() method, this void method takes one input parameter of your type of Thing. The method then searches the collection for the first object that equals the input object and deletes its occurrence if found. After the item has been deleted, the list must still be maintained IN ORDER. This is the most difficult method in this assignment so you may wish to do it last. You may also wish to implement an additional helper method (or not). If you cannot get this method working, just create an empty method as a placeholder to complete the implementation of the interface.

Implement these additional methods. (It is perfectly OK to have methods that are not part of the DataCollection interface.)

int positionOf(Thing): searches for the matching Thing and returns its position. Numbering starts at 1 (the first thing in the list is at position 1). If the Thing is not found, return 0.

Thing grab(int position): returns the Thing located at the specified position in the list or null if position is negative, zero or past the end of the list. The first element in the list is at position 1. Note that this method does not remove the element from the list.

Driver Class

Implement a Driver class that includes a test program to:

Create two collection classes.

Use the add() method to add 5-10 items to one collection. You may use any arbitrary values in the objects to be inserted.

Use the insert() method to insert 5-10 items into the second collection. You may use any arbitrary values in the objects to be inserted.

The driver tests all the methods of the collection class using the ordered list. Display the results of each operation after it is performed. Label your output clearly.

Use at least two assert statements to test your code.

Do not use a Scanner to read any inputs from the user. Instead, use hard coded values for the different methods' inputs.

Other Requirements

Draw a UML structure diagram showing the relationship between the classes in your solution. You may hand draw or use any tool of your choice but the diagram must be submitted in a format that I can read (one of .doc, .docx, .pdf, .jpg, .txt). If I cannot read it, I cannot grade it.

Draw a UML class diagram for your collection class (may be combined with the structure diagram).

Note that automated tools often do not follow the conventions that I require.

Factor the classes as described above. This just means you should implement the classes and put the methods in the correct class as indicated above. It also means that instance variables are private and one class should not interfere with the internal workings of another class.

In the comments, document the invariant for your collection class. You do not need to provide any other comments for this program.

Use good coding style throughout (see slide deck 01-D Objects and Chapter 1 of your text) including

correct private/public access modifiers

consistent indenting

meaningful variable names

normal capitalization conventions

other aspects of easy-to-read code

You are free to adopt and adapt code from the textbook and class slides. However, document the source of any borrowed code.

Project Plans

Turn in a project plan. Create a spreadsheet using Excel (Microsoft), Calc (Open Office) or Google sheets (export in Excel format). Use formulas to add up columns as appropriate. Put your plan in the D2L dropbox for Program #3 Project Plans.

As you work on the project, fill in the time you actually spend. At the end, total up the time you spent on the assignment. Use spreadsheet formulas. Turn in this time report with your programming assignment in the D2L dropbox for Program #3.