CSCI 151 Lab 4: Extensible arrays and dictionaries

Overview

This lab will:

Give you even more experience working with arrays;
Teach you about Object methods like toString and equals; and
Give you experience working at multiple levels of abstraction.

We will start by improving our GenericExtensibleArray class, and then use our improved arrays to create a better (though not more efficient) Dictionary implementation.

Materials

Setup

Download GenericExtensibleArray.java, GenericAssociation.java, and GenericDictionary.java.
Create a new project in Eclipse called Lab04 (or something similar; really it does not matter what you call it).
Now copy GenericExtensibleArray.java, GenericAssociation.java, and GenericDictionary.java into your new Eclipse project, either by dragging and dropping them into the src package, or by right-clicking on src and choosing "Import... From File System". Alternatively, if you simply move them into the appopriate folder on your file system, go back into Eclipse and hit F5 to refresh the project view, and the new files should show up.
From now on we will make pretty much everything generic, so there is no need for the classes to actually have the word Generic in their names. To avoid a bunch of tedious find-and-replace, use Eclipse to change the name of each class to get rid of the word Generic: click on the name of the class and choose Refactor > Rename from the menu, or hit Alt + Shift + R.

Part 1: extending `ExtensibleArray`

Your first assignment is to add more useful methods to ExtensibleArray. Similar methods already exist in ArrayList, and it is important for you to explore how these methods are implemented. In particular, you should add each of the following methods:

public String toString(): The Object class has a toString method which is intended to produce some sort of string representation of an object, and which is called automatically whenever an object gets converted to a string (for example, by printing it with System.out.println). The default implementation of toString simply prints out the memory address of an object---not very useful! Typically, we will override the inherited toString so that it returns a more useful string.

In particular, you should add a toString method which returns string representations of the elements of the array (using their own toString method!) separated by spaces. For example, the following code:
```
ExtensibleArray<Integer> arr = new ExtensibleArray<>();
arr.append(1);
arr.append(3);
arr.append(7);
System.out.printn(arr);
```
should produce the output
```
1 3 7
```
Be sure to put an @Override annotation on the line before the toString method, to indicate that we are overriding an inherited method.
public int indexOf(E elt): returns the index of the first occurrence of element elt in the ExtensibleArray. If no element of the ExtensibleArray is equal to elt, it should return -1 instead. (Remember to use .equals to test for equality, not ==!)
public E find(E elt): finds the first element which is equal to elt and returns it. This may seem pointless (why return an element when we already know what it is?), but the purpose will become clearer in the next few sections.

Hint: your implementation of find should only be one or two lines long, if you make use of indexOf.
public E removeElementAt(int index): delete the element at index, and return the element that was deleted. "Delete" means to shift all the following elements over by one position. For example, this code:
```
System.out.println(v);
v.removeElementAt(3);
System.out.println(v);
```
might produce this output:
```
1 3 17 25 0 9 8
1 3 17 0 9 8
```
public void remove(E elt): delete the first occurrence of an element which is equal to elt. For example, this code:
```
System.out.println(v);
v.remove(3);
System.out.println(v);
```
might produce this output:
```
1 3 17 25 0 3 8
1 17 25 0 3 8
```
Hint: again, this method should only be a few lines long. Think about how to reuse functionality you have already implemented.
public void add(int index, E elt): inserts the new element elt so that it is now at index, by shifting later elements over one spot to make room. For example, this code:
```
System.out.println(v);
v.add(4, 6984);
System.out.println(v);
```
might produce this output:
```
1 3 17 25 0 3 8
1 3 17 25 6984 0 3 8
```
Notice that get or removeElementAt require an index 0 <= i < length, but add requires an index 0 <= i <= length. That is, length is a valid index for add, which corresponds to inserting an element at the very end of the ExtensibleArray.

Note also that it is allowed to have two methods named add, as long as Java can tell them apart by their arguments. Typically, methods with the same name will perform variants of the same task. In this case, add with a single argument of type E adds to the end, whereas add with int and E arguments inserts in the middle.
public boolean equals(Object other): determine whether this vector is equal to another one (by comparing all the elements). Be sure to put an @Override annotation before it. The one annoying thing about this method is that it has to take an Object instead of a ExtensibleArray<E>. To implement it, you should simply cast other to the type ExtensibleArray<E>. If anyone calls equals with something other than a ExtensibleArray, it will crash---but that's OK since no one should ever do that. In fact, it is better to have the program crash than for it to silently return false, because calling equals on objects of two different types is almost certainly a bug.

Part 2: Equality for Associations

In order to effectively look up an Association in a Dictionary, we will want to be able to compare two Associations, so we will also implement equals for them. However, we are going to do something a bit strange and just compare their keys, not their values. If we were just implementing a generic class for pairs, this would be the wrong thing to do. However, Associations are not just generic pairs: we are going to use them to store key-value associations, to implement things like dictionaries. In a key-value association, we always look things up by key, so it makes sense to only compare Associations by key.

Add a method public boolean equals(Object other) to the Association class as well. As with ExtensibleArray, you should just assume that other is an Association and cast it appropriately.

Part 3: A better dictionary

Finally, we will use the improved ExtensibleArray and Association classes to simplify the implementation of Dictionary.

First, modify the put method so that it does not use any loops. It is possible to implement it in a concise, elegant way making use of some of the things you developed in parts 1 and 2. If you are unsure how to do this, then go back and think about parts 1 and 2 again.
Now rewrite the get method of Dictionary to make use of our new tools. The new implementation of get should also not have any loops. (Hint: try making a new Association(key, null).)

What to Hand In

You should turn in

ExtensibleArray.java
Association.java
Dictionary.java

Grading

To get a D, complete three of the methods in Part 1.
To get a C, complete Part 1.
To get a B, complete Part 2.
To get an A, complete Part 3.