Implementing the Bridge pattern using templates with Microsoft Visual C++ 6.0

I wonder whether you had a similar experience to me. You read with excitement Andrei Alexandrescu's Modern C++ Design [Alexandrescu] (the author's remark "Truly there is beauty in computer engineering" could be applied to his own book). Then you came up against Microsoft Visual C++ at your place of work and found you couldn't try much of it out. Do we have to be content with using all that fun template stuff on our home computers, where we get to choose the compiler, or can we use some of the techniques even with Visual C++?

The main limitation of Visual C++ 6.0 is its lack of support for partial specialisation of class templates. That eliminates using Alexandrescu's TypeLists, upon which a significant portion of his book depends. Another limitation is that it does not permit template parameters that are themselves class templates. This is less of a problem since the inferior alternative of member function templates is supported (though the implementation of such functions has to be placed in the class definition, "inline" style). Within the boundaries set by these limitations there are some valuable techniques available to us as I hope to demonstrate.

The example I have chosen is to implement the Bridge pattern [Gamma-et-al] for a class by making the class of its implementation member variable a policy class, passed as a template parameter. This application of templates was mentioned by Nicolai Josuttis in his talk at the 2001 ACCU Conference (a talk described in C Vu as "solid but uninspiring". Well, I was inspired by it!). I am also indebted in what follows to Lois Goldthwaite's stimulating presentation of polymorphism using templates in Overload [Goldthwaite].

To be specific, I am going to develop a Blackjack Hand class, as suggested by Code Critique 14 [CVu14.1]. For card names I will use a simple enum:

// card.h (include guard not shown)
namespace Blackjack {
  enum Card { ace, king, queen, jack, ten,
              nine, eight, seven, six,
              five, four, three, two };
}

I will also use an encapsulated lookup table of card values:

// card_values.h (include guard not shown)
#include <map>
#include <exception>
#include "card.h"

namespace Blackjack {
  class Card_Values {
  public:
    explicit Card_Values(unsigned int
                         ace_value = 1);
    // copy constructor, assignment, swap,
    // destructor not shown

    class Card_Has_No_Value
         : public std::exception {};
    unsigned int lookup(Card card) const
         throw(Card_Has_No_Value);
  private:
    typedef std::map<Card, unsigned int>
                           Card_Lookup;
    Card_Lookup card_lookup;
  };
}

For a first pass, we build a non-template version of the Hand class:

// hand.h (include guard not shown)
#include "card.h"
#include <map>
#include <exception>

namespace Blackjack {
  class Hand {
  public:
    // default constructor, copy constructor,
    // assignment, swap and destructor not shown
    class Four_Of_That_Card_Already
             : public std::exception {};
    class Five_Cards_Already
             : public std::exception {};
    class Fewer_Than_Two_Cards
             : public std::exception {};
    Hand& add(Card card)
             throw(Four_Of_That_Card_Already,
    Five_Cards_Already);
    unsigned int value() const
             throw(Fewer_Than_Two_Cards);
  private:
    struct Card_Data {
       unsigned int count;
    };
    typedef std::map<Card, Card_Data>
    Card_Container;
    Card_Container cards;
    unsigned int number_of_cards;
    class Accumulate_Card_Value;
  };
}

// hand.cpp
#include "hand.h"
#include "card_values.h"
#include <numeric>

namespace {
  const Blackjack::Card_Values&
             get_card_values() {
  static const Blackjack::Card_Values
             card_values;
  return card_values;
}

class Blackjack::Hand::Accumulate_Card_Value {
  public:
    Accumulate_Card_Value(
             const Card_Values& card_values)
             : values(card_values) {}
    unsigned int operator()(
      unsigned int accumulated_value,
      const Card_Container::value_type&
             card_data) {
      return accumulated_value +=
             (card_data.second.count *
             values.lookup(card_data.first));
    }
  private:
    const Card_Values& values;
  };
}

// default constructor, copy constructor,
// assignment, swap and destructor not shown

Blackjack::Hand::AddStatus
Blackjack::Hand::add(Card card)
            throw(Four_Of_That_Card_Already,
                  Five_Cards_Already) {
  if(number_of_cards == 5) {
    throw Five_Cards_Already();
  }
  Card_Data& card_data = cards[card];
  if(card_data.count == 4) {
    throw Four_Of_That_Card_Already();
  }
  ++card_data.count;
  ++number_of_cards;
  return *this;
}

unsigned int Blackjack::Hand::value() const
             throw(Fewer_Than_Two_Cards) {
  if(number_of_cards < 2) {
    throw Fewer_Than_Two_Cards();
  }
  unsigned int hand_value =
             std::accumulate(cards.begin(),
             cards.end(),
             0,
             Accumulate_Card_Value(
               get_card_values()));
  if( (hand_value < 12) &&
      (cards.find(ace) != cards.end()) ) {
    hand_value += 10;
  }
  return hand_value;
}

In the non-template version, the implementation of hand is hard coded to be a std::map<Card, Card_Data> together with a cached value number_of_cards. Our goal is to replace this implementation with a single member variable.The class of this member variable will be a template parameter. To reach this goal we need to identify all the places in the implementation of Hand that will depend upon that member variable. To simplify matters we make the reasonable assumption that the class of the member variable will always have the properties of an STL container, i.e. we can assume things like size() and iterators are always available. In add() we additionally need to obtain non-const references to the count for a given card and to the total number of cards in the hand. In value() we need to determine the total number of cards in the hand and whether the container contains an ace. We can turn these four requirements into helper function templates. Function templates are particularly useful because of the way C++ deduces the instantiation required from the function arguments, avoiding the need for explicit instantiations.

// hand_implementation.h (include guard not
// shown)
#include "card.h"

namespace Blackjack {
  // Assume that Card_Container is usually a
  // std::map If something else is used,
  // e.g. std::vector, these function
  // templates would need to be specialised to
  // use std::find

  template< class Card_Container >
  unsigned int& hand_implementation_count(
              Card card,
              Card_Container& card_container) {
    return card_container[card].count;
  }

  template< class Card_Container >
  typename Card_Container::const_iterator
  hand_implementation_find(
              Card card,
              const Card_Container&
              card_container) {
    return card_container.find(card);
  }

  // non-const reference version of
  // number_of_cards
  template< class Card_Container >
  unsigned int&
      hand_implementation_number_of_cards
             (Card_Container& card_container) {
    return card_container.number_of_cards;
  }

  // const version of number_of_cards
  template< class Card_Container >
  unsigned int
      hand_implementation_number_of_cards
             (const Card_Container&
             card_container) {
    return card_container.number_of_cards;
  }
}

Less obviously, perhaps, Accumulate_Card_Value depends upon the type of values contained by the container, so is indirectly dependent upon the container. We therefore make it a nested class of the container like so:

// card_count_container.h (include guard not
// shown)
#include <map>
#include "card.h"
#include "card_values.h"

namespace Blackjack {
  struct Card_Count {
    unsigned int count;
    Card_Count() : count(0) {}
  };

  class Card_Count_Container
        : public std::map<Card, Card_Count> {
  public:
    unsigned int number_of_cards;
    // cached value as before
    class Accumulate_Card_Value {
      // same as before
    };
  };
}

We are now in a position to re-implement Hand as a class template. I follow the convention described by Dietmar Kuehl at the 2002 ACCU Conference of placing the implementation of the class template in a .tpp file. For this article I am going to put all the instantiations in a .cpp file in which this .tpp file is included. The alternative is to let clients include the .tpp file and perform the instantiations themselves. The .tpp file serves to keep both of these alternatives available to us.

// hand_type.h (include guard not shown)
#include "card.h"
#include "card_count_container.h"

namespace Blackjack {
  // Exceptions moved out of class into
  // namespace so that all instantiations
  // can share the exceptions
  class Four_Of_That_Card_Already
            : public std::exception {};
  class Five_Cards_Already
            : public std::exception {};
  class Fewer_Than_Two_Cards
            : public std::exception {};
  template< class Card_Container >
  class Hand_Type {
  public:
    // identical to public section of
    // non-template Hand class except
    // for exceptions as noted above
  protected:
    // get_card_values() is moved here in
    // case we want to provide the
    // implementation of this class template
    // in a header file
    const Card_Values& get_card_values() const;
  private:
    Card_Container cards;
  };

  // declare the valid instantiations
  typedef Hand_Type<Card_Count_Container>
                           Hand_No_Cached_Values;
}

// hand_type.tpp
#include "card_values.h"
#include "hand_implementation.h"
#include <numeric>

// default constructor, copy constructor,
// assignment, swap and destructor not
// shown
template< class Card_Container >
Blackjack::Hand_Type<Card_Container>::Hand_Type&
Blackjack::Hand_Type<Card_Container>::add(
                                     Card card)
         throw(Four_Of_That_Card_Already,
               Five_Cards_Already) {
  // use the helper to access the number of
  // cards
  unsigned int& number_of_cards =
    hand_implementation_number_of_cards(
                              cards);
  if(number_of_cards == 5) {
    throw Five_Cards_Already();
  }
  // use the helper to access the count
  unsigned int& count =
    hand_implementation_count(card, cards);
  if(count == 4) {
    throw Four_Of_That_Card_Already();
  }
  ++count;
  ++number_of_cards;
  return *this;
}

template< class Card_Container >
unsigned int Blackjack::Hand_Type<
                 Card_Container>::value() const
       throw(Fewer_Than_Two_Cards) {
  // use the helper to check the number of
  // cards
  if(hand_implementation_number_of_cards(
                              cards) < 2) {
    throw Fewer_Than_Two_Cards();
  }

  unsigned int hand_value =
    std::accumulate(
         cards.begin(),
         cards.end(),
         0,
         typename Card_Container::
              Accumulate_Card_Value(
                     get_card_values()));
  if( (hand_value < 12) &&
      // use the helper to check for an ace
      (hand_implementation_find(ace, cards)
              != cards.end()) ) {
    hand_value += 10;
  }
  return hand_value;
}

template< class Card_Container >
const Blackjack::Card_Values&
    Blackjack::Hand<Card_Container>::
                   get_card_values() const {
  static const Card_Values card_values;
  return card_values;
}

// hand_type.cpp
#include "hand_type.h"
#include "hand_type.tpp"
#include "card_count_container.h"

// instantiate the valid instantiations
template
Blackjack::Hand_Type<
              Blackjack::Card_Count_Container>;

So far so good, but we only have one instantiation at the moment. It may appear, therefore, that we haven't gained very much. In fact we have significantly improved the testability of the Hand class, a point to which I will return later.

Let's try and build a variant of Hand that looks up the value of a card when it is added to the hand, and caches that value. For this we need an additional helper function template that will set the value for a card. We need to specialise this new function template to do nothing when there is nowhere to cache the value (which is the case for our first instantiation). Hence:

// hand_implementation.h (include guard not
// shown)
#include "card.h"
#include "card_count_container.h"

namespace Blackjack {
  // hand_implementation_count(),
  // hand_implementation_find()
  // and
  // hand_implementation_number_of_cards()
  // as before
  template< class Card_Container >
  void hand_implementation_set_value(
                       Card card,
                       unsigned int value,
                       Card_Container& card_container) {
    card_container[card].value = value;
  }

  // specialisation to do nothing when there
  // is nowhere to cache the value
  template<>
  void hand_implementation_set_value(
                       Card card,
                       unsigned int value,
                       Card_Count_Container& card_container);
}

// hand_implementation.cpp
#include "hand_implementation.h"

template <>
void Blackjack::hand_implementation_set_value
                      (Card card,
                      unsigned int value,
                      Card_Count_Container& card_container) {}

The container class is:

// card_count_with_value_container.h
// (include guard not shown)
#include "card_count_container.h"

namespace Blackjack {
  struct Card_Count_With_Value
           : public Card_Count {
    unsigned int value;
    Card_Count_With_Value() : value(0){}
  };

  class Card_Count_With_Value_Container
           : public std::map<Card,
                    Card_Count_With_Value> {
  public:
    unsigned int number_of_cards; // as before
    class Accumulate_Card_Value {
    public:
      Accumulate_Card_Value(
             const Card_Values& /* unused */) {}
      unsigned int operator()
             (unsigned int accumulated_value,
             const std::map<Card,
             Card_Count_With_Value>::value_type&
                          card_data) {
        return accumulated_value +=
             (card_data.second.count *
             card_data.second.value);
      }
    };
  };
}

Notice that we have adjusted Accumulate_Card_Value operator() to take advantage of the cached values; the signature of its constructor is preserved, even though the Card_Values argument is unused, so that it will work with the Hand_Type we have already. We then modify Hand_Type::add() to call hand_implementation_set_value() at the appropriate point:

template< class Card_Container >
Blackjack::Hand_Type<Card_Container>::Hand_Type&
  Blackjack::Hand_Type<Card_Container>::add(
                                      Card card)
                throw(Four_Of_That_Card_Already,
                      Five_Cards_Already) {
    unsigned int& number_of_cards =
      hand_implementation_number_of_cards(cards);
    if(number_of_cards == 5) {
      throw Five_Cards_Already();
    } 
    unsigned int& count =
      hand_implementation_count(card, cards);
    if(count == 4) {
      throw Four_Of_That_Card_Already();
    }
    if(count == 0) {
      // use the helper to cache the card value
      hand_implementation_set_value(card,
                 get_card_values().lookup(card),
                 cards);
    }
    ++count;
    ++number_of_cards;
    return *this;
  }

We add the new instantiations:

// in hand_type.h
typedef
  Hand_Type<Card_Count_With_Value_Container>
  Hand_With_Cached_Values;
  // in hand_type.cpp
template Blackjack::Hand_Type<
  Blackjack::Card_Count_With_Value_Container>;

I have used long names for the instantiation typedefs in an attempt to document the characteristics of each variant. I am assuming that any particular client is likely to want only one variant, and will further typedef the variant required to a shorter name like Hand. (I have used Hand_Type for the class template so that the simple name Hand is available for clients to use).

The classic Bridge pattern, of course, has the implementation member variable as a pointer. This allows us to change the implementation without forcing clients to recompile. We cannot simply instantiate our existing Hand_Type with a pointer because its implementation does not dereference the member variable cards. The ideal solution would be to partially specialise Hand_Type for all instantiations taking a pointer as the template parameter, but this is not supported by Visual C++ 6.0. The workaround is to define another class template which I will name Hand_Bridge.

Bjarne Stroustrup [Stroustrup] writes that this was the approach he tried before deciding upon partial specialisation. He comments that he abandoned it because even good programmers forgot to use the templates designed to be instantiated with pointers. That problem does not arise in our case, though, because the compiler prevents us from instantiating Hand_Type with a pointer.

For this class template I will assume the existence of a suitable smart pointer (deep copy is appropriate - see Alexandrescu [Alexandrescu] for a full discussion of smart pointers):

// hand_bridge.h (include guard not shown)
#include "card.h"
#include "smart_pointer.h"

namespace Blackjack {
  template< class Card_Container >
  class Hand_Bridge {
  public:
    // identical to public section of
    // Hand_Type class
  private:
    Smart_Pointer<Card_Container> cards;
  };

  // Forward declaration is now sufficient in
  // the header
  class Card_Container_Implementation;
  // declare the valid instantiation
  typedef Hand_Bridge<
          Card_Container_Implementation> Hand;
}

// hand_bridge.tpp
#include "card_values.h"
#include "hand_implementation.h"
#include <numeric>

// default constructor, copy constructor,
// assignment, swap and destructor not shown
template< class Card_Container >
Blackjack::Hand_Bridge<Card_Container>::
    Hand_Bridge& Blackjack::Hand_Bridge<
        Card_Container>::add(Card card)
            throw(Four_Of_That_Card_Already,
                  Five_Cards_Already) {
  unsigned int& number_of_cards =
      hand_implementation_number_of_cards(
          cards->implementation());
  if(number_of_cards == 5) {
    throw Five_Cards_Already();
  }
  unsigned int& count = hand_implementation_count(
      card, cards->implementation());
  if(count == 4) {
    throw Four_Of_That_Card_Already();
  }
  if(count == 0) {
    hand_implementation_set_value(card,
        get_card_values().lookup(card),
    cards->implementation());
  }
  ++count;
  ++number_of_cards;
  return *this;
}

template< class Card_Container >
unsigned int Blackjack::Hand_Bridge<
    Card_Container>::value() const
      throw (Fewer_Than_Two_Cards) {
  if(hand_implementation_number_of_cards(
      cards->const_implementation()) < 2) {
    throw Fewer_Than_Two_Cards();
  }
  unsigned int hand_value =
      std::accumulate(cards->begin(),
           cards->end(), 0, typename
  Card_Container::Accumulate_Card_Value(
       get_card_values()));
  if( (hand_value < 12) &&
      (hand_implementation_find(ace,
          cards->const_implementation()) !=
              cards->end()) ) {
    hand_value += 10;
  }
  return hand_value;
}


//hand_bridge.cpp
#include "hand_bridge.h"
#include "hand_bridge.tpp"
#include "card_count_container.h"
#include "card_count_with_value_container.h"

namespace {
  template< class Card_Container >
  class Implementation : public Card_Container {
  public:
    Card_Container& implementation() {
      return *this;
    }
    const Card_Container&
    const_implementation() const {
      return *this;
    }
  };
}

#ifdef NO_CACHED_CARD_VALUES
class Blackjack::Card_Container_Implementation
    : public Implementation<
         Blackjack::Card_Count_Container> {};
#else // use the implementation with cached
      // card values
class Blackjack::Card_Container_Implementation
    : public Implementation<Blackjack::
        Card_Count_With_Value_Container> {};
#endif // NO_CACHED_CARD_VALUES

// instantiate the valid instantiation template
Blackjack::Hand_Bridge<
    Blackjack::Card_Container_Implementation>;

We can switch the implementation of Hand simply by recompiling hand_bridge.cpp with or without NO_CACHED_CARD_VALUES being defined; clients of Hand do not need to be recompiled.

You will no doubt be wondering why I have found it necessary to derive Card_Container_Implementation from the helper class template Implementation. The reason is so that the specialisations of the helper function templates are used. Take for example hand_implementation_set_value(). This has a specialisation for Card_Count_Container. If we simply called hand_implementation_set_value(*cards) the type of *cards is Card_Container_Implementation for which there is no specialisation (nor can there be since this is the class that changes depending upon our compilation settings); the compiler tries to use the unspecialised function template and fails to compile if NO_CACHED_CARD_VALUES is defined. In contrast, when we call hand_implementation_set_value(cards-> implementation()) the type of cards-> implementation() is Card_Count_Container (if NO_CACHED_CARD_VALUES is defined) and the compiler uses the specialised function template as required.

Implementing the Bridge pattern in the way I have described has the benefit of facilitating unit testing. It realises the Dependency Inversion Principle [DIP] because classes depend upon other classes only via template parameters. It is therefore easy to use stub versions of classes that a class under test depends upon: the class under test is simply instantiated with the stub. I believe that this realisation of the Dependency Inversion Principle by means of templates is an improvement upon the realisation using abstract base classes [Main] for a number of reasons:

In conclusion, the lack of support for partial specialisation in Visual C++ 6.0 is a serious inconvenience. However we should not underestimate the power and usefulness of full specialisation which it does support.