SVIterator.h

Go to the documentation of this file.

/*
 *  This is free software: you can redistribute it and/or modify it
 *  under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  any later version.
 *  The software is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *  You should have received a copy of the GNU General Public License
 *  along with the software. If not, see <http://www.gnu.org/licenses/>.
 *
 *  Copyright 2018, Kuylen E, Willem L, Broeckhove J
 */

#pragma once

#include <cassert>
#include <cmath>
#include <iterator>
#include <type_traits>

namespace stride {
namespace util {

template <typename T, std::size_t N, bool Safe>
class SegmentedVector;

template <typename T, std::size_t N, bool Safe, typename P = const T*, typename R = const T&,
          bool is_const_iterator = true>
class SVIterator
{
public:
        // C++17 deprecates std::iterator so we need to define these traits ourselves.
        using iterator_category = std::random_access_iterator_tag;
        using value_type        = T;
        using difference_type   = std::ptrdiff_t;
        using pointer           = P;
        using reference         = R;

public:
        // ==================================================================
        // Member types (in addition to those introduced by the std::iterator
        // base class (i.e. value_type, difference_type, pointer, reference,
        // iterator_category).
        // ==================================================================
        using self_type = SVIterator<T, N, Safe, P, R, is_const_iterator>;

        // ==================================================================
        // Construction / Copy / Move / Destruction
        // ==================================================================
        SVIterator() : m_p(0), m_c(nullptr) {}

        SVIterator(const self_type& other) : m_p(other.m_p), m_c(other.m_c) {}

        // ==================================================================
        // Bidirectional iterator methods
        // ==================================================================

        R operator*() const
        {
                // assert(m_c != nullptr && 0 <= m_p && m_p < m_c->m_size);
                assert(m_c != nullptr && 0 <= m_p && m_p < m_c->m_size);
                return *static_cast<T*>(static_cast<void*>(&(m_c->m_blocks[m_p / N][m_p % N])));
        }

        P operator->() const
        {
                assert(m_c != nullptr && 0 <= m_p && m_p < m_c->m_size);
                return static_cast<T*>(static_cast<void*>(&(m_c->m_blocks[m_p / N][m_p % N])));
        }

        self_type& operator++()
        {
                assert(m_c != nullptr && 0 <= m_p && m_p <= m_c->m_size);
                // defensive: m_p = std::max(++m_p, mc->m_size);
                ++m_p;
                assert(m_c != nullptr && 0 <= m_p && m_p <= m_c->m_size);
                return *this;
        }

        const self_type operator++(int)
        {
                self_type tmp(*this);
                          operator++();
                return tmp;
        }

        self_type& operator--()
        {
                assert(m_c != nullptr && 0 <= m_p && m_p <= m_c->m_size);
                // defensive: m_p = std::max(--m_p, 0);
                --m_p;
                assert(m_c != nullptr && 0 <= m_p && m_p <= m_c->m_size);
                return *this;
        }

        const self_type operator--(int)
        {
                self_type tmp(*this);
                          operator--();
                return tmp;
        }

        bool operator==(const self_type& other) const { return (m_p == other.m_p) && (m_c == other.m_c); }

        bool operator!=(const self_type& other) const { return (m_p != other.m_p) || (m_c != other.m_c); }

        // ==================================================================
        // Random-Access iterator methods
        // ==================================================================

        R operator[](std::size_t n) const
        {
                assert(m_c != nullptr && 0 <= m_p + n && m_p + n < m_c->m_size);
                return *static_cast<T*>(static_cast<void*>(&(m_c->m_blocks[(m_p + n) / N][(m_p + n) % N])));
        }

        self_type& operator+=(std::ptrdiff_t n)
        {
                assert(m_c != nullptr && 0 <= m_p && m_p <= m_c->m_size);
                // defensive: m_p = std::max((m_p+=n), mc->m_size);
                m_p += n;
                return *this;
        }

        self_type& operator-=(std::ptrdiff_t n)
        {
                assert(m_c != nullptr && 0 <= m_p && m_p <= m_c->m_size);
                // defensive: m_p = std::max((m_p -= n), 0);
                m_p -= n;
                assert(m_c != nullptr && 0 <= m_p && m_p <= m_c->m_size);
                return *this;
        }

        self_type operator+(std::ptrdiff_t n)
        {
                assert(m_c != nullptr && 0 <= m_p && m_p <= m_c->m_size);
                assert(m_c != nullptr && 0 <= m_p + n && m_p + n <= m_c->m_size);
                return self_type(m_p + n, m_c);
        }

        self_type operator-(std::ptrdiff_t n)
        {
                assert(m_c != nullptr && 0 <= m_p && m_p <= m_c->m_size);
                assert(m_c != nullptr && 0 <= m_p - n && m_p - n <= m_c->m_size);
                return self_type(m_p - n, m_c);
        };

        long int operator-(const self_type& other) const
        {
                assert(m_c != nullptr && 0 <= m_p && m_p <= m_c->m_size);
                assert(other.m_c != nullptr && 0 <= other.m_p && other.m_p <= other.m_c->m_size);
                return m_p - other.m_p;
        }

        bool operator<(const self_type& other) const
        {
                assert(m_c != nullptr && 0 <= m_p && m_p <= m_c->m_size);
                assert(other.m_c != nullptr && 0 <= other.m_p && other.m_p <= other.m_c->m_size);
                return m_p < other.m_p;
        }

        bool operator<=(const self_type& other) const
        {
                assert(m_c != nullptr && 0 <= m_p && m_p <= m_c->m_size);
                assert(other.m_c != nullptr && 0 <= other.m_p && other.m_p <= other.m_c->m_size);
                return m_p <= other.m_p;
        }

        bool operator>(const self_type& other) const
        {
                assert(m_c != nullptr && 0 <= m_p && m_p <= m_c->m_size);
                assert(other.m_c != nullptr && 0 <= other.m_p && other.m_p <= other.m_c->m_size);
                return m_p > other.m_p;
        }

        bool operator>=(const self_type& other) const
        {
                assert(m_c != nullptr && 0 <= m_p && m_p <= m_c->m_size);
                assert(other.m_c != nullptr && 0 <= other.m_p && other.m_p <= other.m_c->m_size);
                return m_p >= other.m_p;
        }

private:
        friend class SegmentedVector<T, N, Safe>;

private:
        using container_pointer_type = typename std::conditional<is_const_iterator, const SegmentedVector<T, N, Safe>*,
                                                                 SegmentedVector<T, N, Safe>*>::type;

private:
        SVIterator(std::size_t p, container_pointer_type c) : m_p(p), m_c(c) {}

private:
        std::size_t            m_p; 
        container_pointer_type m_c; 
};

//------------------------------------
// Helpers
//------------------------------------
template <typename T, std::size_t N, bool Safe, typename P = const T*, typename R = const T&,
          bool is_const_iterator = true>
SVIterator<T, N, Safe, P, R, is_const_iterator> operator+(std::ptrdiff_t                                  i,
                                                          SVIterator<T, N, Safe, P, R, is_const_iterator> p)
{
        return p.operator+(i);
}

template <typename T, std::size_t N, bool Safe, typename P = const T*, typename R = const T&,
          bool is_const_iterator = true>
SVIterator<T, N, Safe, P, R, is_const_iterator> operator-(std::ptrdiff_t                                  i,
                                                          SVIterator<T, N, Safe, P, R, is_const_iterator> p)
{
        return p.operator-(i);
}

} // namespace util
} // namespace stride