07 ADTs Chapter 7 Abstract Data Types and Classes This chapter describes a fundamental concept of modern programming that of abstract data type Program development with abstract data types enables us to express problem solutions using concepts that is abstractions that are appropriate to the problem Constructing data types appropriate to a problem isolates the principal task of expressing the algorithms of an application 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 Introduction The principal data types of a language such as Java commonly include integer and real numbers booleans characters and strings and arrays of fixed size Such a listing of types appears rich until one reflects on what is not included fractions imaginary numbers complex numbers polynomials sequences queues stacks trees and graphs to name just a few Thus while Java s collection of primitive types is substantial it is by no means complete Other languages offer a few more types including subrange restricting the values of an integer or character to some smaller range enumerated types where the type is defined by simply listing all the possible values and sets But we can t fix the problem by adding more types any collection will be incomplete The lack of an appropriate data type can cause substantial problems to arise even in conceptually simple situations Consider the problem of calculating the due date for a book that is borrowed from a library and of calculating the fine for a book that was returned after the due date If the lending period is two weeks then each time a book is loaned the due date is the date of the loan plus fourteen days If a data type called date were available and the value of the variable currentDate was today s date then the due date might reasonably be expressed as the value of the expression currentDate 14 Similarly when an overdue book was returned we could calculate the number of days overdue as the value of 2001Donald F Stanat Stephen F Weiss Chapter 7 Abstract Data Types and Classes Page 2 the expression currentDate dueDate While adding 14 to a date and finding the difference between two dates are conceptually simple tasks there are ample opportunities for error Does adding 14 cause the month or year to change Is it a leap year If the programmer is provided with a correctly implemented date data type these questions do not arise because they are handled by the implementation Clearly using a data type appropriate to a problem can make the expression of algorithms both more transparent and less error prone Faced with the problem of designing and implementing algorithms a naive programmer is tempted to fall into the trap of not keeping separate the problems of how data are represented and manipulated from the problems of expressing the algorithms of interest In contrast the sophisticated programmer recognizes that the choice of data representation and therefore the implementation of the operations can be made independently and can be solved separately Divorcing the problems of implementing a data type from those of expressing the desired algorithms is one way that programmers enforce a separation of concerns This separation not only supports unencumbered thinking e g subtraction of one date from another can be done without concern for whether a leap year is involved but also simplifies changes in either the essential algorithms of the application or in the way that data are represented and manipulated This leads to an approach to problem solving based on abstract data types the solution to a problem is expressed using data types appropriate to the problem For example the algorithms of a chess playing program will be expressed in terms of the current board configuration and movements of the pieces A particular board configuration will be a value of the data type The operations on the data type will include legitimate moves of a piece from one square to another and capture of the opponent s pieces as well as less obvious operations 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 to implement 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 representation changes when a piece is moved Entirely separately a programmer is faced with the problem of implementing the data types with which the strategies are expressed For chess this requires first choosing a representation for legitimate board configurations and then writing algorithms to interpret moves 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 provides tremendous 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 is satisfactory for every need so our definition is necessarily informal Printed at 2 Chapter 7 Abstract Data Types and Classes Page 3 Definition An abstract data type ADT is a set of values some of which may be distinguished as constants together with a collection of operations involving members of the set This suffices as a definition of ADT But if the ADT is to be useful we must be able to create instances of the ADT and apply the operations to those instances For example the set of values could be the set of all arrangements of chess pieces on a chessboard together with a flag or switch that indicates whether it is white or black s move 1 The set of operations on those values must include the set of all legal moves and will almost certainly include others as well such as tests for whether the game is over There is also a distinguished value or constant which is the initial configuration of a game While a chessboard provides a convenient illustration of an ADT there is really no need to step outside Java to illustrate the concept 2 since it is simply a generalization of our view of built in data