CSCI 151 Lab 4: Vector and Dictionary

Overview

This lab will give you more experience working with Vectors, and experience working at multiple levels of abstraction. We will start by improving our Vector class, and then use our improved Vectors to create a better Dictionary.

Materials

Setup

Download Vector-generic.java, Dictionary-generic.java, and Association-generic.java.
Rename the files you downloaded to get rid of -generic. For example, you should rename Vector-generic.java to Vector.java.
Create a new project in Eclipse called Lab04 (or something similar; really it does not matter what you call it).
Now copy Vector.java, Association.java, and Dictionary.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”. Do not simply drag them into your workspace folder using Explorer/Finder, since then Eclipse does not know about them.

Part 1: extending `Vector`

Your first assignment is to add more useful methods to Vector. In particular, you should add each of the following methods:

public int indexOf(E elt): returns the index of the first occurrence of element elt in the Vector. If no element of the Vector is equal to elt, it should return -1 instead.
public E find(E elt): finds the first element which is equal to elt and returns it. This may seem pointless, 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 code you have already written.
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 Vector.

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 Vector<E>. To implement it, you should simply cast other to the type Vector<E>. If anyone calls equals with something other than a Vector, 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 Vector, you should just assume that other is an Association and cast it appropriately.

Part 3: A better dictionary

Finally, we will use the improved Vector and Association classes to build a better Dictionary.

First, modify the add method so that it works as we discussed in class:
- First, it checks to see whether the given key already exists in the dictionary.
- If so, it just updates the existing Association to have the new value.
- Otherwise, it adds a new Association to the end of the Vector.
To make this more interesting, you should implement add without using 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).)
Finally, rewrite hasKey as well. The new implementation should not have any loops; in fact, it can be as short as a single line of code.

What to Hand In

You should turn in

Vector.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.