Abstract Data TypesData types IData types IIPrimitive types in JavaPrimitive types as data typesClasses in JavaMethods and operatorsMethods are operatorsInsertion into a listCognitive loadEfficiencySlide 12Data StructuresData representation in an ADTExample of setters and gettersNaming setters and gettersWhat’s the point?ContractsImportance of the contractPromise no more than necessaryImplementing an ADTExample contract (Javadoc)Implementation, page 1Implementation, page 2ResponsibilitiesAside: an interesting bugSummaryThe EndJan 13, 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 IIA 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 TypesAn 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 StructuresMany kinds of data consist of multiple parts, organized (structured) in some wayA data structure is simply some way of organizing a value that consists of multiple partsHence, an array is a data structure, but an integer is notWhen we talk about data structures, we are talking about the implementation of a data typeIf I talk about the possible values of, say, complex numbers, and the operations I can perform with them, I am talking about them as an ADTIf I talk about the way the parts (“real” and “imaginary”) of a complex number are stored in memory, I am talking about a data structureAn ADT may be implemented in several different waysA complex number might be stored as two separate doubles, or as an array of two doubles, or even in some bizarre way14Data 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 getters15Example 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; }}16Naming 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, replace get with is (for example,
View Full Document