// copyright christoph.heindl@gmail.com 2009

#ifndef WIDEST_CONVERTIBLE_HPP
#define WIDEST_CONVERTIBLE_HPP

#include <boost/iterator/iterator_categories.hpp>
#include <boost/static_assert.hpp>
#include <boost/math/common_factor_ct.hpp>

// Relevant includes for working with sequences
#include <boost/mpl/if.hpp>
#include <boost/mpl/empty.hpp>
#include <boost/mpl/fold.hpp>

namespace boost {
  namespace detail {

    // Defines the forward mapping of category to constant id
    template<class TraversalCategory>
    struct traversal_category_to_id {
      BOOST_STATIC_ASSERT((false));
    };

    // Defines the backward mapping of constant id to category type
    template<unsigned long Id>
    struct id_to_traversal_category {
      BOOST_STATIC_ASSERT((false));
    };

    // Generates a forward and backward mapping for a given category and id
    // Mappings a template specializations of id_to_traversal_category and
    // traversal_category_to_id.
    #define BOOST_TRAVERSAL_CATEGORY_ID_MAPPING(Cat, Id) \
      template<> \
      struct traversal_category_to_id < Cat > { \
        static unsigned long const value = Id; \
      }; \
      template<> \
      struct id_to_traversal_category < Id > { \
        typedef Cat type; \
      };

    // Carefully choose the mappings
    BOOST_TRAVERSAL_CATEGORY_ID_MAPPING(::boost::no_traversal_tag, 1)
    BOOST_TRAVERSAL_CATEGORY_ID_MAPPING(::boost::incrementable_traversal_tag, 2)
    BOOST_TRAVERSAL_CATEGORY_ID_MAPPING(::boost::single_pass_traversal_tag, 4)
    BOOST_TRAVERSAL_CATEGORY_ID_MAPPING(::boost::forward_traversal_tag, 8)
    BOOST_TRAVERSAL_CATEGORY_ID_MAPPING(::boost::bidirectional_traversal_tag, 16)
    BOOST_TRAVERSAL_CATEGORY_ID_MAPPING(::boost::random_access_traversal_tag, 32)
  }

  // Derive the widest convertible iterator traversal category of
  // two given traversal categories.
  //
  // The problem is reformulated as a a 'greatest common divisor' problem by
  // building a mapping from category to ids. The ids are chosen to be the powers of two, where
  // 2^0 is assigned to incrementable_traversal_tag, 2^1 to single_pass_traversal_tag, etc.
  template<class FirstCat, class SecondCat>
  struct widest_convertible_binary {
    typedef typename detail::id_to_traversal_category<
      math::static_gcd<
        detail::traversal_category_to_id<FirstCat>::value,
        detail::traversal_category_to_id<SecondCat>::value
      >::value
    >::type type;
  };

  template<class Sequence>
  struct widest_convertible_sequence {
    typedef typename boost::mpl::if_<
      boost::mpl::empty<Sequence>,
      boost::no_traversal_tag,
      typename boost::mpl::fold<
        Sequence,
        boost::random_access_traversal_tag,
        boost::widest_convertible_binary<boost::mpl::_1, boost::mpl::_2>
      >::type
    >::type type;
  };
}


#endif //TRAVERSAL_CATEGORIES_HPP