Session 8: Abstract Data Types

A. 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, and designed since 1980, support data abstraction.

B. Introduction

Data abstraction refers to, providing only essential information to the outside world and hiding their background details, i.e., to represent the needed information in program without presenting the details. An ADT (Abstract Data Types in extend) may be implemented by specific data types or data structures, in many ways and in many programming languages; or described in a formal specification language. An ADT is a user-defined data type that satisfies the following two conditions:

• 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
• 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.
• Advantages of Data Abstraction
• Advantages of the first 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
  • Reduces range of code and variables of which the programmer must be aware of
  • Name conflicts are less likely to happen
• Advantages of the second condition
  • Provides a method of program organization
  • Aids modifiability (everything associated with a data structure is together)
  • Separate compilation

Languange 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 dynamic

• Information hiding :

• Private clause for hidden entities
• Public clause for interface entities
• Protected clause for inheritance
• 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 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 (~)
• Friend functions or classes – to provide access to private members to some unrelated units or functions (necessary in C++)

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 number) {

if (topSub == maxLen)

cerr << ″Error in push – stack is full\n″;

else stackPtr[++topSub] = number;

};

void pop () {…};

int top () {…};

int empty () {…};

}

C. Parameterized ADTs (C++)

Classes can be somewhat generic by writing parameterized constructor functions

Stack (int size)

{

stk_ptr = new int [size];

max_len = size – 1;

top = -1;

};

 

– A declaration of a stack object : Stack stk(150);

 

The stack element type can be parameterized by making the class a templated class
template <class Type>
class Stack

{
private:
Type *stackPtr;
const int maxLen;
int topPtr;
public:
Stack() {  // Constructor for 100 elements
stackPtr = new Type[100];
maxLen = 99;
topPtr = -1;
}

Stack(int size) {  // Constructor for a given number

stackPtr = new Type[size];

maxLen = size – 1;

topSub = -1;

}
…
}

– Instantiation : Stack<int> myIntStack;

 

D. Encapsulation Constructs

Large programs have two special needs:

• Some means of organization, other than simply division into subprograms
• Some means of partial compilation (compilation units that are smaller than the whole program)

Obvious solution: a grouping of subprograms that are logically related into a unit that can be separately compiled (compilation units). Such collections are called encapsulation.

 

E. Encapsulation in C++

Encapsulation in C++ can define header and code files, similar to those of C, or, classes can be used for encapsulation. The class is used as the interface (prototypes), and the member definitions are defined in a separate file. Friends provide a way to grant access to private members of a class.

• Naming Encapsulations
  • Large programs define many global names; need a way to divide into logical groupings
  • A naming encapsulation is used to create a new scope for names
  • C++ Namespaces
  • Can place each library in its own namespace and qualify names used outside with the namespace

F. Typical operations

Some operations that are often specified for ADTs (possibly under other names) are :

• compare(s, t), that tests whether two instances’ states are equivalent in some sense;
• hash(s), that computes some standard hash function from the instance’s state;
• print(s) or show(s), that produces a human-readable representation of the instance’s state.

In imperative-style ADT definitions, one often finds also

• create(), that yields a new instance of the ADT;
• initialize(s), that prepares a newly created instance s for further operations, or resets it to some “initial state”;
• copy(s, t), that puts instance s in a state equivalent to that of t;
• clone(t), that performs s ← create(), copy(s, t), and returns s;
• free(s) or destroy(s), that reclaims the memory and other resources used by s.

 

Data Abstraction Example :

Any C++ program where you implement a class with public and private members is an example of data abstraction.

 

#include <iostream>

using namespace std;

 

class Adder {

public:

// constructor

Adder(int i = 0) {

total = i;

}

 

// interface to outside world

void addNum(int number) {

total += number;

}

 

// interface to outside world

int getTotal() {

return total;

};

 

private:

// hidden data from outside world

int total;

};

 

int main( ) {

Adder a;

 

a.addNum(10);

a.addNum(20);

a.addNum(30);

 

cout << “Total ” << a.getTotal() <<endl;

return 0;

}

When the above code is compiled and executed, it produces the following result:

Total 60

Source(s) :

https://www.tutorialspoint.com/cplusplus/cpp_data_abstraction.htm

https://en.wikipedia.org/wiki/Abstract_data_type

Slide Binus Maya