teaching machines

CS 330 Lecture 28 – Parametric Polymorphism

April 13, 2015 by Chris Johnson. Filed under cs330, lectures, spring 2015.

Agenda

• what ?s
• program this
• the cost of subtype polymorphism
• a Set class in C++
• a Set class in Java
• C++ templates vs. Java generics

Learning Intentions

• I understand that some methods of making code reusable lead to costs in performance and error detection.
• I can use templates to achieve parametric polymorphism in C++.
• I can identify some of of the restrictions of Java’s implementation of parametric polymorphism.

Program This

You are writing a Set class. It manages a collection of unique objects. In pseudocode, write one of the following with your neighbor:

1. A constructor that allocates unused space for the collection.
2. A Contains method that determines if an item already is in the set.
3. An += method that adds an item to the set, if it’s not already a member.

Code

Set.h

#ifndef SET_H
#define SET_H

#include <cassert>

template<typename T> class Set {
  public:
    Set() : 
      capacity(10),
      nitems(0),
      items(new T[capacity]) {
    }

    int GetSize() const {
      return nitems;
    }

    const T& operator[](int i) const {
      assert(i >= 0 && i < nitems);
      return items[i];
    }

    bool Contains(const T& item) const {
      for (int i = 0; i < nitems; ++i) {
        if (items[i] == item) {
          return true;
        }
      }

      return false;
    }

    void operator+=(const T& item) {
      if (Contains(item)) {
        return;
      } 

      // Expand as necessary
      if (nitems == capacity) {
        capacity *= 2;
        T *bigger = new T[capacity];
        for (int i = 0; i < nitems; ++i) {
          bigger[i] = items[i];
        }
        delete[] items;
        items = bigger;
      }

      // Append
      items[nitems] = item;
      ++nitems;
    }

  private:
    int capacity;
    int nitems;
    T *items;
};

#endif

main.cpp

#include <iostream>

#include "Set.h"

class Point2D {
  public:
    Point2D() : x(0), y(0) {
    }

    Point2D(int x, int y) : x(x), y(y) {
    }

    bool operator==(const Point2D& other) {
      return x == other.x && y == other.y;
    }

  private:
    int x, y;
};

int main(int argc, char **argv) {
  Set<int> ns;

  ns += 12;
  ns += 12;
  ns += 12;
  ns += 12;
  ns += 12;
  ns += 12;
  ns += 12;
  ns += 12;
  ns += 12;
  ns += 12;
  ns += 12;
  ns += 12;
  ns += 21;
  /* ns += std::exception(); */

  std::cout << "ns.GetSize(): " << ns.GetSize() << std::endl;

  Set<Point2D> points;
  points += Point2D(5, 10);
  points += Point2D(1, 2);
  points += Point2D(3, 4);
  std::cout << "points.GetSize(): " << points.GetSize() << std::endl;

  return 0;
}

Haiku