utils.hh

Go to the documentation of this file.

//
// Created by jonathan.hanks on 4/29/17.
//

#ifndef NDS_LITE_UTILS_HH
#define NDS_LITE_UTILS_HH

#include <cstddef>
#include <stdexcept>
#include <string>
#include <vector>

namespace nds_impl
{
    namespace common
    {
        template < typename T >
        class IdentityTransform
        {
        public:
            auto
            operator( )( const T& input ) -> T
            {
                return input;
            }
        };

        enum split_type
        {
            INCLUDE_EMPTY_STRING = 0,
            EXCLUDE_EMPTY_STRING = 1,
        };

        static std::vector< std::string >
        split( const std::string& source,
               const std::string& sep,
               split_type         filter_mode = INCLUDE_EMPTY_STRING )
        {
            std::vector< std::string > results;

            if ( source == "" )
                return results;
            std::string::size_type prev = 0;
            std::string::size_type pos = 0;
            if ( sep.size( ) > 0 )
            {
                std::string::size_type sep_size = sep.size( );
                while ( pos < source.size( ) && pos != std::string::npos )
                {
                    pos = source.find( sep, prev );
                    if ( pos != std::string::npos )
                    {
                        auto tmp = source.substr( prev, pos - prev );
                        if ( tmp != "" || filter_mode == INCLUDE_EMPTY_STRING )
                            results.push_back( tmp );
                        pos += sep_size;
                        prev = pos;
                    }
                }
            }
            else
            {
                while ( pos < source.size( ) && pos != std::string::npos )
                {
                    pos = source.find_first_of( " \t\n\r", prev );
                    if ( pos != std::string::npos )
                    {
                        auto tmp = source.substr( prev, pos - prev );
                        if ( tmp != "" || filter_mode == INCLUDE_EMPTY_STRING )
                            results.push_back( tmp );
                        ++pos;
                        prev = pos;
                    }
                }
            }
            auto tmp = source.substr( prev );
            if ( tmp != "" || filter_mode == INCLUDE_EMPTY_STRING )
                results.push_back( tmp );
            return results;
        }

        template < typename T >
        class TruePredicate
        {
        public:
            bool
            operator( )( const T& input )
            {
                return true;
            }
        };

        template < typename T >
        class FirstNPredicate
        {
        public:
            typedef std::size_t size_type;

            FirstNPredicate( size_type max )
                : max_{ max }, local_cur_{ 0 }, ext_cur_{ &local_cur_ }
            {
            }
            FirstNPredicate( size_type max, size_type* ext_tracker )
                : max_{ max }, local_cur_{ 0 }, ext_cur_{ ext_tracker }
            {
            }
            bool
            operator( )( const T& input )
            {
                if ( *ext_cur_ < max_ )
                {
                    ++( *ext_cur_ );
                    return true;
                }
                return false;
            }

            size_type
            accepted( ) const
            {
                return *ext_cur_;
            }

        private:
            size_type  max_;
            size_type  local_cur_;
            size_type* ext_cur_;
        };

        template < typename T >
        class Span
        {
        public:
            typedef T              value_type;
            typedef std::size_t    size_type;
            typedef T*             pointer;
            typedef std::ptrdiff_t difference_type;
            typedef T&             reference;
            typedef T*             iterator;

            Span( const Span< T >& other )
                : data_{ other.data_ }, size_{ other.size_ }
            {
            }
            Span( T* data, size_type count )
                : data_{ data }, size_{ ( data ? count : 0 ) }
            {
            }
            size_type
            size( ) const
            {
                return size_;
            }
            size_type
            max_size( ) const
            {
                return size( );
            }
            bool
            empty( ) const
            {
                return size( ) == 0;
            }
            pointer
            data( ) const
            {
                return data_;
            }
            pointer
            begin( ) const
            {
                return data_;
            }
            pointer
            end( ) const
            {
                return data_ + size_;
            }
            reference
            at( size_t index ) const
            {
                if ( index >= size_ )
                    throw std::out_of_range(
                        "accessing outside of the array range" );
                return data_[ index ];
            }
            reference operator[]( size_t index )
            {
                return data_[ index ];
            }
            reference
            front( ) const
            {
                return *data_;
            }
            reference
            back( ) const
            {
                return data_[ size_ - 1 ];
            }
            void
            swap( Span< T >& other )
            {
                std::swap( other.data_, data_ );
                std::swap( other.size_, size_ );
            }
            void
            fill( T& value )
            {
                std::fill( begin( ), end( ), value );
            }

        private:
            value_type* data_;
            size_type   size_;
        };

        template < typename It, typename BinaryPred >
        It
        adjacent_find( It begin, It end, BinaryPred p )
        {
            auto cur = begin;
            if ( cur == end )
            {
                return end;
            }
            auto prev = cur;
            ++cur;
            for ( ; cur != end; ++cur, prev = cur )
            {
                if ( p( *prev, *cur ) )
                {
                    return prev;
                }
            }
            return end;
        }
    }
}

// Tests only after this point.

#ifdef _NDS_IMPL_ENABLE_CATCH_TESTS_

#include <algorithm>
#include <cstring>
#include "catch.hpp"

namespace nds_impl_cmn_utils
{
    struct simple_struct
    {
        int  field1;
        char field2[ 10 ];
    };
}

TEST_CASE( "An identity transform transforms an object to itself",
           "[nds2][utils][transforms]" )
{
    {
        nds_impl::common::IdentityTransform< std::string > t_str;
        auto input = std::string( "hello" );
        auto output = t_str( input );
        REQUIRE( input == output );
    }
}

TEST_CASE( "Test split", "[utils][split]" )
{
    {
        auto result = nds_impl::common::split( "", "" );
        REQUIRE( result.size( ) == 0 );
    }
    {
        auto result = nds_impl::common::split(
            "", "", nds_impl::common::split_type::EXCLUDE_EMPTY_STRING );
        REQUIRE( result.size( ) == 0 );
    }
    {
        auto result = nds_impl::common::split( "", "a" );
        REQUIRE( result.size( ) == 0 );
    }
    {
        auto result = nds_impl::common::split(
            "", "a", nds_impl::common::split_type::EXCLUDE_EMPTY_STRING );
        REQUIRE( result.size( ) == 0 );
    }
    {
        auto result = nds_impl::common::split( "abc", "b" );
        REQUIRE( result.size( ) == 2 );
        REQUIRE( result[ 0 ] == "a" );
        REQUIRE( result[ 1 ] == "c" );
    }
    {
        auto result = nds_impl::common::split(
            "abc", "b", nds_impl::common::split_type::EXCLUDE_EMPTY_STRING );
        REQUIRE( result.size( ) == 2 );
        REQUIRE( result[ 0 ] == "a" );
        REQUIRE( result[ 1 ] == "c" );
    }
    {
        auto result = nds_impl::common::split( "abc", "d" );
        REQUIRE( result.size( ) == 1 );
        REQUIRE( result[ 0 ] == "abc" );
    }
    {
        auto result = nds_impl::common::split(
            "abc", "d", nds_impl::common::split_type::EXCLUDE_EMPTY_STRING );
        REQUIRE( result.size( ) == 1 );
        REQUIRE( result[ 0 ] == "abc" );
    }
    {
        auto result = nds_impl::common::split( "babcabbdb", "b" );
        REQUIRE( result.size( ) == 6 );
        std::vector< std::string > expected{ "", "a", "ca", "", "d", "" };
        REQUIRE( result == expected );
    }
    {
        auto result = nds_impl::common::split( "catbatdog", "at" );
        REQUIRE( result.size( ) == 3 );
        REQUIRE( result[ 0 ] == "c" );
        REQUIRE( result[ 1 ] == "b" );
        REQUIRE( result[ 2 ] == "dog" );
    }
    {
        auto result = nds_impl::common::split(
            "catbatdog",
            "at",
            nds_impl::common::split_type::EXCLUDE_EMPTY_STRING );
        REQUIRE( result.size( ) == 3 );
        REQUIRE( result[ 0 ] == "c" );
        REQUIRE( result[ 1 ] == "b" );
        REQUIRE( result[ 2 ] == "dog" );
    }
    {
        auto result = nds_impl::common::split( "abc", "" );
        REQUIRE( result.size( ) == 1 );
        REQUIRE( result[ 0 ] == "abc" );
    }
    {
        auto result = nds_impl::common::split(
            "abc", "", nds_impl::common::split_type::EXCLUDE_EMPTY_STRING );
        REQUIRE( result.size( ) == 1 );
        REQUIRE( result[ 0 ] == "abc" );
    }
    {
        auto result = nds_impl::common::split( "a b\r \tc\nd", "" );
        REQUIRE( result.size( ) == 6 );
        std::vector< std::string > expected{ "a", "b", "", "", "c", "d" };
        REQUIRE( result == expected );
    }
    {
        auto result = nds_impl::common::split(
            "a b\r \tc\nd",
            "",
            nds_impl::common::split_type::EXCLUDE_EMPTY_STRING );
        REQUIRE( result.size( ) == 4 );
        std::vector< std::string > expected{ "a", "b", "c", "d" };
        REQUIRE( result == expected );
    }
    {
        auto result = nds_impl::common::split(
            "a b\r \tc\nd ",
            "",
            nds_impl::common::split_type::EXCLUDE_EMPTY_STRING );
        REQUIRE( result.size( ) == 4 );
        std::vector< std::string > expected{ "a", "b", "c", "d" };
        REQUIRE( result == expected );
    }
}

TEST_CASE( "TruePredicate", "[utils][predicates]" )
{
    nds_impl::common::TruePredicate< int > p;
    REQUIRE( p( 10000000 ) );
    REQUIRE( p( 1 ) );
    REQUIRE( p( 0 ) );
    REQUIRE( p( -1 ) );
    REQUIRE( p( -1000000 ) );
}

TEST_CASE( "FirstNPredicate", "[utils][predicates]" )
{
    {
        nds_impl::common::FirstNPredicate< int > p( 5 );
        for ( auto i = 0; i < 5; ++i )
        {
            REQUIRE( p.accepted( ) == i );
            REQUIRE( p( 1 ) );
        }
        REQUIRE( p.accepted( ) == 5 );
        REQUIRE( !p( 1 ) );
        REQUIRE( p.accepted( ) == 5 );
        REQUIRE( !p( 1 ) );
        REQUIRE( p.accepted( ) == 5 );
    }

    {
        auto test_cb = []( nds_impl::common::FirstNPredicate< int > p,
                           int                                      val ) {
            REQUIRE( p.accepted( ) == val );
            REQUIRE( p( 1 ) );
        };
        nds_impl::common::FirstNPredicate< int > p( 5 );
        for ( auto i = 0; i < 5; ++i )
        {
            test_cb( p, i );
        }
        REQUIRE( p.accepted( ) == 5 );
        REQUIRE( !p( 1 ) );
        REQUIRE( p.accepted( ) == 5 );
        REQUIRE( !p( 1 ) );
        REQUIRE( p.accepted( ) == 5 );
    }
}

TEST_CASE( "Array_view", "[utils][array_view]" )
{
    using namespace nds_impl_cmn_utils;

    const int     ARRAY_SIZE = 20;
    simple_struct base[ ARRAY_SIZE ];
    for ( auto i = 0; i < ARRAY_SIZE; ++i )
    {
        base[ i ].field1 = static_cast< int >( i );
        std::strncpy(
            base[ i ].field2, "a string", sizeof( base[ i ].field2 ) );
    }

    nds_impl::common::Span< simple_struct > array( base, ARRAY_SIZE );
    REQUIRE( array.empty( ) == false );
    REQUIRE( array.size( ) == ARRAY_SIZE );
    REQUIRE( array.max_size( ) == array.size( ) );
    REQUIRE( array.data( ) == base );
    REQUIRE( array.begin( ) == base );
    REQUIRE( array.end( ) == base + ARRAY_SIZE );
    REQUIRE( &array.at( 0 ) == base );
    REQUIRE( &array[ 0 ] == base );
    REQUIRE_THROWS_AS( array.at( ARRAY_SIZE + 1 ), std::out_of_range );
    REQUIRE_THROWS_AS( array.at( -1 ), std::out_of_range );
    REQUIRE( &array.front( ) == base );
    REQUIRE( &array.back( ) == base + ( ARRAY_SIZE - 1 ) );
    for ( auto i = 0; i < ARRAY_SIZE; ++i )
    {
        REQUIRE( array.at( i ).field1 == static_cast< int >( i ) );
        REQUIRE( std::strncmp( array.at( i ).field2,
                               "a string",
                               sizeof( base[ i ].field2 ) ) == 0 );

        REQUIRE( array[ i ].field1 == static_cast< int >( i ) );
        REQUIRE( std::strncmp( array[ i ].field2,
                               "a string",
                               sizeof( base[ i ].field2 ) ) == 0 );
    }

    typedef nds_impl::common::Span< simple_struct > sstruct_array;
    static_assert(
        std::is_same< sstruct_array::value_type, simple_struct >::value, "" );
    static_assert( std::is_same< sstruct_array::size_type, std::size_t >::value,
                   "" );
    static_assert(
        std::is_same< sstruct_array::pointer, simple_struct* >::value, "" );
    static_assert(
        std::is_same< sstruct_array::difference_type, std::ptrdiff_t >::value,
        "" );
    static_assert(
        std::is_same< sstruct_array::reference, simple_struct& >::value, "" );
    static_assert(
        std::is_same< sstruct_array::iterator, simple_struct* >::value, "" );
    //    static_assert(std::is_same<sstruct_array::, >::value, "");
}

TEST_CASE( "Empty Span", "[utils][array_view]" )
{
    using namespace nds_impl_cmn_utils;

    const int     ARRAY_SIZE = 5;
    simple_struct base[ 5 ];

    nds_impl::common::Span< simple_struct > array1( nullptr, 0 );
    REQUIRE( array1.empty( ) );
    REQUIRE( array1.size( ) == 0 );
    REQUIRE( array1.data( ) == nullptr );
    REQUIRE( array1.begin( ) == array1.end( ) );
    REQUIRE( array1.begin( ) == nullptr );

    nds_impl::common::Span< simple_struct > array2( nullptr, 5 );
    REQUIRE( array2.empty( ) );
    REQUIRE( array2.size( ) == 0 );
    REQUIRE( array2.data( ) == nullptr );
    REQUIRE( array2.begin( ) == array2.end( ) );
    REQUIRE( array2.begin( ) == nullptr );

    nds_impl::common::Span< simple_struct > array3( base, 0 );
    REQUIRE( array3.empty( ) );
    REQUIRE( array3.size( ) == 0 );
    REQUIRE( array3.data( ) == base );
    REQUIRE( array3.begin( ) == array3.end( ) );
    REQUIRE( array3.begin( ) == base );
}

TEST_CASE( "Copy and assign ArrayViews", "[utils][array_view]" )
{
    using namespace nds_impl_cmn_utils;

    const int     ARRAY_SIZE = 5;
    simple_struct base[ 5 ];

    nds_impl::common::Span< simple_struct > array1( base, ARRAY_SIZE );
    nds_impl::common::Span< simple_struct > array2( base + 1, ARRAY_SIZE - 2 );
    nds_impl::common::Span< simple_struct > array3( array1 );
    REQUIRE( array1.size( ) == array3.size( ) );
    REQUIRE( array1.data( ) == array3.data( ) );

    array3 = array2;
    REQUIRE( array3.size( ) == array2.size( ) );
    REQUIRE( array3.data( ) == array2.data( ) );

    array3.swap( array1 );
    REQUIRE( array3.data( ) == base );
    REQUIRE( array3.size( ) == ARRAY_SIZE );
    REQUIRE( array1.data( ) == base + 1 );
    REQUIRE( array1.size( ) == ARRAY_SIZE - 2 );
}

TEST_CASE( "array_view fill", "[utils][array_view]" )
{
    using namespace nds_impl_cmn_utils;

    const int     ARRAY_SIZE = 5;
    simple_struct base[ 5 ];

    nds_impl::common::Span< simple_struct > array( base, ARRAY_SIZE );
    simple_struct                           ref;
    ref.field1 = 42;
    std::strncpy( ref.field2, "answer", sizeof( ref.field2 ) );
    array.fill( ref );
    for ( auto entry : array )
    {
        REQUIRE( entry.field1 == 42 );
        REQUIRE( std::strncmp(
                     entry.field2, "answer", sizeof( entry.field2 ) ) == 0 );
    }
    ref.field1 = 32;
    std::strncpy( ref.field2, "nonanswer", sizeof( ref.field2 ) );
    array.fill( ref );
    for ( auto entry : array )
    {
        REQUIRE( entry.field1 == 32 );
        REQUIRE( std::strncmp(
                     entry.field2, "nonanswer", sizeof( entry.field2 ) ) == 0 );
    }
}

TEST_CASE( "adjacent_find finds two entries next to each other that are equal",
           "[utils][algorithms]" )
{
    using namespace nds_impl_cmn_utils;

    auto eq = []( int a, int b ) -> bool { return a == b; };

    {
        std::vector< int > s;
        REQUIRE( adjacent_find( s.begin( ), s.end( ), eq ) == s.end( ) );
    }

    {
        std::vector< int > s;
        s.push_back( 1 );
        REQUIRE( adjacent_find( s.begin( ), s.end( ), eq ) == s.end( ) );
    }

    {
        std::vector< int > s;
        s.push_back( 1 );
        s.push_back( 2 );
        REQUIRE( adjacent_find( s.begin( ), s.end( ), eq ) == s.end( ) );
    }

    {
        std::vector< int > s;
        s.push_back( 1 );
        s.push_back( 1 );
        REQUIRE( adjacent_find( s.begin( ), s.end( ), eq ) == s.begin( ) );
    }

    {
        std::vector< int > s{ 1, 0, 5, 5, 6 };
        auto               it = adjacent_find( s.begin( ), s.end( ), eq );
        REQUIRE( it != s.end( ) );
        REQUIRE( *it == 5 );
        ++it;
        REQUIRE( *it == 5 );
        ++it;
        REQUIRE( it != s.end( ) );
        REQUIRE( *it == 6 );
    }

    {
        std::vector< int > s{ 1, 0, 5, 6, 5, 5 };
        auto               it = adjacent_find( s.begin( ), s.end( ), eq );
        REQUIRE( it != s.end( ) );
        REQUIRE( *it == 5 );
        ++it;
        REQUIRE( *it == 5 );
        ++it;
        REQUIRE( it == s.end( ) );
    }
}

#endif // _NDS_IMPL_ENABLE_CATCH_TESTS_

#endif // NDS_LITE_UTILS_HH