Description
Introduction In this project you are going to implement a list [1] interface to construct your own ArrayList data structure. Using this you will construct an ElephantHerd to hold a family of elephants [2]. [1]. Lists: A List is a list of ordered items that can also contain duplicates. In Java, lists are constructed either using an array or linked list data structure. The implementations for each have certain pros and cons with respect to cost of space and runtime. In this project, you will implement lists using only an array data structure from a custom List interface. [2]. Inheritance: Interface: Interfaces are an important aspect of inheritance in Object Oriented Programming. All methods defined in an Interface are un-implemented and required to be implemented by an inheriting class. In Java an Interface class is inherited by other classes using the keyword implements. See the example code below. 1 List: An interface A List must consist of specific methods irrespective of underlying data structure. These methods are defined as part of an interface that you are required to inherit in your array list and linked list implementations. Refer to List.java for methods and their definitions. Note that methods have generic types∗ and you are required to implement your inherited classes as generic types too (continue reading to see what it means…). ∗A generic type is a generic class or interface that is parameterized over types. In the context of List, T is the type of the object that is in the list, and note that T extends Comparable. 3 CSCI 1933 PROJECT 2 Inheritance Java Example: // An interface. interface IName { public void printName(); } // This class implements the Name interface. class PeopleName implements IName { String firstName; String secondName; // Need to implement printName(). public void printName() { System.out.println(this.firstName + ” ” + this.secondName); } } 1.1 Array List Implementation The first part of this project will be to implement an array list. Create a class ArrayList that implements all the methods in List interface. Recall that to implement the List interface and use the generic compatibility with your code, ArrayList should have following structure: public class ArrayList> implements List { … } The underlying structure of an array list is (obviously) an array. This means you will have an instance variable that is an array. Since our implementation is generic, the type of this array will be T[]. Due to Java’s implementation of generics† , you CANNOT simply create a generic array with: T[] a = new T[size]; Rather, you have to create a Comparable (since T extends Comparable) ‡ array and cast it to an array of type T. T[] a = (T[]) new Comparable[size]; Your ArrayList class should have a single constructor: public ArrayList() { … } that initializes the underlying array to a length of 2. † specifically because of type erasure ‡had T not extended Comparable, you would say T[] a = (T[])new Object[size]; 4 CSCI 1933 PROJECT 2 Due: Wednesday, February 28th 2018 Implementation Details • In addition to the methods described in the List interface, the ArrayList class should contain a private class variable isSorted. This should be initialized to true in the constructor (because it is sorted if it has no elements) and updated when the list is sorted, or more elements are added or set. For the purposes of this class, isSorted is only true if the list is sorted in ascending order. • When the underlying array becomes full, both add methods will automatically add more space by creating a new array that is twice the length of the original array, copying over everything from the original array to the new array, and finally setting the instance variable to the new array. Hint: You may find it useful to write a separate private method that does the growing and copying • When calling either remove method, the underlying array should no longer have that spot. For example, if the array was [“hi”, “bye”, “hello”, “okay”, …] and you called remove with index 1, the array would be [“hi”, “hello”, “okay”, …]. Basically, the only null elements of the array should be after all the data. • Initially and after a call to clear(), the size method should return 0. The “size” refers to the number of elements in the list , NOT the length of the array. After a call to clear(), the underlying array should be reset to a length of 2 as in the constructor. After you have implemented your ArrayList class, include junit tests that test all functionality. 5 CSCI 1933 PROJECT 2 2 An Elephant Herd You will use array list and linked list implementations to now construct a herd of elephants. Elephants have a name, age and height. You will use the ArrayList data structure to construct this Elephant Herd. You are provided with Elephant.java which implements Comparable (Refer to the Elephant.java file for details) which is a class with three properties: name, age, and height, setters and getters, a compareTo() and a toString() method. 2.1 The Herd Create a class ElephantHerd. To create this herd you will use your ArrayList class as the underlying object list. The type for the object in the list will be Elephant. Your ElephantHerd should include the following methods: • private List list – Your underlying list of Elephants. • public ElephantHerd() – This constructor will initialize the underlying list. • public boolean add(Elephant ellie) – This will add ellie to the end of the list and return true if successful, false otherwise. • public Elephant find(String name) – This will try to find an elephant with name field that contains name. Note that the name need not be exactly the same as the name of elephant. You can use the built in String method public boolean contains(String anotherString ) § . Return null if no Elephant was found. • public Elephant remove(int index) – This will remove the elephant object currently at index index, if index is out of bounds, return null. • public void sort() – This will sort the list in order of height, from tallest to shortest. Note that you cannot just use the ArrayList sort method that you wrote earlier, because that method sorts based on the results of compareTo(), not on the basis of height. • public Elephant[] getTopKLargestElephants(int k) – This will return an array of length k containing the top-k elephants sorted by their height, from tallest to shortest. If the list is empty, return null. If the number of elephants (M) in the list is smaller than k, then return an array of length M. After you have implemented your ElephantHerd class, write junit tests that test all functionality. §The actual signature of contains is public boolean contains(CharSequence s) but you don’t have to worry about that 6 CSCI 1933 PROJECT 2 3 File Input Now that you have created your ElephantHerd, it is time to make a convenient way to input the data for the herd. You will do this by creating an ElephantReader class which will be able to read data from a file into an ElephantHerd object and to write data from the herd to a file. To do this, you will need to import File, Scanner, and PrintWriter. These are the only imports allowed. To read the data, you will create a File object, and then use a Scanner to parse the data. The following code gives examples of how to read and write to files called “fileName”. // assume our filename is stored in the string fileName Scanner s = null; // declare s outside try-catch block try { s = new Scanner(new File(fileName)); } catch (Exception e) { // returns false if fails to find fileName return false; } // Now use s in the same way we used Scanners previously for user input to write to an arbitrary textfile, do the following: // assume our filename is stored in the string fileName PrintWriter p = null; // declare p outside try-catch block try { p = new PrintWriter(new File(fileName)); } catch (Exception e) { return false; } At this point, it is not critical that you understand exactly how the try/catch block works, but know that the contents of the “try” portion are what could throw an Exception, while the contents of the “catch” block are what you want the program to do if the Exception is thrown. This class only contains two method: • public static boolean readElephants(ElephantHerd e, String fileName) – This method removes all previous elephants in e and replaces them with elephants from the file of the given name. If there is an error, or e is null, return false. Otherwise, return true. You can assume that the file is formatted such that there is data for one elephant per line. The data will be in the form of “name age height”. An example text file is provided for testing. • public static boolean writeElephants(ElephantHerd e, String fileName) – This method will write all elements of e to a file of the given name. If there is an error, or e is null or 7 CSCI 1933 PROJECT 2 empty, return false. Otherwise, return true. The file should be written using the toString function in List. This should give the same format as the file being read, so a written file can be reloaded later. 4 Iterators (Honors) Note: This section is **required** for students in Honors section only. Optional for others but no extra credit. An iterator is an object that traverses a list, going through each element exactly once. This section will require you to write another class, and to make modifications to the ArrayList class. You will write a ArrayListIterator class which will iterate over a list. This iterator should implement java’s iterator interface in addition to the List interface. Make sure to import java.util.Iterator. This class will have two functions and a constructor. It will also need class variables to store a pointer to its ArrayList and the current index. 1. ArrayListIterator(ArrayList a) – the constructor. This constructor will never be directly called by the user. Instead, it will be called in the iterator() function in the ArrayList class. 2. hasNext() – This will return true if there is another object to iterate on, and false otherwise. 3. next() – This will return the next object if there is one, and null otherwise. The first line of the ArrayListIterator class should be as follows: private class ArrayListIterator implements Iterator, List Note that in order for a class to be private, it must be in the same document as another class, and within the curly braces of that class. This means that ArrayListIterator should be in the ArrayList.java file, and should be in the curly braces of ArrayList, with the methods of ArrayList. You will also need to make some modification to the ArrayList class. First, the class now needs to implement Iterable. public class ArrayList> implements Iterable, List Secondly, you will need to add the method public Iterator iterator(). This method should 8 return an ArrayListIterator object by calling the ArrayListIterator constructor and passing itself to the constructor (via the this keyword). Make sure to create junit tests to ensure that your iterator functions as desired. Example code using the iterator is provided below: Iterator Example: // the main method of a class using the ArrayListIterator ArrayList arr = new ArrayList(); arr.add(‘‘hello”); arr.add(‘‘how”); arr.add(‘‘are”); arr.add(‘‘you?”); Iterator it = arr.iterator(); System.out.println(it.next()); //prints ‘‘hello” System.out.println(it.hasNext())); //prints true while (it.hasNext()) { System.out.print(it.next()); //prints ”how are you?” } 9
