CHAPTER 6

Array-Based Lists

The main focus of this chapter is the user's view of the ArrayList class. We start by investigating the method specifications. We then briefly turn to the developer's view: The Java Collection Framework's ArrayList class implements the List interface with an underlying array that allows constant-time access of any element from its index. We finish up the chapter with an application in the area of public-key cryptography.

As with all of the other collection classes in the Java Collections Framework, the ArrayList class is parameterized, and the element class is the type parameter, so it would be more appropriate to refer to the class as ArrayList<E>. When a user creates an instance of the ArrayList<E> class, the user specifies the element type that will replace the type parameter E. For example, to create an empty ArrayList object whose elements must be of type (reference to) String, we write

ArrayList<String> myList = new ArrayList<String>();

As we saw in Chapter 4, the only stipulation on the element type is that it cannot be a primitive type, such as int (but the wrapper class Integer is acceptable).

Chapter 7 covers another List implementation, the LinkedList class The ArrayList and LinkedList classes have their own advantages and disadvantages: there is no "best" List implementation. A major goal of the two chapters is to help you recognize situations in which one of the classes would be preferable to the other.

CHAPTER OBJECTIVES

1. Recognize the methods in the List interface that are not in the Collection interface.
2. Understand the user's view of the ArrayList class.
3. Be able to decide when an ArrayList is preferable to an array–and vice versa.
4. Understand the VeryLongInt class from both the user's view and the developers' view.

6.1 The List Interface

The List interface extends the Collection interface with methods that have an index as either a parameter or a return type. Here are thumbnail sketches of five of the methods. For each method below, E (for "element") is the type parameter.

// Returns the element at position index in this List object. The worstTime(n) is O(n).
E get (int index);

// Replaces the element that was at position index in this List object with the
// parameter element, and returns the previous occupant. The worstTime(n) is O(n).
E set (int index, E element);

// Returns the index of the first occurrence of obj in this List object, if obj
// appears in this List object.. Otherwise, returns -1.    The worstTime(n) is O(n).
int indexOf (Object obj);

// Inserts element at position index in this List object; every element that
// was at a position >= index before this call is now at the next higher position.
// The worstTime(n) is O(n).
void add (int index, E element);

// Removes and returns the element at position index in this List object; every
//  element that was at a position > index before this call is now at the next lower
// position. The worstTime(n) is O(n).
E remove (int index);

Any implementation of this interface may improve on the time-estimate upper bounds for the methods; and, in fact, for the ArrayList class (see following), worstTime(n) is O(1) for both the get and set methods. We cannot give examples of calls to the List methods because interfaces cannot be instantiated, but the above five methods should give you the idea that many of the methods in a List object are index based. Of course, we also have some holdovers from the Collection interface: the methods size, isEmpty, contains, clear, and so on. And the add (E element) method specifies that the element is inserted at the end of the list.

Section 6.2 introduces the ArrayList class, which implements the List interface. We will emphasize the user's perspective of the ArrayList class by studying the method specifications. In Section 6.3, we take a quick look at the developer's perspective: the actual fields and method definitions in the Java Collections Framework. Then we return to the user's view with an application of the ArrayList class.

6.2 The ArrayList Class

As we will see shortly, an ArrayList object can be thought of as an improved version of the one-dimensional array. Like an array, the ArrayList class supports random access of its elements, that is, any element can be accessed in constant time, given only the index of the element. But unlike an array, an ArrayList object's size (as well as its capacity) is automatically maintained during the execution of a program. Also, there are ArrayList methods for inserting and deleting at any index—if you insert or delete in an array, you must write the code to open up or close up the space. Finally, if you want to insert an element into an array that is already full, you must write the code (to create a new array, copy the old array to the new array, and so on). With an ArrayList object, such expansions are handled automatically.

Figure 6.1 has the big picture from the user's perspective: the method heading for each public method in the ArrayList class. Except for the constructors, the headings are in alphabetical order by method identifier. The type parameter E may appear as the return type as well as the element type of a parameter.

Section 6.2.1 has more detail: the method specifications, with examples, for several ArrayListmethods.

FIGURE 6.1 Public methods in the class ArrayList<E>, where E is the type parameter. Except for the constructors, the method headings are in alphabetical order by method identifier

6.2.1 Method Specifications for the ArrayList Class

The method specifications following use javadoc, and will yield specifications that are similar to, but shorter than, those provided with Sun's Application Programming Interface (API). You are strongly urged to consult that API to get the full details of each specification. The phrase "this ArrayList object" refers to the calling object.

Each method's time requirements are specified with Big-O notation because we are merely establishing an upper bound: a specific implementation of the method may reduce that upper bound. If no time estimate for a method is given, you may assume that worstTime(n) is constant. If a method's average-time estimate is the same as the worst-time estimate, only the worst-time estimate is given.

The following method specifications give you a user's view of the ArrayList class. For each method, we include an example and a comparison with an array.

1. Constructor with initial-capacity parameter

   /**
    * Initializes this ArrayList object to be empty, with the specified initial capacity.
    *
    * @param initialCapacity the initial capacity of the list.
    *
    * @throws IllegalArgumentException - if the specified initial capacity is negative
    *
    *
    */
   public ArrayList (int initialCapacity)

   Example The following creates an empty ArrayList object called fruits, with String elements and an initial capacity of 100:

   ArrayList<String> fruits = new ArrayList<String>  (100);

   Note: There is also a default constructor. For example,

   ArrayList<String> fruits = new ArrayList<String>();

   simply constructs an empty ArrayList object with a default initial capacity (namely, 10).

   Comparison to an array: An array object can be constructed with a specified initial capacity. For example,

   String  [  ]  vegetables = new String  [10];

   makes vegetables an array object with null references at indexes 0 through 9. Unlike an ArrayList object, an array object can consist of primitive elements. For example,

   double  [  ]   salaries = new double  [200];

   constructs an array object whose elements will be of type double and whose initial capacity is 200.

2. Copy constructor

   /**
    * Constructs a list containing the elements of the specified collection, in the order
    * they are stored in the specified collection. This ArrayList object has an
    * initial capacity of 110% the size of the specified collection.   The worstTime(n)
    * is O(n), where n is the number of elements in the specified collection.
    *
   
    * @param c - the specified collection whose elements this ArrayList object is
    *            initialized from.
    *
    */
   public ArrayList (Collection<? extends E> c)

   Example Suppose that myList is an ArrayList object whose elements are the Strings ''yes'', ''no'', and ''maybe''. We can create another ArrayList object that initially contains a copy of myList as follows:

   ArrayList<String> newList = new ArrayList<String> (myList);

   Note 1: This constructor is called the copy constructor.

   Note 2: The argument corresponding to the parameter c must be an instance of a class (not necessarily the ArrayList class) that implements the Collection interface. And the element type must be the same as the element type of the calling object or a subclass of that type.

   For example, if intList is an ArrayList object whose elements are of type Integer (a subclass of Object), we can create an ArrayList object of type Object as follows:

   ArrayList<Object> objList = new ArrayList<Object> (intList);

   At this point, all of the elements in objList are of type Integer, but we can add elements of type Object (and, therefore, elements of type Integer)to objList.

   It might seem that it would be sufficient for the parameter type to be Collection<E> instead of Collection<? extends E>. After all, an instance of the class ArrayList<Object> is legal as the argument corresponding to a parameter of type Collection<E>, so by the Subclass Substitution Rule, an instance of any subclass of ArrayList<Object> would also be legal. But even though Integer is a subclass of Object, ArrayList<Integer> is not allowed as a subclass of ArrayList<Object>.¹ Otherwise, the following code fragment would be able to violate the type restrictions by adding a string to an ArrayList of Integer:

   ArrayList<Integer> intList = new ArrayList<Integer>();
   ArrayList<Object> objList = intList;         // illegal!
   objList.add ("oops");

   Then intList would have "oops" at index 0.

   Note 3: The new ArrayList object contains a copy of the elements in c. Strictly speaking, those elements are references, not objects; the objects referenced are not copied. For this reason, the copy constructor is said to produce a shallow copy.

   Note 4: The clone() method is an alternative, but less desirable way to obtain a shallow copy of an ArrayList object. Here is the method specification:

   /**
    * Returns a shallow copy of this ArrayList object.
   
    * The worstTime(n) is O(n).
    *
    * @return a shallow copy of this ArrayList object.
    */
   public Object clone()

   For example, if myList is an ArrayList object, we can create a shallow copy of myList as follows:

   ArrayList<String> newList = (ArrayList<String>)myList.clone();

   Unfortunately, there is no assurance of type safety, so the assignment will be made even if myList is an ArrayList object with Integer elements. See Programming Exercise 6.4 for details. For more discussion of clone drawbacks, see Bloch 2001, pages 45-52.

   Comparison to an array: An array object can be copied with the static method arraycopy in the System of the package java.lang. For example,

   System.arraycopy (vegetables, i, moreVeggies, 0, 3);

   performs a shallow copy of the array object vegetables, starting at index i, to the array object moreVeggies, starting at index 0. A total of 3 elements are copied.

3. One-parameter add method

   /**
   *  Appends the specified element to the end of this ArrayList object.
   *  The worstTime(n)  is O(n)  and averageTime(n)  is constant.
   *
   *  @param element - the element to be appended to this ArrayList object
   *
   *  @return true  (as per the general contract of the Collection.add method)
   *
   */
   public boolean add  (E element)

   Note. According to the general contract of the add method in the Collection interface, true is returned if the element is inserted. So this ArrayList method will always return true. Then why bother to have it return a value? Because if we replace the return type boolean with void, then the ArrayList class would no longer implement the Collection interface. Incidentally, there are some implementations—the TreeSet class, for example—of the Collection interface that do not allow duplicate elements, so false will sometimes be returned when a TreeSet object calls this version of the add method.

   Example We can insert items at the end of an ArrayList object as follows:

   ArrayList<String> fruits = new ArrayList<String>  (100);
   fruits.add ("oranges");
   fruits.add ("apples");
   fruits.add ("durian");
   fruits.add ("apples");

   The ArrayList object fruits will now have "oranges" at index 0, "apples" at index 1, "durian" at index 2, and "apples" at index 3.

   Comparison to an array: To insert into an array, an index must be specified:

   String [ ] vegetables = new String [10];
   vegetables [0] = "carrots";
   vegetables [1] = "broccoli";
   vegetables [2] = "spinach";
   vegetables [3] = "corn";

4. The size method

   /**
    * Determines the number of elements in this ArrayList object.
    *
    * @return the number of elements in this ArrayList object.
    *
    */
   public int size()

   Example Suppose we create an ArrayList object as follows:

   ArrayList<String> fruits = new ArrayList<String> (100);
   fruits.add ("oranges");
   fruits.add ("apples");
   fruits.add ("durian");
   fruits.add ("apples");

   Then

   System.out.println (fruits.size());

   will output 4.

   Comparison to an array: Arrays have nothing that corresponds to a size() method. The length field contains the capacity of the array, that is, the maximum number of elements that can be inserted into the array, not the current number of elements in the array.

5. The get method

   /**
    *
    * Replaces the element at the specified index in this ArrayList object with the
    * specified element.
    *
    * @param index - the index of the element to be replaced.
    * @param element - the element to be stored at the specified index
    *
    * @return the element previously stored at the specified index
    *
    * @throws IndexOutOfBoundsException - if index is less than 0 or greater
    *         than or equal to size()
    */
   public E set (int index, E element)

   Note: Since no time estimates are given, you may assume that worstTime(n) is constant.

   Example Suppose we start by constructing an ArrayList object:

   ArrayList<String> fruits = new ArrayList<String> (100);
   fruits.add ("oranges");
   fruits.add ("apples");
   
   fruits.add ("oranges");
   fruits.add ("apples");
   fruits.add ("durian");
   fruits.add ("apples");

   Then

   System.out.println (fruits.get (2));

   will output "durian".

   Comparison to an array: The get method is similar to, but weaker than, the index operator for arrays. For example, suppose we start by constructing an array object:

   String [ ] vegetables = new String [10];
   vegetables [0] = "carrots";
   vegetables [1] = "broccoli";
   vegetables [2] = "spinach";
   vegetables [3] = "corn";

   Then

   System.out.println  (vegetables  [1]);

   Will output "broccoli". But we can also overwrite that element:

   vegetables  [1]  =  "potatoes";

   In contrast, the following is illegal if fruits is an ArrayList object:

   fruits.get (1) = "pears";    // illegal

6. The set method

   /**
    *
    * Replaces the element at the specified index in this ArrayList object with the
    * specified element.
    *
    * @param index - the index of the element to be replaced.
    * @param element - the element to be stored at the specified index
    *
    * @return the element previously stored at the specified index
    *
    * @throws IndexOutOfBoundsException - if index is less than 0 or greater
    *         than or equal to size()
    */
   public E set (int index, E element)

   Note: The worstTime(n) is constant.

   Example Suppose we start by constructing an ArrayList object:

   ArrayList<String> fruits = new ArrayList<String> (100);
   fruits.add ("oranges");
   fruits.add ("apples");
   
   fruits.add ("durian");
   fruits.add ("apples");

   Then

   System.out.println (fruits.set (2, "bananas"));

   will change the element at index 2 to ''bananas" and output ''durian'', the element that had been at index 2 before the set method was invoked.

   Comparison to an array: As noted in the comparison for the get method, an array's index operator can be used on the left-hand side of an assignment statement. For example, if vegetables is an array object,

   vegetables [1] = "potatoes";

   will change the element at index 1 to "potatoes".

7. Two-parameter add method

   /**
    *  Inserts the specified element at the specified index in this ArrayList object.
    *  All elements that were at positions greater than or equal to the specified
    *  index have been moved to the next higher position. The worstTime(n) is
    *  O(n).
    *
    *  @param index - the index at which the specified element is to be inserted.
    *  @param element - the element to be inserted at the specified index
    *
    *  @throws IndexOutOfBoundsException - if index is less than 0 or greater
    *          than size().
    */
   public void add (int index, E element)

   Example Suppose we start by constructing an ArrayList object:

   ArrayList<String> fruits = new ArrayList<String> (100);
   fruits.add ("oranges");
   fruits.add ("apples");
   fruits.add ("durian");
   fruits.add ("apples");

   Then

   fruits.add (1, "cherries");
   for (int i = 0; i < fruits.size(); i++)
          System.out.println (fruits.get (i));
   
   

   will produce output of

   oranges
   cherries
   apples
   durian
   apples

   Comparison to an array: For an insertion anywhere except at the end of the array object, the code must be written to open up the space. For example, suppose we start by constructing an array object:

   String [ ] vegetables = new String [10];
   vegetables [0] = "carrots";
   vegetables [1] = "broccoli";
   vegetables [2] = "spinach";
   vegetables [3] = "corn";

   We can insert "lettuce" at index 1 as follows:

   for (int j = 4; j > 1; j--)
        vegetables [j] = vegetables [j - 1];
   vegetables [1] = "lettuce";

   The array vegetables now consists of "carrots", "lettuce", "broccoli", "spinach", "corn", null, null, null, null, null. Note that an insertion in a full array will throw an ArrayindexOutOf Bounds exception.

8. The remove method with an index parameter

   /**
    * Removes the element at the specified index in this ArrayList object.
    * All elements that were at positions greater than the specified index have
    * been moved to the next lower position. The worstTime(n) is O(n).
    *
    * @param index - the index of the element to be removed.
    *
    * @return the element removed the specified index
    *
    * @throws IndexOutOfBoundsException - if index is less than 0 or greater
    *          than or equal to size()
    */
   public E remove (int index)

   Example Suppose we start by constructing an ArrayList object:

   ArrayList<String> fruits = new ArrayList<String> (100);
   fruits.add ("oranges");
   fruits.add ("apples");
   fruits.add ("durian");
   fruits.add ("apples");

   Then we can remove (and return) the element at index 2 as follows:

   System.out.println  (fruits.remove (2));

   The output will be "durian", and fruits will now contain "oranges", "apples", and "apples".

   Comparison to an array: For removal anywhere except at the end of an array, the code must be written to close up the space. For example, suppose we start by creating an array object:

   String [ ] vegetables = new String [10];
   vegetables [0] = "carrots";
   vegetables [1] = "broccoli";
   vegetables [2] = "spinach";
   
   vegetables [3] = "corn";
   vegetables [4] = "potatoes";
   vegetables [5] = "squash";

   Then we can remove the element at index 2 as follows:

   for (int j = 2; j < 5; j++)
          vegetables [j] = vegetables [j + 1];

   The array vegetables now consists of "carrots", "broccoli", "corn", "potatoes", "squash", null, null, null, null and null.

9. The indexOf method

   /**
    * Searches for the first occurrence of a specified element, testing for equality with
    * the equals method. The worstTime(n) is O(n).
    *
    * @param obj - the element to be searched for.
    *
    * @return the index of the first occurrence of obj in this ArrayList object; if
    *          obj is not in this ArrayList object, -1 is returned.
    *
    */
   public int indexOf (Object obj)

   Example Suppose we start by constructing an ArrayList object:

   ArrayList<String> fruits = new ArrayList<String>  (100);
   fruits.add ("oranges");
   fruits.add ("apples");
   fruits.add ("durian");
   fruits.add ("apples");

   Then

   System.out.println (fruits.indexOf ("apples"));

   will output 1, and

   System.out.println (fruits.indexOf ("kiwi"));

   will output −1.

   Note: The type of the parameter element is Object, not E, so the following is legal:

   System.out.println (fruits.indexOf (new Integer (8)));

   Of course, the output will be −1, because all the elements in fruits are of type String.

   Comparison to an array: An explicit search must be conducted to determine if an element occurs in an array. For example, suppose we start by creating an array object:

   String [ ] vegetables = new String [10];
   vegetables [0] = "carrots";
   vegetables [1] = "broccoli";
   vegetables [2] = "spinach";
   
   vegetables [3] = "corn";
   vegetables [4] = "potatoes";
   vegetables [5] = "squash";

   If myVeg is a String variable, we can print the index of the first occurrence of myVeg in the vegetables array as follows:

   boolean found = false;
   for (int j = 0; j < 6 && !found; j++)
          if (vegetables [j].equals (myVeg))
          {
                 System.out.println (j);
                 found = true;
          } // if
   if (!found)
           System.out.println (-1);

   If myVeg does not occur in the array object vegetables, −1 will be output.

These represent just a sampling of the ArrayList class's methods, but even at this point you can see that an ArrayList object is superior, in most respects, to an array object. For example, an ArrayList object's size and capacity are automatically maintained, but an array object's size and capacity must be explicitly maintained by the programmer.

6.2.2 A Simple Program with an ArrayList Object

Perhaps you need more convincing that ArrayList objects are more convenient than array objects. Here is a simple program that creates an ArrayList object from a file of words (one word per line), and then searches for a word in the ArrayList object, removes all instances of a word, appends a word and converts a word to upper case. The resulting ArrayList object is then printed out—with a single call to println. Because this is an illustrative program, there are no constant identifiers.

import java.util.*;

import java.io.*;

public class ArrayListExample
{
  public static void main (String[ ] args)
  {
    new ArrayListExample().run();
  } // method main

  public void run()
  {
     ArrayList<String> aList = new ArrayList<String>();

     Scanner keyboardScanner = new Scanner (System.in),
             fileScanner;

     String inFilePath,
            word;

try
 {
    System.out.print (" n Please enter the path for the input file: ");
    inFilePath = keyboardScanner.nextLine();
    fileScanner = new Scanner (new File (inFilePath));
    while (fileScanner.hasNext())
    {
      word = fileScanner.next();
      System.out.println (word);
      aList.add (word);
    } // while not end of file

    System.out.print ("

 Please enter the word you want to search for: ");
    word = keyboardScanner.next();
    if (aList.indexOf (word) >= 0)
        System.out.println (word + " was found.
 n");
    else
        System.out.println (word + " was not found.

");

    System.out.print ("Please enter the word you want to remove: ");
    word = keyboardScanner.next();
    int removalCount = 0;
    while (aList.remove (word))
        removalCount++;
    if (removalCount == 0)
        System.out.println (word + " was not found, so not removed.

");
    else if (removalCount == 1)
        System.out.println ("The only instance of " + word +
                            " was removed.

");
    else
        System.out.println ("All " + removalCount + " instances of " +
                            word + " were removed.

");

    System.out.print ("Please enter the word you want to append: ");
    word = keyboardScanner.next();
    aList.add (word);
    System.out.println (word + " was appended.

");

    System.out.print ("Please enter the word you want to upper case: ");
    word = keyboardScanner.next();
    int position = aList.indexOf (word);
    if (position >= 0)
    {
        aList.set (position, word.toUpperCase());
        System.out.println (word + " was converted to upper-case.

");
    } // if word is in aList
    else
        System.out.println (word +
                            " was not found, so not upper-cased.
 n");


         System.out.println ("Here is the final version:
" + aList);
                                    // same as aList.toString()
       } // try
       catch (IOException e)
       {
         System.out.println (e);
       } // catch
     } // method run

} // class ArrayListExample

When this program was run, the file a.in1 contained the following words, one per line:

Don't get mad Don't get even Get over it all and get on with

Here is a sample run, with input in boldface:

Please enter the path for the input file: a.in1

Please enter the word you want to search for: even
even was found.

Please enter the word you want to remove: all
The only instance of all was removed.

Please enter the word you want to append: life
life was appended.

Please enter the word you want to convert to upper case: over
over was converted to upper-case.

Here is the final version:

[Don't, get, mad, Don't, get, even, Get, OVER, it, and, get, on, with, life]

In the above program, each removal takes linear time. Programming Exercise 6.8 suggests how to perform all removals in a single loop. And you are invited, in Programming Exercise 6.9, to endure the grind of converting the program from ArrayList-based to array-based.

In Sections 6.2.3 and 6.2.4, we briefly put on a developer's hat and look at the ArrayList class heading, fields and a few method definitions. In Section 6.3, we return to a user's perspective with an application of the ArrayList class.

6.2.3 The ArrayList Class's Heading and Fields

Here is the heading of the ArrayList class:

public class ArrayList<E> extends AbstractList<E>
       implements List<E>, RandomAccess, Cloneable, java.io.Serializable

This says that the ArrayList class is a subclass of the class AbstractList, and implements four interfaces: List, RandomAccess, Cloneable, and Serializable. Figure 6.2 has a UML diagram to indicate where the ArrayList class fits in the Java Collections Framework, with a solid-line arrow from an extension (to a class or interface) and a dashed-line arrow from a class to an interface implemented by the class.

The AbstractCollection class provides a minimal implementation of the Collection interface, just as the AbstractList class provides a "bare bones" implementation of the List interface. As we saw in Section 6.1, the List interface extends the Collection interface by including some index-related methods, such as get (int index) and remove (int index).

Basically, a class that implements the Cloneable interface must have a method that returns a shallow copy of the calling object. For a description of the clone() method, see Note 4 on the copy constructor (method number 2) in Section 6.2.1. The RandomAccess interface ensures that if an implementation of the List interface satisfies the random-access property (with an underlying array), then any sub-list of that list will also satisfy the random-access property. The Serializable interface, discussed in Appendix 1, has to do with saving objects to a stream (such as a disk file), which is called serialization, and restoring those object from the stream, called deserialization.

FIGURE 6.2 The UML diagram to illustrate the relative position of the ArrayList<E> class in the Java Collections Framework

It may come as no surprise to you that the ArrayList class has an array field:

private transient E[    ]  elementData;

The reserved word transient indicates that this field is not saved during serialization (see Appendix 1). That is, each element would be saved, but not the entire array. The field is private instead of protected because the developers of the Java Collections Framework were opposed to giving users who subclass direct access to a superclass's fields. See Section 2.6 for a discussion of this choice.

The only other field defined in the ArrayList class is

private int size;

So an ArrayList object has an array field to store the elements and an int field to keep track of the number of elements.

We will finish up our developer's view of the ArrayList class by studying the implementation of the add method that appends an element to the end of the calling ArrayList object.

6.2.4 Definition of the One-Parameter add Method

To give you an idea of how expansion of an ArrayList object is accomplished, let's look at the definition of the one-parameter add method:

public boolean add (E element)
{
    ensureCapacity (size + 1);
    elementData [size++] = element;
    return true;
}
}

The call to the ensureCapacity method expands the underlying array, if necessary, to accommodate the new element; we'll get to the details of that method momentarily. Then the new element, element, is inserted at index size in the array, size is incremented, and true is returned. Suppose that fruits has been constructed as an empty ArrayList by a default-constructor call, and the next message is

fruits.add ("oranges");

After that message is processed, the elementData and size fields in fruits will have the contents shown in Figure 6.3.

Now let's get back to the ensureCapacity method. If the underlying array is not filled to capacity, then the call to ensureCapacity does nothing. But if size == elementData.length, then the argument size + 1 must be greater than elementData.length, so we need to expand the array. First, the array's current reference, elementData, is copied to oldData:

E oldData [ ] = elementData;

This does not make a copy of the array, just a copy of the reference. Then a new array object is constructed:

elementData = (E[ ]) new Object [newCapacity];

where (because the argument was size + 1) the variable newCapacity was given a value about 50% larger than oldData.length. The cast was necessary because the new operator must be applied to a "real" type, not to a type parameter (such as E). Finally, the arraycopy method in the System class is called to copy all the elements from oldData to elementData; the number of elements copied is the value of size.

FIGURE 6.3 The contents of the elementData and size fields in the ArrayList object fruits after the message fruits.add ("oranges") is sent. As usual, we pretend that the non-null elements in the array are objects; in fact, the elements are references to objects

Here is the complete definition:

public void ensureCapacity(int minCapacity)
{
       modCount++;   // discussed in Appendix 1
       int oldCapacity = elementData.length;
       if (minCapacity > oldCapacity)
       {
           E oldData[ ] = elementData;
           int newCapacity = (oldCapacity * 3) / 2 + 1;
           if (newCapacity < minCapacity) // can't happen if argument is size +
               newCapacity = minCapacity;
           elementData = (E[ ]) new Object [newCapacity];
           System.arraycopy(oldData, 0, elementData, 0, size);
       }
}

To see the effect of an expansion, suppose that the ArrayList object fruits already has ten elements and the following message is sent:

fruits.add ("cantaloupes");

Figure 6.4 shows the effect of this message on the elementData and size fields of fruits.

What are the time estimates of the one-parameter add method? Let n represent the number of elements in the calling ArrayList object. In the worst case, we will have n = elementData.length, and so, in the ensureCapacity method, we will have minCapacity > oldCapacity. Then the call to arrayCopy entails copying n elements from oldData to elementData. We conclude that worstTime(n) is linear in n.

FIGURE 6.4 The contents of the elementData and size fields in the ArrayList object fruits, if fruits already had ten elements when the message fruits.add ("cantaloupes") was sent. As usual, we pretend that the non-null elements in the array are objects instead of references

What about the average case? The only occasion for copying occurs when n = elementD ata.length. But then, by the details of the ensureCapacity method, no copying would have occurred in the previous n/3 (approximately) calls to the one-parameter add method. So in n/3 + 1 calls to that add method, the total number of elements copied would be n, and the average number of elements copied per call would be about 3. We conclude, since the only non-constant-time code in the ensureCapacity method is in the initialization of elementData and in the call to arrayCopy, that averageTime(n) is constant for the one-parameter add method.

Incidentally, the developers of the ArrayList class could have doubled oldCapacity instead of increasing it by about 50%. There is a trade-off: with doubling, additional space is allocated immediately, but then there will be a longer period before the next re-sizing occurs. In fact, in the C++ analogue of the ArrayList class, the old capacity is doubled when a re-sizing occurs.

The previous examination of fields and implementation details is intended just to give you the flavor of the developer's view of the ArrayList class. A few more ArrayList method-definitions are covered in Lab 10. Of course, all of the ArrayList definitions are available in the ArrayList (or AbstractList or AbstractCollection) class of java.util.

Section 6.3 presents an application of the ArrayList class, so the emphasis once again is on the user's viewpoint.

6.3 Application: High-Precision Arithmetic

We now introduce high-precision arithmetic as an application of the ArrayList class. We will get to the details shortly, but it is worth recalling that the use of a class is independent (except for efficiency) of how the class is implemented. So we are not locked in to any particular implementation of the ArrayList class.

In public-key cryptography (see Simmons [1992]), information is encoded and decoded using integers more than 100 digits long. The essential facts about the role of these very long integers in public-key cryptography are:

1. It takes relatively little time—O(n³)—to generate a very long integer with n digits that is prime². For example, suppose we want to generate a prime number that has 500 digits. Then the number of loop iterations required is approximately 500³ = 125,000,000.
2. It takes a very long time—currently, Ω2(10^n/2)—to determine the prime factors of a very long integer with n digits that is not prime. For example, suppose we want to factor a non-prime with 500 digits. Then the number of loop iterations required is approximately (10^500/2) = 10²⁵⁰.
3. Assume that you have generated p and q, two very long integers that are prime. You then calculate another prime e to be greater than pq. The product pq can be calculated quickly, and you supply this product, and e, to anyone who wants to send you a message, M. First, the sender splits the message M up into sequences of characters M₁, M₂,.... The sequence M_i is then treated as a very long integer V_i by concatenating the bits in each character in M_i. The encrypted integer corresponding to V_i is V^e_i % pq. That is, we raise V_i to the power e and then take the remainder when the result of that exponentiation is divided by pq. This seems complicated, but in fact, the calculation can be performed relatively quickly. (See Simmons, [1992] for details.) The encoded message, as well as pq and e, are public, that is, transmitted over an insecure channel such as a telephone, postal service, or computer network.
4. But decoding the message requires knowing the values of p and q. Since determining the factors p and q takes a prohibitively long time, only you can decode the message.

Very long integers require far greater precision than is directly available in programming languages. We will now design and implement a simple version of the VeryLongInt class. Exercise 6.5 asks you to amplify this version, Lab 12 involves the testing of the amplified version, and Programming Assignment 6.1 further expands the VeryLongInt class.

For an industrial-strength class that is applicable to public-key cryptography, see the BigInteger class in java.math. The BigInteger class includes efficient methods for primality testing, multiplication, and modular exponentiation.

6.3.1 Method Specifications and Testing of the VeryLongInt Class

There will be only three methods: A very long integer can be constructed from a string, converted to a string, or incremented by another very long integer. Here are the method specifications, with examples:

1. /**
    * Initializes this VeryLongInt object from the digit characters in a
    * given String object.
    * There are no leading zeros, except for 0 itself, which has a single '0'.
    * The worstTime(n) is O(n), where n represents the number of characters in s.
    *
    * @param s - the given String object.
    *
    * @throws NullPointerException - if s is null.
    * @throws IllegalArgumentException - if s contains no digit characters.
    *
    */
    public VeryLongInt (String s)

   Example Suppose we have

   VeryLongInt veryLong = new VeryLongInt ("112237344556677889900");

   Then veryLong will be initialized to the VeryLongInt object whose integer value is 11223344556677889900. The '?' is ignored because it is not a digit character. The value is greater than the largest int value.

2. /** Returns a String representation of this VeryLongInt object. The worstTime(n) is
    * O(n), where n represents the number of digits in this VeryLongInt object.
    *
    * @return a String representation of this VeryLongInt object in the form '[' followed
    *         by the digits, separated by commas and single spaces, followed by ']'.
    *
    */
   public String toString()

   Example Suppose we have

   VeryLongInt veryLong = new VeryLongInt ("52?481");
   System.out.println (veryLong); // same as
                                // System.out.println (veryLong.toString());

   The output would be

   [5,2,4,8,1]

3. /**
    * Increments this VeryLongInt object by a specified VeryLongInt object.
    * The worstTime(n) is O(n), where n is the number of digits in the larger of this
    * VeryLongInt object (before the call) and the specified VeryLongInt object.
    *
    * @param otherVeryLong - the specified VeryLongInt object to be added to
    *         this VeryLongInt object.
    *
   
    * @throws NullPointerException - if otherVeryLong is null.
    *
    */
   public void add (VeryLongInt otherVeryLong)

   Example Suppose that newInt and oldInt are VeryLongInt objects with values of 328 and 97, respectively, and the message sent is

   newInt.add (oldInt);

   Then the value of newInt has become 425.

   Note: This method performs the arithmetic operation of addition. Contrast that to the ArrayList class's one-paramter add method, which appends the argument to the calling ArrayList object.

   The book's website has a VeryLongIntTest class, with the following fields:

   protected VeryLongInt very;
   
   protected String answer;

That class also includes the following tests, one for a constructor call with an argument that has no digits, and one for a simple addition:

@Test (expected = IllegalArgumentException.class)
public void testConstructorWithNoDigits()
{
     very = new VeryLongInt ("x t?.o");
} // method testConstructorWithNoDigits


@Test
public void testAdd()
{
   very = new VeryLongInt ("99");
   VeryLongInt other = new VeryLongInt ("123");
   very.add (other);
   answer = very.toString();
   assertEquals ("[2, 2, 2]", answer);
} // method testAdd

6.3.2 Fields in the VeryLongInt Class

As often happens in developing a class, the major decision involves the field(s) to represent the class. Should we store a very long integer in an array-based structure such as an ArrayList, or would a linked structure be better? (An array itself is not a good idea because then we would have to write the code—for example, to keep track of the number of elements in the array—instead of simply calling methods). In this chapter, we will use the ArrayList class and represent each very long integer as a sequence of digits. In Chapter 7, we will consider a linked structure.

Which is the appropriate relationship between VeryLongInt and ArrayList: is-a (inheritance) or has-a (aggregation)? That is, should VeryLongInt be a subclass of ArrayList, or should VeryLongInt have a field of type ArrayList ? The primary purpose of the VeryLongInt class is to perform arithmetic; as such, it shares little functionality with the ArrayList class. So it makes more sense to say "a VeryLongInt object has-an ArrayList field" than "a VeryLongInt object is-an ArrayList object." The only field in the VeryLongInt class will be an ArrayList object whose elements are of type Integer:

protected ArrayList<Integer> digits;

Each element in the ArrayList object digits will be an Integer object whose value is a single digit (Exercise 6.6 expands each value to a five-digit integer).

Figure 6.5 has the UML diagram for the VeryLongInt class.

FIGURE 6.5 The class diagram for the VeryLongInt class

6.3.3 Method Definitions of the VeryLongInt Class

The digits in the ArrayList field digits will be stored from left-to-right, that is, in their normal order. For example, if the underlying integer value of a VeryLongInt object is 328, we would store the 3 at index 0 in digits, the 2 at index 1, and the 8 at index 2.

Notice that by having the insertions take place at the end of the ArrayList object, we take advantage of the average-case speed of the ArrayList class's one-parameter add method, which is not related to the VeryLongInt method named add. If, instead, we stored a number in reverse order, we would be repeatedly inserting at the front of the ArrayList object digits. Exercise 6.7 explores the effect on efficiency if the digits are stored in reverse order.

We now define the String -parameter constructor, the toString() method and the add method. While we do we will keep in mind the strengths (fast random access and fast end-insertions) and weakness (slow insertions at other-than-the-end positions) of the ArrayList class.

For the String-parameter constructor, we loop through the characters in s. For each character in s, if the character is a digit character, we convert that character to the corresponding digit by subtracting the Unicode representation of '0' from the character. For example,

'7'  -   '0'   = 7

Finally, we append that digit (as an Integer) to digits. The ArrayList field digits never needs resizing during the execution of this constructor because that field is constructed with initial capacity of s.length(). Here is the code:

public VeryLongInt (String s)
{
       final char LOWEST_DIGIT_CHAR = '0';

       digits = new ArrayList<Integer> (s.length());

       char c;

       int digit;

       boolean atLeastOneDigit = false ;

       for (int i = 0; i < s.length(); i++)
       {
              c = s.charAt (i);
              if (Character.isDigit(c))
              {
                      digit = c - LOWEST_DIGIT_CHAR;
                      digits.add (digit);   // digit is boxed to an Integer object
                      atLeastOneDigit = true;
              } // if a digit
       } // for
       if (!atLeastOneDigit)
              throw new IllegalArgumentException();
} // constructor with string parameter

How long will this method take? Assume that there are n characters in the input. Then the loop will be executed n times. For the ArrayList class's one-parameter add method, averageTime (n) is constant, so for this constructor, averageTime(n) is linear in n (that is, O(n)and Ω(n)). As we saw in the analysis of that add method, if n represents the number of elements in the ArrayList object, worstTime(n) is O(n)for n calls to that add method, So for this constructor in the VeryLongInt class, worstTime(n) is O(n). In fact, because worstTime(n) ≥ averageTime(n) and averageTime(n) is Ω(n), worstTime(n) must be Ω(n). We conclude that worstTime(n) is linear in n.

For the toString() method, we simply invoke the ArrayList class's toString() method:

public String toString()
{
     return digits.toString();
} // method toString

For an example of a call to this method, if veryLong is a VeryLongInt object with a value of 6713, the output from the call to

System.out.println (veryLong); // same as System.out.println (veryLong.toString());

will be

[6, 7,1,3]

For this method, worstTime(n) is linear in n, the number of digits in the calling VeryLongInt object. To convince yourself of this estimate, look at the definition of the toString() method in the Abstract Collection class, a superclass of ArrayList.

Finally, we tackle the add (VeryLongInt otherVeryLong) method in the VeryLongInt class. We obtain partial sums by adding otherVeryLong to the calling object digit-by-digit, starting with the least significant digit in each number. Each partial sum, divided by 10, is appended to the end of the ArrayList object sumDigits, which is initially empty.

Because we will be using the ArrayList class's one-parameter add method on the partial sums, we must reverse sumDigits after adding so that the most significant digit will end up at index 0. For example, suppose newInt is a VeryLongInt object with the value 328 and oldInt is a VeryLongInt object with the value 47. If the message is

newInt.add (oldInt);

then after adding and appending the partial sums to the VeryLongInt object sum, sum will have the value 573. When this is reversed—by the generic algorithm reverse in the Collections class of the package java.util—the sum will be correct. Note that the add method in the ArrayList class is used to append a digit to the end of sumDigits; the ArrayList class's add method does not perform arithmetic.

Here is the definition of the add method in the VeryLongInt class:

public void add (VeryLongInt otherVeryLong)
{
       final int BASE = 10;

       int largerSize,
           partialSum,
           carry = 0;

       if (digits.size() > otherVeryLong.digits.size())
               largerSize = digits.size();
       else
               largerSize = otherVeryLong.digits.size();

       ArrayList<Integer> sumDigits = new ArrayList<Integer> (largerSize + 1);

       for (int i = 0; i < largerSize; i++)
       {
              partialSum = least (i) + otherVeryLong.least (i) + carry;
              carry = partialSum / BASE;
              sumDigits.add (partialSum % BASE);
       } // for

       if (carry == 1)
              sumDigits.add (carry);
       Collections.reverse (sumDigits);
       digits = sumDigits;
} // method add

The call to the least method with an argument of i returns the i^th least significant digit in the calling object's digits field. The units (rightmost) digit is considered the 0th least significant digit, the tens digit is considered the 1st least significant digit, and so on. For example, suppose that the calling VeryLongInt object has the value 3284971, and i has the value 2. Then the digit returned by the call to least (2) will be 9 because 9 is the 2^nd least significant digit in the calling object's digits field; the 0^th least-significant digit is 1 and the 1^st least-significant digit is 7. The method definition is:

/** Returns the ith least significant digit in digits if i is a non-negative int less than
 * digits.size(). Otherwise, returns 0.
 *
 * @param i - the number of positions from the right-most digit in digits to the
 *             digit sought.
 *
 * @return the ith least significant digit in digits, or 0 if there is no such digit.
 *
 * @throws IndexOutOfBoundsException - if i is negative.

 *
 */
protected int least (int i)
{
       if (i >= digits.size())
               return 0;
       return digits.get (digits.size() - i - 1);
} // least

For the least method, worstTime(n) is constant because for the size and get methods in the ArrayList class, worstTime(n) is constant.

We can now estimate the time requirements for the VeryLongInt class's add method. Assume, for simplicity, that the calling object and otherVeryLongInt are very long integers with n digits. There will be n iterations of the for loop in the definition of the add method, and during each iteration, a digit is appended to sumDigits. For appending n elements to the end of an ArrayList, worstTime(n) is linear in n; see Exercise 6.2. The reverse generic algorithm also takes linear-in-n time, so for the add method in the VeryLongInt class, worstTime(n) is linear in n.

The book's website has a class, VeryLongIntUser, to demonstrate how an end user might work with the VeryLongInt class. The run method inputs a line from the keyboard, calls a process method to parse the line and invoke the appropriate method,, and outputs the result of processing to the screen. For the testing of that process method, see the test class, VeryLongIntUserTest, also on the book's website.

Programming Exercise 6.7 expands on the VeryLongInt class. You should complete that exercise before you attempt to do Lab 11.

Exercise 7.7 explores the modifications needed to develop the VeryLongInt class with digits a LinkedList field instead of an ArrayList field.

SUMMARY

In this chapter we introduced the List interface, which extends the Collection interface by adding several index-based methods. We then studied the ArrayList class, an implementation of the List interface that allows random-access—that is, constant-time access—of any element from its index. Using an ArrayList object is similar to using an array, but one important difference is that ArrayList objects are automatically resizable. When an ArrayList outgrows the current capacity of its underlying array, an array of 1.5 times that size is created, and the old array is copied to the larger array. This is similar to what hermit crabs do each time they outgrow their shell. A further advantage of ArrayList object over arrays is that, for inserting and deleting, users are relieved of the burden of writing the code to make space for the new entry or to close up the space of the deleted entry.

The application of the ArrayList class was in high-precision arithmetic, an essential component of public-key cryptography.

CROSSWORD PUZZLE

CONCEPT EXERCISES

6.1 State two advantages, and one disadvantage, of using an ArrayList object instead of an array object.

6.2 Show that, for the task of appending n elements to an ArrayList object, worstTime(n) is linear in n.

6.3 The one-parameter add method in the ArrayList class always returns true. Would it make sense to change the return type from boolean to void ? Explain.

6.4 For the one-parameter add method in the ArrayList class, estimate worstSpace(n) and averageSpace(n).

6.5 In choosing fields for the VeryLongInt class, we decided to use, rather than inherit from, the ArrayList class. Why?

Hint: How much commonality is there between the methods in the ArrayList class and the methods in the VeryLongInt class?

6.6 Suppose you modified the VeryLongInt class as follows: each element in digits consists of a five-digit integer. What effect do you think this will have on Big-O time? What about run-time?

6.7 Suppose, in developing the VeryLongInt class, we decide that digits will contain the integer in reverse order. For example, if the constructor call is:

VeryLongInt veryLong = new VeryLongInt ("386");

we would have (Integer elements with values) 6, 8, 3 in positions 0 through 2, respectively of digits. Re-design this constructor so that worstTime(n) is still linear in n.

6.8 Which parts of the VeryLongInt methods would have to be re-written if digits were an array object of int elements instead of an ArrayList object of Integer elements?

6.9 How can a user of the VeryLongInt class easily create a VeryLongInt object that is a copy of an already existing VeryLongInt object?

PROGRAMMING EXERCISES

6.1 Hypothesize the output from the following code, and then test your hypothesis with a small program that includes the code:

ArrayList<String> letters = new ArrayList<String>();

letters.add ("f");
letters.add (1, "i");
letters.add ("e");
letters.add (1, "r");
letters.add ("e");
letters.add (4, "z");
System.out.println (letters);

letters.remove ("i");
int index = letters.indexOf ("e");
letters.remove (index);
letters.add (2, "o");
System.out.println (letters);

6.2 For each of the following program segments, hypothesize if the segment would generate a compile-time error, a run-time exception, or neither. Then test your hypotheses with a main method that includes each segment.

1. ArrayList<String> myList = new ArrayList<String>();
   myList.add ("yes");
   myList.add (7);

2. ArrayList<Double> original = new ArrayList<Double>();
   original.add (7);

3. ArrayList<Integer> original = new ArrayList<Integer>();
   double x = 7;
   original.add (x);

4. ArrayList<String> newList = new ArrayList<String>();
   newList.add ("yes");
   Integer answer = (Integer)newList.get (0);
   

6.3 Suppose we have the following code:

ArrayList<String> myList = new ArrayList<String>();

myList.add ("Karen");
myList.add ("Don");
myList.add ("Mark");

ArrayList<String> temp = new ArrayList<String> (myList);
ArrayList<String> sameList = myList;

myList.add (1, "Courtney");

Hypothesize what the contents of myList, temp, and sameList will be after this last insertion. Then test your hypothesis with a main method that includes the code.

6.4 Hypothesize what will happen when the following code fragment is run, and then test your hypothesis:

ArrayList<String> original = new ArrayList<String>();
original.add ("yes");
ArrayList<Integer> copy = (ArrayList<Integer>)original.clone();

System.out.println (copy.get (0));

Hint: This exercise illustrates why the copy constructor is superior to the clone() method.

6.5 Expand the VeryLongInt class by testing and defining methods that have the following method specifications:

1. /**
    * Initializes this VeryLongInt object from a given int.
    *
    * @param n - the int from which this VeryLongInt is initialized.
    *
    * @throws IllegalArgumentException - if n is negative.
    *
    */
   public VeryLongInt (int n)

2. /**
    *  Returns the number of digits in this VeryLongInt object.
    *
    *  @return the number of digits in this VeryLongInt object.
    *
    */
   public int size()

3. /**
    * Returns true if this VeryLongInt object is less than another VeryLongInt
    * object. The worstTime(n) is O(n).
    *
    * @param otherVeryLong - the other VeryLongInt object.
    *
    * @return true - if this VeryLongInt is less than otherVeryLong.
    *
    * @throws NullPointerException - if otherVeryLong is null
    *
    */
   public boolean less (VeryLongInt otherVeryLong)

4. /**
    * Returns true if this VeryLongInt object is greater than another VeryLongInt
    * object. The worstTime(n) is O(n).
    *
    * @param otherVeryLong - the other VeryLongInt object.
    *
    * @return true - if this VeryLongInt is greater than otherVeryLong.
    *
    * @throws NullPointerException - if otherVeryLong is null
    *
    */
   public boolean greater (VeryLongInt otherVeryLong)

5. /**
    *  Returns true if this VeryLongInt object is equal to a specified object.
    * The worstTime(n) is O(n).
    *
    *  @param obj - the specified object that this VeryLongInt is compared to.
    *
    * @return true - if this VeryLongInt is equal to obj.
    *
    */
   public boolean equals (Object obj)

6. /**
    * Stores a Fibonacci number in this VeryLongInt object.
    *
    * @param n - the index in the Fibonacci sequence
    *
    * @throws IllegalArgumentException - if n is not positive
    *
   
    */
   public void fibonacci (int n)

Example Suppose the following message is sent

tempInt.fibonacci  (100);

Then tempInt's value will be 354224848179261915075—the 100^th Fibonacci number.

Hint: Mimic the iterative design of the Fibonacci function from Lab 7. Both i and n will be ordinary int variables, but previous, current and temp will be VeryLongInt objects. After the loop, instead of returning current, the calling object is modified by assigning to digits a copy of current.digits.

6.6 Assume that myList is (a reference to) an ArrayList<Double> object and that both i and j are int variables with values in the range from 0 to myList.size() −1, inclusive. Hypothesize what the following accomplishes, and then test your hypothesis.

myList.set (i, myList.set (j, myList.get (i)));

6.7 Describe how to find the method definitions for the ArrayList class in your computing environment.

6.8 Modify the simple program in Section 6.2.2 so that all removals are performed in a single loop.

Hint: Create a temporary ArrayList object to hold the un-removed elements. What is a drawback to this approach?

6.9 Convert the simple program in Section 6.2.2 into one that uses an array object instead of an ArrayList object.

6.10 Modify the simple program in Section 6.2.2 to use a binary search instead of the sequential search used in the call to the indexOf method. The Collections class in java.util has a binarySearch method and a sort method.

6.11 Suppose scoreList is an ArrayList object of Integer elements, and the following message is sent:

scoreList.remove  (3);

Does this message remove the element at index 3, or remove the first occurrence of new Integer (3) ? Test your hypothesis.

6.12 Suppose we create the following ArrayList instance:

ArrayList<String> words = new ArrayList<String>();

And then we insert several words into words. Write the code to print out each element of words that has exactly four letters. You should have three different versions of the code:

1. using an index;
2. using an explicit iterator;
3. using an enhanced for statement.

6.13 Test and define the following method

/**
 * In a given ArrayList, remove all duplicates.
 * The worstTime(n) is O(n2).
 *
 * @param list - the given ArrayList.
 *

 * @return - An ArrayList that is identical to list except only the first
 *           occurrence of duplicate elements remains.
 *
 * @throws NullPointerException - if list is null.
 *
 */
public static <T> ArrayList <T> uniquefy (ArrayList <T> list)

For example, suppose myList consists of references to Integer objects with the following values, in sequence

3, 8, 6, 4, 8, 7, 8, 9, 4

Then the ArrayList returned by the call to uniquefy (myList) will consist of references to Integer objects with the following values, in sequence

3, 8, 6, 4, 7, 9

/** Stores in this VeryLongInt object the product of its pre-call value and the value
 * of a specified VeryLongInt object. The worstTime(n) is O(n * n), where n is
 * the maximum of the number of digits in the pre-call value of this
 * VeryLongInt object and the number of digits in the specified VeryLongInt object.
 *
 * @param otherVeryLong - the specified VeryLongInt object to be multiplied by
 *         this VeryLongInt object.
 *
 * @throws NullPointerException - if otherVeryLong is null
 *
 */
public void multiply (VeryLongInt otherVeryLong)

/**
 * Stores, in this VeryLongInt object, the product of all integers between 1 and
 * specified integer n. The worstTime(n) is O(n log (n!)): n multiplications, and
 * each product has fewer digits than log (n!), the number of digits in n!
 *
 * @param n - the number whose factorial will be stored in this VeryLongInt
 *             object.
 *
 * @throws IllegalArgumentException - if n is negative.

 *
 */
public void factorial (int n)

/**
 * Initializes this Filter object from the paths for the input file
 * and common words.
 *
 * @param inFilePath - the path for the input file.
 * @param commonFilePath - the path for the file with the common words.
 *
 *  @throws IOException - if either file does not exist.
 *
 */
public Filter (String inFilePath, String commonFilePath) throws IOException

/**
 *  Creates the ArrayList of tokens from the input file.
 *
 *   @return - an ArrayList of tokens.
 *
 *
 */
public  ArrayList<String> createList()

¹. This phenomenon is called invariant subtyping, and it is required for type safety. Why? The element type of a parameterized collection is not available at run time, so the type checking of elements cannot be done at run time. This is in contrast to arrays, whose element type is available at run time. As a result, arrays use covariant subtyping; for example, String[ ] is a subclass of Object[ ].

². An integer p > 1is prime if the only positive-integer factors of p are 1 and p itself.