Transcript Chapter 1

Chapter 11
Abstract Data
Types and
Encapsulation
Concepts
ISBN 0-321-49362-1
Chapter 11 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
Copyright © 2007 Addison-Wesley. All rights reserved.
1-2
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
Copyright © 2007 Addison-Wesley. All rights reserved.
1-3
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.
Copyright © 2007 Addison-Wesley. All rights reserved.
1-4
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
Copyright © 2007 Addison-Wesley. All rights reserved.
1-5
Data Abstraction
• Interface is public
• Implementation is private
Copyright © 2007 Addison-Wesley. All rights reserved.
1-6
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
Copyright © 2007 Addison-Wesley. All rights reserved.
1-7
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
Copyright © 2007 Addison-Wesley. All rights reserved.
1-8
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
Copyright © 2007 Addison-Wesley. All rights reserved.
1-9
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 (~)
Copyright © 2007 Addison-Wesley. All rights reserved.
1-10
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 () {…};
}
void main () {
int topOne;
stack stk;
stk.push(42);
stk.push(17);
topOne =
stk.top();
stk.pop();
..
}
Stack
dynamic
Heap
dynamic
Copyright © 2007 Addison-Wesley. All rights reserved.
1-11
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.
Copyright © 2007 Addison-Wesley. All rights reserved.
1-12
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
Copyright © 2007 Addison-Wesley. All rights reserved.
1-13
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 () {…};
}
Copyright © 2007 Addison-Wesley. All rights reserved.
1-14
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
Copyright © 2007 Addison-Wesley. All rights reserved.
1-15
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);
Copyright © 2007 Addison-Wesley. All rights reserved.
1-16
Generics in Java
• Pre V5.0
ArrayList alist = new ArrayList();
myArray.add(0, new Integer(47));
Integer myInt = (Integer) myArray.get(0);
Post V5.0
ArrayList<Integer> alist = new ArrayList<Integer>();
alist.add(0, 47);
Integer myInt = myArray.get(0);
alist.add(1, 55.5); ---- Compile time error
Copyright © 2007 Addison-Wesley. All rights reserved.
1-17
Generics in Java
public class StackClass <T> {
private T [] stackRef;
private int topIndex;
public StackClass(int size) { // a constructor
stackRef = (T[]) new Object[size];
topIndex = -1;
};
public void push (T value) {…};
public void pop () {…};
public T top () {…};
public boolean empty () {…};
}
…
StackClass<Integer> intStack =
new StackClass<Integer> (100);
Copyright © 2007 Addison-Wesley. All rights reserved.
1-18
Encapsulation Constructs
• Large programs have two special needs:
– Managing complexity through some means of
organization, other than simple division into
subprograms.
– Managing the processing cost of re-compilation
through some means of partial compilation
• Solution - Encapsulations
– An encapsulation is a syntactic container for
logically related software resources, such as
subprograms and ADTs, each of which can be
separately compiled.
Copyright © 2007 Addison-Wesley. All rights reserved.
1-19
Nested Subprograms
• Organizing programs by nesting
subprogram definitions inside the logically
larger subprograms that use them is not a
primary organizing encapsulation
construct.
–
Nested subprograms are supported in Ada,
Ruby, Python and Fortran 95
Copyright © 2007 Addison-Wesley. All rights reserved.
1-20
Encapsulation in C
• Files containing one or more subprograms can be
independently compiled.
• The implementation is separated from the interface by
– Placing the interface in a header file which is provided to the
client in source form.
– Placing the implementations in a library file which is provided to
the client in binary form.
• The #include preprocessor specification is used by the
client so that references to library code an be type checked.
• This approach does have security problems rooted in the fact
that the client has direct access to the source header file.
–
Example:
•
•
•
•
–
A client copies the header file directly vs. using the #include.
The implementation changes the data type of variable x from int to float.
The client code is compiled with x as a float.
The linker does not detect this error.
Places the responsibility of making sure that both the header and the
implementation files are up-to-date upon the client. (via the make utility)
Copyright © 2007 Addison-Wesley. All rights reserved.
1-21
Encapsulation in C++ and Ada
• C++
– Similar to C in that header files are used to
provide the interface to the resources of the
encapsulation.
– Uses friend functions to allow access to private
members of the friend class where they are
declared to be friends. Can also have friend
classes
• Ada
–
Uses packages which can include any number
of data and subprogram declarations
•
Can be compiled separately
Copyright © 2007 Addison-Wesley. All rights reserved.
1-22
Naming Encapsulations
• Dealing with name collisions through
scope.
– Small scale: use of local scope in methods.
– Large scale: many global names are declared by
different program units.
• a way is needed to divide these names into logical
groupings.
• A naming encapsulation is used to create scopes for
names.
Copyright © 2007 Addison-Wesley. All rights reserved.
1-23
Naming Encapsulations
• C++ uses Namespaces
– Each library can be placed in its own namespace.
– The client qualifies each name used with the name of
namespace if outside its own namespace.
– Example:
• Place all of the declarations in a namespace block as in
– MyStack { //stack declarations … }
• To refer to a name declared in the header file the scope
resolution operator is used as in
– MyStack::topPtr
• Or the using directive can be used as in
– using MyStack:: topPtr; , which makes topPtr visible.
– using namespace MyStack; which makes all visible.
– Usage can then be p = topPtr;
Copyright © 2007 Addison-Wesley. All rights reserved.
1-24
Naming Encapsulations (continued)
• Java Packages
– Packages can contain more than one class
definition.
– Clients of a package can use fully qualified
name or use the import declaration.
Copyright © 2007 Addison-Wesley. All rights reserved.
1-25
Summary
• The concept of ADTs and their use in program
design was a milestone in the development of
languages
• Two primary features of ADTs are the packaging of
data with their associated operations and
information hiding
• Ada provides packages that simulate ADTs
• C++ data abstraction is provided by classes
• Java’s data abstraction is similar to C++
• Ada and C++ allow parameterized ADTs
• C++, C#, Java, and Ada provide naming
encapsulation
Copyright © 2007 Addison-Wesley. All rights reserved.
1-26