CPSC170
Fundamentals of Computer Science II

pre-lab video

Lab 16

Templates

IntPair is a simple class that holds two integers. As its name suggests, it models a pair of integers. The file IntPair.h contains its implementation. Study the code to make sure you understand every line. Please ask questions if anything doesn't make sense.

We use IntPair to create a class called Stack. The Stack class is declared below with all the member functions defined within the declaration.

#define MAXSIZE 100  // Maximum size of the stack
class Stack {
  private:
    IntPair Data[MAXSIZE];    // The array representing the stack
    bool empty;               // boolean value indicating if the stack
                              // is empty. 
    bool full;                // boolean value indicating if the stack
                              // is full.
    int topPosition;          // The next free position on the stack, starting at 0. 

// CI: This stack contains topPosition number of items, i.e.,
//      Data[0]..Data[topPosition-1] are defined. 
//      Data[topPosition-1] is at the top of the stack.
//      empty = true iff topPosition = 0
//      full = true iff topPosition = MAXSIZE
  public:
    // Deafult constructor
    // PRE:
    // POST: This object satisfies the CI.
    Stack() {
      empty = true;
      full = false;
      topPosition = 0;
    };

    // PRE: This object is defined and satisfies the CI.
    //      Element = e is defined.
    //      This object is not a full stack.
    // POST: This object now contains e at the top of the stack.
    //       This object satisfies the CI.
    void push (IntPair Element) {
      Data[topPosition] = Element;
      topPosition++;
      if (topPosition == MAXSIZE)
        full = true;
      if (empty)
        empty = false;
    };

    // PRE: This object is defined and satisfies the CI.
    //      This object is not an empty stack.
    // POST: The element at the top of the stack is removed.
    //       This object satisfies the CI
    void pop () {
      topPosition--;
      if (topPosition == 0)
        empty = true;
      if (full)
        full = false;
    }

    // PRE: This object is defined and satisfies the CI.
    //      This object is not an empty stack.
    // POST: RV is the top element of the stack.
    IntPair top () const {return (Data[topPosition-1]);};

    // PRE: This object is defined and satisfies the CI.
    // POST: RV is true iff this stack is empty.
    bool isEmpty() const {return (empty);};

    // PRE: This object is defined and satisfies the CI.
    // POST: RV is true iff this stack is full.
    bool isFull() const {return (full);};
};

Here we declared a stack of IntPair objects. Now suppose we need a stack of int objects. Unfortunately, the above class declaration is not useful. We have to declare another stack class as follows:

#define MAXSIZE 100  // Maximum size of the stack

class Stack {
  private:
    int Data[MAXSIZE];        // The array representing the stack
    bool empty;               // boolean value indicating if the stack
                              // is empty. 
    bool full;                // boolean value indicating if the stack
                              // is full.
    int topPosition;          // The next free position on the stack, starting at 0. 

  // CI: This stack contains topPosition number of items, i.e.,
  //      Data[0]..Data[topPosition-1] are defined. 
  //      Data[topPosition-1] is at the top of the stack.
  //      empty = true iff topPosition = 0
  //      full = true iff topPosition = MAXSIZE
  public:
    // Default constructor
    // PRE:
    // POST: This object satisfies the CI.
    Stack() {
      empty = true;
      full = false;
      topPosition = 0;
    };

    // PRE: This object is defined and satisfies the CI.
    //      Element = e is defined.
    //      This object is not a full stack.
    // POST: This object now contains e at the top of the stack.
    //       This object satisfies the CI.
    void push (int Element) {
      Data[topPosition] = Element;
      topPosition++;
      if (topPosition == MAXSIZE)
        full = true;
      if (empty)
        empty = false;
    };

    // PRE: This object is defined and satisfies the CI.
    //      This object is not an empty stack.
    // POST: The element at the top of the stack is removed.
    //       This object satisfies the CI
    void pop () {
      topPosition--;
      if (topPosition == 0)
        empty = true;
      if (full)
        full = false;
    }

    // PRE: This object is defined and satisfies the CI.
    //      This object is not an empty stack.
    // POST: RV is the top element of the stack.
    int top () const {return (Data[topPosition-1]);};

    // PRE: This object is defined and satisfies the CI.
    // POST: RV is true iff this stack is empty.
    bool isEmpty() const {return (empty);};

    // PRE: This object is defined and satisfies the CI.
    // POST: RV is true iff this stack is full.
    bool isFull() const {return (full);};
};

Note that the only change in the two declarations is that IntPair is replaced with int. In other words, simply making a textual replacement of the type in a copy of the first class declaration gives us the second class declaration. Of course, if we needed to use both kinds of stacks in the same program, we would have to name one of the stack classes differently.

C++ provides the feature of templates to help the programmer with declaring such classes. The idea of a template is that we declare a class that has a type name as a parameter. This is a templated or parametrized class. The real class is constructed by the compiler when we declare an object of this class with a type for its parameter. More concretely, the header for the templated stack class would be:
```
   template <class T>
   class Stack {
      ...
   };
```
and then in a client program we could declare a stack of IntPair objects and a stack of int objects as:
```
Stack<IntPair> PairStack;
Stack<int> intStack;
```

All the member functions declared in the Stack class are available for both the objects PairStack and intStack. The parameter for the class Stack is denoted above by the name T. It is much like a formal parameter in a function header. The name is simply a valid identifier---an alphanumeric string beginning with a letter.

Stack.h is the complete declaration and definition of a templated stack class. (I have removed the comments below for succinctness.)

#define MAXSIZE 100

template <class T>
class Stack {
  private:
    T Data[MAXSIZE];
    bool empty;
    bool full;
    int topPosition;

  public:
    Stack() {
      empty = true;
      full = false;
      topPosition = 0;
    };

    void push (T Element) {
      Data[topPosition] = Element;
      topPosition++;
      if (topPosition == MAXSIZE)
        full = true;
      if (empty)
        empty = false;
    };

    void pop () {
      topPosition--;
      if (topPosition == 0)
        empty = true;
      if (full)
        full = false;
    };

    T top () const {return (Data[topPosition-1]);};

    bool isEmpty() const {return (empty);};
  
    bool isFull() const {return (full);};
};

Since the compiler "creates" the instances of classes as and when they are declared in a program, the compiler needs to see the declaration and definition of the class together. So, for templated classes, we do not write a .cc file; we include the definitions of the member functions in the class declaration as shown above.

Consider the IntPair class. We could have defined that to be a templated class too, as the objects of that class could be of any type, that is we may want objects that are pairs of floats or pairs of Student objects, etc. We would declare and define the templated class Pair just as above.

Copy the file IntPair.h to a file Pair.h and modify it to declare and define a templated Pair class.

Once we have a templated Pair class, we could use that as the type for an instance of a stack. That is we could declare objects as
```
Stack<Pair<int> > IntPairStack;
Stack<Pair<Student> > StudentPairStack;
```
Note the space between the two > > in the two declarations above. If the space is not left, the some compilers confuses the sequence >> with the input operator.

One can also use a templated class as a type for itself. That is,
```
Pair<Pair<int> > TwoPairs;
```
declares an object that contains a pair of pairs of integers.

Exercise

Complete the homework.