> ### Section 12.1
> Generic Programming

> GENERIC PROGRAMMING refers to writing code that will work for many types of data. We encountered the term in Section 8.3, where we looked at dynamic arrays of integers. The source code presented there for working with dynamic arrays of integers works only for data of type `int`. But the source code for dynamic arrays of `double`, `String`, `JButton`, or any other type would be almost identical. It seems silly to write essentially the same code over and over. As we saw in Section 8.3, Java goes some distance towards solving this problem by providing the `ArrayList` class. An `ArrayList` is essentially a dynamic array of values of type `Object`. Since every class is a sub-class of `Object`, objects belonging to any class can be stored in an `ArrayList`. This is an example of generic programming: The source code for the `ArrayList` class was written once, and it works for objects of any type. (It does, not, however, work for data belonging to the primitive types, such as `int` and `double`.)

> The `ArrayList` class is just one of several classes and interfaces that are used for generic programming in Java. We will spend this chapter looking at these classes and how they are used. All the classes discussed in this chapter are defined in the package `java.util`, and you will need an import statement at the beginning of your program to get access to them. (Before you start putting `import` `java.util.*` at the beginning of every program, you should know that some things in `java.util` have names that are the same as things in other packages. For example, both `java.util.List` and `java.awt.List` exist.)

> It is no easy task to design a library for generic programming. Java's solution has many nice features but is certainly not the only possible approach. It is almost certainly not the best, but in the context of the overall design of Java, it might be close to optimal. To get some perspective on generic programming in general, it might be useful to look very briefly at generic programming in two other languages.

> ### Generic Programming in Smalltalk

> Smalltalk was one of the very first object-oriented programming languages. It is still used today. Although it has not achieved anything like the popularity of Java or C++, it is the source of many ideas used in these languages. In Smalltalk, essentially all programming is generic, because of two basic properties of the language.

> First of all, variables in Smalltalk are typeless. A data value has a type, such as integer or string, but variables do not have types. Any variable can hold data of any type. Parameters are also typeless, so a subroutine can be applied to parameter values of any type. Similarly, a data structure can hold data values of any type. For example, once you've defined a binary tree data structure in SmallTalk, you can use it for binary trees of integers or strings or dates or data of any other type. There is simply no need to write new code for each data type.

> Secondly, all data values are objects, and all operations on objects are defined by methods in a class. This is true even for types that are "primitive" in Java, such as integers. When the "+" operator is used to add two integers, the operation is performed by calling a method in the integer class. When you define a new class, you can define a "+" operator, and you will then be able to add objects belonging to that class by saying "a + b" just as if you were adding numbers. Now, suppose that you write a subroutine that uses the "+" operator to add up the items in a list. The subroutine can be applied to a list of integers, but it can also be applied, automatically, to any other data type for which "+" is defined. Similarly, a subroutine that uses the "<" operator to sort a list can be applied to lists containing any type of data for which "<" is defined. There is no need to write a different sorting subroutine for each type of data.

> Put these two features together and you have a language where data structures and algorithms will work for any type of data for which they make sense, that is, for which the appropriate operations are defined. This is real generic programming. This might sound pretty good, and you might be asking yourself why all programming languages don't work this way. This type of freedom makes it easier to write programs, but unfortunately it makes it harder to write programs that are correct and robust. (See Chapter 9.) Once you have a data structure that can contain data of any type, it becomes hard to ensure that it only holds the type of data that you want it to hold. If you have a subroutine that can sort any type of data, it's hard to ensure that it will only be applied to data for which the "<" operator is defined. More particularly, there is no way for a compiler to ensure these things. The problem will show up at run time when an attempt is made to apply some operation to a data type for which it is not defined, and the program will crash.

> ### Generic Programming in C++

> Unlike Smalltalk, C++ is a very strongly typed language, even more so than Java. Every variable has a type, and can only hold data values of that type. This means that the type of generic programming used in Smalltalk is impossible. Furthermore, C++ does not have anything corresponding to Java's `Object` class. That is, there is no class that is a superclass of all other classes. This means that C++ can't use Java's style of generic programming either. Nevertheless, C++ has a powerful and flexible system of generic programming. It is made possible by a language feature known as templates. In C++, instead of writing a different sorting subroutine for each type of data, you can write a single subroutine template. The template is not a subroutine; it's more like a factory for making subroutines. We can look at an example, since the syntax of C++ is very similar to Java's:

>           template<class ItemType>
>           void sort( ItemType A[], int count ) {
>                 // Sort count items in the array, A, into increasing order.
>                 // The algorithm that is used here is selection sort.
>              for (int i = count-1; i > 0; i--) {
>                 int position_of_max = 0;
>                 for (int j = 1; j <= count ; j++)
>                    if ( A[j] > A[position_of_max] )
>                       position_of_max = j;
>                 ItemType temp = A[count];
>                 A[count] = A[position_of_max];
>                 A[position_of_max] = temp;
>              }
>           }

> This piece of code defines a subroutine template. If you remove the first line, "template<class ItemType>", and substitute the word "int" for the word "ItemType" in the rest of the template, you get a subroutine for sorting arrays of ints. (Even though it says "class ItemType", you can actually substitute any type for ItemType, including the primitive types.) If you substitute "string" for "ItemType", you get a subroutine for sorting arrays of strings. This is pretty much what the compiler does with the template. If your program says "sort(list,10)" where list is an array of ints, the compiler uses the template to generate a subroutine for sorting arrays of ints. If you say "sort(cards,10)" where cards is an array of objects of type Card, then the compiler generates a subroutine for sorting arrays of Cards. At least, it tries to. The template uses the ">" operator to compare values. If this operator is defined for values of type Card, then the compiler will successfully use the template to generate a subroutine for sorting Cards. If ">" is not defined for Cards, then the compiler will fail -- but this will happen at compile time, not, as in Smalltalk, at run time where it would make the program crash.

> C++ also has templates for making classes. If you write a template for binary trees, you can use it to generate classes for binary trees of ints, binary trees of strings, binary trees of dates, and so on -- all from one template. The most recent version of C++ comes with a large number of pre-written templates called the Standard Template Library or STL. The STL is quite complex. Many people would say that its much too complex. But it is also one of the most interesting features of C++.

> ### Generic Programming in Java

> Like C++, Java is a strongly typed language. However, generic programming in Java is closer in spirit to Smalltalk than it is to C++. As I've already noted, generic programming in Java is based on the fact that class `Object` is a superclass of every other class. To some extent, this makes Java similar to Smalltalk: A data structure designed to hold `Objects` can hold values belonging to any class. There is no need for templates or any other new language feature to support generic programming.

> Of course, primitive type values, such as integers, are not objects in Java and therefor cannot be stored in generic data structures. In fact, there is no way to do generic programming with the primitive data types in Java. The Smalltalk approach doesn't work except for objects, and the C++ approach is not available. Furthermore, generic subroutines are more problematic in Java than they are in either Smalltalk or C++. In Smalltalk, a subroutine can be called with parameter values of any type, and it will work fine as long as all the operations used by the subroutine are supported by the actual parameters. In Java, parameters to a subroutine must be of a specified type, and the subroutine can only use operations that are defined for that type. A subroutine with a parameter of type `Object` can be applied to objects of any type, but the subroutine can only use operations that are defined in class `Object`, and there aren't many of those! For example, there is no comparison operation defined in the `Object` class, so it is not possible to write a completely generic sorting algorithm. We'll see below how Java addresses this problem.

> Because of problems like these, some people (including myself) claim that Java does not really support true generic programming. Other people disagree. But whether it's true generic programming or not, that doesn't prevent it from being very useful.

> ### Collections and Maps

> Java's generic data structures can be divided into two categories: collections and maps. A collection is more or less what it sound like: a collection of objects. A map associates objects in one set with objects in another set in the way that a dictionary associates definitions with words or a phone book associates phone numbers with names. A map is similar to what I called an "association list" in Section 8.4.

> There are two types of collections: lists and sets. A list is a collection in which the objects are arranged in a linear sequence. A list has a first item, a second item, and so on. For any item in the list, except the last, there is an item that directly follows it. A set is a collection in which no object can appear more than once.

> Note that the terms "collection," "list," "set," and "map" tell you nothing about how the data is stored. A list could be represented as an array, as a linked list, or, for that matter, as a map that associates the elements of the list to the numbers 0, 1, 2, `...`. In fact, these terms are represented in Java not by classes but by interfaces. The interfaces `Collection`, `List`, `Set`, and `Map` specify the basic operations on data structures of these types, but do not specify how the data structures are to be represented or how the operations are to be implemented. That will be specified in the classes that implement the interfaces. Even when you use these classes, you might not know what the implementation is unless you go look at the source code. Java's generic data structures are abstract data types. They are defined by the operations that can be performed on them, not by the physical layout of the data in the computer.

> We will look at list and set classes in Section 2 and map classes in Section 3. But before we do that, we'll look briefly at some of the general operations that are available for all collections.

> ### Generic Algorithms and Iterators

> The `Collection` interface includes methods for performing some basic operations on collections of objects. Since "collection" is a very general concept, operations that can be applied to all collections are also very general. They are generic operations in the sense that they can be applied to various types of collections containing various types of objects. Suppose that `coll` is any object that implements the `Collection` interface. Here are some of the operations that are defined:

> - `coll.size()` -- returns an `int` that gives the number of objects in the collection.
> - `coll.isEmpty()` -- returns a boolean value which is `true` if the size of the collection is 0.
> - `coll.clear()` -- removes all objects from the collection.
> - `coll.contains(object)` -- returns a boolean value that is true if `object` is in the collection.
> - `coll.add(object)` -- adds `object` to the collection. The parameter can be any `Object`. Some collections can contain the value `null`, while others cannot. This method returns a boolean value which tells you whether the operation actually modified the collection. For example, adding an object to a `Set` has no effect if that object was already in the set.
> - `coll.remove(object)` -- removes `object` from the collection, if it occurs in the collection, and returns a boolean value that tells you whether the object was found.
> - `coll.containsAll(coll2)` -- returns a boolean value that is true if every `object` in `coll2` is also in the `coll`. The parameter can be any `Collection`.
> - `coll.addAll(coll2)` -- adds all the objects in the collection `coll2` to `coll`.
> - `coll.removeAll(coll2)` -- removes every `object` from `coll` that also occurs in the collection `coll2`.
> - `coll.retainAll(coll2)` -- removes every `object` from `coll` that does not occur in the collection `coll2`. It "retains" only the objects that do occur in `coll2`.
> - `coll.toArray()` -- returns an array of type `Object[]` that contains all the items in the collection. The return value can be type-cast to another array type, if appropriate. For example, if you know that all the items in `coll` are of type `String`, then `(String[])coll.toArray()` gives you an array of `Strings` containing all the strings in the collection.

> Since these methods are part of the `Collection` interface, they must be defined for every object that implements that interface. There is a problem with this, however. For example, the size of some kinds of `Collection` cannot be changed after they are created. Methods that add or remove objects don't make sense for these collections. While it is still legal to call the methods, an exception will be thrown when the call is evaluated at run time. The type of exception is `UnsupportedOperationException`.

> There is also the question of efficiency. Even when an operation is defined for several types of collections, it might not be equally efficient in all cases. Even a method as simple as `size()` can vary greatly in efficiency. For some collections, computing the `size()` might involve counting the items in the collection. The number of steps in this process is equal to the number of items. Other collections might have instance variables to keep track of the size, so evaluating `size()` just means returning the value of a variable. In this case, the computation takes only one step, no matter how many items there are. When working with collections, it's good to have some idea of how efficient operations are and to choose a collection for which the operations you need can be implemented most efficiently. We'll see specific examples of this in the next two sections.

> The `Collection` interface defines a few basic generic algorithms, but suppose you want to write your own generic algorithms. Suppose, for example, you want to do something as simple as printing out every item in a collection. To do this in a generic way, you need some way of going through an arbitrary collection, accessing each item in turn. We have seen how to do this for specific data structures: For an array, you can use a for loop to iterate through all the array indices. For a linked list, you can use a while loop in which you advance a pointer along the list. For a binary tree, you can use a recursive subroutine to do an infix traversal. Collections can be represented in any of these forms and many others besides. With such a variety of traversal mechanisms, how can we hope to come up with a single generic method that will work for collections that are stored in wildly different forms? This problem is solved by iterators. An iterator is an object that can be used to traverse a collection. Different types of collections have different types of iterators, but all iterators are used in the same way. An algorithm that uses an iterator to traverse a collection is generic, because the same technique can be applied to any type of collection. Iterators can seem rather strange to someone who is encountering generic programming for the first time, but you should understand that they solve a difficult problem in an elegant way.

> The `Collection` interface defines a method that can be used to obtain an iterator for any collection. If `coll` is a collection, then `coll.iterator()` returns an iterator that can be used to traverse the collection. You should think of the iterator as a kind of generalized pointer that starts at the beginning of the collection and can move along the collection from one item to the next. Iterators are defined by an interface named `Iterator`. This interface defines just three methods. If `iter` refers to an `Iterator`, then:

> - `iter.next()` -- returns the next item, and advances the iterator. The return value is of type `Object`. Note that there is no way to look at an item without advancing the iterator past that item. If this method is called when no items remain, it will throw a `NoSuchElementException`.
> - `iter.hasNext()` -- returns a boolean value telling you whether there are more items to be processed. You should test this before calling `iter.next()`.
> - `iter.remove()` -- if you call this after calling `iter.next()`, it will remove the item that you just saw from the collection. This might produce an `UnsupportedOperationException`, if the collection does not support removal of items.

> Using iterators, we can write code for printing all the items in any collection. Suppose that `coll` is of type `Collection`. Then we can say:

>                 Iterator iter = coll.iterator();
>                 while ( iter.hasNext() ) {
>                    Object item = iter.next();
>                    System.out.println(item);
>                 }

> The same general form will work for other types of processing. For example, here is a subroutine that will remove all `null` values from any collection (as long as that collection supports removal of values):

>                 void removeNullValues( Collection coll ) {
>                    Iterator iter = coll.iterator():
>                    while ( iter.hasNext() ) {
>                        Object item = iter.next();
>                        if (item == null)
>                           iter.remove();
>                    }
>                 }

> Collections can hold objects of any type, so the return value of `iter.next()` is `Object`. Now, there's not very much you can do with a general `Object`. In practical situations, a collection is used to hold objects belonging to some more specific class, and objects from the collection are type-cast to that class before they are used. Suppose, for example, that we are working with `Shapes`, where `Shape` is a class that represents geometric figures. Suppose that the `Shape` class includes a `draw()` method for drawing the figure. Then we can write a generic method for drawing all the figures in a collection of `Shapes`:

>                 void drawAllShapes( Collection shapeCollection ) {
>                       // Precondition: Every item in shapeCollection is non-null
>                       //               and belongs to the class Shape.
>                    Iterator iter = shapeCollection.iterator();
>                    while ( iter.hasNext() ) {
>                       Shape figure = (Shape)iter.next();
>                       figure.draw();
>                    }
>                 }

> The precondition of this method points out that the method will fail if the method contains an item that does not belong to class `Shape`. When that item is encountered, the type-cast "`(Shape)iter.next()`" will cause an exception of type `ClassCastException`. Although it's unfortunate that we can't have a "Collection of Shapes" in Java, rather than a "Collection of Objects", it's not a big problem in practice. You just have to be aware of what type of objects you are storing in your collections.

> ### Equality and Comparison

> The discussion of methods in the `Collection` interface had an unspoken assumption: It was assumed that it's known what it means for two objects to be "equal." For example, the methods `coll.contains(object)` and `coll.remove(object)` look for an item in the collection that is equal to `object`. However, equality is not such a simple matter. The obvious technique for testing equality -- using the `==` operator -- does not usually give a reasonable answer when applied to objects. The `==` operator tests whether two objects are identical in the sense that they share the same location in memory. Usually, however, we want to consider two objects to be equal if they represent the same value, which is a very different thing. Two values of type `String` should be considered equal if they contain the same sequence of characters. The question of whether those characters are stored in the same location in memory is irrelevant. Two values of type `Date` should be considered equal if they represent the same time.

> The `Object` class defines a boolean-valued method `equals(Object)` for testing whether one object is equal to another. For the purposes of collections, `obj1` and `obj2` are considered to be equal if they are both `null`, or if they are both non-`null` and `obj1.equals(obj2)` is `true`. In the `Object` class, `obj1.equals(obj2)` is defined to be the same as `obj1 == obj2`. However, for most sub-classes of `Object`, this definition is not reasonable, and it should be overridden. The `String` class, for example, overrides `equals()` so that for a `String` `str`, `str.equals(obj)` if `obj` is also a `String` and `obj` contains the same sequence of characters as `str`.

> If you write your own class, you might want to define an `equals()` method in that class to get the correct behavior when objects are tested for equality. For example, a `Card` class that will work correctly when used in collections could be defined as:

>             public class Card {  // Class to represent playing cards.
>                int suit;  // Number from 0 to 3 that codes for the suit --
>                           // spades, diamonds, clubs or hearts.
>                int value; // Number from 1 to 13 that represents the value.
>                public boolean equals(Object obj) {
>                    if (obj == null || ! (obj instanceof Card) ) {
>                          // obj can't be equal to this Card if obj
>                          // is not a Card, or if it is null.
>                       return false;
>                    }
>                    else {
>                       Card other = (Card)obj;  // Type-cast obj to a Card.
>                       if (suit == other.suit && value == other.value) {
>                             // The other card has the same suit and value as
>                             // this card, so they should be considered equal.
>                          return true;
>                       }
>                       else
>                          return false;
>                    }
>                }
>                 ... // other methods and constructors
>             }

> Without the `equals()` method in this class, methods such as `contains()` and `remove()` from the `Collection` interface will not work as expected for values of type `Card`.

> A similar concern arises when items in a collection are sorted. Sorting refers to arranging a sequence of items in ascending order, according to some criterion. The problem is that there is no natural notion of ascending order for arbitrary objects. Before objects can be sorted, some method must be defined for comparing them. Objects that are meant to be compared should implement the interface `java.lang.Comparable`. This interface defines one method:

>                 public int compareTo(Object obj)

> The value returned by `obj1.compareTo(obj2)` should be zero if and only if the objects are equal (that is, if `obj1.equals(obj2)` is true). It should be negative if and only if `obj1` comes before `obj2`, when the objects are arranged in ascending order. And it should be positive if and only if `obj1` comes after `obj2`. In general, it should be considered an error to call `obj1.compareTo(obj2)` if `obj2` is not of the same type as `obj1`. The `String` class implements the `Comparable` interface and defines `compareTo` in a reasonable way. If you define your own class and want to be able to sort objects belonging to that class, you should do the same. For example:

>           class FullName implements Comparable {
>                   // Represents a full name consisting of a first
>                   // name and a last name.
>              String firstName, lastName;
>              public boolean equals(Object obj) {
>                 if (obj == null || ! (obj instanceof FullName)) {
>                    return false;
>                 }
>                 else {
>                    FullName other = (FullName)obj;
>                    return firstName.equals(other.firstName)
>                                && lastName.equals(other.lastName);
>                 }
>              }
>              public void compareTo(Object obj) {
>                 Fullname other = (FullName)obj;
>                    // Will cause an error if obj is not a FullName.
>                 if ( lastName.compareTo(other.lastName) < 0 ) {
>                        // If lastName comes before the last name of
>                        // the other object, then this FullName comes
>                        // before the other FullName.  Return a negative
>                        // value to indicate this.
>                    return -1;
>                 }
>                 if ( lastName.compareTo(other.lastName) > 0 ) {
>                        // If lastName comes after the last name of
>                        // the other object, then this FullName comes
>                        // after the other FullName.  Return a positive
>                        // value to indicate this.
>                    return 1;
>                 }
>                 else {
>                        // Last names are the same, so base the comparison
>                        // on the first names.
>                    return firstName.compareTo(other.firstName);
>                 }
>              }
>               ... // other methods and constructors
>           }

> There is another way to allow for comparison of objects in Java, and that is to provide a separate object that is capable of making the comparison. The object must implement the interface `java.util.Comparator`, which defines the method:

>                 public int compare(Object obj1, Object obj2)

> This method compares two objects and returns a value that is negative, or zero, or positive depending on whether `obj1` comes before `obj2`, or is the same as `obj2`, or comes after `obj2`. Comparators are useful for comparing objects that do not implement the `Comparable` interface and for defining several different orderings on the same collection of objects.

> In the next two sections, we'll see how `Comparable` and `Comparator` are used in the context of collections and maps.

> ### Wrapper Classes

> As noted above, Java's generic programming does not apply to the primitive types. Before leaving this section, we should try to address this problem.

> You can't store an integer in a generic data structure designed to hold `Objects`. On the other hand, there is nothing to stop you from making an object that contains an integer and putting that object into the data structure. In the simplest case, you could define a class that does nothing but contain an integer:

>             public class IntContainer {
>                public int value;
>             }

> In fact, Java already has a class similar to this one. An object belonging to the class `java.lang.Integer` contains a single `int`. It is called a wrapper for that `int`. The `int` value is provided as a parameter to the constructor. For example,

>                 Integer val = new Integer(17);

> creates an `Integer` object that "wraps" the number 17. The `Integer` object can be used in generic data structures and in other situations where an object is required. The `int` value is stored in a `private` `final` instance variable of the `Integer` object. If `val` refers to an object of type `Integer`, you can find out what `int` it contains by calling the instance method `val.intValue()`. There is no way to change that value. We say that an `Integer` is an immutable object. That is, after it has been constructed, there is no way to change it. (Similarly, an object of type `String` is immutable.)

> There are wrapper classes for all the primitive types. All objects belonging to these classes are immutable. The wrapper class for values of type `double` is `java.lang.Double`. The value stored in an object of type `Double` can be retrieved by calling the instance method `doubleValue()`.

> The wrapper classes define a number of useful methods. Some of them exist to support generic programming. For example, the wrapper classes all define instance methods `equals(Object)` and `compareTo(Object)` in a reasonable way. Other methods in the wrapper classes are utility functions for working with the primitive types. For example, we encountered the static methods `Integer.parseInt(String)` and `Double.parseDouble(String)` in Section 7.4. These functions are used to convert strings such as "42" or "2.71828" into the numbers they represent.

[ Next Section | Chapter Index | Main Index ]