Abstract Data TypesData typesSlide 3Classes in JavaADTs are better than DTsExample of an ADTData representation in an ADTExample of setters and gettersAside: Naming setters and gettersWhat’s the point?And another thing...ContractsImportance of the contractPromise no more than necessaryImplementing an ADTWriting the contractInterfacesSummaryThe EndJan 13, 2019Abstract Data Types2Data typesA 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 values3Abstract 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?4Classes in JavaA class defines a data typeThe possible values of a class are called objectsThe operations on the objects are called methodsThe data representation is all the fields that are contained within the objectIf there is no external access to the data representation, you have an abstract data typeSun’s Java classes are (almost all) abstract data types5ADTs are better than DTsIt is the responsibility of a class to protect its own data, so that objects are always in a valid stateInvalid objects cause program bugsBy keeping the responsibility in one place, it is easier to debug when invalid objects are presentThe less the user has to know about the implementation, the easier it is to use the classThe less the user does know about the implementation, the less likely s\he is to write code that depends on it“Less is more”6Example of an ADTStack s = new Stack();s.push("Hello");String a = s.peek();Color b = s.pop();if (s.empty()) {...}int i = s.search("Hello");The operations are the methods shown on the leftThe values are all the possible stacksWe can construct any value with the supplied operationsWe can discover the value by using the given operationsWe don’t care about the representation (so long as it works well!)“Less is more”7Data 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 getters8Example 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; }}9Aside: 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 requirement10What’s the point?We can claim that a class is an abstract data type if we make all data privateHowever, if we then provide unlimited access by providing simple getters and setters for everything, we are only fooling ourselvesRules:Only supply getters and setters if there is a clear use for themDo not supply getters and setters that depend on the particular implementation you are usingNever, never write a setter that could be used to create an invalid object!Your setters should do all possible error checking before they change the object11And another thing...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 used setters and getters, you could redefine them to compute x and y from θ and ρ12ContractsEvery ADT should have a contract (or specification) that:Specifies the set of valid values of the ADTSpecifies, for each operation of the ADT:Its nameIts parameter typesIts result type, if anyIts observable behaviorDoes not specify:The data representationThe algorithms used to implement the operations13Importance of the contractA contract is an agreement between two parties; in this caseThe implementer of the ADT, who is concerned with making the operations correct and efficient, and also with preserving the flexibility to make changes laterThe applications programmer, who just wants to use the ADT to get a job doneIt doesn’t matter if you are both of these parties; the contract is still essential for good codeThis separation of concerns is essential in any large project14Promise no more than necessaryFor a general API, the implementer should provide as much generality as feasibleThis is the way Sun’s classes are (mostly) writtenBut for a specific program, the class author should provide only what is essential at the momentIn Extreme Programming terms, “You ain’t gonna need it!”In fact, XP practice is to remove functionality that isn’t currently needed!Your documentation should not expose anything that the application programmer does not need to knowIf you design for generality, it’s easy to add functionality later—but removing it may have serious consequences15Implementing an ADTTo implement an ADT, you need to choose:a data representation thatmust be able to represent all possible values of the ADTshould be privatea set of methods that support normal use of the ADTThe user must be able to create, possibly modify, and examine the values of the ADTan algorithm for each of the possible operations thatmust be consistent with the chosen representationall auxiliary (helper) operations that are not in the contract should be private16Writing the contractIn most cases, the Javadoc for a class is the contractThis means:The Javadoc documentation should describe what the class is for and how it should be usedThe Javadoc
View Full Document
Unlocking...