GenericsCollectionsIterator
COMP2511
Generics and Collections in Java
Iterator Pattern
Prepared by
Dr. Ashesh Mahidadia
Generics in Java
These lecture notes use material from the website at https://docs.oracle.com/javase/tutorial/java/generics/index.html
2COMP2511: Generics, Collections, Iterator
Generics in Java: Java Tutorial
v Good introduction at the following web page, Oracle’s official Java Tutorial,
you must read all the relevant pages!
https://docs.oracle.com/javase/tutorial/java/generics/index.html
v The following lecture slides cover only some parts of the above tutorial,
however, you should read all the relevant sections (pages) in the above tutorial.
COMP2511: Generics, Collections, Iterator 3
Generics in Java
Generics enable types (classes and interfaces) to be parameters when defining:
• classes,
• interfaces and
• methods.
Benefits
v Removes casting and offers stronger type checks at compile time.
v Allows implementations of generic algorithms, that work on collections of different types, can
be customized, and are type safe.
v Adds stability to your code by making more of your bugs detectable at compile time.
COMP2511: Generics, Collections, Iterator 4
Without Generics With Generics
Generic Types
v A generic type is a generic class or interface that is parameterized over types.
v A generic class is defined with the following format:
class name< T1, T2, ..., Tn > { /* … */ }
v The most commonly used type parameter names are:
v E – Element (used extensively by the Java Collections Framework)
v K – Key
v N – Number
v T – Type
v V – Value
v S,U,V etc. – 2nd, 3rd, 4th types
v For example,
Box
OR
Box
COMP2511: Generics, Collections, Iterator 5
Multiple Type Parameters
v A generic class can have multiple type
parameters.
v For example, the generic OrderedPair class,
which implements the generic Pair interface
COMP2511: Generics, Collections, Iterator 6
v Usage examples,
Pair
Pair
… …
OrderedPair
OrderedPair
… …
OrderedPair
Generic Methods
Generic methods are methods that introduce their own type parameters.
COMP2511: Generics, Collections, Iterator 7
The complete syntax for invoking this method would be:
Pair
Pair
boolean same = Util.
The type has been explicitly provided, as shown above.
Generally, this can be left out and the compiler will infer the type that is needed:
Pair
Pair
boolean same = Util.compare(p1, p2);
Bounded Type Parameters
v There may be times when you want to restrict the types that can be used as type
arguments in a parameterized type.
v For example, a method that operates on numbers might only want to accept instances
of Number or its subclasses.
COMP2511: Generics, Collections, Iterator 8
Multiple Bounds
v A type parameter can have multiple bounds:
< T extends B1 & B2 & B3 >
v A type variable with multiple bounds is a subtype of all the types listed in the bound.
v Note that B1, B2, B3, etc. in the above refer to interfaces or a class. There can be at
most one class (single inheritance), and the rest (or all) will be interfaces.
v If one of the bounds is a class, it must be specified first.
COMP2511: Generics, Collections, Iterator 9
Generic Methods and Bounded Type Parameters
COMP2511: Generics, Collections, Iterator 10
X – invalid
Valid
Generics, Inheritance, and Subtypes
v Consider the following method:
public void boxTest( Box
v What type of argument does it accept?
v Are you allowed to pass in
Box
v The answer is “no”, because Box
Box
v This is a common misunderstanding when it comes to
programming with generics.
COMP2511: Generics, Collections, Iterator 11
Generic Classes and Subtyping
v You can subtype a generic class or interface by extending or
implementing it.
v The relationship between the type parameters of one class or interface
and the type parameters of another are determined by the extends and
implements clauses.
v ArrayList
v So ArrayList
which is a subtype of Collection
v So long as you do not vary the type argument,
the subtyping relationship is preserved between the types.
COMP2511: Generics, Collections, Iterator
12
Wildcards: Upper bounded
v In generic code, the question mark (?), called the wildcard, represents an unknown
type.
v The wildcard can be used in a variety of situations: as the type of a parameter, field, or
local variable; sometimes as a return type.
v The upper bounded wildcard, < ? extends Foo >, where Foo is any type, matches
Foo and any subtype of Foo .
v You can specify an upper bound for a wildcard, or you can specify a lower bound, but
you cannot specify both.
COMP2511: Generics, Collections, Iterator 13
Wildcards: Unbounded
v The unbounded wildcard type is specified using the wildcard character (?),
for example, List< ? >. This is called a list of unknown type.
COMP2511: Generics, Collections, Iterator 14
It prints only a list of Object instances;
it cannot print List
List
To write a generic printList
method, use List>
Wildcards: Lower Bounded
v An upper bounded wildcard restricts the unknown type to be a specific type or a
subtype of that type and is represented using the extends keyword.
v A lower bounded wildcard is expressed using the wildcard character (‘?’), following by
the super keyword, followed by its lower bound: < ? super A >.
v To write the method that works on lists of Integer and the super types of Integer, such
as Integer, Number, and Object, you would specify List Super Integer>.
v The term List
COMP2511: Generics, Collections, Iterator 15
Wildcards and Subtyping
v Although Integer is a subtype of Number,
List
these two types are not related.
v The common parent of
List
List>.
COMP2511: Generics, Collections, Iterator 16
Collections in Java
COMP2511: Generics, Collections, Iterator 17
Collections in Java
A collections framework is a unified architecture for representing and manipulating
collections. A collection is simply an object that groups multiple elements into a single unit.
All collections frameworks contain the following:
v Interfaces: allows collections to be manipulated independently of the details of their
representation.
v Implementations: concrete implementations of the collection interfaces.
v Algorithms: the methods that perform useful computations, such as searching and
sorting, on objects that implement collection interfaces.
• The algorithms are said to be polymorphic: that is, the same method can be used
on many different implementations of the appropriate collection interface.
COMP2511: Generics, Collections, Iterator 18
Core Collection Interfaces:
v The core collection interfaces encapsulate different types of collections
v The interfaces allow collections to be manipulated independently of the details of their
representation.
COMP2511: Generics, Collections, Iterator 19
The Collection Interface
v A Collection represents a group of objects known as its elements.
v The Collection interface is used to pass around collections of objects where maximum
generality is desired.
v For example, by convention all general-purpose collection implementations have a
constructor that takes a Collection argument.
v The Collection interface contains methods that perform basic operations, such as
• int size(),
• boolean isEmpty(),
• boolean contains(Object element),
• boolean add(E element),
• boolean remove(Object element),
• Iterator
• … …many more …
More at : https://docs.oracle.com/javase/tutorial/collections/interfaces/collection.html
COMP2511: Generics, Collections, Iterator 20
Collection Implementations
v The general purpose implementations are summarized in the following table:
COMP2511: Generics, Collections, Iterator 21
Interface Hash Table Resizable Array Balanced Tree Linked List Hash Table + Linked List
Set HashSet TreeSet LinkedHashSet
List ArrayList LinkedList
Deque ArrayDeque LinkedList
Map HashMap TreeMap LinkedHashMap
Implemented Classes in the Java Collection,
Read their APIs.
v Overview of the Collections Framework at the following page:
https://docs.oracle.com/javase/8/docs/technotes/guides/collections/overview.html
Wrappers for the Collection classes
• https://docs.oracle.com/javase/tutorial/collections/implementations/
wrapper.html
COMP2511: Generics, Collections, Iterator 22
Demo: Collections Framework
Demo …
COMP2511: Generics, Collections, Iterator 23
Iterator Pattern
COMP2511: Generics, Collections, Iterator 24
Iterator Pattern: Intent and Motivation
v The intent of the Iterator design pattern is to:
“Provide a way to access the elements of an aggregate object sequentially without
exposing its underlying representation.” [GoF]
v Exposing representation details of an aggregate breaks its encapsulation.
v Problem to address:
How can the elements of an aggregate object be accessed and traversed without
exposing its underlying representation?
v “But you probably don’t want to bloat the List [Aggregate] interface with operations for
different traversals, even if you could anticipate the ones you will need.” [GoF, p257]
COMP2511: Generics, Collections, Iterator 25
Iterator Pattern: Possible Solution
v Encapsulate the access and traversal of an
aggregate in a separate Iterator object.
v Clients request an Iterator object from an
aggregate (say by calling createIterator()) and use
it to access and traverse the aggregate.
v Define an interface for accessing and traversing the
elements of an aggregate object
(next(), hasNext()).
v Define classes (Iterator1,…) that implement the
Iterator interface.
COMP2511: Generics, Collections, Iterator 26
Iterator Pattern: Possible Solution
v An iterator is usually implemented as inner class of an aggregate class. This enables the
iterator to access the internal data structures of the aggregate.
v New access and traversal operations can be added by defining new iterators.
For example, traversing back-to-front: previous(), hasPrevious().
v An aggregate provides an interface for creating an iterator (createIterator()).
v Clients can use different Iterator objects to access and traverse an aggregate object in
different ways.
v Multiple traversals can be in progress on the same aggregate object (simultaneous
traversals). However, need to consider concurrent usage issues!
COMP2511: Generics, Collections, Iterator 27
Iterator Pattern: Java Collection Framework
The Java Collections Framework provides,
v a general purpose iterator
next(), hasNext(), remove()
v an extended listIterator
next(), hasNext(), previous(), hasPrevious(), remove(), ….
COMP2511: Generics, Collections, Iterator 28
Example:
Custom Iterator
COMP2511: Generics, Collections, Iterator 29
Using or forwarding an iteratormethod from
a collection (i.e. Hashtable, ArrayList, etc.)
Implement Iterator interface, and provide the
required methods (and more if required).
Demo: Iterator Pattern
Demo …
COMP2511: Generics, Collections, Iterator 30
End
COMP2511: Generics, Collections, Iterator 31