#include <iostream>

#include <vector>
#include <list>

#include <boost/type_traits.hpp>
#include <boost/iterator_adaptors.hpp>

#include "boost/variant.hpp"

#include "boost/apply_visitor.hpp"
#include "boost/static_visitor.hpp"
#include "boost/extract.hpp"


struct do_increment: boost::static_visitor<void>
{
  template<typename T>
  void operator()( T& t ) const
    { ++t; }
};


struct do_decrement: boost::static_visitor<void>
{
  template<typename T>
  void operator()( T& t ) const
    { --t; }
};


template< typename Difference >
struct do_advance: boost::static_visitor<void>
{
  do_advance( const Difference& theN ): n ( theN )
    { }

  template<typename T>
  void operator()( T& t ) const
    { t += n; }

private:
  Difference n;
};


template< typename Reference >
struct do_dereference: boost::static_visitor<Reference>
{
  template<typename T>
  Reference operator()( const T& t ) const
    { return *t; }
};


template< typename VisitorT, typename T0, typename T1 >
struct visit_helper
{
  typedef typename VisitorT::result_type result_type;

  visit_helper( const VisitorT& theVisit = VisitorT() )
    : visit( theVisit )
    { } 

  result_type operator()( T0& t0 )
    { return visit( t0 ); }

  result_type operator()( const T0& t0 ) const
    { return visit( t0 ); }

  result_type operator()( boost::variant< T0, T1 >& v )
    { return boost::apply_visitor( visit, v ); }

  result_type operator()( const boost::variant< T0, T1 >& v ) const
    { return boost::apply_visitor( visit, v ); }

private:
  VisitorT visit;
};


template< typename T0, typename T1 >
struct equality_helper
{
  bool operator()( const T0& t0, const T0& t1 ) const
  { return t0 == t1; }

  //### Using references caused check() to fail / a bad_extract() exception?!
  //bool operator()( const boost::variant<T0,T1>& v0, const boost::variant<T0,T1>& v1 ) const
  bool operator()( boost::variant<T0,T1> v0, boost::variant<T0,T1> v1 ) const
  { 
    if( v0.which() != v1.which() ) return false;
    try 
      {
      switch( v0.which() )
         {
         case 0: 
           {
           boost::extract<T0> extT0v0( v0 );
           boost::extract<T0> extT0v1( v1 );

           if( !extT0v0.check() || !extT0v1.check() )
             { return false; }

           return( extT0v0() == extT0v1() ); 
           }
           break;
         case 1: return( boost::extract<T1>( v0 )() == boost::extract<T1>( v1 )() ); break;
         default: return false;
         }
      }
    catch( boost::bad_extract& exc )
      { 
        std::cerr << exc.what();
        return false; 
      }
  }
};


template< typename Iter0, typename Iter1 >
class variant_iterator_policy: public boost::default_iterator_policies 
{
public:
  // Constructors
  variant_iterator_policy() 
  { }

  template< class AdaptedT >
  typename AdaptedT::reference dereference( const AdaptedT& x ) const
  { 
    typedef do_dereference< typename AdaptedT::reference > do_dereference_type;
    return visit_helper< do_dereference_type, Iter0, Iter1 >()( x.base() );
  }


  template< typename AdaptedT >
  void increment( AdaptedT& x )
    { 
      //boost::apply_visitor( do_increment(), x.base() ); 
      visit_helper< do_increment, Iter0, Iter1 >()( x.base() );
    }

  template< typename AdaptedT >
  void decrement( AdaptedT& x )
    { 
      //boost::apply_visitor( do_decrement(), x.base() ); 
      visit_helper< do_decrement, Iter0, Iter1 >()( x.base() );
    }

  template< typename AdaptedT >
  void advance( AdaptedT& x, typename AdaptedT::difference_type n )
    {
      typedef do_advance< typename AdaptedT::difference_type > do_advance_type;
      visit_helper< do_advance_type, Iter0, Iter1 >( do_advance_type(n) )( x.base() );
    }
  
  template<class AdaptedT1, class AdaptedT2 > 
  bool equal( const AdaptedT1& x, const AdaptedT2& y ) const
  { 
    return equality_helper< Iter0, Iter1 >()( x.base(), y.base() );
  }

private:

};


template< class T0, class T1 >
struct variant_helper
{
  template< bool B >
  struct select { typedef boost::variant< T0, T1 > ret; };

  template<>
  struct select< true > { typedef T0 ret; };

  typedef select< boost::is_same< T0, T1 >::value >::ret type;
};


template< typename Iter0,
          typename Iter1,
          typename Value0     = boost::detail::iterator_traits<Iter0>::value_type,
          typename Value1     = boost::detail::iterator_traits<Iter1>::value_type,
          typename Reference0 = boost::detail::iterator_defaults<Iter0,Value0>::reference,
          typename Reference1 = boost::detail::iterator_defaults<Iter1,Value1>::reference,
          typename Pointer0   = boost::detail::iterator_defaults<Iter0,Value0>::pointer,
          typename Pointer1   = boost::detail::iterator_defaults<Iter1,Value1>::pointer,
          typename Category0  = boost::detail::iterator_traits<Iter0>::iterator_category,
          typename Category1  = boost::detail::iterator_traits<Iter1>::iterator_category,
          typename Distance0  = boost::detail::iterator_traits<Iter0>::difference_type,
          typename Distance1  = boost::detail::iterator_traits<Iter1>::difference_type
>
struct variant_iterator_generator 
{
  typedef variant_helper< Iter0, Iter1 >::type          base_type;
  typedef variant_iterator_policy< Iter0, Iter1 >       policies_type;

  typedef variant_helper< Value0, Value1 >::type        value_type;

  //### variant does NOT accept references
  //typedef boost::variant< Reference0, Reference1 >   reference; 
  typedef variant_helper< Value0, Value1 >::type        reference;

  typedef variant_helper< Pointer0, Pointer1 >::type    pointer;

  typedef variant_helper< Category0, Category1 >::type  category;
  typedef variant_helper< Distance0, Distance1 >::type  distance;
    
  typedef boost::iterator_adaptor<
            base_type, policies_type,
            value_type, reference, pointer, category, distance >   type;
};



int main( void )
{
  typedef std::list<int> U;
  typedef std::vector<int> V;

  U u;
  for( int i = 42; i < 51; ++i ) { u.push_back( i ); }

  V v;
  for( int i = 0; i < 10; ++i ) { v.push_back( i ); }

  typedef variant_iterator_generator< 
      typename U::iterator,        typename V::iterator,
      typename U::value_type,      typename V::value_type,
      typename U::reference,       typename V::reference,
      typename U::pointer,         typename V::pointer,
   boost::detail::iterator_traits< typename U::iterator >::iterator_category,
   boost::detail::iterator_traits< typename V::iterator >::iterator_category,
      typename U::difference_type, typename V::difference_type
    >::type variant_iter_type;

  variant_iter_type it( u.begin() );
  variant_iter_type e( u.end() );

  for( ; it != e; ++it )
    { std::cout << *it << " "; }
  std::cout << std::endl;

  it = variant_iter_type( v.begin() );
  e  = variant_iter_type( v.end() );

  for( ; it != e; ++it )
    { std::cout << *it << " "; }
  std::cout << std::endl;

  return 0;
}