teaching machines

CS 330 Lecture 25 – Generics/templates II

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

Agenda

• Java before generics
• genericizing in Java
• type erasure
• adding templates to C
• templates in C++

Code

ArrayList.java

package cs330;

public class ArrayList {
  private Object[] stuff;
  private int size;
  
  public ArrayList() {
    stuff = new Object[10];
    size = 0;
  }
  
  public Object get(int i) {
    return stuff[i];
  }
  
  public int size() {
    return size;
  }
  
  public boolean add(Object o) {
    if (size == stuff.length) {
      Object[] aWholeLotMoreStuff = new Object[stuff.length * 2];
      System.arraycopy(stuff, 0, aWholeLotMoreStuff, 0, stuff.length);
      stuff = aWholeLotMoreStuff;
    }
    
    stuff[size] = o;
    ++size;
    
    return true;
  }
}

GenericArrayList.java

package cs330;

public class GenericArrayList<T> {
  private T[] stuff;
  private int size;
  
  public GenericArrayList() {
    stuff = (T[]) new Object[10];
    size = 0;
  }
  
  public T get(int i) {
    return stuff[i];
  }
  
  public int size() {
    return size;
  }
  
  public boolean add(T o) {
    if (size == stuff.length) {
      T[] aWholeLotMoreStuff = (T[]) new Object[stuff.length * 2];
      System.arraycopy(stuff, 0, aWholeLotMoreStuff, 0, stuff.length);
      stuff = aWholeLotMoreStuff;
    }
    
    stuff[size] = o;
    ++size;
    
    return true;
  }
}

Tester.java

package cs330;

public class Tester {
  public static void main(String[] args) {
    ArrayList list = new ArrayList();
    list.add("stuff1");
    list.add("stuff2");
    list.add(new Banana());
    
    String grabbed = (String) list.get(0);
//    grabbed = (String) list.get(2);
    
    GenericArrayList<String> list2 = new GenericArrayList<String>();
    list2.add("stuff1");
    list2.add("stuff2");
//    list2.add(new Banana());
    
    grabbed = list2.get(0);
    
    
    GenericArrayList<Banana> list3 = new GenericArrayList<Banana>();
    
    System.out.println(list3.getClass() == list2.getClass());
  }
}

class Banana {
}

stack_T.c

#include <assert.h>
#include <stdlib.h>

typedef struct {
  T elements[100];
  int top;
} stack_TNAME_t;

stack_TNAME_t *make_stack() {
  stack_TNAME_t *stack = (stack_TNAME_t *) malloc(sizeof(stack_TNAME_t));
  stack->top = -1;
  return stack;
}

void free_stack(stack_TNAME_t *stack) {
  free(stack);
}

T peek(const stack_TNAME_t *stack) {
  assert(stack->top >= 0);
  return stack->elements[stack->top];
}

void push(stack_TNAME_t *stack, T c) {
  assert(stack->top < 100);
  ++stack->top;
  stack->elements[stack->top] = c;
}

T pop(stack_TNAME_t *stack) {
  assert(stack->top >= 0);
  T c = stack->elements[stack->top];
  --stack->top;
  return c;
}

ctemplates.mk

stack_float.c: stack_T.c
	sed -e 's/\<T\>/float/g' -e 's/TNAME/float/g' stack_T.c > stack_float.c

stack_floatp.c: stack_T.c
	sed -e 's/\<T\>/float */g' -e 's/TNAME/floatp/g' stack_T.c > stack_floatp.c

stack_intppp.c: stack_T.c
	sed -e 's/\<T\>/int ***/g' -e 's/TNAME/intppp/g' stack_T.c > stack_intppp.c

exe: stack_float.c exe.c
	gcc -std=c99 -o exe exe.c 

clean:
	rm -f exe stack_float.c stack_floatp.c stack_intppp.c

exe.c

#include <stdio.h>

#include "stack_float.c"

int main() {
  stack_float_t *stack = make_stack();

  for (int i = 0; i < 20; i += 2) {
    push(stack, i + 0.5f);
  }

  for (int i = 0; i < 20; i += 2) {
    printf("pop(stack): %f\n", pop(stack));
  }

  return 0;
}

stack.cpp

#include <cassert>

template<typename T> class Stack {
  public:
    Stack();
    T peek();
    void push(T item_to_add);
    T pop();

  private:
    T elements[100];
    int top;
};

template<typename T>
Stack<T>::Stack() :
  top(-1) {
}

template<typename T>
T Stack<T>::peek() {
  assert(top >= 0);
  return elements[top];
}

template<typename T>
void Stack<T>::push(T item_to_add) {
  assert(top < 100);
  ++top;
  elements[top] = c;
}

template<typename T>
T Stack<T>::pop() {
  assert(top >= 0);
  T c = elements[top];
  --top;
  return c;
}

Haiku