Figure 3: Finding the minimum default iterator tag category

//
// Combine traits computing the common denominator of two types.
// This works via a mapping to integers, taking the minimum, 
// and mapping back to corresponding types.
//

// Compute the minimum of two integers at compile time.
template<int a, int b> 
struct min_traits 
{ enum { x = a < b ? a: b }; };

// Given two types and priority mappings to and from integers,
// compute the lower type.
template <class A, class B, template<class T> class map,
          template<class T, int x> class inv>
struct combine_traits {
   typedef typename 
      inv<A, min_traits<map<A>::x, map<B>::x>::x>::type type;
};

// Mapping iterator tags to integers.
template <class T> 
struct iterator_tag_mapping 
{ enum { x = 0 }; };

template<> 
struct iterator_tag_mapping<std::input_iterator_tag>
{ enum { x = 1 }; };

template<> 
struct iterator_tag_mapping<std::forward_iterator_tag> 
{  enum { x = 2 }; };

template<> 
struct iterator_tag_mapping<std::bidirectional_iterator_tag> 
{ enum { x = 3 }; };

template<> 
struct iterator_tag_mapping<std::random_access_iterator_tag> 
{ enum { x = 4 }; };

// Mapping integers to iterator tags.
template<class T, int x> 
struct mapping_iterator_tag 
{ typedef void type; };

template<class T> 
struct mapping_iterator_tag<T,1>   
{ typedef std::input_iterator_tag type; };

template<class T> 
struct mapping_iterator_tag<T,2>   
{ typedef std::forward_iterator_tag type; };

template<class T> 
struct mapping_iterator_tag<T,3>   
{ typedef std::bidirectional_iterator_tag type; };

template<class T> 
struct mapping_iterator_tag<T,4>   
{ typedef std::random_access_iterator_tag type; };

// Given two iterator categories, compute the lower one.
template <class cat_a, class cat_b>
struct combine_iterator_categories
  : public combine_traits<
             cat_a,
             cat_b,
             iterator_tag_mapping,
             mapping_iterator_tag
           > 
{};

// Given two iterator types, compute the lower category.
template<class A, class B>
struct combine_iterator_tags
  : public combine_traits<
             iterator_traits<A>
               ::iterator_category,
             iterator_traits<B>
               ::iterator_category,
             iterator_tag_mapping,
             mapping_iterator_tag
           > 
{};