adt presentation

7/25/2019 ADt Presentation

1/19

Jan 29, 2016

Abstract Data Types


2/19

Data types

2

A data typeis characterized by:a set of valuesa data representation,which is common to

all these values, anda set of operations,which can be applied

uniformly to all these values


3/19

Abstract Data Types

3

An Abstract Data Type(ADT) is:a set of valuesa set of operations,which can be applied

uniformly to all these values

To abstractis to leave out information,eepin! (hopefully) the more importantparts

"hat part of a Data Type does an ADT leaveout#


4/19

$lasses in %ava

&

A class de'nes a data typeThe possible valuesof a class are called obectsThe operationson the obects are called methodsThe data representationis all the 'elds that are

contained within the obect

f there is no e*ternal access to the datarepresentation, you have an abstract data type

+uns %ava classes are (almost all) abstract datatypes


5/19

ADTs are better than DTs

-

t is the responsibility of a class to protect its owndata, so that obects are always in a valid statenvalid obects cause pro!ram bu!s.y eepin! the responsibility in one place, it is

easier to debu! when invalid obects are presentThe less the user has to now about the

implementation, the easier it is to use the class

The less the user doesnow about the

implementation, the less liely s/he is to writecode that depends on it

01ess is more


6/19

*ample of an ADT

4

Stack s = new Stack();

s.push("Hello");

String a = s.peek();

Color b = s.pop();if (s.empty()) {...

int i = s.search("Hello");

The operationsare themethods shown on the left

The valuesare all thepossible stacs

"e can construct any valuewith the supplied operations

"e can discover the value byusin! the !iven operations

"e dont careabout the

representation (so lon! asit wors well5)01ess is more


7/19

Data representation in anADT

6

An ADT must obviously have someind ofrepresentation for its dataThe user need not now the representationThe user should not be allowed to tamper

with the representation+olution: 7ae all data private

.ut what if its really more convenient for

the user to have direct access to the data#+olution: 8se settersand getters


8/19

*ample of setters and!etters

9

class Pair {private int first, last;

public getFirst() { return first; }

public setFirst(int first) { this.first = first; }

public getLast() { return last; }

public setLast(int last) { this.last = last; }

}


9/19

Aside: amin! setters and!etters

;

+etters and !etters should be named by:$apitalizin! the 'rst letter of the variable

(firstbecomes First), and


10/19

"hats the point#

?@

"e can claimthat a class is an abstract data type ifwe mae all data private

owever, if we then provide unlimited access byprovidin! simple !etters and setters for everythin!,we are only foolin! ourselves

Bules:Cnly supply !etters and setters if there is a clear use for

them

Do not supply !etters and setters that depend on theparticular implementation you are usin!

ever, neverwrite a setter that could be used to create aninvalid obect5our setters should do all possible error checin! before they

chan!e the obect


11/19

And another thin!EEE

??

+etters and !etters allow you to eep control ofyour implementation

=or e*ample, you decide to de'ne a Pointin aplane by its *Fy coordinates:class Point { public int x; public int ; }

1ater on, as you !radually add methods to thisclass, you decide that its more eGcient torepresent a point by its an!le and distance fromthe ori!in, H and I

+orry, you cant do that>youll brea too muchcode that accesses xand directlyf you had used setters and !etters, you could

rede'ne them to computexand from H and I


12/19

$ontracts

?2

very ADT should have a contract(orspeci'cation) that:+peci'es the set of valid values of the ADT+peci'es, for each operation of the ADT:ts name

ts parameter types

ts result type, if any

ts observable behavior

Does notspecify:The data representation

The al!orithms used to implement the operations


13/19

mportance of the contract

?3

A contract is an a!reement between twopartiesJ in this caseThe implementerof the ADT, who is concerned

with main! the operations correct and eGcient,and alsowith preservin! the Ke*ibility to maechan!es laterThe applications pro!rammer, who ust wants to

usethe ADT to !et a ob done

t doesnt matter if you are bothof these

partiesJ the contract is still essentialfor !oodcodeThis separation of concernsis essential in any

lar!e proect


14/19


15/19

mplementin! an ADT

?-

To implement an ADT, you need to choose:a data representation thatmust be able to represent all possible values of the ADT

should be private

a set of methods that support normal use of theADTThe user must be able to create, possibly modify, and

e*amine the values of the ADT

an al!orithm for each of the possible operations

thatmust be consistent with the chosen representation

all au*iliary (helper) operations that are not in thecontract should be private


16/19

"ritin! the contract

?4

n most cases, the %avadoc for a class isthe contractThis means:The %avadoc documentation should describe what the class is

for and how it should be used

The %avadoc documentation should notdescribe

implementation detailsAlso, now is a !ood time to read DocumentationComments(rules 39 to -9) in The Elements of Java Style

+ometimes, howeverEEE

The particular implementation maes certain operationseGcient at the cost of main! others ineGcient

=or e*ample, %ava provides both !rrayist(fast randomaccess) and inke#ist(fast insertions and deletions)

The user needs to now this information, but doesnt needdetailed implementation information


17/19

nterfaces

?6

n many cases, an interfacemaes a bettercontract than a concrete implementation

"hy# .ecause the interface can only describewhat the ADT doest cannot describe variablest cannot provide an implementationAlso, unfortunately, it cannot describe constructors

Desi!n principle: 0


18/19

+ummary

?9

A Data Typedescribes values, representations, andoperations

An Abstract Data Typedescribes values andoperations, but notrepresentations

An ADT shouldprotect its dataand keep it validAll, or nearly all, data should be private

Access to data should be via !etters and setters

An ADT should provide:

A contract

A necessary and sucientset of operations for theintended use of the ADT

Depend on the abstraction, not the particularimplementation


19/19

?;

adt presentation

Documents