Session X2: Vectors

As you've seen, arrays provide a useful mechanism for collecting different pieces of information and working with the collection. In particular, arrays let you create collections of a specified size, add and remove elements, and refer to elements by number (the index in the array). Arrays provide homogeneous collections: all the elements in an array are of the same type. For example, although you can have an array of ints and an array of floats, you cannot have an array that contains both ints and floats.

In Experiment X2.1 you will investigate what happens when you try to treat arrays as heterogeneous structures.

Vectors

What are the disadvantages of arrays? We've already seen one. Arrays are homogeneous. What if we want a heterogeneous collection, one in which different elements can have different types? It will be difficult to use arrays for such cases.

But even if we want to collection only one type of information, there are drawbacks to using arrays. In particular, arrays require you to prespecify the capacity, the number of elements you expect to use. A programmer who is not sure how much space to specify runs the risk of wasting memory by overspecifying the capacity or of running out of space by underestimating the needed capacity. How does one get around this? Traditionally, programmers use dynamic data structures, which are data structures whose size can change dynamically while the program is running.

Java includes a number of common programming structures as utility classes for the language. One of these, java.util.Vector, is a dynamic data structure quite similar to arrays, but which can grow dynamically. (For a comment on the term ``vector'', see the notes.) Like arrays, vectors permit you to add and look up elements and to refer to elements by number.

What methods do vectors provide?

• The size() method gives the number of elements in the vector.
• The capacity() method gives the current capacity of the vector, the number of elements that can be stored in the vector before the vector needs to grow further; vectors often grow in chunks.
• The addElement(element) method adds an element at the end of the vector, expanding the vector if necessary.
• The elementAt(position) method gets the element at a particular position in the vector. The position should be less than the size of the vector.
• The setElementAt(element,position) method replaces an element in the vector. The position must be nonnegative and less than the size of the vector. For example, if the size is 5, the position can be 0, 1, 2, 3, or 4.
• The removeElementAt(position) method removes an element from the vector, shifting the remaining elements down one position. This also shrinks the size of the vector by 1.

How do vectors differ from arrays?

• Arrays are a fixed size; vectors grow dynamically as elements are added to them.
• Arrays are homogeneous; vectors are heterogeneous: one vector can store a variety of types of objects.
• Vectors can store only objects; arrays can also store primitive values.
• Arrays provide a default initial value for each element, based on the type (normally 0 for numeric types and null for objects); vectors do not.
• Arrays permit gaps: you can assign to the third element of an array without first assigning to the second element; vectors do not permit gaps: in order to assign a value to the nth element, you must first assign values to the 0th, 1st, 2nd, 3rd, ..., n-1st element.
• The elements in an array do not move; the elements in a vector may shift as other elements are deleted. This shifting is necessary to prevent gaps.

The first two attribute are perhaps the most important. When you create an array, you must know in advance how much space you'll need and what you'll be storing in it. When you create a vector, you can let it grow as the needs of the program dictate, and store whatever is appropriate.

In Experiment X2.2, you will study the basic operations on vectors. In Experiment X2.3, you will consider some of the limits and limitations of vectors.

Other vector capabilities

Vectors also provide a number of methods that are not immediately available for arrays (but that you could probably implement if called upon to do so). These special methods include:

• The contains(element) method, which determines whether a vector contains a particular element.
• The indexOf(element) method, which returns the first index of an element equal to the specified element. If the element is not in the vector, this method returns -1.
• The removeElement(element) method, which removes an element from the vector.

As you can tell, such methods are useful when you want to get information about the collection. For example, if we built a collection of students (e.g., for a class list), we might want to check whether a particular student is in that collection. In effect, these are similar to the methods provided by java.util.Hashtable, except that there is not a separate key for each value. In some situations, it makes more sense to build a table of objects without creating separate keys.

For example, here is a class used to implement a list of students enrolled in a particular course.

import java.util.Vector;
import Student;

/**
 * A list of students enrolled in a particular course.  Developed as
 * an illustration of a use of vectors.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of January 1999
 */
public class ClassList {
  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /** The members of the class.  */
  protected Vector members;

  /** The name of the class.  */
  protected String name;


  // +--------------+--------------------------------------------
  // | Constructors |
  // +--------------+

  /**
   * Build a new class list, specifying the name of the class.
   */
  public ClassList(String name) {
    this.name = name;
    this.members = new Vector();
  } // ClassList(String)


  // +-----------+-----------------------------------------------
  // | Modifiers |
  // +-----------+

  /**
   * Add a student to the class list.  Does not add a student
   * who is already in the class.
   */
  public void addStudent(Student student) {
    if (this.members.contains(student)) {
      // Already in the class, do nothing.
    }
    else {
      this.members.addElement(student);
    }
  } // addStudent(Student)

  /**
   * Remove a student from the class.  
   */
  public void removeStudent(Student student) {
    this.members.removeElement(student);
  } // removeStudent(Student)

  /**
   * Set the grade of a student in the class.
   */
  public void setGrade(Student student, int grade) {
    // Look up the index of the student.
    int index = this.members.indexOf(student);
    // Declare a member of the class.
    Student member;

    // Did we find the student?
    if (index != -1) {
      member = (Student) this.members.elementAt(index);
      member.setGrade(grade);
    } // if the student is in the class
  } // setGrade(Student, int)


  // +------------+----------------------------------------------
  // | Extractors |
  // +------------+

  /**
   * Get the grade assigned to a particular student.  Returns
   * -1 if there is no such student in the class.
   */
  public int getGrade(Student student) {
    // Look up the index of the student.
    int index = this.members.indexOf(student);
    // Declare a member of the class.
    Student member;

    // Did we find the student?
    if (index != -1) {
      member = (Student) this.members.elementAt(index);
      return member.getGrade();
    } // if the student is in the class
    else { // the student is not in the class
      return -1;
    } // the student is not in the class
  } // getGrade(Student)

  /**
   * Generate a string listing the members of the class.
   */
  public String toString() {
    return this.name + ": " + this.members.toString();
  } // toString()

} // class ClassList

Note that most of these methods were relatively trivial to write, as they could rely on the corresponding methods in java.util.Vector. The most complex methods are setGrade and getGrade. It may seem odd that each is passed a Student, and then modifies or uses a different Student. However, the Student passed as an argument is used only to match the student record stored in the class list. Success in finding the actual student depends on the operation of the equals method of the Student class.

The following is the corresponding class used to implement the students in the course.

/**
 * A record for a student in a particular class.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of January 1999
 */
public class Student {
  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /** The student's first name. */
  protected String firstName;

  /** The student's last name.  */
  protected String lastName;

  /**
   * The student's current grade.  Set to -1 if the student does
   * not have a grade.
   */
  protected int grade;


  // +--------------+--------------------------------------------
  // | Constructors |
  // +--------------+

  /**
   * Create a new student record.
   */
  public Student(String firstName, String lastName) {
    this.firstName = firstName;
    this.lastName = lastName;
    this.grade = -1;
  } // Student(String)


  // +-----------+-----------------------------------------------
  // | Modifiers |
  // +-----------+

  /**
   * Set the grade of a student.
   */
  public void setGrade(int newgrade) {
    this.grade = newgrade;
  } // setGrade()


  // +------------+----------------------------------------------
  // | Extractors |
  // +------------+

  /**
   * Determine if this student is the same as another student.
   * Relies on names to make this determination.  (It may also
   * be appropriate to rely on identification number or something
   * else.)
   */
  public boolean equals(Student other) {
    return (this.firstName.equals(other.firstName) &&
            this.lastName.equals(other.lastName));
  } // equals(Student)

  /**
   * Determine if this student is the same as another object.
   * That object must be a student.
   */
  public boolean equals(Object other) {
    if (other instanceof Student) {
      return this.equals((Student) other);
    }
    else {
      return false;
    }
  } // equals(Object)

  /**
   * Get the grade assigned to the particular student.  Returns
   * -1 if the student does not yet have an assigned grade.
   */
  public int getGrade() {
    return this.grade;
  } // getGrade()

  /**
   * Generate a string giving the name of the student.
   */
  public String toString() {
    return this.firstName + " " + this.lastName;
  } // toString()

} // class Student

In Experiment X2.4, you will test these new methods. In Experiment X2.5, you will use and modify the ClassList and Student classes.

Determining the class of vector elements

Vectors are heterogeneous. This means that each element of the vector may have a different class. This isn't really a problem if all one needs to do is print elements, or find elements, in which case we know the type. What if you don't know the type of an element, and want to do different things depending on the type? For example, let's consider how one might scan through the elements of a vector, capitalizing the strings and resetting each date to the first of the month. In pseudocode, this is not difficult.

  for i = 0 to the number of element in the vector
    e = vec.elementAt(i)
    if e is a string, then
      vec.setElementAt(e.toUpperCase(), i)
    else if e is a date, then
      vec.setElementAt(makeNewDate(e), i)

How does one write this in Java? Fortunately, Java includes an instanceof operator that does the same thing as ``is a'' in the pseudocode above.

The following is the Java equivalent.

    int i; // A counter
    String s; // A string in the vector
    SimpleDate d; // A date in the vector
    for(i = 0; i < vec.size(); ++i) {
      // Replace each string by its uppercase equivalent
      if (vec.elementAt(i) instanceof String) {
        s = (String) vec.elementAt(i);
        vec.setElementAt(e.toUpperCase(), i);
      } // it's a string
      // Replace each date by the first of he month
      else if (vec.elementAt(i) instanceof SimpleDate) {
        d = (SimpleDate) vec.elementAt(i);
        vec.setElementAt(new SimpleDate(d.getYear(), d.getMonth(), 0), i);
      } // it's a date
    } // for

Note that we were able to cast the elements of the vector, just as we can cast primitive types. What happens if we cast elements incorrectly? You will explore that further in Experiment X2.6.

Storing primitive values in vectors

We've seen that it's possible to use vectors to store a wide variety of objects, including strings, dates, and student records. What if we want to store primitive types, such as int, float, or boolean. It turns out that vectors can only store objects, and not primitive types.

What if we'd like to create a collection of numbers, characters, or boolean values? One option would be to implement our own IntVector, CharVector, and such. However, this will be time consuming, and the resultant classes will not be heterogeneous.

Fortunately, Java provides a solution to our problem. For every primitive type, there is a corresponding class. These primitive classes include java.lang.Integer (for int), java.lang.Byte, java.lang.Short, java.lang.Long, java.lang.Float, java.lang.Double, java.lang.Character (for char), and java.lang.Boolean. Because they are part of the java.lang package, you do not need to explicitly import these classes.

How do you create one of these objects? You pass in the corresponding value. For example, to create the Integer with value 1, you could use new Integer(1). Similarly, to create the Character with value 'z', you would use new Character('z').

How do you extract the primitive values from these types? For the Character class, you can use the charValue method. For example

    Character charobj;
    char ch;
    ...
    ch = charobj.charValue();

For the Boolean, you can use the booleanValue method. For all of the numeric types, you can use of one byteValue, shortValue, intValue, longValue, floatValue, or doubleValue. You can also use these methods to convert between types (e.g., to get a long from a Double).

You will work with these primitive objects in Experiment X2.7.