#ifndef ALGORITHMS_ITERATOR_H
#define ALGORITHMS_ITERATOR_H

#include <iterator>
#include <iostream>

/// brief Random access const_iterator over a container with index operation
/// note no copy assignment / move assignment.
template<typename A>
class const_index_iterator {
    typedef const_index_iterator<A> self_type;
public:
    typedef typename A::value_type value_type;
    typedef value_type& reference;
    typedef value_type* pointer;
    typedef typename A::difference_type difference_type;
    typedef std::random_access_iterator_tag iterator_category;

    const_index_iterator(const A& a, const typename A::size_type ix)
            : a_(a), ix_(ix) {
        // + 1 because of end().
        assert(ix_ < a_.size() + 1 && ix_ >= 0 && "Index is out of bounds.");
    }

    // Arithmetic
    self_type operator++() {
        ++ix_;
        check_ix();
        return *this;
    }

    self_type operator++(int dummy) { return operator++(); }

    self_type& operator+=(difference_type n) {
        ix_ += n;
        check_ix();
        return *this;
    }

    self_type operator--() {
        --ix_;
        check_ix();
        return *this;
    }

    self_type operator--(int dummy) { return operator--(); }

    self_type& operator-=(difference_type n) {
        return operator+=(-n);
    }

    friend const_index_iterator<A> operator+(const const_index_iterator<A>& a,
                                             const difference_type n) {
        return const_index_iterator<A>(a.a_, a.ix_ + n);
    }

    friend difference_type operator-(const const_index_iterator<A>& a,
                                     const const_index_iterator<A>& b) {
        return a.ix_ - b.ix_;
    }

    // Dereference
    const value_type& operator[](const difference_type ix) const {
        check_dereference(ix);
        return a_[ix];
    }

    const value_type& operator*() const {
        check_dereference();
        return a_[ix_];
    }

    const value_type* operator->() const {
        check_dereference();
        assert(ix_ < a_.size());
        return &(a_[ix_]);
    }

    // Logical
    bool operator==(const self_type& rhs) const { return ix_ == rhs.ix_; }

    bool operator!=(const self_type& rhs) const { return !operator==(rhs); }

    bool operator>(const self_type& rhs) const { return ix_ > rhs.ix_; }

    bool operator<=(const self_type& rhs) const { return !operator>(rhs); }

    bool operator<(const self_type& rhs) const { return ix_ < rhs.ix_; }

    bool operator>=(const self_type& rhs) const { return !operator<(rhs); }

protected:
    void check_ix() const { check_ix(ix_); }

    void check_ix(const difference_type ix) const {
        assert(ix < a_.size() + 1 && ix >= 0 && "Index is out of bounds.");
    }

    void check_dereference() const { check_dereference(ix_); }

    void check_dereference(const difference_type ix) const {
        assert(ix < a_.size() && ix >= 0
               && "The iterator cannot be dereferenced because it is out of "
                       "bounds");
    }

    const A& a_;
    typename A::size_type ix_;
};


template<typename A>
const_index_iterator<A> operator+(const typename
                                  const_index_iterator<A>::difference_type n,
                                  const const_index_iterator<A>& a) {
    return operator+(a, n);
}

template<typename A>
const_index_iterator<A> operator-(const const_index_iterator<A>& a,
                                  const typename
                                  const_index_iterator<A>::difference_type n) {
    return operator+(a, -n);
}

/// brief Random access const_iterator over a container with index operation
/// note no copy assignment / move assignment.
template<typename A>
class index_iterator : public const_index_iterator<A> {
    typedef const_index_iterator<A> Base;
    typedef index_iterator<A> self_type;
public:
    typedef typename A::value_type value_type;
    typedef value_type& reference;
    typedef value_type* pointer;
    typedef typename A::difference_type difference_type;
    typedef std::random_access_iterator_tag iterator_category;

    index_iterator(A& a, const typename A::size_type ix)
            : Base::const_index_iterator(a, ix) {}

    // Arithmetic
    friend index_iterator<A> operator+(const index_iterator<A>& a,
                                       const difference_type n) {
        return index_iterator<A>(a.mutable_a(), a.ix_ + n);
    }

    friend difference_type operator-(const index_iterator<A>& a,
                                     const index_iterator<A>& b) {
        return a.ix_ - b.ix_;
    }

    // Dereference
    using Base::operator*;
    using Base::operator->;

    value_type& operator[](const difference_type ix) const {
        check_dereference(ix);
        return mutable_a()[ix];
    }

    value_type& operator*() const {
        check_dereference();
        return mutable_a()[ix_];
    }

    value_type* operator->() const {
        check_dereference();
        return &(mutable_a()[ix_]);
    }

private:
    A& mutable_a() const { return const_cast<A&>(a_); }
    using Base::a_;
    using Base::ix_;
    using Base::check_dereference;

};

template<typename A>
index_iterator<A> operator+(const typename
                            index_iterator<A>::difference_type n,
                            const index_iterator<A>& a) {
    return operator+(a, n);
}

template<typename A>
index_iterator<A> operator-(const index_iterator<A>& a,
                            const typename
                            index_iterator<A>::difference_type n) {
    return operator+(a, -n);
}

template<typename A>
typename A::difference_type distance(const const_index_iterator<A>& a,
                                     const const_index_iterator<A>& b) {
    return a - b;
}

#endif //ALGORITHMS_ITERATOR_H