brick-cons

// -*- mode: C++; indent-tabs-mode: nil; c-basic-offset: 4 -*-

/*
 * (c) 2019 Petr Ročkai <code@fixp.eu>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#pragma once

#include "brick-assert"
#include <type_traits>
#include <optional>
#include <memory>

namespace brq
{

    struct nil
    {
        using co = nil;
        using unique_t = nil;
        static constexpr bool empty = true;
        static constexpr size_t size = 0;

        template< int idx > using type_at = void;

        template< typename T, int = 0 >
        static constexpr int index_of = -1;

        template< template< typename > class f > using map_t = nil;
        template< template< typename > class f > using filter_t = nil;
        template< typename L >                   using cat_t = L;

        template< typename F >     void each( const F & ) const {}
        template< typename F >     nil map( F ) const { return {}; }
        template< typename... Fs > auto match( Fs... ) const { return std::nullopt; }
        template< typename L >     auto cat( const L &l ) const { return l; }
        template< typename T >     static constexpr bool has = false;

        template< template< typename > class P >
        constexpr nil filter() const { return {}; }
        constexpr nil reverse() const { return {}; }

        template< typename F, typename... args_t >
        auto apply( const F &f, args_t && ... args ) const
        {
            return f( args... );
        }
    };

    template< typename, typename > struct cons;
    template< typename, typename > struct ns;

    template< template< typename > class pred_t, typename cons_t >
    constexpr auto cons_filter( const cons_t &x )
    {
        if constexpr ( cons_t::empty )
            return nil();
        else if constexpr ( pred_t< typename cons_t::car_t >::value )
            return make_cons( x.car(), cons_filter< pred_t >( x.cdr() ) );
        else
            return cons_filter< pred_t >( x.cdr() );
    }

    template< typename A, typename B >
    auto make_cons( const A &a, const B &b ) { return cons< A, B >( a, b ); }

    template< typename A, typename B >
    struct cons : B
    {
        using car_t = A;
        using cdr_t = B;
        using co = ns< car_t, typename cdr_t::co >;

        car_t _car;

        operator       car_t&()       { return _car; }
        operator const car_t&() const { return _car; }

        car_t       &car()       { return _car; }
        const car_t &car() const { return _car; }
        cdr_t       &cdr()       { return *this; }
        const cdr_t &cdr() const { return *this; }

        template< typename F > void each( const F &f )       { f( car() ); cdr().each( f ); }
        template< typename F > void each( const F &f ) const { f( car() ); cdr().each( f ); }
        template< typename L > auto cat( const L &l ) const { return make_cons( car(), cdr().cat( l ) ); }
        constexpr auto reverse() const { nil rev; return cons_reverse( *this, rev ); }

        template< typename T > auto &get()
        {
            if constexpr ( std::is_same_v< std::remove_reference_t< T >, car_t > )
                return car();
            else
                return cdr().template get< T >();
        }

        template< typename L >
        auto view()
        {
            if constexpr ( std::is_same_v< L, nil > )
                return nil();
            else
            {
                static_assert( has< std::remove_reference_t< typename L::car_t > > );
                auto tail = view< typename L::cdr_t >();
                return cons< typename L::car_t, decltype( tail ) >( get< typename L::car_t >(), tail );
            }
        }

        static constexpr bool empty = false;
        static constexpr size_t size = 1 + cdr_t::size;

        template< int idx >
        using type_at = std::conditional_t< idx == 0, car_t,
                                            typename cdr_t::template type_at< idx - 1 > >;

        template< typename T, int i = 0 > static constexpr int index_of =
            std::is_same_v< T, car_t > ? i : cdr_t::template index_of< T, i + 1 >;

        template< typename T > static constexpr bool has =
            std::is_same_v< T, car_t > || cdr_t::template has< T >;

        template< template< typename > class f >
        using map_t = cons< f< car_t >, typename cdr_t::template map_t< f > >;
        using unique_t = std::conditional_t< cdr_t::unique_t::template has< car_t >,
                                             typename cdr_t::unique_t,
                                             cons< car_t, typename cdr_t::unique_t > >;
        template< template< typename > class f >
        using filter_t = decltype( cons_filter< f >( std::declval< cons >() ) );

        template< typename L > using cat_t = cons< car_t, typename cdr_t::template cat_t< L > >;

        template< typename F, typename... args_t >
        auto apply( const F &f, args_t &&... args ) const
        {
            return cdr().apply( f, car(), std::forward< args_t >( args ) ... );
        }

        template< typename F, typename... args_t >
        auto apply( const F &f, args_t &&... args )
        {
            return cdr().apply( f, car(), std::forward< args_t >( args ) ... );
        }

        template< template< typename > class P >
        constexpr auto filter() const { return cons_filter< P >( *this ); }

        template< typename F >
        auto map( F f )
        {
            auto car_ = f( car() );
            auto cdr_ = cdr().map( f );
            return make_cons( car_, cdr_ );
        }

        template< typename F >
        auto map( F f ) const
        {
            auto car_ = f( car() );
            auto cdr_ = cdr().map( f );
            return make_cons( car_, cdr_ );
        }

        cons( const car_t &car ) : _car( car ) {}
        cons( const car_t &car, const cdr_t &cdr ) : cdr_t( cdr ), _car( car ) {}

        template< typename ucar_t, typename ucdr_t >
        cons( ucar_t && car, ucdr_t && cdr )
            : cdr_t( std::forward< ucdr_t >( cdr ) ),
              _car( std::forward< ucar_t >( car ) )
        {}

        template< typename T, typename U, typename... Us >
        cons( const T &t, const U &u, const Us &... us ) : cdr_t( u, us... ), _car( t ) {}

        cons() = default;
    };

    template< typename F > auto zip( F, nil, nil ) { return nil(); }

    template< typename F, typename A, typename B >
    auto zip( F f, A a, B b )
    {
        auto car_ = f( a.car(), b.car() );
        auto cdr_ = zip( f, a.cdr(), b.cdr() );
        return make_cons( car_, cdr_ );
    }

    template< typename D >
    constexpr auto cons_reverse( nil, const D &rev )
    {
        return rev;
    }

    template< typename C, typename D >
    constexpr auto cons_reverse( const C &cell, const D &rev )
    {
        return cons_reverse( cell.cdr(), cons< typename C::car_t, D >( cell.car(), rev ) );
    }

    static auto cons_list() { return nil(); }
    static auto cons_list_ref() { return nil(); }

    template< typename T, typename... Ts >
    auto cons_list_ref( T &&t, Ts &&... ts )
    {
        auto tail = cons_list_ref( std::forward< Ts >( ts )... );
        return cons< T, decltype( tail ) >( std::forward< T >( t ), std::move( tail ) );
    }

    template< typename T, typename... Ts >
    auto cons_list( const T &t, const Ts &... ts )
    {
        auto tail = cons_list( ts... );
        return cons< T, decltype( tail ) >( t, tail );
    }

    template< typename... Ts > struct cons_list_t__;

    template< typename T, typename... Ts >
    struct cons_list_t__< T, Ts... >
    {
        using type = cons< T, typename cons_list_t__< Ts... >::type >;
    };

    template<> struct cons_list_t__<>
    {
        using type = nil;
    };

    template< typename... Ts >
    using cons_list_t_ = typename cons_list_t__< Ts... >::type;

    template< typename... Ts >
    struct cons_list_t: cons_list_t_< Ts... >
    {
        using cons_list_t_< Ts... >::cons_list_t_;
    };

    template< typename... Ts >
    cons_list_t( Ts... ) -> cons_list_t< Ts... >;

    static_assert( std::is_same_v< cons_list_t< int, int >::unique_t, cons_list_t_< int > > );
    static_assert( std::is_same_v< cons_list_t< int, int, int >::unique_t, cons_list_t_< int > > );

    template< typename... > using discard_t = void;
    template< typename T, typename = void > struct is_list : std::false_type {};

    template<> struct is_list< nil > : std::true_type {};
    template<> struct is_list< cons_list_t<> > : std::true_type {};
    template< typename T >
    struct is_list< T, discard_t< typename T::car_t, typename T::cdr_t > > : std::true_type {};

    template< typename T > constexpr bool is_list_v = is_list< T >::value;

    template< typename car_t_, typename cdr_t_ >
    struct ns
    {
        using car_t = car_t_;
        using cdr_t = cdr_t_;
        using co = cons< car_t, typename cdr_t::co >;

        bool _is_car;
        union { car_t car; cdr_t cdr; };

        ns( const car_t &car ) : _is_car( true ), car( car ) {}
        ns( car_t &&car ) : _is_car( true ), car( std::move( car ) ) {}
        ns() : _is_car( false ), cdr() {}
        ns( const ns &o ) : ns() { *this = o; }
        ns( ns &&o ) : ns() { *this = std::move( o ); }
        void destroy() { if ( _is_car ) car.~car_t(); else cdr.~cdr_t(); }
        ~ns() { destroy(); }

        ns &operator=( const ns &o )
        {
            if ( &o == this )
                return *this;
            destroy();
            _is_car = o._is_car;
            if ( _is_car )
                std::uninitialized_copy( &o.car, &o.car + 1, &car );
            else
                std::uninitialized_copy( &o.cdr, &o.cdr + 1, &cdr );
            return *this;
        }

        ns &operator=( ns &&o )
        {
            if ( &o == this )
                return *this;
            destroy();
            _is_car = o._is_car;
            if ( _is_car )
                std::uninitialized_move( &o.car, &o.car + 1, &car );
            else
                std::uninitialized_move( &o.cdr, &o.cdr + 1, &cdr );
            return *this;
        }

        template< typename X >
        ns( const X &cdr ) : _is_car( false ), cdr( cdr ) {}
        template< typename X >
        ns( X &&cdr ) : _is_car( false ), cdr( std::move( cdr ) ) {}

        template< typename arg_t >
        std::optional< std::reference_wrapper< arg_t > > get()
        {
            if constexpr ( std::is_same_v< arg_t, car_t > )
            {
                if ( _is_car )
                    return car;
                else
                    return std::nullopt;
            }
            else
                return cdr.template get< arg_t >();
        }

        auto match() const { return std::nullopt; }

        template< typename F, typename... Fs >
        auto match( F f, Fs... fs )
        {
            if constexpr ( std::is_invocable_v< F, car_t & > )
            {
                using R = std::invoke_result_t< F, car_t & >;
                using R_ = std::conditional_t< std::is_same_v< R, void >, void, std::optional< R > >;
                if ( _is_car )
                    return R_( f( car ) );
                else
                    return R_( cdr.match( f, fs... ) );
            }
            else
            {
                using R1 = decltype( match( fs... ) );
                using R2 = decltype( cdr.match( f, fs... ) );
                using R = std::conditional_t< std::is_same_v< R1, std::nullopt_t >, R2, R1 >;
                if ( _is_car )
                    return R( match( fs... ) );
                else
                    return R( cdr.match( f, fs... ) );
            }
        }

        template< typename F, typename... Fs >
        auto match( F f, Fs... fs ) const
        {
            if constexpr ( std::is_invocable_v< F, car_t & > )
            {
                using R = std::invoke_result_t< F, car_t & >;
                using R_ = std::conditional_t< std::is_same_v< R, void >, void, std::optional< R > >;
                if ( _is_car )
                    return R_( f( car ) );
                else
                    return R_( cdr.match( f, fs... ) );
            }
            else
            {
                using R1 = decltype( match( fs... ) );
                using R2 = decltype( cdr.match( f, fs... ) );
                using R = std::conditional_t< std::is_same_v< R1, std::nullopt_t >, R2, R1 >;
                if ( _is_car )
                    return R( match( fs... ) );
                else
                    return R( cdr.match( f, fs... ) );
            }
        }
    };
}

namespace t_brq
{
    struct cons
    {
        TEST( view_ref )
        {
            auto x = brq::cons_list( 3.0, 7, static_cast< const char * >( "bla " ) );
            using v = brq::cons_list_t< int & >;
            static_assert( std::is_same_v< v::car_t, int & > );
            auto y = x.view< v >();
            ASSERT_EQ( y.car(), 7 );
            y.car() ++;
            ASSERT_EQ( y.car(), 8 );
            ASSERT_EQ( x.cdr().car(), 8 );
        }

        TEST( view_val )
        {
            auto x = brq::cons_list( 3.0, 7, static_cast< const char * >( "bla " ) );
            using v = brq::cons_list_t< int >;
            auto y = x.view< v >();
            ASSERT_EQ( y.car(), 7 );
            y.car() ++;
            ASSERT_EQ( y.car(), 8 );
            ASSERT_EQ( x.cdr().car(), 7 );
        }

        TEST( val_ctor )
        {
            int x;
            auto y = brq::cons_list( x );
            auto z = brq::cons_list_ref( x );
            static_assert( std::is_same_v< decltype( y ), brq::cons_list_t_< int > > );
            static_assert( std::is_same_v< decltype( z ), brq::cons_list_t_< int & > > );
        }
    };

    using test_list = brq::cons_list_t< int, long, void * >;
    static_assert( test_list::index_of< int > == 0 );
    static_assert( test_list::index_of< long > == 1 );
    static_assert( test_list::index_of< void * > == 2 );
}

// vim: syntax=cpp tabstop=4 shiftwidth=4 expandtab ft=cpp