_TEMPLATES IN C++_
by Nicholas Wilt

[LISTING ONE]
// select.h -- Template-based C++ implementation of the randomized
//   selection algorithm from _Introduction to Algorithms_ by Cormen, 
//   Leiserson and Rivest (pg. 187). Copyright (C) 1992 by Nicholas Wilt.  
//   All rights reserved.

template<class T> T
Select(T *base, const int n, int inx)
{
  int left = 0;
  int right = n;

  // This while loop terminates when base[left..right]
  // defines a 1-element array.
  while (right != left + 1) {
    // Partition about the q'th element of the array
    int q = left + rand() % (right - left);

    T t = base[q];
    base[q] = base[left];
    base[left] = t;

    // Partition about base[left]; all elements less than
    // base[left] get swapped into the left-hand side of
    // the array.
    int i = left - 1;
    int j = right;
    while (j >= i) {
      while (j > 0 && t < base[--j]);
      while (i < (right-1) && base[++i] < t);
      if (i < j) {
    T t = base[i];
    base[i] = base[j];
    base[j] = t;
      }
    }
    // Now focus attention on the partition containing
    // the order statistic we're interested in.
    if (inx <= j - left)
      // Throw away the right-hand partition; we know it
      // doesn't contain the i'th order statistic.
      right = j + 1;
    else {
      // Throw away the left-hand partition; we know it
      // doesn't contain the i'th order statistic.
      // Now we're looking for the inx - j - left + 1'th
      // order statistic of the right-hand partition.
      inx -= j - left + 1;
      left = j + 1;
    }
  }
  // base[left] is the element we want, return it.
  return base[left];
}


[LISTING TWO]

// select.cpp -- Demonstrates the use of the Select function template on 
//   arrays of integers and Point2D's. It generates a random of array of 
//   integers, then enumerates the order statistics from 0..n-1. This will 
//   print out the members of the array in sorted order. This isn't a 
//   suggestion for how to use Select (obviously it's more efficient to sort 
//   the array if you want to print out the members in sorted order!) but it's
//   good to enumerate them all to verify that algorithm is working properly.
//   The other class the program deals with is a used-defined Point2D class.
//   This is a two-dimensional point defined by two floating-point numbers. 
//   The ordering chosen, defined by the operator< for the class, is a 
//   standard topological ordering from computational geometry.
//   Copyright (C) 1992 by Nicholas Wilt.  All rights reserved.

#include <fstream.h>
#include <iomanip.h>
#include <stdlib.h>
#include "select.h"

// Just for fun, here's a signum template function. Returns -1 if a < b; 1 if 
// b < a; 0 if they're equal. I've ensured only operator< is used for 
// comparisons, so operator> isn't defined for a user-defined class.
template<class T> int
Signum(T a, T b)
{
  if (a < b)         return -1;
  else if (b < a)    return 1;
  else           return 0;
}
class Point2D {
  double x, y;
public:
  Point2D() { }
  Point2D(double X, double Y): x(X), y(Y) { }

  // operator< makes our points sorted in topological order: increasing order 
  // in x, and increasing order in y if there is a tie in x.
  friend int operator<(const Point2D& x, const Point2D& y) {
    int ret = Signum(x.x, y.x);
    return (ret) ? ret < 0 : Signum(x.y, y.y) < 0;
  }
  friend ostream& operator<< (ostream& a, Point2D& b) {
    a << "(" << b.x << ", " << b.y << ")";
    return a;
  }
};
// Number of elements to allocate in the test arrays
const int NumInts = 10;
const int NumPts = 5;
int
main()
{
  int *x = new int[NumInts];
  int i;
  for (i = 0; i < NumInts; i++) {
    x[i] = rand() % 100;
    cout << x[i] << ' ';
  }
  cout << '\n';
  for (i = 0; i < NumInts; i++) {
    cout << Select(x, NumInts, i) << ' ';
  }
  cout << '\n';
  delete x;
  Point2D *y = new Point2D[NumPts];
  cout << setprecision(2);
  for (i = 0; i < NumPts; i++) {
    y[i] = Point2D( (double) rand() * 10.0 / RAND_MAX,
            (double) rand() * 10.0 / RAND_MAX);
    cout << y[i] << ' ';
  }
  cout << '\n';
  for (i = 0; i < NumPts; i++) {
    cout << Select(y, NumPts, i) << ' ';
  }
  cout << '\n';
  return 0;
}


[LISTING THREE]

// bintree.h -- Header file for simple binary tree class template.
//   Copyright (C) 1992 by Nicholas Wilt.  All rights reserved.
//  BinaryNode is a helper class template for the BinaryTree class template. It
//  should be needed only rarely by the end user of the BinaryTree class, if 
//  ever. BinaryTree<T> is BinaryNode<T>'s friend. The only other classes that 
//  can access BinaryNode's data are classes for which it is a base class.
template<class T>
class BinaryNode {
protected:
  T x;
  BinaryNode<T> *left, *right;
public:
  BinaryNode(const T& X): x(X) {
    left = right = 0;
  }
  BinaryNode(const T& X, BinaryNode<T> *l, BinaryNode<T> *r): x(X) {
    left = l;
    right = r;
  }
  friend class BinaryTree<T>;
}
// BinaryTree manipulates binary trees described by pointers to BinaryNode.
template<class T>
class BinaryTree {
protected:
// Pointer to the root node of the binary tree.
  BinaryNode<T> *root;
// Various functions to manipulate collections of binary
// tree nodes.  These are the functions that do the real work.
  static BinaryNode<T> *InsertNode(BinaryNode<T> *r, T x);
  static BinaryNode<T> *DupNode(BinaryNode<T> *r);
  static void PostOrderDeletion(BinaryNode<T> *r);
  static T *QueryNode(BinaryNode<T> *r, const T& x);
  static void PreOrderNode(BinaryNode<T> *r, void (*f)(T *));
  static void InOrderNode(BinaryNode<T> *r, void (*f)(T *));
  static void PostOrderNode(BinaryNode<T> *r, void (*f)(T *));
public:
  // Constructors and assignment operator
  BinaryTree() { root = 0; }
  // Copy constructor duplicates all the nodes in the tree.
  BinaryTree(BinaryTree<T>& x) { root = DupNode(x.root); }
  // Assignment operator deletes nodes already there, then
  // copies the ones in the tree to be copied.
  BinaryTree<T>& operator=(const BinaryTree<T>& x) {
    PostOrderDeletion(root);
    root = DupNode(x.root);
    return *this;
  }
  // Destructor frees all the nodes in the binary tree.
  ~BinaryTree() { PostOrderDeletion(root);  }
  // Inserts a node containing x into the binary tree.
  void Insert(const T& x) { root = InsertNode(root, x); }
  // Returns a pointer to node equal to x, if in tree.
  // If none found Query returns 0.
  T *Query(const T& x) { return QueryNode(root, x); }

  // Various traversal functions perform the traversal
  // in the order given and call f with a pointer to the
  // node contents when visiting.
  void PreOrder(void (*f)(T *)) { PreOrderNode(root, f); }
  void InOrder(void (*f)(T *)) { InOrderNode(root, f); }
  void PostOrder(void (*f)(T *)) { PostOrderNode(root, f); }
};
// The following function declarations give examples of how to
// write function templates for member functions.
// Deletes the tree pointed to by r.
template<class T> void
BinaryTree<T>::PostOrderDeletion(BinaryNode<T> *r)
{
  if (r) {
    PostOrderDeletion(r->left);
    PostOrderDeletion(r->right);
    delete r;
  }
}
// Inserts a node with key x into the binary tree with the
// root given, and returns the new root.
template<class T> BinaryNode<T> *
BinaryTree<T>::InsertNode(BinaryNode<T> *r, T x)
{
  if (r) {
    if (x < r->x)
      r->left = InsertNode(r->left, x);
    else
      r->right = InsertNode(r->right, x);
  }
  else
    r = new BinaryNode<T>(x);
  return r;
}
// Duplicates the binary tree given and returns pointer to the new root.
template<class T> BinaryNode<T> *
BinaryTree<T>::DupNode(BinaryNode<T> *r)
{
  if (r)
    return new BinaryNode<T>(r->x,
                 DupNode(r->left),
                 DupNode(r->right));
  else
    return 0;
}
// Returns pointer to key given, if found in binary tree. Otherwise returns 0.
template<class T> T *
BinaryTree<T>::QueryNode(BinaryNode<T> *r, const T& x)
{
  if (r) {
    if (x == r->x)
      return &r->x;
    if (x < r->x) return QueryNode(r->left, x);
    else      return QueryNode(r->right, x);
  }
  else
    return 0;
}
// Traversal functions. These three functions traverse the tree and call the 
// pointer to function on the node contents when it's time to visit the node.
template<class T> void
BinaryTree<T>::PreOrderNode(BinaryNode<T> *r, void (*f)(T *))
{
  if (r) {
    (*f)(&r->x);
    PreOrderNode(r->left, f);
    PreOrderNode(r->right, f);
  }
}
template<class T> void
BinaryTree<T>::InOrderNode(BinaryNode<T> *r, void (*f)(T *))
{
  if (r) {
    InOrderNode(r->left, f);
    (*f)(&r->x);
    InOrderNode(r->right, f);
  }
}
template<class T> void
BinaryTree<T>::PostOrderNode(BinaryNode<T> *r, void (*f)(T *))
{
  if (r) {
    PostOrderNode(r->left, f);
    PostOrderNode(r->right, f);
    (*f)(&r->x);
  }
}




[LISTING FOUR]

// bintree.cpp -- Demonstration program for BinaryTree class template. Inserts 
//  10 random numbers into a BinaryTree<int>, prints them out and then prints 
//  out the pre-, in- and post-order traversals of the resulting binary tree.
//  Copyright (C) 1992 by Nicholas Wilt.  All rights reserved.

#include <iostream.h>
#include <stdlib.h>
#include <alloc.h>

#include "bintree.h"

// Passed to BinaryTree<int> traversal functions. This gets called with a 
// pointer to the node contents (int in this case, since it's a 
// BinaryTree<int>) whenever it's time to visit a node in the tree.
void
PrintInt(int *x)
{
  cout << *x << ' ';
}
int
main()
{
  int i;
  BinaryTree<int> tree;
  cout << "Insertion:\t";
  for (i = 0; i < 10; i++) {
    int insertme = rand() % 100;
    tree.Insert(insertme);
    cout << insertme << ' ';
  }
  cout << '\n';
  cout << "Pre-order:\t";  tree.PreOrder(PrintInt);  cout << '\n';
  cout << "In-order:\t";   tree.InOrder(PrintInt);   cout << '\n';
  cout << "Post-order:\t"; tree.PostOrder(PrintInt); cout << '\n';
  return 0;
}


Example 1: Declaring a function template

template<template parameters>
return value               // From here on we define
name(function parameters) {    // the function in terms of
  function body            // the template parameters.
}




Example 2: (a) defining a template-based Select function; (b) 
calling the Select function

(a)

template<class T> T
Select(T *base, const int n, int i)
{
    // Implementation
}


(b)

    int *arr, n;
    // ... allocate array and set n
    // Set penultimate to the second-largest element in arr.
    int penultimate = Select(arr, n, n - 2);

(c)

int
Select(int *x, const int n, int i)
{
  // Own function definition of Select<int>
}



Example 3

(a)

template<class T>
class BinaryNode {
  T x;              // Contents of node
  BinaryNode<T> *left, *right;  // Left and right children
//etc.
};


(b)

// Class template for a binary tree node including a
// pointer to the parent.
template<class T>
class BinaryNodeWithParent : public BinaryNode<T> {
  BinaryNodeWithParent<T> *parent;
// etc.
};


(c)

template<class T, int Size>
class Vector {
  T x[Size];       // Vector contains Size T's.
// etc.
};