iterator.hpp

Go to the documentation of this file.

//============================================================================
// MCKL/include/mckl/core/iterator.hpp
//----------------------------------------------------------------------------
// MCKL: Monte Carlo Kernel Library
//----------------------------------------------------------------------------
// Copyright (c) 2013-2018, Yan Zhou
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
//   Redistributions of source code must retain the above copyright notice,
//   this list of conditions and the following disclaimer.
//
//   Redistributions in binary form must reproduce the above copyright notice,
//   this list of conditions and the following disclaimer in the documentation
//   and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS AS IS
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.
//============================================================================

#ifndef MCKL_CORE_ITERATOR_HPP
#define MCKL_CORE_ITERATOR_HPP

#include <mckl/internal/common.hpp>

namespace mckl {

template <typename Base>
class StepIterator
{
  public:
    using difference_type = std::make_signed_t<
        typename std::iterator_traits<Base>::difference_type>;
    using value_type = typename std::iterator_traits<Base>::value_type;
    using pointer = typename std::iterator_traits<Base>::pointer;
    using reference = typename std::iterator_traits<Base>::reference;
    using iterator_category =
        typename std::iterator_traits<Base>::iterator_category;

    StepIterator() noexcept(std::is_nothrow_default_constructible<Base>::value)
        : base_(Base()), step_(1)
    {
    }

    explicit StepIterator(Base base, difference_type step = 1) noexcept(
        std::is_nothrow_copy_constructible<Base>::value)
        : base_(base), step_(step)
    {
    }

    template <typename T>
    StepIterator(const StepIterator<T> &other) noexcept(
        std::is_nothrow_copy_constructible<Base>::value)
        : base_(other.base()), step_(other.step())
    {
    }

    Base base() const { return base_; }

    difference_type step() const { return step_; }

    reference operator*() const { return *base_; }

    Base operator->() const { return base_; }

    template <typename IntType>
    reference operator[](IntType n) const
    {
        return *((*this) + n);
    }

    friend bool operator==(
        const StepIterator &iter1, const StepIterator &iter2)
    {
        runtime_assert(iter1.step_ == iter2.step_,
            "Compare two StepIterator objects with different steps");

        return iter1.base_ == iter2.base_;
    }

    friend bool operator!=(
        const StepIterator &iter1, const StepIterator &iter2)
    {
        runtime_assert(iter1.step_ == iter2.step_,
            "Compare two StepIterator objects with different steps");

        return iter1.base_ != iter2.base_;
    }

    friend bool operator<(const StepIterator &iter1, const StepIterator &iter2)
    {
        runtime_assert(iter1.step_ == iter2.step_,
            "Compare two StepIterator objects with different steps");

        return iter1.base_ < iter2.base_;
    }

    friend bool operator<=(
        const StepIterator &iter1, const StepIterator &iter2)
    {
        runtime_assert(iter1.step_ == iter2.step_,
            "Compare two StepIterator objects with different steps");

        return iter1.base_ <= iter2.base_;
    }

    friend bool operator>(const StepIterator &iter1, const StepIterator &iter2)
    {
        runtime_assert(iter1.step_ == iter2.step_,
            "Compare two StepIterator objects with different steps");

        return iter1.base_ > iter2.base_;
    }

    friend bool operator>=(
        const StepIterator &iter1, const StepIterator &iter2)
    {
        runtime_assert(iter1.step_ == iter2.step_,
            "Compare two StepIterator objects with different steps");

        return iter1.base_ >= iter2.base_;
    }

    friend StepIterator &operator++(StepIterator &iter)
    {
        using std::advance;

        advance(iter.base_, iter.step_);

        return iter;
    }

    friend StepIterator operator++(StepIterator &iter, int)
    {
        StepIterator ret(iter);
        ++iter;

        return ret;
    }

    friend StepIterator &operator--(StepIterator &iter)
    {
        using std::advance;

        advance(iter.base_, -iter.step_);

        return iter;
    }

    friend StepIterator operator--(StepIterator &iter, int)
    {
        StepIterator ret(iter);
        --iter;

        return ret;
    }

    template <typename IntType>
    friend StepIterator operator+(const StepIterator &iter, IntType n)
    {
        using std::advance;

        StepIterator ret(iter);
        advance(ret.base_, static_cast<difference_type>(n) * ret.step_);

        return ret;
    }

    template <typename IntType>
    friend StepIterator operator+(IntType n, const StepIterator &iter)
    {
        return iter + n;
    }

    template <typename IntType>
    friend StepIterator operator-(const StepIterator &iter, IntType n)
    {
        return iter + (-static_cast<difference_type>(n));
    }

    template <typename IntType>
    friend StepIterator &operator+=(StepIterator &iter, IntType n)
    {
        return iter = iter + n;
    }

    template <typename IntType>
    friend StepIterator &operator-=(StepIterator &iter, IntType n)
    {
        return iter = iter - n;
    }

    friend difference_type operator-(
        const StepIterator &iter1, const StepIterator &iter2)
    {
        runtime_assert(iter1.step_ == iter2.step_,
            "Subtract two StepIterator objects with different steps");

        using std::distance;

        return distance(iter2.base_, iter1.base_) / iter1.step_;
    }

  private:
    Base base_;
    difference_type step_;
}; // class StepIterator

template <typename T, bool = std::is_integral<T>::value>
class Range;

template <typename IntType>
class Range<IntType, true>
{
  public:
    using size_type = std::size_t;
    using iterator = IntType;

    Range() noexcept : begin_(0), end_(0), grainsize_(1) {}

    Range(iterator begin, iterator end, size_type grainsize = 1)
        : begin_(begin), end_(end), grainsize_(grainsize)
    {
        runtime_assert(begin_ <= end_,
            "**Range::Range** used with invalid pair of integers");
    }

    Range(const Range &) = default;

    template <typename Split>
    Range(Range &other, Split)
        : begin_(other.begin_ + (other.end_ - other.begin_) / 2)
        , end_(other.end_)
        , grainsize_(other.grainsize_)
    {
        other.end_ = begin_;
    }

    size_type size() const { return empty() ? 0 : end_ - begin_; }

    size_type grainsize() const { return grainsize_; }

    bool empty() const { return begin_ >= end_; }

    bool is_divisible() const { return grainsize_ <= size(); }

    iterator begin() const { return begin_; }

    iterator end() const { return end_; }

  private:
    iterator begin_;
    iterator end_;
    size_type grainsize_;
}; // class Range

template <typename Iterator>
class Range<Iterator, false>
{
  public:
    using size_type = std::size_t;
    using iterator = Iterator;
    using value_type = typename std::iterator_traits<iterator>::value_type;
    using pointer = typename std::iterator_traits<iterator>::pointer;
    using reference = typename std::iterator_traits<iterator>::reference;

    Range() : begin_(iterator()), end_(begin_), grainsize_(1) {}

    Range(iterator begin, iterator end, size_type grainsize = 1)
        : begin_(begin), end_(end), grainsize_(grainsize)
    {
        using std::distance;

        runtime_assert(distance(begin_, end_) >= 0,
            "**Range::Range** used with invalid pair of iterators");
    }

    Range(const Range &) = default;

    template <typename Split>
    Range(Range &other, Split)
        : begin_(other.begin_), end_(other.end_), grainsize_(other.grainsize_)
    {
        using std::advance;
        using std::distance;

        advance(begin_, distance(begin_, end_) / 2);
        other.end_ = begin_;
    }

    size_type size() const
    {
        using std::distance;

        return empty() ? 0 : static_cast<size_type>(distance(begin_, end_));
    }

    size_type grainsize() const { return grainsize_; }

    bool empty() const
    {
        using std::distance;

        return distance(begin_, end_) <= 0;
    }

    bool is_divisible() const { return grainsize_ <= size(); }

    iterator begin() const { return begin_; }

    iterator end() const { return end_; }

    reference at(size_type n) const
    {
        runtime_assert<std::out_of_range>(
            n < size(), "**Range::at** index out of range");

        return operator[](n);
    }

    reference operator[](size_type n) const
    {
        using std::advance;

        iterator iter = begin_;
        advance(iter, n);

        return *iter;
    }

    reference front() const { return *begin_; }

    reference back() const { return *(--end_); }

  private:
    iterator begin_;
    iterator end_;
    size_type grainsize_;
}; // class Range

} // namespace mckl

#endif // MCKL_CORE_ITERATOR_HPP