Abstract Data Types

• Data abstraction, or abstract data types, is a programming

methodology where one defines not only the data
structure to be used, but the processes to manipulate the
structure
– like process abstraction, ADTs can be supported directly by
programming languages
• To support it, there needs to be mechanisms for
– defining data structures
– encapsulation of data structures and their routines to manipulate
the structures into one unit
• by placing all definitions in one unit, it can be compiled at one time
– information hiding to protect the data structure from outside
interference or manipulation
• the data structure should only be accessible from code encapsulated with
it so that the structure is hidden and protected from the outside
• objects are one way to implement ADTs, but because objects have
additional properties, we defer discussion of them until the next chapter
 ADT Design Issues
• Encapsulation: it must be possible to define a unit
that contains a data structure and the subprograms
that access (manipulate) it
– design issues:
• will ADT access be restricted through pointers?
• can ADTs be parameterized (size and/or type)?
• Information hiding: controlling access to the data
structure through some form of interface so that it
cannot be directly manipulated by external code
– this is often done by using two sections of an ADT
definition
• public part (interface) constitutes those elements that can be accessed
externally (often the interface permits only access to subprograms and
constants)
• the private part, which remains secure because it is only accessible by
subprograms of the ADT itself
 Modula-2 ADTs
• Unit for encapsulation called a module
– modules can be combined to form libraries of ADTs
• To define a module:
– definition module: the interface containing a partial
or complete type definition (data structure) and the
subprogram headers and parameters
– implementation module: the portion of the data
structure that is to be hidden, along with all operation
subprograms
• If the complete type declaration is given in the definition
module, the type is “transparent” otherwise it is
“opaque”
– opaque types represent true ADTs and must be accessed
through pointers
• this restriction allows the ADT to be entirely hidden from user
programs since the user program need only define a pointer
 ADTs in Ada
• The encapsulation construct is the package
• Packages consist of two parts:
– specification package (the public or interface
part)
• – body package (the hidden or private part)
The two packages can be compiled
• separately
The specification package must include details of the data
– but onlyitself
structure if specification package is compiled
first
– to preserve information hiding, the data structure’s definition
the word private denoting that the following is hidden
can follow
• Ada offers three forms of ADTs
– those without information hiding, and thus are not true ADTs
– those that preserve information hiding by specifying that the data structure
is private
– those that specify that the data structure is limited private
• all ADTs have built-in operations for assignment and equality except for
limited private ADTs which have no built-in operations at all
 Example Part I
package Stack_Pack is The specification package
type Stack_Type is limited private; for a stack ADT – see the next
Max_Size : constant := 100; slide for the body package
function Empty(Stk : in Stack_Type) return Boolean;
procedure Push(Stk : in out Stack_Type; Element : in Integer);
procedure Pop(Stk : in out Stack_Type);
function Top(Stk : in Stack_Type) return Integer;
private The actual ADT
type List_Type is array (1..Max_Size) of Integer; definition must either
type Stack_Type is appear in the open
section (e.g., the public
record
part) or in the private
List : List_Type; section
Topsub : Integer range 0..Max_Size := 0;
end record;
end Stack_Pack; An alternative implementation to this approach is to
define a pointer in the private section of this package and
define the actual Stack_Type ADT in the body package.
This is discussed in more detail in the notes section of this
slide.
 Example Part II
with Ada.Text_IO; use Ada.Text_IO;
package body Stack_Pack is
function Empty(Stk : in Stack_Type) return Boolean is
begin
return Stk.Topsub = 0;
end Empty;
procedure Push(Stk : in out Stack_Type; Element : in Integer) is
begin
if Stk.Topsub >= Max_Size then
Put_Line(“ERROR – Stack overflow”);
else
Stk.Topsub := Stk.Topsub +1; Stk.List(Topsub):=Element;
end if;
end Push;
procedure Pop(Stk : in out Stack_Type) is
begin … end Pop;
function Top(Stk : in Stack_Type) return Integer is
begin … end Top; The rest of the implementation
end Stack_Pack; can be found on page 481
 C++ ADTs
• C++ offers two mechanisms for building data structures:
the struct and the class
– because the struct does not have a mechanism for information
hiding, it can only offer encapsulation, so for a true ADT, we
must use C++s object
– C++ classes contain both visible (public) and hidden (private)
components (as well as protected)
– C++ instances can be static, heap-dynamic and stack-
dynamic
• the lifetime of an instance ends when it reaches the end of the scope of
where it was declared
• a stack-dynamic object may have heap-dynamic data so that parts of the
object may continue even though the instant is deallocated
– we defer most of our discussion of objects in C++ to the next
chapter, but we will see an example next
 C++ Example
include <iostream.h> Unlike the Ada example, in C++, the
entire definition is encapsulated in one
lass stack {
location
private:
int Information hiding is preserved through
*stackPtr; the use of a private part with the interface
int max; being defined in the public part
public:int topPtr;
stack( ) { // Any methods that are to be defined in this
stackPtr = new int [100];
constructor class but not accessible outside of the
max = 99; class would also be defined in the private
section
topPtr = -1;
}
~stack( ) {delete [ ] stackPtr;} // destructor
void push(int number) {…} // details omitted
void pop( ) {…}
int top( ) {…}
int empty( ) {…}
 Java, C# and Ruby ADTs
• All three languages support ADTs through classes
– Java permits no stand-alone functions, only methods defined
in class definitions and unlike C++, referenced through
reference variables (pointers), therefore, in Java, every data
structure is an ADT
• it is up to the programmer as to whether information hiding is enforced
or not
– C# borrows from both C++ and Java but primarily from Java,
where all objects are heap dynamic, modifiers are private,
public, protected, but C# also offers
• internal and protected internal modifiers which are used for assemblies
(cross-platform objects), and methods that can serve as both accessors
and mutators (see the example on page 500-501)
– Ruby requires that all class variables be private, and all
methods default to being public (but the programmer can
change this)
• class variables do not have to be explicitly declared in Ruby, see the
example on page 502-04
• we look at Ruby in more detail in chapter 12
 Parameterized ADTs
• The ability to define an ADT
where the type and/or size is
In ADA:
specified generically so that a
specific version can be generic
generated later Max_Size : positive;
type Element_Type is private;
– a stack defined without … rest of ADT as before except that
specifying the element type Element_Type replaces Integer
(integer vs. string vs. float, etc) and Max_Size as a constant is
– a stack defined without a removed
restriction on the size of the stack
now we instantiate our ADT:
– Ada, C++, Java and C# all have
package Integer_Stack is new
this capability
• Generic_Stack(100,
The approach is to replace Integer);
type
the definition with a place
holder that is filled in later
 Parameterized ADTs Continued
• In C++, parameterized ADTs are implemented as
templated classes
– to change the stack class’ size, only change the constructor to
receive the size as a parameter, which is used to establish the
size of the array
– to change the stack’s type, the class is now defined as a
template using template <class Type> where Type is the
place-holder to be filled in by a specific type at run-
time
• In both Ada and C++, the parameterized ADT
definition is generated at compile-time
– the new statement signals that a new package should be
generated by the compiler
• in C++, if two definitions ask for the same type of ADT, only 1 set of
source code is generated, in Ada, the same source code is generated
twice!
• In Java and C#, parameterized ADTs are implemented
as generic classes (you should have covered this in 360
 Encapsulation Constructs
• For large programs, to avoid having to recompile all code when
one section changes
– code can be grouped into logically related chunks called encapsulations
• one approach is the nested subprogram, place logically related subprograms
inside of the subprograms that commonly call them, although this approach is
not available in C-languages since nesting of subprograms is not possible
• use a header file (C, C++) and place logically related functions in the same
file, distributing the program across multiple files
– C++ goes beyond simple header files and includes the notation of a friend which
has access to private definitions
•
Ada packages (which can be compiled separately) can include any number of
data and subprogram declarations so that they can contain interfaces for
multiple ADTs
• C# assemblies that can share code with other software written in the .NET
environment
• Each language has some technique for then using the named
encapsulation, sometimes called a namespace
– see the notes section of this slide for details in various
languages