Abstract Data TypesData types IData types II (p. 98)Primitive types in JavaPrimitive types as data typesClasses in JavaMethods and operatorsMethods are operatorsInsertion into a listCognitive loadEfficiencyAbstract Data Types (p. 103)Data representation in an ADTExample of setters and gettersAside: naming setters and gettersWhat’s the point?ContractsImportance of the contractPromise no more than necessaryImplementing an ADTContract and implementation in Java, method IContract and implementation in Java, method IIExample contract (method I)Implementation, method I, page 1Implementation, method I, page 2Contract, method IIImplementation, method IIResponsibilitiesAside: an interesting bugSummaryThe EndJan 14, 2019Abstract Data Types2Data types IWe type data--classify it into various categories--such as int, boolean, String, AppletA data type represents a set of possible values, such as {..., -2, -1, 0, 1, 2, ...}, or {true, false}By typing our variables, we allow the computer to find some of our errorsSome operations only make sense when applied to certain kinds of data--multiplication, searchingTyping simplifies internal representationA String requires more and different storage than a boolean3Data types II (p. 98)A data type is characterized by:a set of valuesa data representation, which is common to all these values, and a set of operations, which can be applied uniformly to all these values4Primitive types in JavaJava provides eight primitive types:booleanchar, byte, short, int, longfloat, doubleEach primitive type hasa set of valuesa data representationa set of operationsThese are “set in stone”—there is nothing the programmer can do to change anything about them5Primitive types as data typesType Values Representation Operations boolean true, false Single byte &&, ||, ! char, byte, short, int, long Integers of varying sizes Two’s complement +, -, *, /, others float, double Floating point numbers of varying sizes and precisions Two’s complement with exponent and mantissa +, -, *, /, others6Classes in JavaA class is a data typeThe possible values of a class are called objectsThe data representation is a reference (pointer) to a block of storageThe structure of this block is defined by the fields (both inherited and immediate) of the classThe operations on the objects are called methodsMany classes are defined in Java’s packagesYou can (and must) define your own, as well7Methods and operatorsAn operator typicallyIs written with non-alphabetic characters: +, *, ++, +=, &&, etc.Is written as prefix, infix, or postfix: -x, x+y, x++Has only one or two arguments, or operandsA method (or function) typicallyIs written with letters, and its arguments are enclosed in parentheses: toString(), Math.abs(n)Has any (predetermined) number of arguments8Methods are operatorsThe differences between methods and operations are only syntactic differences, not fundamental onesMany languages (not including Java) let you define new operators, that is, new syntaxWhen you define a new class and its methods, you are, fundamentally, defining a new data type and its operatorsSuppose a language defines the operator @ to mean “times 3 plus 1”; for example @7 is 22Would you consider this a good operation to have in the language?What does this suggest about defining classes and their methods?9Insertion into a listThere are many ways you could insert a new node into a list:Is it a good idea to supply all of these?If not, why not?• As the new first element• As the new last element• Before a given node• After a given node• Before a given value• After a given value• Before the nth element• After the nth element• Before the nth from the end• After the nth from the end• In the correct location to keep the list in sorted order10Cognitive loadHuman minds are limited—you can’t remember everythingYou probably don’t even remember all the Java operators for integersWhat’s the difference between >> and >>> ?What about between << and <<< ?We want our operators (and methods) to be useful and worth remembering11EfficiencyA list is just a sequence of values—it could be implemented by a linked list or by an arrayInserting as a new first element is efficient for a linked list representation, inefficient for an arrayAccessing the nth element is efficient for an array representation, inefficient for a linked listInserting in the nth position is efficient for neitherDo we want to make it easy for the user to be inefficient?Do we want the user to have to know the implementation?12Abstract Data Types (p. 103)An Abstract Data Type (ADT) is:a set of valuesa set of operations, which can be applied uniformly to all these valuesTo abstract is to leave out information, keeping (hopefully) the more important partsWhat part of a Data Type does an ADT leave out?13Data representation in an ADTAn ADT must obviously have some kind of representation for its dataThe user need not know the representationThe user should not be allowed to tamper with the representationSolution: Make all data privateBut what if it’s really more convenient for the user to have direct access to the data?Solution: Use setters and getters14Example of setters and gettersclass 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; }}15Aside: naming setters and gettersSetters and getters should be named by:Capitalizing the first letter of the variable (first becomes First), andPrefixing the name with get or set (setFirst)For boolean variables, you can replace get with is (for example, isRunning) This is more than just a convention—if and when you start using JavaBeans, it becomes a requirement16What’s the point?Setters and getters allow you to keep control of your implementationFor example, you decide to define a Point in a plane by its x-y coordinates:class Point { public int x; public int y; }Later on, as you gradually add methods to this class, you decide that it’s more efficient to represent a point by its angle and distance from the origin, θ and ρSorry, you can’t do that—you’ll break too much code that accesses x and y directlyIf you had
View Full Document