Generics chapter-12

Chapter 12

Generics

With generics you can write a parameterized type and create instances of it by passing a reference type or reference types. The objects will then be restricted to the type(s). For example, thejava.util.List interface is generic. If you create a List by passing java.lang.String, you'll get a List that will only store Strings; In addition to parameterized types, generics support parameterized methods too.

The first benefit of generics is stricter type checking at compile time. This is most apparent in the Collections Framework. In addition, generics eliminate most type castings you had to perform when working with the Collections Framework.

This chapter teaches you how to use and write generic types. It starts with the section “Life without Generics” to remind us what we missed in earlier versions of JDK—s. Then, it presents some examples of generic types. After a discussion of the syntax, this chapter concludes with a section that explains how to write generic types.

Life without Generics

All Java classes derive from java.lang.Object, which means all Java objects can be cast to Object. Because of this, in pre-5 JDK—s, many methods in the Collections Framework accept anObject argument. This way, the collections become general-purpose utility types that can hold objects of any type. This imposes unpleasant consequences.

For example, the add method of List in pre-5 JDK's takes an Object argument:

public boolean add(java.lang.Object element)

As a result, you can pass an object of any type to add. The use of Object is by design. Otherwise, it could only work with a specific type of objects and there would then have to be differentList types, e.g. StringList, EmployeeList, AddressList, etc.

The use of Object in add is fine, but consider the get method, that returns an element in a List instance. Here is its signature prior to Java 5.

public java.lang.Object get(int index)
        throws IndexOutOfBoundsException

get returns an Object. Here is where the unpleasant consequences start to kick in. Suppose you have stored two String objects in a List:

List stringList1 = new ArrayList();
stringList1.add("Java 5 and later");
stringList1.add("with generics");

When retrieving a member from stringList1, you get an instance of java.lang.Object. In order to work with the original type of the member element, you must first downcast it to String.

String s1 = (String) stringList1.get(0);

With generic types, you can forget about type casting when retrieving objects from a List. And, there is more. Using the generic List interface, you can create specialized Lists, like one that only accepts Strings.

Introducing Generic Types

Like a method, a generic type can accept parameters. This is why a generic type is often called a parameterized type. Instead of passing primitives or object references in parentheses as with methods, you pass reference types in angle brackets to generic types.

Declaring a generic type is like declaring a non-generic one, except that you use angle brackets to enclose the list of type variables for the generic type.

MyType<typeVar1, typeVar2, ...>

For example, to declare a java.util.List, you would write

List<E> myList;

E is called a type variable, namely a variable that will be replaced by a type. The value substituting for a type variable will then be used as the argument type or the return type of a method or methods in the generic type. For the List interface, when an instance is created, E will be used as the argument type of add and other methods. E will also be used as the return type of getand other methods. Here are the signatures of add and get.

public boolean add<E o>
 
public E get(int index)

Note

A generic type that uses a type variable E allows you to pass E when declaring or instantiating the generic type. Additionally, if E is a class, you may also pass a subclass of E; if E is an interface, you may also pass a class that implements E.

If you pass String to a declaration of List, as in

List<String> myList;

the add method of the List instance referenced by myList will expect a String object as its argument and its get method will return a String. Because get returns a specific type of object, no downcasting is required.

Note

By convention, you use a single uppercase letter for type variable names.

To instantiate a generic type, you pass the same list of parameters as when declaring it. For instance, to create an ArrayList that works with String, you pass String in angle brackets.

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

The diamond language change in Java 7 allows explicit type arguments to constructors of parameterized classes, most notably collections, to be omitted in many situations. Therefore, the statement above can be written more concisely in Java 7 or later.

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

In this case, the compiler will infer the arguments to the ArrayList.

As another example, java.util.Map is defined as

public interface Map<K, V>

K is used to denote the type of map keys and V the type of map values. The put and values methods have the following signatures:

V put(K key, V value)
Collection<V> values()

Note

A generic type must not be a direct or indirect child class of java.lang.Throwable because exceptions are thrown at runtime, and therefore it is not possible to check what type of exception that might be thrown at compile time.

As an example, Listing 12.1 compares List with and without generics.

Listing 12.1: Working with generic List

package app12;
import java.util.List;
import java.util.ArrayList;
 
public class GenericListTest {
    public static void main(String[] args) {
        // without generics
        List stringList1 = new ArrayList();
        stringList1.add("Java");
        stringList1.add("without generics");
        // cast to java.lang.String
        String s1 = (String) stringList1.get(0);
        System.out.println(s1.toUpperCase());
 
        // with generics and diamond
        List<String> stringList2 = new ArrayList<>();
        stringList2.add("Java");
        stringList2.add("with generics");
        // no type casting is necessary
        String s2 = stringList2.get(0);
        System.out.println(s2.toUpperCase());
    }
}

In Listing 12.1, stringList2 is a generic List. The declaration List<String> tells the compiler that this instance of List can only store Strings. When retrieving member elements of the List, no downcasting is necessary because its get method returns the intended type, namely String.

Note

With generic types, type checking is done at compile time.

What's interesting here is the fact that a generic type is itself a type and can be used as a type variable. For example, if you want your List to store lists of strings, you can declare the List by passing List<String> as its type variable, as in

List<List<String>> myListOfListsOfStrings;

To retrieve the first string from the first list in myList, you would write:

String s = myListOfListsOfStrings.get(0).get(0);

Listing 12.2 presents a class that uses a List that accepts a List of Strings.

Listing 12.2: Working with List of Lists

package app12;
import java.util.ArrayList;
import java.util.List;
public class ListOfListsTest {
    public static void main(String[] args) {
        List<String> listOfStrings = new ArrayList<>();
        listOfStrings.add("Hello again");
        List<List<String>> listOfLists =
                new ArrayList<>();
        listOfLists.add(listOfStrings);
        String s = listOfLists.get(0).get(0);
        System.out.println(s); // prints "Hello again"
    }
}

Additionally, a generic type can accept more than one type variables. For example, the java.util.Map interface has two type variables. The first defines the type of its keys and the second the type of its values. Listing 12.3 presents an example that uses a generic Map.

Listing 12.3: Using the generic Map

package app12;
import java.util.HashMap;
import java.util.Map;
public class MapTest {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        map.put("key1", "value1");
        map.put("key2", "value2");
        String value1 = map.get("key1");
    }
}

In Listing 12.3, to retrieve a value indicated by key1, you do not need to perform type casting.

Using Generic Types without Type Parameters

Now that the collection types in Java have been made generic, what about legacy codes? Fortunately, they will still work in Java 5 or later because you can use generic types without type parameters. For example, you can still use List the old way, as demonstrated in Listing 12.1.

List stringList1 = new ArrayList();
stringList1.add("Java");
stringList1.add("without generics");
String s1 = (String) stringList1.get(0);

A generic type used without parameters is called a raw type. This means that code written for JDK 1.4 and earlier versions will continue working in Java 5 or later.

One thing to note, though, starting from Java 5 the Java compiler expects you to use generic types with parameters. Otherwise, the compiler will issue warnings, thinking that you may have forgotten to define type variables with the generic type. For example, compiling the code in Listing 12.1 gave you the following warning because the first List was used as a raw type.

Note: app12/GenericListTest.java uses unchecked or unsafe
        operations.
Note: Recompile with –Xlint:unchecked for details.

You have these options at your disposal to get rid of the warnings when working with raw types:

 compile with the −source 1.4 flag.

 use the @SuppressWarnings(“unchecked”) annotation (See Chapter 18, “Annotations”)

 upgrade your code to use List<Object>. Instances of List<Object> can accept any type of object and behave like a raw type List. However, the compiler will not complain.

Warning

Raw types are available for backward compatibility. New development should shun them. It is possible that future versions of Java will not allow raw types.

Using the? Wildcard

I mentioned that if you declare a List<aType>, the List works with instances of aType and you can store objects of one of these types:

 an instance of aType.

 an instance of a subclass of aType, if aType is a class

 an instance of a class implementing aType if aType is an interface.

However, note that a generic type is a Java type by itself, just like java.lang.String or java.io.File. Passing different lists of type variables to a generic type result in different types. For example, list1 and list2 below reference to different types of objects.

List<Object> list1 = new ArrayList<>();
List<String> list2 = new ArrayList<>();

list1 references a List of java.lang.Object instances and list2 references a List of String objects. Even though String is a subclass of Object, List<String> has nothing to do withList<Object>. Therefore, passing a List<String> to a method that expects a List<Object> will raise a compile time error. Listing 12.4 shows this.

Listing 12.4: AllowedTypeTest.java

package app12;
import java.util.ArrayList;
import java.util.List;
 
public class AllowedTypeTest {
    public static void doIt(List<Object> l) {
    }
    public static void main(String[] args) {
        List<String> myList = new ArrayList<>();
        // this will generate a compile error
        doIt(myList);
    }
}

Listing 12.4 won't compile because you are passing the wrong type to the doIt method. doIt expects an instance of List<Object> and you are passing an instance of List<String>.

The solution to this problem is the ? wildcard. List<?> means a list of objects of any type. Therefore, the doIt method should be changed to:

public static void doIt(List<?> l) {
}

There are circumstances where you want to use the wildcard. For example, if you have a printList method that prints the members of a List, you may want to make it accept a List of any type. Otherwise, you would end up writing many overloads of printList. Listing 12.5 shows the printList method that uses the ? wildcard.

Listing 12.5: Using the? wildcard

package app12;
import java.util.ArrayList;
import java.util.List;
 
public class WildCardTest {
    public static void printList(List<?> list) {
        for (Object element : list) {
            System.out.println(element);
        }
    }
    public static void main(String[] args) {
        List<String> list1 = new ArrayList<>();
        list1.add("Hello");
        list1.add("World");
        printList(list1);
 
        List<Integer> list2 = new ArrayList<>();
        list2.add(100);
        list2.add(200);
        printList(list2);
    }
}

The code in Listing 12.4 demonstrates that List<?> in the printList method means a List of any type.

Note, however, it is illegal to use the wildcard when declaring or creating a generic type, such as this.

List<?> myList = new ArrayList<?>(); // this is illegal

If you want to create a List that can accept any type of object, use Object as the type variable, as in the following line of code:

List<Object> myList = new ArrayList<>();

Using Bounded Wildcards in Methods

In the section “Using the? Wildcard” above, you learned that passing different type variables to a generic type creates different Java types. In many cases, you might want a method that accepts a List of different types. For example, if you have a getAverage method that returns the average of numbers in a list, you may want the method to be able to work with a list of integers or a list of floats or a list of another number type. However, if you write List<Number> as the argument type to getAverage, you won't be able to pass a List<Integer> instance or a List<Double> instance because List<Number> is a different type from List<Integer> or List<Double>. You can use List as a raw type or use a wildcard, but this is depriving you of type safety checking at compile time because you could also pass a list of anything, such as an instance of List<String>. You could use List<Number>, but you must always pass aList<Number> to the method. This would make your method less useful because you work with List<Integer> or List<Long> probably more often than with List<Number>.

There is another rule to circumvent this restriction, i.e. by allowing you to define an upper bound of a type variable. This way, you can pass a type or its subtype. In the case of thegetAverage method, you may be able to pass a List<Number> or a List of instances of a Number subclass, such as List<Integer> or List<Float>.

The syntax for using an upper bound is as follows:

GenericType<? extends upperBoundType>

For example, for the getAverage method, you would write:

List<? extends Number>

Listing 12.6 illustrates the use of such a bound.

Listing 12.6: Using a bounded wildcard

package app12;
import java.util.ArrayList;
import java.util.List;
public class BoundedWildcardTest {
    public static double getAverage(
            List<? extends Number> numberList) {
        double total = 0.0;
        for (Number number : numberList) {
            total += number.doubleValue();
        }
        return total/numberList.size();
    }
 
    public static void main(String[] args) {
        List<Integer> integerList = new ArrayList<>();
        integerList.add(3);
        integerList.add(30);
        integerList.add(300);
        System.out.println(getAverage(integerList)); // 111.0
        List<Double> doubleList = new ArrayList<>();
        doubleList.add(3.0);
        doubleList.add(33.0);
        System.out.println(getAverage(doubleList)); // 18.0
    }
}

Thanks to the upper bound, the getAverage method in Listing 12.6 allows you to pass a List<Number> or a List of instances of any subclass of java.lang.Number.

Lower Bounds

The extends keyword is used to define an upper bound of a type variable. Though useable only in very few applications, it is also possible to define a lower bound of a type variable, by using the super keyword. For example, using List<? super Integer> as the type to a method argument indicates that you can pass a List<Integer> or a List of objects whose class is a superclass of java.lang.Integer.

Writing Generic Types

Writing a generic type is not much different from writing other types, except for the fact that you declare a list of type variables that you intend to use somewhere in your class. These type variables come in angle brackets after the type name. For example, the Point class in Listing 12.7 is a generic class. A Point object represents a point in a coordinate system and has an X component (abscissa) and a Y component (ordinate). By making Point generic, you can specify the degree of accuracy of a Point instance. For example, if a Point object needs to be very accurate, you can pass Double as the type variable. Otherwise, Integer would suffice.

Listing 12.7: The generic Point class

package app12;
public class Point<T> {
    T x;
    T y;
    public Point(T x, T y) {
        this.x = x;
        this.y = y;
    }
    public T getX() {
        return x;
    }
    public T getY() {
        return y;
    }
    public void setX(T x) {
        this.x = x;
    }
    public void setY(T y) {
        this.y = y;
    }
}

In Listing 12.7, T is the type variable for the Point class. T is used as the return value of both getX and getY and as the argument type for setX and setY. In addition, the constructor also accepts two T type variables.

Using Point is just like using other generic types. For example, the following code creates two Point objects, point1 and point2. The former passes Integer as the type variable, the latter Double.

Point<Integer> point1 = new Point<>(4, 2);
point1.setX(7);
Point<Double> point2 = new Point<>(1.3, 2.6);
point2.setX(109.91);

Summary

Generics enable stricter type checking at compile time. Used especially in the Collections Framework, generics make two contributions. First, they add type checking to collection types at compile time, so that the type of objects that a collection can hold is restricted to the type passed to it. For example, you can now create an instance of java.util.List that hold strings and will not accept Integer or other types. Second, generics eliminate the need for type casting when retrieving an element from a collection.

Generic types can be used without type variables, i.e. as raw types. This provision makes it possible to run pre-Java 5 codes with JRE 5 or later. For new applications, you should not use raw types as future releases of Java may not support them.

In this chapter you have also learned that passing different type variables to a generic type results in different Java types. This is to say that List<String> is a different type fromList<Object>. Even though String is a subclass of java.lang.Object, passing a List<String> to a method that expects a List<Object> generates a compile error. Methods that expect aList of anything can use the ? wildcard. List<?> means a List of objects of any type.

Finally, you have seen that writing generic types is not that different from writing ordinary Java types. You just need to declare a list of type variables in angle brackets after the type name. You then use these type variables as the types of method return values or as the types of method arguments. By convention, a type variable name consists of a single up

1. What are the main benefits of generics?

2. What does “parameterized type” mean?

Read More

The Collections Framework chapter-11

Chapter 11

The Collections Framework

When writing an object-oriented program, you often work with groups of objects, either objects of the same type or of different types. In Chapter 5, “Core Classes” you learned that arrays can be used to group objects of the same type. Unfortunately, arrays lack the flexibility you need to rapidly develop applications. They cannot be resized and they cannot hold objects of different types. Fortunately, Java comes with a set of interfaces and classes that make working with groups of objects easier: the Collections Framework. This chapter deals with the most important types in the Collections Framework that a Java beginner should know. Most of them are very easy to use and there's no need to provide extensive examples. More attention is paid to the last section of the chapter, “Making Your Objects Comparable and Sortable” where carefully designed examples are given because it is important for every Java programmer to know how to make objects comparable and sortable.

Note on Generics

Discussing the Collections Framework would be incomplete without generics. On the other hand, explaining generics without previous knowledge of the Collections Framework would be difficult. Therefore, there needs to be a compromise: The Collections Framework will be explained first in this chapter and will be revisited in Chapter 12, “Generics.” Since up to this point no knowledge of generics is assumed, the discussion of the Collections Framework in this chapter will have to use class and method signatures as they appear in pre-5 JDK—s, instead of signatures used in Java 5 or later that imply the presence of generics. As long as you read both this chapter and Chapter 12, you will have up-to date knowledge of both the Collections Framework and generics.

An Overview of the Collections Framework

A collection is an object that groups other objects. Also referred to as a container, a collection provides methods to store, retrieve, and manipulate its elements. Collections help Java programmers manage objects easily.

A Java programmer should be familiar with the most important types in the Collections Framework, all of which are part of the java.util package. The relationships between these types are shown in Figure 11.1.

Figure 11.1: The Collections Framework

The main type in the Collections Framework is, unsurprisingly, the Collection interface. List, Set, and Queue are three main subinterfaces of Collection. In addition, there is a Mapinterface that can be used for storing key/value pairs. A subinterface of Map, SortedMap, guarantees that the keys are in ascending order. Other implementations of Map are AbstractMapand its concrete implementation HashMap. Other interfaces include Iterator and Comparator. The latter is used to make objects sortable and comparable.

Most of the interfaces in the Collections Frameworks come with implementation classes. Sometimes there are two versions of an implementation, the synchronized version and the unsynchronized version. For instance, the java.util.Vector class and the ArrayList class are implementations of the List interface. Both Vector and ArrayList provide similar functionality, however Vector is synchronized and ArrayList unsynchronized. Synchronized versions of an implementation were included in the first version of the JDK. Only later did Sun add the unsynchronized versions so that programmers could write better performing applications. The unsynchronized versions should thus be in preference to the synchronized ones. If you need to use an unsynchronized implementation in a multi-threaded environment, you can still synchronize it yourself.

Note

Working in a multi-threaded environment is discussed in Chapter 23, “Java Threads.”

The Collection Interface

The Collection interface groups objects together. Unlike arrays that cannot be resized and can only group objects of the same type, collections allow you to add any type of object and do not force you to specify an initial size.

Collection comes with methods that are easy to use. To add an element, you use the add method. To add members of another Collection, use addAll. To remove all elements, use clear. To inquire about the number of elements in a Collection, call its size method. To test if a Collection contains an element, use isEmpty. And, to move its elements to an array, use toArray.

An important point to note is that Collection extends the Iterable interface, from which Collection inherits the iterator method. This method returns an Iterator object that you can use to iterate over the collection's elements. Check the section, “Iterable and Iterator” later in this chapter.

In addition, you'll learn how to use the for statement to iterate over a Collection's elements.

List and ArrayList

List is the most popular subinterface of Collection, and ArrayList is the most commonly used implementation of List. Also known as a sequence, a List is an ordered collection. You can access its elements by using indices and you can insert an element into an exact location. Index 0 of a List references the first element, index 1 the second element, and so on.

The add method inherited from Collection appends the specified element to the end of the list. Here is its signature.

public boolean add(java.lang.Object element)

This method returns true if the addition is successful. Otherwise, it returns false. Some implementations of List, such as ArrayList, allow you to add null, some don—t.

List adds another add method with the following signature:

public void add(int index, java.lang.Object element)

With this add method you can insert an element at any position.

In addition, you can replace and remove an element by using the set and remove methods, respectively.

public java.lang.Object set(int index, java.lang.Object element)
 
public java.lang.Object remove(int index)

The set method replaces the element at the position specified by index with element and returns the reference to the element inserted. The remove method removes the element at the specified position and returns a reference to the removed element.

To create a List, you normally assign an ArrayList object to a List reference variable.

List myList = new ArrayList();

The no-argument constructor of ArrayList creates an ArrayList object with an initial capacity of ten elements. The size will grow automatically as you add more elements than its capacity. If you know that the number of elements in your ArrayList will be more than its capacity, you can use the second constructor:

public ArrayList(int initialCapacity)

This will result in a slightly faster ArrayList because the instance does not have to grow in capacity.

List allows you to store duplicate elements in the sense that two or more references referencing the same object can be stored. Listing 11.1 demonstrates the use of List and some of its methods.

Listing 11.1: Using List

package app11;
import java.util.ArrayList;
import java.util.List;
 
public class ListTest {
    public static void main(String[] args) {
        List myList = new ArrayList();
        String s1 = "Hello";
        String s2 = "Hello";
        myList.add(100);
        myList.add(s1);
        myList.add(s2);
        myList.add(s1);
        myList.add(1);
        myList.add(2, "World");
        myList.set(3, "Yes");
        myList.add(null);
        System.out.println("Size: " + myList.size());
        for (Object object : myList) {
            System.out.println(object);
        }
    }
}

When run, here is the result on the console.

Size: 6
100
Hello
World
Yes
Hello
1
null

The java.util.Arrays class provides an asList method that lets you add multiple elements to a List in one go. For example, the following snippet adds multiple Strings in a single call.

List members = Arrays.asList("Chuck", "Harry", "Larry", "Wang");

List also adds methods to search the collection, indexOf and lastIndexOf:

public int indexOf(java.lang.Object obj)
public int lastIndexOf(java.lang.Object obj)

indexOf compares the obj argument with its elements by using the equals method starting from the first element, and returns the index of the first match. lastIndexOf does the same thing but comparison is done from the last element to the first. Both indexOf and lastIndexOf return -1 if no match was found.

Note

List allows duplicate elements. By contrast, Set does not.

Iterating Over a Collection with Iterator and for

Iterating over a Collection is one of the most common tasks around when working with collections. There are two ways to do this: by using Iterator and by using for.

Recall that Collection extends Iterable, which has one method: iterator. This method returns a java.util.Iterator that you can use to iterate over the Collection. The Iterator interface has the following methods:

 hasNext. Iterator employs an internal pointer that initially points to a place before the first element. hasNext returns true if there are more element(s) after the pointer. Calling nextmoves this pointer to the next element. Calling next for the first time on an Iterator causes its pointer to point to the first element.

 next. Moves the internal pointer to the next element and returns the element. Invoking next after the last element is returned throws a java.util.NoSuchElementException. Therefore, it is safest to call hasNext before invoking next to test if there is a next element.

 remove. Removes the element pointed by the internal pointer.

A common way to iterate over a Collection using an Iterator is either by employing while or for. Suppose myList is an ArrayList that you want to iterate over. The following snippet uses a while statement to iterate over a collection and print each element in the collection.

Iterator iterator = myList.iterator();
while (iterator.hasNext()) {
    String element = (String) iterator.next();
    System.out.println(element);
}

This is identical to:

for (Iterator iterator = myList.iterator(); iterator.hasNext(); ) {
    String element = (String) iterator.next();
    System.out.println(element);
}

The for statement can iterate over a Collection without the need to call the iterator method. The syntax is

for (Type identifier : expression) {
    statement(s)
}

Here expression must be an Iterable. Since Collection extends Iterable, you can use enhanced for to iterate over any Collection. For example, this code shows how to use for.

for (Object object : myList) {
    System.out.println(object);
}

Using for to iterate over a collection is a shortcut for using Iterator. In fact, the code that uses for above is translated into the following by the compiler.

for (Iterator iterator = myList.iterator(); iterator.hasNext(); ) {
    String element = (String) iterator.next();
    System.out.println(element);
}

Set and HashSet

A Set represents a mathematical set. Unlike List, Set does not allow duplicates. There must not be two elements of a Set, say e1 and e2, such that e1.equals(e2). The add method of Setreturns false if you try to add a duplicate element. For example, this code prints “addition failed.”

Set set = new HashSet();
set.add("Hello");
if (set.add("Hello")) {
    System.out.println("addition successful");
} else {
    System.out.println("addition failed");
}

The first time you called add, the string “Hello” was added. The second time around it failed because adding another “Hello” would result in duplicates in the Set.

Some implementations of Set allow at most one null element. Some do not allow nulls. For instance, HashSet, the most popular implementation of Set, allows at most one null element. When using HashSet, be warned that there is no guarantee the order of elements will remain unchanged. HashSet should be your first choice of Set because it is faster than other implementations of Set, TreeSet and LinkedHashSet.

Queue and LinkedList

Queue extends Collection by adding methods that support the ordering of elements in a first-in-first-out (FIFO) basis. FIFO means that the element first added will be the first you get when retrieving elements. This is in contrast to a List in which you can choose which element to retrieve by passing an index to its get method.

Queue adds the following methods.

 offer. This method inserts an element just like the add method. However, offer should be used if adding an element may fail. This method returns false upon failing to add an element and does not throw an exception. On the other hand, a failed insertion with add throws an exception.

 remove. Removes and returns the element at the head of the Queue. If the Queue is empty, this method throws a java.util.NoSuchElementException.

 poll. This method is like the remove method. However, if the Queue is empty it returns null and does not throw an exception.

 element. Returns but does not remove the head of the Queue. If the Queue is empty, it throws a java.util.NoSuchElementException.

 peek. Also returns but does not remove the head of the Queue. However, peek returns null if the Queue is empty, instead of throwing an exception.

When you call the add or offer method on a Queue, the element is always added at the tail of the Queue. To retrieve an element, use the remove or poll method. remove and poll always remove and return the element at the head of the Queue.

For example, the following code creates a LinkedList (an implementation of Queue) to show the FIFO nature of Queue.

Queue queue = new LinkedList();
queue.add("one");
queue.add("two");
queue.add("three");
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());

The code produces this result:

one
two
three

This demonstrates that remove always removes the element at the head of the Queue. In other words, you cannot remove “three” (the third element added to the Queue) before removing “one” and “two.”

Note

The java.util.Stack class is a Collection that behaves in a last-in-first-out (LIFO) manner.

Collection Conversion

Collection implementations normally have a constructor that accepts a Collection object. This enables you to convert a Collection to a different type of Collection. Here are the constructors of some implementations:

public ArrayList(Collection c)
 
public HashSet(Collection c)
 
public LinkedList(Collection c)

As an example, the following code converts a Queue to a List.

Queue queue = new LinkedList();
queue.add("Hello");
queue.add("World");
List list = new ArrayList(queue);

And this converts a List to a Set.

List myList = new ArrayList();
myList.add("Hello");
myList.add("World");
myList.add("World");
Set set = new HashSet(myList);

myList has three elements, two of which are duplicates. Since Set does not allow duplicate elements, only one of the duplicates will be accepted. The resulting Set in the above code only has two elements.

Map and HashMap

A Map holds key to value mappings. There cannot be duplicate keys in a Map and each key maps to at most one value.

To add a key/value pair to a Map, you use the put method. Its signature is as follows:

public void put(java.lang.Object key, java.lang.Object value)

Note that both the key and the value cannot be a primitive. However, the following code that passes primitives to both the key and the value is legal because boxing is performed before theput method is invoked.

map.put(1, 3000);

Alternatively, you can use putAll and pass a Map.

public void putAll(Map map)

You can remove a mapping by passing the key to the remove method.

public void remove(java.lang.Object key)

To remove all mappings, use clear. To find out the number of mappings, use the size method. In addition, isEmpty returns true if the size is zero.

To obtain a value, you can pass a key to the get method:

public java.lang.Object get(java.lang.Object key)

In addition to the methods discussed so far, there are three no-argument methods that provide a view to a Map.

 keySet. Returns a Set containing all keys in the Map.

 values. Returns a Collection containing all values in the Map.

 entrySet. Returns a Set containing Map.Entry objects, each of which represents a key/value pair. The Map.Entry interface provides the getKey method that returns the key part and the getValue method that returns the value.

There are several implementations of Map in the java.util package. The most commonly used are HashMap and Hashtable. HashMap is unsynchronized and Hashtable is synchronized. Therefore, HashMap is the faster one between the two.

The following code demonstrates the use of Map and HashMap.

Map map = new HashMap();
map.put("1", "one");
map.put("2", "two");
 
System.out.println(map.size()); //print 2
System.out.println(map.get("1")); //print "one"
 
Set keys = map.keySet();
// print the keys
for (Object object : keys) {
    System.out.println(object);
}

Making Objects Comparable and Sortable

In real life, objects are comparable. Dad's car is more expensive than Mom—s, this dictionary is thicker than those books, Granny is older than Auntie Mollie (well, yeah, living objects too are comparable), and so forth. In object-oriented programming there are often needs to compare instances of the same class. And, if instances are comparable, they can be sorted. As an example, given two Employee objects, you may want to know which one has been staying in the organization longer. Or, in a search method for Person instances whose first name is Larry, you may want to display search results sorted by age in descending or ascending order. You can make objects comparable by implementing the java.lang.Comparable andjava.util.Comparator interfaces. You'll learn to use these interfaces in the following sections.

Using java.lang.Comparable

The java.util.Arrays class provides the static method sort that can sort any array of objects. Here is its signature.

public static void sort(java.lang.Object[] a)

Because all Java classes derive from java.lang.Object, all Java objects are a type of java.lang.Object. This means you can pass an array of any objects to the sort method.

However, how does the sort method know how to sort arbitrary objects? It's easy to sort numbers or strings, but how do you sort an array of Elephant objects, for example?

First, examine the Elephant class in Listing 11.2.

Listing 11.2: The Elephant class

public class Elephant {
    public float weight;
    public int age;
    public float tuskLength; // in centimeters
}

Since you are the author of the Elephant class, you get to decide how you want Elephant objects to be sorted. Let's say you want to sort them by their weights and ages. Now, how do you tell Arrays.sort of your decision?

Arrays.sort has defined a contract between itself and objects that needs its sorting service. The contract takes the form of the java.lang.Comparable interface. (See Listing 11.3)

Listing 11.3: The java.lang.Comparable method

package java.lang;
public interface Comparable {
    public int compareTo(Object obj);
}

Any class that needs to support sorting by Arrays.sort must implement the Comparable interface. In Listing 11.3, the argument obj in the compareTo method refers to the object being compared with this object. The code implementation for this method in the implementing class must return a positive number if this object is greater than the argument object, zero if both are equal, and a negative number if this object is less than the argument object.

Listing 11.4 presents a modified Elephant class that implements Comparable.

Listing 11.4: The Elephant class implementing Comparable

package app11;
public class Elephant implements Comparable {
    public float weight;
    public int age;
    public float tuskLength;
    public int compareTo(Object obj) {
        Elephant anotherElephant = (Elephant) obj;
        if (this.weight > anotherElephant.weight) {
            return 1;
        } else if (this.weight < anotherElephant.weight) {
            return -1;
        } else {
            // both elephants have the same weight, now
            // compare their age
            return (this.age - anotherElephant.age);
        }
    }
}

Now that Elephant implements Comparable, you can use Arrays.sort to sort an array of Elephant objects. The sort method will treat each Elephant object as a Comparable object (because Elephant implements Comparable, an Elephant object can be considered a type of Comparable) and call the compareTo method on the object. The sort method does this repeatedly until the Elephant objects in the array have been organized correctly by their weights and ages. Listing 11.5 provides a class that tests the sort method on Elephant objects.

Listing 11.5: Sorting elephants

package app11;
import java.util.Arrays;
 
public class ElephantTest {
    public static void main(String[] args) {
        Elephant elephant1 = new Elephant();
        elephant1.weight = 100.12F;
        elephant1.age = 20;
        Elephant elephant2 = new Elephant();
        elephant2.weight = 120.12F;
        elephant2.age = 20;
        Elephant elephant3 = new Elephant();
        elephant3.weight = 100.12F;
        elephant3.age = 25;
 
        Elephant[] elephants = new Elephant[3];
        elephants[0] = elephant1;
        elephants[1] = elephant2;
        elephants[2] = elephant3;
 
        System.out.println("Before sorting");
        for (Elephant elephant : elephants) {
            System.out.println(elephant.weight + ":" +
                    elephant.age);
        }
        Arrays.sort(elephants);
        System.out.println("After sorting");
        for (Elephant elephant : elephants) {
            System.out.println(elephant.weight + ":" +
                    elephant.age);
        }
    }
}

If you run the ElephantTest class, you'll see this on your console.

Before sorting
100.12:20
120.12:20
100.12:25
After sorting
100.12:20
100.12:25
120.12:20

Classes such as java.lang.String, java.util.Date, and primitive wrapper classes all implement java.lang.Comparable.

Using Comparable and Comparator

Implementing java.lang.Comparable enables you to define one way to compare instances of your class. However, objects sometimes are comparable in more ways. For example, twoPerson objects may need to be compared by age or by last/first name. In cases like this, you need to create a Comparator that defines how two objects should be compared. To make objects comparable in two ways, you need two comparators.

To create a comparator, you write a class that implements the Comparator interface. You then provide the implementation for its compare method. This method has the following signature.

public int compare(java.lang.Object o1, java.lang.Object o2)

compare returns zero if o1 and o2 are equal, a negative integer if o1 is less than o2, and a positive integer if o1 is greater than o2.

As an example, the Person class in Listing 11.6 implements Comparable. Listings 11.7 and 11.8 present two comparators of Person objects (by last name and by first name), andListing 11.9 offers the class that instantiates the Person class and the two comparators.

Listing 11.6: The Person class implementing Comparable.

package app11;
 
public class Person implements Comparable {
    private String firstName;
    private String lastName;
    private int age;
    public String getFirstName() {
        return firstName;
    }
    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }
    public String getLastName() {
        return lastName;
    }
    public void setLastName(String lastName) {
        this.lastName = lastName;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    public int compareTo(Object anotherPerson)
            throws ClassCastException {
        if (!(anotherPerson instanceof Person)) {
            throw new ClassCastException(
                    "A Person object expected.");
        }
        int anotherPersonAge = ((Person) anotherPerson).getAge();
        return this.age - anotherPersonAge;
    }
}

Listing 11.7: The LastNameComparator class

package app11;
import java.util.Comparator;
 
public class LastNameComparator implements Comparator {
    public int compare(Object person, Object anotherPerson) {
        String lastName1 = ((Person)
      person).getLastName().toUpperCase();
        String firstName1 =
                ((Person) person).getFirstName().toUpperCase();
        String lastName2 = ((Person)
                anotherPerson).getLastName().toUpperCase();
        String firstName2 = ((Person) anotherPerson).getFirstName()
                .toUpperCase();
        if (lastName1.equals(lastName2)) {
            return firstName1.compareTo(firstName2);
        } else {
            return lastName1.compareTo(lastName2);
        }
    }
}

Listing 11.8: The FirstNameComparator class

package app11;
import java.util.Comparator;
 
public class FirstNameComparator implements Comparator {
    public int compare(Object person, Object anotherPerson) {
        String lastName1 = ((Person)
      person).getLastName().toUpperCase();
        String firstName1 = ((Person)
      person).getFirstName().toUpperCase();
        String lastName2 = ((Person)
      anotherPerson).getLastName().toUpperCase();
        String firstName2 = ((Person) anotherPerson).getFirstName()
                .toUpperCase();
        if (firstName1.equals(firstName2)) {
            return lastName1.compareTo(lastName2);
        } else {
            return firstName1.compareTo(firstName2);
        }
    }
}

Listing 11.9: The PersonTest class

package app11;
import java.util.Arrays;
 
public class PersonTest {
    public static void main(String[] args) {
        Person[] persons = new Person[4];
        persons[0] = new Person();
        persons[0].setFirstName("Elvis");
        persons[0].setLastName("Goodyear");
        persons[0].setAge(56);
 
        persons[1] = new Person();
        persons[1].setFirstName("Stanley");
        persons[1].setLastName("Clark");
        persons[1].setAge(8);
 
        persons[2] = new Person();
        persons[2].setFirstName("Jane");
        persons[2].setLastName("Graff");
        persons[2].setAge(16);
 
        persons[3] = new Person();
        persons[3].setFirstName("Nancy");
        persons[3].setLastName("Goodyear");
        persons[3].setAge(69);
 
        System.out.println("Natural Order");
        for (int i = 0; i < 4; i++) {
            Person person = persons[i];
            String lastName = person.getLastName();
            String firstName = person.getFirstName();
            int age = person.getAge();
            System.out.println(lastName + ", " + firstName +
                    ". Age:" + age);
        }
 
        Arrays.sort(persons, new LastNameComparator());
        System.out.println();
        System.out.println("Sorted by last name");
        for (int i = 0; i < 4; i++) {
            Person person = persons[i];
            String lastName = person.getLastName();
            String firstName = person.getFirstName();
            int age = person.getAge();
            System.out.println(lastName + ", " + firstName +
                    ". Age:" + age);
        }
 
        Arrays.sort(persons, new FirstNameComparator());
        System.out.println();
        System.out.println("Sorted by first name");
        for (int i = 0; i < 4; i++) {
            Person person = persons[i];
            String lastName = person.getLastName();
            tSring firstName = person.getFirstName();
            int age = person.getAge();
            System.out.println(lastName + ", " + firstName +
                    ". Age:" + age);
        }
 
        Arrays.sort(persons);
        System.out.println();
        System.out.println("Sorted by age");
        for (int i = 0; i < 4; i++) {
            Person person = persons[i];
            String lastName = person.getLastName();
            String firstName = person.getFirstName();
            int age = person.getAge();
            System.out.println(lastName + ", " + firstName +
                    ". Age:" + age);
        }
    }
}

If you run the PersonTest class, you will get the following result.

Natural Order
Goodyear, Elvis. Age:56
Clark, Stanley. Age:8
Graff, Jane. Age:16
Goodyear, Nancy. Age:69
 
Sorted by last name
Clark, Stanley. Age:8
Goodyear, Elvis. Age:56
Goodyear, Nancy. Age:69
Graff, Jane. Age:16
 
Sorted by first name
Goodyear, Elvis. Age:56
Graff, Jane. Age:16
Goodyear, Nancy. Age:69
Clark, Stanley. Age:8
 
Sorted by age
Clark, Stanley. Age:8
Graff, Jane. Age:16
Goodyear, Elvis. Age:56
Goodyear, Nancy. Age:69

Summary

In this chapter you have learned to use the core types in the Collections Framework. The main type is the java.util.Collection interface, which has three direct subinterfaces: List, Set, andQueue. Each subtype comes with several implementations. There are synchronized implementations and there are unsynchronized ones. The latter are usually preferable because they are faster.

There is also a Map interface for storing key/value pairs. Two main implementations of Map are HashMap and Hashtable. HashMap is faster than Hashtable because the former is unsynchronized and the latter is synchronized.

Lastly, you have also learned the java.lang.Comparable and java.util.Comparator interfaces. Both are important because they can make objects comparable and sortable.

Questions

1. Name at least seven types of the Collections Framework.

2. What is the different between ArrayList and Vector?

3. Why is Comparator more powerful than Comparable?

Read More