Generics & Collections

CISC6795, Spring 2011

Dr. Zhang
 A sideline about array
An array: a sequence of either objects or primitives
that are all the same type and are packaged together
under one identifier name.
Arrays are defined and used with the square brackets
indexing operator [ ].
To define an array reference:
int[] a1; //Preferred by some in Java community
Or put square brackets after identifier:
int a1[]; //C/C++ style
The similarity between C and Java array ends here !

2
 Initializing array
Unlike in C/C++, Java does not allow
int a1[20];
int a1[]; // declare a reference to an array (memory is
allocated for the reference), and there’s been no space
allocated for the array object itself.
To create storage for the array, you must write an
initialization expression
int[] a1 = { 1, 2, 3, 4, 5 };
Compiler allocates storage allocation (equivalent of using
new) at this point.
int[] a2=a1; // copying the reference,

3
 Create array of primitive types
import java.util.*;
import static net.mindview.util.Print.*;
public class ArrayNew {
public static void main(String[] args) {
int[] a; // a reference to an array (of integer) object
Random rand = new Random(47);
a = new int[rand.nextInt(20)]; // create an array of size 20 integer
print("length of a = " + a.length);
print(Arrays.toString(a));
}
} /* Output: use new to create the elements in the array.
new works even though it’s creating an array of primitives
length of a = 18
(new won’t create a non-array primitive)
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

4
 Create array of non-primitive types
If you create a non-primitive array, you create an array
of references:
public class Inventory {
public Inventory ( )
{ items is only an array of references
items = new Item[5]; new is called to create the array,
items[0] = new Item (1, "MEDIUM_PIZZA“, 1239, 0.0,10);
items[1] = new Item (2, "LARGE_PIZZA“, 1598, 0.0, 10);

reference itself is initialized by creating

a new Item object

5
 Outline: next two lessons
Generics, new feature of J2SE 5.0
Provide compile-time type safety: catch invalid types at compile
time
Generic methods: A single method declaration => a set of methods
Generic interfaces: A single interface declaration => a set of
interface
Generic classes: A single class declaration => a set of classes
Java collections framework
Contain prepackaged data structures, interfaces, algorithms
Use existing data structures
 Example of code reuse
Provides reusable components

6
 Motivation for Generic Methods
Overloaded methods
Similar methods perform same operations on different types of data
Overloaded printArray methods to print:
 Integer array
 Double array
 Character array

Only reference types can be used with generic methods/classes

Type-wrapper classes in package java.lang
Enable programmers to manipulate primitive-type values as objects
Boolean, Byte, Character, Double, Float, Integer,
Long and Short

7
  Autoboxing and Auto-Unboxing
Boxing conversion
Converts a value of a primitive type to an object of the
corresponding type-wrapper class
From int to Integer, double to Double …
Unboxing conversion
Converts an object of a type-wrapper class to a value of the
corresponding primitive type
From Long to long, Float to float
J2SE 5.0 automatically performs these conversions
Called autoboxing and auto-unboxing

8
 1 // Fig. 18.1: OverloadedMethods.java
2 // Using overloaded methods to print array of different types.
3

Outline
4 public class OverloadedMethods
5 {
6 // method printArray to print Integer array
7 public static void printArray( Integer[] inputArray )
8 {
9 // display array elements
Method printArray accepts
10 for ( Integer element : inputArray )
an array of Integer objects
11 System.out.printf( "%s ", element );
12
13 System.out.println();
14 } // end method printArray
15
16 // method printArray to print Double array
17 public static void printArray( Double[] inputArray )
18 {
19 // display array elements Method printArray accepts
20 for ( Double element : inputArray ) an array of Double objects
21 System.out.printf( "%s ", element );
22
23 System.out.println();
24 } // end method printArray
25

9
 10
26 // method printArray to print Character array

Outline
27 public static void printArray( Character[] inputArray )
28 {
Method printArray accepts
29 // display array elements an array of Character objects
30 for ( Character element : inputArray )
31 System.out.printf( "%s ", element );
32
33 System.out.println();
34 } // end method printArray
35
36 public static void main( String args[] )
37 {
38 // create arrays of Integer, Double and Character
39 Integer[] integerArray = { 1, 2, 3, 4, 5, 6 };
40 Double[] doubleArray = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7 };
41 Character[] characterArray = { 'H', 'E', 'L', 'L', 'O' };
42

Auto-boxing happens here…

43 System.out.println( "Array integerArray contains:" );
44
45 Outline
printArray( integerArray ); // pass an Integer array
System.out.println( "\nArray doubleArray contains:" );
46 printArray( doubleArray ); // pass a Double array
47 System.out.println( "\nArray characterArray contains:" );
48 printArray( characterArray ); // pass a Character array
49 } // end main
At compile time, compiler determines argument
50 } // end class OverloadedMethods
integerArray’s type (i.e., Integer[]), attempts
Array integerArray contains: to locate a method named printArray that
1 2 3 4 5 6 specifies a single Integer[] parameter (lines 7-14)

Array doubleArray contains:

1.1 2.2 3.3 4.4 5.5 6.6 7.7

Array characterArray contains:

H E L L O

11
 Motivation for Generic Methods (Cont.)
The three printArray methods
Array element type appears in two location
Method header
for statement header
Combine three printArray methods into one
Replace element types with a generic name E
Declare one printArray method
Display string representation of the elements of any array

12
 Towards generic method
1 public static void printArray( E[] inputArray )
2 {
Replace the element type with
3 // display array elements a single generic type E
4 for ( E element : inputArray )
5 System.out.printf( "%s ", element );
6
7 System.out.println();
8 } // end method printArray

Actual syntax:
public static < E > void printArrays( E[] array)
Type parameter section, also called formal type parameters
 Delimited by angle brackets ( < and > )
 Precede the method’s return type
 Contain one or more type parameters
13
 Generic Methods: type parameter
Type parameter, also known as type variable
An identifier that specifies a generic type name
Act as placeholders for the types of the argument passed to
the generic method, i.e., actual type arguments
Usually use a capital letter
 Convention: use E (element) for a type parameter that represents the
type of an element in an array (or other collection)
Can be used in return type, parameter types and local
variable types
 Can be declared only once but can appear more than once:
public static < E > void printTwoArrays(
E[] array1, E[] array2 )

14
1 // Fig. 18.3: GenericMethodTest.java
2 // Using generic methods to print array of different types.
Use the type parameter to declare
3
method printArray’s parameter type
4 public class GenericMethodTest
5 {
6 // generic method printArray
7 public static < E > void printArray( E[] inputArray )
8 {
9 // display array elements Type parameter section delimited
10 for ( E element : inputArray ) by angle brackets (< and > )
11 System.out.printf( "%s ", element );
12
Use the type parameter to declare method
13 System.out.println();
printArray’s local variable type
14 } // end method printArray
15
16 public static void main( String args[] )
17 {
18 // create arrays of Integer, Double and Character
19 Integer[] intArray = { 1, 2, 3, 4, 5 };
20 Double[] doubleArray = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7 };
21 Character[] charArray = { 'H', 'E', 'L', 'L', 'O' };
22

15
 23 System.out.println( "Array integerArray contains:" );
24 printArray( integerArray ); // pass an Integer array
Invoke generic method printArray
25 System.out.println( "\nArray doubleArray contains:" );
with an Integer array
26 printArray( doubleArray ); // pass a Double array
27 System.out.println( "\nArray characterArray contains:" );
28 printArray( characterArray ); // pass a Character array
29 } // end main
30 } // end class GenericMethodTest

Array integerArray contains:

1 2 3 4 5 6 Invoke generic method printArray
with a Character array
Array doubleArray contains:
1.1 2.2 3.3 4.4 5.5 6.6 7.7

Array characterArray contains:

H E L L O

16
 Questions/Exercises
A generic method that find the maximum value in
an array?
Problem: need to make sure the type is
comparable…
Objects o1, and o2 of the type can be compared, using
o1.compareTo (o2) …
Need to say the type is any type that provides
compareTo() method
Interface ? But the parameter of compareTo is type
specific, …
=> generic interface, an parameterized interface

17
 Outline
Generics, new feature of J2SE 5.0
Provide compile-time type safety: catch invalid types at compile time
Generic methods: A single method declaration => a set of related
methods
Generic interface: a single interface declaration=> a set of related
interface
Generic classes: A single class declaration => a set of related classes
Java collections framework, use generics
Contain prepackaged data structures, interfaces, algorithms
Use existing data structures
 Example of code reuse
Provides reusable components

18
 Generic Interface: Comparable
public interface Comparable<T>
{
int compareTo(T other);
}
 compareTo(): Compare two objects (this and other) of type T
 Return 0 if two objects are equal
 Return -1 if this is less than other
 Return 1 if this is greater than other

imposes a total ordering, or natural ordering on the objects of

each class that implements it.
 natural ordering is consistent with equals if and only if:
(e1.compareTo(e2) == 0) <=> e1.equals(e2) for every e1 and e2 of class C.

19
 Generic Interface: Comparable
public interface Comparable<T>
{
int compareTo(T o);
}
Lists (and arrays) of objects that implement this
interface can be sorted using Collections.sort (and
Arrays.sort).
Objects that implement this interface can be used as
keys in a sorted map or elements in a sorted set

20
 Upper bound of type parameter
Next example, generic method maximum (x,y,z)
Call compareTo method to compare two objects
Actual type must implement Comparable interface

21
1 // Fig. 18.5: MaximumTest.java
2 // Generic method maximum returns the largest of three objects.
3
4 public class MaximumTest Type parameter is used in the
5 { return type of method maximum
6 // determines the largest of three Comparable objects
7 public static < T extends Comparable< T > > T maximum( T x, T y, T z )
8 {
9 T max = x; // assume x is initially the largest
only object of classes that implement
10 interface Comparable can be used
11 if ( y.compareTo( max ) > 0 )
12 max = y; // y is the largest so far
13
14 if ( z.compareTo( max ) > 0 )
15 max = z; // z is the largest
16 Invokes method compareTo method
17 Comparable to compare z and max
return max; // returns the largest object
18 } // end method maximum
19

Generic interface: with a single interface declaration, a set of related types

E.g., Comparable< T >, all types that implement interface Comparable
22
 20
21
Outline
public static void main( String args[] )
{
22 System.out.printf( "Maximum of %d, %d and %d is %d\n\n", 3, 4, 5,
23 maximum( 3, 4, 5 ) );
24 System.out.printf( "Maximum of %.1f, %.1f and %.1f is %.1f\n\n",
25 6.6, 8.8, 7.7, maximum( 6.6, 8.8, 7.7 ) );
26 System.out.printf( "Maximum of %s, %s and %s is %s\n", "pear",
27 "apple", "orange", maximum( "pear", "apple", "orange" ) );
28 } // end main Invoke generic method
29 } // end class MaximumTest maximum with three strings

Maximum of 3, 4 and 5 is 5

Maximum of 6.6, 8.8 and 7.7 is 8.8

Maximum of pear, apple and orange is pear

23
 Compile-Time Translation
Upper bound of type parameter: constraints on actual
type
Default is Object
use keyword extends to specify
 E.g., T extends Comparable< T >

When compiler translates generic method to Java

bytecode
Replaces type parameter with its upper bound
Insert explicit cast operation
e.g., line 23 of Fig. 18.5 I preceded by an Integer cast
(Integer) maximum( 3, 4, 5 )

24
 Erasure
1 public static void printArray( Object[] inputArray )
2 {
3 // display array elements
4 for ( Object element : inputArray )
5 System.out.printf( "%s ", element );
6
7 System.out.println();
8 } // end method printArray

1 public static Comparable maximum(Comparable x, Comparable y, Comparable z)

2 {
3 Comparable max = x; // assume x is initially the largest
Erasure replaces type parameter T with
4
its upper bound Comparable
5 if ( y.compareTo( max ) > 0 )
6 max = y; // y is the largest so far
7
8 if ( z.compareTo( max ) > 0 )
9 max = z; // z is the largest
10
11 return max; // returns the largest object
25 12 } // end method maximum
 Overloading Generic Method
Generic method may be overloaded
By another generic method
 Same method name but different method parameters
By non-generic methods
 Same method name and number of parameters

When compiler encounters a method call

Search for most precise matching method first
 Exact method name and argument types
Then search for inexact but applicable matching method
Exercise:
Write a generic method bubbleSort based on your lab3

26
 Outline
Generics, new feature of J2SE 5.0
Provide compile-time type safety: catch invalid types at compile
time
Generic methods: A single method declaration => a set of related
methods
Generic classes: A single class declaration => a set of related
classes
Java collections framework, use generics
Contain prepackaged data structures, interfaces, algorithms
Use existing data structures
 Example of code reuse
Provides reusable components

27
 Generic Classes
Generic classes, parameterized classes, also called
parameterized types
Generic class declaration, looks like a non-generic class
declaration, except class name is followed by a type
parameter section
a simple, concise notation to indicate the actual type(s)
We study generic class Stack that implements basic stack
operations: push a new element onto stack, pop an element
from stack,…, independent of the actual element type
Instantiate a stack of different element type: e.g., Stack<
Double >, Stack<Integer>, Stack<Item>

28
1 // Fig. 18.7: Stack.java
2 // Generic class Stack.
3
4 public class Stack< E > Generic class declaration, class name is
5 { followed by a type parameter section
6 private final int size; // number of elements in the stack
7 private int top; // location of the top element
8 private E[] elements; // array that stores stack elements
9
10 Declareaelements
// no-argument constructor creates stack of as an default
the array size
11 public Stack() that stores objects of type E
12 {
13 this( 10 ); // default stack size
14 } // end no-argument Stack constructor
15
16 // constructor creates a stack of the specified number of elements
17 public Stack( int s )
18 {
19 size = s > 0 ? s : 10; // set size of Stack
20 top = -1; // Stack initially empty
21
22 elements = ( E[] ) new Object[ size ]; // create array
23 } // end Stack constructor
24 Create an array of type E. The generic
mechanism does not allow type parameter
29 in array-creation expressions because the
type parameter is not available at runtime
 25
26 Outline
// push element onto stack; if successful, return true;
// otherwise, throw FullStackException
27 public void push( E pushValue ) Method push pushes
28 { element of type E onto stack
29 if ( top == size - 1 ) // if stack is full
30 throw new FullStackException( String.format(
31 "Stack is full, cannot push %s", pushValue ) );
32
33 elements[ ++top ] = pushValue; // place pushValue on Stack
34 } // end method push
35
36 // return the top element if not empty; else throw EmptyStackException
37 public E pop()
Method pop returns the top
38 {
element, which is of type E
39 if ( top == -1 ) // if stack is empty
40 throw new EmptyStackException( "Stack is empty, cannot pop" );
41
42 return elements[ top-- ]; // remove and return top element of Stack
43 } // end method pop
44 } // end class Stack< E >

30
1 // Fig. 18.8: FullStackException.java
2 // Indicates a stack is full.
3 public class FullStackException extends RuntimeException
4 {
5 // no-argument constructor
6 public FullStackException()
7 {
8 this( "Stack is full" );
9 } // end no-argument FullStackException constructor
10
11 // one-argument constructor
12 public FullStackException( String exception )
13 {
14 super( exception );
15 } // end one-argument FullStackException constructor
16 } // end class FullStackException

31
1 // Fig. 18.9: EmptyStackException.java
2
3
Outline
// Indicates a stack is full.
public class EmptyStackException extends RuntimeException
4 {
5 // no-argument constructor
6 public EmptyStackException()
7 {
8 this( "Stack is empty" );
9 } // end no-argument EmptyStackException constructor
10
11 // one-argument constructor
12 public EmptyStackException( String exception )
13 {
14 super( exception );
15 } // end one-argument EmptyStackException constructor
16 } // end class EmptyStackException

32
 Generic Classes (Cont.)
Generic class at compilation time
Compiler performs erasure on class’s type parameters
Compiler replaces type parameters with their upper
bounds
Generic class test program at compilation time
Compiler performs type checking
Compiler inserts cast operations as necessary

33
 1 // Fig. 18.10: StackTest.java
2 // Stack generic class test program.
3
4 public class StackTest
5 {
6 private double[] doubleElements = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6 };
7 private int[] integerElements = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
8
9 Generic
private Stack< Double > doubleStack; // stack storesclass Stack’s
Double type
objects
10 argument
private Stack< Integer > integerStack; // stack is Double
stores Integer objects
11
12 // test Stack objects
Generic class Stack’s type
13 public void testStacks()
argument is Integer
14 {
15 doubleStack = new Stack< Double >( 5 ); // Stack of Doubles
16 integerStack = new Stack< Integer >( 10 ); // Stack of Integers
17
Instantiate object doubleStack of
18 testPushDouble(); // push double onto doubleStack
size 5 and ingeterStack of size 10
19 testPopDouble(); // pop from doubleStack
20 testPushInteger(); // push int onto intStack
21 testPopInteger(); // pop from intStack
22 } // end method testStacks
23

3
4
 24
25
26
Outline
// test push method with double stack
public void testPushDouble()
{
27 // push elements onto stack
28 try
29 {
30 System.out.println( "\nPushing elements onto doubleStack" );
31
32 // push elements to Stack
33 for ( double element : doubleElements )
34 {
35 System.out.printf( "%.1f ", element );
36 doubleStack.push( element ); // push onto doubleStack
37 } // end for
Invoke Stack’s method push to place
38 } // end try a double value onto doubleStack
39 catch ( FullStackException fullStackException )
40 {
41 System.err.println();
42 fullStackException.printStackTrace();
43 } // end catch FullStackException
44 } // end method testPushDouble
45

3
5
 46 // test pop method with double stack
47 public void testPopDouble()
48 {
49 // pop elements from stack
50 try
51 {
52 System.out.println( "\nPopping elements from doubleStack" );
53 double popValue; // store element removed from stack
54
55 // remove all elements from Stack
56 while ( true )
57 {
58 popValue = doubleStack.pop(); // pop from doubleStack
59 System.out.printf( "%.1f ", popValue );
60 } // end while Auto-unboxing occurs when the value
61 } // end try returned by pop (Double) is assigned
62 catch( EmptyStackException emptyStackException )
to a double primitive variable
63 {
64 System.err.println();
65 emptyStackException.printStackTrace();
66 } // end catch EmptyStackException
67 } // end method testPopDouble
68

3
6
 69 // test push method with integer stack
70
71
Outline
public void testPushInteger()
{
72 // push elements to stack
73 try
74 {
75 System.out.println( "\nPushing elements onto intStack" );
76
77 // push elements to Stack
78 for ( int element : integerElements )
79 {
80 System.out.printf( "%d ", element );
81 integerStack.push( element ); // push onto integerStack
82 } // end for Invoke Stack’s method push to place
83 } // end try an int value onto integerStack
84 catch ( FullStackException fullStackException )
85 {
86 System.err.println();
87 fullStackException.printStackTrace();
88 } // end catch FullStackException
89 } // end method testPushInteger
90

3
7
 91 // test pop method with integer stack
92 public void testPopInteger()
93
94
95
Outline
{
// pop elements from stack
try
96 {
97 System.out.println( "\nPopping elements from intStack" );
98 int popValue; // store element removed from stack
99 Auto-unboxing occurs when the value
100 // remove all elements from Stack returned by pop (Integer) is assigned
101 while ( true ) to an int primitive variable
102 {
103 popValue = integerStack.pop(); // pop from intStack
104 System.out.printf( "%d ", popValue );
105 } // end while
106 } // end try
107 catch( EmptyStackException emptyStackException )
108 {
109 System.err.println();
110 emptyStackException.printStackTrace();
111 } // end catch EmptyStackException
112 } // end method testPopInteger
113
114 public static void main( String args[] )
115 {
116 StackTest application = new StackTest();
117 application.testStacks();
118 } // end main
119 } // end class StackTest

38
 Outline
Pushing elements onto doubleStack
1.1 2.2 3.3 4.4 5.5 6.6
FullStackException: Stack is full, cannot push 6.6
at Stack.push(Stack.java:30)
at StackTest.testPushDouble(StackTest.java:36)
at StackTest.testStacks(StackTest.java:18)
at StackTest.main(StackTest.java:117)

Popping elements from doubleStack

5.5 4.4 3.3 2.2 1.1
EmptyStackException: Stack is empty, cannot pop
at Stack.pop(Stack.java:40)
at StackTest.testPopDouble(StackTest.java:58)
at StackTest.testStacks(StackTest.java:19)
at StackTest.main(StackTest.java:117)

Pushing elements onto integerStack

1 2 3 4 5 6 7 8 9 10 11
FullStackException: Stack is full, cannot push 11
at Stack.push(Stack.java:30)
at StackTest.testPushInteger(StackTest.java:81)
at StackTest.testStacks(StackTest.java:20)
at StackTest.main(StackTest.java:117)
Popping elements from integerStack
10 9 8 7 6 5 4 3 2 1
EmptyStackException: Stack is empty, cannot pop
at Stack.pop(Stack.java:40)
at StackTest.testPopInteger(StackTest.java:103)
at StackTest.testStacks(StackTest.java:21)
at StackTest.main(StackTest.java:117)

39
 Generic Classes (Cont.)
Creating generic methods to test class Stack< E >
Method testPush
 Perform same tasks as testPushDouble and
testPushInteger
Method testPop
 Perform same tasks as testPopDouble and testPopInteger

40
 1 // Fig. 18.11: StackTest2.java
2
3
4
Outline
// Stack generic class test program.

public class StackTest2

5 {
6 private Double[] doubleElements = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6 };
7 private Integer[] integerElements =
8 { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
9
10 private Stack< Double > doubleStack; // stack stores Double objects
11 private Stack< Integer > integerStack; // stack stores Integer objects
12
13 // test Stack objects
14 public void testStacks()
15 {
16 doubleStack = new Stack< Double >( 5 ); // Stack of Doubles
17 integerStack = new Stack< Integer >( 10 ); // Stack of Integers
18
19 testPush( "doubleStack", doubleStack, doubleElements );
20 testPop( "doubleStack", doubleStack );
21 testPush( "integerStack", integerStack, integerElements );
22 testPop( "integerStack", integerStack );
23 } // end method testStacks
24 Invoke generic methods testPush and
testPop to push elements onto stack
and pop elements from stack
41
 42
25
26 Outline
// generic method testPush pushes elements onto a Stack
public < T > void testPush( String name, Stack< T > stack,
27 T[] elements )
28 { Generic method testPush replaces
29 // push elements onto stack
testPushDouble and testPushInteger
30 try
31 {
32 System.out.printf( "\nPushing elements onto %s\n", name );
33
34 // push elements onto Stack
35 for ( T element : elements )
36 {
37 System.out.printf( "%s ", element );
38 stack.push( element ); // push element onto stack
Replace element type Double/Integer
39 }
with type parameter T
40 } // end try
41 catch ( FullStackException fullStackException )
42 {
43 System.out.println();
44 fullStackException.printStackTrace();
45 } // end catch FullStackException
46 } // end method testPush
47
 48 // generic method testPop pops elements from a Stack
49 public < T > void testPop( String name, Stack< T > stack )
50 {
51 // pop elements from stack Generic method testPop replaces

Outline
52 try
testPopDouble and testPopInteger
53 {
54 System.out.printf( "\nPopping elements from %s\n", name );
55 T popValue; // store element removed from stack
56
57 Replace
// remove elements from element
Stack type Double/Integer
58 while ( true ) with type parameter T
59 {
60 popValue = stack.pop(); // pop from stack
61 System.out.printf( "%s ", popValue );
62 } // end while
63 } // end try
64 catch( EmptyStackException emptyStackException )
65 {
66 System.out.println();
67 emptyStackException.printStackTrace();
68 } // end catch EmptyStackException
69 } // end method testPop
70
71 public static void main( String args[] )
72 {
73 StackTest2 application = new StackTest2();
74 application.testStacks();
75 } // end main
76 } // end class StackTest2

43
 Pushing elements onto doubleStack

Outline
1.1 2.2 3.3 4.4 5.5 6.6
FullStackException: Stack is full, cannot push 6.6
at Stack.push(Stack.java:30)
at StackTest2.testPush(StackTest2.java:38)
at StackTest2.testStacks(StackTest2.java:19)
at StackTest2.main(StackTest2.java:74)

Popping elements from doubleStack

5.5 4.4 3.3 2.2 1.1
EmptyStackException: Stack is empty, cannot pop
at Stack.pop(Stack.java:40)
at StackTest2.testPop(StackTest2.java:60)
at StackTest2.testStacks(StackTest2.java:20)
at StackTest2.main(StackTest2.java:74)

Pushing elements onto integerStack

1 2 3 4 5 6 7 8 9 10 11
FullStackException: Stack is full, cannot push 11
at Stack.push(Stack.java:30)
at StackTest2.testPush(StackTest2.java:38)
at StackTest2.testStacks(StackTest2.java:21)
at StackTest2.main(StackTest2.java:74)

Popping elements from integerStack

10 9 8 7 6 5 4 3 2 1
EmptyStackException: Stack is empty, cannot pop
at Stack.pop(Stack.java:40)
at StackTest2.testPop(StackTest2.java:60)
at StackTest2.testStacks(StackTest2.java:22)
at StackTest2.main(StackTest2.java:74)

44
 Outline
Generics, new feature of J2SE 5.0
Provide compile-time type safety: catch invalid types at compile time
Generic methods: A single method declaration => a set of related
methods
Generic classes: A single class declaration => a set of related classes
Data Structure: linked list
Java collections framework, use generics
Contain prepackaged data structures, interfaces, algorithms
Use existing data structures
 Example of code reuse
Provides reusable components

45
 Primer on Data structure
*

46
 How to store a collection of data
Array: fixed-size data structure for holding reference to
objects with same type
cannot grow and shrink at execution time
Dynamic data structure:
Linked list: collection of data items that link up in a chain

Tree: collection of data items that form a tree

47
 Linked list
Self-referential class: contains an instance variable that
refers to another object of the same class type, called a
link
Drawn as an line with arrow pointing to the other object
A null reference indicates that the link does not refer to
another object (drawn as a backslash in diagram)
Diagram of a linked list

48
data link
1 // Fig. 17.3: List.java
2 // ListNode and List class definitions.
3 package com.deitel.jhtp6.ch17;
4
5 // class to represent one node in a list
List.java
Field data can refer to any object
6 class ListNode  (1 of 6)
7 {
8 // package access members; List can access these directly
9 Object data;
10 ListNode nextNode; Stores a reference to the next
11 ListNode object in the linked list
12 // constructor creates a ListNode that refers to object
13 ListNode( Object object )
14 {
15 this( object, null );
16 } // end ListNode one-argument constructor
17
18 // constructor creates ListNode that refers to
19 // Object and to next ListNode
20 ListNode( Object object, ListNode node )
21 {
22 data = object;
23 nextNode = node;
24 } // end ListNode two-argument constructor
49
25
 26
27
// return reference to data in node
Object getObject()
Outline
28 {
29 return data; // return Object in this node
30 } // end method getObject
List.java
31
32 // return reference to next node in list  (2 of 6)
33 ListNode getNext()
34 {
35 return nextNode; // get next node
36 } // end method getNext
37 } // end class ListNode
38
39 // class List definition References to the first and last
40 public class List ListNodes in a List
41 {
42 private ListNode firstNode;
43 private ListNode lastNode;
44 private String name; // string like "list" used in printing
45
46 // constructor creates empty List with "list" as the name
47 public List()
48 {
49 this( "list" ); Call one-argument constructor
50 } // end List no-argument constructor
51
50
 52 // constructor creates an empty List with a name
53 public List( String listName )
54 {
55 name = listName; Initialize both references to null
56 firstNode = lastNode = null; List.java
57 } // end List one-argument constructor
 (3 of 6)
58
59 // insert Object at front of List
60 public void insertAtFront( Object insertItem )
61 {
62 if ( isEmpty() ) // firstNode and lastNode refer to same object
63 firstNode = lastNode = new ListNode( insertItem );
64 else // firstNode refers to new node
65 firstNode = new ListNode( insertItem, firstNode );
66 } // end method insertAtFront
67
68 // insert Object at end of List
69 public void insertAtBack( Object insertItem )
70 {
71 if ( isEmpty() ) // firstNode and lastNode refer to same Object
72 firstNode = lastNode = new ListNode( insertItem );
73 else // lastNode's nextNode refers to new node
74 lastNode = lastNode.nextNode = new ListNode( insertItem );
75 } // end method insertAtBack
76 Order of evaluation?
51
 77 // remove first node from List
78 public Object removeFromFront() throws EmptyListException
79 {
80 if ( isEmpty() ) // throw exception if List is empty
List.java
81 throw new EmptyListException( name );
82  (4 of 6)
83 Object removedItem = firstNode.data; // retrieve data being removed
84
85 // update references firstNode and lastNode
86 if ( firstNode == lastNode )
87 firstNode = lastNode = null;
88 else
89 firstNode = firstNode.nextNode;
90
91 return removedItem; // return removed node data
92 } // end method removeFromFront
93
94 // remove last node from List
95 public Object removeFromBack() throws EmptyListException
96 {
97 if ( isEmpty() ) // throw exception if List is empty
98 throw new EmptyListException( name );
99
100 Object removedItem = lastNode.data; // retrieve data being removed
101
52
 102 // update references firstNode and lastNode
Outline
103 if ( firstNode == lastNode )
104 firstNode = lastNode = null;
105 else // locate new last node
106 { List.java
107 ListNode current = firstNode;  (5 of 6)
108
109 // loop while current node does not refer to lastNode
110 while ( current.nextNode != lastNode )
111 current = current.nextNode;
112
113 lastNode = current; // current is new lastNode
114 current.nextNode = null;
115 } // end else
116
117 return removedItem; // return removed node data
118 } // end method removeFromBack
119
120 // determine whether list is empty Predicate method that determines
121 public boolean isEmpty() whether the list is empty
122 {
123 return firstNode == null; // return true if List is empty
124 } // end method isEmpty
125

53
 126 // output List contents Outline
127 public void print() Display the list’s contents
128 {
129 if ( isEmpty() )
130 { List.java
131 System.out.printf( "Empty %s\n", name );  (6 of 6)
132 return;
133 } // end if
134
135 System.out.printf( "The %s is: ", name );
136 ListNode current = firstNode;
137
138 // while not at end of list, output current node's data
139 while ( current != null ) Output a string representation
140 { of current.data
141 System.out.printf( "%s ", current.data );
142 current = current.nextNode;
143 } // end while
144
145 System.out.println( "\n" );
Move to the next node in the list
146 } // end method print
147 } // end class List

54
1 // Fig. 17.4: EmptyListException.java
2 // Class EmptyListException definition. An unchecked exception
EmptyListEx
3 package com.deitel.jhtp6.ch17;
4 ception.java
5 public class EmptyListException extends RuntimeException
6 {
7 // no-argument constructor
8 public EmptyListException()
9 {
10 this( "List" ); // call other EmptyListException constructor
11 } // end EmptyListException no-argument constructor
12
13 // one-argument constructor
14 public EmptyListException( String name )
15 {
16 super( name + " is empty" ); // call superclass constructor
17 } // end EmptyListException one-argument constructor
18 } // end class EmptyListException

55
 1 // Fig. 17.5: ListTest.java
2
3 Outline
// ListTest class to demonstrate List capabilities.
import com.deitel.jhtp6.ch17.List;
4 import com.deitel.jhtp6.ch17.EmptyListException;
5
6 public class ListTest
7 {
8 public static void main( String args[] )
9 {
10 List list = new List(); // create the List container
11
12 // insert integers in list
13 list.insertAtFront( -1 );
14 list.print();
15 list.insertAtFront( 0 );
16 list.print();
17 list.insertAtBack( 1 );
18 list.print();
19 list.insertAtBack( 5 );
20 list.print();
21

56
 22 // remove objects from list; print after each removal
23 try
24 {
25 Object removedObject = list.removeFromFront();
26 System.out.printf( "%s removed\n", removedObject );
27 list.print();
28
29 removedObject = list.removeFromFront();
30 System.out.printf( "%s removed\n", removedObject );
31 list.print();
32
33 removedObject = list.removeFromBack();
34 System.out.printf( "%s removed\n", removedObject );
35 list.print();
36
37 removedObject = list.removeFromBack();
38 System.out.printf( "%s removed\n", removedObject );
39 list.print();
40 } // end try
41 catch ( EmptyListException emptyListException )
42 {
43 emptyListException.printStackTrace();
44 } // end catch
45 } // end main
46 } // end class ListTest

57
 Trees
Trees:
Has a single root node
Each node has multiple links, each
referring to a child node
Left child is the root of the left subtree
Right child is the root of the right
subtree
Siblings are the children of a specific
node
A leaf node has no children, i.e.,
null links

58
  Trees (Cont.)
Binary search trees
Value stores in a node,
 Larger than values stored in its left subtree
 Smaller than values stored in its right
subtree
Searching is easy:
Compare value to search for with root
If smaller, goes to left subtree; if
larger, goes to right subtree; if same,
return found …
Other algorithms:
traversing a tree: inorder, preorder,
postorder
59
 Abstract Data Structure (ADT)
 Many applications need to use collections with access
constraints
List: a collection of data stored in certain order where
insertion and deletion can be made any where in the order
 E.g. Insert an element at the 5 th position
Stack: insertion and deletion are made at one end only, i.e.,
top
 Used in compiler, operating system
Queue: insertion made at one end (tail) and deletion made at
another end (head)
Implementation details are hidden
Can use array or linked list to implement above ADT

60
 Stacks
Stacks, Last-in, first-out (LIFO) data structure
Method push adds a new node to the top of the stack
Method pop removes a node from the top of the stack
and returns the data from the popped node
Application example:
Program execution stack
 Holds the return addresses , local variables and parameters of
method invocation
Used by the compiler to evaluate arithmetic expressions

61
 Stack Implementation option 1
Stack class that inherits from List
Stack methods push, pop, isEmpty and print are
performed by inherited methods insertAtFront,
removeFromFront, isEmpty and print
 push calls insertAtFront
 pop calls removeFromFront
 isEmpty and print can be called as inherited
Other List methods are also inherited
 Including methods that should not be in the stack class’s public
interface

62
  Stacks implementation option 2
Stack class that contains a reference to a List
Each stack method invoked delegates the call to the
appropriate List method
 method push delegates to List method insertAtFront
 method pop delegates to List method removeFromFront
 method isEmpty delegates to List method isEmpty
 method print delegates to List method print
Enables us to hide the List methods that should not be
in our stack’s public interface

63
 Outline
1 // Fig. 17.12: StackComposition.java
2 // Class StackComposition definition with composed List object.
3 package com.deitel.jhtp6.ch17;
4
5 public class StackComposition
6 {
7 private List stackList;
private List reference
8
9 // no-argument constructor
10 public StackComposition()
11 {
12 stackList = new List( "stack" );
13 } // end StackComposition no-argument constructor
14
15 // add object to stack
16 public void push( Object object )
push method delegates call to List
17 {
method insertAtFront
18 stackList.insertAtFront( object );
19 } // end method push
20

64
 21
22
Outline
// remove object from stack
public Object pop() throws EmptyListException
23 {
24 return stackList.removeFromFront(); Method pop delegates call to List
25 } // end method pop method removeFromFront
26
27 // determine if stack is empty
28 public boolean isEmpty()
29 {
30 return stackList.isEmpty();
Method isEmpty delegates call to
31 } // end method isEmpty
List method isEmpty
32
33 // output stack contents
34 public void print()
35 { Method print delegates call to
36 stackList.print(); List method print
37 } // end method print
38 } // end class StackComposition

65
 Queues
Queue, First-in, first-out (FIFO) data structure
Similar to a checkout line in a supermarket
Enqueue: inserts nodes at the tail (or end)
Dequeue: removes nodes from the head (or front)
Application example:
Used to support print spooling: a spooler program
manages the queue of printing jobs
Multi-thread programming: a pool of thread, a
queue of tasks

66
 Queues implementation
Queue class that contains a reference to a List
Method enqueue calls List method
insertAtBack
Method dequeue calls List method
removeFromFront
Method isEmpty calls List method isEmpty
Method print calls List method print

67
 Outline
1 // Fig. 17.13: Queue.java
2 // Class Queue.
3 package com.deitel.jhtp6.ch17;
4
5 public class Queue
6 { An object of class List
7 private List queueList;
8
9 // no-argument constructor
10 public Queue()
11 {
12 queueList = new List( "queue" );
13 } // end Queue no-argument constructor
Method enqueue calls List
14
method insertAtBack
15 // add object to queue
16 public void enqueue( Object object )
17 {
18 queueList.insertAtBack( object );
19 } // end method enqueue
20

68
 21 // remove object from queue
22
23 {Outline
public Object dequeue() throws EmptyListException
Method dequeue calls List
24 return queueList.removeFromFront(); method removeFromFront
25 } // end method dequeue
26
27 // determine if queue is empty
28 public boolean isEmpty()
29 {
30 return queueList.isEmpty();
31 } // end method isEmpty
32
33 // output queue contents
34 public void print()
35 {
36 queueList.print();
37 } // end method print
38 } // end class Queue

69
 Outline
1 // Fig. 17.14: QueueTest.java
2 // Class QueueTest.
3 import com.deitel.jhtp6.ch17.Queue;
4 import com.deitel.jhtp6.ch17.EmptyListException;
Create a Queue object
5
6 public class QueueTest
7 {
8 public static void main( String args[] )
9 {
Enqueue four integers
10 Queue queue = new Queue();
11
12 // use enqueue method
13 queue.enqueue( -1 );
14 queue.print();
15 queue.enqueue( 0 );
16 queue.print();
17 queue.enqueue( 1 );
18 queue.print();
19 queue.enqueue( 5 );
20 queue.print();
21

70
22 // remove objects from queue
23 try
24 {
Dequeue the objects in
25 Object removedObject = null; first-in, first-out order
26
27 while ( true )
28 {
29 removedObject = queue.dequeue(); // use dequeue method
30 System.out.printf( "%s dequeued\n", removedObject );
31 queue.print();
32 } // end while
Display the exception’s stack trace
33 } // end try
34 catch ( EmptyListException emptyListException )
35 {
36 emptyListException.printStackTrace();
37 } // end catch
38 } // end main
39 } // end class QueueTest

71
 Outline
The queue is: -1

The queue is: -1 0

The queue is: -1 0 1

The queue is: -1 0 1 5

-1 dequeued
The queue is: 0 1 5

0 dequeued
The queue is: 1 5

1 dequeued
The queue is: 5

5 dequeued
Empty queue
com.deitel.jhtp6.ch17.EmptyListException: queue is empty
at com.deitel.jhtp6.ch17.List.removeFromFront(List.java:81)
at com.deitel.jhtp6.ch17.Queue.dequeue(Queue.java:24)
at QueueTest.main(QueueTest.java:29)

72
 End of primer

73
 Java Collections Framework
A unified architecture for representing and manipulating
collections. It contains:
Interfaces: abstract data types that represent collections.
Interfaces allow collections to be manipulated independently of the
details of their representation.
Implementations: concrete implementations of collection
interfaces. They are reusable data structures.
Algorithms: methods that perform useful computations, such as
searching and sorting, on objects that implement collection
interfaces.
 polymorphic: same method can be used on many different implementations
of the appropriate collection interface. In essence, algorithms are reusable
functionality.

74
 Some collection framework interfaces
 Java Collections Framework: enhanced with generics
capabilities in J2SE 5.0
 Allow one to declare a stack of Card, a queue of Customers, using
the type parameter
 Compile-time type checking ensure only objects of given type can
be stored into the collection
 Object retrieved from the collection is cast to appropriate type
 In comparison, implementation of stack/queue seen so far
store a collection of Object
 One can store different objects into it
 Programmer needs to cast the object retrieved to its original type
…

75
 Java Collection Framework:
Interfaces Hierarchy

These interfaces allow collections to be manipulated independently

of the details of their representation.

76
 Collection Interface hierarchy
Collection interface: basic functionality used by all
collections, such as add and remove methods
Set interface: does not allow duplicate elements
useful for storing collections such as a deck of cards or student
records.
a subinterface, SortedSet, provides for ordering of elements
List interface: an ordered collection, provides precise control
over where each element is inserted or retrieved from
Queue interface: additional insertion, extraction, and
inspection operations.
elements in a Queue are typically ordered in on a FIFO basis.

77
 Collection Interface hierarchy (2)
Map interface: maps keys and values similar to a
Hashtable.
Map's subinterface, SortedMap, maintains its key-value
pairs in ascending order or in an order specified by a
Comparator.

78
 Collection Interfaces are generic
All core collection interfaces are generic.
E.g, the declaration of the Collection interface:
public interface Collection<E>...
The <E> syntax tells you that the interface is generic.
When you declare a Collection instance you can and
should specify the type of object contained in the
collection.
Allow compiler to verify (at compile-time) that the type
of object you put into the collection is correct, reducing
errors at runtime.

79
 Collection Interface
public interface Collection<E> extends Iterable<E>
{
// Basic operations
int size();
boolean isEmpty();
boolean contains(Object element);
boolean add(E element); //optional
boolean remove(Object element); //optional

80
 Collection Interface (cont’d)
Return a iterator: an object for traversing through a
Iterator<E> iterator(); collection and to remove elements from the collection
// Bulk operations selectively
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c); //optional
boolean removeAll(Collection<?> c); //optional
boolean retainAll(Collection<?> c); //optional
void clear(); //optional
// Array operations
Object[] toArray();
<T> T[] toArray(T[] a);
}

81
 General-purpose Implementations
Interface
 Implementation
Interfaces Implementations
 Hash Resizable Tree
  Hash table Linked
Resizable Hash
array Tree
table array list table+Linked list
Linked list Hash table + Linked list Set HashSet  
Set HashSe TreeSet LinkedHashSet
TreeSet
t
  LinkedHashSet List   ArrayList   LinkedList  
Queue           Map HashMap   TreeMap  
List ArrayList LinkedList
LinkedHashMap
Queue

Map HashMap TreeMap LinkedHashMap

82
 Lists: ordered collection
List: ordered Collection that can
contain duplicates
Implemented via interface List
ArrayList, vector
ArrayList behaves like Vector without
synchronization and therefore execute faster than
Vectors (no overhead of thread synchronization)
LinkedLists can be used to create stacks,
queues, trees and deques (double-ended queues,
pronounced “decks”).

83
 ArrayList and Iterator
ArrayList example
Demonstrate Collection interface capabilities
Place two String arrays in ArrayLists
Use Iterator to remove elements in ArrayList

84
1 // Fig. 19.3: CollectionTest.java
2
3
Outline
// Using the Collection interface.
import java.util.List;
4 import java.util.ArrayList;
5 import java.util.Collection;
6 import java.util.Iterator;
7
8 public class CollectionTest
9 {
10 private static final String[] colors =
11 { "MAGENTA", "RED", "WHITE", "BLUE", "CYAN" };
12 private static final String[] removeColors =
13 { "RED", "WHITE", "BLUE" };
14
15 Create ArrayList
// create ArrayList, add Colors to it and manipulate it objects and assign
16 public CollectionTest() their references to variable list and
17 { removeList, respectively
18 List< String > list = new ArrayList< String >();
19 List< String > removeList = new ArrayList< String >();
20

85
 21 // add elements in colors array to list
22 for ( String color : colors )
23
24 Outlinelist.add( color ); add objects to list and
removeList, respectively
25 // add elements in removeColors to removeList
26 for ( String color : removeColors )
27 removeList.add( color ); Get number of
28 ArrayList elements
29 System.out.println( "ArrayList: " );
30
31 // output list contents
32 for ( int count = 0; count < list.size(); count++ )
33 System.out.printf( "%s ", list.get( count ) );
34
retrieve individual element values
35 // remove colors contained in removeList
36 removeColors( list, removeList );
37
38 System.out.println( "\n\nArrayList after calling removeColors: " );
39
40 // output list contents
41 for ( String color : list )
42 System.out.printf( "%s ", color ); Method removeColors takes two
43 } // end CollectionTest constructor Collections as arguments; Line 36
44
passes two Lists, which extends
Collection, to this method
86
 45 // remove colors specified in collection2 from collection1
46 private void removeColors(
47
48 Outline
{
Collection< String > collection1, Collection< String > collection2 )
Take any Collections containing
49 // get iterator strings as arguments
50 Iterator< String > iterator = collection1.iterator();
51
52 // loop while collection has items hasNext determines whether the
53 while ( iterator.hasNext() ) Iterator contains more elements
54
55 if ( collection2.contains( iterator.next() ) )
56 iterator.remove(); // remove current Color next returns a reference
57 } // end method removeColors to the next element
58
59 public static void main( String args[] )
60 { contains determines whether
61 new CollectionTest(); collection2 contains the element
62 } // end main
returned by next
63 } // end class CollectionTest

ArrayList: Use Iterator method remove to

MAGENTA RED WHITE BLUE CYAN
remove String from Iterator
ArrayList after calling removeColors:
MAGENTA CYAN

87
 Common Programming Error
If a collection is modified by one of its methods
after an iterator is created for that collection, the
iterator immediately becomes invalid—any
operations performed with the iterator after this
point throw
ConcurrentModificationExceptions . For
this reason, iterators are said to be “fail fast.”

88
 LinkedList
LinkedList example
Add elements of one List to the other
Convert Strings to uppercase
Delete a range of elements

89
1 // Fig. 19.4: ListTest.java

Outline
2 // Using LinkLists.
3 import java.util.List;
4 import java.util.LinkedList;
5 import java.util.ListIterator;
6
7 public class ListTest
8 {
9 private static final String colors[] = { "black", "yellow",
10 "green", "blue", "violet", "silver" };
11 private static final String colors2[] = { "gold", "white",
12 "brown", "blue", "gray", "silver" };
13
14 // set up and manipulate LinkedList objects
15 public ListTest()
16 {
17 List< String > list1 = new LinkedList< String >();
18 List< String > list2 = new LinkedList< String >();
19
20 // add elements to list link
Create two
21 for ( String color : colors )
LinkedList objects
22 list1.add( color );
23
Use List method add to append elements from
array colors to the end of list1
90
 24 // add elements to list link2
25 for ( String color : colors2 )
26 list2.add( color ); Use List method add to append elements from
27
28
29
Outline array colors2 to the end of list2
list1.addAll( list2 ); // concatenate lists
list2 = null; // release resources
30 Use
printList( list1 ); // print list1 elements List method addAll to append all
31
elements of list2 to the end of list1
32 convertToUppercaseStrings( list1 ); // convert to upper case string
33 printList( list1 ); // print list1 elements
34
35 System.out.print( "\nDeleting elements 4 to 6..." );
36 removeItems( list1, 4, 7 ); // remove items 4-7 from list
37 printList( list1 ); // print list1 elements
38 printReversedList( list1 ); // print list in reverse order
39 } // end ListTest constructor
40
41 // output List contents
42 public void printList( List< String > list )
43 {
44 System.out.println( "\nlist: " );
Method printList allows any
45 Lists containing strings to be
46 for ( String color : list ) passed as arguments to this method
47 System.out.printf( "%s ", color );
48
49 System.out.println();
50 } // end method printList
51

91
 52 // locate String objects and convert to uppercase
53
54
55
Outline
private void convertToUppercaseStrings( List< String > list )
{
ListIterator< String > iterator = list.listIterator();
56
57 while ( iterator.hasNext() )
58 {
59 String color = iterator.next(); // get item
60 iterator.set( color.toUpperCase() ); // convert to upper case
61 } // end while
62 } // end method convertToUppercaseStrings
63
64 // obtain sublist and use clear method to delete sublist items
65 private void removeItems( List< String > list, int start, int end )
66 {
67 anyitems
list.subList( start, end ).clear(); // remove List that contains strings
68 } // end method removeItems
69
70 // print reversed list subList: obtain a portion of the List
71 private void printReversedList( List< String > list )
72 {
73 ListIterator< String > iterator = list.listIterator( list.size() );
74
calllistIterator with one argument
(starting position) to get a bidirectional
92 iterator
 hasPrevious: determine whether there are
more elements while traversing the list backward

Outline
75 System.out.println( "\nReversed List:" );
76
77 // print list in reverse order
78 while ( iterator.hasPrevious() )
79 System.out.printf( "%s ", iterator.previous() );
80 } // end method printReversedList Invoke ListIterator method
81 previous to get the previous
82 public static void main( String args[] ) element from the list
83 {
84 new ListTest();
85 } // end main
86 } // end class ListTest

list:
black yellow green blue violet silver gold white brown blue gray silver

list:
BLACK YELLOW GREEN BLUE VIOLET SILVER GOLD WHITE BROWN BLUE GRAY SILVER

Deleting elements 4 to 6...

list:
BLACK YELLOW GREEN BLUE WHITE BROWN BLUE GRAY SILVER

Reversed List:
SILVER GRAY BLUE BROWN WHITE BLUE GREEN YELLOW BLACK

93
 Sets
Set interface: Collection that contains unique
elements
Implementations:
HashSet
 Stores elements in hash table
TreeSet
 Stores elements in tree

Example: using HashSet to find unique elements in a

collection …

94
1 // Fig. 19.18: SetTest.java
2
3
Outline
// Using a HashSet to remove duplicates.
import java.util.List;
4 import java.util.Arrays;
5 import java.util.HashSet;
6 import java.util.Set;
7 import java.util.Collection;
8
9 public class SetTest
10 {
11 private static final String colors[] = { "red", "white", "blue",
12 "green", "gray", "orange", "tan", "white", "cyan",
13 "peach", "gray", "orange" };
14
15 // create and output ArrayList
16 public SetTest() Create a List that
17 { contains String objects
18 List< String > list = Arrays.asList( colors );
19 System.out.printf( "ArrayList: %s\n", list );
20 printNonDuplicates( list );
21 } // end SetTest constructor
22

95
 Method printNonDuplicates accepts
a Collection of type String
23 // create set from array to eliminate duplicates

Outline
24 private void printNonDuplicates( Collection< String > collection )
25 {
26 // create a HashSet
27 Set< String > set = new HashSet< String >( collection );
28
29 System.out.println( "\nNonduplicates are: " );
30
31 for ( String s : set )
Conversion construct: create a
32 System.out.printf( "%s ", s ); HashSet from Collection
33 argument
34 System.out.println();
35 } // end method printNonDuplicates
36
37 public static void main( String args[] )
38 {
39 new SetTest();
40 } // end main
41 } // end class SetTest

ArrayList: [red, white, blue, green, gray, orange, tan, white, cyan, peach, gray,
orange]

Nonduplicates are:
red cyan white tan gray green orange blue peach

96
 Software Engineering Observation
Collection interface is used to pass around
collections of objects where maximum generality is
desired.
The collection might be a linked list, an array list, a set , …
E.g., All general-purpose collection implementations have a
conversion constructor that takes a Collection argument. It
initializes new collection to contain all elements in
specified collection
Next: useful Collection methods for manipulating
any collections

97
 How to iterate Collection
for-each construct: to concisely traverse a collection
or array using a for loop.
for (Object o : collection)
System.out.println(o);
Using Iterator: an object for traversing through a
collection and to remove elements from the collection
selectively, if desired.
Use Iterator instead of the for-each construct when you
need to remove element.

98
 Iterator
1. Get an Iterator for a collection by calling its
iterator method
2. Call methods of Iterator to traverse through collection
Iterator interface:
public interface Iterator<E> {
boolean hasNext();
E next();
void remove(); //optional
}
hasNext: returns true if iteration has more elements
next: returns next element in the iteration.

99
 Iterator: remove method
remove: removes last element that was returned by
next from underlying Collection.
only safe way to modify a collection during iteration
may be called only once per call to next and throws an
exception if this rule is violated.
 behavior is unspecified if underlying collection is modified in any
other way while iteration is in progress.

100
 toArray method
 toArray: translate contents of a Collection into an array.
 a bridge between collections and older APIs that expect arrays
on input
 Object[] toArray(); //creates a new array of Object.
 <T> T[] toArray(T[] a); //allows caller to provide an
array or to choose runtime type of output array.
E.g, to dump contents of a Collection c into a newly
allocated array of Object
 Object[] a = c.toArray();
E.g., suppose that c is known to contain only string, to
dumps contents of c into a newly allocated array of String:
 String[] a = c.toArray(new String[0]);
101
 Java Collection Framework:
Interfaces

102
 Maps
Map interface: associates keys to values, one-to-one
mapping (no duplicate keys)
Implementation classes
 Hashtable, HashMap
 Store elements in hash tables
 TreeMap
 Store elements in trees
Interface SortedMap
 Extends Map
 Maintains its keys in sorted order

103
 hash table
Hash tables: data structure that use hashing, an
algorithm for determining a key in table
Each table cell is a hash “bucket”, i.e., linked list of all
key-value pairs that hash to that cell (collision)
Load factor in a hash table: average length of bucket

Hash table

104
 1
2
3
Outline
// Fig. 19.20: WordTypeCount.java
// Program counts the number of occurrences of each word in a string
import java.util.StringTokenizer;
4 import java.util.Map;
5 import java.util.HashMap;
6 import java.util.Set;
7 import java.util.TreeSet;
8 import java.util.Scanner;
9
10 public class WordTypeCount Create an empty HashMap with
11 { a default capacity 16 and a
12 private Map< String, Integer > map; default load factor 0.75. The
13 private Scanner scanner; keys are of type String and the
14 values are of type Integer
15 public WordTypeCount()
16 {
17 map = new HashMap< String, Integer >(); // create HashMap
18 scanner = new Scanner( System.in ); // create scanner
19 createMap(); // create map based on user input
20 displayMap(); // display map content
21 } // end WordTypeCount constructor
22

105
 Create a StringTokenizer to break
23 // create map from user input input string into individual words
24
25 Outline
private void createMap()
{
26 System.out.println( "Enter a string:" ); // prompt for user input
27 String input = scanner.nextLine();
28
29 // create StringTokenizer for input
30 StringTokenizer tokenizer = new StringTokenizer( input );
31
32 // processing input text
containsKey: whether a key
33 while ( tokenizer.hasMoreTokens() ) // whilespecified as an argument is
more input in hash table
34 {
35 String word = tokenizer.nextToken().toLowerCase(); // get word
36
37 // if the map contains the word Use method get to obtain the key’s
38 associated value in the map
if ( map.containsKey( word ) ) // is word in map
39 {
40 int count = map.get( word ); // get current count
41 map.put( word, count + 1 ); // increment count
42 } // end if
43 else
44 map.put( word, 1 ); // add new word with a count of 1 to map
45 } // end while
Increment the value and use method put
46 } // end method createMap
47
to replace the key’s associated value

106
 Outline
48 // display map content
Use HashMap method keySet to
49 private void displayMap()
obtain a set of the keys
50 {
51 Set< String > keys = map.keySet(); // get keys
52
53 // sort keys
54 TreeSet< String > sortedKeys = new TreeSet< String >( keys );
55
56 System.out.println( "Map contains:\nKey\t\tValue" );
57 Access each key and its
58 // generate output for each key in map value in the map
59 for ( String key : sortedKeys )
60 System.out.printf( "%-10s%10s\n", key, map.get( key ) );
61
62 System.out.printf(
63 "\nsize:%d\nisEmpty:%b\n", map.size(), map.isEmpty() );
64 } // end method displayMap
65

Call Map method size to get the Call Map method isEmpty to
number of key-value pairs in the Map determine whether the Map is empty
107
 66 public static void main( String args[] )
67
68 Outline
{
new WordTypeCount();
69 } // end main
70 } // end class WordTypeCount

Enter a string:
To be or not to be: that is the question Whether 'tis nobler to suffer
Map contains:
Key Value
'tis 1
be 1
be: 1
is 1
nobler 1
not 1
or 1
question 1
suffer 1
that 1
the 1
to 3
whether 1

size:13
isEmpty:false

108
 Collections algorithms
Collections framework provides set of algorithms,
implemented as static methods of Collections class
Algorithm Description
sort Sorts the elements of a List.
binarySearch Locates an object in a List.
reverse Reverses the elements of a List.
shuffle Randomly orders a List’s elements.
fill Sets every List element to refer to a specified object.
Copy Copies references from one List into another.
min Returns the smallest element in a Collection.
max Returns the largest element in a Collection.
addAll Appends all elements in an array to a collection.
frequency Calculates how many elements in the collection are equal to the
specified element.
disjoint Determines whether two collections have no elements in common.
109
 Software Engineering Observation
Collections framework algorithms are polymorphic method
first argument is the collection on which the operation is to be
performed.
 majority of the algorithms operate on List instances,
 a few operate on arbitrary Collection instances.
Each algorithm can operate on objects that implement specific
interfaces, regardless of the underlying implementations.

110
 Algorithm sort
 sort
 Sorts List elements
 Order is determined by natural order of elements’ type
 List elements must implement the Comparable interface
 Or, pass a Comparator to method sort

 Sorting in ascending order

 Collections method sort
 Sorting in descending order
 Collections static method reverseOrder
 Sorting with a Comparator
 Create a custom Comparator class

111
 Example
import java.util.*;
public class Sort {
public static void main(String[] args) {
List<String> list = Arrays.asList(args);
Collections.sort(list);
System.out.println(list);
}
}

112
 1 // Fig. 19.8: Sort1.java
2
3
Outline
// Using algorithm sort.
import java.util.List;
4 import java.util.Arrays;
5 import java.util.Collections;
6
7 public class Sort1
8 {
9 private static final String suits[] =
10 { "Hearts", "Diamonds", "Clubs", "Spades" };
11
12 // display array elements
13 public void printElements()
14 {
15 List< String > list = Arrays.asList( suits ); // create List
16 Create List of Strings

113
 17 // output list
18
19
Outline
System.out.printf( "Unsorted array elements:\n%s\n", list );

20 Collections.sort( list ); // sort ArrayList Implicit call to the list’

21 toString method to
22 // output list output the list contents
23 System.out.printf( "Sorted array elements:\n%s\n", list );
24 } // end method printElements
25 Use algorithm sort to order the
26 public static void main( String args[] ) elements of list in ascending order
27 {
28 Sort1 sort1 = new Sort1();
29 sort1.printElements();
30 } // end main

31 } // end class Sort1

Unsorted array elements:

[Hearts, Diamonds, Clubs, Spades]
Sorted array elements:
[Clubs, Diamonds, Hearts, Spades]

114
 1
2
3
Outline
// Fig. 19.9: Sort2.java
// Using a Comparator object with algorithm sort.
import java.util.List;
4 import java.util.Arrays;
5 import java.util.Collections;
6
7 public class Sort2
8 {
9 private static final String suits[] =
10 { "Hearts", "Diamonds", "Clubs", "Spades" };
11
12 // output List elements
13 public void printElements()
14 {
15 List list = Arrays.asList( suits ); // create List
16

115
 Method reverseOrder of class
17 // output List elements Collections returns a

Outline
18 System.out.printf( "Unsorted array Comparator
elements:\n%s\n", list ); object that represents
19 the collection’s reverse order
20 // sort in descending order using a comparator
21 Collections.sort( list, Collections.reverseOrder() );
22
23 // output List elements
24 System.out.printf( "Sorted list elements:\n%s\n", list );
25 } // end method printElements
26
27 public static void main( String args[] )
28 { Method sort of class Collections can use a
29 Sort2 sort2 = new Sort2(); Comparator object to sort a List
30 sort2.printElements();
31 } // end main

32 } // end class Sort2

Unsorted array elements:

[Hearts, Diamonds, Clubs, Spades]
Sorted list elements:
[Spades, Hearts, Diamonds, Clubs]

116
 Custom comparator TimeComparator
1 // Fig. 19.10: TimeComparator.java
2 // Custom Comparator class that compares two
implements Comparator interface and
Time2 objects.

Outline
3 import java.util.Comparator; compares Time2 object
4
5 public class TimeComparator implements Comparator< Time2 >
6 {
7 public int compare( Time2 tim1, Time2 time2 )
8 {
9 int hourCompare = time1.getHour() - time2.getHour(); // compare hour
10
11 // test the hour first
12 if ( hourCompare != 0 ) Implement method compare to determine
13 return hourCompare; the order of two Time2 objects
14
15 int minuteCompare =
16 time1.getMinute() - time2.getMinute(); // compare minute
17
18 // then test the minute
19 if ( minuteCompare != 0 )
20 return minuteCompare;
21
22 int secondCompare =
23 time1.getSecond() - time2.getSecond(); // compare second
24
25 return secondCompare; // return result of comparing seconds
26 } // end method compare
27 } // end class TimeComparator

117
 1 // Fig. 19.11: Sort3.java
2
3 Outline
// Sort a list using the custom Comparator class TimeComparator.
import java.util.List;
4 import java.util.ArrayList;
5 import java.util.Collections;
6
7 public class Sort3
8 {
9 public void printElements()
10 {
11 List< Time2 > list = new ArrayList< Time2 >(); // create List
12
13 list.add( new Time2( 6, 24, 34 ) );
14 list.add( new Time2( 18, 14, 58 ) );
15 list.add( new Time2( 6, 05, 34 ) );
16 list.add( new Time2( 12, 14, 58 ) );
17 list.add( new Time2( 6, 24, 22 ) );
18

118
 19
20
21
Outline
// output List elements
System.out.printf( "Unsorted array elements:\n%s\n", list );

22 // sort in order using a comparator

23 Collections.sort( list, new TimeComparator() );
24
25 // output List elements
26 System.out.printf( "Sorted list elements:\n%s\n", list );
27 } // end method printElements
28 Sort in order using a custom
29 public static void main( String args[] ) comparator TimeComparator
30 {
31 Sort3 sort3 = new Sort3();
32 sort3.printElements();
33 } // end main
34 } // end class Sort3

Unsorted array elements:

[6:24:34 AM, 6:14:58 PM, 6:05:34 AM, 12:14:58 PM, 6:24:22 AM]
Sorted list elements:
[6:05:34 AM, 6:24:22 AM, 6:24:34 AM, 12:14:58 PM, 6:14:58 PM]

119
 Algorithms on List
reverse: Reverses the order of List elements
fill: populates List elements with values
copy: Creates copy of a List
max: Returns largest element in List
min: Returns smallest element in List
 binarySearch: Locates object in List

120
 1 // Fig. 19.13: Algorithms1.java
2 // Using algorithms reverse, fill, copy, min and max.

Outline
3 import java.util.List;
4 import java.util.Arrays;
5 import java.util.Collections;
6
7 public class Algorithms1
8 {
9 private Character[] letters = { ‘P’, ‘C’, ‘M’ };
10 private Character[] lettersCopy;
11 private List< Character > list;
12 private List< Character > copyList;
13
14 // create a List and manipulate it with methods from Collections
15 public Algorithms1()
16 {
17 list = Arrays.asList( letters ); // get List
18 lettersCopy = new Character[ 3 ];
19 copyList = Arrays.asList( lettersCopy ); // list view of lettersCopy
20 Use method reverse of
21 System.out.println( "Initial list: " ); class Collections to
22 output( list ); obtain List in reverse order
23
24 Collections.reverse( list ); // reverse order
25 System.out.println( "\nAfter calling reverse: " );
26 output( list );
27

121
 Outline
28 Collections.copy( copyList, list ); // copy List
29 System.out.println( "\nAfter copying: " );
30 output( copyList );
Use method copy of class
31
Collections to obtain copy of List
32 Collections.fill( list, ‘R’ ); // fill list with Rs
33 System.out.println( "\nAfter calling fill: " );
34 output( list );
35 } // end Algorithms1 constructor
36 Use method fill of class Collections
37 // output List information to populate List with the letter ‘R’
38 private void output( List< Character > listRef )
39 {
40 System.out.print( "The list is: " );
41
42 for ( Character element : listRef )
43 System.out.printf( "%s ", element );
44
45 System.out.printf( "\nMax: %s", Collections.max( listRef ) );
46 System.out.printf( " Min: %s\n", Collections.min( listRef ) );
47 } // end method output
48
Obtain minimum value in List

122
 49 public static void main( String args[] )
50
51
Outline
{
new Algorithms1();
52 } // end main
53 } // end class Algorithms1

Initial list:
The list is: P C M
Max: P Min: C

After calling reverse:

The list is: M C P
Max: P Min: C

After copying:
The list is: M C P
Max: P Min: C

After calling fill:

The list is: R R R
Max: R Min: R

123
 Algorithm binarySearch
binarySearch locates object in List
Returns index of object in List if object exists
Returns negative value if Object does not exist
Calculate insertion point: if the object is to be inserted
into the List, where should it be inserted ?
Make the insertion point sign negative
Subtract 1 from insertion point (Why ?)

124
 1 // Fig. 19.14: BinarySearchTest.java
2
3
Outline
// Using algorithm binarySearch.
import java.util.List;
4 import java.util.Arrays;
5 import java.util.Collections;
6 import java.util.ArrayList;
7
8 public class BinarySearchTest
9 {
10 private static final String colors[] = { "red", "white",
11 "blue", "black", "yellow", "purple", "tan", "pink" };
12 private List< String > list; // ArrayList reference
13
14 // create, sort and output list
15 public BinarySearchTest()
16 {
17 list = new ArrayList< String >( Arrays.asList( colors ) );
18 Collections.sort( list ); // sort the ArrayList Sort List in ascending order
19 System.out.printf( "Sorted ArrayList: %s\n", list );
20 } // end BinarySearchTest constructor
21

125
 22 // search list for various values

Outline
23 private void search()
24 {
25 printSearchResults( colors[ 3 ] ); // first item
26 printSearchResults( colors[ 0 ] ); // middle item
27 printSearchResults( colors[ 7 ] ); // last item
28 printSearchResults( "aqua" ); // below lowest
29 printSearchResults( "gray" ); // does not exist
30 printSearchResults( "teal" ); // does not exist
31 } // end method search
32
33 // perform searches and display search result
34 private void printSearchResults( String key ) Use method binarySearch
35 { of class Collections to
36 int result = 0;
search list for specified key
37
38 System.out.printf( "\nSearching for: %s\n", key );
39 result = Collections.binarySearch( list, key );
40
41 if ( result >= 0 )
42 System.out.printf( "Found at index %d\n", result );
43 else
44 System.out.printf( "Not Found (%d)\n",result );
45 } // end method printSearchResults
46

126
 Outline
47 public static void main( String args[] )
48 {
49 BinarySearchTest binarySearchTest = new BinarySearchTest();
50 binarySearchTest.search();
51 } // end main
52 } // end class BinarySearchTest

Sorted ArrayList: [black, blue, pink, purple, red, tan, white, yellow]

Searching for: black

Found at index 0

Searching for: red

Found at index 4

Searching for: pink

Found at index 2

Searching for: aqua

Not Found (-1)

Searching for: gray

Not Found (-3)

Searching for: teal

Not Found (-7)

127
 Algorithms addAll, frequency and
disjoint
addAll
Insert all elements of an array into a collection
frequency
Calculate the number of times a specific element appear
in the collection
Disjoint
Determine whether two collections have elements in
common

128
 1 // Fig. 19.15: Algorithms2.java

Outline
2 // Using algorithms addAll, frequency and disjoint.
3 import java.util.List;
4 import java.util.Vector;
5 import java.util.Arrays;
6 import java.util.Collections;
7
8 public class Algorithms2
9 {
10 private String[] colors = { "red", "white", "yellow", "blue" };
11 private List< String > list;
12 private Vector< String > vector = new Vector< String >();
13
14 // create List and Vector
15 // and manipulate them with methods from Collections
16 public Algorithms2()
17 {
18 // initialize list and vector
19 list = Arrays.asList( colors );
20 vector.add( "black" );
21 vector.add( "red" );
22 vector.add( "green" );
23
24 System.out.println( "Before addAll, vector contains: " );
25

129
26
27 Outline
// display elements in vector
for ( String s : vector )
28 System.out.printf( "%s ", s ); Invoke method addAll to
29 add elements in array
30 // add elements in colors to list colors to vector
31 Collections.addAll( vector, colors );
32
33 System.out.println( "\n\nAfter addAll, vector contains: " );
34
35 // display elements in vector
36 for ( String s : vector )
37 System.out.printf( "%s ", s );
38
39 // get frequency of "red"
40 int frequency = Collections.frequency( vector, "red" );
41 System.out.printf(
42 "\n\nFrequency of red in vector: %d\n", frequency );
43
Get the frequency of String
“red” in Collection vector
using method frequency

130
 44 // check whether list and vector have elements in common
45
46
Outline
boolean disjoint = Collections.disjoint( list, vector );

47 System.out.printf( "\nlist and vector %s elements in common\n",

Invoke method disjoint to test
48 ( disjoint ? "do not have" : "have" ) ); whether Collections list and
49 } // end Algorithms2 constructor vector have elements in common
50
51 public static void main( String args[] )
52 {
53 new Algorithms2();
54 } // end main
55 } // end class Algorithms2

Before addAll, vector contains:

black red green

After addAll, vector contains:

black red green red white yellow blue

Frequency of red in vector: 2

list and vector have elements in common

131
 Synchronized Collections
Built-in collections are unsynchronized
Concurrent access to a Collection can cause errors
Java provides synchronization wrappers to avoid this
 Via set of public static methods

public static method headers

< T > Collection< T > synchronizedCollection( Collection< T > c )
< T > List< T > synchronizedList( List< T > aList )
< T > Set< T > synchronizedSet( Set< T > s )
< T > SortedSet< T > synchronizedSortedSet( SortedSet< T > s )
< K, V > Map< K, V > synchronizedMap( Map< K, V > m )
< K, V > SortedMap< K, V > synchronizedSortedMap( SortedMap< K, V > m )

132
 Unmodifiable Collections
Unmodifiable wrapper
Converting collections to unmodifiable collections
Throw UnsorrtedOperationException if
attempts are made to modify the collection

public static method headers

< T > Collection< T > unmodifiableCollection( Collection< T > c )
< T > List< T > unmodifiableList( List< T > aList )
< T > Set< T > unmodifiableSet( Set< T > s )
< T > SortedSet< T > unmodifiableSortedSet( SortedSet< T > s )
< K, V > Map< K, V > unmodifiableMap( Map< K, V > m )
< K, V > SortedMap< K, V > unmodifiableSortedMap( SortedMap< K, V > m )

133