// Copyright David Abrahams 2008. Distributed under the Boost
// Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#define _GLIBCXX_DEBUG 1

#include "boost/iterator/iterator_categories.hpp"
#include "boost/type_traits/is_class.hpp"
#include "boost/static_assert.hpp"
#include "boost/iterator/iterator_adaptor.hpp"
#include "boost/iterator/counting_iterator.hpp"
#include "boost/iterator.hpp"
//#include <algorithm>
#include <numeric>
#include <cassert>
#include <iostream>
#include <iterator>

template <std::size_t N, class Predicate, class Iterator>
  class filter_strided_iterator;

  namespace detail
  {
    template <std::size_t N, class Predicate, class Iterator>
    struct filter_strided_iterator_base
    {
        typedef boost::iterator_adaptor<
            filter_strided_iterator<N, Predicate, Iterator>
          , Iterator
          , boost::use_default
          , typename boost::mpl::if_<
                boost::is_convertible<
                    typename boost::iterator_traversal<Iterator>::type
                  , boost::random_access_traversal_tag
                >
              , boost::bidirectional_traversal_tag
              , boost::use_default
            >::type
        > type;
    };
  }
  
template <std::size_t N, class Predicate, class Iterator>
  class filter_strided_iterator
    : public detail::filter_strided_iterator_base<N, Predicate, Iterator>::type
  {
      typedef typename detail::filter_strided_iterator_base<
          N, Predicate, Iterator
      >::type super_t;

      friend class boost::iterator_core_access;

   public:
      filter_strided_iterator() { }

      filter_strided_iterator(Predicate f, Iterator x, Iterator end_ = Iterator())
          : super_t(x), m_predicate(f), m_end(end_)
      {
          satisfy_predicate();
      }

      filter_strided_iterator(Iterator x, Iterator end_ = Iterator())
        : super_t(x), m_predicate(), m_end(end_)
      {
        // Pro8 is a little too aggressive about instantiating the
        // body of this function.
#if !BOOST_WORKAROUND(__MWERKS__, BOOST_TESTED_AT(0x3003))
          // Don't allow use of this constructor if Predicate is a
          // function pointer type, since it will be 0.
          BOOST_STATIC_ASSERT(boost::is_class<Predicate>::value);
#endif 
          satisfy_predicate();
      }

      template<class OtherIterator>
      filter_strided_iterator(
          filter_strided_iterator<N, Predicate, OtherIterator> const& t
          , typename boost::enable_if_convertible<OtherIterator, Iterator>::type* = 0
          )
          : super_t(t.base()), m_predicate(t.predicate()), m_end(t.end()) {}

      Predicate predicate() const { return m_predicate; }

      Iterator end() const { return m_end; }

   private:
      void increment()
      {
          if (m_end - this->base() > N)
          {
              this->base_reference() += N;
              satisfy_predicate();
          }              
          else
          {
              this->base_reference() = m_end;
          }
      }

      void decrement()
      {
        while(!this->m_predicate(*(this->base_reference() -= N))){};
      }

      void satisfy_predicate()
      {
          while (!this->m_predicate(*this->base()))
          {
              if (m_end - this->base() > N)
              {
                  this->base_reference() += N;
              }
              else
              {
                  this->base_reference() = m_end;
                  break;
              }
          }
      }
      
      // Probably should be the initial base class so it can be
      // optimized away via EBO if it is an empty class.
      Predicate m_predicate;
      Iterator m_end;
  };

template <std::size_t N, class Predicate, class I>
filter_strided_iterator<N,Predicate,I> make_filter_strided_iterator(I pos, I finish, Predicate pred)
{
    return filter_strided_iterator<N,Predicate,I>(pred, pos, finish);
}

template <std::size_t N, class Predicate, class I>
filter_strided_iterator<N,Predicate,I> make_filter_strided_iterator(I pos, I finish)
{
    return filter_strided_iterator<N,Predicate,I>(pos, finish);
}


struct is_odd
{
    template <class T>
    bool operator()(T x) const { return x % 2 != 0; }
};

int main()
{
    boost::counting_iterator<int> start(0);
    boost::counting_iterator<int> finish(13*7);

    int total = std::accumulate(
        make_filter_strided_iterator<5, is_odd>(start, finish),
        make_filter_strided_iterator<5, is_odd>(finish, finish), 0);

    int t2 = 0;
    for (int i = 0; i < 13*7; i+=5)
    {
        if (i % 2 != 0)
             t2 += i;
    }
    
    assert(total == t2);

    std::copy(
        make_filter_strided_iterator<5,is_odd>(start, finish),
        make_filter_strided_iterator<5,is_odd>(finish, finish),
        std::ostream_iterator<int>(std::cout, " "));
}