teaching machines

CS 330 Lecture 27 – Inheritance and polymorphism

April 9, 2012 by Chris Johnson. Filed under cs330, lectures, spring 2012.

Agenda

• constructors and destructors
• a destructor’s job: release dynamically-allocated members
• a linked list in C++
• a Stack using inheritance in C++
• implementation inheritance vs. interface inheritance
• the enlightened stance: favor composition, shallow hierarchies, interfaces
• how polymorphism works

TODO

• Why extends is evil: http://www.javaworld.com/javaworld/jw-08-2003/jw-0801-toolbox.html?page=1
• What OOP isn’t: http://hacksoflife.blogspot.com/2010/12/what-oop-isnt.html

Program This

Given the List<T> implementation discussed in class, write one of the a) prepend method or b) the append method.

Code

List.h

#ifndef LIST_H
#define LIST_H

#include <cstdlib>

template<class T> class List {
  public:
    List();
    ~List();

    void append(T item);
    void prepend(T item);
    void apply(void (*f)(T& item));
    int size() const;

    struct Node {
      T item;
      Node *next;
      Node *prev;
    };
  protected:
    void remove(Node *node);

    Node *head;
    Node *tail;

    int nelements;
};

/* ------------------------------------------------------------------------- */

template<class T>
List<T>::List() :
  nelements(0) {
  head = new Node;
  tail = new Node;

  head->next = tail;
  head->prev = NULL;
  tail->next = NULL;
  tail->prev = head;
}

/* ------------------------------------------------------------------------- */

template<class T>
List<T>::~List() {
  std::cout << "is in dtor" << std::endl;
  Node *curr = head;
  while (curr->next) {
    curr = curr->next;
    delete curr->prev;
  }
  delete curr;
}

/* ------------------------------------------------------------------------- */

template<class T>
void List<T>::append(T item) {
  Node *new_node = new Node;
  new_node->next = tail;
  new_node->prev = tail->prev;
  tail->prev = new_node;
  new_node->prev->next = new_node;
  new_node->item = item;
  ++nelements;
}

/* ------------------------------------------------------------------------- */

template<class T>
void List<T>::prepend(T item) {
  Node *new_node = new Node;
  new_node->next = head->next;
  new_node->prev = head;
  head->next = new_node;
  new_node->next->prev = new_node;
  new_node->item = item;
  ++nelements;
}

/* ------------------------------------------------------------------------- */

template<class T>
void List<T>::remove(Node *node) {
  node->prev->next = node->next;
  node->next->prev = node->prev;
  delete node;
  --nelements;
}

/* ------------------------------------------------------------------------- */

template<class T>
int List<T>::size() const {
  return nelements;
}

/* ------------------------------------------------------------------------- */

template<class T>
void List<T>::apply(void (*f)(T& item)) {
  Node *curr = head->next;
  while (curr != tail) {
    f(curr->item);
    curr = curr->next;
  }
}

/* ------------------------------------------------------------------------- */

#endif

Stack.h

#ifndef STACK_H
#define STACK_H

#include "List.h"

template<typename T> class Stack : public List<T> {
  public:

    void push(T item);
    T pop();

  private:
};

/* ------------------------------------------------------------------------- */

template<typename T>
void Stack<T>::push(T item) {
  append(item);
}

/* ------------------------------------------------------------------------- */

template<typename T>
T Stack<T>::pop() {
  if (List<T>::size() == 0) {
    throw "stack empty, sorry";
  }

  // TODO: this errs
  List<T>::Node *last_node = this->tail->prev;
  T last_item = last_node->item;
  this->tail->prev = last_node->prev;
  this->tail->prev->next = this->tail;

  delete last_node;

  return last_item;
}

/* ------------------------------------------------------------------------- */

#endif

lister.cpp

#include <iostream>
#include "List.h"
#include "Stack.h"

void print(int& item) {
  std::cout << "item: " << item << std::endl;
}

int main() {
  List<int> nums;

  nums.append(10);
  nums.append(20);
  nums.append(30);

  nums.apply(print);

  Stack<double> percents;
  percents.push(5.0);

  List<double>::Node *last_node;
}

Haiku