iteration_ranges.h

/*
Copyright CeleraOne GmbH 2012 - 2013
Distributed under the Boost Software License, Version 1.0:

Permission is hereby granted, free of charge, to any person or organization
obtaining a copy of the software and accompanying documentation covered by
this license (the "Software") to use, reproduce, display, distribute,
execute, and transmit the Software, and to prepare derivative works of the
Software, and to permit third-parties to whom the Software is furnished to
do so, all subject to the following:

The copyright notices in the Software and this entire statement, including
the above license grant, this restriction and the following disclaimer,
must be included in all copies of the Software, in whole or in part, and
all derivative works of the Software, unless such copies or derivative
works are solely in the form of machine-executable object code generated by
a source language processor.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
*/

#ifndef ITERATION_RANGES_FOR_RANGE_BASED_FOR_H
#define ITERATION_RANGES_FOR_RANGE_BASED_FOR_H

#include <utility>
#include <cstddef>

namespace
{

/** Stores a pair of inner_iterator begin and end iterators
 *  and converts them to wrap_iterator when begin() or end() are called.
 */
template <typename inner_iterator,
          template <class inner> class wrap_iterator>
class IteratorWrapperRange
{
public:
    typedef wrap_iterator<inner_iterator> iterator;

    IteratorWrapperRange(inner_iterator begin, inner_iterator end)
        : begin_(begin)
        , end_(end)
    {}

    iterator begin() const
    { return iterator(begin_); }
    iterator end() const
    { return iterator(end_); }

private:
    inner_iterator begin_;
    inner_iterator end_;
};

/** Basic counting iterator.
 */
template <typename T>
class RangeIterator
{
public:
    explicit RangeIterator(T i)
        : i_(i)
    {}

    T operator*() const
    { return i_; }
    bool operator!=(RangeIterator other) const
    { return i_ != other.i_; }
    RangeIterator& operator++()
    { ++i_; return *this; }

private:
    T i_;
};

/** Return value for Enumerate*Iterator::operator*().
 */
template <typename T>
struct EnumerateValue
{
    const size_t index;
    T value;
};

/** Enumerating iterator that tracks index and value
 *  and returns a copy of the value in operator*().
 */
template <typename Iter>
class EnumerateByValIterator
{

public:
    explicit EnumerateByValIterator(Iter it)
        : it_(it)
        , i_(0)
    {}

    auto operator*() const
        -> EnumerateValue<typename std::iterator_traits<Iter>::value_type>
    { return { i_, *it_ }; }
    bool operator!=(const EnumerateByValIterator& other) const
    { return it_ != other.it_; }
    EnumerateByValIterator& operator++()
    { ++i_; ++it_; return *this; }

private:
    Iter it_;
    size_t i_;
};

/** Enumerating iterator that tracks index and value
 *  and returns a reference of the value in operator*().
 */
template <typename Iter>
class EnumerateByRefIterator
{
public:
    explicit EnumerateByRefIterator(Iter it)
        : it_(it)
        , i_(0)
    {}

    auto operator*() const
        -> EnumerateValue<typename std::iterator_traits<Iter>::reference>
    { return { i_, *it_ }; }
    bool operator!=(const EnumerateByRefIterator& other) const
    { return it_ != other.it_; }
    EnumerateByRefIterator& operator++()
    { ++i_; ++it_; return *this; }

private:
    Iter it_;
    size_t i_;
};

/** Always returns the .first member of the underlying value.
 */
template <typename inner_iterator>
class FirstOfPairIterator
{
    inner_iterator it_;

public:
    explicit FirstOfPairIterator(inner_iterator it)
        : it_(it)
    {}

    auto operator*() const -> decltype((it_->first))
    { return it_->first; }
    bool operator!=(const FirstOfPairIterator & other) const
    { return it_ != other.it_; }
    FirstOfPairIterator& operator++()
    { ++it_; return *this; }
};

/** Always returns the .second member of the underlying value.
 */
template <typename inner_iterator>
class SecondOfPairIterator
{
    inner_iterator it_;

public:
    explicit SecondOfPairIterator(inner_iterator it)
        : it_(it)
    {}

    auto operator*() const -> decltype((it_->second))
    { return it_->second; }
    bool operator!=(const SecondOfPairIterator & other) const
    { return it_ != other.it_; }
    SecondOfPairIterator& operator++()
    { ++it_; return *this; }
};

} // anonymous namespace


/** Range for iterating over the values begin, ..., end-1.
 *
 * for (const auto i : range(3, 9))
 * is equivalent to
 * for (size_t i = 3, e = 9; i != e; ++i)
 *
 * T needs to support copying, ++T and T != T
 *
 * Example:
 *   for (const auto i : range(3, 9))
 *     writefln("%0", i); // prints 3, 4, 5, 6, 7, 8
 */
template <typename T>
auto range(T begin, T end)
    -> IteratorWrapperRange<T, RangeIterator>
{
    return { begin, end };
}

/** Equivalent to range(0, n)
 */
template <typename T>
auto range(T count)
    -> IteratorWrapperRange<T, RangeIterator>
{
    return range<T>(0, count);
}

/** Equivalent to range(0, container.size())
 */
template <typename T>
auto indices(T& container)
    -> IteratorWrapperRange<decltype(container.size()), RangeIterator>
{
    return range<decltype(container.size())>(0, container.size());
}

/** Range for iterating over index and value of a container.
 *
 * A copy of the value is made.
 *
 * Example:
 *   for (const auto e : enumerate_byval(vector))
 *     writefln("%0 is the %1th element", e.value, e.index)
 */
template <typename T>
auto enumerate_byval(T& container)
    -> IteratorWrapperRange<decltype(container.begin()),
                            EnumerateByValIterator>
{
    return { container.begin(), container.end() };
}

/** Range for iterating over index and value of a container.
 *
 * The value is accessed by reference.
 *
 * Example:
 *   for (const auto e : enumerate_byref(vector))
 *     e.value = e.index; // actually modifies vector!
 */
template <typename T>
auto enumerate_byref(T& container)
    -> IteratorWrapperRange<decltype(container.begin()),
                            EnumerateByRefIterator>
{
    return { container.begin(), container.end() };
}

/** Range for iterating over the first component of a std::pair-valued container.
 */
template <typename T>
auto keys(T& container)
    -> IteratorWrapperRange<decltype(container.begin()),
                            FirstOfPairIterator>
{
    return { container.begin(), container.end() };
}

/** Range for iterating over the second component of a std::pair-valued container.
 */
template <typename T>
auto values(T& container)
    -> IteratorWrapperRange<decltype(container.begin()),
                            SecondOfPairIterator>
{
    return { container.begin(), container.end() };
}

#endif // ITERATION_RANGES_FOR_RANGE_BASED_FOR_H