2 Abstract Data Types and Encapsulation Concepts

abstraction

An — is a view or representation of an entity that includes only the most significant attributes

programming (and computer science)

The concept of abstraction is fundamental in —

process abstraction with subprograms

Nearly all programming languages support —

data abstraction

Nearly all programming languages designed since 1980 support —

abstract data type

An — is a user-defined data type that satisfies the following two conditions

representation of objects of the type

ADT 1st Condition

The — is hidden from the program units that use these objects, so the only operations possible are those provided in the type's definition

declarations of the type and the protocols of the operations on objects of the type

ADT 2nd Condition

The — are contained in a single syntactic unit. Other program units are allowed to create variables of the defined type.

Reliability

Advantages the first condition

— 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

range of code and variables

Advantages the first condition

Reduces the — of which the programmer must be aware

Name conflicts

Advantages the first condition

— are less likely

program organization

Advantages the second condition

Provides a method of —

modifiability

Advantages the second condition

Aids — (everything associated with a data structure is together)

Separate

Advantages the second condition

— compilation

syntactic unit

Language Requirements for ADTs

A — in which to encapsulate the type definition

type names and subprogram headers

Language Requirements for ADTs

A method of making — visible to clients, while hiding actual definitions

primitive operations

Language Requirements for ADTs

Some — must be built into the language processor

parameterized

Design Issues

Can abstract types be —?

access controls

Design Issues

What — are provided?

specification of the type

Design Issues

Is the — physically separate from its implementation?

C++

Language Examples: —

Based on C struct type and Simula 67 classes

class

Language Examples: C++

The — is the encapsulation device

type

Language Examples: C++

A class is a —

member functions

Language Examples: C++

All of the class instances of a class share a single copy of the —

class data members

Language Examples: C++

Each instance of a class has its own copy of the —

static, stack dynamic, or heap dynamic

Language Examples: C++

Instances can be —

Private clause

Language Examples: C++

Information Hiding

— for hidden entities

Public clause

Language Examples: C++

Information Hiding

— for interface entities

Protected clause

Language Examples: C++

Information Hiding

— for inheritance

Constructors

Language Examples: C++

— Functions to initialize the data members of instances (they do not create the objects)

heap-dynamic

Language Examples: C++

Constructors:

May also allocate storage if part of the object is —

parameterization of the objects

Language Examples: C++

Constructors:

Can include parameters to provide —

Implicitly called

Language Examples: C++

Constructors:

— when an instance is created

explicitly called

Language Examples: C++

Constructors:

Can be

class name

Language Examples: C++

Constructors:

Name is the same as the —

Destructors

Language Examples: C++

— Functions to cleanup after an instance is destroyed; usually just to reclaim heap storage

object’s lifetime ends

Language Examples: C++

Destructors:

implicitly called when the —

explicitly called

Language Examples: C++

Destructors:

Can be —

tilde (~)

Language Examples: C++

Destructors:

Name is the class name, preceded by a —

Friend functions or classes

Language Examples: C++

— to provide access to private members to some unrelated units or functions

Necessary in C++

Java

Language Examples: —

Similar to C++, except

user-defined types

Language Examples: Java

All — are classes

reference variables

Language Examples: Java

All objects are allocated from the heap and accessed through —

access control modifiers (private or public)

Language Examples: Java

Individual entities in classes have —, rather than clauses

garbage collection

Language Examples: Java

Implicit — of all objects

package scope

Language Examples: Java

Java has a second scoping mechanism, —, which can be used in place of friends

visible throughout the package

Language Examples: Java

All entities in all classes in a package that do not have access control modifiers are —

C#

Language Examples: —

Based on C++ and Java

internal and protected internal

Language Examples: C#

Adds two access modifiers —

heap dynamic

Language Examples: C#

All class instances are —

Default constructors

Language Examples: C#

— are available for all classes

Garbage collection

Language Examples: C#

— is used for most heap objects, so destructors are rarely used

structs

Language Examples: C#

— are lightweight classes that do not support inheritance

accessor methods (getter and setter)

Language Examples: C#

Common solution to need for access to data members:

properties

Language Examples: C#

C# provides — as a way of implementing getters and setters without requiring explicit method calls

Parameterized Abstract Data Types

Also known as generic classes

static typed languages

Parameterized ADTs allow designing an ADT that can store any type elements (only an issue for —)

C++, Java 5.0, and C# 2005

— provide support for parameterized ADTs

C++

Parameterized ADTs in —

Classes can be somewhat generic by writing parameterized constructor functions

declaration

Parameterized ADTs in C++

A — of a stack object

templated class

Parameterized ADTs in C++

The stack element type can be parameterized by making the class a —

Instantiation

Parameterized ADTs in C++

—: Stack myIntStack;

Java 5.0

Parameterized Classes in —

Generic parameters must be classes

LinkedList and ArrayList

Parameterized Classes in Java 5.0

Most common generic types are the collection types, such as

cast objects

Parameterized Classes in Java 5.0

Eliminate the need to — that are removed

multiple types in a structure

Parameterized Classes in Java 5.0

Eliminate the problem of having —

Users

Parameterized Classes in Java 5.0

— can define generic classes

store primitives

Parameterized Classes in Java 5.0

Generic collection classes cannot

Indexing

Parameterized Classes in Java 5.0

— is not supported

myArray.add(0, 47); // Put an element with subscript 0 in it

Parameterized Classes in Java 5.0

Example of the use of a predefined generic class: ArrayList myArray = new ArrayList ();

Instantiation: Stack2 myStack = new Stack2 ();

Parameterized Classes in Java 5.0

Example

C# 2005

Parameterized Classes in —

Similar to those of Java 5.0, except no wildcard classes

Array, List, Stack, Queue, and Dictionary

Parameterized Classes in C# 2005

Predefined for

indexing

Parameterized Classes in C# 2005

Elements of parameterized structures can be accessed through

organization

Encapsulation Constructs

Large programs have two special needs:

Some means of —, other than simply division into subprograms

partial compilation

Encapsulation Constructs

Large programs have two special needs:

Some means of — (compilation units that are smaller than the whole program)

separately compiled (compilation units)

Encapsulation Constructs

Obvious solution: a grouping of subprograms that are logically related into a unit that can be

encapsulation

Encapsulation Constructs

Such collections are called

Nested Subprograms

Organizing programs by nesting subprogram definitions inside the logically larger subprograms that use them

Python, JavaScript, and Ruby

Nested subprograms are supported in —

Encapsulation in C

Files containing one or more subprograms can be independently compiled

header file

Encapsulation in C

The interface is placed in a

linker

Encapsulation in C

Problem 1: the — does not check types between a header and associated implementation

inherent problems with pointers

Encapsulation in C

Problem 2: the —

#include preprocessor specification

Encapsulation in C

– used to include header files in applications

Encapsulation in C++

Can define header and code files, similar to those of C

encapsulation

Encapsulation in C++

Or, classes can be used for —

interface (prototypes)

Encapsulation in C++

The class is used as the —

separate file

Encapsulation in C++

The member definitions are defined in a —

Friends

Encapsulation in C++

— provide a way to grant access to private members of a class

C# Assemblies

A collection of files that appears to application programs to be a single dynamic link library or executable

separately compiled

C# Assemblies

Each file contains a module that can be —

DLL

C# Assemblies

A — is a collection of classes and methods that are individually linked to an executing program

internal

C# Assemblies

C# has an access modifier called —; an —member of a class is visible to all classes in the assembly in which it appears

naming encapsulation

Large programs define many global names; need a way to divide into logical groupings.

A — is used to create a new scope for names

C++ Namespaces

C#

– Can place each library in its own namespace and qualify names used outside with the namespace

— also includes namespaces

Java Packages

partial friends

Naming Encapsulations

— Packages can contain more than one class definition; classes in a package are —

import declaration

Naming Encapsulations: Java Packages

Clients of a package can use fully qualified name or use the —

modules

Naming Encapsulations

Ruby classes are name encapsulations, but Ruby also has

constants and methods

Naming Encapsulations: Ruby Modules

Typically encapsulate collections of —

Modules

Naming Encapsulations: Ruby Modules

cannot be instantiated or subclassed, and they cannot define variables