Abstract Data Types Data types I We type data classify it into various categories such as int boolean String Applet A 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 errors Some operations only make sense when applied to certain kinds of data multiplication searching Typing simplifies internal representation A String requires more and different storage than a boolean Data types II p 98 A data type is characterized by a set of values a data representation which is common to all these values and a set of operations which can be applied uniformly to all these values Primitive types in Java Java provides eight primitive types boolean char byte short int long float double Each primitive type has a set of values a data representation a set of operations These are set in stone there is nothing the programmer can do to change anything about them Primitive types as data types Type Values Representation Operations boolean true false Single byte Two s complement others Floating point Two s complement numbers of with exponent and varying sizes mantissa and precisions others char byte Integers of short int varying sizes long float double Classes in Java A class is a data type The possible values of a class are called objects The data representation is a reference pointer to a block of storage The structure of this block is defined by the fields both inherited and immediate of the class The operations on the objects are called methods Many classes are defined in Java s packages You can and must define your own as well Methods and operators An operator typically Is written with non alphabetic characters etc Is written as prefix infix or postfix x x y x Has only one or two arguments or operands A method or function typically Is written with letters and its arguments are enclosed in parentheses twoString Math abs n Has any predetermined number of arguments Methods are operators The differences between methods and operations are only syntactic differences not fundamental ones Many languages not including Java let you define new operators that is new syntax When you define a new class and its methods you are fundamentally defining a new data type and its operators Suppose a language defines the operator to mean times 3 plus 1 for example 7 is 22 Would you consider this a good operation to have in the language What does this suggest about defining classes and their methods Insertion into a list There are many ways you could insert a new node into a list 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 order Is it a good idea to supply all of these If not why not Cognitive load Human minds are limited you can t remember everything You probably don t even remember all the Java operators for integers What s the difference between and What about between and We want our operators and methods to be useful and worth remembering Efficiency A list is just a sequence of values it could be implemented by a linked list or by an array Inserting as a new first element is efficient for a linked list representation inefficient for an array Accessing the nth element is efficient for an array representation inefficient for a linked list Inserting in the nth position is efficient for neither Do we want to make it easy for the user to be inefficient Do we want the user to have to know the implementation Abstract Data Types p 103 An Abstract Data Type ADT is a set of values a set of operations which can be applied uniformly to all these values To abstract is to leave out information keeping hopefully the more important parts What part of a Data Type does an ADT leave out Data representation in an ADT An ADT must obviously have some kind of representation for its data The user need not know the representation The user should not be allowed to tamper with the representation Solution Make all data private But what if it s really more convenient for the user to have direct access to the data Solution Use setters and getters Example of setters and getters 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 Aside naming setters and getters Setters and getters should be named by Capitalizing the first letter of the variable first becomes First and Prefixing 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 requirement What s the point Setters and getters allow you to keep control of your implementation For 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 directly If you had used setters and getters you could redefine them to compute x and y from and Contracts p 104 Every ADT should have a contract or specification that Specifies the set of values of the ADT Specifies for each operation of the ADT Its name Its parameter types Its result type if any Its observable behavior Does not specify The data representation The algorithms used to implement the operations Importance of the contract A contract is an agreement between two parties in this case The implementor of the ADT who is concerned with making the operations correct and efficient The applications programmer who just wants to use the ADT to get a job done It doesn t matter if you are both of these parties the contract is still essential for good code This separation of concerns is essential in any large project Implementing an ADT To implement an ADT you need to choose a data representation must be able to represent all possible values of the ADT should be private an algorithm for each of the possible operations must be consistent with the chosen representation all auxiliary helper operations that are not in the contract should be private Contract and implementation in Java method I Express the contract as an
View Full Document
Unlocking...