Compiler Explorer

Source code

#include <functional>
#include <tuple>
#include <type_traits>
#include <map>
#include <optional>
#include <queue>
#include <iostream>

namespace memoization::details
{
    template <typename T>
    struct function_components
    {
    };

template <typename R, typename... Args>
    struct function_components<std::function<R(Args...)>>
    {
        using type = std::tuple<R(Args...), R, std::tuple<std::decay_t<Args>...>>;
    };

template <typename T>
    using function_components_t = typename function_components<T>::type;

template <typename T, auto I>
    using get_function_component_t = std::tuple_element_t<I, function_components_t<T>>;

template <typename T>
    using function_signature_t = get_function_component_t<T, 0>;

template <typename T>
    using function_result_t = get_function_component_t<T, 1>;

template <typename T>
    using function_arguments_t = get_function_component_t<T, 2>;

} // namespace memoization::details

namespace memoization
{
    using namespace memoization::details;

template <typename T>
    using AsFunction = decltype(std::function{std::declval<T>()});

#if defined(__GNUC__) || defined(__GNUG__)
// CTAD bug in gcc, see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98077
#define AS_FUNCTION(T) decltype(std::function{std::declval<T>()})
#else
#define AS_FUNCTION(T) AsFunction<T>
#endif

template <typename T, typename = void>
    struct is_callable : std::false_type
    {
    };

template <typename T>
    struct is_callable<T, std::void_t<AS_FUNCTION(T)>> : std::true_type
    {
    };

template <typename T>
    inline constexpr auto is_callable_v = is_callable<T>::value;

template <typename T>
    struct callable_to_function
    {
        static_assert(is_callable_v<T>);
        using type = AS_FUNCTION(T);
    };

template <typename T>
    using callable_to_function_t = typename callable_to_function<T>::type;

template <typename T>
    struct callable_result
    {
        using type = function_result_t<callable_to_function_t<T>>;
    };

template <typename T>
    using callable_result_t = typename callable_result<T>::type;

template <typename T>
    struct callable_arguments
    {
        using type = function_arguments_t<callable_to_function_t<T>>;
    };

template <typename T>
    using callable_arguments_t = typename callable_arguments<T>::type;

} // namespace memoization

namespace memoization
{
    template <auto CacheCapacity>
    struct LRUCache
    {
    };
} // namespace memoization

namespace memoization::detail
{
    struct MapCache
    {
    };

template <typename Callable>
    using OrderedMap = std::map<callable_arguments_t<Callable>, callable_result_t<Callable>, std::less<>>;

template <typename Container, auto CacheCapacity>
    struct LRUCacheImpl
    {
        Container cacheMap{};
        std::queue<typename Container::const_iterator> cacheQueue{};
    };

template <typename Cache, typename Key>
    auto findInCache(const Cache &cache, const Key &key)
    {
        auto iterator{cache.find(key)};
        return iterator == cache.end() ? std::nullopt : std::optional{iterator};
    }

template <typename T, auto CacheCapacity, typename Key>
    auto findInCache(const LRUCacheImpl<T, CacheCapacity> &lru, const Key &key)
    {
        return findInCache(lru.cacheMap, key);
    }

template <typename Cache, typename Key, typename Value>
    auto emplaceInCache(Cache &cache, const Key &key, Value &&value)
    {
        return cache.try_emplace(key, std::forward<Value>(value)).first;
    }

template <typename T, auto CacheCapacity, typename Key, typename Value>
    auto emplaceInCache(LRUCacheImpl<T, CacheCapacity> &lru, const Key &key, Value &&value)
    {
        if (lru.cacheQueue.size() == CacheCapacity)
        {
            lru.cacheMap.erase(lru.cacheQueue.front());
            lru.cacheQueue.pop();
        }
        auto iterator{emplaceInCache(lru.cacheMap, key, std::forward<Value>(value))};
        return lru.cacheQueue.emplace(iterator);
    }

template <typename Callable, typename Arguments, typename Cache>
    auto applyFunction(Callable &callable, const Arguments &arguments, Cache &cache)
    {
        auto result{std::apply(callable, arguments)};
        return emplaceInCache(cache, arguments, std::move(result));
    }

template <typename CacheReturn, typename Callable, typename Cache>
    auto createMemoizer(Callable callable, Cache cache)
    {
        return [callable{std::move(callable)}, cache{std::move(cache)}](auto &&... args) mutable -> CacheReturn {
            auto arguments{std::forward_as_tuple(std::forward<decltype(args)>(args)...)};
            if (auto maybeValue{findInCache(cache, arguments)})
            {
                return (*maybeValue)->second;
            }
            return applyFunction(callable, arguments, cache)->second;
        };
    }

template <typename Cache, typename Callable>
    struct create_cache
    {
        using type = OrderedMap<Callable>;
    };

template <auto CacheCapacity, typename Callable>
    struct create_cache<LRUCache<CacheCapacity>, Callable>
    {
        static_assert(CacheCapacity > 0, "LRU cache capacity must be greater 0!");
        using type = LRUCacheImpl<OrderedMap<Callable>, CacheCapacity>;
    };

template <typename Cache, typename Callable>
    using create_cache_t = typename create_cache<Cache, Callable>::type;

template <typename CacheTag, typename Result>
    struct result_adaption : std::add_lvalue_reference<std::add_const_t<Result>>
    {
    };

template <auto CacheCapacity, typename Result>
    struct result_adaption<LRUCache<CacheCapacity>, Result> : std::remove_cv<std::remove_reference_t<Result>>
    {
    };

template <typename CacheTag, typename Result>
    using result_adaption_t = typename result_adaption<CacheTag, Result>::type;

} // namespace memoization::detail

namespace memoization
{
    using namespace memoization::detail;

template <typename CacheTag = MapCache, typename Callable>
    [[nodiscard]] auto memoize(Callable &&callable) noexcept
    {
        using ResultType = callable_result_t<Callable>;
        static_assert(!std::is_void_v<ResultType>, "Callable with void return type cannot be memoized!");
        static_assert(
            !(std::is_reference_v<ResultType> && !std::is_const_v<std::remove_reference_t<ResultType>>),
            "Callable with non-const reference return type cannot be memoized!");
        static_assert(std::is_copy_constructible_v<ResultType>, "Callable return type must be copy constructible!");
        static_assert(
            std::tuple_size_v<callable_arguments_t<Callable>> > 0, "Callable with no arguments cannot be memoized!");

using AdaptedResultType = result_adaption_t<CacheTag, ResultType>;
        using CacheType = create_cache_t<CacheTag, callable_to_function_t<Callable>>;

return createMemoizer<AdaptedResultType>(std::forward<Callable>(callable), CacheType{});
    }

template <auto CacheCapacity, typename Callable>
    [[nodiscard]] auto memoizeWithLRU(Callable &&callable) noexcept
    {
        return memoize<LRUCache<CacheCapacity>>(std::forward<Callable>(callable));
    }
} // namespace memoization

int main()
{
    auto fooM = memoization::memoize([](int n, std::string s){ return 42; });
    auto fooMWithLRU = memoization::memoizeWithLRU<3>([](int n, std::string s){ return 72; });

auto x = fooM(14, "bla");
    auto y = fooMWithLRU(14, "blubb");

std::cout << "fooM result " << x << " fooMWithLRU result " << y;

return 0;
}