CS计算机代考程序代写 compiler Java algorithm GenericsCollectionsIterator

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 integerBox = new Box();

OR
Box integerBox = new 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 p1 = new OrderedPair(“Even”, 8);
Pair p2 = new OrderedPair(“hello”, “world”);
… …
OrderedPair p1 = new OrderedPair<>(“Even”, 8);
OrderedPair p2 = new OrderedPair<>(“hello”, “world”);
… …
OrderedPair> p = new OrderedPair<>(“primes”, new Box(…));

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 p1 = new Pair<>(1, “apple”);
Pair p2 = new Pair<>(2, “pear”);
boolean same = Util.compare(p1, p2);

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 p1 = new Pair<>(1, “apple”);
Pair p2 = new Pair<>(2, “pear”);
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 n ) { /* … */ }

v What type of argument does it accept?

v Are you allowed to pass in
Box or Box ?

v The answer is “no”, because Box and
Box are not subtypes of 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 implements List, and List extends Collection.
v So ArrayList is a subtype of List,

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,
List, and so on

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.

v The term List is more restrictive than List.

COMP2511: Generics, Collections, Iterator 15

Wildcards and Subtyping

v Although Integer is a subtype of Number,
List is not a subtype of List and,
these two types are not related.

v The common parent of
List and List is
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 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