CS245 - Comp Sci II

Chapter 11 - Classes in the Abstract

OBJECTIVES

• Introduce the notion of an abstract data type (ADT)
• Provide and review examples of two implementations of a list ADT.
• Discuss the memory and processing trade-offs between the two list implementations.
• Discuss stacks and queues as ADTs.

11.1 Abstract Data Types: Bears, Cats, and Dogs

An abstract data type(ADT) is defined by describing 1. the logical structure of the information represented by an instance of the type 2. the operations performed on the information

Aspect I: Structures

List - either empty or consists of a finite collection of elements, arranged so that each element has at most one element following it and at most one element preceding it

Stack - a LIFO list
Queue - a FIFO list
Tree - each element may have more than one sucessor
Graph - each element may have more than one sucessor and more than one predecessor
Rings - lists with first and last element linked
Bags - collections with no structure
Tables - each element of one collection is associated with a single element of another collection

Aspect II: Operations

List - create, insert, delete, find, destroy
Stack - create, push, pop, destroy

ADTs and OOP

11.2 The List ADT - Array Implementation

If all of the elements are of the same type, we have a homogeneous list, otherwise we have a heterogeneous list

Some general categories of ADT operations are:

• Construction/Initialization: used to create and set initial values for the ADT.
• Destruction: free the space used by instances of the ADT.
• Modification: alter some of the ADT information.
• Access: allow inspection of the internal information of the ADT.
• Assignment / Copy operators
• Input / Output operators

Specific operations for List:

• Move the current position one position
• Move the current position to the head or tail of the list
• Retrieve a copy of the element at the current position
• Return the length of the list
• Update the element at the current position
• Insert / Remove the element at the current position

Declaring the List Class

List of ???? - use parameterized class

template <class T> 
   class TList 
   { }

where T is now a place-holder for any type:

void Update(T x);

Tlist<T>& operator= (const Tlist<T>& lst);

and we would reference the TList class by TList<int> or Tlist<Fraction>

example of a generic swap function:

template<class SWAP_TYPE> void Swap(SWAP_TYPE& a, SWAP_TYPE& b)
{
   SWAP_TYPE temp = a;
   a = b;
   b = temp;
}

Example of Array Implementation

//---------- ALISTS.H ----------

#ifndef ALISTS_H
#define ALISTS_H
#include <iostream.h>

//-------------------------- TList
// Declaration of an array implementation of list of values of parametrized type.
// All insertion and deletion is done at the current position in the list.

template <class T>class TList
{
   friend ostream& operator<< (ostream& os, TList<T> l);
   public:
       TList();					// Construct an empty list.
       TList(const TList<T>& l);		             // copy constructor
       ~TList();				            // destructor

       TList<T>& operator= (const TList<T>& l);	// assignment overload

       void Insert(T x);				// Insert x at current position
       void Remove();				// Delete the node at the current position

       void Head(); 				// Move current location to the head
       void Tail(); 				// Move current location to the tail
       TList<T>& operator++ (int);		// Move current to next position (postfix)
       TList<T>& operator-- (int);		// Move current to prior position (postfix)

       T Retrieve() const;			// Return the element at the current position
       void Update(T x);			// Store x in current location

       int Length();				// Return the size of the list
    private:
       T	*value;				// pointer to the array
        int	size,				// number of elements in the list (<= max)
              max,			// size of the array
              current;		// current index in the array (0 <=# current < size)
       void Grow();				// Grow the array to twice its size
};
#endif

Defining the List Class

//---------- ALISTS.CPP ----------
#include <stdlib.h>		// for exit
#include "ALISTS.H"

//----------------- Definition of TList member functions and friends

template <class T> ostream& operator<< (ostream& os, TList<T> l)
// Display an entire TList, from first position to last.
{
    for (int i = 0; i < size; i++)
    os << value[i] << '\t';
    return os;
}
template<class T> TList<T>::TList()
// Default constructor.  Builds an empty list, using an array of 10 elements.
{	
    size = 0;
    max = 10;
    current = 0;
    value = new T[max]; 
}

template<class T> TList::TList(const TList& l)
// copy constructor
{
    size = l.size;
    max = l.max;
    current = l.current;

    value = new T[max];
    for (int i = 0; i < size; i++)
       value[i] = l.value[i];	
}

template<class T> TList::~TList()
// Delete all nodes in the List.
{
   delete []value;	 // We need the brackets because T might have its own destructor.
   size = 0;
   max = 0;
   current = 0;
}

template<class T> TList& TList::operator= (const TList& l)
// assignment overload
{
   size = l.size;
   max = l.max;
   current = l.current;

// Kill the old array and construct a new one, filling it with l's values
   delete []value;
   value = new T[max];
   for (int i = 0; i < size; i++)
      value[i] = l.value[i];
   return *this;	
}

template<class T> void TList::Insert(T x)
// Insert x at the current position.
{
   if (size == max)	// No room in the array, so make it larger.
      Grow();
   for (int i = size - 1; i >= current; i--)
      value[i + 1] = value[i];
   value[current] = x;
   size++;
}

template<class T> void TList::Remove()
// Delete the node at the current position.
// If the list is empty, display a warning, but continue working.
{
    if (size > 0)
   {
       for (int i = current; i < size - 1; i++)
           value[i] = value[i + 1];
       size--;
   }
   else
        cerr << "Attempt to Remove an element from an empty list" << endl;
}

template<class T> void TList::Head()
// Move current location to the head.
{ current = 0;}

template<class T> void TList::Tail()
// Move current location to the tail.
{
    if (size > 0)		// We don't have to do anything if the list is empty.
       current = size - 1;
}

template<class T> TList& TList::operator++ (int)
// Move current location to next node (postfix operator).
// Do nothing if current is at the tail of the list.
{
    if (current < size - 1)
        current++;
    return *this;
}

template<class T> TList& TList::operator-- (int)
// Move current location to previous node (postfix operator).
// Do nothing if current is at the head of the list
{
    if (current > 0)
        current--;
    return *this;
}

template<class T> T TList::Retrieve() const	
// Return the element at the current position.
// Quit the program if the list is empty, since we can't return anything.
{
    if (size > 0)
       return value[current];
   else
   {
       cerr << "Cannot Return an element from an empty list";
       exit(1);
   }
}

template<class T> void TList::Update(T x)
// Store x in current location.
// Quit the program if the list is empty.
{
    if (size > 0)
       value[current] = x;
    else
    {
       cerr << "Cannot Update an element in an empty list";
       exit(1);
    }
}

template<class T> int TList::Length()
// Return the number of elements in the list.
{ return size;}

template<class T> void TList::Grow()
// PRIVATE.  Double the size of the array
{
    max *= 2;
    T* newValue = new T[max];
    for (int i = 0; i < size; i++)
        newValue[i] = value[i];
    delete []value;
    value = newValue;
}

11.3 The List ADT - Linked List Implementation

template <class T>
class Node
{ public:
     Node() {next = NULL;}
     data value;
     Node* next;
};

//---------- LLISTS.CPP ----------

#include <stdlib.h>		// for exit
#include "LLISTS.H"

//----------------- Definition of TList member functions and friends
template<class T> ostream& operator<< (ostream& os, TList<T> l)
// Display an entire TList, from first position to last.
{
    Node<T>* p = l.first;
    while (p)
    {
         os << p->value << '\t';
         p = p->next;
     }
     return os;
}

template<class T> TList<T>::TList()
// Default constructor.  Builds an empty list.
{	first = current = last = NULL; size = 0; }

template<class T> TList<T>::TList(const TList<T>& l)
// copy constructor
{
    Node<T>	*lptr = l.first,			// tracks through the argument list
    *nptr;			// tracks through this list

    if (lptr == NULL)		
    {	current = first = last = NULL; size = 0;}
    else
    {
//---- Construct the first node in the list.
         nptr = new Node<T>;
         nptr->value = lptr->value;
         if (lptr == l.current)
               current = nptr;
         first = nptr;
         lptr = lptr->next;

//---- Track through the remainder of the list, copying nodes.
        while (lptr)
        {
            nptr->next = new Node<T>;
            nptr = nptr->next;
            if (lptr == l.current)
                 current = nptr;
           nptr->value = lptr->value;
           lptr = lptr->next;
        }
        nptr->next = NULL;
        last = nptr;
        size = l.size;
   }	
}

template<class T> TList<T>::~TList()
// Delete all nodes in the List.
{
    Node<T>* nptr = first;
    current = first;
    while (current)
    {
         current = current->next;
         delete nptr;
         nptr = current;
    }
    first = current = last = NULL;
    size = 0;
}

template<class T> TList<T>& TList<T>::operator= (const TList<T>& l)
// assignment overload
{	
//--------- First, destroy the existing list.
    Node<T>* nptr = first;
    current = first;
    while (current)
    {
         current = current->next;
         delete nptr;
         nptr = current;
    }

//--------- Now build the new list
    Node<T>	*lptr = l.first;	// tracks through the argument list

    if (lptr == NULL)		
    {	current = first = last = NULL; size = 0;}
    else
    {
//---- Construct the first node in the list.
         nptr = new Node<T>;
         nptr->value = lptr->value;
         if (lptr == l.current)
                current = nptr;
         first = nptr;
         lptr = lptr->next;

//---- Track through the remainder of the list, copying nodes.
        while (lptr)
        {
             nptr->next = new Node<T>;
             nptr = nptr->next;
             if (lptr == l.current)
                 current = nptr;
             nptr->value = lptr->value;
             lptr = lptr->next;
         }
         nptr->next = NULL;
         last = nptr;
         size = l.size;
     }
     return *this;	
}

template<class T> void TList<T>::Insert(T x)
// Insert x at the current position.
{
    Node<T>* nptr = new Node<T>;
    if (current == NULL)				// List is empty.
    {
        nptr->value = x;
        nptr->next = NULL;
        current = first = last = nptr;
    }
    else						// List is nonempty.
    {
        nptr->value = current->value;
        nptr->next = current->next;
        current->value = x;
        current->next = nptr;
        if (current == last)
            last = nptr;
   }
   size++;
}

template<class T> void TList<T>::Remove()
// Delete the node at the current position.
{
           //You fill it in!!!
}

template<class T> void TList<T>::Head()
// Move current location to the head.
{ current = first;}

template<class T> void TList<T>::Tail()
// Move current location to the tail.
{ current = last;}

template<class T> TList<T>& TList<T>::operator++ (int)
// Move current location to next node (postfix operator).
// Do nothing if current is at the tail of the list.
{
    if (current != last)
        current = current->next;
    return *this;
}

template<class T> TList<T>& TList<T>::operator-- (int)
// Move current location to previous node (postfix operator).
// Do nothing if current is at the head of the list
{
    if (current != first)
    {
        Node<T>* nptr = first;
        while (nptr->next != current)
        nptr = nptr->next;
       current = nptr;
    }
    return *this;
}

template<class T> T TList<T>::Retrieve() const	
// Return the element at the current position.
{ 
    if (current)
        return current->value;
    else
    {
        cerr << "Attempted to Return an element from an empty list";
        exit(1);
    }
}


template<class T> void TList<T>::Update(T x)
// Store x in current location.
{ 
    if (current)
        current->value = x;
    else
    {
         cerr << "Attempted to Update an element in an empty list";
         exit(1);
     }
}

template<class T> int TList<T>::Length()
// Return the number of nodes in the list.
{ return size;}

Traversing a List

p = head;
while (p)
{
    process node;
    p = p -> next;
}

11.4 Comparing Implementation

• Space
• Time (see table in chapter 10)
• Comprehensibility
• Trade-Offs

11.5 Applications of Stacks

TStack* stackPtr;
class TStack
{public:
TStack()
// Used: To initialize the receiver stack.
// Pre:  None
// Post: Receiver stack is initialized and Size = 0
//   and Error = False and S = ()

~TStack 
// Used: To destroy the receiver stack.
// Pre:  Receiver is initialized.
// Post: Receiver stack is destroyed.

void Push (T element)
// Used: To add a new element onto the top of the stack.
// Pre:  S = (e[1] e[2] ... e[N]) and Size = N
// Post: N < MaxElements and Size = N+1 and S = (e[1] e[2] ... e[N] Eptr)
//   or N = MaxElements and Error = True

void Pop()
// Used: To remove the top element from the stack.
// Pre:  S = (e[1] e[2] ... e[N]) and Size = N
// Post: N = 0 and Error = True
//   or N > 0 and S = (e[1] e[2] ... e[N-1]) and Size = N-1

T Top()
// Used: To access the element at the top of the stack
// Pre:  S = (e[1] e[2] ... e[N]) and Size = N
// Post: N = 0 and Error = True and result = NIL
//   or N > 0 and result = e[N]
}

Run-Time Stacks and Procedure Activation

Stack Machines

von Neumann machine -

• LOAD R1,17
• MUL R1, 40
• ADD R1, 35

stack machine

• PUSH 40
• PUSH 17
• PUSH 35
• MUL
• ADD

Application: Evaluating Polish Expressions

• 1. Any operand x is a Polish expression
• 2. If p1 and p2 are Polish expressions, then p1 p2 op is a Polish expression.

Rules for evaluation:

• 1. Scan the expression from left to right until the first operator op is reached.
• 2. Apply this operator to the two operands p1 and p2 that appear immediately on its left, obtaining the result p, and then replace the triple p1 p2 op in the expression by p.

Algorithm:

• 1. Scan the expression from left to right.
  • As each operand is reached, perform Step 2.
  • As each operator is reached, perform Step 3.
• 2. Push the operand onto the operand stack.
• 3. Pop the topmost two operands from the stack, apply this operator to them, push the result onto the stack.

11.6 Applications of Queues

Init	Done	ReadIn
Display	Save	Empty
Enqueue	Dequeue	Front
Rear

TQueue* queuePtr;
class TQueue
{public:
TQueue
// Used: To initialize the receiver queue.
// Pre:  None
// Post: The receiver queue is intialized 

~TQueue
// Used: To destroy the receiver queue.
// Pre:  Receiver queue is initialized.
// Post: The receiver queue is destroyed.

void EnQueue(T element)
// Used: To add a new object to the rear of the receiver queue
// Pre:  Q = (e[1] ... e[N]) and Size = N
// Post: Size = MaxElements ^ Error = True 
or Size < MaxElements ^ Q = (e[1] ... e[N] Eptr) and Size = N + 1)

void DeQueue()
// Used: To remove an object from the front of the queue.
// Pre:  Q = (e[1] e[2] ... e[N]) and Size = N
// Post: Size = 0 and Error = True or N > 0 ^ Q = (e[2] ... e[N]) and Size = N-1)

void Empty

T Front()
// Used: To access the object at the front of the queue.
// Pre:  Q = (e[1] ... e[N]) and Size = N
// Post: Size = 0 and result = Nil and Error = True or Size > 0 and result = e[1]

T Rear();
// Used: To access the object at the rear of the queue.
// Pre:  Q = (e[1] ... e[N]) and Size = N
// Post: Size = 0 and result = Nil and Error = True or Size > 0 and result = e[N]
}

Exercises

• Lab 12: pg. 394: #2, 4
• Lab 13: pg. 394-395: #8, 14
• Lab 14: pg. 396: #18