Existing data collection interface: public interface DataCollection { public void insert(E oneThing); public int size(); public String toString(); public E find(String key); public int countOccurrences(boolean lookFor); public boolean contains(E oneThing); public int total(); public double average(); public int countRange(int low, int high); } 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 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 creat 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 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 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 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 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.