Chapter 11: Abstract Data Types and Encapsulation

Chapter 11: Abstract Data Types and Encapsulation Concepts

11.1 Topics

  • The Concept of Abstraction

  • Introduction to Data Abstraction

  • Design Issues for Abstract Data Types

  • Language Examples

  • Parameterized Abstract Data Types

  • Encapsulation Constructs

  • Naming Encapsulations

11.2 The Concept of Abstraction

  • Definition of Abstraction: An abstraction is a view or representation of an entity that includes only the most significant attributes.

  • Importance: The concept of abstraction is fundamental in programming and computer science.

  • Support Across Languages:

    • Nearly all programming languages support process abstraction with subprograms.

    • Nearly all programming languages designed after 1980 support data abstraction.

11.3 Introduction to Data Abstraction

  • Definition: An abstract data type (ADT) is a user-defined data type that satisfies the following conditions:

    • Condition 1: The representation of objects of the type is hidden from the program units that use these objects, meaning only the operations provided in the type's definition are possible.

    • Condition 2: 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 can create variables of the type.

11.4 Advantages of Data Abstraction

  • Advantages of the First Condition:

    • Reliability: Hiding data representations prevents user code from directly accessing objects of the type or depending on the representation, allowing the representation to change without affecting user code.

    • Reduced Complexity: Reduces the range of code and variables that programmers need to be aware of.

    • Conflict Reduction: Decreases the likelihood of name conflicts.

  • Advantages of the Second Condition:

    • Program Organization: Provides a method of organization for programs.

    • Modification: Aids in program modifiability since everything associated with a data type is encapsulated.

11.5 Language Requirements for ADTs

  • A syntactic unit is needed to encapsulate the type definition.

  • A method should be available to make type names and subprogram headers visible to clients while hiding actual definitions.

  • Some primitive operations must be built into the language processor.

11.6 Design Issues

  • Can abstract types be parameterized?

  • What access controls are provided?

  • Is the specification of the type physically separate from its implementation?

11.7 Language Examples: C++

  • Overview: C++ is based on the C struct type and Simula 67 classes.

  • Encapsulation: The class is the encapsulation device; a class is considered a type.

  • Function Sharing: All instances of a class share a single copy of member functions, while each instance has its own copy of data members.

11.8 C++ Class Structure

  • Class Instances: 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 (referenced in Chapter 12).

  • Constructors:

    • Functions that initialize data members of instances (do not create objects).

    • May also allocate storage if part of the object is heap-dynamic, can include parameters for parameterization.

    • Implicitly called when an instance is created and can be explicitly called. The name is the same as the class name.

  • Destructors:

    • Functions that clean up after an instance is destroyed, usually for reclaiming heap storage.

    • Implicitly called when the object’s lifetime ends and can also be explicitly called.

    • Name format: class name preceded by a tilde (~).

11.9 C++ Example: Stack Class

  • Class Definition:

class Stack {
 private:
   int *stackPtr, maxLen, topPtr;
 public:
   Stack() {
      stackPtr = new int[100];
      maxLen = 99;
      topPtr = -1;
   };
   ~Stack() {
      delete[] stackPtr;
   };
   void push(int number) {
      if (topPtr == maxLen)
         cerr << "Error in push - stack is full\n";
      else
         stackPtr[++topPtr] = number;
   };
   void pop() {...};
   int top() {...};
   int empty() {...};
};

  • Header File:

// Stack.h - the header file for the Stack class
#include <iostream.h>
class Stack {
 private:
   int *stackPtr;
   int maxLen;
   int topPtr;
 public:
   Stack();  // Constructor
   ~Stack(); // Destructor
   void push(int);
   void pop();
   int top();
   int empty();
};

  • Code File:

// Stack.cpp - the implementation file for the Stack class
#include <iostream.h>
#include "Stack.h"
using std::cout;
Stack::Stack() {
   stackPtr = new int[100];
   maxLen = 99;
   topPtr = -1;
}
Stack::~Stack() {
delete[] stackPtr;
};
void Stack::push(int number) {
   if (topPtr == maxLen)
      cerr << "Error in push--stack is full\n";
   else
      stackPtr[++topPtr] = number;
}
...

11.10 Friend Functions and Classes in C++

  • Friend functions or classes are used to provide access to private members to some unrelated units or functions.

  • Friend access is necessary in C++.

11.11 Language Examples: Java

  • Comparison to C++: Java is similar to C++, with some differences:

    • All user-defined types are classes.

    • All objects are allocated from the heap and accessed through reference variables.

    • Classes include access control modifiers (private or public) rather than clauses.

    • Implicit garbage collection of all objects.

    • Additional scoping mechanism: package scope, which works instead of friends.

11.12 Java Example: StackClass

  • Class Definition:

class StackClass {
 private int [] stackRef;
 private int maxLen, topIndex;
 public StackClass() {
   stackRef = new int[100];
   maxLen = 99;
   topIndex = -1;
};
 public void push(int num) {...};
 public void pop() {...};
 public int top() {...};
 public boolean empty() {...};
};

11.13 Language Examples: C#

  • Based on C++ and Java, with two additional access modifiers: internal and protected internal.

  • All class instances are heap dynamic.

  • Default constructors are available for all classes.

  • Garbage collection is used for most heap objects, making destructors rarely needed.

  • Structs are lightweight classes.

  • Common solution for accessing data members involves accessor methods (getter and setter).

    • C# provides properties for implementing getters and setters without requiring explicit method calls.

11.14 C# Property Example

  • Property Definition:

public class Weather {
 public int DegreeDays {
   get { return degreeDays; }
   set {
      if (value < 0 || value > 30)
         Console.WriteLine("Value is out of range: {0}", value);
      else
         degreeDays = value;
   }
 }
 private int degreeDays;
}

  • Usage:

Weather w = new Weather();
int degreeDaysToday, oldDegreeDays;
w.DegreeDays = degreeDaysToday;
oldDegreeDays = w.DegreeDays;

11.15 Abstract Data Types in Ruby

  • Encapsulation: Ruby provides classes as the encapsulation construct.

  • Variable Naming Conventions:

    • Local variables have “normal” names.

    • Instance variables begin with an “@” sign.

    • Class variable names start with two “@” signs.

  • Method Definition: Instance methods follow the syntax of Ruby functions (def ... end).

  • Constructor Naming: Constructors are named 'initialize' and are implicitly called when 'new' is called. If multiple constructors are needed, they must have different names and explicitly call 'new'.

  • Access Modifiers: Class members can be marked private or public (default is public).

11.16 Ruby Example: StackClass

  • Class Definition:

class StackClass {
 def initialize
   @stackRef = Array.new
   @maxLen = 100
   @topIndex = -1
 end
 def push(number)
   if @topIndex == @maxLen
     puts "Error in push – stack is full"
   else
     @topIndex += 1
     @stackRef[@topIndex] = number
   end
 end
 def pop ... end
 def top ... end
 def empty ... end
end

11.17 Parameterized Abstract Data Types

  • Definition: Parameterized ADTs allow designing an ADT that can store any type of elements, particularly important for statically typed languages.

  • Also Known As: Generic classes.

  • Support: Languages like C++, Java 5.0, and C# 2005 provide support for parameterized ADTs.

11.18 Parameterized ADTs in C++

  • Generic Class Definition:

template <class Type> class Stack {
 private:
   Type *stackPtr;
   const int maxLen;
   int topPtr;
 public:
   Stack() {
      stackPtr = new Type[100];
      maxLen = 99;
      topPtr = -1;
   }
   Stack(int size) {
      stackPtr = new Type[size];
      maxLen = size - 1;
      topPtr = -1;
   }
 ...
};

  • Instantiation:

Stack<int> myIntStack;

11.19 Parameterized Classes in Java 5.0

  • Generic Parameters: Must be classes.

  • Common Generic Types: Collection types such as LinkedList and ArrayList facilitate the elimination of casting objects when removed and the problem of multiple types in structures.

  • Limitations: Generic collection classes cannot store primitives and indexing is not supported.

11.20 Java Example: Stack2

  • Class Definition:

import java.util.*;
public class Stack2<T> {
 private ArrayList<T> stackRef;
 private int maxLen;
 public Stack2() {
   stackRef = new ArrayList<T>();
   maxLen = 99;
 }
 public void push(T newValue) {
   if (stackRef.size() == maxLen)
      System.out.println("Error in push – stack is full");
   else
      stackRef.add(newValue);
   ...
}
};

  • Instantiation:

Stack2<String> myStack = new Stack2<String>();

11.21 Parameterized Classes in C# 2005

  • Similarities to Java: Similar to Java 5.0, except no wildcard classes are provided.

  • Predefined Classes: Predefined for Array, List, Stack, Queue, and Dictionary.

  • Accessing Elements: Elements of parameterized structures can be accessed through indexing.

11.22 Encapsulation Constructs

  • Need for Encapsulation:

    • Large programs necessitate organization beyond simple division into subprograms.

    • They require partial compilation (compilation units smaller than the whole program).

  • Solution: A grouping of logically related subprograms into a unit that can be compiled separately, referred to as encapsulation.

11.23 Nested Subprograms

  • Definition: Organizing programs by nesting subprogram definitions within the logically larger subprograms that utilize them.

  • Support: Nested subprograms are supported in languages such as Python, JavaScript, and Ruby.

11.24 Encapsulation in C

  • File Compilation: In C, files containing one or more subprograms can be independently compiled.

  • Header Files: The interface is placed in a header file.

  • Problems:

    1. The linker does not check types between a header and associated implementation.

    2. Inherent issues with pointers.

11.25 Encapsulation in C++

  • Definition: C++ can define header and code files similar to those of C.

  • Class Use for Encapsulation: Classes can be used as interfaces (prototypes), with member definitions in a separate file.

  • Access through Friends: Friends provide a way to grant access to the private members of a class.

11.26 C# Assemblies

  • Definition: Assemblies are collections of files appearing to application programs as a single dynamic link library (DLL) or executable.

  • Compilation: Each file contains a module that can be compiled separately.

  • DLL Nature: A DLL consists of a collection of classes and methods individually linked to an executing program.

11.27 Naming Encapsulations

  • Definition: Large programs define many global names; a means to logically group them is necessary.

  • Purpose: A naming encapsulation creates a new scope for names.

  • C++ Namespaces:

    • Each library can be placed within its own namespace, qualifying names used outside with the namespace.

    • C# also includes namespaces.

11.28 Java Packages

  • Definition: Packages can contain multiple class definitions; classes in a package are partial friends.

  • Access: Clients of a package can use either fully qualified names or employ the import declaration.

11.29 Summary

  • Milestone: The concept of ADTs and their use in program design was a significant milestone in the development of programming languages.

  • Primary Features of ADTs: The two main features are the packaging of data with their associated operations and information hiding.

  • Language Support:

    • Ada provides packages that simulate ADTs.

    • C++ utilizes classes for data abstraction.

    • Java's data abstraction is similar to that of C++.

    • C++, Java 5.0, and C# 2005 support parameterized ADTs.

    • C++, C#, Java, and Ruby provide naming mechanisms to manage encapsulations.