Main Page

Previous Next

Using Vectors

The Vector class defines a collection of elements of type Object that works rather like an array, but with the additional feature that it can grow itself automatically when you need more capacity. It implements the List interface so it can be used as a list. Because it stores elements of type Object, and Object is a superclass of every object, you can store any type of object in a Vector. This also means that potentially you can use a single Vector object to store objects that are instances of a variety of different classes. This is another advantage the Vector class has over arrays, but the circumstances where this is desirable are relatively rare.

This ability to store diverse objects has a downside. It implies that it's very easy for you to store objects in a Vector by mistake. You can set up a Vector in which you plan to store a particular kind of object, but there's nothing to prevent the storage of some other kind of object in the Vector, or to signal that this may cause problems. If you need to protect against this kind of error, you must program for it yourself. This isn't terribly difficult. As you'll see later in this chapter, all you need to do is package your Vector as a private member of a class that you define, and then supply methods to store objects in the Vector that will only accept the type that you want.

Important 

Like arrays, vectors only hold object references, not actual objects. To keep things simple we refer to a Vector as holding objects. We'll make the distinction only when it's important, but you should keep in mind that all the collection classes you're about to encounter hold object references.

Creating a Vector

There are four constructors for a Vector. The default constructor creates an empty Vector object with the capacity to store up to a default number of objects, and the Vector object will increase in size each time you add an element when the Vector is full. The default capacity of a Vector object is ten objects, and the Vector object will double in size when you add an object when it is full. For example:

Vector transactions = new Vector();      // Create an empty Vector

If the default capacity isn't suitable for what you want to do, you can set the initial capacity of a Vector explicitly when you create it by using a different constructor. You just specify the capacity you require as an argument of type int. For example:

Vector transactions = new Vector(100);   // Vector to store 100 objects

The Vector object we're defining here will store 100 elements initially. It will also double in capacity each time you exceed the current capacity. The process of doubling the capacity of the Vector when more space is required can be quite inefficient. For example, if you end up storing 7000 objects in the Vector we've just defined, it will actually have space for 12800 objects. If each object reference requires 4 bytes, say, you'll be occupying more than 20 kilobytes of memory unnecessarily.

One way of avoiding this is to specify the amount by which the Vector should be incremented as well as the initial capacity when you create the Vector object. Both of these arguments to the constructor are of type int. For example:

Vector transactions = new Vector(100,10);   

This Vector object has an initial capacity of 100, but the capacity will only be increased by 10 elements each time more space is required.

Note 

Why don't we increment the Vector object by 1 each time then? The reason is that the process of incrementing the capacity takes time because it involves copying the contents to a new area of memory. The bigger the vector is, the longer the copy takes, and that will affect your program's performance if it happens very often.

The last constructor creates a Vector object containing object references from another collection that is passed to the constructor as an argument of type Collection. Since all the set and list collection classes implement the Collection interface, the constructor argument can be of any set or list class type, including another Vector. The objects are stored in the Vector object that is created in the sequence in which they are returned from the iterator for the Collection object that is passed as the argument.

Let's see a vector working.

Try It Out – Using a Vector

We'll take a very simple example here, just storing a few strings in a vector:

import java.util.*;

public class TrySimpleVector {
  public static void main(String[] args) {
    Vector names = new Vector();
    String[] firstnames = { "Jack", "Jill", "John", 
                            "Joan", "Jeremiah", "Josephine"};

    for(int i = 0 ; i<firstnames.length ; i++)
      names.add(firstnames[i]);
    for(int i = 0 ; i<names.size() ; i++)
      System.out.println((String)names.get(i));    
  }
}

If you compile and run this, it will list the names that are defined in the program.

How It Works

We copy the references to the Vector object, names, in the first for loop. The add() method adds the object to the vector at the next available position. The second for loop retrieves the String references from the vector using the get() method. This returns the reference at the index position specified by the argument as type Object, so we have to cast it to the original type, String, in the println() call. The size() method returns the number of elements in the Vector, so this is the upper limit for the second for loop. Note that the Vector object doesn't care what type of objects are added – we could pass any type of reference to the add() method, even type Vector.

The Capacity and Size of a Vector

Although we said at the beginning that a Vector works like an array, this isn't strictly true. One significant difference is in the information you can get about the storage space it provides. An array has a single measure, its length, which is the count of the total number of elements it can reference. A vector has two measures relating to the space it provides – the capacity and the size.

Click To expand

The capacity of a Vector is the maximum number of objects that it can hold at any given instant. Of course, the capacity can vary over time, because when you store an object in a Vector object that is full, its capacity will automatically increase. For example, the Vector object transactions that we defined in the last of the constructor examples earlier had an initial capacity of 100. After you've stored 101 objects in it, its capacity will be 110 objects. A vector will typically contain fewer objects than its capacity.

You can obtain the capacity of a Vector with the method capacity(), which returns it as a value of type int. For example:

int transMax = transactions.capacity();  // Get current capacity

If this statement follows the current definition we have for transactions, the variable transMax will have the value 100.

You can also ensure that a Vector has a sufficient capacity for your needs by calling its ensureCapacity() method. For example:

transactions.ensureCapacity(150);       // Set minimum capacity to 150

If the capacity of transactions is less than 150, the capacity will be increased to that value. If it's already 150 or greater, it will be unchanged by this statement. The argument you specify for ensureCapacity() is of type int. There's no return value.

Changing the Size

When you first create a Vector object, the elements don't reference anything. An element will be occupied once you've stored an object in it. The number of elements that are occupied by objects in a Vector is referred to as the size of the Vector. The size of a Vector clearly can't be greater than the capacity. As we have seen, you can obtain the size of a Vector object as a value of type int by calling the size() method for the object. For example, you could calculate the number of free entries in the Vector object transactions with the statement:

int freeCount = transactions.capacity() – transactions.size();

You usually increase the size value for a Vector indirectly by storing an object in it, but you can also change the size directly by calling a method. Using the method setSize(), you can increase and decrease the size. For example:

transactions.setSize(50);              // Set size to 50

The size of the Vector is set to the argument value (of type int). If the Vector transactions has less than fifty elements occupied, the additional elements up to fifty will be filled with null references. If it already contains more than fifty objects, all object references in excess of fifty will be discarded. The objects themselves may still be available if other references to them exist.

Looking back to the situation we discussed earlier, we saw how the effects of incrementing the capacity by doubling each time the current capacity was exceeded could waste memory. A Vector object provides you with a direct way of dealing with this – the trimToSize() method. This just changes the capacity to match the current size. For example:

transactions.trimToSize();              // Set capacity to size

If the size of the Vector is 50 when this statement executes, then the capacity will be too. Of course, you can still add more objects to the Vector as it will grow to accommodate them.

Storing Objects in a Vector

The simplest way to store an object in a Vector is to use the add() method as we did in the last example. To store a transaction in the transactions vector, you could write:

transactions.add(aTransaction);

This will add a reference to the object aTransaction to the Vector object called transactions. The new entry will be added at the end of the existing objects in the vector, and the size of the Vector will be increased by 1. All the objects that were already stored in the Vector remain at their previous index position.

You can also store an object at a particular index position in a Vector using another version of add() that has two parameters. The first argument is the index position and the second argument is the object to be stored. The index value must be less than or equal to the size of the Vector, which implies that either there is already an object reference at this position or it is the position at the end of the Vector that is next in line to receive one. The index value is the same as for an array – an offset from the first element – so you reference the first element using an index value of zero. For example, to insert the object aTransaction as the third entry of transactions, you would write:

transactions.add(2, aTransaction);

The index value is of type int, and represents the index value for the position of the new object. The new object, aTransaction, is inserted in front of the object that previously corresponded to the index value 2, so objects stored in elements with index values equal to or greater than 2 will be shuffled along, and their index values will increase by 1. If you specify an index value argument that is negative, or greater than or equal to the size of the Vector, the method will throw an ArrayIndexOutOfBoundsException.

To change an element in a vector you use the set() method. This accepts two arguments: the first argument is the index position where the object specified by the second argument is to be stored. To change the third element in the Vector object transactions to theTransaction, you would write:

transactions.set(2, theTransaction);

The method returns a reference of type Object to the object that was previously stored at this position. This gives you a chance to hang on to the displaced object if you want to keep it. If the first argument is negative, or is greater than or equal to the current size of the Vector, the method will throw an ArrayIndexOutOfBoundsException.

You can add all the objects from another collection to a vector, either appended at the end or inserted following a given index position. For instance, to append the contents of a LinkedList object, myList, to a Vector object, transactions, you would write:

transactions.addAll(myList);

The parameter to the method is of type Collection, so the objects in any list or set can be added. To insert the collection objects at a particular position, you specify the index position as the first argument. So to insert the objects in myList starting at index position i, you would write:

transactions.addAll(i, myList);

The object originally at position i, and objects originally to the right of position i, will all be shuffled to the right to make room for the new objects. If the index value passed as the first argument is negative, or is not less than the size of transactions, an ArrayIndexOutOfBoundsException object will be thrown. Adding a collection will increase the size of the vector by the number of objects added.

Retrieving Objects from a Vector

As we saw in the simple example earlier, if you have the index for an element, you can obtain the element at a particular position by using the get() method for the Vector. For the transactions vector you could write:

Transaction theTransaction = (Transaction)transactions.get(4);

This statement will retrieve the fifth element in the vector. Note that the explicit cast is essential here. If you don't cast the object returned to the type of the variable that you're using to store it, you'll get an error.

Of course, this is where an object of an incorrect type in the Vector will cause a problem. If the object returned here isn't of type Transaction, an exception will be thrown. Although you could always store it in a variable of type Object, you should always cast it to the original or most appropriate type. Note that the get() method will throw an exception of type ArrayIndexOutOfBoundsException if the argument is an illegal index value. The index must be non-negative and less than the size of the vector.

You can retrieve the first element in a Vector by using the firstElement() method, which returns the object stored as type Object. For example:

Transaction theTransaction = (Transaction)transactions.firstElement();

You can also retrieve the last element in a Vector by using the method lastElement() in a similar manner. However, a vector has a flavor of a list about it, and if you want to process the objects in your vector like a list, you can obtain an iterator.

Accessing Elements in a Vector through an Iterator

You can also obtain all the elements in a Vector object by using an Iterator object that you obtain from the Vector object. In most instances this will be the preferred way of accessing the elements in a vector. You obtain a reference to an iterator by calling the iterator() method for the Vector object:

Iterator theData = names.iterator(); 

The method iterator() returns an Iterator object that you can use to iterate through all the elements in the Vector object. You can now process them serially using the methods defined for Iterator class that we discussed earlier. For example, you could now output the elements from names in the last example we ran using the iterator:

while(theData.hasNext())
  System.out.println((String)theData.next());

This loop iterates through all the elements referenced by theData one at a time, and outputs each String object to the display. When we've retrieved the last element from the Iterator, the method hasNext() will return false and the loop will end.

You can also obtain a ListIterator reference from a vector by calling the listIterator() method:

ListIterator listIter = names.listIterator();

Now you can go backwards or forwards though the objects using the ListIterator methods that we saw earlier.

It is also possible to obtain a ListIterator object that encapsulates just a part of the vector, using a version of the listIterator() method that accepts an argument specifying the index position of the first vector element in the iterator:

ListIterator listIter = names.listIterator(2);

This statement will result in a list iterator that encapsulates the elements from names from the element at index position 2 to the end. The argument must not be negative and must be less than the size of names, otherwise an IndexOutOfBoundsException will be thrown. Take care not to mix the interface name with a capital L with the method name with a small l.

To cap that, you can retrieve an internal subset of the objects in a vector as a collection of type List using the subList() method:

List list = names.subList(2, 5);   //Extract elements 2 to 4 as a sublist

The first argument is the index position of the first element from the vector to be included in the list, and the second index is the element at the upper limit – not included in the list. Thus this statement extracts elements 2 to 4 inclusive. Both arguments to subList() must be positive, the first argument must be less than the size of the vector, and the second argument must not be greater than the size, otherwise an IndexOutOfBoundsException will be thrown.

There are lots of ways of using the subList() method in conjunction with other methods, for example:

ListIterator listIter = transactions.subList(5, 15).listIterator(2);

Here we obtain a list iterator for elements 2 to the end of the list returned by the subList()call, which will be elements 7 to 14 inclusive from the transactions vector.

Extracting All the Elements from a Vector

A Vector provides you with tremendous flexibility in use, particularly with the ability to automatically adjust its capacity. Of course, the flexibility you get through using a Vector comes at a price. There is always some overhead involved when you're retrieving elements. For this reason, there may be times when you want to get the elements contained in a Vector object back as a regular array. The method toArray() will do this for you. You would typically use the method toArray() to obtain the elements of a Vector object, transactions, as follows:

Object[] data = transactions.toArray();  // Extract the vector elements

The toArray() method returns an array of type Object containing all the elements from transactions in the correct sequence.

It may be inconvenient to have the elements returned as an array of type Object. You may need to cast each element to its proper type before using it, for instance. There is another version of toArray() that will return an array of the type that you specify as an argument. You might use this with the transactions Vector as follows:

Transaction[] data = new Transaction(transactions.size());
data = transactions.toArray(data);

We allocate sufficient space for the elements using the size() member of our Vector object. You could supply an array as an argument that has more elements than are necessary to store the contents of the Vector. In this case the extra elements will be set to null. You can also supply an array that is too small as the argument to toArray(). In this case a new array will be created of the type you specify for the argument, with sufficient space to hold all the objects from the vector.

Of course, the type of objects stored in the vector must be the same as, or a supertype of, the type of the array. If not, an exception of type ArrayStoreException will be thrown. The method will also throw an exception of type NullPointerException if you pass null as the argument.

Removing Objects from a Vector

You can remove the reference at a particular index position by calling the remove() method with the index position of the object as the argument. For example:

transactions.remove(3);

will remove the fourth reference from transactions. The references following this will now be at index positions that are one less than they were before, so that what was previously the fifth object reference will now be at index position 3. Of course, the index value that you specify must be legal for the Vector on which you're operating, meaning greater than or equal to 0 and less than its size(), otherwise an exception will be thrown. This version of the remove() method returns a reference to the object removed, so it provides a means for you to retain a reference to the object after you remove it from the vector:

Transaction aTransaction = (Transaction)transactions.remove(3);

Here we save a reference to the object that was removed in aTransaction. The cast is necessary because the reference is returned as type Object.

Sometimes you'll want to remove a particular reference, rather than the reference at a given index. If you know what the object is that you want to remove, you can use another version of the remove() method to delete it:

boolean deleted = transactions.remove(aTransaction);

This will search the vector transactions from the beginning to find the first reference to the object aTransaction and remove it. If the object is found and removed from the vector, the method returns true, otherwise it returns false.

Another way to remove a single element is to use the removeElementAt() method, which requires an argument specifying the index position for the element to be removed. This is clearly similar to the version of remove() that accepts an index as an argument, the difference being that here the return type is void.

There is also a removeAll() method that accepts an argument of type Collection, which removes elements from the collection passed to the method if they are present in the vector. The method returns true if the Vector object is changed by the operation, that is, at least one element was removed. You could use this in conjunction with the subList() method to remove a specific set of elements:

transactions.removeAll(transactions.subList(5,15));

This will remove elements 5 to 14 inclusive from the Vector object transactions, plus any duplicates of those objects that are in the vector.

The retainAll() method provides you with a backhanded removal mechanism. You pass a reference of type Collection as the argument to the method that contains the elements to be retained. Any elements not in the collection you pass to the method will be removed. For instance, you could keep the elements at index positions 5 to 15 and discard the rest with the statement:

transactions.retainAll(transactions.subList(5,15));

The method returns true if the Vector has been changed – in other words if at least one element has been removed as a result of the operation. The method will throw an exception of type NullPointerException if the argument is null.

If you want to discard all the elements in a Vector, you can use the clear() method to empty the Vector in one go:

transactions.clear();     // Dump the whole lot

With all these ways of removing elements from a Vector, there's a lot of potential for ending up with an empty Vector. It's often handy to know whether a Vector contains elements or not, particularly if there's been a lot of adding and deleting of elements. You can check whether or not a Vector contains elements by using the isEmpty() method. This returns true if a Vector object has zero size, and false otherwise.

Note 

Note that a Vector may contain only null references, but this doesn't mean the size() will be zero or that isEmpty() will return true. To empty a Vector object you must actually remove the elements, not just set the elements to null.

Searching a Vector

You can get the index position of an object stored in a Vector by passing the object as an argument to the method indexOf(). For example, the statement

int position = transactions.indexOf(aTransaction);

will search the Vector from the beginning for the object aTransaction using the equals() method for the argument, so your class needs to have a proper implementation of equals() for this to work. The variable position will contain either the index of the first reference to the object in transactions, or -1 if the object isn't found.

You have another version of the method indexOf() available that accepts a second argument that is the index position where the search for the object should begin. The main use for this arises when an object can be referenced more than once in a Vector. You can use the method in this situation to recover all occurrences of any particular object, as follows:

int position = -1;                                   // Search starting index
while(++position<transactions.size()) {              // Search with a valid index
  if(position = transactions.indexOf(aTransaction, position))<0) // Find next
    break;
  // Code to process the object in some way...
}

The while loop will continue as long as the method indexOf() returns a valid index value and the index doesn't get incremented beyond the end of the Vector.

Click To expand

Each iteration will search transactions from the element given by the index stored in the variable position. The initial value of -1 is incremented in the while loop condition, so on the first iteration it is 0. On subsequent iterations where indexOf() finds an occurrence of aTransaction, the loop condition increments position to the next element ready for the next search. When no further references to the object can be found from the position specified by the second argument, the method indexOf() will return –1 and the loop will end by executing the break statement. If aTransaction happens to be found in the last element in the Vector at index position size-1, the value of position will be incremented to size by the loop condition expression, so the expression will be false and the loop will end.

Applying Vectors

Let's implement a simple example to see how using a Vector works out in practice. We will write a program to model a collection of people, where we can add the names of the persons that we want in the crowd from the keyboard. We'll first define a class to represent a person:

public class Person {
  // Constructor
  public Person(String firstName, String surname) {
    this.firstName = firstName;
    this.surname = surname;
  }

  public String toString() {
    return firstName + " " + surname;
  }

  private String firstName;    // First name of person
  private String surname;      // Second name of person
}

The only data members are the String members to store the first and second names for a person. By overriding the default implementation of the toString() method, provided by the Object class, we allow objects of the Person class to be used as arguments to the println() method for output, since as you are well aware by now, toString() will be automatically invoked in this case.

Now we can define a class that will represent a crowd. We could just create a Vector object in main() but this would mean any type of object could be stored. By defining our own class we can ensure that only Person objects can be stored in the Vector and in this way make our program less prone to errors.

The class definition representing a crowd is:

import java.util.*;
class Crowd {
  // Constructors
  public Crowd() {
    // Create default Vector object to hold people
    people = new Vector();
  }

  public Crowd(int numPersons) {
    // Create Vector object to hold people with given capacity
    people = new Vector(numPersons);
  }

  // Add a person to the crowd
  public boolean add(Person someone) {
    return people.add(someone);     // Use the Vector method to add
  }

  // Get the person at a given index
  Person get(int index) {
    return (Person)people.get(index); 
  }

  // Get number of persons in crowd
  public int size() {
    return people.size(); 
  }

  // Get people store capacity
  public int capacity() {
    return people.capacity(); 
  }

  // Get an iterator for the crowd
  public Iterator iterator() {
    return people.iterator(); 
  }

  // Person store – only accessible through methods of this class
  private Vector people;    
}

We've defined two constructors for the class for illustration purposes. One creates a Vector with a default capacity, and the other creates a Vector with the capacity given by the argument. Both constructors just call the appropriate Vector constructor. You could easily add the ability to provide the capacity increment with a third constructor, if you want.

By keeping the Vector member of the class private, we ensure the only way an object can be added to the Vector is by using the add() method in the class. Since this method only accepts an argument of type Person, we can be sure that it's impossible to store elements of any other type. Of course, if you wanted to allow other specific types to be stored, an object of type Child for example, you could arrange to derive the class Child from Person, so the add() method would allow an argument of type Child, since Person would be its superclass.

The remaining methods here are just to show how simple it is to implement the equivalent of the Vector methods for our class. In each case they use the Vector method to produce the required result. Now we are ready to put together a working example.

Try It Out – Creating the Crowd

We can now add a class containing a main() method to test these classes. We'll call it TryVector:

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

public class TryVector {
  public static void main(String[] args) {
    Person aPerson;                  // A person object
    Crowd filmCast = new Crowd();

    // Populate the crowd
    for( ; ; ) {                     // Indefinite loop
      aPerson = readPerson();        // Read in a film star
      if(aPerson == null)            // If null obtained...
        break;                       // We are done...
      filmCast.add(aPerson);         // Otherwise, add to the cast
    }

    int count = filmCast.size();
    System.out.println("You added " + count +
      (count == 1 ? " person":  " people") + " to the cast.\n");

    // Show who is in the cast using an iterator
    Iterator thisLot = filmCast.iterator();  // Obtain an iterator

    while(thisLot.hasNext())    // Output all elements
      System.out.println( thisLot.next() );
  }
}

Note the two import statements at the beginning. The first is needed for the Iterator in main(). The other is used for the BufferedReader and InputStreamReader objects in the readPerson() method. Let's now add this method to the TryVector class:

  // Read a person from the keyboard
  static public Person readPerson() {
     FormattedInput in = new FormattedInput();

    // Read in the first name and remove blanks front and back
    System.out.println(
                     "\nEnter first name or ! to end:");
    String firstName = in.readString().trim();        // Read and trim a string

    if(firstName.charAt(0) == '!')                    // Check for ! entered
      return null;                                    // If so, we are done...
 
    // Read in the surname, also trimming blanks
    System.out.println("Enter surname:");
    String surname = in.readString().trim();          // Read and trim a string
    return new Person(firstName,surname);
  }

Here we read the first name followed by the surname as two separate strings, and then create the Person object that is returned. If a ! character was entered instead of a first name, null is returned by the readPerson() method signaling the end of the input. Since this method uses the FormattedInput class that we defined in Chapter 8, you need to copy the file containing the definition of this class to the same directory as the TryVector class. The readString() method that we defined in the FormattedInput class doesn't quite do what we want though. We could insist that the ! character to end the input is entered between quotes. However, it's not a very natural way to enter the data. If we could get a single character that is not alphanumeric back as a string, then that would fix the problem for us. A small tweak of the readString() method in the FormattedInput class will accommodate that:

  public String readString() {
    if(readToken()==tokenizer.TT_WORD ||  ttype == '\"' || ttype == '\'')
       return tokenizer.sval;              
    else
       return String.valueOf((char)ttype);
  }

You will recall that if you enter a string delimited by quotes, the quote character that you use is returned by the nextToken() method. If a character string is entered without quotes, then TT_WORD is returned. Thus the first if expression will be true if either of these is the case, so we return the string stored in sval. Of course, this will not include the double quote characters if they are present. Programming the method like this provides for quoted and unquoted strings, so we can enter names that contain spaces by putting them between quotes.

When a ! is entered, it is returned by the nextToken() method, so in this case we return a string containing just this character to signal to the calling program that this is the end of the input. You could use any non-alphanumeric character for this. Note that ttype is of type int so we can't pass its value directly to the valueOf() method. If we did, we would get the string representation of its numerical value.

If you've swapped this version of the method into the FormattedInput class, and placed the source files for the other classes in the same directory, you should be ready to give it a whirl. With a modest film budget, I got the output (my input is in bold):

Enter first name or ! to end:
Roy
Enter surname:
Rogers

Enter first name or ! to end:
Marilyn
Enter surname:
Monroe

Enter first name or ! to end:
Robert
Enter surname:
"de Niro"
Enter first name or ! to end:
!
You added 3 people to the cast.

Roy Rogers
Marilyn Monroe
Robert de Niro

How It Works

Here we'll be assembling an all-star cast for a new blockbuster. The method main() creates a Person variable, which will be used as a temporary store for an actor or actress, and a Crowd object filmCast, to hold the entire cast.

The for loop uses the readPerson()method to obtain the necessary information from the keyboard and create a Person object. If ! or "!" is entered from the keyboard, readPerson() will return null and this will end the input process for cast members.

We then output the members of the cast by obtaining an Iterator. As you see, this makes the code for listing the members of the cast very simple. Instead of an iterator we could also have used the get() method that we implemented in Crowd to retrieve the actors:

for(int i = 0 ; i<filmCast.size() ; i++)
  System.out.println(filmCast.get());

Sorting

The output from the last example appears in the sequence in which you enter it. If we want to be socially correct, say, in the creation of a cast list, we should arrange them in alphabetical order. We could write our own method to sort Person objects in the Crowd object, but it will be a lot less trouble to take advantage of another feature of the java.util package, the Collections class – not to be confused with the Collection interface. The Collections class defines a variety of handy static methods that you can apply to collections, and one of them happens to be a sort() method.

The sort() method will only sort lists, that is, collections that implement the List interface. Obviously there also has to be some way for the sort() method to determine the order of objects from the list that it is sorting – in our case, Person objects. The most suitable way to do this for Person objects is to implement the Comparable interface for the class. The Comparable interface only declares one method, compareTo(). We saw this method in the String class so you know it returns –1, 0, or +1 depending on whether the current object is less than, equal to, or greater than the argument passed to the method. If the Comparable interface is implemented for the class, we just pass the collection object as an argument to the sort() method. The collection is sorted in place so there is no return value.

We can implement the Comparable interface very easily for our Person class, as follows:

public class Person implements Comparable {
  // Constructor
  public Person(String firstName, String surname) {
    this.firstName = firstName;
    this.surname = surname;
  }

  public String toString() {
    return firstName + " " + surname;
  }

  // Compare Person objects
  public int compareTo(Object person) {
    int result = surname.compareTo(((Person)person).surname);
    return result == 0 ? firstName.compareTo(((Person)person).firstName):result;
  }

  private String firstName;    // First name of person
  private String surname;      // Second name of person
}

We use the compareTo() method for String objects to compare the surnames, and if they are equal the result is determined from the first names. We can't apply the sort() method from the Collections class to a Crowd object though – a Crowd is not a list since it doesn't implement the List interface. A Vector does though, so we can sort the people member of the Crowd class by adding a sort() method to the class:

class Crowd {
  // Sort the people
  public void sort() {
    Collections.sort(people);               // Use the static sort method
  }

  // Rest of the class as before...
}

We can just pass our Vector object to the sort() method, and this will use the compareTo() method in the Person class to compare members of the list.

Let's see if it works for real.

Try It Out – Sorting the Stars

You can now add a statement to the main() method in TryVector, to sort the cast members:

  public static void main(String[] args) {
    Person aPerson;                  // A person object
    Crowd filmCast = new Crowd();

    // Populate the cast
    for( ; ; ) {                     // Indefinite loop
      aPerson = readPerson();        // Read in a film star
      if(aPerson == null)            // If null obtained...
        break;                       // We are done...
      filmCast.add(aPerson);         // Otherwise, add to the cast
    }
    

    int count = filmCast.size();
    System.out.println("You added "+count +
      (count == 1 ? " person":  " people")+ " to the cast.\n");

    filmCast.sort();                 // Sort the cast

    // Show who is in the cast using an iterator
    Iterator thisLot = filmCast.iterator();  // Obtain an iterator

    while(thisLot.hasNext())         // Output all elements
      System.out.println( thisLot.next() );
  }

If you run the example with these changes, the cast will be in alphabetical order in the output. Here's what I got:

Enter first name or ! to end:
Roy
Enter surname:
Rogers
Enter first name or ! to end:
Mae
Enter surname:
West

Enter first name or ! to end:
Charles
Enter surname:
Chaplin

Enter first name or ! to end:
!
You added 3 people to the cast.

Charles Chaplin
Roy Rogers
Mae West

How It Works

The sort() method for the Crowd object calls the sort() method defined in the Collections class, and this sorts the objects in the people vector in place. Like shelling peas!

Stack Storage

A stack is a storage mechanism that works on a last-in first-out basis, often abbreviated to LIFO. Don't confuse this with FIFO, which is first-in first-out, or FIFI, which is a name for a poodle. The operation of a stack is analogous to the plate stack you see in some self-service restaurants. The stack of plates is supported by a spring that allows the stack of plates to sink into a hole in the countertop so that only the top plate is accessible. The plates come out in the reverse order to the way they went in, so the cold plates are at the bottom, and the hot plates fresh from the dishwasher are at the top.

Click To expand

A stack in Java doesn't have a spring, but it does have all the facilities of a Vector object because the class Stack is derived from the class Vector. Of course, since we know the Vector class implements the List interface, a Stack object is also a List.

The Stack class adds five methods to those inherited from Vector, two of which provide you with the LIFO mechanism, and the other three give you extra capabilities. These methods are:

Method

Description

push (Object anObject)

Pushes a reference to the object passed as an argument to the method onto the top of the stack.

pop()

Pops the object reference off the top of the stack and returns it as type Object. This removes the reference from the stack. If the stack contains no references when you call this method the EmptyStackException will be thrown.

peek()

This method allows you to take a look at the object reference at the top of the stack without popping it off the stack. It returns the reference from the top of the stack as type Object without removing it. Like the previous method, this method can throw an EmptyStackException.

search (Object anObject)

This will return an int value which is the position on the stack of the reference to the object passed as an argument. The reference at the top of the stack is at position 1, the next reference is at position 2, and so on. Note that this is quite different from referencing elements in a Vector or an array, where indexes are an offset, so they start at 0. If the object isn't found on the stack, –1 is returned.

empty()

This method returns true if the stack is empty, and false otherwise.

The only constructor for a Stack object is the default constructor. This will call the default constructor for the base class, Vector, so you'll always get an initial capacity for 10 objects, but since it's basically a Vector, it will grow automatically in the same way.

One possible point of confusion is the relationship between the top of a Stack object, and the elements in the underlying Vector. Intuitively, you might think that the top of the stack is going to correspond to the first element in the Vector, with index 0. If so you would be totally wrong! The push() method for a Stack object is analogous to add() for a Vector, which adds an object to the end of the Vector. Thus the top of the Stack corresponds to the end of the Vector.

Let's try a Stack object out in an example so we get a feel for how the methods are used.

Try It Out – Dealing Cards

We can use a Stack along with another useful method from the Collections class to simulate dealing cards from a card deck. Let's start by defining a class to represent a card. Our Card class can use two integer data members – one to define the suit with values from 0 to 3 for clubs, diamonds, hearts, and spades, and the other with values from 1 to 13 to specify the face value of the card, 1 being an ace and 11 through 13 being jack, queen, and king. It will make the code clearer if we define some constants representing the suits and the court card values. Let's put that as a skeleton class definition:

class Card {
  // Suit values
  public static final int HEARTS = 0;
 
  public static final int CLUBS = 1;
  public static final int DIAMONDS = 2;
  public static final int SPADES = 3;

  // Card face values
  public static final int ACE = 1;
  public static final int JACK = 11;
  public static final int QUEEN = 12;
  public static final int KING = 13;
  private int suit;
  private int value;
}

We need a constructor that ensures that the suit and face value of a card are legal values. We can implement the constructor like this:

class Card {
  public Card(int value, int suit) throws IllegalArgumentException {
    if(value >= ACE && value <= KING)
      this.value = value;
    else
      throw new IllegalArgumentException("Invalid card value");
    if(suit >= HEARTS && suit <= SPADES)
      this.suit = suit;
    else
      throw new IllegalArgumentException("Invalid suit");
  }

  // Other members as before...
}

To deal with invalid arguments to the constructor, we just throw an exception of the standard type, IllegalArgumentException, that we create with a suitable message.

We will undoubtedly need to display a card so we will need a String representation of a Card object. The toString() method will do this for us:

class Card {
  public String toString() {
    String cardStr;
    switch(value) {
      case ACE: cardStr = "A";
                break;
      case JACK: cardStr = "J";
                break;
      case QUEEN: cardStr = "Q";
                break;
      case KING: cardStr = "K";
                break;
      default: cardStr = Integer.toString(value);
    }

    switch(suit) {
      case CLUBS: cardStr += "C";
                break;
      case DIAMONDS: cardStr += "D";
                break;
      case HEARTS: cardStr += "H";
                break;
      case SPADES: cardStr += "S";
                break;
      default:
        assert false;                    // We should never get to here
    }
    return cardStr;
  }

  // Other members as before...
}

Here we just use two switch statements to sort out the strings to represent the face value and the suit respectively from the values of the data members. In general, we might need to be able to compare cards, so we could also implement the Comparable interface:

class Card implements Comparable {
  // Compare two cards
  public int compareTo(Object card) {
    if(suit != ((Card)card).suit)                 // First compare suits
      return suit < ((Card)card).suit ? -1: 1;    // Sequence is C<D<H<S
    else                                          // Suits are the same
      if(value == ((Card)card).value)             // So check face values 
        return 0;                                 // They are equal
      else
        return value < ((Card)card).value ? -1 : 1;
  }

// Other members as before...
}

We could represent a hand of cards that is dealt from a deck as an object of type Hand. A Hand object will need to be able to accommodate an arbitrary number of cards as this will depend on what game the hand is intended for. We can define the Hand class using a Stack object to store the cards:

// Class defining a hand of cards
import java.util.*;

class Hand {
  public void add(Card card) {
    hand.push(card);
  }

  public String toString() {
    Iterator cards = hand.iterator();

    StringBuffer str = new StringBuffer();
    while(cards.hasNext())
      str.append(" "+ (Card)cards.next());
    return str.toString();
  }
    
  private Stack hand = new Stack();       // Stores the cards in the hand
}

The default constructor generated by the compiler will create a Hand object containing an empty Stack member, hand. The add() member will add the Card object passed as an argument by pushing it onto the hand. We also have implemented a toString() method here. We obtain an iterator to traverse the cards in the hand, and construct a string representation of the complete hand. Note that we should not use the pop() method here, because it removes an object from the stack, so using it here would remove all the cards from the hand.

We might well want to compare hands in general, but this is completely dependent on the context. The best approach to accommodate this when required would be to derive a game-specific class from Hand – a PokerHand class for instance – and make it implement its own version of the compareTo() method in the Comparable interface.

The last class we need will represent a deck of cards, and will also deal a hand:

import java.util.*;
class CardDeck {
  // Create a deck of 52 cards
  public CardDeck() {
    for(int theSuit = Card.HEARTS; theSuit<= Card.SPADES; theSuit++)
      for(int theValue = Card.ACE; theValue <= Card.KING; theValue++)
        deck.push(new Card(theValue, theSuit));
  }

  // Deal a hand
  public Hand dealHand(int numCards) {
    Hand hand = new Hand();
    for(int i = 0; i<numCards; i++)
      hand.add((Card)deck.pop());
    return hand;
  }
  
  private Stack deck = new Stack();
}

The card deck is stored as a Stack object, deck. In the constructor, the nested for loops create the cards in the deck. For each suit in turn, we generate all the Card objects from ace to king and push them onto the Stack object, deck.

The dealHand() method creates a Hand object, and then pops numCards objects off the deck stack and adds each of them to hand. The Hand object is then returned. At the moment our deck is completely sequenced. We need a method to shuffle the deck:

class CardDeck {
  // Shuffle the deck
  public void shuffle() {
    Collections.shuffle(deck);
  }

  // Rest of the class as before...
}

With the aid of another static method from the Collections class it couldn't be easier. The shuffle() method in Collections shuffles the contents of any collection that implements the List interface, so we end up with a shuffled deck of Card objects. For those interested in the details of shuffling, this shuffle() method randomly permutes the list by running backwards through its elements swapping the current element with a randomly chosen element between the first and the current element. The time taken to complete the operation is proportional to the number of elements in the list.

An overloaded version of the shuffle() method allows you to supply an object of type Random as the second argument that is used for selecting elements at random while shuffling.

The final piece is a class that defines main():

class TryDeal {
  public static void main(String[] args) {
    CardDeck deck = new CardDeck();
    deck.shuffle();

    Hand myHand = deck.dealHand(5);
    Hand yourHand = deck.dealHand(5);
    System.out.println("\nMy hand is" + myHand);
    System.out.println("\nYour hand is" + yourHand);
  }
}

I got the output:

My hand is 3D KD 7D 8C 7S

Your hand is 9C 6D 6C 3C AS

You will almost certainly get something different.

How It Works

The code for main() first creates a CardDeck object and calls its shuffle() method to randomize the sequence of Card objects. It then creates two Hand objects of 5 cards by calling the dealHand() method. The output statements just display the hands that were dealt.

A Stack object is particularly suited to dealing cards, as we want to remove each card from the deck as it is dealt and this is done automatically by the pop() method that retrieves an object. When we need to go through the objects in a Stack collection without removing them, we can use an iterator as we did in the toString() method in the Hand class. Of course, since the Stack class is derived from Vector, all the Vector class methods are available too, when you need them.

I think you'll agree that using a stack is very simple. A stack is a powerful tool in many different contexts. A stack is often applied in applications that involve syntactical analysis, such as compilers and interpreters – including those for Java.

Previous Next
JavaScript Editor Java Tutorials Free JavaScript Editor