Many variations of collections are possible. Here we define a basic collection, a content-based repository that supports addition, removal, and retrieval of elements.

Our collections allow duplicate elements. Element first is considered to be a duplicate of element second if first.equals(second) returns true. When an operation involves “finding” such an element, it can “find” any one of the duplicates. There is no distinction among duplicate elements in these cases.

As with our stacks and queues, collections do not support null elements. As a general precondition for all of our collection methods, null elements cannot be used as arguments. Rather than stating this precondition for each method, we state it once in the lead comment of the interface. This is a standard precondition when defining ADTs. It simplifies coding, which removes the need for testing for null pointers every time we use an argument within a method.

Other than prohibiting null elements, our collection classes have minimal preconditions for operations. For example, it is possible to specify a remove operation that requires a matching object to be present in the collection. We do not do this. Instead, we define a remove operation that returns a boolean value indicating whether the operation succeeded. This approach provides greater flexibility to applications. Similarly we could require that the add operation not be invoked on a full collection, perhaps stating that in such a situation it throws a “Collection Overflow” exception. Instead we use the same approach as with remove—add returns a boolean indicating success or failure of the operation. An attempt to add to a full collection would return false.

As we did with stacks and queues, we capture the formal specifications of our Collection ADT using the Java interface construct. Our collections are generic—the type of object held by any particular collection is indicated by the client at the time the list is instantiated. It is the client’s responsibility to use a class whose equals method definition suits their needs. Here is the code for our CollectionInterface. Study the comments and method signatures to learn more about the details. As you can see, this interface is part of the ch05.collections package. The implementation classes are also stored in the same package.

//---------------------------------------------------------------------------
// CollectionInterface.java       by Dale/Joyce/Weems               Chapter 5
//
// Interface for a class that implements a collection of T.
// A collection allows addition, removal, and access of elements.
// Null elements are not allowed. Duplicate elements are allowed.
//---------------------------------------------------------------------------
package ch05.collections;

public interface CollectionInterface<T>
{
  boolean add(T element);
  // Attempts to add element to this collection.
  // Returns true if successful, false otherwise.

  T get(T target);
  // Returns an element e from this collection such that e.equals(target).
  // If no such element exists, returns null.

  boolean contains(T target);
  // Returns true if this collection contains an element e such that
  // e.equals(target); otherwise returns false.

  boolean remove (T target);
  // Removes an element e from this collection such that e.equals(target)
  // and returns true. If no such element exists, returns false.

  boolean isFull();
  // Returns true if this collection is full; otherwise, returns false.

  boolean isEmpty();
  // Returns true if this collection is empty; otherwise, returns false.


  int size();
  // Returns the number of elements in this collection.
}

Figure 5.4, in this chapter’s summary, shows the relationships among the primary classes and interfaces created to support our Collection ADT.

Section 1.5, “Basic Structuring Mechanisms,” discussed comparing objects using the comparison operator (==). Recall that when using ==, the comparison is actually made between the contents of the two reference variables that point to the objects, and not between the contents of the objects themselves. This is demonstrated in Figure 5.1 (which replicates Figure 1.6).

The comparison operator does not compare the contents of objects. What else can we do? How do we compare the actual objects? One option is to use the equals method. Because this method is exported from the Object class that is the root of the Java inheritance tree, it can be used with objects of any Java class. If c1 and c2 are objects of the class Circle, then we can compare them using:

c1.equals(c2)

The equals method, as defined in the Object class, acts in much the same way as the comparison operator. It returns true if and only if the two variables reference the same object. To circumvent this problem we can, within a class, redefine the equals method to fit the purpose of the class.

Suppose we have a Circle class that features a radius attribute of type int. A reasonable definition for equality of Circle objects is that they are equal if they have the same radii. To implement this approach, we include the following method in the Circle class:

@Override
public boolean equals(Object obj)
// Returns true if obj is a Circle with same radius as this Circle,
// otherwise returns false.
{
   if (obj == this)
      return true;
   else
   if (obj == null || obj.getClass() != this.getClass())
      return false;
   else
   {
      Circle c = (Circle) obj;
      return (this.radius == c.radius);
   }
}

This design of the equals method reflects standard good practice. A few notes about the design follow:

• The @Override notation indicates to the compiler that we are overriding an ancestor’s method. The compiler double-checks our syntax and ensures that we are in fact overriding a method.

• The first if clause checks to see if we are comparing a circle to itself. In that case we return true.

• The second if clause checks to see if the argument is null. If so we return false. Due to the short-circuit nature of the Java || operator the second part of the or expression is only evaluated if the first part is false, protecting us from a null pointer exception. In the second part of the expression we check to make sure the two objects being compared are of the same type—if not we return false.

• If processing reaches the final else clause we can safely cast the obj argument as a Circle and compare the two radii.

Now when a statement such as

c1.equals(c2)

is encountered, the customized equals method of the Circle class is used, rather than the equals method of the Object class. Even though c1 and c2 may reference different Circle objects, if those objects have equal radii, the equals method returns true. As discussed previously in Section 5.1, “The Collection Interface,” we sometimes refer to the attribute, or combination of attributes, of an object used by the equals method to determine equality as the key of the class. The key of a class, from the point of view of an application, is the set of attributes that are used to determine the identity of an object of the class, for that application. For example, if an application uses the Circle class equals method to determine identity, then the radius of a circle is the key.

@Override
public boolean equals(Object obj)
// Returns true if 'obj' is a FamousPerson with same first and last
// names as this FamousPerson, otherwise returns false.
{
   if (obj == this)
      return true;
   else
   if (obj == null || obj.getClass() != this.getClass())
       return false;
   else
   {
      FamousPerson fp = (FamousPerson) obj;
      return (this.firstName.equals(fp.firstName) &&
              this.lastName.equals(fp.lastName));
   }
}

//---------------------------------------------------------------------------
// CSInfo.java              by Dale/Joyce/Weems                     Chapter 5
//
// Reads information about famous computer scientists from the file
// FamousCS.txt. Allows user to enter names and provides them the information
// from the file that matches the name.
//---------------------------------------------------------------------------
package ch05.apps;

import java.io.*;
import java.util.*;
import ch05.collections.*;
import support.FamousPerson;

public class CSInfo
{
  public static void main(String[] args) throws IOException
  {
    // instantiate collection
    final int CAPACITY = 300;
    ArrayCollection<FamousPerson> people
          = new ArrayCollection<FamousPerson>(CAPACITY);

    // set up file reading
    FileReader fin = new FileReader("input/FamousCS.txt");
    Scanner info = new Scanner(fin);
    info.useDelimiter("[,\n]");  // delimiters are commas, line feeds

    Scanner scan = new Scanner(System.in);
    FamousPerson person;
    String fname, lname, fact;
    int year;

    // read the info from the file and put in collection
    while (info.hasNext())
    {
      fname = info.next();   lname = info.next();
      year = info.nextInt(); fact = info.next();
      person = new FamousPerson(fname, lname, year, fact);
      people.add(person);
    }

    // interact with user, getting names and displaying info
    final String STOP = "X";
    System.out.println("Enter names of computer scientists.");
    System.out.println("Enter: firstname lastname (" + STOP + " to exit)
");
    fname = null; lname = null;
    while (!STOP.equals(fname))
    {
      System.out.print("Name> ");
      fname = scan.next();
      if (!STOP.equals(fname))
      {
         lname = scan.next();
         person = new FamousPerson(fname, lname, 0, "");
         if (people.contains(person))

         {
           person = people.get(person);
           System.out.println(person);
         }
         else
           System.out.println("No information available
");
      }
    }
  }
}

Enter names of computer scientists.
Enter: firstname lastname (X to exit)

Name> Ada Lovelace
Ada Lovelace(Born 1815): Considered by many to be first computer programmer.

Name> Molly Joyce
No information available

Name> Edsger Dijkstra
Edsger Dijkstra(Born 1930): 1972 Turing Award winner.

Name> X

person = people.get(person);

person = new FamousPerson(fname, lname, 0, "");

firstName: "Ada" lastName: "Lovelace" yearOfBirth: 0
fact: ""

firstName: "Ada" lastName: "Lovelace" yearOfBirth: 1815
fact: "Considered by many to be first computer programmer."

The equals method allows us to check whether a particular element is in a collection. But in addition to checking objects for equality, we need another type of comparison. We often need to be able to tell when one object is less than, equal to, or greater than another object. The Java library provides an interface, called Comparable, that can be used to ensure that a class provides this functionality.

The Comparable interface consists of exactly one abstract method:

public int compareTo(T o);
// Returns a negative integer, zero, or a positive integer as this object
// is less than, equal to, or greater than the specified object.

The compareTo method returns an integer value that indicates the relative “size” relationship between the object upon which the method is invoked and the object passed to the method as an argument. As we see in the next section, this information can be used to order the objects of a collection within the internal representation structure, facilitating faster search. By convention the compareTo method of a class should support the standard order of a class—lexicographic order for strings, numeric order for numbers, low score to high score for bowlers, high score to low score for golfers, and so on. We call the order established by a class compareTo method the natural order of the class.

Any class that implements the Comparable interface defines its own compareTo method, with a signature that matches the abstract method defined in the interface. After all, the implementer of the class is in the best position to define how objects of the class should be compared—to know the natural order.

The Java Comparable interface is able to work with generics. Use of generic types with the compareTo method helps ensure that comparison takes place only between compatible objects.

Let us return to our famous person example. Recalling that people are compared on their first and last names when determining equality, we use the same two fields when determining relative order. Following standard procedure we first compare last names using the String class equals method—only if the two last names under consideration are equal do we turn our attention to the first names. When a key consists of multiple attributes, starting with the most significant attribute, first is the best approach. Here is the compareTo method implemented within our FamousPerson class (our FamousPerson class does implement the Comparable interface):

public int compareTo(FamousPerson other)
// Precondition: 'other' is not null
//
// Compares this FamousPerson with 'other' for order. Returns a
// negative integer, zero, or a positive integer as this object
// is less than, equal to, or greater than 'other'.
{
  if (!this.lastName.equals(other.lastName))
    return this.lastName.compareTo(other.lastName);
  else
    return this.firstName.compareTo(other.firstName);
}

Our compareTo method uses the compareTo method of the String class. This makes sense because the attributes upon which we are basing the comparison are strings. Notice that the equals method described previously and the compareTo method described here are consistent with each other. In other words, the equals method returns true for two people if and only if the compareTo method returns 0 for the two people. It is good programming practice to ensure consistency between these two methods. Unlike with the equals method it is common to assume the argument passed to compareTo is not null.

As elements are added to our collection we intend to keep the protected array sorted according to the natural order of the elements—therefore we intend to use the compareTo method associated with the elements. In order to do this we must ensure that only classes that implement the Comparable interface are used with our collection.

Is it possible to force applications to use Comparable classes when providing an argument for a generic type? Yes it is. We can use what is called a “bounded type.” For example, we could design a class Duo that holds a pair of elements and that provides a largest operation to return the larger of the two elements:

public class Duo<T extends Comparable<T>>
{
  protected T first;
  protected T second;

  public Duo(T f, T s)
  {
    first = f; second = s;
  }

  public T larger()
  {
    if (first.compareTo(second) > 0)
       return first;
    else
       return second;
  }
}

Note that in the class declaration instead of indicating the generic parameter as <T> we used <T extends Comparable <T>>. This indicates that the generic argument must be of a class that implements the Comparable interface. If we instantiate a Duo object using a class that does not implement Comparable, a syntax error is generated.

Although it appears we can use the above approach to solve our problem of assuring that only Comparable classes are used with our SortedArrayCollection classes, it turns out that is not the case. Because we wish to use an array as our internal representation structure, we cannot use this approach due to type safety issues and differences between the way arrays and generic types are treated by Java. Attempting to declare an array of <T extends Comparable<T>> results in a syntax error. So we need to find a different approach.

Rather than try to enforce the use of Comparable classes using syntactic means we will use our “programming by contract” approach. We specify as a precondition of the add method that its argument is comparable to the previous objects added to the collection. As the add method is the only way for an element to get into the collection, we are guaranteed that all elements held in our SortedArrayCollection can be compared to each other. If a client class ignores the contract then it is likely that an exception will be thrown when they use the class.

The SortedArrayCollection class implements the CollectionInterface using an array. For this class we are concerned about the order in which we keep elements stored—the array must be kept sorted. Nevertheless, the implementation of the SortedArrayCollection class has much in common with the implementation of the ArrayCollection class developed in Section 5.2 “Array-Based Collection Implementation,” so we do not provide complete code listings here. The code for the new class can be found in the ch05.collections package. A few notes follow.

• As already mentioned, this implementation is unbounded, using a protected enlarge method as needed to increase the size of the internal representation array by the original capacity.

• The class includes a protected find method that serves the same function as the find method of the ArrayCollection class—search the collection for an occurrence of an element that is equal to the target element, and if successful set the instance variable found to true and set the instance variable location to the index where the target was found. For this class, however, the find method makes use of the binary search algorithm to provide excellent efficiency. The recursive approach to the binary search algorithm described in Section 3.3, “Recursive Processing of Arrays,” is used.

• During the search process the compareTo operation is used. Therefore, within the find method we must cast elements as Comparable, so that the Java compiler will accept our use of the compareTo method. Some compilers will generate a warning message regarding an unchecked call to compareTo, because there is no way for the compiler to verify that the generic type T will actually implement Comparable. Because we understand the reason for the warning message and because our precondition prohibits the use of elements that do not implement Comparable, we can safely ignore the compiler warning. An application that ignores the precondition and adds elements to the SortedArrayCollection that are not Comparable will cause a type mismatch exception to be thrown—which is exactly the result we desire because incomparable elements should not be added to a sorted collection.

• Unlike with the ArrayCollection class we cannot simply add a new element in the next available location of the array. So that the add method can also make use of the find method, to determine where the new element should be inserted, the find method of the SortedArrayCollection class has additional functionality. In the case of an "unsuccessful" search, the find method sets the instance variable found to false and sets the instance variable location to the index where the target should be inserted.

• Once the index where the addition of the new element is identified, the add method creates room for the new element by shifting all of the elements from that index through the end of the collection, one index higher, and then inserts the new element in the free slot that is created:

  

  The code for the add method is as follows:

  public boolean add(T element)
  // Precondition:  element is Comparable to previously added objects
  //
  // Adds element to this collection.
  {
    if (numElements == elements.length)
      enlarge();
  
    find(element); // sets location to index where element belongs
  
    for (int index = numElements; index > location; index--)
      elements [index] = elements[index - 1];
  
    elements [location] = element;
    numElements++;
    return true;
  }

  Note that since the SortedArrayCollection is unbounded the add method always returns true—it should always be able to add the given element successfully.

• Similarly, the remove method shifts elements one index lower in order to remove the targeted element without disrupting the already sorted array.

  

When designing an ADT, such as for a stack, queue, or collection, we have a choice about how to handle the elements—“by copy” or “by reference.”

public void add (T element)
// Adds a copy of the element to this collection
{
  elements[numElements] = element.clone();
  numElements++;
}

public T get(T target)
// Returns a copy of element e from this collection such that e.equals(target);
// if no such element exists, returns null.
{
  find(target);
  if (found)
    return elements[location].clone();
  else
    return null;
}

public void add (T element)
// Adds an element to this collection
{
  elements[numElements] = element;
  numElements++;
}

An Example

The diagrams in Figure 5.2 show the ramifications of both approaches. Suppose we have objects that hold a person’s name and weight. Further suppose that we have a collection of these objects sorted by the variable weight. We add three objects into the collection, and then transform one of the objects with a diet method that changes the weight of the object. The left side of the figure models the approach of storing references to copies of the objects—the “by copy” approach. The right side models the approach of storing references to the original objects—the “by reference” approach.

The middle section of the figure, showing the state of things after the objects have been inserted into the collections, clearly demonstrates the differences in the internal implementations. The “by copy” approach creates copies and the collection elements reference them; these copies take up space that is not required in the “by reference” approach. It is also clear from the right side of the figure that the “by reference” approach creates aliases for the objects, as we can see more than one reference to an object. In both approaches, the collection elements are kept sorted by weight.

The situation becomes more interesting when we modify one of the objects. When the person represented by the S1 object loses some weight, the diet method is invoked to decrease the weight of the object. In this scenario, both approaches display problems. In the “by copy” approach, we see that the S1 object has been updated. The copy of the S1 object maintained in the collection is clearly out of date. It holds the old weight value. A programmer must remember that such a collection stores only the values of objects as they existed at the time of the add operation and that changes to those objects are not reflected in the objects stored on the collection. The programmer must design the code to update the collection, if appropriate.

In the “by reference” approach, the object referred to by the collection contains the up-to-date weight information, because it is the same object referred to by the S1 variable. The collection, however, is no longer sorted by the weight attribute. Because the update to weight took place without any collection activity, the collection objects remain in the same order as before. The collection structure is now corrupt, and calls to the collection methods may behave unpredictably. Instead of directly updating the S1 object, the program should have removed the object from the collection, updated the object, and then reinserted it into the collection.

To provide evidence that our new collection implementation works correctly we return to the vocabulary density problem introduced in Section 5.3, “Application: Vocabulary Density.” The application developed in that section used the ArrayCollection class:

CollectionInterface<String> words =
                             new ArrayCollection<String>(CAPACITY);

The only thing we need to do, to use our new implementation, is to change the above line to use the SortedArrayCollection class:

CollectionInterface<String> words =
                             new SortedArrayCollection<String>(CAPACITY);

To compare the two approaches in terms of time efficiency we used a suite of text files, most obtained from the Project Gutenberg website, as input to both versions of the application. We timed the programs using the currentTimeMillis method of the Java Library System class. Although this approach to measuring execution time is not extremely precise, it is good enough for our purposes here.

See Table 5.1 for the results of our experiment. The text files are presented in the table from smallest to largest. The “Linux Word File” is an alphabetical list of words used by the Linux Operating System’s spell-checker program. It has the lowest density, essentially 1 (due to some words, for example “unix,” being repeated in the file with different capitalization schemes, the number of words and number of unique words are not exactly the same). Other than that special case, the density tends to increase as the size of the file increases, as is expected. The “Mashup” file is a concatenation of 121 files from the Gutenberg site consisting of all the other files on the list (except the Linux Word File) plus other novels, “complete works,” dictionaries, and technical manuals including Spanish, French, and German language texts in addition to the English.

Before running the program on a particular text file we made sure that the instantiated collection would be large enough to hold all of the unique words in the file—this way we guaranteed that the bounded ArrayCollection was able to handle the problem and we did not “penalize” the unbounded SortedArrayCollection for time spent enlarging its internal storage.

The benefits of the sorted array approach are clear from the table. As the size of the input increases, the fast performance of the binary search used by the SortedArrayCollection as compared to the sequential search used by the ArrayCollection become obvious. This is most evident in the comparison of times for the large Mashup file, with the array-based approach requiring over 10 hours and the sorted array approach taking only 7 minutes, on the author’s desktop computer.

As we did for our link-based stacks and queues, we again use the LLNode class from the support package to provide our nodes. The information attribute of a node contains the collection element; the link attribute contains a reference to the node holding the next collection element. We maintain a variable, head of type LLNode<T> that references the first node in the linked list. This linked list acts as the internal representation for the collection. It is an unsorted linked list. The start of the class is

package ch05.collections;
import support.LLNode;

public class LinkedCollection<T> implements CollectionInterface<T>
{
  protected LLNode<T> head;        // head of the linked list
  protected int numElements = 0;   // number of elements in this collection

  // set by find method
  protected boolean found;         // true if target found, else false
  protected LLNode<T> location;    // node containing target, if found
  protected LLNode<T> previous;    // node preceding location

  public LinkedCollection()
  {
    numElements = 0;
    head = null;
  }

There is only one constructor provided for LinkedCollection. There is no need to deal with capacity as there was with the array-based implementations. The constructor sets the instance variables numElements and head, essentially constructing an empty collection.

Why do we need a numElements instance variable? Recall that in the array-based approach, the numElements variable was used to indicate the first empty array location. Because we are now using a linked list, we do not have array locations. Nevertheless, to support the size operation we still maintain numElements, incrementing it whenever an element is added to the collection and decrementing it whenever an element is removed. The size method simply returns the value of numElements just as it does in ArrayCollection. The isEmpty method also remains unchanged from the array-based approach and the isFull method just trivially returns false because our linked structure is never full.

The add method is passed an argument of class T, and adds it to the collection. Because the internal linked list is unsorted, and order of the elements is not important, we can just add new elements to the front of the linked list. This is the easiest, most efficient approach, because head already provides a reference to this location. The code for the add method is very similar to that of the push method in the LinkedStack class developed in Section 2.8, “A Link-Based Stack.” Note that since our LinkedCollection is unbounded, the add method always returns the value true—it should always be able to add the given element successfully.

public boolean add(T element)
// Adds element to this collection.
{
  LLNode<T> newNode = new LLNode<T>(element);
  newNode.setLink(head);
  head = newNode;
  numElements++;
  return true;
}

As we did for both the unsorted and sorted array-based implementation approaches, we create a protected helper method for our linked approach and call it find. Recall that this method sets the values of the instance variables found and location, which can then be used by the other methods. Given that the find method works correctly, coding both the contains and get methods become easy—in fact they are exactly the same as their counterparts in the array-based implementations:

public boolean contains (T target)      public T get(T target)
{                                       {
  find(target);                           find(target);
  return found;                           if (found)
}                                           return location.getInfo();
                                          else
                                            return null;
                                        }

The protected find method is also used by the remove method—we discuss remove below. For now, let us consider find in more detail. It follows the same algorithm as the find method of the array-based implementation: Walk through the internal representation of elements until the target element is found or the end of the representation is reached. The only difference is the use of linked list statements instead of array-related statements. Here is the code for both methods, for comparison. In the array-based approach, location is of type int, indicating the array index of the target element; in the link-based approach, location is an LLNode, indicating the node containing the target element.

protected void find(T target)
{
  location = 0;
  found = false;
  while (location < numElements)
  {
    if (elements[location].equals(target))
    {
      found = true;
      return;
    }
    else
      location++;
  }
}

Link-Based

protected void find(T target)
{
  location = head;
  found = false;
  while (location != null)
  {
    if (location.getInfo().equals(target))
     {
      found = true;
      return;
    }
    else
    {
      previous = location;
      location = location.getLink();
    }
  }
}

Actually, we lied. There is another difference between the two find implementations. Do you see it? The link-based implementation assigns a value to a variable named previous that is not mentioned in the array-based implementation. This variable is used by the LinkedCollection remove method. We will take a closer look now at this method.

To remove the target, we must first find it. We do so using the find method, which sets the location variable to indicate the target element. As shown in Figure 5.3, however, to actually remove the node referenced by location, we must change the reference in the previous node. That is, we must change the link of the previous node to reference the node following the one being removed. We “jump over” the removed node. This is where we use the previous variable.

Not only does find set location, but it also sets previous so that the remove method has access to the previous node and can implement the “jump over” step. This is accomplished by remove with the statement:

previous.setLink(location.getLink());

Removing the first node must be treated as a special case because the main reference to the linked list (head) must be changed. We handle that special case with an if statement at the beginning of the code for remove. Is removing the last node a special case that requires additional code? No. The link within the last node is null. Therefore, in the case of removing the last node the above statement correctly sets the value of the link of the previous node to null, indicating that it is now the end of the list. Here is remove:

public boolean remove (T target)
// Removes an element e from this collection such that e.equals(target)
// and returns true; if no such element exists, returns false.
{
  find(target);
  if (found)
  {
    if (head == location)
      head = head.getLink();    // remove first node
    else
      previous.setLink(location.getLink());  // remove node at location

    numElements--;
  }
  return found;
}

We have now looked at several different implementations of the Collection ADT. How do they compare? Let us briefly review each implementation—a summary of this discussion is found in Table 5.2.

All three implementation approaches, the ArrayCollection, SortedArrayCollection, and LinkedCollection, maintain an instance variable numElements that holds the current size of the collection. This allows simple O(1) implementations of the size, isEmpty, and isFull operations.

Our ArrayCollection implementation is a bounded implementation. It is the responsibility of the client to indicate the capacity of an ArrayCollection object at instantiation. If an add operation is invoked on a full collection the add operation returns false and there is no change to the collection. A client must therefore ensure the initial capacity is large enough to handle the problem they are addressing. Being an array-based implementation the constructor is an O(N) operation, where N indicates the capacity—for any particular collection object we only execute the constructor once. The array in this implementation is unsorted—meaning the add operation is trivial and is O(1), whereas to locate a target element in the array for the contains, get, and remove operations requires a O(N) sequential search.

The SortedArrayCollection is also an array-based implementation; however, in this case we decided to make it an unbounded array-based implementation. If an add operation is invoked when the array is full then additional space is created using the enlarge method. This approach relieves the client of the responsibility of predetermining the needed capacity. Keeping the internal array sorted requires a more complex add method with a cost of O(N). However, it also means that the cost of locating a target element is now O(log₂N) as we can use the binary search algorithm. This significantly lowers the time cost of both contains and get.

Capacity is not a concern for the LinkedCollection. In this unbounded implementation the amount of space used to hold the collection grows and shrinks along with the collection. As we pointed out when discussing linked implementations previously, we do require two reference variables for each element in the collection—one to hold the link and one to reference the collection element. The constructor for the LinkedCollection simply initializes the instance variables. Other than the constructor, the efficiency of the unsorted linked list approach is the same as that of the unsorted array approach. For both approaches it makes no difference where we add an element so the add method is fast. On the other hand, searching for a target element requires traversing the collection element by element.

It is not surprising that the Java platform includes a "Collections Framework"—a unified architecture of classes and interfaces that provides powerful, flexible tools for storing and retrieving information. At the center of the framework is the Collection interface, found in the java.util package of the library. This interface supports 11 subinterfaces including Deque, List, and Set and has 33 implementing classes including the somewhat familiar ArrayList, LinkedList, Stack, and PriorityQueue and exotic-sounding classes such as BeanContextServicesSupport and RoleUnresolvedList.

There are 15 abstract methods defined within the Java Collection interface, including methods that mirror our isEmpty, size, add, remove, and contains methods. Note, however, that the interface does not define anything analogous to our get method. So how is one supposed to retrieve information from a collection? The answer is that the designers of the Collections Framework do not intend for anyone to directly implement the Collection interface. Instead it is used as the root of an inheritance tree of interfaces as previously mentioned, and it is those interfaces that are implemented. Various methods similar to our get method are defined within those interfaces.

It is instructive to look at some of the additional method definitions from the Collection interface:

Methods such as equals, addAll, retainAll, and removeAll allow clients to use collections as more than just separate repositories—collections can be combined and compared. The Set ADT we define below is a collection intended to be used in that fashion.

As mentioned in Chapter 2, in this text we do not cover the Collections Framework in great detail. This text is meant to teach you about the fundamental nature of data structures and to demonstrate how to define, implement, and use them. It is not an exploration of how to use Java’s specific library architecture of similar structures. If you are interested in learning more about the Java Collections Framework, you can study the extensive documentation available at Oracle’s website.

We want to define an ADT that fits our everyday notion of a bag—a bag of marbles, a bag of groceries, a bag of money! What assumptions should we make about our bag? What operations should we include?

Think about a bag of marbles. Suppose marbles are identified by their color. It certainly is possible to place more than one red marble into our bag—we decide that our Bag ADT should allow duplicate elements.

We can put marbles into the bag, look into the bag to see if it contains a particular marble (“is there a green marble in there?”) and reach in and remove a specific marble. These activities correspond to our Collection ADT’s add, contains, and remove operations. We can check to see if the bag is full or is empty and we could look inside and count how many marbles it contains—our isFull, isEmpty, and size operations. With a bit of a stretch of imagination we can think about reaching into the bag and pointing to a marble (which is essentially what our get operation does). In short, all of the operations we defined for our Collection ADT also make sense for our Bag ADT.

What other operations can we include? We could close our eyes and reach into the bag and draw out a random marble (“I hope I get the blue one”). We could peek into the bag and count all marbles of a specified color (“How many red ones are there?”) or remove all marbles of a specified color (“I don’t like the purple ones”). We could turn the bag upside down and empty it (“Watch out, here they come!”). We will add grab, count, removeAll, and clear to our Bag operations. Their formal definitions are included in our BagInterface listed below. As with our Collection ADT, our Bag ADT requires a valid equals method to be defined for the objects that it contains.

//---------------------------------------------------------------------------
// BagInterface.java           by Dale/Joyce/Weems                  Chapter 5
//
// Interface for a class that implements a bag of T.
// A bag is a collection that supports a few extra operations.
//---------------------------------------------------------------------------
package ch05.collections;

public interface BagInterface<T> extends CollectionInterface<T>
{
  T grab();
  // If this bag is not empty, removes and returns a random element of the
  // bag; otherwise returns null.

  int count(T target);
  // Returns a count of all elements e in this collection such that
  // e.equals(target).

  int removeAll(T target);
  // Removes all elements e from this collection such that e.equals(target)
  // and returns the number of elements removed.

  void clear();
  // Empties this bag so that it contains zero elements.
}

As you can see, the BagInterface is located in the ch05.collections package. The interface extends our CollectionInterface. Any class that implements BagInterface must provide concrete methods for the add, get, contains, remove, isFull, isEmpty, and size operations of the CollectionInterface in addition to the grab, count, removeAll, and clear operations that are explicitly listed in the interface.

The Bag ADT is suited for use by applications that need to be able to count specific elements in a collection or remove all of a specific element from a collection—perhaps applications that manage inventories or allow distribution of resources. Additionally, the unique grab operation allows the Bag ADT to be used for applications that require randomness, for example, games or tutorial programs. Implementation of the Bag ADT is left as an exercise.

A feature of each of our collection ADTs so far is that they allow duplicate elements. If we change our approach, that is, if we disallow duplicate elements, we have a collection commonly known as a Set. The Set ADT models the mathematical set that is typically defined as a collection of distinct objects.

We can implement a Set class by copying and changing the code from one of our collection implementations—the only method we need to change is the add method. The new add method could be designed to check if the element argument is not already in the collection, and if not it would add the element and return true. Otherwise, of course, it returns false.

Instead of copying the code from one of our implementations is there another way we can reuse it? Yes, in fact, there are two common approaches. We can extend the implementation class or we can wrap an object of the class within the new implementation. Let us investigate each approach.

The BasicSet1 class below extends the LinkedCollection. Therefore, it inherits all of the methods of the LinkedCollection. To ensure that duplicate elements are not entered into the collection we redefine the add method as discussed above. Applications that instantiate a BasicSet1 object and use it to invoke the add method will use the safe add method, that prevents duplicate elements from being added, rather than the overridden method from the LinkedCollection class, which allows duplicates.

//---------------------------------------------------------------------------
// BasicSet1.java              by Dale/Joyce/Weems                  Chapter 5
//
// Implements the CollectionInterface by extending LinkedCollection.
// Overrides add method so that duplicate elements are not added.
//
// Null elements are not allowed.
// One constructor is provided, one that creates an empty collection.
//---------------------------------------------------------------------------
package ch05.collections;

public class BasicSet1<T> extends LinkedCollection<T>
                          implements CollectionInterface<T>
{
  public BasicSet1()
  {
    super();
  }

  @Override
  public boolean add(T element)
  // If element is not already contained in this collection adds element to
  // this collection and returns true; otherwise returns false.
  {
    if (!this.contains(element))
    {
      super.add(element);
      return true;
    }
    else
      return false;
  }
}

As you can see, the BasicSet1 class code is short and was easy to create owing to the effort already expended in the design and creation of the LinkedCollection class.

A drawback of the above approach is that future changes to the LinkedCollection implementation could invalidate the unique element provision of its BasicSet1 subclass. For example, suppose the LinkedCollection was enhanced with the following method:

public void addAll(LinkedCollection elements)
// Adds all the contents of the elements collection to this collection.

Because BasicSet1 inherits from LinkedCollection, this new method would be available to BasicSet1 objects. If the maintenance programmer does not update BasicSet1 to override addAll, then the integrity of BasicSet1 would be compromised as it is possible that addAll could be used to add duplicate elements.

Let us look at another reuse approach that does not suffer from this drawback. Rather than extending LinkedCollection we can use a LinkedCollection object inside our new basic set implementation. This approach is sometimes called “wrapping” because, similar to the Java wrapper classes such as Integer, we hold an object of one type within an object of another type and delegate calls to it. Here is the code:

//---------------------------------------------------------------------------
// BasicSet2.java             by Dale/Joyce/Weems                   Chapter 5
//
// Implements the CollectionInterface by wrapping a LinkedCollection.
// Ensures that duplicate elements are not added.
//
// Null elements are not allowed.
// One constructor is provided, one that creates an empty collection.
//---------------------------------------------------------------------------
package ch05.collections;

public class BasicSet2<T> implements CollectionInterface<T>
{
  LinkedCollection<T> set;

  public BasicSet2()
  {
    set = new LinkedCollection<T>();
  }
  public boolean add(T element)
  // If element is not already contained in this collection adds element to
  // this collection and returns true; otherwise returns false.
  {
    if (!this.contains(element))
    {
      set.add(element);
      return true;
    }
    else
      return false;
  }

  public int size(){return set.size();}
  public boolean contains (T target){return set.contains(target);}
  public boolean remove (T target){return set.remove(target);}
  public T get(T target){return set.get(target);}
  public boolean isEmpty(){return set.isEmpty();}
  public boolean isFull(){return set.isFull();}
}

The only instance variable in the BasicSet2 class is the variable set of type LinkedCollection. In the case of every method provided, except for the add method, the method just invokes the corresponding method of LinkedCollection through the set variable. In the case of add the corresponding LinkedCollection add is also invoked but only if it is safe to do so. Although BasicSet2 is longer than BasicSet1, it does not require more work to create since the only method requiring extra code is the add method—as was also the case for BasicSet1. Furthermore, BasicSet2 does not suffer from the maintenance issue discussed above for BasicSet1. Our BasicSet2 class is a good example of a hierarchical implementation. It is built on top of the LinkedCollection class that in turn uses the LLNode class.

It is possible to define a more complex Set ADT, one that supports the set operations we learned in mathematics classes such as union and intersection. Exercise 36 asks the reader to define and implement such an ADT.

1. For each of the methods declared in CollectionInterface, identify what type of operation it is (observer, transformer, or both).

2. CollectionInterface defines seven abstract methods. Define at least three more operations that might be useful for a Collection ADT to provide.

3. Identify which attributes would make a good key for determining equality of objects for each of the following classes and explain your reasoning:

   1. A Golfer class that supports finding the latest score of your favorite golfer.

   2. A Student class for use by a university accounting office that includes name, ID number, and payment attributes.

   3. A Rectangle class with attributes length, width, area, and perimeter.

   4. A Book class for an online store that includes book name, author name, edition number, cost, and number of pages attributes.

4. Discuss the ramification of dropping the “null elements are not allowed” general precondition of CollectionInterface.

5. Discuss the difference between an operation that pushes an element onto a full (bounded) stack as defined by our StackInterface (Section 2.4, “The Stack Interface”) and one that adds an element to a full collection.

6. Show the values contained in the instance variables elements and numElements of the sample collection after the following sequence of operations:

   ArrayCollection<String> sample = new ArrayCollection<String>;
   sample.add("A"); sample.add("B"); sample.add("C"); sample.add("D");
   sample.remove("B");

7. Describe the ramifications of each of the following changes to ArrayCollection:

   1. the first three lines of the add method are deleted

   2. the numElements++ statement is deleted from the add method

   3. in the find method “protected” is changed to “public”

   4. in the find method “<” is changed to “<=”

   5. the elements[numElements – 1] = null statement is deleted from the remove method

   6. the “==” in the isEmpty method is changed to “=”

   7. in the get method, “found” is changed to “!found”

8. Add the following methods to the ArrayCollection class, and create a test driver for each to show that they work correctly. In order to practice your array coding skills, code each of these methods by accessing the internal variables of the ArrayCollection, not by calling the previously defined public methods of the class.

   1. String toString() creates and returns a string that correctly represents the current collection. Such a method could prove useful for testing and debugging the class and for testing and debugging applications that use the class. Assume each stored element already provides its own reasonable toString method.

   2. int count(T target) returns a count of the number of elements e in the collection such that e.equals(target) is true.

   3. void removeAll(T target) removes all elements e from the collection such that e.equals(target) is true.

   4. ArrayCollection<T> combine(ArrayCollection<T> other) creates and returns a new ArrayCollection object that is a combination of this object and the argument object.

9. What would be the result of using the ArrayCollection class to hold objects of a class that has not overridden the equals method of the Object class?

10. The Vocabulary Density application allows you to analyze text, reporting on the total number of words, the number of unique words, and the vocabulary density. Use it to analyze one or more texts of your choice. Create a report on the results. This is a wide open exercise—we leave it up to you to figure out something interesting to analyze.

11. Study the Vocabulary Density application and answer the following questions:

    1. How is the name and location of the input file provided to the program?

    2. What happens if the input text contains more than CAPACITY unique words?

    3. What would be the effect of removing the ’ (apostrophe) from the delimiters definition?

    4. What is the effect of removing the “word = word.toLowerCase()” statement?

12. Revise the Vocabulary Density application so that

    1. if the collection becomes full, then the application no longer continues processing—instead it displays a suitable message and then ends.

    2. it includes a constant THRESHOLD of type int and ignores words whose length is less than the threshold value—thus the word analysis would not include “short” words.

    3. it permits multiple filenames to be passed as command line arguments, and will proceed to separately analyze and report on each of the files.

    4. expand on the previous revision so that in addition to the separate analysis of the files it also performs a combined analysis, as if the combined files all represented a single text.

13. The file Animals.txt found in the input folder contains a long list of animal names, one per line. Create an application that reads that file and creates a collection of animal names. Use the ArrayCollection class. Your application should then generate a random character and challenge the user to repeatedly enter an animal name that begins with that character, reading the names entered by the user until they either enter a name that does not begin with the required character or is not in the collection, or they enter a name they used before. Finally, your application reports how many names they successfully entered.

14. The file Keywords.txt found in the input folder contains all the Java keywords. Create an application that accepts the name of a Java program file as a command line argument and displays a count of the total number of keywords the program contains. For example, if you use the VocabularyDensity.java program as your input, the application should display

    
    VocabularyDensity.java contains 24 Java keywords

    As part of your solution you should create a collection of keywords using the information in the Keywords.txt file. Do not worry about the fact that you might be counting keywords contained within comments or strings.

15. Based on the equals method for Circle objects defined in Section 5.4, “Comparing Objects Revisited,” what is the output of the following code sequence?

    Circle c1 = new Circle(5);
    Circle c2 = new Circle(5);
    Circle c3 = new Circle(15);
    Circle c4 = null;
    System.out.println(c1 == c1);
    System.out.println(c1 == c2);
    System.out.println(c1 == c3);
    System.out.println(c1 == c4);
    System.out.println(c1.equals(c1));
    System.out.println(c1.equals(c2));
    System.out.println(c1.equals(c3));
    System.out.println(c1.equals(c4));

16. An equals method is supposed to provide an equivalence relation among the objects of a class. This means that if a, b, and c are non-null objects of the class, then

    1. a.equals(a) is true.

    2. a.equals(b) has the same value as b.equals(a).

    3. If a.equals(b) is true and b.equals(c) is true, then a.equals(c) is true.

    State whether the following definitions of equals are valid. If they are not, explain why not.

    1. Two circles are equal if they have the same area.

    2. Two circles are equal if their radii are within 10% of each other.

    3. Two integers are equal if they have the same remainder when divided by a specific integer, for example, when divided by 3.

    4. Two integers are equal if the second integer is a multiple of the first.

17. Suppose we have a Rectangle class that includes length and width attributes, of type int, both set by the constructor. Define an equals method for this class so that two rectangle objects are considered equal if

    1. They have the exact same length and width.

    2. They have the same dimensions—that is, they are congruent.

    3. They have the same shape—that is, they are similar.

    4. They have the same perimeter.

    5. They have the same area.

18. Which of the definitions of equals listed in Exercise 17 is valid, based on the criteria listed in Exercise 16?

19. Based on the compareTo method for FamousPerson objects defined in Section 5.4, “Comparing Objects Revisited,” what is the output of the following code sequence? Answers may include phrases such as “a negative integer.”

    FamousPerson f1 = new FamousPerson("Peter","Parker",1962,"Spiderman");
    FamousPerson f2 = new FamousPerson("Bonnie","Parker",1910,"Criminal");
    FamousPerson f3 = new FamousPerson("Clark","Kent",1938,"Superman");
    FamousPerson f4 = new FamousPerson("Clark","Kent",1938,"Reporter");
    System.out.println(f1.compareTo(f1));
    System.out.println(f1.compareTo(f2));
    System.out.println(f2.compareTo(f1));
    System.out.println(f1.compareTo(f3));
    System.out.println(f3.compareTo(f4));
    System.out.println(f4.compareTo(f3));

20. In Exercise 16 we stated some rules for the behavior of the equals method. What similar rule or rules should the compareTo method follow?

21. Suppose we have a Rectangle class that includes length and width attributes of type int, both set by the constructor. Create a compareTo method for this class so that rectangle objects are ordered based on their

    1. Perimeter.

    2. Area.

22. How many “known” classes in the Java library implement the Comparable interface? List five such classes that you have used before, or at least have studied.

23. Show the values contained in the instance variables elements and numElements of the sample collection after the following sequence of operations:

    SortedArrayCollection<String> sample
                = new SortedArrayCollection<String>;
    sample.add("A"); sample.add("D"); sample.add("B"); sample.add("C");
    sample.remove("B");

24. Fill in the following table with the order of growth of the indicated operations for the given implementation approach—assume the collection holds N elements:

    operation	ArrayCollection	SortedArrayCollection add
    get
    contains
    remove
    isEmpty

25. Describe the ramifications of each of the following changes to SortedArrayCollection:

    1. in the enlarge method "origCap" is changed to "DEFCAP"

    2. the first two statements are deleted from the find method

    3. the if (result > 0) location++ statement is deleted from the recFind method

26. Add the following methods to the SortedArrayCollection class, and create a test driver for each to show that they work correctly. Code each of these methods by accessing the internal variables of the SortedArrayCollection, not by calling the previously defined methods of the class.

    1. String toString() creates and returns a string that correctly represents the current collection. Such a method could prove useful for testing and debugging the class and for testing and debugging applications that use the class. Assume each stored element already provides its own reasonable toString method.

    2. T smallest() returns null if the collection is empty, otherwise returns the smallest element of the collection.

    3. int greater(T element) returns a count of the number of elements e in the collection that are greater than element, that is such that e.compareTo (element) is > 0.

    4. SortedArrayCollection<T> combine(SortedArrayCollection<T> other) creates and returns a new SortedArrayCollection object that is a combination of this object and the argument object.

27. Describe the functional difference between the following two sections of code:

    CollectionInterface<String> c = new ArrayCollection<String>(10);
    c.add("Tom"); c.add("Julie"); c.add("Molly");
    System.out.println(c.contains("Kathy");
    
    CollectionInterface<String> c = new SortedArrayCollection<String>(10);
    c.add("Tom"); c.add("Julie"); c.add("Molly");
    System.out.println(c.contains("Kathy");

28. Show the values contained in the instance variables head and numElements of the sample collection after the following sequence of operations:

    LinkedCollection<String> sample = new LinkedCollection<String>;
    sample.add("A"); sample.add("B"); sample.add("C"); sample.add("D");
    sample.remove("B");

29. Describe the ramifications of each of the following changes to LinkedCollection:

    1. the statement newNode.setLink(head) is deleted from the add method

    2. the statement location = location.getLink() is deleted from the find method

    3. the statement head = head.getLink() within the remove method is changed to head = location.getLink()

30. Add the following methods to the LinkedCollection class, and create a test driver for each to show that they work correctly. Code each of these methods by accessing the internal variables of the LinkedCollection, not by calling the previously defined methods of the class.

    1. String toString() creates and returns a string that correctly represents the current collection. Such a method could prove useful for testing and debugging the class and for testing and debugging applications that use the class. Assume each stored element already provides its own reasonable toString method.

    2. int count(T target) returns a count of the number of elements e in the collection such that e.equals(target) is true.

    3. void removeAll(T target) removes all elements e from the collection such that e.equals(target) is true.

    4. LinkedCollection<T> combine(LinkedCollection<T> other) creates and returns a new SortedArrayCollection object that is a combination of this object and the argument object.

31. Create a new collection class named SortedLinkedCollection that implements a collection using a sorted linked list. Include a toString method as described in Exercise 30a. Include a test driver application that demonstrates your class works correctly.

32. Recreate the contents of Table 5.2 (no peeking).

33. Create a class that implements the BagInterface, plus a test driver that shows that your class operates correctly:

    1. Using an unsorted array (if you like, you can extend the ArrayCollection class)

    2. Using a sorted array (if you like, you can extend the SortedArrayCollection class)

    3. Using a linked list (if you like, you can extend the LinkedCollection class)

34. Create an application that creates a Bag of FamousPerson using one of your implementation classes from Exercise 33. Your application should use the information in the input/FamousCS.txt file (see Section 5.4, “Comparing Objects Revisited”) to create the Bag. Next your application will repeat the following five times:

    • selects a random “famous person” from the bag

    • tells the user the year of birth and the fact about the person

    • asks the user to enter the last name of the famous person and reads their response

    • display all the information about the famous person

    Finally, your application tells the user how many they “got right” out of the five chances, that is, how many famous people they correctly identified.

35. Describe the three approaches discussed in the section to reuse the LinkedCollection class in the creation of a Basic Set ADT implementation.

36. An Advanced Set includes all the operations of a Basic Set plus operations for the union, intersection, and difference of sets.

    1. Define an Advanced Set interface.

    2. Implement the Advanced Set using an unsorted array; include a test driver that demonstrates your implementation works correctly.

    3. Implement the Advanced Set using a sorted array; include a test driver that demonstrates your implementation works correctly.

    4. Implement the Advanced Set using a linked list; include a test driver that demonstrates your implementation works correctly.