I. Design and Implementaiton of ADTs (HR 9.1) A. overview ------------------------------------------ HR CHAPTER 9 DESIGN AND IMPLEMENTAITON OF ADTS Topics: A. How to design an ADT's operations? 1. abstract domain 2. kinds of operations 3. completeness and testability B. How to implement an ADT correctly? 1. Choosing a reprsentation 2. Abstraction map 3. Abstract vs concrete assertions 4. Examples C. How to specify an ADT? 1. Primitive models 2. Non-primitive models (layers) ------------------------------------------ B. review of ADTs ------------------------------------------ ABSTRACT DATA TYPES def: an *abstract data type* (ADT) is a type specified by: (1) a set of *abstract values*, and (2) specifications for the *operations* on the values ------------------------------------------ ------------------------------------------ def: an *implementation* of an ADT consists of: (1) a data structure that (concretely) represents the abstract values (2) code for the operations that has - the specified interface, and - behaves as specified ------------------------------------------ What's the C++ mechanism for an ADT implementation? What in C++ defines the data structure representation? What in C++ defines the code for the operations? II. design of ADT operations (HR 9.2) A. overview (p. 390) ------------------------------------------ OVERVIEW OF ADT DESIGN PROCESS Steps involved: 1. describe (model) the abstract values 2. select and specify the operations 3. evaluate for completeness, simplicity ------------------------------------------ B. examples 1. immutable Ratl type ------------------------------------------ DESIGN OF RATIONAL NUMBER TYPES Ratl 1. model is ___________________________ 2. operations class Ratl { public: Ratl(int n, int d); // PRE: d != 0 // MODIFIES: self // POST: self = (n/d) int numr() const; // POST: FCTVAL == numerator of self int denr() const; // POST: FCTVAL == denominator of self #include "Ratl.pri" }; ------------------------------------------ What is being hidden by this type? ------------------------------------------ def: a ADT has *immutable objects* iff the abstract value of the object ------------------------------------------ Is Ratl simple? Is Ratl complete? What kinds of things might we want to do? Can you program these as a client of Ratl? What if we didn't have the denr function, would it be complete? 2. immutable Fraction type (more operations) ------------------------------------------ A "FULL-FEATURED" TYPE DESIGN class Fraction { public: // C++ constructors (primitive) Fraction(); Fraction(int i); Fraction(int n, int d); // ADT-constructors (non-primitive) Fraction operator +(Fraction oth) const; Fraction operator -(Fraction oth) const; // etc. // observers int numr() const; int denr() const; double DoubleEquiv() const; Boolean operator ==(Fraction oth) const; Boolean operator < (Fraction oth) const; // etc. #include "Fraction.pri" }; ostream& operator << (ostream& out, Fraction f); istream& operator >> (istream& in, Fraction& f); ------------------------------------------ 3. set types ------------------------------------------ MUTABLE OBJECTS def: a ADT has *mutable objects* iff the abstract value of the object ------------------------------------------ ------------------------------------------ KINDS OF OPERATIONS FOR TYPES WITH MUTABLE OBJECTS - C++ constructors (primitive) - a C++ destructor - ADT-constructors (non-primitive) - observers - mutators e.g., Delete from an IntSet operator = ------------------------------------------ Where does the assignment operator fit in? The copy constructor? ------------------------------------------ FOR YOU TO DO (In groups of 3 or 4) A first step in the design of an ADT for sets of Integers. Use mathematical sets as the model. List operations in two parts: (a) a minimal, but complete set (b) others for a "full-featured" set Also, write down any functions that (c) should be implemented as client code. Write down both a name and a prototype for each operation and function. ------------------------------------------ C. completeness (HR pp. 394-5) ------------------------------------------ COMPLETENESS FOR ADTS def: Let T be an ADT with domain D. The design of T is *complete* iff: 1. For each abstract value v in D, a client can construct an object with abstract value v. 2. A client can program any computable function on ------------------------------------------ ------------------------------------------ 3. If T has mutators, then ------------------------------------------ Does set have enough constructors? ------------------------------------------ TESTABILITY def: an ADT has testable preconditions if the veracity of each precondition in its specifiction ------------------------------------------ III. Correctness of ADT implementations (HR 9.3) A. overview 1. abstraction maps ------------------------------------------ THE ABSTRACTION MAP RELATES REPRESENTATION TO ABSTRACT VALUES // IntStack.h class IntStack { public: // ABSTRACTLY: a sequence of ints, // written <3,4,5>, with 3 the top // ... #include "IntStack.pri" }; // IntStack.pri private: struct ElemNode { int val; ElemNode *link; }; ElemNode *top; // ABSTRACTION MAP: the abstract value // is the sequence formed from the list // in order starting from *top. PICTURE abstract value: concrete rep: ------------------------------------------ 2. model pictures of operations in abstract and concrete views ------------------------------------------ ABSTRACT AND CONCRETE VIEW OF OPERATIONS IntStack(); s: ------------> s: <> s.Push(3) s: <> -----------> s: <3> ------------------------------------------ ------------------------------------------ FOR YOU TO DO Complete the following: s.Pop() s: <3> -----------> s: <> s.Top() s: <3> -----------> s: <3> FCTVAL: 3 ------------------------------------------ 3. predicate pictures of operations in abstract and concrete ------------------------------------------ ABSTRACT AND CONCRETE VIEW OF SPECS IntStack(); true ==========> self == <> Push(n) self isn't ==========> self == full AppendFront(self) ------------------------------------------ ------------------------------------------ FOR YOU TO DO Complete the following: Pop() self isn't =============> self == empty RemoveFront(self) Top() self isn't =======> FCTVAL == Front(self) empty ------------------------------------------ 4. remarks on invariants What's the use of having an abstract invariant for a class? What's the use of having a concrete invariant for a class? If we implemented IntSet with a singly-linked list, what might be a useful concrete invariant? B. examples (HR 9.7 and 9.8, see also HR 9.3-6) ------------------------------------------ RING BUFFER IMPLEMENTATION OF QUEUE Pictures: ------------------------------------------ IV. specification issues (HR 9.9-10) A. primitive models ------------------------------------------ PROBLEM English specifications can be ambiguous. How can they be made less ambiguous? ------------------------------------------ What are the parts of an ADT specification? How can we formalize each part? ------------------------------------------ PRIMITIVE MODELS Examples: - integers - Booleans - characters - sets - sequences - tuples def: a *primitive model* is a mathematically characterized concept. These are used to define ------------------------------------------ ------------------------------------------ It should: - be commonly understood - have a well-defined notation ------------------------------------------ B. levels of abstraction (HR 9.10) ------------------------------------------ LEVELS OF ABSTRACTION IntSet abstract values: {3, 4} list picture: hardware picture: ------------------------------------------ ------------------------------------------ GOING HIGHER Map of City: Graph: Set: List: ------------------------------------------ V. design and implementation of ADT summary ------------------------------------------ SUMMARY What are the steps in designing an ADT? What are the key ideas in making a correct implementation of an ADT? ------------------------------------------