VECTORS

1. Overview
2. Example program
3. Vectors of objects

1. OVERVIEW

From the work on arrays we have seen that we usual declare the size of the array prior to run time. Using the dynamic array concept we can of course delay this declaration till run time, but the size of the array is always fixed once it has been declared. An alternative data structure, known as a vector, will allow for data items to be stored in an array like structure but without having to declare its length. On declaring a vector we specify an initial size which is automatically doubled whenever we run out of space.

The Java API includes a class vector contained in the java.util package (Figure 1).

The idea behind vectors is similar to the concept of flexible arrays found in some early imperative languages (for exsample Algol'68), although it is not found in more recent imperative languages such as Ada or C. Flexible arrays are essentially arrays that can be "resized" during runtime, thus not quite the same thing asd vectors which have both a capcity and a size (more on this in the following section).

Figure 1: Vector class diagram.

2. EXAMPLE

The vector example given in Table 1 does the following:

Creates an instance of the class Vector.
Loads the newly created vector with a sequence of even numbers from 0 to 38, and then trims and outputs the vector.
Finds the index of the first element equal to the number 10.
Changes the elements at indexes 9, 13, 19 and 20 to the number 10.
Finds all indexes of elements equal to the number 10
Adds the element 40 to the vector and outputs the result.
Removes elements at index 7 and 17, and outputs the result.
Removes all elements equivalent to 10, and outputs the result.
Adds a given integer to all the elements in the indicated vector.

// VECTOR EXAMPLE
// Frans Coenen
// 10 February 2000, revised 16 September 2000
// Dept Computer Science, University of Liverpool

import java.util.*;
// import java.io.*;

class VectorExample{

    // ------------------- FIELDS ------------------------ 
    
    private static final int INITIAL_SIZE = 4;
    private static final int INDEX_MAXIMUM = 20;  
    private static Vector myVector;     
		      
    // ------------------ METHODS ------------------------  
    
    /* Main method */
    
    public static void main(String[] args) /* throws IOException */ {
        int n1, n2;
                   
	// Crerate an instance of the class Vector
	
	myVector = new Vector(INITIAL_SIZE);
	
	// Load vector with sequence of even numbers from 0 to 40, 
	// trim and output vector
	
	loadVector();
	trimVector();
	outputVector();
	
	// Find the index of the first elment equal to the number 10
	
	indexOf(10);
	
	// Change element at indexes 9, 13, 19 and 20 to the number 10
	
	changeElement(9,10);
	changeElement(13,10);
	changeElement(19,10);
	changeElement(20,10);
	
	// Find all indexes of element equal to the number 10
	
	indexesOf(10);
	
	// Add another element to vector and output
	
	addToVector(40);
	outputVector();
	
	// Remove elements at index 7 and 17, and output
	
	removeElementAtIndex(7);
	removeElementAtIndex(17);
	outputVector();
	
	// Remove all elements equivalent to 10 and output
	
	removeAllElements(10);
	outputVector();
	
	// Add 10 to all elements
	
	addToAllElements(10);
	outputVector();
	}
	
    /* LOAD VECTOR: Load vector method */
    
    public static void loadVector() {
        System.out.println("LOAD VECTOR");
	
	// Loop
	
	for (int index=0;index < INDEX_MAXIMUM;index++) {		             
            myVector.addElement(new Integer(index*2));
	    System.out.println("(" + index + ") Element = " + myVector.elementAt(index).toString() + 
	    		", Capacity = " + myVector.capacity() +
			", Size = " + myVector.size());
	    }
	}
	
    /* TRIM VECTOR: trim vector method */
    
    public static void trimVector() {
        
	System.out.println("\nTRIM VECTOR");
	myVector.trimToSize();

	// Output
	
	System.out.println("Capcity = " + myVector.capacity() + ", size = " + 
			myVector.size());
	System.out.println("First Element = " + myVector.firstElement() + 
			", Last Element = " + myVector.lastElement());
    	}
	
    /* OUTPUT VECTOR: Output vector method */
    
    public static void outputVector() {
        System.out.println("\nOUTPUT VECTOR");

	// Loop
	
	for (int index=0;index < myVector.size();index++)	{	             
	    System.out.print(myVector.elementAt(index).toString() + " ");
	    }
	System.out.println();
	}
    
    /* INDEX OF: Index of given element method */
    
    public static void indexOf(int element) {
        System.out.println("\nINDEX OF");
	
        System.out.println("Index of element equivalent to " + element + " is " +
			myVector.indexOf(new Integer(element)));
	}
	
    /* CHANGE ELEMENT: Method to change element at given index with new given element */
    
    public static void changeElement(int index, int element) {
        System.out.println("\nCHANGE ELEMENT");
	
    	if (index >= 0 && index < myVector.size()) 
			myVector.setElementAt(new Integer(element),index);
        else System.out.println("Index " + index + " out of range!");
	}	
	
    /* INDEXES OF: Method to find indexes of occurances of given element*/
    
    public static void indexesOf(int element) {
	int index = 0, total =0;
	
	System.out.println("\nINDEXES OF");
	
	// Loop
	
	while (index != -1) {
	    index = myVector.indexOf(new Integer(element),index);
	    if (index != -1) {
	     	System.out.print(index + " ");
		total++;
	        index++;
		}
	    }
	     
	// End
	 
	System.out.println();
	System.out.println("Number of occurances of the element " + element +
			" is equal to " + total);
        }

    /* ADD TO VECTOR: Method to add given element to vector */
    
    public static void addToVector(int element) {
        
	System.out.println("\nADD TO VECTOR");
	
        myVector.addElement(new Integer(element));
	System.out.println("Element = " + element + 
	    		", Capacity = " + myVector.capacity() +
			", Size = " + myVector.size());
        }
    
    // Remove  element at a given index
    
    public static void removeElementAtIndex(int index) {
        
	System.out.println("\nREMOVE ELEMENT AT INDEX " + index + " (" +
			myVector.elementAt(index).toString() + ")");
	
        myVector.removeElementAt(index);
	System.out.println("Capacity = " + myVector.capacity() +
			", Size = " + myVector.size());
        }
    
    // REMOVE ALL ELEMENTS: Methid to remove all instances of a given element
    
    public static void removeAllElements(int element) {
        
	System.out.println("\nREMOVE ALL OCCURANCES OF " + element);
	
	// Loop
	
	while (myVector.removeElement(new Integer(element))) {}
	
	// End 
	
	System.out.println("Capacity = " + myVector.capacity() +
			", Size = " + myVector.size());
        }	
	
    /* ADD TO ALL ELEMENTS: Add given integer to all vector elements */
    
    public static void addToAllElements(int value) {
        int newValue;
	Integer newInt;
	
	System.out.println("\nADD INTEGER " + value + " TO ALL ELEMENTS");
	
	// Loop
	
	for (int index=0;index < myVector.size();index++)	{
	    newInt = new Integer(myVector.elementAt(index).toString());
	    newValue = newInt.intValue() + 10;
	    myVector.setElementAt(new Integer(newValue),index); 
	    }
	}	
    }

Table 1: Vector example code

Notes

In the main method we create a new isntance of the class vector. The initial size of the vector is given by the constant INITIAL_SIZE which is set to 4. Note that the instance is a static private instance of the class.

In the loadVector method elements are added to the vector using a for loop. A number of instance methods from the Vector class are used here:

void addElement(Object obj) which adds an object as the last element of the vector. Note that the argument must be an object so we use the constructor Integer(int n) from the Integer wrapper class to convert the number into an object (i.e. an instancec of the class Integer).
Object elementAt(int index): returns the element at the given index. Note that to output the returned element, which is an object, we must convert it to a string. We do this using the toString() instance method found in the AbstractCollection grandparent class of the class Vector.
int capacity() returns the current capacity of the vector. This is the number of elements the vector can hold without creating new storage to hold more elements.
int size() returns the number of elements currently in the vector (this is not neceessarily the same as the capacity).
The void trimVector() "trims" the capacity of the vector to be equal to its size. This is done using the trimToSize() method. Note that subsequent addition to the vector will cause it to grow again (initially by doubling the current size). The method also includes calls to the firstElement() and lastElement() methods in the vector class.
The outputVector() method outputs the contents of the vector by looping through it until the index equals the size of the vector as returned by the size() method. Use is also made of elementAt(int index) method to access indivaidual elements and the toString() to convert the resulting object to a string.
The following method (indexOf(int element)) uses a Vector class method of the same name to access a particular object. Note that we convert the integer input argument to be an instance of the Integer wrapper class.
The changeElement illustrates the use of the setElementAt(Object obj,int index) method which places the given ovject at the given index. This throws an IndexOutOfBoundsException if the given index is larger than the current size, so the method uses the sdiz() methid to terst whether the given index is within range.
The indexesOf(int element) method is similar to the indexOf method described earlier except that the search is started at a given index. This is facilitated by the indexOf(Object obj, int index) method. This allows us, as in this case, to count the number of occurances of a given element. Note that when we have found an element we increment the returned index by one to otherwise the same element will be found at infinitem.
The method addToVector(Object obj) serves to show that we can continue adding to the vector even though it has been "resized".
The removeElementAt removes an element from the vector at a given instance. As a result the size of the vector is reduced by one but not the capacity.
The method, removeElement, is equivalent to using indexOf(Object) as the argument to removeElementAt. If the object is not found the method returns false, otherwise true.
The final method (addToAllElements) adds a given integer to all the elements in the given vector. Note that we have to convert to vector element into an instance of class integer and then aquire the value. We could dispense with the declaration of the Integer object by writing:
```
newValue = (new Integer(myVector.elementAt(index).toString())).intValue()+10;
```

Some sample output produced by the above code is given in Table 2.

LOAD VECTOR
(0) Element = 0, Capacity = 4, Size = 1
(1) Element = 2, Capacity = 4, Size = 2
(2) Element = 4, Capacity = 4, Size = 3
(3) Element = 6, Capacity = 4, Size = 4
(4) Element = 8, Capacity = 8, Size = 5
(5) Element = 10, Capacity = 8, Size = 6
(6) Element = 12, Capacity = 8, Size = 7
(7) Element = 14, Capacity = 8, Size = 8
(8) Element = 16, Capacity = 16, Size = 9
(9) Element = 18, Capacity = 16, Size = 10
(10) Element = 20, Capacity = 16, Size = 11
(11) Element = 22, Capacity = 16, Size = 12
(12) Element = 24, Capacity = 16, Size = 13
(13) Element = 26, Capacity = 16, Size = 14
(14) Element = 28, Capacity = 16, Size = 15
(15) Element = 30, Capacity = 16, Size = 16
(16) Element = 32, Capacity = 32, Size = 17
(17) Element = 34, Capacity = 32, Size = 18
(18) Element = 36, Capacity = 32, Size = 19
(19) Element = 38, Capacity = 32, Size = 20       

TRIM VECTOR
Capcity = 20, size = 20
First Element = 0, Last Element = 38

OUTPUT VECTOR
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38

INDEX OF
Index of element equivalent to 10 is 5

CHANGE ELEMENT

CHANGE ELEMENT

CHANGE ELEMENT

CHANGE ELEMENT
Index 20 out of range!

INDEXES OF
5 9 13 19
Number of occurances of the element 10 is equal to 4

ADD TO VECTOR
Element = 40, Capacity = 40, Size = 21

OUTPUT VECTOR
0 2 4 6 8 10 12 14 16 10 20 22 24 10 28 30 32 34 36 10 40

REMOVE ELEMENT AT INDEX 7 (14)
Capacity = 40, Size = 20

REMOVE ELEMENT AT INDEX 17 (36)
Capacity = 40, Size = 19

OUTPUT VECTOR
0 2 4 6 8 10 12 16 10 20 22 24 10 28 30 32 34 10 40

REMOVE ALL OCCURANCES OF 10
Capacity = 40, Size = 15

OUTPUT VECTOR
0 2 4 6 8 12 16 20 22 24 28 30 32 34 40

ADD INTEGER 10 TO ALL ELEMENTS

OUTPUT VECTOR
10 12 14 16 18 22 26 30 32 34 38 40 42 44 50

Table 2: Sample output generate from vector example code given in Table 1

3. VECTORS OF OBJECTS

Suppose we have a class Node and a number of instances of the class node1, node2 ... nodeN which we wish to stor in a vector data structure called myVector (an instance of the class Vector). We would create the myVector instance in the normal way:

Vector myVector = new Vector(INITIAL_SIZE);

and allocate the instances as follows:

myVector.addElement(node1);
myVector.addElement(node2);
...
myVector.addElement(nodeN);

To retreive the data we would use a statement of the Vector class instance method:

myVector.elementAt(index1);

This will return a reference to an instance of the class object; the parent of all Java classes. Consequently, if we had an instance method in the Node class called outputNode() we could not write:

myVector.elementAt(index1).outputNode();

because, as far as Java is concerned, we have an instance of the class Object and there is no such method in that class. To use the method outputNode we must cast the reference to the assumed object instance so that it becomes an instance of the class Node. Thus:

Node myNode = (Node) myVector.elementAt(index1);

now we can use the outputNode() method:

myNode.outputNode();






Created and maintained by
Frans Coenen.
Last updated 17 September 2000

VECTORS

CONTENTS

1. OVERVIEW

2. EXAMPLE

3. VECTORS OF OBJECTS