algorithm.hpp

#ifndef QLIBS_ALGORITHM
#define QLIBS_ALGORITHM
 
#include <include/qlibs_types.hpp>

 

namespace qlibs {

    namespace algorithm {

        template <typename T>
        void swap( T& x, T& y ) noexcept
        {
            T tmp = x;
            x = y;
            y = tmp;
        }

        namespace impl {
            struct sort_pair {
                int first;
                int second;
            };
            template<typename T, size_t N>
            class sort_stack {
                private:
                    T dat[ N ];
                    size_t topIndex;
                public:
                    sort_stack() : topIndex( 0 ) {}
                    bool empty( void ) const noexcept
                    {
                        return 0 == topIndex;
                    }
                    void push( const T& value ) noexcept
                    {
                        if ( topIndex < N ) {
                            dat[ topIndex++ ] = value;
                        }
                    }
                    void pop( void ) noexcept
                    {
                        if ( topIndex > 0 ) {
                            --topIndex;
                        }
                    }
                    T& top( void ) noexcept
                    {
                        return dat[ topIndex - 1 ];
                    }
            };
        }

        template<typename T, size_t n>
        void sort( T ( &array )[ n ],
                       size_t first = 0U,
                       size_t last = n - 1U,
                       bool (*comp)( const T&, const T&) = nullptr ) noexcept
        {
            if ( n > 1U ) {
                algorithm::impl::sort_stack<impl::sort_pair, n> stack;
                int start = static_cast<int>( first );
                int end = static_cast<int>( last );
 
                stack.push( { start, end } );
                while ( !stack.empty() ) {
                    impl::sort_pair indices = stack.top();
                    stack.pop();
                    start = indices.first;
                    end = indices.second;
                    int pivotIndex = start;
                    T pivotValue = array[ end ];
 
                    for ( int i = start; i < end; ++i ) {
                        if ( nullptr != comp ) {
                            if ( comp( array[ i ], array[ pivotIndex ] ) ) {
                                algorithm::swap( array[ i ], array[ pivotIndex ] );
                                ++pivotIndex;
                            }
                        }
                        else if ( array[ i ] < pivotValue ) {
                            algorithm::swap( array[ i ], array[ pivotIndex ] );
                            ++pivotIndex;
                        }
                    }
                    algorithm::swap( array[ pivotIndex ], array[ end ] );
                    if ( pivotIndex - 1 > start ) {
                        stack.push( { start, pivotIndex - 1 } );
                    }
                    if ( pivotIndex + 1 < end ) {
                        stack.push( { pivotIndex + 1, end } );
                    }
                }
            }
        }

        template<typename T, size_t n>
        inline void reverse( T ( &array )[ n ],
                             const size_t first = 0U,
                             const size_t last = n - 1U ) noexcept
        {
            if ( last > first ) {
                size_t s = first, e = last;
 
                while ( s < e ) {
                    algorithm::swap( array[ s ], array[ e ] );
                    ++s;
                    --e;
                }
            }
        }

        template<typename T, size_t n>
        void rotate( T ( &array )[ n ],
                         const int k = 1 ) noexcept
        {
            if ( 0 != k ) {
                size_t r;
                if ( k > 0 ) {
                    r = static_cast<size_t>( k );
                    r %= n;
                    algorithm::reverse( array, n - r, n - 1U );
                    algorithm::reverse( array, 0U, n - r - 1U );
                    algorithm::reverse( array, 0U, n - 1U );
                }
                else {
                    /*cstat -MISRAC++2008-5-0-9*/
                    r = static_cast<size_t>( -k );
                    /*cstat +MISRAC++2008-5-0-9*/
                    r %= n;
                    algorithm::reverse( array, 0U, r - 1U );
                    algorithm::reverse( array, r, n - 1U );
                    algorithm::reverse( array, 0U, n - 1U );
                }
            }
        }

        template<typename T, size_t n>
        inline void fill( T ( &array )[ n ],
                         const T value,
                         const size_t first = 0U,
                         const size_t last = n - 1U ) noexcept
        {
            for ( size_t i = first ; i <= last; ++i ) {
                array[ i ] = value;
            }
        }

        template<typename T, size_t n>
        inline T* find( T ( &array )[ n ],
                        const T key,
                        const size_t first = 0U,
                        const size_t last = n - 1U ) noexcept
        {
            T* found = nullptr;
 
            for ( size_t i = first; i <= last; ++i ) {
                if ( array[ i ] == key ) {
                    found = &array[ i ];
                    break;
                }
            }
            return found;
        }

        template<typename T, size_t n>
        inline bool any_of( T ( &array )[ n ],
                            bool (*pred)( const T ),
                            const size_t first = 0U,
                            const size_t last = n - 1U ) noexcept
        {
            bool ret = false;
 
            for ( size_t i = first; i <= last; ++i ) {
                if ( pred( array[ i ] ) ) {
                    ret = true;
                    break;
                }
            }
            return ret;
        }

        template<typename T, size_t n>
        inline bool all_of( T ( &array )[ n ],
                            bool (*pred)( const T ),
                            const size_t first = 0U,
                            const size_t last = n - 1U ) noexcept
        {
            bool ret = true;
 
            for ( size_t i = first; i <= last; ++i ) {
                if ( !pred( array[ i ] ) ) {
                    ret = false;
                    break;
                }
            }
            return ret;
        }

        template<typename T, size_t n>
        inline void replace( T ( &array )[ n ],
                             const T& old_value,
                             const T& new_value,
                             const size_t first = 0U,
                             const size_t last = n - 1U ) noexcept
        {
            for ( size_t i = first; i <= last; ++i ) {
                if ( old_value == array[ i ] ) {
                    array[ i ] = new_value;
                    break;
                }
            }
        }

        template<typename T, size_t n>
        inline void replace_if( T ( &array )[ n ],
                                bool (*pred)( const T& ),
                                const T& new_value,
                                const size_t first = 0U,
                                const size_t last = n - 1U ) noexcept
        {
            for ( size_t i = first; i <= last; ++i ) {
                if ( pred( array[ i ] ) ) {
                    array[ i ] = new_value;
                    break;
                }
            }
        }

        template<typename T, size_t n>
        inline size_t count_if( T ( &array )[ n ],
                                bool (*pred)( const T ),
                                const size_t first = 0U,
                                const size_t last = n - 1U ) noexcept
        {
            size_t count = 0U;
 
            for ( size_t i = first; i <= last; ++i ) {
                if ( pred( array[ i ] ) ) {
                    ++count;
                }
            }
            return count;
        }

        template<typename T, size_t n>
        inline T* find_if( T ( &array )[ n ],
                           bool (*pred)( const T ),
                           const size_t first = 0U,
                           const size_t last = n - 1U ) noexcept
        {
            T *found = nullptr;
 
            for ( size_t i = first; i <= last; ++i ) {
                if ( pred( array[ i ] ) ) {
                    found = &array[ i ];
                }
            }
            return found;
        }

        template<typename T, size_t n>
        inline void for_each( T ( &array )[ n ],
                              void (*fn)( T& ),
                              const size_t first = 0U,
                              const size_t last = n - 1U ) noexcept
        {
            for ( size_t i = first; i <= last; ++i ) {
                (void)fn( array[ i ] );
            }
        }

        template<typename T, size_t n>
        inline T* binary_search( T ( &array )[ n ],
                                 const T key,
                                 const size_t first = 0U,
                                 const size_t last = n - 1U ) noexcept
        {
            T* found = nullptr;
            int left = static_cast<int>( first );
            int right = static_cast<int>( last );
 
            while ( left <= right ) {
                int mid = left + ( right - left )/2;
 
                if ( array[ mid ] == key ) {
                    found =  &array[ mid ];
                    break;
                }
                if ( array[ mid ] < key ) {
                    left = mid + 1;
                }
                else {
                    right = mid - 1;
                }
            }
            return found;
        }

    }
}
 
 
#endif /*QLIBS_ALGORITHM*/