M/F 2:30-3:20   
in Philips 101

CS 1130: Transition to OO Programming

Spring 2015

Vector Exercises

There is a PDF version of these instructions, if you would prefer to have that instead.

Class java.util.Vector provides the ability to maintain a growable/shrinkable list of objects, which can be of great utility in cases where you do not know ahead of time how many objects will be in the final list. The purpose of this lab is to gain some experience with class Vector and learn just how useful it can be.

Requirements For This Lab

The very first thing that you should do in this lab is to download the file VisualVector.java. You will note that this is a subclass of JFrame. That is because, instead of a JUnit test, we are going to use a GUI program to help you "test" the lab. The GUI will give you a visual representation of the changes that you make to the class.

Within VisualVector.java you will notice several function (and procedure) stubs. They stand out because they have the comments


        //-------- IMPLEMENT ME! --------//
in their method bodies. As with the last lab, you will be filling in code here.

For this lab you will show your instructor the contents of VisualVector.java and what you have written on this sheet; there is no JUnit test this time. As always, you should try to finish the lab during your section. However, if you do not finish during section, you have until the beginning of lab next week to finish it. You should always do your best to finish during lab hours; remember that labs are graded on effort, not correctness.


Understanding the Vector Class

The material in this lab is covered in Section 5.3 (pp. 184-188) of the text. After the lab, you should study that section.

Basic Terminology

A Vector v contains a list of elements, numbered 0, 1, 2, …. The function v.size() tells how many elements are in the list.

We use the following non-Java notation to refer to parts of the list. The notation helps us write things more clearly and succinctly. We refer to the elements in the list as v[0], v[1], …, v[v.size()–1]. We refer to part of the list, say elements v[h], v[h+1], …, v[k], using v[h..k]. We also write v[h..] to mean v[h], v[h+1], …, v[v.size()–1].

As Vector is a generic class, we use the following assignment statement to create a Vector that can contain only elements of the class C, and store the name of this Vector in \texttt{v}:


    Vector  v = new Vector();
The appearance of <C> says that the Vector may contain only elements of class C. In this lab, we will be working with Vector<Character>, meaning a Vector whose elements are of class Character.

Finally, Vector whose name is in v has a capacity, which is the number of elements for which space in the computer memory has been allocated. This is different from its size, which is the number of elements in it. When an element is to be added to v but the size is already equal to the capacity, Java allocates space for more elements (for efficiency reasons, the capacity is usually doubled). The capacity can also be controlled by the programmer, and it os sometimes possible to save memory or make a program a little faster in this way (though you should never worry about this).

The Vector API

For this lab, you will need to make use of methods that are found in the Vector API. We highly recommend that you follow this link, and that you do not Google for the Vector API. For historical reasons (see below), the top Google link is to the Java 1.4.2 version of Vector. There have been a lot of changes to this class over the years and it is important that you only look at the API for the current (for this course, Java 1.6) version of Vector.

Remember from class that Vector is a generic class. That means that its type is specified by what it contains, which is put inside ``angled brackets'' (e.g. <, >). On the API page for Vector, you will notice that it puts the letter E in the angled brackets and then uses E as a type through the web page. The way to read this page is to place the letter E with whatever you have put in your angled brackets (which for this lab is the class Character).

In this class, we will use a small subset of the API. For your convenience, here are the important methods:

Method Description
v.add(E ob) Append ob to v’s list. If v’s type is class Vector<C>, ob should be of class C or a subtype of C.
v.add(int k, Object ob) Change v’s list to v[0..k-1], ob, v[k..]. If v’s type is class Vector<C>, ob should be of class C or a subtype of C.
v.get(int k) Yields: v[k]
v.remove(E ob) Remove ob from the list in v (if it is there)
v.remove(int k) Remove v[k] from v’s list, changing it to v[0..k-1], v[k+1..]
v.clear() Remove all elements from v
set(int k, E ob) Replace v[k] by ob
v.size() Yields: the number of elements in v’s list
v.capacity() Yields: the number of elements that are currently allocated for v’s list —this can be different from the number of elements that are actually IN v’s list!
v.indexOf(E ob) Yields: i, where v[i] is the first occurrence of ob in the list
v.lastIndexOf(E ob) Yields: i, where v[i] is the last occurrence of ob in the list
v.toString() Yields: a comma-separated list of the elements in v, enclosed in brackets

A History Lesson

The developers of Java knew early on that they wanted some kind of growable list, so they created class Vector and shipped it out with Java v1.0. Later, however, they wanted to generalize the idea of a list. So they created new classes that provide a more general implementation than Vector.

Rather than get rid of Vector (for "backward compatability" reasons, you cannot simply throw out old stuff), the developers of Java v1.2 added new methods to class Vector so that it would be consistent with the other, newer, classes. Many of these new methods do the same thing as the old ones. This is why you will see some methods in the documentation for the Vector class that seem redundant — they are.

Another major change happened in Java 1.5. This is the first version of Java to support generic classes. Before then, Vector to only hold objects whose class is Object. Since Object is the "superest" class of them all, this was not a problem. However, it made programming with Vector much, much harder for beginners. That is why it is important that you do not use any API for Vector that is older than Java 1.5.


Experimenting with Vector

Once you have downloaded VisualVector.java, you should first play with it a bit. We have already provided you with quite a bit of code there, and this code is intended to make the lab a bit more interesting. In particular, this is some of the first GUI code that we have seen in this course.

Look over the code that we have provided. We have defined a Vector<Character> v, which you will use throughout this lab. You can access it from the Interactions pane of DrJava. We have also defined two constructors, which will illustrate different qualities of Vector. Read the specifications so you understand what each one does (according to the Vector API, the capacity increment is the amount by which the capacity of the vector is automatically incremented when its size becomes greater than its capacity).

Do not worry about the stubbed-in methods yet (the ones you have to write); you will get to them later.

Working with VisualVector

Compile the class VisualVector and type this into the Interactions pane:


  VisualVector lab = new VisualVector();
A window should appear at the top of your screen containing a drawing of numbered boxes. This drawing represents Vector<Character> object v in class VisualVector. Note that there are 10 empty boxes, numbered 0-9. The numbers are called the indices or indexes. You use them to refer to the objects in the boxes.

Resize your DrJava window so it does not block the representation. In the Interactions pane, type:


> lab.v.add(new Character('A'));
A Character object that wraps 'A' has been added to Vector v, and you can see it in box 0.

Now type the following:


> lab.v.remove(new Character('A'));
It is now gone from v. Note that you passed in two different objects (every time you use a new-expression it makes a new object) to the methods add and remove. Vector uses the method equals of each element v[i] of Vector v to find a match; for elements of class Character, v[i].equals(ob) yields \bf true if the character in v[i] is the same as the character in ob.

Note: As we said in class, the latest version of Java supports "boxing" which allows us to write


> lab.v.add('A');
to do the same thing as the add statement above. However, you should avoid doing this, because it is dangerous. In particular,

> lab.v.remove('A');
is very bad as Java will actually try to cast 'A' to an int (meaning an index to remove from) before it tries to box it in a Character object.

VisualVector Exercises

Type the following command to put some more objects in Vector v:


> lab.initializeV();
Look over the Vector representation in the JFrame. Note that an object can appear many times in the same list ('3' and '2' both appear twice). In the interactions pane, try the commands on the left in the table below. On the right, write down what the command returned (if anything) and what happened to the Vector representation. If you do not understand why certain commands do certain things, ask!

Tip 1: Use the up arrow key to get your previous command instead of repeatedly typing in "new Character….

Tip 2: Make sure you ae watching the Vector representation when you hit Enter to execute your commands or evaluate your expressions in the Interactions pane. It will be much easier to see what happened.

Tip 3: Make sure you leave off the semicolon when you make a function call; otherwise, you will not see not what the function returned.

Command Result/Explation
lab.v.remove(new Character('3'));  
lab.v.remove(new Character('7'));  
lab.v.indexOf(new Character('1'))  
lab.v.indexOf(new Character('B'))  
lab.v.get(5)  
lab.v.get(12)  
lab.v.indexOf(lab.v.get(2)) What is this call doing?
 
lab.v.indexOf(lab.v.get(8)) Why does this not return 8?
 
lab.v.firstElement()  
lab.v.set(1, new Character('O'));  
lab.v.capacity()  
lab.v.size()  
lab.v.toString()  
lab.v.trimToSize();  
lab.v.setSize(12); What is in the cells that have red question marks?
Is the new capacity also 12?
 

Writing Methods to Manipulate a Vector

We have written four method stubs for you to implement; implement them. As usual, we suggest you write and test the methods one at a time, thoroughly testing one before moving on to the next. However, you do not need to make a VisualVectorTester JUnit class this time. You can simply use the visual representation in the JFrame to test your code in an ad-hoc fashion. For example, after writing the swap method, try lab.swap(0,1) and see what happens in the JFrame window.

Method Description
public void swap(int first, int second) Swap the objects at v[first] and v[second]
public boolean moreThanOne(Object obj) Yields: "there is more than one occurrence of obj in v"
Hint: Does looking at the first and last occurrences of obj in v help?
public boolean hasExtraSpace() Yields: "there is space allotted to v that is not being used"
public String toString() Yields: a string that has contains the characters of v, in the order in which they occur in v.
Precondition: v may not contain commas or spaces (see the hint below).

Important: Do not use loops or recursion (if you know what they are) in this lab. Everything can be done using the methods of either Vector or String. Here is a hint for the last method: Use the existing toString of class Vector, but remove the square brackets, commas, and spaces using methods of class String. Furthermore, remove the brackets first; because of some syntax issues involving "regular expressions", you should not use the function replaceAll() on Strings containing brackets. Furthermore, this is the reason for the precondition on toString().

When you are done, show your work to your TA or a consultant.