algorithm.h

Go to the documentation of this file.

 
#pragma once
 
#include "./algorithm/impl.h"
#include "./bounded.h"
#include "./min_max.h"
#include "./range.h"
#include "./types.h"
#include "./view.h"
 
#include <cmath>
#include <cstdlib>
#include <tuple>
 
namespace emlabcpp
{
 
constexpr float default_epsilon = 1.19e-07f;
 
template < typename T >
constexpr int sign( T const& val )
{
        using value_type = std::decay_t< T >;
        if ( value_type{ 0 } > val )
                return -1;
        if ( value_type{ 0 } < val )
                return 1;
        return 0;
}
 
template < typename T >
[[nodiscard]] constexpr T ceil_to( T val, T base )
{
        auto m = val % base;
        if ( m == 0 )
                return val;
        return val + base - m;
}
 
template < additive_operators T, arithmetic_operators U >
[[nodiscard]] constexpr U map_range( T input, T from_min, T from_max, U to_min, U to_max )
{
        return to_min + static_cast< U >(
                            ( to_max - to_min ) * static_cast< U >( input - from_min ) /
                            static_cast< U >( from_max - from_min ) );
}
 
template < container Container >
[[nodiscard]] constexpr std::size_t cont_size( Container const& cont ) noexcept
{
        if constexpr ( static_sized< Container > )
                return std::tuple_size_v< Container >;
        else
                return std::size( cont );
}
 
template < typename T >
[[nodiscard]] constexpr bool
almost_equal( T const& lh, T const& rh, float const eps = default_epsilon )
{
        return float( std::abs( lh - rh ) ) < eps;
}
 
template < referenceable_container Container, typename Iterator = iterator_of_t< Container > >
[[nodiscard]] constexpr view< Iterator > tail( Container&& cont, int const step = 1 )
{
        return view< Iterator >( std::next( std::begin( cont ), step ), std::end( cont ) );
}
 
template < referenceable_container Container, typename Iterator = iterator_of_t< Container > >
[[nodiscard]] constexpr view< Iterator > init( Container&& cont, int const step = 1 )
{
        return view< Iterator >( std::begin( cont ), std::end( cont ) - step );
}
 
template <
    range_container                  Container,
    container_invocable< Container > PredicateCallable = std::identity >
[[nodiscard]] constexpr auto find_if( Container&& cont, PredicateCallable&& f = std::identity() )
{
        auto beg = std::begin( cont );
        auto end = std::end( cont );
        for ( ; beg != end; ++beg )
                if ( f( *beg ) )
                        return beg;
        return cont.end();
}
 
template <
    gettable_container               Container,
    container_invocable< Container > PredicateCallable = std::identity >
requires( !range_container< Container > )
[[nodiscard]] constexpr std::size_t
find_if( Container&& t, PredicateCallable&& f = std::identity() )
{
        return impl::find_if_impl(
            std::forward< Container >( t ),
            std::forward< PredicateCallable >( f ),
            std::make_index_sequence< std::tuple_size_v< std::decay_t< Container > > >{} );
}
 
template < container Container, typename T >
[[nodiscard]] constexpr auto find( Container&& cont, T const& item )
{
        return find_if( std::forward< Container >( cont ), [&]( auto const& sub_item ) {
                return sub_item == item;
        } );
}
 
template < container Container, typename T >
[[nodiscard]] constexpr bool contains( Container const& cont, T const& item )
{
        if constexpr ( range_container< Container > )
                return find( cont, item ) != cont.end();
        else
                return find( cont, item ) != cont_size( cont );
}
 
template < gettable_container Container, container_invocable< Container > UnaryCallable >
requires( !range_container< Container > )
constexpr void for_each( Container&& cont, UnaryCallable&& f )
{
        std::apply(
            [&f]< typename... Items >( Items&&... items ) {
                    ( f( std::forward< Items >( items ) ), ... );
            },
            std::forward< Container >( cont ) );
}
 
template < range_container Container, container_invocable< Container > UnaryCallable >
constexpr void for_each( Container&& cont, UnaryCallable&& f )
{
        for ( auto&& item : std::forward< Container >( cont ) )
                f( std::forward< decltype( item ) >( item ) );
}
 
template <
    container                        Container,
    container_invocable< Container > UnaryCallable = std::identity,
    typename T = std::decay_t< mapped_t< Container, UnaryCallable > > >
[[nodiscard]] constexpr min_max< T >
min_max_elem( Container&& cont, UnaryCallable&& f = std::identity() )
{
        min_max< T > res;
        res.max() = std::numeric_limits< T >::lowest();
        res.min() = std::numeric_limits< T >::max();
 
        for_each( cont, [&]( auto& item ) {
                auto val  = f( item );
                res.max() = std::max( res.max(), val );
                res.min() = std::min( res.min(), val );
        } );
        return res;
}
 
template <
    container                        Container,
    container_invocable< Container > UnaryCallable = std::identity,
    typename T = std::decay_t< mapped_t< Container, UnaryCallable > > >
[[nodiscard]] constexpr T max_elem( Container&& cont, UnaryCallable&& f = std::identity() )
{
        T val = std::numeric_limits< T >::lowest();
        for_each( cont, [&]( auto& item ) {
                val = std::max( f( item ), val );
        } );
        return val;
}
 
template <
    container                        Container,
    container_invocable< Container > UnaryCallable = std::identity,
    typename T = std::decay_t< mapped_t< Container, UnaryCallable > > >
[[nodiscard]] constexpr T min_elem( Container&& cont, UnaryCallable&& f = std::identity() )
{
        T val = std::numeric_limits< T >::max();
        for_each( cont, [&]( auto& item ) {
                val = std::min( f( item ), val );
        } );
        return val;
}
 
template < container Container, container_invocable< Container > UnaryCallable = std::identity >
[[nodiscard]] constexpr std::size_t count( Container&& cont, UnaryCallable&& f = std::identity() )
{
        std::size_t res = 0;
        for_each( cont, [&]( auto& item ) {
                if ( f( item ) )
                        res += 1;
        } );
        return res;
}
 
template <
    container                        Container,
    container_invocable< Container > UnaryCallable = std::identity,
    typename T = std::decay_t< mapped_t< Container, UnaryCallable > > >
[[nodiscard]] constexpr T sum( Container&& cont, UnaryCallable&& f = std::identity(), T init = {} )
{
        for_each( cont, [&]( auto& item ) {
                init += f( item );
        } );
        return init;
}
 
template < container Container, typename T, typename BinaryCallable >
[[nodiscard]] constexpr T accumulate( Container&& cont, T init, BinaryCallable&& f )
{
        for_each( cont, [&]( auto& item ) {
                init = f( std::move( init ), item );  
        } );
        return init;
}
 
template <
    container                        Container,
    container_invocable< Container > UnaryCallable = std::identity,
    typename T = std::decay_t< mapped_t< Container, UnaryCallable > > >
[[nodiscard]] constexpr T avg( Container&& cont, UnaryCallable&& f = std::identity() )
{
        T res{};
        for_each( cont, [&]( auto& item ) {
                res += f( item );
        } );
        if constexpr ( std::is_arithmetic_v< T > )
                return res / static_cast< T >( cont_size( cont ) );
        else
                return res / cont_size( cont );
}
 
template <
    container                        Container,
    container_invocable< Container > UnaryCallable = std::identity,
    typename T = std::decay_t< mapped_t< Container, UnaryCallable > > >
[[nodiscard]] constexpr T variance( Container&& cont, UnaryCallable&& f = std::identity() )
{
        T u = avg( cont, f );
 
        T res = sum( cont, [&f, &u]( auto& val ) {
                auto v = f( val ) - u;
                return v * v;
        } );
        if constexpr ( std::is_arithmetic_v< T > )
                return res / static_cast< T >( cont_size( cont ) );
        else
                return res / cont_size( cont );
}
 
template < container LhContainer, container RhContainer, typename BinaryCallable >
constexpr void for_cross_joint( LhContainer&& lh_cont, RhContainer&& rh_cont, BinaryCallable&& f )
{
        for_each( lh_cont, [&]( auto& lh_item ) {
                for_each( rh_cont, [&]( auto& rh_item ) {
                        f( lh_item, rh_item );
                } );
        } );
}
 
template < container Container, container_invocable< Container > PredicateCallable = std::identity >
[[nodiscard]] constexpr bool any_of( Container&& cont, PredicateCallable&& f = std::identity() )
{
        auto res = find_if( cont, std::forward< PredicateCallable >( f ) );
 
        if constexpr ( is_std_tuple_v< Container > )
                return res != std::tuple_size_v< std::decay_t< Container > >;
        else
                return res != cont.end();
}
 
template < container Container, container_invocable< Container > PredicateCallable = std::identity >
[[nodiscard]] constexpr bool none_of( Container&& cont, PredicateCallable&& f = std::identity() )
{
        return !any_of( cont, std::forward< PredicateCallable >( f ) );
}
 
template < container Container, container_invocable< Container > PredicateCallable = std::identity >
[[nodiscard]] constexpr bool all_of( Container&& cont, PredicateCallable&& f = std::identity() )
{
        return !any_of( cont, [&]( auto& item ) {
                return !f( item );
        } );
}
 
template <
    range_container LhContainer,
    range_container RhContainer,
    typename BinaryPredicateCallable = std::equal_to< void > >
[[nodiscard]] constexpr bool
equal( LhContainer&& lh, RhContainer&& rh, BinaryPredicateCallable&& f = std::equal_to< void >{} )
{
        if ( cont_size( lh ) != cont_size( rh ) )
                return false;
        auto rbeg = std::begin( rh );
        for ( auto& item : lh ) {
                if ( !f( item, *rbeg ) )
                        return false;
                ++rbeg;
        }
        return true;
}
 
template <
    impl::map_f_collectable          ResultContainer,
    container                        Container,
    container_invocable< Container > UnaryCallable = std::identity >
[[nodiscard]] ResultContainer map_f( Container&& cont, UnaryCallable&& f = std::identity() )
{
        ResultContainer                          res{};
        impl::map_f_collector< ResultContainer > collector;
 
        for_each( std::forward< Container >( cont ), [&]< typename Item >( Item&& item ) {
                collector.collect( res, f( std::forward< Item >( item ) ) );
        } );
        return res;
}
 
template <
    std::size_t                      N,
    range_container                  Container,
    container_invocable< Container > UnaryCallable = std::identity,
    typename T = std::decay_t< mapped_t< Container, UnaryCallable > > >
[[nodiscard]] std::array< T, N > map_f_to_a( Container&& cont, UnaryCallable&& f = std::identity() )
requires( !static_sized< Container > )
{
        return impl::map_f_to_a_impl< T, N >(
            std::forward< Container >( cont ),
            std::forward< UnaryCallable >( f ),
            std::make_index_sequence< N >() );
}
 
template <
    gettable_container               Container,
    std::size_t                      N = std::tuple_size< std::decay_t< Container > >::value,
    container_invocable< Container > UnaryCallable = std::identity,
    typename T = std::decay_t< mapped_t< Container, UnaryCallable > > >
[[nodiscard]] std::array< T, N > map_f_to_a( Container&& cont, UnaryCallable&& f = std::identity() )
requires static_sized< Container >
{
        return impl::map_f_to_a_impl< T, N >(
            std::forward< Container >( cont ),
            std::forward< UnaryCallable >( f ),
            std::make_index_sequence< N >() );
}
 
template < typename T >
struct convert_to
{
        template < typename U >
        constexpr T operator()( U&& src ) const
            noexcept( noexcept( T{ std::forward< U >( src ) } ) )
        {
                return T{ std::forward< U >( src ) };
        }
};
 
template <
    range_container Container,
    typename T,
    container_invocable< Container > UnaryCallable = std::identity >
[[nodiscard]] constexpr T
joined( Container&& cont, T const& val, UnaryCallable&& f = std::identity() )
{
        if ( cont.empty() )
                return T{};
        T res = f( *std::begin( cont ) );
        for ( auto& item : tail( cont ) )
                res += val + f( item );
        return res;
}
 
template < container Container, typename Iterator >
void copy( Container&& cont, Iterator iter )
{
        for_each( cont, [&]( auto& item ) {
                *iter = item;
                ++iter;
        } );
}
 
template < std::size_t N, typename NullCallable >
constexpr void for_each_index( NullCallable&& f )
{
        impl::index_seq< 0, N >( f );
}
 
template < std::size_t N, typename PredicateCallable >
constexpr std::size_t find_if_index( PredicateCallable&& f )
{
        std::size_t res = N;
        until_index< N >( [&f, &res]< std::size_t i >() {
                res = i;
                return f.template operator()< i >();
        } );
        return res;
}
 
template < std::size_t i, typename PredicateCallable >
constexpr bool until_index( PredicateCallable&& f )
{
        return impl::index_until< 0, i >( f );
}
 
//
template < bounded_derived IndexType, typename Callable >
requires( !requires( Callable f ) {
        { f.template operator()< 0 >() } -> std::same_as< void >;
} )
constexpr auto select_index( IndexType i, Callable&& f )
{
        using T = std::decay_t< decltype( f.template operator()< 0 >() ) >;
        T res{};
        select_index( i, [&res, &f]< std::size_t i >() {
                res = f.template operator()< i >();
        } );
        return res;
}
 
template < bounded_derived IndexType, typename Callable >
requires requires( Callable f ) {
        { f.template operator()< 0 >() } -> std::same_as< void >;
}
constexpr void select_index( IndexType i, Callable&& f )
{
        static_assert( IndexType::min_val == 0 );
        impl::index_switch< 0, IndexType::max_val + 1 >( *i, f );
}
 
template < typename... Args, std::size_t N = sizeof...( Args ) >
constexpr std::array< std::byte, N > bytes( Args const&... args )
{
        return std::array< std::byte, N >{ static_cast< std::byte >( args )... };
}
 
template < typename Arr, typename... Arrs >
constexpr auto merge_arrays( Arr&& first, Arrs&&... arrs )
{
        using value_type = typename std::decay_t< Arr >::value_type;
 
        static_assert(
            ( std::convertible_to< typename std::decay_t< Arrs >::value_type, value_type > && ... &&
              true ),
            "All arrays have to provide similar types" );
 
        constexpr std::size_t size =
            ( std::tuple_size_v< std::decay_t< Arrs > > + ... +
              std::tuple_size_v< std::decay_t< Arr > > );
 
        auto f = [&]< std::size_t... Is >( std::index_sequence< Is... > ) {
                return std::array< value_type, size >{
                    impl::get_ith_item_from_arrays< Is >( first, arrs... )... };
        };
        return f( std::make_index_sequence< size >{} );
}
 
template < std::size_t N, typename T >
constexpr std::array< T, N > filled( T const& item )
{
        return map_f_to_a< N >( range( N ), [&]( auto ) -> T {
                return item;
        } );
}
 
}  // namespace emlabcpp