[attachment=12793]
Abstract Data Types and Encapsulation Concepts
The Concept of Abstraction
Introduction to Data Abstraction
Design Issues for Abstract Data Types
Language Examples
Parameterized Abstract Data Types
Encapsulation Constructs
Naming Encapsulations
The 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
Example: sort(myArray);
Nearly all programming languages designed since 1980 support data abstraction.
Built in
Example: Float data type.
User Defined (ADTs)
Example: Stack
Introduction to Data Abstraction
An ADT, abstract data type, is a user-defined data type that satisfies the following two conditions:
The representation of, and operations on, objects of the type are defined in a single syntactic unit.
Example: In Java the class is used.
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 definition.
Example: In Java visibility modifiers are used.
Advantages of Data Abstraction
Advantage of the first condition
Program organization, modifiability (everything associated with a data structure is together), and separate compilation
Advantage the second condition
Reliability--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
Data Abstraction
Interface is public
Implementation is private
An Example
Stack ADT
Create (stack)
Destroy (stack)
Boolean Empty (stack)
Push (stack, element)
Element Pop (stack)
Element Top (stack)
Client code
Create(stk1)
Push(stk1, color1)
Push(stk1, color2)
If (!Empty(stk1))
Element temp = Pop(stk1);
Scenarios
Implementation change
Interface change
Design Issues
A syntactic unit to define an ADT.
Type name must be visible.
Implementation must be private.
Limited Built-in operations
Assignment
Comparison
Common operations
Iterators
Accessors
Constructors
Destructors
Parameterized ADTs
Language Examples: C++
Encapsulation
The class - based on C struct type and Simula 67 classes
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 stack dynamic or heap dynamic
Information Hiding
Private clause for hidden entities
Public clause for interface entities
Protected clause for inheritance
Language Examples: C++ (continued)
Constructors:
Functions to initialize the data members of instances
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 name
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 (~)
An Example in C++
class stack {
private:
int *stackPtr, maxLen, topPtr;
public:
stack() { // a constructor
stackPtr = new int [100];
maxLen = 99;
topPtr = -1;
};
~stack () {delete [] stackPtr;};
void push (int num) {…};
void pop () {…};
int top () {…};
int empty () {…};
}
Evaluation of ADTs in C++ and Ada
C++ support for ADTs is similar to expressive power of Ada
Both provide effective mechanisms for encapsulation and information hiding
In C++, classes are types, whereas in Ada packages are more general encapsulations.
Language Examples: Java
Similar to C++, except:
All user-defined types are classes (structs, etc…)
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 second scoping mechanism, package scope, which can be used in place of friends
All entities in all classes in a package that do not have access control modifiers are visible throughout the package
An Example in Java
public class StackClass {
private int [] stackRef;
private topIndex;
public StackClass() { // a constructor
stackRef = new int [100];
topIndex = -1;
};
public void push (int num) {…};
public void pop () {…};
public int top () {…};
public boolean empty () {…};
}
Parameterized Abstract Data Types
Parameterized ADTs allow designing an ADT that can store any type elements
Also known as generic classes
C++ and Ada provide support for parameterized ADTs
Java 5.0 provides a restricted form of parameterized ADTs
C# does not currently support parameterized classes
Parameterized ADTs in C++
Classes can be somewhat generic by writing parameterized constructor functions
template <class type>
class stack {
private:
Type *stackptr{
int maxLen; int topPtr;
public:
stack(int size) {
stk_ptr = new Type[size];
max_len = size - 1;
topPtr = -1;
};
…
void push( Type number) { …}
void pop () {…}
Type top() {…}
…
}
stack<int> stk(150);