Collections

Due Date: Sun, March 26th by 11:59PM 2 day extension!

This assignment involves creating a number of Java classes, each of these classes will be tested independently. Feel free to include your own test code, but keep in mind that we will write our own test code! Make sure that you use the exact class names listed below - if you don't we won't be able to test your code and you will get a crummy grade!

You need to create a class named MyList that implements the old-style Collections interface java.util.List Your list should be similar to ArrayList, in that it stores list elements in a java array (array of Objects). Make sure your class implements the correct interface, do not implement the (new and improved) interface List<E>. Here is some sample code that could be a start towards testing your MyList class:

import java.util.Random;
import java.util.Iterator;

public class testMyList {
  public static void main(String [] args ) {

        MyList x = new MyList();

        // Populate with 10 random Integer objects
        Random r = new Random();

        for (int i=0;i<10;i++) {
          x.add( new Integer(r.nextInt(100)));
        }

        // print using random access (get)
        for (int i=0;i<x.size();i++) {
          System.out.println("x[" +i+ "] = " + x.get(i));
        }

		// create another list - this one to hold strings
		x = new MyList();

		x.add("Hello");
		x.add("another item for you");
		x.add("there are lots of funny strings");
		x.add("but none of them are here");

        // print all elements of x using iterator
        Iterator i = x.iterator();

        while (i.hasNext()) {
          System.out.println( i.next());
        }

  }

IMPORTANT!!! At first glance the appears to be a significant amount of work. The List interface includes something like 25 different methods that must be implemented! However, most of the work has already been done for you in the abstract class named java.util.AbstractList. Use this as the basis for MyList (have MyList extend AbstractList). Make sure you read the API documentation for java.util.AbstractList to know what you need to do when extending this abstract class. Note that MyList must be a modifiable, variable sized list, so you will need to provide an implementation of each of the following methods:

• get(int index)
• size()
• set(int index, Object element)
• add(int index, Object element)
• add(Object element)
• remove(int index)

The abstract class AbstractList provides everything else, including support for an Iterator.

NOTES:

• You must use an array to store your list elements, you are not allowed to use any of the collections classes (you can't use an ArrayList, TreeList, Vector or any other java Object to do the work for you!)

• Your array needs to be able to grow to accomdate as many elements as are added to the list. You will find the static method java.lang.System.arraycopy useful.

• Don't worry about the compiler warnings that indicate that you are using the old API ("unchecked or unsafe operation")

• don't settle for the test code above, try lots of things (we will), including using the static methods in java.util.Collections for things like sorting and searching.

Create a class named MyBackwardsList that also implements the List interface, but whose Iterator moves backwards through the list. To do this you need to create a class that implements the interface Iterator (once again, not Iterator<E>!). Your iterator must support the methods hasNext(), next(), and remove().

If you want to create a nested class for this, feel free (but this is not required, we have not yet talked about this). The Iterator class you need to write can be a top-level class, it needs to have a reference to the array in which you store elements, and the ability to move backwards through the list. You can assume the only changes to the list (while iterating) are through the Iterator remove method (you don't need to worry about multi-threaded application, or even that the code using your iterator will make structural changes to the list while iterating.)

Here is a bit of sample code you could use to test your backwards list class:

public static void main(String [] args ) {

        MyList x = new MyList();

        // Populate with 10 random Integer objects
        Random r = new Random();

        for (int i=0;i<10;i++) {
          x.add( new Integer(r.nextInt(100)));
        }

        // print all elements of x using iterator
        Iterator i = x.iterator();

        while (i.hasNext()) {
          System.out.println( i.next());
        }

        List y = new MyBackwardsList();
        for (Object e : x)
          y.add(e);

        // print all elements of x using iterator
        Iterator j = y.iterator();

        while (j.hasNext()) {
          System.out.println( j.next());
        }
  }

NOTES:

• Make your MyBackwardsList class an extension of your MyList class!. If you do this, the only things you need to write are the iterator() method and the constructor.

• Remember that in Java, everything except primitive type are references. This means that if you do this something like this:

  Object foo[] = blah;

  foo is a reference to the same array as blah (changes made to blah are also changes made to foo). Your iterator does not want to make a new copy of the array you use to implement your list, just a reference to that array.

This exercise involves the use of maps, there are no requirements as to whether you use the old style (Map) or the new style (Map). Feel free to use composition (your class has a map object it uses) or inheritence (your class is a map, by extending a concrete class such as HashMap or TreeMap).

Write a class named JavaGrades that can be used to keep track of student grades for one assignment. Your class must support the following operations:

void assign(String studentName, int grade);

assign should record the grade for the named student. If there already is a grade recorded for the student, the old grade should be replaced by the new one.

int lookup(String studentName);

lookup should return the currently recorded grade for the student, or 0 if there is no grade currently recorded.

void printByName();

printByName should print out a list of the student names and grades (one student name and grade per line) ordered alphabetically by name (ascending order).

printByGrade should print out a list of the student names and grades (one student name and grade per line), ordered numerically from the highest grade to the lowest.

Your JavaGrades class does not need to have a main method, but feel free to include one. We will write our own to test your class.

Submit to WebCT dropbox for HW4. Make sure all your code is commented with JavaDoc comments!