Chapter 11Chapter 11 TopicsThe Concept of AbstractionIntroduction to Data AbstractionAdvantages of Data AbstractionLanguage Requirements for ADTsDesign IssuesLanguage Examples: C++Language Examples: C++ (continued)Slide 10Slide 11An Example in C++A Stack class header fileSlide 14Language Examples: JavaAn Example in C++ (need updated)Parameterized Abstract Data TypesParameterized ADTs in C++Parameterized ADTs in C++ (continued)Parameterized Classes in Java 5.0Encapsulation ConstructsNested SubprogramsEncapsulation in CEncapsulation in C++Naming EncapsulationsNaming Encapsulations (continued)SummaryChapter 11Abstract Data Types and Encapsulation ConceptsCopyright © 2012 Addison-Wesley. All rights reserved. 1-2Chapter 11 Topics•The Concept of Abstraction•Introduction to Data Abstraction•Design Issues for Abstract Data Types•Language Examples•Parameterized Abstract Data Types•Encapsulation Constructs•Naming EncapsulationsCopyright © 2012 Addison-Wesley. All rights reserved. 1-3The Concept of Abstraction•An abstraction is a view or representation of an entity that includes only the most significant attributes•The concept of abstraction is fundamental in programming (and computer science)•Nearly all programming languages support process abstraction with subprograms•Nearly all programming languages designed since 1980 support data abstractionsmalltalk, common lisp, C++, etc.Copyright © 2012 Addison-Wesley. All rights reserved. 1-4Introduction to Data Abstraction•An abstract data type is a user-defined data type that satisfies the following two conditions:1. The representation of objects of the type is hidden from the program units that use these objects, so the only operations possible are those provided in the type's definition2. The declarations of the type and the protocols of the operations on objects of the type are contained in a single syntactic unit. Other program units are allowed to create variables of the defined type. (e.g. an object contains data and its method.)Copyright © 2012 Addison-Wesley. All rights reserved. 1-5Advantages of Data Abstraction•Advantages the first condition (hidden)–Reliability (security) -- by hiding the data representations, user code cannot directly access objects of the type or depend on the representation, allowing the representation to be changed without affecting user code–Reduces the range of code and variables of which the programmer must be aware–Name conflicts are less likely•Advantages of the second condition (Unit)–Provides a method of program organization–Aids modifiability (everything associated with a data structure is together)–Separate compilationCopyright © 2012 Addison-Wesley. All rights reserved. 1-6Language Requirements for ADTs•A syntactic unit in which to encapsulate the type definition•A method of making (1) type names and (2) subprogram headers visible to clients, while hiding actual definitions•Some primitive operations must be built into the language processorCopyright © 2012 Addison-Wesley. All rights reserved. 1-7Design Issues•What is the form of the container for the interface to the type?•Can abstract types be parameterized?•What access controls are provided?•Is the specification of the type physically separate from its implementation?Copyright © 2012 Addison-Wesley. All rights reserved. 1-8Language Examples: C++•Based on C struct type and Simula 67 classes•The class is the encapsulation device•A class is a type•All of the class instances of a class share a single copy of the member functions•Each instance of a class has its own copy of the class data members•Instances can be static, stack dynamic, or heap dynamicCopyright © 2012 Addison-Wesley. All rights reserved. 1-9Language Examples: C++ (continued)•Information Hiding–Private clause (e.g., for hidden entities)–Public clause (e.g. for interface entities)–Protected clause (e.g. for inheritance)Copyright © 2012 Addison-Wesley. All rights reserved. 1-10Language Examples: C++ (continued)•Constructors:–Functions to initialize the data members of instances (they do not create the objects)–May also allocate storage if part of the object is heap-dynamic–Can include parameters to provide parameterization of the objects–Implicitly called when an instance is created–Can be explicitly called–Name is the same as the class nameCopyright © 2012 Addison-Wesley. All rights reserved. 1-11Language Examples: C++ (continued)•Destructors–Functions to cleanup after an instance is destroyed; usually just to reclaim heap storage–Implicitly called when the object’s lifetime ends–Can be explicitly called–Name is the class name, preceded by a tilde (~)Copyright © 2012 Addison-Wesley. All rights reserved. 1-12An Example in C++class Stack {private:int *stackPtr, maxLen, topPtr;public:Stack() { // a constructorstackPtr = new int [100];maxLen = 99;topPtr = -1;};~Stack() {delete [] stackPtr;};void push (int number) { if (topSub == maxLen) cerr << ″Error in push - stack is full\n″; else stackPtr[++topSub] = number; };void pop () {…};int top () {…};int empty () {…};}A Stack class header file// Stack.h - the header file for the Stack class#include <iostream.h>class Stack {private: //** These members are visible only to other//** members and friends (see Section 11.6.4) int *stackPtr; int maxLen; int topPtr;public: //** These members are visible to clients Stack(); //** A constructor ~Stack(); //** A destructor void push(int); void pop(); int top(); int empty();}Copyright © 2012 Addison-Wesley. All rights reserved. 1-13Language Examples: C++ (continued)•Friend functions or classes to provide access to private members to some unrelated units or functionsNecessary in C++class Foo; // Forward declaration of class Foo in order for example to compile. class Bar { private: int a; friend void ::show(Bar& x, Foo& y); // declaration of global friend }; class Foo { private: int b; void Bar::show(Bar& x, Foo& y); // declaration of friend from other class }; Copyright © 2012 Addison-Wesley. All rights reserved. 1-14Copyright © 2012 Addison-Wesley. All rights reserved. 1-15Language Examples: Java•Java, similar to C++, except:–All user-defined types are classes–All objects are allocated from the heap and accessed through reference variables–Individual entities in classes have access control modifiers (private or public), rather than clauses–Java has a