Transcript 05.ADTs_mod

5
Abstract Data Types
• Data types: values, operations, and data representation.
• Abstract data type: values and operations only.
• Requirements, contract, implementation(s).
• (Design of abstract data types.)
• String abstract data types.
• Abstract data types in the Java class library.
© 2001, D.A. Watt and D.F. Brown
5-1
Data types
• We classify all data into data types, such as:
 Booleans
 integers
 objects of various classes.
• Each data type is characterized by:
 a set of values
 a data representation
(which is common to all these values)
 a set of operations
(which can be applied uniformly to all these values).
5-2
Java data types
Type
Values
Data
representation
Operations
boolean
false, true
1 byte
|| && !
char
Unicode characters
2 bytes
(as for int)
int
negative, zero, positive 32-bit twoswhole numbers
complement
float
negative, zero, positive IEEE 32-bit
floating-point numbers floating-point
String
sequences of characters array of characters + length
charAt etc.
+ - * / %
< > == etc.
5-3
Introducing new data type
• To introduce a new data type, we must define its values,
data representation, and operations.
• In Java, use a class declaration:
 The class’s instance variables determine the values and data
representation.
 The class’s constructors and methods are the operations.
• Each object of the class:
 has those instance variables
 is created by one of those constructors
 may be inspected and/or updated by any of those methods.
5-4
Example 1 (2)
• Possible application code:
Person p1 =
new Person("Curie", "Pierre", 1859);
Person p2 =
new Person("Sklodowska", "Marie", 1867);
…
p2.changeName(p1.surname);
5-5
Example 2: Date data type (1)
• Class declaration:
public class Date {
// Each Date value is a past, present, or future date.
// This date is represented by a year number y, a month number
// m (1…12), and a day-in-month number d (1…31):
public int y, m, d;
public Date (int y, int m, int d) {
// Construct a date with year y, month m, and day-in-month d.
if (m < 1 || … ) throw …;
this.y = y; this.m = m; this.d = d;
}
5-6
Example 2 (2)
• Class declaration (continued):
public void advance (int n) {
// Advance this date by n days (where n ≥ 0).
int y = this.y, m = this.m,
d = this.d + n;
for (;;) {
int last = …; // no. of days in m, y
if (d <= last) break;
d -= last;
if (m < 12) m++;
else { m = 1; y++; }
}
this.y = y; this.m = m; this.d = d;
}
}
5-7
Example 2 (3)
• Possible application code:
Date today = new Date(2001, 2, 14);
today.advance(16);
System.out.println(today.y + '-' + today.m
+ '-' + today.d);
This should print “2001-3-2”.
5-8
Example 2 (4)
• Problem: This data representation admits improper values
(e.g., m = 0; or m = 2 and d = 30).
• Constructors and methods can (should) be coded to avoid
improper values. E.g.:
Date today = new Date(2001, 2, 30);
will throw an exception.
• But what if the data representation is accessed directly?
Date today = new Date(2001, 2, 14);
today.d += 16;
5-9
Example 3: Date data type again (1)
• A different data representation is possible:
public class Date {
// Each Date value is a past, present, or future date.
// This date is represented by a day-in-epoch number d
// (where 0 represents 1 January 2000):
public int d;
public Date (int y, int m, int d) { … }
public void advance (int n) { … }
}
• This makes advance faster, but Date() slower.
5-10
Example 3 (2)
• Recall existing application code:
Date today = new Date(2001, 2, 14);
today.advance(16);
System.out.println(today.y + '-' + today.m
+ '-' + today.d);
yields wrong value
fails to compile
fails to compile
5-11
Public vs. private data representation
• If the data representation is public:
– Application code might make improper values.
– Existing application code might be invalidated by change of
representation.
• If the data representation is private:
+ Application code cannot make improper values.
+ Existing application code cannot be invalidated by change of
representation.
5-12
Abstract data types
• An abstract data type (ADT) is characterized by:
 a set of values
 a set of operations.
It is not characterized by its data representation.
• The data representation is private, so application code
cannot access it. (Only the operations can.)
• The data representation is changeable, with no effect on
application code. (Only the operations must be recoded.)
5-13
ADT specification (1)
• Each ADT should have a contract that:
 specifies the set of values of the ADT
 specifies each operation of the ADT
(i.e., the operation’s name, parameter type(s), result type, and
observable behavior).
• The contract does not specify the data representation, nor
the algorithms used to implement the operations.
• The observable behavior of an operation is its effect as
‘observed’ by the application code.
 Example of observable behavior: search an array.
 Examples of algorithms with that behavior: linear search, binary
search.
5-14
ADT specification (2)
• The ADT programmer undertakes to provide an
implementation of the ADT that respects the contract.
• The application programmer undertakes to process
values of the ADT using only the operations specified in
the contract.
• Separation of concerns:
 The ADT programmer is not concerned with what applications the
ADT is used for.
 The application programmer is not concerned with how the ADT is
implemented.
• Separation of concerns is essential for designing and
implementing large systems.
5-15
Example 4: contract for Date ADT (1)
•
Assumed application requirements:
1) *** The values must be all past, present, and future dates.
2) *** It must be possible to construct a date from year number y,
month number m, and day-in-month number d.
3) It must be possible to compare dates.
4) It must be possible to render a date in ISO format “y-m-d”.
5) It must be possible to advance a date by n days.
5-16
En Java - généralité
• Spécifier un contrat comme une interface
 Méthodes exigées
• Déclarer une clase conforme à cette interface
 Choix des structures de données et définition des attributs
 Implantation de toutes les méthodes exigées
• Utilisation de la classe dans une application
5-17
Spécifier un contrat en Java
• Interface:
 Constante
 Méthode abstraite
• Mécanisme idéal en Java pour définir un ADT
• (Un autre mécanisme possible est la classe abstraite)
• Note: les spécifications présentées ici sont modifiées par
rapport au livre (class -> interface)
5-18
Example 4 (2)
• Possible contract, expressed as an interface:
public interface DateADT {
// Each Date value is a past, present, or future date.
public int compareTo (Date that);
// Return –1 if this date is earlier than that,
// or 0 if this date is equal to that,
// or +1 if this date is later than that.
public String toString ();
// Return this date rendered in ISO format.
public void advance (int n);
// Advance this date by n days (where n ≥ 0).
}
5-19
Définir une classe conforme à une
interface
• Utiliser ‘implements’
• Exemple
class <nom_classe> implements <interface> {
<attributs>
<constructeurs>
<implantation de toutes les méthodes
exigées dans l’interface>
<autres méthodes>
}
5-20
Exemple 4
class Date implements DateADT {
private … // les attributs de la classe
public Date(int y, int m, int d) { ... }
//constructeur
public int compareTo (Date that) { ... }
public String toString () {...}
public void advance (int n) {...}
...
}
5-21
Example 4 (4)
• Possible application code:
Date today = …;
Date easter = new Date(2001, 4, 15);
today.advance(16);
if (today.compareTo(easter) < 0)
System.out.println(today.toString());
• Impossible application code:
today.d += 16;
System.out.println(today.y + '-' + today.m
+ '-' + today.d);
fails to compile
fails to compile
5-22
ADT implementation (in a class)
• An implementation of an ADT entails:
 choosing a data representation
 choosing an algorithm for each operation.
• The data representation must be private.
• The data representation must cover all possible values.
• The algorithms must be consistent with the data
representation.
5-23
Example 5: first implementation
of Date ADT (1)
• Class declaration:
public class Date implements DateADT {
// Each Date value is a past, present, or future date.
// This date is represented by a year number y, a month number
// m, and a day-in-month number d:
private int y, m, d;
public Date (int y, int m, int d) {
// Construct a date with year y, month m, and day-in-month d.
this.y = y; this.m = m; this.d = d;
}
5-24
Example 5 (2)
• Class declaration (continued) – implementation of the
required methods:
public int compareTo (Date that) {
// Return –1 if this date is earlier than that,
// or 0 if this date is equal to that,
// or +1 if this date is later than that.
return (this.y < that.y ? -1 :
this.y > that.y ? +1 :
this.m < that.m ? -1 :
this.m > that.m ? +1 :
this.d < that.d ? -1 :
this.d > that.d ? +1 : 0);
}
5-25
Example 5 (3)
• Class declaration (continued):
public String toString () {
// Return this date rendered in ISO format.
return (this.y + '-' + this.m + '-'
+ this.d);
}
public void advance (int n) {
// Advance this date by n days (where n ≥ 0).
…
}
complicated
}
5-26
Example 6: second implementation
of Date ADT (1)
• Class declaration:
public class Date implements DateADT{
// Each Date value is a past, present, or future date.
// This date is represented by a day-in-epoch number d
// (where 0 represents 1 January 2000):
private int d;
public Date (int y, int m, int d) {
// Construct a date with year y, month m, and day-in-month d.
…;
complicated
this.d = …;
}
5-27
Example 6 (2)
• Class declaration (continued):
public int compareTo (Date that) {
// Return –1 if this date is earlier than that,
// or 0 if this date is equal to that,
// or +1 if this date is later than that.
return (this.d < that.d ? -1 :
this.d > that.d ? +1 : 0);
}
5-28
Example 6 (3)
• Class declaration (continued):
public String toString () {
// Return this date rendered in ISO format.
int y, m, d;
…;
return (y + '-' + m + '-' + d);
}
complicated
public void advance (int n) {
// Advance this date by n days (where n ≥ 0).
this.d += n;
}
}
5-29
ADT design (1)
• A constructor is an operation that creates a value of the
ADT (dans une classe qui implante cet ADT)
• An accessor is an operation that uses a value of the ADT
to compute a value of some other type.
• A transformer is an operation that computes a new value
of the same ADT.
• A well-designed ADT provides at least one constructor, at
least one accessor, and at least one transformer. The
constructors and transformers together can generate all
values of the ADT.
5-30
ADT design II (2)
• A transformer is:
 mutative if it overwrites the old value with the new value
 applicative if it returns the new value, without overwriting the old
value.
• The values of an ADT are:
 mutable if the ADT provides at least one mutative transformer
 immutable if the ADT provides no mutative transformer.
• Ces caractéristiques déterminent le choix d’une structure
de données.
5-31
Example 8: design of Date ADT (1)
• Recall the Date contract of Example 4:
public interface DateADT {
// private …;
// public Date (int y, int m, int d); constructor
accessor
public int compareTo (Date that);
public String toString ();
accessor
public void advance (int n);
mutative
}
transformer
5-32
Example 8 (2)
• Consider another possible Date contract:
public inerface DateADT2 {
// private …;
// public Date (int y, int m, int d); constructor
accessor
public int compareTo (Date that);
public String toString ();
accessor
public Date plus (int n);
applicative
}
transformer
5-33
Strings
• A string is a sequence of characters.
• The characters have consecutive indices.
• A substring of a string is a subsequence of its characters.
• The length of a (sub)string is its number of characters.
• The empty string has length zero.
5-34
String ADTs
•
Assumed application requirements:
1) The values are to be strings of any length.
2) It must be possible to determine the length of a string.
3) It must be possible to obtain the character at a given index.
4) It must be possible to obtain the substring at a given range of
indices.
5) It must be possible to compare strings lexicographically.
6) It must be possible to concatenate strings.
5-35
Immutable strings: contract (1)
• Possible contract expressed as an outline class declaration:
public interface StringADT {
// Each String value is an immutable string of characters,
// of any length, with indices starting at 0.
// private …;
/////////////// Constructor ///////////////
// public String (char[] cs);
// Construct a string consisting of all the chars in cs.
5-36
Immutable strings: contract (2)
• Possible contract (continued):
/////////////// Accessors ///////////////
public int length ();
// Return the length of this string.
public char charAt (int i);
// Return the character at index i in this string.
public bool equals (String that);
// Return true if and only if this string is equal to that.
public int compareTo (String that);
// Return –1 if this string is lexicographically less than that,
// or 0 if this string is equal to that,
// or +1 if this string is lexicographically greater than that.
5-37
Immutable strings: contract (3)
• Possible contract (continued):
/////////////// Transformers ///////////////
public String substring (int i, int j);
// Return the substring of this string consisting of the characters
// whose indices are i, …, j–1.
public String concat (String that);
// Return the string obtained by concatenating this string and
// that.
}
applicative
transformers
5-38
Immutable strings: implementations
• Represent a string by its length n together with an array of
exactly n characters, e.g.:
length 0
4
1
2
3
‘J’ ‘a’ ‘v’ ‘a’
• Or represent a string by its length n together with an SLL
of characters, e.g.:
length first
4
‘J’
‘a’
‘v’
‘a’
• The array representation is much better. Since these strings
are immutable, we never insert or delete characters.
5-39
Mutable strings: contract (1)
• Possible contract expressed as an intertface declaration:
public interface MutableStringADT {
// Each MutableString value is a mutable string, of any
// length, with indices starting at 0.
// private …;
/////////////// Constructor ///////////////
// public MutableString ();
// Construct an empty mutable string.
5-40
Mutable strings: contract (2)
• Possible contract (continued):
/////////////// Accessors ///////////////
public int length ();
// Return the length of this string.
public char charAt (int i);
// Return the character at index i in this string.
public int compareTo (MutableString that);
// Return –1 if this string is lexicographically less than that,
// or 0 if this string is equal to that,
// or +1 if this string is lexicographically greater than that.
public String substring (int i, int j);
// Return the substring of this string consisting of the characters
// whose indices are i, …, j–1.
5-41
Mutable strings: contract (3)
• Possible contract (continued):
/////////////// Transformers ///////////////
public void setCharAt (int i, char c);
// Set the character at index i in this string to c.
public void append (String s);
// Insert the characters of s after the last character of this string.
public void insert (int i, String s);
// Insert the characters of s before the character at index i in
// this string.
public void delete (int i, int j);
// Delete the characters of this string whose indices are i, …,
// j–1.
}
Question: Tableau ou liste?
mutative
transformers
5-42
ADTs in the Java class library
• Class java.lang.String is similar to String above.
• Class java.lang.StringBuffer is similar to
MutableString above.
• Interface java.util.List supports lists.
• Interface java.util.Set supports sets.
• Interface java.util.Map supports maps (tables).
• Packages java.awt, java.io, java.util, etc.,
support many other ADTs.
5-43