regular.hpp

Go to the documentation of this file.

/*
 *   Copyright 2021 Huawei Technologies Co., Ltd.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef _H_GRB_ITERATOR_REGULAR
#define _H_GRB_ITERATOR_REGULAR

#include <utility>
#include <iterator>
#include <functional>

#include <assert.h>


namespace grb {

    namespace utils {

        namespace iterators {

            template< typename T >
            class Repeater;

            template< typename T >
            class Sequence;

        }

        namespace internal {

            template<
                typename R,
                typename T,
                typename SelfType
            >
            class PosBasedIterator {

                friend class grb::utils::iterators::Repeater< R >;

                friend class grb::utils::iterators::Sequence< R >;

                protected:

                    static constexpr const size_t block_size = 256;

                    size_t _count;

                    size_t _pos;

                    R _val;

                    T _state;

                    PosBasedIterator(
                        const size_t count, const size_t pos,
                        const R val, const T state
                    ) :
                        _count( count ), _pos( pos ), _val( val ), _state( state )
                    {}


                public:

                    // standard STL typedefs

                    typedef std::random_access_iterator_tag iterator_category;

                    typedef size_t difference_type;

                    typedef R value_type;

                    typedef const R * pointer;

                    typedef const R & reference;

                    // STL-like typedefs

                    typedef PosBasedIterator< R, T, SelfType > self_type;

                    typedef self_type & self_reference_type;

                    typedef const PosBasedIterator< R, T, SelfType > self_const_reference_type;

                    // constructor

                    PosBasedIterator(
                        const size_t count,
                        const bool start,
                        const T state,
                        const R dummy = R(),
                        const size_t s = 0,
                        const size_t P = 1
                    ) :
                        _count( count ), _val( dummy ), _state( state )
                    {
                        // static run-time checks
                        static_assert( block_size > 0,
                            "Regular iterator: internal block size must be larger than zero" );
                        // run-time checks
                        if( P == 0 || s >= P ) {
                            throw std::runtime_error( "Illegal values for s and/or P" );
                        }
                        // adjust count according to P
                        size_t entries_per_process = count;
                        if( P > 1 && count > block_size ) {
                            const size_t bcount = (count % block_size) > 0
                                ? count / block_size + 1
                                : count / block_size;
                            const size_t bcount_per_process = (bcount % P) > 0
                                ? bcount / P + 1
                                : bcount / P;
                            entries_per_process = bcount_per_process * block_size;
                        }
                        // adjust count according to s
                        _count = (s+1) * entries_per_process;
                        if( _count > count ) { _count = count; }
                        // select start position according to s
                        _pos = start
                            ? s * entries_per_process
                            : _count;
                        // correct potential overflow of starting position
                        if( _pos > _count ) { _pos = _count; }
                        // initialise selected starting position
                        if( _pos != count ) {
                            SelfType::func( _val, state, _pos );
                        }
                    }

                    PosBasedIterator( const self_const_reference_type &other ) :
                        _count( other._count ), _pos( other._pos ),
                        _val( other._val ), _state( other._state )
                    {}

                    PosBasedIterator( PosBasedIterator< R, T, SelfType > &&other ) :
                        _count( other._count ), _pos( other._pos )
                    {
                        _val = std::move( other._val );
                        _state = std::move( other._state );
                        other._count = other._pos = 0;
                    }

                    ~PosBasedIterator() {}

                    // standard iterator interface

                    reference operator*() const noexcept {
                        return _val;
                    }

                    self_reference_type operator=( self_const_reference_type other ) noexcept {
                        _count = other._count;
                        _pos = other._pos;
                        _val = other._val;
                        _state = other._state;
                        return *this;
                    }

                    self_reference_type operator=(
                        PosBasedIterator< R, T, SelfType > &&other
                    ) noexcept {
                        _count = other._count;
                        _pos = other._pos;
                        _val = std::move( other._val );
                        _state = std::move( other._state );
                        other._count = other._pos = 0;
                        return *this;
                    }

                    self_reference_type operator++() noexcept {
                        assert( _pos < _count );
                        (void) ++_pos;
                        if( _pos != _count ) {
                            SelfType::func( _val, _state, _pos );
                        }
                        return *this;
                    }

                    friend void swap( self_reference_type left, self_reference_type right ) {
                        std::swap( left._count, right._count );
                        std::swap( left._pos, right._pos );
                        std::swap( left._val, right._val );
                        std::swap( left._state, right._state );
                    }

                    // input iterator interface

                    pointer operator->() const noexcept {
                        return &_val;
                    }

                    self_type operator++(int) noexcept {
                        assert( _pos < _count );
                        self_type ret =
                            SelfType::create_iterator( _count, _pos, _val, _state );
                        (void) _pos++;
                        if( _pos != _count ) {
                            SelfType::func( _val, _state, _pos );
                        }
                        return ret;
                    }

                    friend bool operator==(
                        self_const_reference_type left, self_const_reference_type right
                    ) noexcept {
                        assert( left._count == right._count );
                        return left._pos == right._pos;
                    }

                    friend bool operator!=(
                        self_const_reference_type left, self_const_reference_type right
                    ) noexcept {
                        return !(left == right);
                    }

                    // bi-directional iterator interface

                    self_reference_type operator--() noexcept {
                        assert( _pos > 0 );
                        (void) --_pos;
                        if( _pos < _count ) {
                            SelfType::func( _val, _state, _pos );
                        }
                        return *this;
                    }

                    self_type operator--(int) noexcept {
                        assert( _pos > 0 );
                        self_type ret =
                            SelfType::make_iterator( _pos, _count, _val, _pos );
                        (void) _pos--;
                        if( _pos < _count ) {
                            SelfType::func( _val, _state, _pos );
                        }
                        return ret;
                    }

                    // random access iterator interface

                    value_type operator[]( const size_t i ) const noexcept {
                        assert( i < PosBasedIterator::_count );
                        R ret = _val;
                        SelfType::func( ret, _state, i );
                        return ret;
                    }

                    friend bool operator<(
                        self_const_reference_type left,
                        self_const_reference_type right
                    ) {
                        assert( left._count == right._count );
                        return left._pos < right._pos;
                    }

                    friend bool operator>(
                        self_const_reference_type left,
                        self_const_reference_type right
                    ) {
                        return left._count == right._count &&
                            left._state == right._state &&
                            left._pos > right._pos;
                    }

                    friend bool operator<=(
                        self_const_reference_type left,
                        self_const_reference_type right
                    ) {
                        return left._count == right._count &&
                            left._state == right._state &&
                            left._pos <= right._pos;
                    }

                    friend bool operator>=(
                        self_const_reference_type left,
                        self_const_reference_type right
                    ) {
                        return left._count == right._count &&
                            left._state == right._state &&
                            left._pos >= right._pos;
                    }

                    self_reference_type operator+=( const size_t count ) noexcept {
                        assert( _pos + count <= _count );
                        _pos += count;
                        if( _pos != _count ) {
                            SelfType::func( _val, _state, _pos );
                        }
                        return *this;
                    }

                    friend self_type operator+(
                         self_const_reference_type iterator,
                         const size_t count
                    ) noexcept {
                        assert( iterator._pos + count <= iterator._count );
                        const size_t pos = iterator._pos + count;
                        R val = iterator._val;
                        if( pos != iterator._count ) {
                            SelfType::func( val, iterator._state, pos );
                        }
                        return self_type(
                            iterator._count, pos,
                            val, iterator._state
                        );
                    }

                    friend self_type operator+(
                        const size_t count,
                        self_const_reference_type iterator
                    ) noexcept {
                        assert( iterator._pos + count <= iterator._count );
                        const size_t pos = iterator._pos + count;
                        R val = iterator._val;
                        if( pos != iterator._count ) {
                            SelfType::func( val, iterator._state, pos );
                        }
                        return self_type(
                            iterator._count, pos,
                            val, iterator._state
                        );
                    }

                    self_reference_type operator-=( const size_t count ) noexcept {
                        assert( _pos >= count );
                        _pos -= count;
                        return *this;
                    }

                    friend self_type operator-(
                        self_const_reference_type iterator,
                        const size_t count
                    ) noexcept {
                        assert( iterator._pos >= count );
                        const size_t pos = iterator._pos - count;
                        R val = iterator._val;
                        if( pos != iterator._count ) {
                            SelfType::func( val, iterator._state, pos );
                        }
                        return self_type(
                            iterator._count, pos,
                            val, iterator._state
                        );
                    }

                    friend self_type operator-(
                        const size_t count,
                        self_const_reference_type iterator
                    ) noexcept {
                        assert( iterator._pos >= count );
                        const size_t pos = iterator._pos - count;
                        R val = iterator._val;
                        if( pos != iterator._count ) {
                            SelfType::func( val, iterator._state, pos );
                        }
                        return self_type(
                            iterator._count, pos,
                            val, iterator._state
                        );
                    }

                    difference_type operator-(
                        self_const_reference_type iterator
                    ) const noexcept {
                        assert( iterator._count == _count );
                        assert( iterator._state == _state );
                        return static_cast< difference_type >( _pos - iterator._pos );
                    }

            };

        } // end namespace grb::utils::internal

        namespace iterators {

            template< typename T >
            class Repeater {

                friend class internal::PosBasedIterator< T, T, Repeater< T > >;

                public:

                    typedef grb::utils::internal::PosBasedIterator< T, T, Repeater< T > >
                        RealType;


                protected:


                    static RealType create_iterator(
                        const size_t count,
                        const size_t pos,
                        const T val,
                        const T state
                    ) {
                        return RealType( count, pos, val, state );
                    }

                    inline static void func( T&, const T&, const size_t ) {}


                public:

                    static RealType make_iterator(
                        const size_t count,
                        const bool start,
                        const T val,
                        const size_t s = 0,
                        const size_t P = 1
                    ) {
                        return RealType( count, start, val, val, s, P );
                    }

            };

            template< typename T >
            class Sequence {

                friend class internal::PosBasedIterator<
                    T, std::tuple< size_t, size_t, size_t >,
                    Sequence< T >
                >;

                public:

                    typedef grb::utils::internal::PosBasedIterator<
                        T, std::tuple< size_t, size_t, size_t >, Sequence< T >
                    > RealType;


                protected:


                    static RealType create_iterator(
                        const size_t count,
                        const size_t pos,
                        const T val,
                        const std::tuple< size_t, size_t, size_t > state
                    ) {
                        return RealType( count, pos, val, state );
                    }

                    inline static void func(
                        T &val,
                        const std::tuple< size_t, size_t, size_t > &state,
                        const size_t pos
                    ) {
                        const size_t offset = std::get<0>(state);
                        const size_t stride = std::get<1>(state);
                        const size_t repetitions = std::get<2>(state);
                        val = offset + ( pos / repetitions ) * stride;
                    }


                public:

                    static RealType make_iterator(
                        const size_t count,
                        const bool start,
                        const size_t offset = static_cast< size_t >( 0 ),
                        const size_t stride = static_cast< size_t >( 1 ),
                        const size_t repetitions = static_cast< size_t >( 1 ),
                        T dummy = T(),
                        const size_t s = 0,
                        const size_t P = 1
                    ) {
                        return RealType(
                            count,
                            start,
                            std::tuple< size_t, size_t, size_t >( offset, stride, repetitions ),
                            dummy,
                            s, P
                        );
                    }

            };

        } // end namespace grb::utils::iterators

        namespace containers {

            template< typename T >
            class ConstantVector {

                private:

                    typedef typename grb::utils::iterators::Repeater< T > FactoryType;

                    const T _val;

                    const size_t _n;


                public:

                    typedef typename grb::utils::iterators::Repeater< T >::RealType iterator;

                    typedef iterator const_iterator;

                    ConstantVector( const T val, const size_t n ) : _val( val ), _n( n ) {}

                    iterator begin( const size_t s = 0, const size_t P = 1 ) const {
                        return FactoryType::make_iterator( _n, true, _val, s, P );
                    }

                    iterator end( const size_t s = 0, const size_t P = 1 ) const {
                        return FactoryType::make_iterator( _n, false, _val, s, P );
                    }

                    const_iterator cbegin( const size_t s = 0, const size_t P = 1 ) const {
                        return FactoryType::make_iterator( _n, true, _val, s, P );
                    }

                    const_iterator cend( const size_t s = 0, const size_t P = 1 ) const {
                        return FactoryType::make_iterator( _n, false, _val, s, P );
                    }

            };

            template< typename T = size_t >
            class Range {

                private:

                    typedef grb::utils::iterators::Sequence< T > FactoryType;

                    const size_t _start, _end;

                    const size_t _stride;

                    const size_t _repetitions;

                    const size_t _count;


                public:

                    typedef typename grb::utils::iterators::Sequence< T >::RealType iterator;

                    typedef iterator const_iterator;

                    Range(
                        const size_t start, const size_t end,
                        const size_t stride = static_cast< size_t >( 1 ),
                        const size_t repetitions = static_cast< size_t >( 1 )
                    ) noexcept :
                        _start( start ),
                        _end( end ),
                        _stride( stride ),
                        _repetitions( repetitions ),
                        _count(
                            start == end
                                ? 0
                                : ( (end-start) % stride > 0
                                    ? ((end-start) / stride + 1)
                                    : (end-start) / stride
                                ) * repetitions
                        )
                    {
                        assert( start <= end );
                    }

                    iterator begin( const size_t s = 0, const size_t P = 1 ) const {
                        return FactoryType::make_iterator( _count, true, _start, _stride,
                            _repetitions, T(), s, P );
                    }

                    iterator end( const size_t s = 0, const size_t P = 1 ) const {
                        return FactoryType::make_iterator( _count, false, _start, _stride,
                            _repetitions, T(), s, P );
                    }

                    const_iterator cbegin( const size_t s = 0, const size_t P = 1 ) const {
                        return FactoryType::make_iterator( _count, true, _start, _stride,
                            _repetitions, T(), s, P );
                    }

                    const_iterator cend( const size_t s = 0, const size_t P = 1 ) const {
                        return FactoryType::make_iterator( _count, false, _start, _stride,
                            _repetitions, T(), s, P );
                    }

            };

        } // end namespace grb::utils::containers

    } // end namespace grb::utils

} // end namespace grb

#endif // end _H_GRB_ITERATOR_REGULAR