Abstract Data Types and Encapsulation Concepts

abstraction

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

concept of abstraction

is fundamental in programming (and computer science)

process abstraction with subprograms

Nearly all programming languages support

data abstraction

Nearly all programming languages designed since 1980 support

abstract data type

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

hidden from the program units

type's definition

abstract data type condition:

The representation of objects of the type is — that use these objects, so the only operations possible are those provided in the —

single syntactic unit

abstract data type condition:

The representation of, and operations on, objects of the type are defined in a —

Reliability

Advantage of 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

• Program organization

• modifiability

• separate

Advantage of the second condition

• Provides a method of —

• aids — (everything associated with a data structure is together)

• — compilation

type definition

Language Requirements for ADTs

A syntactic unit in which to encapsulate the —

• A syntactic unit to define an ADT

• Built-in operations

• Common operations

• Parameterized ADTs

Design Issues (4)

• Assignment

• Comparison

Design Issues: 2 Built-in operations

• Accessors

• Constructors

• Destructors

Design Issues: 3 Common operations

packages

• Specification package

• Body package

Language Examples: Ada

The encapsulation construct is called —

• — (the interface)

• — (implementation of the entities named in the specification)

• private part

• no built-in operations

• pointer

• pointed-to structure's definition

Language Examples: Ada

Two ways for Information Hiding

• The representation of type appears in a part of the specification called the —

  • More restricted form with limited private types: objects of this type have —

• Define the ADT as a — and provide the — in the body package, whose entire contents are hidden from clients.

• C struct type and Simula 67 classes

• encapsulation device

• member functions

• class data members

• static, stack dynamic, or heap dynamic

Language Examples: C++

• Based on (2)

• The class is the —

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

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

• Instances can be (3)

• hidden entities

• interface entities

• inheritance

Information Hiding:

• Private clause for —

• Public clause for —

• Protected clause for —

Constructors

Language Examples: C++

—

• Name is the same as the class name

• Implicitly called when an instance is created

the objects)

• data members of instances

• heap-dynamic

• parameters

Constructors:

• initialize the — (they do not create the objects

• May also allocate storage if part of the object is —

• Can include — to provide parameterization of the objects

Destructors

• lifetime ends

• cleanup

Language Examples: C++

—

• Name is the class name, preceded by a tilde (~)

• Implicitly called when the object's —

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

Friend functions or classes -

Language Examples: C++

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

• Necessary in C++

• circularly linked list

• push

• put

• class Cell

Language Examples: C++

• The class List defines a —

  • —: add to the front

  • —: add at the back

• The — is used to form lists.

class cell

Language Examples: C++

class list

Java

• classes

• heap - reference variables

Language Examples: —

Similar to C++, except:

• All user-defined types are —

• All objects are allocated from the — and accessed through —

• access control modifiers (private or public) - clauses

Language Examples: Java

Similar to C++, except:

• Individual entities in classes have—, rather than —

• second scoping mechanism, package scope,

• visible

Language Examples: Java

Similar to C++, except:

• Java has a — which can be used in place of friends

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

C#

• internal and protected internal

• heap dynamic

Language Examples: —

• Based on C++ and Java

• Adds two access modifiers, —

• All class instances are —

C#

• Default constructors

• Garbage collection

• structs

Language Examples: C#

• — are available for all classes

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

• — are lightweight classes that do not support inheritance

• accessor methods (getter and setter)

• properties

Language Examples: C#

• Common solution to need for access to data members: —

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

Parameterized Abstract Data Types

—

• allow designing an ADT that can store any type elements

  • only an issue for static typed languages

• generic classes

• C++, Java 5.0, and C# 2005

Parameterized Abstract Data Types

• Also known as —

• (3) provide support for parameterized ADTs

• parameterized constructor functions

• Stack stk(150);

Parameterized ADTs in C++

• Classes can be somewhat generic by writing —

• A declaration of a stack object:

templated class

Stack myIntStack;

Parameterized ADTs in C++

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

Instantiation: —

Java 5.0

• classes

• collection types

• LinkedList and ArrayList

Parameterized Classes in —

• Generic parameters must be —

• Most common generic types are the —, such as —

• Eliminate the need to cast objects that are removed

• Eliminate the problem of having multiple types in a structure

• Users can define generic classes

• Generic collection classes cannot store primitives

• Indexing is not supported

• cast objects

• multiple types in a structure

Parameterized Classes in Java 5.0

• Eliminate the need to — that are removed

• Eliminate the problem of having —

• Users

• primitives

• Indexing

Parameterized Classes in Java 5.0

• — can define generic classes

• Generic collection classes cannot store —

• — 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 ();

Stack2 myStack = new Stack2 ();

Parameterized Classes in Java 5.0

Instantiation:

C# 2005

Parameterized Classes in —

• Similar to those of Java 5.0, except no • Predefined for Array, List, Stack, Queue, and Dictionary • Elements of parameterized structures can be accessed through indexing

C# 2005

• wildcard classes

Parameterized Classes in —

• Similar to those of Java 5.0, except no —

• Predefined for Array, List, Stack, Queue, and Dictionary

• Elements of parameterized structures can be accessed through indexing

• Array, List, Stack, Queue, and Dictionary

• indexing

Parameterized Classes in C#2005

• Predefined for (5)

• Elements of parameterized structures can be accessed through —

Encapsulation Constructs

• means of organization

• means of partial compilation

—

• Large programs have two special needs:

  • Some —, other than simply division into subprograms

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

• separately compiled

• encapsulation

Encapsulation Constructs

• Obvious solution: a grouping of subprograms that are logically related into a unit that can be — (compilation units)

• Such collections are called —

Nested Subprograms

• Python, JavaScript, and Ruby

• Organizing programs by — definitions inside the logically larger subprograms that use them

• are supported in (3)

C

• independently compiled

• header file

Encapsulation in —

• Files containing one or more subprograms can be —

• The interface is placed in a —

• linker

• pointers

Encapsulation in C

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

• Problem 2: the inherent problems with —

• #include preprocessor specification – used to include header files in applications

• #include preprocessor specification

Encapsulation in C

• — used to include header files in applications

C++

• header and code files

• encapsulation

• interface (prototypes)

Encapsulation in —

• Can define —, similar to those of C

• Or, classes can be used for —

• The class is used as the —

• member definitions

• Friends

Encapsulation in C++

• The — are defined in a separate file

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

C# Assemblies

• single dynamic link library or executable

• separately compiled

—

• A collection of files that appears to application programs to be a —

• Each file contains a module that can be —

• DLL

• internal

• internal member

C# Assemblies

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

• C# has an access modifier called —;

• an — of a class is visible to all classes in the assembly in which it appears

• global names

• logical groupings

Naming Encapsulations

• Large programs define many —; need a way to divide into —

naming encapsulation

• C++ Namespaces

• C#

A — is used to create a new scope for names

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

• — also includes namespaces

• Java Packages

• partial friends

• fully qualified name

Naming Encapsulations

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

• Clients of a package can use — or use the import declaration

• Ruby classes

• modules

• constants and methods

Naming Encapsulations

• — are name encapsulations, but Ruby also has —

• Typically encapsulate collections of —

• Modules cannot be instantiated or subclassed, and they cannot define variables

• Methods defined in a module must include the module’s name

• Access to the contents of a module is requested with the require method