ADT implementation

The specification of an ADT (Abstract Data Type) defines abstract data values and abstract operations for the user. Of course, the ADT must implemented in program code.

To implement an ADT, the programmer must do two things:

• choose an concrete data representation of the abstract data, using data type that already exist
• implement each of the allowabel operations in terms of program instructions

Our choice may be based on:

• time efficiency (the speed at which the algorithms execute)
• space efficiency (the economical use of memory space)
• simplicity and readability of the algorithms

Categories of ADT operations

The basic operations that are performed on an abstract data type fall into different categories. Such as:

Constructor: An operation that creates a new instance (variable) of an ADT. For example: creating a new instance of a list

Transformer: An operation that builds a new value of the ADT, given one or more previous values of the type. For example: inserting an item in a list or deleting an item from a list.

Observer: An operation that allows us to observe the state of an instance of an ADT without changing it. For example: checking if a list is empty or searching a list for a target.

Iterator: This is less common operation, it allows us to process all components in an instance of an ADT. For example: printing the items of a list.

Mutators (setters): Changing the value of an attribute

Accessors (getters): getting the value of an attribute


Reference: wikipedia, acm, answers

Previous post

Next post

Abstract Data Types

Data abstraction is important because:

• It allows uns to create data types not otherwise available in a programming language
• It allows us to produce off-the-shelf-software, pieces of software that can be used over and over again in different programs by any programmer

The primary tool for practicing data abstraction is the abstract data type(ADT), a new data type that is not built into the programming language, concentrating only on its logical properties and deferring the details of its implementation.

An abstract data type has both a specification (the what) and an implementation (the how) 

Properties of abstract data types

• Attributes
  
  • Java: fields
  • C++: data members or member variables
  
  
• Oprations
• Java: methods
• C++: member functions

Interaction with (usage of) an abstract data type is made through its interface or public interface

• Public attributes
• Public operations

TIP: public interface should be built around public operations. 

Example of informal specification

TYPE
    IntList
DOMAIN
    Each IntList value is a collection of up to 100 separate integer numbers
OPERATIONS
    Insert an item into the list
    Delete an item from the list
    Return the current length of the list
    Print the list

Notice the complete absense of implementation details


Reference: wikipedia, google books, thefreedictionary

Previous post

Next post

 

Abstraction

To cope with complexity, the human mind engages in abstraction, the act of separating the essential qualities of an idea or object from the details of how it works or is composed. With abstraction, we focus on the what, not the how. Abstraction can be performed from different viewpoints.

Examples:

• Words of a spoken language
• Metaphysical abstractions
• Objects in a classroom
• Mathematical abstractions
• Abstraction in programming

Fig: Abstraction in real life



Abstraction in Programming

Data types: An int-type represents an integer, a float-type represents a floating point number

Functions: absoluteValue

double absoluteValue(double d)
{
    if(d<0)
    {
        return -d;
    }
    else
    {
        return d;
    }
}

#include<cmath>
double absoluteValue(double d)
{
    return abs(d);
}

Both of the given example functions do the same thing. We don't need to know how they are doing. So we are focusing on what, not how.

Types of Abstraction

There are two important abstraction techniques:

• control abstraction
• data abstraction

Control abstraction is the separation of the logical properties of an action from its implementation.

Data abstraction is the separation of a data type's logical properties from its implementation.

Reference: wikipedia, artima, microsoft

Previous post

Next post