In this assignment, you are asked to implement a sorted list collection, called ThingSortedArrayBag where Thing is a class that represents an object of your choice. Requirements Part 1: Implement your Thing class 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. It is prohibited to use grocery items, circles, lines, persons, cars, students, bank accounts, points in two-dimensional space, or songs. Please note that you will reuse your Thing class across more than one programming assignment, so try to choose something that interests you. Include the name of your Thing class and its instance variables in your initial plan submission on February, 4th. Your Thing class must have the following characteristics: has a meaningful name (not Thing). has exactly 2 instance variables such that: o one instance variable must be String and this variable will be used as a search key. o one instance variable must be int and this variable will be used to find aggregate information about Things that are stored in the collection class as will be explained later. All instance variables must be declared as private. Implement a constructor for your Thing class that takes two input parameters to initialize the two instance variables. The order of the input parameters must be as follows String, then int. Implement getters and setters for all the instance variables of your Thing. Implement toString method that returns a String representation of your Thing class where all the instance variables are in one line and separated by tabs. Implement the equals method for your Thing where two things are considered equal when they have the same values in both of the instance variables. 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 prints true: String str1 = "Hello"; String str2 = "hello"; System.out.println(str1.equalsIgnoreCase(str2)); Implement the comapreTo method that takes a Thing object as input parameter and returns either 0, -1, or 1 based on whether the input Thing is equal to, larger than, or smaller than the current thing respectively. Note that Things in your collection are to be sorted on the String search key first, then on the int instance variable. For example, if your Thing is a Circle that has color and radius as the String and int instance variables respectively, then: o (red,10) < (Red,20) because: red is equal to Red and 10 < 20. o (Blue, 10) < (red, 30) because Blue < red in alphabetical order ignoring the case. The Thing class must also implement the Comparable interface. Assume, for example, your Thing is called Circle, then the class header will be as follows: public class Circle implements Comparable Part 2: Implement a Sorted Collection class 1. Implement a collection class of Things that stores the elements in a sorted order using a simple Java array. Note that: 1.1. you may NOT use the Java library classes ArrayList or Vector or any other java collection class. 1.2. you must use simple java Arrays in the same way as we implemented IntArrayBag collection in class. 2. The name of your collection class should include the name of your Thing. For example, if your Thing is called Circle, then your collection class should be called CircleSortedArrayBag. 3. The collection class has two instance variables: (1) numThings which is an integer that represents the number of things in class (note that you should change Things to be the name of your thing, for example, numCircles) and (2) an array of type Thing[] (e.g., Circle[]). 4. Implement a constructor for your collection class that takes one integer input parameter that represents the maximum number of elements that can be stored in your collection. 5. Implement the following methods in your collection class: 5.1. add: a method that takes two input parameters and uses these inputs to instantiate an object of type Thing, initialize its instance variables, and then inserts it in the collection class. Note that (1) the input parameters to the add method must be in the order String, int, and (2) the add method must insert elements in sorted order according to the compareTo method of the Thing class. Note that, it is not the responsibility of the collection class to decide on how to sort things. On the other hand, sorting is dependent on the semantics of the Thing class. Moreover, according to compareTo, the items will be sorted either in ascending or descending order. Do not use the java Arrays's sort method. 5.2. size: a method that returns the number of objects in the collection. 5.3. 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. For example, a list of Circles is represented by the following String: color radius ------------------ blue 10 Green 20 red 20 Red 30 5.4. indexOf: this method takes one input parameter of type Thing. The method returns an integer that represents the array index at which the input element is found or -1 if the element is not found. If the element is found more than once, then the index of any of the element's occurrences can be returned. Note that the equality of things is determined by the equals method in your Thing class. 5.5. remove: similar to the indexOf method, this method takes one input parameter of type Thing. The method then searches the collection for an object that equals the input object and deletes one occurrence of that object if found. The method then returns true if an object is deleted and false otherwise. Note that, this method must maintain the sorted order which means that just replacing the deleted item with the last element in the array will not work anymore because this may break the sorted order. On the other hand, you should shift the array elements up to fill the gap that is created by the deleted item. Do not use the Java's Array sort method. 5.6. countOccurrences: this method depends on the search key attribute of the Thing class. The method takes as input a String value and returns as output the number of objects in the collection that possesses a search key attribute that matches the input search value. Same to the find method, the key match should be case insensitive. 5.7. grab: a method that takes an integer, called index, as input and returns as output the Thing that is stored at position index in the collection or null if index is beyond the size of the collection. Note that, the method does not delete the element from the array. 5.8. total: this method uses the int instance variable of the Thing class. Basically, the method calculates and returns the sum of the integer instance variable of all objects stored in the collection. For example, in the Circle collection, this method finds the sum of radius of all circles in the list. This sum can be used, for example, along with the output of the size method to find the average radius. 5.9. replace: this method takes two inputs, oldThing and newThing, each of them is of type Thing. The method then searches the collection for an element that is equal to oldThing. If found, the method replaces (only one occurrence of) oldThing with newThing while maintaining the sorted order. On the other hand, if oldThing is not found in the collection, the method does not do anything. The method then returns true or false based on whether a replacement took place or no. 5.10. sameContents: this method takes one input parameters of type ThingSortedArrayBag. The method then returns true if the input bag includes the same elements as the current bag even if the count of each element may be different from one bag to the other. For example, the method should return true for the following two bags of integers. The method returns false otherwise. [1,1,2,2,3] and [1,2,3] class ThingArrayBagIterator This is an inner class inside the ThingSortedArrayBag class and it is used to iterate over all elements in the collection. An implementation of the list iterator is discussed in class and can be found in slides#37-39 in Lecture-03-Feb1 and also in lecture-03-code that is posted on D2L. Basically, the header of your iterator class should be as follows: public class ThingArrayBagIterator implements Iterator You have to change of the rest of iterator class as necessary to reflect your Thing data type. You also must change your ThingSortedArrayBag class to implement Iterable and add the iterator method that returns an iterator of type ThingArrayBagIterator. To test this part, write a for-each loop in the driver to iterate over all items in your collection