#include <boost/stl_interfaces/iterator_interface.hpp>

#include <algorithm>
#include <array>

#include <cassert>


// This is a minimal random access iterator.  It uses default template
// parameters for most stl_interfaces template parameters.
struct simple_random_access_iterator
    : boost::stl_interfaces::iterator_interface<
#if !BOOST_STL_INTERFACES_USE_DEDUCED_THIS
          simple_random_access_iterator,
#endif
          std::random_access_iterator_tag,
          int>
{
    // This default constructor does not initialize it_, since that's how int *
    // works as well.  This allows optimum performance in code paths where
    // initializing a single pointer may be measurable.  It is also a
    // reasonable choice to initialize with nullptr.
    simple_random_access_iterator() noexcept {}
    simple_random_access_iterator(int * it) noexcept : it_(it) {}

    int & operator*() const noexcept { return *it_; }
    simple_random_access_iterator & operator+=(std::ptrdiff_t i) noexcept
    {
        it_ += i;
        return *this;
    }
    auto operator-(simple_random_access_iterator other) const noexcept
    {
        return it_ - other.it_;
    }

private:
    int * it_;
};


int main()
{
    std::array<int, 10> ints = {{0, 2, 1, 3, 4, 5, 7, 6, 8, 9}};

    simple_random_access_iterator first(ints.data());
    simple_random_access_iterator last(ints.data() + ints.size());
    std::sort(first, last);
    assert(ints == (std::array<int, 10>{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}}));
}

#include <boost/stl_interfaces/iterator_interface.hpp>

#include <algorithm>
#include <array>
#include <numeric>

#include <cassert>


// This is a random access iterator templated on a value type.  The ValueType
// template parameter allows us easily to define const and non-const iterators
// from the same template.
template<typename ValueType>
struct random_access_iterator : boost::stl_interfaces::iterator_interface<
#if !BOOST_STL_INTERFACES_USE_DEDUCED_THIS
                                    random_access_iterator<ValueType>,
#endif
                                    std::random_access_iterator_tag,
                                    ValueType>
{
    static_assert(std::is_object<ValueType>::value, "");

    // Default constructor.
    constexpr random_access_iterator() noexcept {}

    // Construction from an underlying pointer.
    constexpr random_access_iterator(ValueType * it) noexcept : it_(it) {}

    // Implicit conversion from an existing random_access_iterator with a
    // possibly different value type.  The enable_if logic here just enforces
    // that this constructor only participates in overload resolution when the
    // expression it_ = other.it_ is well-formed.
    template<
        typename ValueType2,
        typename E = std::enable_if_t<
            std::is_convertible<ValueType2 *, ValueType *>::value>>
    constexpr random_access_iterator(
        random_access_iterator<ValueType2> other) noexcept :
        it_(other.it_)
    {}

    constexpr ValueType & operator*() const noexcept { return *it_; }
    constexpr random_access_iterator & operator+=(std::ptrdiff_t i) noexcept
    {
        it_ += i;
        return *this;
    }
    constexpr auto operator-(random_access_iterator other) const noexcept
    {
        return it_ - other.it_;
    }

private:
    ValueType * it_;

    // This friendship is necessary to enable the implicit conversion
    // constructor above to work.
    template<typename ValueType2>
    friend struct random_access_iterator;
};

using iterator = random_access_iterator<int>;
using const_iterator = random_access_iterator<int const>;

int main()
{
    std::array<int, 10> ints = {{0, 2, 1, 3, 4, 5, 7, 6, 8, 9}};

    // Create and use two mutable iterators.
    iterator first(ints.data());
    iterator last(ints.data() + ints.size());
    std::sort(first, last);
    assert(ints == (std::array<int, 10>{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}}));

    // Create and use two constant iterators, one from an existing mutable
    // iterator.
    std::array<int, 10> int_sums;
    const_iterator cfirst(ints.data());
    const_iterator clast = last;
    std::partial_sum(cfirst, clast, int_sums.begin());
    assert(int_sums == (std::array<int, 10>{{0, 1, 3, 6, 10, 15, 21, 28, 36, 45}}));
}

#include <boost/stl_interfaces/iterator_interface.hpp>

#include <algorithm>
#include <array>
#include <tuple>

#include <cassert>


// This is a zip iterator, meaning that it iterates over a notional sequence
// of pairs that is formed from two actual sequences of scalars.  To make this
// iterator writable, it needs to have a reference type that is not actually a
// reference -- the reference type is a pair of references, std::tuple<int &,
// int &>.
struct zip_iterator : boost::stl_interfaces::proxy_iterator_interface<
#if !BOOST_STL_INTERFACES_USE_DEDUCED_THIS
                      zip_iterator,
#endif
                      std::random_access_iterator_tag,
                      std::tuple<int, int>,
                      std::tuple<int &, int &>>
{
    constexpr zip_iterator() noexcept : it1_(), it2_() {}
    constexpr zip_iterator(int * it1, int * it2) noexcept : it1_(it1), it2_(it2)
    {}

    constexpr std::tuple<int &, int &> operator*() const noexcept
    {
        return std::tuple<int &, int &>{*it1_, *it2_};
    }
    constexpr zip_iterator & operator += (std::ptrdiff_t i) noexcept
    {
        it1_ += i;
        it2_ += i;
        return *this;
    }
    constexpr auto operator-(zip_iterator other) const noexcept
    {
        return it1_ - other.it1_;
    }

private:
    int * it1_;
    int * it2_;
};


namespace std {
    // Required for std::sort to work with zip_iterator.  Without this
    // overload, std::sort eventually tries to call std::swap(*it1, *it2),
    // *it1 and *it2 are rvalues, and std::swap() takes mutable lvalue
    // references.  That makes std::swap(*it1, *it2) ill-formed.
    //
    // Note that this overload does not conflict with any other swap()
    // overloads, since this one takes rvalue reference parameters.
    //
    // Also note that this overload has to be in namespace std only because
    // ADL cannot find it anywhere else.  If
    // zip_iterator::reference/std::tuple's template parameters were not
    // builtins, this overload could be in whatever namespace those template
    // parameters were declared in.
    void swap(zip_iterator::reference && lhs, zip_iterator::reference && rhs)
    {
        using std::swap;
        swap(std::get<0>(lhs), std::get<0>(rhs));
        swap(std::get<1>(lhs), std::get<1>(rhs));
    }
}


int main()
{
    std::array<int, 10> ints = {{2, 0, 1, 5, 3, 6, 8, 4, 9, 7}};
    std::array<int, 10> ones = {{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}};

    {
        std::array<std::tuple<int, int>, 10> const result = {{
            {2, 1},
            {0, 1},
            {1, 1},
            {5, 1},
            {3, 1},
            {6, 1},
            {8, 1},
            {4, 1},
            {9, 1},
            {7, 1},
        }};

        zip_iterator first(ints.data(), ones.data());
        zip_iterator last(ints.data() + ints.size(), ones.data() + ones.size());
        assert(std::equal(first, last, result.begin(), result.end()));
    }

    {
        std::array<std::tuple<int, int>, 10> const result = {{
            {0, 1},
            {1, 1},
            {2, 1},
            {3, 1},
            {4, 1},
            {5, 1},
            {6, 1},
            {7, 1},
            {8, 1},
            {9, 1},
        }};
        zip_iterator first(ints.data(), ones.data());
        zip_iterator last(ints.data() + ints.size(), ones.data() + ones.size());
        assert(!std::equal(first, last, result.begin(), result.end()));
        std::sort(first, last);
        assert(std::equal(first, last, result.begin(), result.end()));
    }
}

#include <boost/stl_interfaces/iterator_interface.hpp>

#include <algorithm>
#include <vector>

#include <cassert>


// This is an output iterator that holds a reference to a container, and calls
// push_back() on that container when it is written to, just like
// std::back_insert_iterator.  This is not a lot less code to write than the
// implementation of std::back_insert_iterator, but it demonstrates that
// iterator_interface is flexible enough to handle this odd kind of iterator.
template<typename Container>
struct back_insert_iterator : boost::stl_interfaces::iterator_interface<
#if !BOOST_STL_INTERFACES_USE_DEDUCED_THIS
                                  back_insert_iterator<Container>,
#endif
                                  std::output_iterator_tag,
                                  typename Container::value_type,
                                  back_insert_iterator<Container> &>
{
    // For concept requirements.
    back_insert_iterator() : c_(nullptr) {}

    // Construct from a container.
    explicit back_insert_iterator(Container & c) : c_(std::addressof(c)) {}

    // When writing to *this, copy v into the container via push_back().
    back_insert_iterator & operator=(typename Container::value_type const & v)
    {
        c_->push_back(v);
        return *this;
    }
    // When writing to *this, move v into the container via push_back().
    back_insert_iterator & operator=(typename Container::value_type && v)
    {
        c_->push_back(std::move(v));
        return *this;
    }

    // Dereferencing *this just returns a reference to *this, so that the
    // expression *it = value uses the operator=() overloads above.
    back_insert_iterator & operator*() { return *this; }
    // There is no underlying sequence over which we are iterating, so there's
    // nowhere to go in next().  Do nothing.
    back_insert_iterator & operator++() { return *this; }

    using base_type = boost::stl_interfaces::iterator_interface<
#if !BOOST_STL_INTERFACES_USE_DEDUCED_THIS
        back_insert_iterator<Container>,
#endif
        std::output_iterator_tag,
        typename Container::value_type,
        back_insert_iterator<Container> &>;
    using base_type::operator++;

private:
    Container * c_;
};

// A convenience function that creates a back_insert_iterator<Container>.
template<typename Container>
back_insert_iterator<Container> back_inserter(Container & c)
{
    return back_insert_iterator<Container>(c);
}


int main()
{
    std::vector<int> ints = {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}};
    std::vector<int> ints_copy;
    std::copy(ints.begin(), ints.end(), ::back_inserter(ints_copy));
    assert(ints_copy == ints);
}

#include <boost/stl_interfaces/iterator_interface.hpp>

#include <algorithm>
#include <list>
#include <vector>

#include <cassert>


// In all the previous examples, we only had to implement a subset of the six
// possible user-defined basis operations that was needed for one particular
// iterator concept.  For reverse_iterator, we want to support bidirectional,
// random access, and contiguous iterators.  We therefore need to provide all
// the basis operations that might be needed.
template<typename BidiIter>
struct reverse_iterator
    : boost::stl_interfaces::iterator_interface<
#if !BOOST_STL_INTERFACES_USE_DEDUCED_THIS
          reverse_iterator<BidiIter>,
#endif
#if 201703L < __cplusplus && defined(__cpp_lib_ranges)
          boost::stl_interfaces::v2::v2_dtl::iter_concept_t<BidiIter>,
#else
          typename std::iterator_traits<BidiIter>::iterator_category,
#endif
          typename std::iterator_traits<BidiIter>::value_type>
{
    reverse_iterator() : it_() {}
    reverse_iterator(BidiIter it) : it_(it) {}

    using ref_t = typename std::iterator_traits<BidiIter>::reference;
    using diff_t = typename std::iterator_traits<BidiIter>::difference_type;

    ref_t operator*() const { return *std::prev(it_); }

    // These three are used only when BidiIter::iterator_category is
    // std::bidirectional_iterator_tag.
    bool operator==(reverse_iterator other) const { return it_ == other.it_; }

    // Even though iterator_interface-derived bidirectional iterators are
    // usually given operator++() and operator--() members, it turns out that
    // operator+=() below amounts to the same thing.  That's good, since
    // having operator++() and operator+=() in this class would have lead to
    // ambiguities in iterator_interface.

    // These two are only used when BidiIter::iterator_category is
    // std::random_access_iterator_tag or std::contiguous_iterator_tag.  Even
    // so, they need to compile even when BidiIter::iterator_category is
    // std::bidirectional_iterator_tag.  That means we have to use
    // std::distance() and std::advance() instead of operator-() and
    // operator+=().
    //
    // Don't worry, the O(n) bidirectional implementations of std::distance()
    // and std::advance() are dead code, because compare() and advance() are
    // never even called when BidiIter::iterator_category is
    // std::bidirectional_iterator_tag.
    diff_t operator-(reverse_iterator other) const
    {
        return -std::distance(other.it_, it_);
    }
    reverse_iterator & operator+=(diff_t n)
    {
        std::advance(it_, -n);
        return *this;
    }

    // No need for a using declaration to make
    // iterator_interface::operator++(int) visible, because we're not defining
    // operator++() in this template.

private:
    BidiIter it_;
};

using rev_bidi_iter = reverse_iterator<std::list<int>::iterator>;
using rev_ra_iter = reverse_iterator<std::vector<int>::iterator>;


int main()
{
    {
        std::list<int> ints = {4, 3, 2};
        std::list<int> ints_copy;
        std::copy(
            rev_bidi_iter(ints.end()),
            rev_bidi_iter(ints.begin()),
            std::back_inserter(ints_copy));
        std::reverse(ints.begin(), ints.end());
        assert(ints_copy == ints);
    }

    {
        std::vector<int> ints = {4, 3, 2};
        std::vector<int> ints_copy(ints.size());
        std::copy(
            rev_ra_iter(ints.end()),
            rev_ra_iter(ints.begin()),
            ints_copy.begin());
        std::reverse(ints.begin(), ints.end());
        assert(ints_copy == ints);
    }

    {
        using rev_ptr_iter = reverse_iterator<int *>;

        int ints[3] = {4, 3, 2};
        int ints_copy[3];
        std::copy(
            rev_ptr_iter(std::end(ints)),
            rev_ptr_iter(std::begin(ints)),
            std::begin(ints_copy));
        std::reverse(std::begin(ints), std::end(ints));
        assert(std::equal(
            std::begin(ints_copy),
            std::end(ints_copy),
            std::begin(ints),
            std::end(ints)));
    }
}