CS计算机代考程序代写 prolog data structure Java algorithm ITI 1121. Introduction to Computing II – subtitle

ITI 1121. Introduction to Computing II – subtitle

ITI 1121. Introduction to Computing II
Interface: abstract data types (ADT) and their implementations

by

Marcel Turcotte

Version January 19, 2020

Preamble

Preamble

Overview

Overview

Interface: abstract data types (ADT) and their implementations

Class declarations are one of Java’s mechanisms to create new data types. In this case, we
say that it is a concrete data type. In this module, we discuss the concept of interface
that will allow the definition of abstract types of data.

General objective:
This week, you will be able to declare an abstract data type through an interface.

1 49

Preamble

Learning objectives

Learning objectives

Explain in your own words the concept of interface.
Declare an interface
Implement an interface

Lectures:
Pages 2–7 of E. Koffman and P. Wolfgang.

2 49

Preamble

Plan

Plan

1 Preamble

2 Summary

3 Interface

4 Comparable

5 Call-back function

6 Prologue

3 49

Summary

Defining a new type

A class declaration defines a new data type

4 49

Defining a new type

The following declaration defines a new type

pub l i c c l a s s Po in t {

}

Placed in a file named Point.java, this class declaration can be compiled.

> javac Point.java

5 49

Defining a new type

We can declare a variable of type Point.

pub l i c c l a s s Test {
pub l i c s t a t i c vo id main ( S t r i n g [ ] a r g s ) {

Po in t p ;
}

}

6 49

Defining a new type

We can create an object of the class Point.

pub l i c c l a s s Test {
pub l i c s t a t i c vo id main ( S t r i n g [ ] a r g s ) {

Po in t p ;
p = new Po in t ( ) ;

}
}

It can be done because there exists a default constructor .
Of course, these objects have no variables or methods, for now.

7 49

pub l i c c l a s s Po in t {
p r i v a t e double x ;
p r i v a t e double y ;
pub l i c Po in t ( double x I n i t , double y I n i t ) {

x = x I n i t ;
y = y I n i t ;

}
pub l i c double getX ( ) {

re tu rn x ;
}
// . . .
pub l i c vo id t r a n s l a t e ( double de l taX , double de l t aY ) {

x = x + de l taX ;
y = y + de l taY ;

}
}

The course Web site has a complete implementation.

Using this new type type

pub l i c c l a s s Test {
pub l i c s t a t i c vo id main ( S t r i n g [ ] a r g s ) {

Po in t p1 , p2 ;

p1 = new Po in t (10 , 2 0 ) ;
p2 = new Po in t (522 , 4 3 ) ;

i f ( p1 . getX ( ) < p2 . getX ( ) ) { p1 . t r a n s l a t e ( p2 . getX ( ) − p1 . getX ( ) , 0 . 0 ) ; } i f ( p1 . getY ( ) < p2 . getY ( ) ) { p1 . t r a n s l a t e ( 0 . 0 , p2 . getY ( ) − p1 . getY ( ) ) ; } } } 9 49 Definition: concrete data type A class declaration defines a concrete data type. We say concrete because the data representation and the methods are present. 10 49 Interface Introduction Let’s revisit the two implementations of the class Pair introduced in the last lecture. 11 49 pub l i c c l a s s Pa i rVa r { p r i v a t e i n t f i r s t ; p r i v a t e i n t second ; pub l i c Pa i rVa r ( i n t f i r s t I n i t , i n t s e c o n d I n i t ) { f i r s t = f i r s t I n i t ; second = s e c o n d I n i t ; } pub l i c i n t g e t F i r s t ( ) { re tu rn f i r s t ; } pub l i c i n t getSecond ( ) { re tu rn second ; } pub l i c vo id s e t F i r s t ( i n t v a l u e ) { f i r s t = v a l u e ; } pub l i c vo id se tSecond ( i n t v a l u e ) { second = v a l u e ; } } pub l i c c l a s s P a i r A r r a y { p r i v a t e i n t [ ] e l ems ; pub l i c P a i r A r r a y ( i n t f i r s t , i n t second ) { e lems = new i n t [ 2 ] ; e l ems [ 0 ] = f i r s t ; e l ems [ 1 ] = second ; } pub l i c i n t g e t F i r s t ( ) { re tu rn e lems [ 0 ] ; } pub l i c i n t getSecond ( ) { re tu rn e lems [ 1 ] ; } pub l i c vo id s e t F i r s t ( i n t v a l u e ) { e lems [ 0 ] = v a l u e ; } pub l i c vo id se tSecond ( i n t v a l u e ) { e lems [1]= v a l u e ; } } Introduction PairVar and PairArray are two implementations of the same concept, a pair of integer values. Java provides us with a mechanism to formalize this idea. 14 49 Interface Pair pub l i c i n t e r f a c e P a i r { pub l i c abs t rac t i n t g e t F i r s t ( ) ; pub l i c abs t rac t i n t getSecond ( ) ; pub l i c abs t rac t vo id s e t F i r s t ( i n t f i r s t ) ; pub l i c abs t rac t vo id se tSecond ( i n t f i r s t ) ; } 15 49 Interface Pair The declaration of an interface is similar to that of a class. It starts with the keyword interface, rather than class, followed by the name of an identifier (the name of the interface), followed by the body of the interface. pub l i c i n t e r f a c e P a i r { pub l i c abs t rac t i n t g e t F i r s t ( ) ; pub l i c abs t rac t i n t getSecond ( ) ; pub l i c abs t rac t vo id s e t F i r s t ( i n t f i r s t ) ; pub l i c abs t rac t vo id se tSecond ( i n t f i r s t ) ; } This declaration is saved into a file that has the same name as the interface, with extension .java. When compiled, it produces a .class file. 16 49 Interface An interface contains: Constants; Abstract methods. 17 49 Interface An abstract method has no implementation. Since all the methods of the interface must be abstract and public, public abstract is implied and can be omitted. pub l i c i n t e r f a c e P a i r { i n t g e t F i r s t ( ) ; i n t getSecond ( ) ; vo id s e t F i r s t ( i n t f i r s t ) ; vo id se tSecond ( i n t f i r s t ) ; } 18 49 The interface is a contract. A list of methods to be implemented. Abstract data type We have just defined an abstract data type (ADT). We specified the operations, but not the implementation! pub l i c i n t e r f a c e P a i r { i n t g e t F i r s t ( ) ; i n t getSecond ( ) ; vo id s e t F i r s t ( i n t f i r s t ) ; vo id se tSecond ( i n t f i r s t ) ; } 20 49 Abstract data type What’s the point? We can declare a variable of type Pair! P a i r p ; The operations p.getFirst(), p.getSecond(), p.setFirst(10), and p.setSecond(55) are all valid, from the point of view of the type system. 1 21 49 Abstract data type But what do you put in the reference variable p? P a i r p ; 22 49 Java: implements Here is a new keyword, implements. We say that the class PairVar implements the interface Pair. pub l i c c l a s s Pa i rVa r implements P a i r { p r i v a t e i n t f i r s t ; p r i v a t e i n t second ; pub l i c Pa i rVa r ( i n t f i r s t I n i t , i n t s e c o n d I n i t ) { f i r s t = f i r s t I n i t ; second = s e c o n d I n i t ; } pub l i c i n t g e t F i r s t ( ) { re tu rn f i r s t ; } // . . . } 23 49 pub l i c c l a s s Pa i rVa r implements P a i r { p r i v a t e i n t f i r s t ; p r i v a t e i n t second ; pub l i c Pa i rVa r ( i n t f i r s t I n i t , i n t s e c o n d I n i t ) { f i r s t = f i r s t I n i t ; second = s e c o n d I n i t ; } pub l i c i n t g e t F i r s t ( ) { re tu rn f i r s t ; } pub l i c i n t getSecond ( ) { re tu rn second ; } pub l i c vo id s e t F i r s t ( i n t v a l u e ) { f i r s t = v a l u e ; } pub l i c vo id se tSecond ( i n t v a l u e ) { second = v a l u e ; } } pub l i c c l a s s P a i r A r r a y implements P a i r { p r i v a t e i n t [ ] e l ems ; pub l i c P a i r A r r a y ( i n t f i r s t , i n t second ) { e lems = new i n t [ 2 ] ; e l ems [ 0 ] = f i r s t ; e l ems [ 1 ] = second ; } pub l i c i n t g e t F i r s t ( ) { re tu rn e lems [ 0 ] ; } pub l i c i n t getSecond ( ) { re tu rn e lems [ 1 ] ; } pub l i c vo id s e t F i r s t ( i n t v a l u e ) { e lems [ 0 ] = v a l u e ; } pub l i c vo id se tSecond ( i n t v a l u e ) { e lems [1]= v a l u e ; } } UML: Pair PairVar PairArray + getFirst(): int + getSecond(): int + setFirst(value: int) + setSecond(value: int) Pair 26 49 What’s the point? PairVar PairArray + getFirst(): int + getSecond(): int + setFirst(value: int) + setSecond(value: int) Pair P a i r p ; p = new Pa i rVa r (10 , 2 0 ) ; p = new P a i r A r r a y (10 , 2 0 ) ; new Pair() does not make any sense. 27 49 Comparable Complete example We would like to write a sort method. Compare how you would write a sort method for objects of the class Person and a sort method for objects of the class Time. What are the resemblances and differences? 28 49 Sort algorithm The sort algorithm is the same, regardless of the elements of the array. What changes is the way you compare the elements! 29 49 Comparable Let’s define the interface Comparable: pub l i c i n t e r f a c e Comparable { pub l i c i n t compareTo ( Comparable o t h e r ) ; } An object is “Comparable” if it has a compareTo method! 30 49 UML: Comparable + selectionSort(elms: Comparable[]) SortAlgorithms Person Time + compareTo(other: Comparable): int Comparable 31 49 SortAlgorithms.selectionSort pub l i c c l a s s S o r t A l g o r i t h m s { pub l i c s t a t i c vo id s e l e c t i o n S o r t ( Comparable [ ] a ) { f o r ( i n t i = 0 ; i < a . l e n g t h ; i++ ) { i n t min = i ; // f i n d the s m a l l e s t e l ement i n the un so r t ed // p o r t i o n o f the a r r a y f o r ( i n t j = i +1; j < a . l e n g t h ; j++ ) i f ( a [ j ] . compareTo ( a [ min ] ) < 0 ) min = j ; // exchange tha t e l ement and tha t o f i Comparable tmp = a [ min ] ; a [ min ] = a [ i ] ; a [ i ] = tmp ; } } } 32 49 Time pub l i c c l a s s Time implements Comparable { p r i v a t e i n t t ime InSeconds ; pub l i c i n t compareTo ( Comparable ob j ) { Time o t h e r = ( Time ) ob j ; i n t r e s u l t ; i f ( t i m e I n s e c o n d s < o t h e r . t ime InSeconds ) { r e s u l t = −1; } e l s e i f ( t ime InSeconds == o t h e r . t ime InSeconds ) { r e s u l t = 0 ; } e l s e { r e s u l t = 1 ; } re tu rn r e s u l t ; } } 33 49 Person pub l i c c l a s s Person implements Comparable { p r i v a t e i n t i d ; p r i v a t e S t r i n g name ; pub l i c i n t compareTo ( Comparable ob j ) { Person o t h e r = ( Person ) ob j ; i n t r e s u l t ; i f ( i d < o t h e r . i d ) { r e s u l t = −1; } e l s e i f ( i d == o t h e r . i d ) { r e s u l t = 0 ; } e l s e { r e s u l t = 1 ; } re tu rn r e s u l t ; } } 34 49 Person (2) pub l i c c l a s s Person implements Comparable { p r i v a t e i n t i d ; p r i v a t e S t r i n g name ; pub l i c i n t compareTo ( Comparable ob j ) { Person o t h e r = ( Person ) ob j ; re tu rn name . compareTo ( o t h e r . name ) ; } } 35 49 UML: Comparable + selectionSort(elms: Comparable[]) SortAlgorithms Person Time + compareTo(other: Comparable): int Comparable 36 49 Call-back function Problem: uoAlert Problem: The University of Ottawa wishes to replace the the computer system it uses for the management of warning messages. The system must transmit the alert messages to different clients, including a mobile phone application and a Web application. 37 49 uoAlert: AlertListener As a software developer, you have the idea of creating the interface AlertListener. Any client who wishes to receive alert messages must implement the interface AlertListener. The server has a method register whose parameter is of type AlertListener. Any customer who wishes to receive alert messages must register with the server. pub l i c i n t e r f a c e A l e r t L i s t e n e r { vo id p r o c e s s A l e r t ( S t r i n g message ) ; } 38 49 uoAlert: PhoneApp The application PhoneApp implements the interface AlertListener. pub l i c c l a s s PhoneApp implements A l e r t L i s t e n e r { pub l i c vo id p r o c e s s A l e r t ( S t r i n g message ) { System . out . p r i n t l n ( "PhoneApp : " + message ) ; } // The o t h e r methods o f PhoneApp would be he r e ! } 39 49 uoAlert: WebApp The application WebApp implements the interface AlertListener. pub l i c c l a s s WebApp implements A l e r t L i s t e n e r { pub l i c vo id p r o c e s s A l e r t ( S t r i n g message ) { System . out . p r i n t l n ( "WebApp : " + message ) ; } // The o t h e r methods o f WebApp would be he r e ! } 40 49 uoAlert: AlertServer pub l i c c l a s s A l e r t S e r v e r { p r i v a t e A l e r t L i s t e n e r [ ] c l i e n t s ; p r i v a t e i n t numberOfC l i en t s ; pub l i c A l e r t S e r v e r ( i n t c a p a c i t y ) { c l i e n t s = new A l e r t L i s t e n e r [ c a p a c i t y ] ; numberOfC l i en t s = 0 ; } pub l i c vo id r e g i s t e r ( A l e r t L i s t e n e r c l i e n t ) { c l i e n t s [ numberOfC l i en t s ] = c l i e n t ; numberOfC l i en t s++; } pub l i c vo id b r o a d c a s t ( S t r i n g message ) { f o r ( i n t i =0; i java Run
PhoneApp: Test!
WebApp: Test!

43 49

uoAlert: UML

+ processAlert(message: String)

AlertListener
« interface »

PhoneApp WebApp

+ register(AlertListener: client)
+ broadcast(String: message)

AlertServer 1 n

44 49

Call-back

The method processAlert is a call-back function.
A client registers with the server (service).

Only the clients having a method called processAlert can register with the server.
Later, when an alert is generated, the server informs the clients.
(calls their method processAlert)

45 49

Prologue

Summary

An interface is a formalism to create an abstract data type.
The declaration of an interface is similar to that of a class.

However, an interface contains only abstract methods.
The keyword implements is used to indicate the fact that a class implements all the
methods of a give interface.

46 49

Next module

Inheritance

47 49

References I

E. B. Koffman and Wolfgang P. A. T.
Data Structures: Abstraction and Design Using Java.
John Wiley & Sons, 3e edition, 2016.

48 49

Marcel Turcotte
Marcel.

School of Electrical Engineering and Computer Science (EECS)
University of Ottawa

49 / 49

Marcel.

Preamble
Overview
Learning objectives
Plan

Summary
Interface
Comparable
Call-back function
Prologue