1 Background

A lot of what you learned last semester in IC211 is going to be required knowledge for this course. This homework is essentially an IC211 lab to help you remember those concepts. In particular, we need to dredge up knowledge of generics and interfaces.

This course is almost entirely about storing data in different ways so that you can perform the same tasks in different ways, for different purposes. A set of tasks to be performed, but freedom in implementing them? Well, that sounds like it calls for an interface. Similarly, those tasks will need to be performed on a wide variety of types of data. That, of course, is exactly what generics are for.

Soon enough, this assignment will take on a little bit more meaning - for the moment, you need only understand what each of the functions you need to implement need to do.

2 Testing your code

We’re no longer spoon feeding you error checking code this semester; it’s important you learn how to test code yourself. For this assignment, the only autotest that you will see is a basic sanity check to make sure everything compiles.

You’ll have to make your own main methods to test your code for correctness, making sure the results are what they need to be, even though you won’t necessarily turn those in (or if you turn it in, we won’t run it when testing your class). Testing should include not only performing each function correctly, but also throwing the exceptions specified at the right times.

3 Your task: complete the implementation of BoundedList

• List.java
• BoundedList.java

You can get all these files at once by downloading the file hw01.tar.gz and running tar xzvf hw01.tar.gz

The file List.java defines our List interface. Recall that interfaces in Java provide a way for a programmer to describe how a class of objects should be interacted with without actually describing the implementation directly. For example, the List interface specifies the general method of a List but not the specifics of the implementation. In this case, you’ll implement it with what we’ll call a BoundedList.

N.B.: java.util has its own List interface, which is similar. We have our reasons for making our own. Just make sure you’re using the one we give you, and not the one built into Java. As long as you stay working in the same directory as List.java, this should take care of itself (if you didn’t, you’d need packages).

3.1 Using the List interface

The interface is well commented - you can see the javadoc here. Naturally, your BoundedList should perform all of those functions in the specified way.

3.2 The BoundedList (your code!)

The BoundedList implementation of the List interface is one where the user must define the maximum capacity of the list in the constructor - this capacity can never grow bigger or smaller (though the size, or the number of elements actually within the list can, it can just never outgrow the capacity).

List<Integer> lst = new BoundedList<Integer>(10); //list with a capacity of 10

The elements of this list are stored as an array:

private T elements[]; //array of elements of type generic T

You must implement your BoundedList such that the elements array always arranges items in the lower indexes of the list (that is, it is impossible to have elements in indices 0, 1, and 3, but to have 2 empty). To do this, consider how you must shift elements in the array as items are added and removed.

All methods must also check bounds to ensure that the user only accesses appropriate indexes, as stated in the javadoc. For example, consider the following sequence of operations, the current array arrangement, and the error conditions for the add function.

List<Integer> lst = new BoundedList<Integer>(5); // [ ] -- empty list

lst.add(0, 1);   // [ 1 ]
lst.add(0, 2);   // [ 2 1 ]
lst.add(1, 3);   // [ 2 3 1 ]
lst.add(4, 4);   // IndexOutOfBoundsException -- adding more than +1 the current size
lst.add(5, 5);   // IndexOutOfBoundsException -- outside the bounds of the fixedList at size 5
lst.add(-1, -1); // IndexOutOfBoundsException -- negative index
lst.add(3, 4);   // [ 2 3 1 4 ]
lst.add(0, 5);   // [ 5 2 3 1 4 ]
lst.add(0, 6);   // IllegalStateException -- list is full

To help your development and grading, a toString() method is provided. Note that in grading, we will test on a wide variety of inputs and settings.

3.3 Making an array of Generics

Java generics were not an original part of the language, and sometimes can feel a little duct-taped on. One example is when you try to make an array of generic type. You’re not allowed to do this:

T[] myArray = new T[5];

This is because the way generics were implemented, at run-time, your program actually doesn’t know what T is, so it’s unable to perform this allocation. Instead, you’re required to do this:

T[] myArray = (T[]) new Object[5];

This will compile and almost certainly run fine. But, this gives you a warning that your code uses “unchecked or unsafe operations.” And that’s true! T (whatever it is) is a subclass of Object, and so things that are Objects might not be of type T, making this a potentially-dodgy cast! Fortunately, Java has a way to tell the compiler, “yeah, I know this method/constructor isn’t perfect, but just shut up about it” with the “SuppressWarnings” annotation:

public void aFunction(T e) {
  //stuff
  @SuppressWarnings("unchecked")
  T[] myArray = (T[]) new Object[5];
  //stuff
}

This is better than just ignoring it because sometimes that warning is really useful! Better to suppress it where you know you’re doing it, and pay attention to the warning when it comes up unexpectedly in other parts of your code.

There are a few other ways to do this, which you can read about here. This is a known shortcoming of the Java language, which normally is hidden from the programmer because you should just use the pre-built classes like java.util.ArrayList. But in IC312, we want to build these data structures ourselves, and as a result sometimes we will encounter these “warts” of the language.

Main point: in this class, you should never be happy with code that has any warnings. In this one special circumstance of creating an array with generic type, you can break that rule, but should still hide the warning with the @SuppressWarnings line.

3.4 Bonus: Iterable

+5% on this assignment if you can get this working.

Being able to efficiently loop over all elements of a data structure is called traversal and is a very important operation that we will discuss in detail throughout this semester.

Different programming languages have different mechanisms to enable this generically. Most common is some kind of iterator which classes can support, that allows stepping through elements one at a time.

In Java, this is supported by two interfaces. First is java.util.Iterator, which is for the iterator itself and has required methods hasNext() and next(). The other interface is Iterable, which is for the entire class you want to allow iteration over; it has just one required method iterator() which must returns an instance of Iterator.

In this case, to allow iteration (and for loops!) over your BoundedList class, you need to do two things:

• Create a new class which will serve as the iterator and implements java.util.Iterator<T>. This class will somehow need to be constructed so that it ties in to the original list. It might make sense to have this be an inner class of BoundedList.
• Add a method iterator() to your BoundedList class, which returns a new instance of our iterator class. With this method, your BoundedList should be able to implement Iterable<T> in addition to the List<T> interface which it should already implement.