Introduction to Abstract Data Types and Object-Oriented Programming

Tom Kelliher, CS18

Mar. 13, 1996

Modular Programming --- The Old Paradigm

• Control abstraction.
• How is data access controlled?
• What prohibits uncontrolled modifications?

Example: Controlled Access To An Employee Record

data.h:

#ifndef __DATA_H
#define __DATA_H

const int NAME_LEN = 30;

void GetName(char name[]);
int GetAge(void);
// ...

#endif

data.cc:

#include "data.h"

struct record
{
   char name[NAME_LEN];
   int age;
};

// static restricts scope to this file
static record employee = { "Kelliher, T. P.", 29 };  // and holding :-)

void GetName(char name[])
{
   strcpy(name, employee.name);
}

int GetAge(void)
{
   return employee.age;
}

main.cc:

#include <iostream.h>
#include "data.h"

int main()
{
   char name[NAME_LEN];

   GetName(name);
   cout << name << endl;
   cout << GetAge() << endl;

   return 0;
}

Can my client function use record as a type?

Is this a general, convenient-to-use solution?

Object Oriented Programming

Imagine:

1. Large team project to create, prove, develop product
2. Fiefdoms
3. Proof of concept prototype
4. Re-write for time/space efficiency before shipping

What can go wrong?

How can these problems be addressed?

• Procedural abstraction --- what, not how
• Information hiding
• Data abstraction

Abstract Data Types (ADTs)

A collection of data together with a set of operations on that data.

• Simula68
• Objects
• Object oriented programming

Interface/Implementation (data structure)

ADT examples:

• Integers
• Complex numbers
• The factorial of a number
• Matrices
• A chair
• An automobile
• A CD collection (classical vs. rock)

Example: Controlled Access To An Employee Record

data.h:

#ifndef __DATA_H
#define __DATA_H

const int NAME_LEN = 30;

class Record
{
 public:
   Record(const char inName[], int inAge);
   void GetName(char outName[]);
   int GetAge(void);
   // ...

 private:
   char name[NAME_LEN];
   int age;
};

#endif

data.cc:

#include <string.h>
#include "data.h"

Record::Record(const char inName[], int inAge)
{
   strcpy(name, inName);
   age = inAge;
}

void Record::GetName(char outName[])
{
   strcpy(outName, name);
}

int Record::GetAge(void)
{
   return age;
}

main.cc:

#include <iostream.h>
#include "data.h"

int main()
{
   Record r("Kelliher, T. P.", 29);
   Record s("Presley, E.", 39);
   char name[NAME_LEN];

   r.GetName(name);
   cout << name << endl;
   cout << r.GetAge() << endl;

   return 0;
}

The List ADT

A list is a collection of ordered items

• Head
• Tail
• Successor, predecessor
• Order
• Items
• Insertion/deletion semantics --- yield different ``lists:''
  • Anywhere --- list
  • Insert at tail, delete at head --- queue
  • Insert, delete at head --- stack

ADT List Operations

1. CreateList()
2. DestroyList()
3. ListIsEmpty()
4. ListLength()
5. ListInsert(newPosition, newItem, success)
6. ListDelete(position, success)
7. ListRetrieve(position, dataItem, success)

List Parameters???

Have we specified a data structure (implementation)?

Behavioral specification

Example:

List l;
dataItem d;

l.CreateList();
l.ListInsert(1, bread, success);
l.ListInsert(2, butter, success);
l.ListInsert(3, jam, success);
l.ListInsert(4, toaster, success);
l.ListRetrieve(2, d, success);
l.ListDelete(2, success);

Building on ADT List

Without knowledge of the implementation:

1. Write a display function
2. Write a multiple insert function
3. Delete all items and destroy entire list
4. Build other ADTs from ADT List:
   1. Sorted list
   2. queue
   3. stack

Example: ADT Sorted List Operations:

1. CreateSortedList
2. DestroySortedList
3. SortedListIsEmpty
4. SortedListLength
5. SortedListInsert(newItem, success)
6. SortedListDelete(item, success)
7. SortedListRetrieve(position, dataItem, success)
8. LocatePosition(anItem, position, success)

ADT Design Examples

1. Set
2. Matrix
3. String
4. Terry Winograd developed a program called SHRDLU that was intended to model a simple ``world'' consisting of children's blocks of various shapes and colors. Among other things, SHRDLU was designed to simulate manipulation of the blocks by picking them up and placing them elsewhere. Design ADT block operations.