1 Introduction2 What is an Abstract Data Type?2.1 The ADTs Integer and Java int3 How is an ADT specified?4 The concept of class and objects5 The ADT Pair5.1 An implementation of the ADT Pair as a class5.2 Using the class implementation of the ADT Pair6 A second example: rationals6.1 The class for rationals6.2 A helper class for the rationals7 Keeping track of objects8 Summary07 ADTs Chapter 7Abstract Data Types and ClassesThis chapter describes a fundamental concept of modern programming: thatof abstract data type. Program development with abstract data types enablesus to express problem solutions using concepts – that is, abstractions – thatare appropriate to the problem. Constructing data types appropriate to aproblem isolates the principal task of expressing the algorithms of anapplication from the details of data representation and manipulation.Abstract data types provide the foundation for object-oriented programming.We will be revisiting some Java concepts we have seen already: classes,objects, and methods, but this time with emphasis on abstraction.1 IntroductionThe principal data types of a language such as Java commonly include integer and realnumbers, booleans, characters and strings, and arrays of fixed size. Such a listing of typesappears rich until one reflects on what is not included: fractions, imaginary numbers,complex numbers, polynomials, sequences, queues, stacks, trees, and graphs, to name just afew. Thus, while Java's collection of primitive types is substantial, it is by no meanscomplete. Other languages offer a few more types including subrange (restricting the valuesof an integer or character to some smaller range), enumerated types (where the type isdefined by simply listing all the possible values), and sets. But we can’t fix the problem byadding more types – any collection will be incomplete. The lack of an appropriate data type can cause substantial problems to arise even inconceptually simple situations. Consider the problem of calculating the due date for a bookthat is borrowed from a library, and of calculating the fine for a book that was returned afterthe due date. If the lending period is two weeks, then each time a book is loaned, the duedate is the date of the loan plus fourteen days. If a data type called “date” were available andthe value of the variable currentDate was today’s date, then the due date might reasonablybe expressed as the value of the expression (currentDate + 14). Similarly, when anoverdue book was returned, we could calculate the number of days overdue as the value of 2001Donald F. Stanat & Stephen F. WeissChapter 7 Abstract Data Types and Classes Page 2the expression (currentDate - dueDate). While adding 14 to a date and finding thedifference between two dates are conceptually simple tasks, there are ample opportunitiesfor error: Does adding 14 cause the month or year to change? Is it a leap year? If theprogrammer is provided with a (correctly implemented) “date” data type; these questions donot arise because they are handled by the implementation. Clearly, using a data typeappropriate to a problem can make the expression of algorithms both more transparent andless error-prone.Faced with the problem of designing and implementing algorithms, a naive programmer istempted to fall into the trap of not keeping separate the problems of how data arerepresented and manipulated from the problems of expressing the algorithms of interest. Incontrast, the sophisticated programmer recognizes that the choice of data representation,and therefore the implementation of the operations, can be made independently, and can besolved separately. Divorcing the problems of implementing a data type from those ofexpressing the desired algorithms is one way that programmers enforce a separation ofconcerns. This separation not only supports unencumbered thinking (e.g., subtraction of onedate from another can be done without concern for whether a leap year is involved), but alsosimplifies changes in either the essential algorithms of the application or in the way that dataare represented and manipulated.This leads to an approach to problem solving based on abstract data types: the solution to aproblem is expressed using data types appropriate to the problem. For example, thealgorithms of a chess-playing program will be expressed in terms of the current boardconfiguration and movements of the pieces. A particular board configuration will be a valueof the data type. The operations on the data type will include legitimate moves of a piecefrom one square to another and capture of the opponent’s pieces as well as less obviousoperations such as tests to determine the condition of the current board configuration (e.g.,Is the king is under attack?). The availability of such a data type makes it possible toimplement algorithms related to chess in a way familiar to and comfortable for chess players.There is no reference to the way a chess board is represented or how the representationchanges when a piece is moved.Entirely separately, a programmer is faced with the problem of implementing the data typeswith which the strategies are expressed. For chess, this requires first choosing arepresentation for legitimate board configurations and then writing algorithms to interpretmoves of chess pieces as changes in the representation and tests of board configurations(such as “Is the king in check?”) as tests of properties of the representation. The problems in both domains – that of playing chess, and that of representing the play –can be difficult, but divorcing the difficulties of the domains from one another providestremendous advantages both for writing and maintaining software.2 What is an Abstract Data Type?The concept of abstract data type is not one that can be rigorously defined in a way that issatisfactory for every need, so our definition is necessarily informal.Printed at &2Chapter 7 Abstract Data Types and Classes Page 3Definition: An abstract data type (ADT) is a set of values, some of which may bedistinguished as constants, together with a collection of operations involving members