Description
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
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
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
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
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
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
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