Library
This documentation is automatically generated by online-judge-tools/verification-helper
Cached
(src/utils/cached.hpp)
- View this file on GitHub
- Last update: 2021-11-30 17:55:32+09:00
- Include:
#include "src/utils/cached.hpp"
Depends on
Code
#pragma once
/**
* @file cached.hpp
* @brief Cached
*/
#include "fixed_point.hpp"
#include "lib/cxx17"
namespace workspace {
namespace _cached_impl {
// Convert keys to tuple.
template <class... _Args> struct as_tuple {
using type = decltype(std::tuple_cat(
std::declval<std::tuple<std::conditional_t<
std::is_convertible<std::decay_t<_Args>, _Args>::value,
std::decay_t<_Args>, _Args>>>()...));
};
// Associative array.
template <class _Value, class... _Keys>
struct assoc
: std::integral_constant<int, !std::is_void<_Value>::value>,
std::conditional_t<std::is_void<_Value>::value,
std::set<typename as_tuple<_Keys...>::type>,
std::map<typename as_tuple<_Keys...>::type, _Value>> {
};
// Non-resursive lambda type.
template <class _F, class = void> struct is_recursive : std::false_type {};
// Resursive lambda type.
template <class _F>
struct is_recursive<
_F, std::__void_t<decltype(&_F::template operator()<fixed_point<_F> &>)>>
: std::true_type {};
// Recursive ver.
template <class _F> class _recursive {
template <class...> struct _cache;
template <class _G, class _R, class _H, class... _Args>
struct _cache<_R (_G::*)(_H, _Args...)> : assoc<_R, _Args...> {};
template <class _G, class _R, class _H, class... _Args>
struct _cache<_R (_G::*)(_H, _Args...) const> : assoc<_R, _Args...> {};
template <class _G, class _R, class _H, class... _Args>
struct _cache<_R (_G::*)(_H, _Args...) noexcept> : assoc<_R, _Args...> {};
template <class _G, class _R, class _H, class... _Args>
struct _cache<_R (_G::*)(_H, _Args...) const noexcept> : assoc<_R, _Args...> {
};
public:
using cache_type =
_cache<decltype(&_F::template operator()<_recursive<_F> &>)>;
private:
_F __fn;
cache_type __c;
struct _wrapper {
_F &__fn;
cache_type &__c;
template <class... _Args>
decltype(auto) operator()(_Args &&...__args) noexcept(
noexcept(__fn(*this, std::forward<_Args>(__args)...))) {
typename cache_type::key_type __key{__args...};
auto __i = __c.lower_bound(__key);
if _CXX17_CONSTEXPR (cache_type::value) {
if (__i != __c.end() && __i->first == __key) return __i->second;
return __c
.emplace_hint(__i, std::move(__key),
__fn(*this, std::forward<_Args>(__args)...))
->second;
}
else if (__i == __c.end() || *__i != __key)
__c.emplace_hint(__i, std::move(__key)),
__fn(*this, std::forward<_Args>(__args)...);
}
};
public:
_recursive(_F &&__x) noexcept : __fn(__x) {}
// Function call.
template <class... _Args>
decltype(auto) operator()(_Args &&...__args) noexcept(noexcept(_wrapper{
__fn, __c}(std::forward<_Args>(__args)...))) {
return _wrapper{__fn, __c}(std::forward<_Args>(__args)...);
}
};
// Non-recursive ver.
template <class _F> class _non_recursive {
template <class _T, class = void> struct _get_func { using type = _T; };
template <class _T>
struct _get_func<_T, std::__void_t<decltype(&_T::operator())>> {
using type = decltype(&_T::operator());
};
template <class...> struct _cache;
template <class _R, class... _Args>
struct _cache<_R(_Args...)> : assoc<_R, _Args...> {};
template <class _R, class... _Args>
struct _cache<_R (*)(_Args...)> : assoc<_R, _Args...> {};
template <class _G, class _R, class... _Args>
struct _cache<_R (_G::*)(_Args...)> : assoc<_R, _Args...> {};
template <class _G, class _R, class... _Args>
struct _cache<_R (_G::*)(_Args...) const> : assoc<_R, _Args...> {};
template <class _R, class... _Args>
struct _cache<_R(_Args...) noexcept> : assoc<_R, _Args...> {};
template <class _R, class... _Args>
struct _cache<_R (*)(_Args...) noexcept> : assoc<_R, _Args...> {};
template <class _G, class _R, class... _Args>
struct _cache<_R (_G::*)(_Args...) noexcept> : assoc<_R, _Args...> {};
template <class _G, class _R, class... _Args>
struct _cache<_R (_G::*)(_Args...) const noexcept> : assoc<_R, _Args...> {};
public:
using cache_type = _cache<typename _get_func<_F>::type>;
private:
_F __fn;
cache_type __c;
public:
_non_recursive(_F &&__x) noexcept : __fn(__x) {}
// Function call.
template <class... _Args>
decltype(auto) operator()(_Args &&...__args) noexcept(
noexcept(__fn(std::forward<_Args>(__args)...))) {
typename cache_type::key_type __key{__args...};
auto __i = __c.lower_bound(__key);
if _CXX17_CONSTEXPR (cache_type::value) {
if (__i != __c.end() && __i->first == __key) return __i->second;
return __c
.emplace_hint(__i, std::move(__key),
__fn(std::forward<_Args>(__args)...))
->second;
}
else if (__i == __c.end() || *__i != __key)
__c.emplace_hint(__i, std::move(__key)),
__fn(std::forward<_Args>(__args)...);
}
};
template <class _F>
using _cached = std::conditional_t<is_recursive<_F>::value, _recursive<_F>,
_non_recursive<_F>>;
} // namespace _cached_impl
/**
* @brief Cached caller of function
*/
template <class _F> class cached : public _cached_impl::_cached<_F> {
public:
// Construct a new cached object.
cached() noexcept : _cached_impl::_cached<_F>(_F{}) {}
// Construct a new cached object.
cached(_F __x) noexcept : _cached_impl::_cached<_F>(std::move(__x)) {}
};
} // namespace workspace#line 2 "src/utils/cached.hpp"
/**
* @file cached.hpp
* @brief Cached
*/
#line 2 "src/utils/fixed_point.hpp"
/**
* @file fixed_point.hpp
* @brief Fixed Point Combinator
*/
#include <utility>
namespace workspace {
// Fixed Point Combinator.
template <class _F> class fixed_point {
struct _wrapper {
_F &__ref;
template <class... _Args>
decltype(auto) operator()(_Args &&...__args) noexcept(
noexcept(__ref(*this, std::forward<_Args>(__args)...))) {
return __ref(*this, std::forward<_Args>(__args)...);
}
};
_F __fn;
public:
// Construct a new fixed-point object.
fixed_point(_F __x) noexcept : __fn(__x) {}
// Function call.
template <class... _Args>
decltype(auto) operator()(_Args &&...__args) noexcept(noexcept(_wrapper{
__fn}(std::forward<_Args>(__args)...))) {
return _wrapper{__fn}(std::forward<_Args>(__args)...);
}
};
} // namespace workspace
#line 2 "lib/cxx17"
#line 2 "lib/cxx14"
#ifndef _CXX14_CONSTEXPR
#if __cplusplus >= 201402L
#define _CXX14_CONSTEXPR constexpr
#else
#define _CXX14_CONSTEXPR
#endif
#endif
#line 4 "lib/cxx17"
#ifndef _CXX17_CONSTEXPR
#if __cplusplus >= 201703L
#define _CXX17_CONSTEXPR constexpr
#else
#define _CXX17_CONSTEXPR
#endif
#endif
#ifndef _CXX17_STATIC_ASSERT
#if __cplusplus >= 201703L
#define _CXX17_STATIC_ASSERT static_assert
#else
#define _CXX17_STATIC_ASSERT assert
#endif
#endif
#include <iterator>
#if __cplusplus < 201703L
namespace std {
/**
* @brief Return the size of a container.
* @param __cont Container.
*/
template <typename _Container>
constexpr auto size(const _Container& __cont) noexcept(noexcept(__cont.size()))
-> decltype(__cont.size()) {
return __cont.size();
}
/**
* @brief Return the size of an array.
*/
template <typename _Tp, size_t _Nm>
constexpr size_t size(const _Tp (&)[_Nm]) noexcept {
return _Nm;
}
/**
* @brief Return whether a container is empty.
* @param __cont Container.
*/
template <typename _Container>
[[nodiscard]] constexpr auto empty(const _Container& __cont) noexcept(
noexcept(__cont.empty())) -> decltype(__cont.empty()) {
return __cont.empty();
}
/**
* @brief Return whether an array is empty (always false).
*/
template <typename _Tp, size_t _Nm>
[[nodiscard]] constexpr bool empty(const _Tp (&)[_Nm]) noexcept {
return false;
}
/**
* @brief Return whether an initializer_list is empty.
* @param __il Initializer list.
*/
template <typename _Tp>
[[nodiscard]] constexpr bool empty(initializer_list<_Tp> __il) noexcept {
return __il.size() == 0;
}
struct monostate {};
} // namespace std
#else
#include <variant>
#endif
#line 10 "src/utils/cached.hpp"
namespace workspace {
namespace _cached_impl {
// Convert keys to tuple.
template <class... _Args> struct as_tuple {
using type = decltype(std::tuple_cat(
std::declval<std::tuple<std::conditional_t<
std::is_convertible<std::decay_t<_Args>, _Args>::value,
std::decay_t<_Args>, _Args>>>()...));
};
// Associative array.
template <class _Value, class... _Keys>
struct assoc
: std::integral_constant<int, !std::is_void<_Value>::value>,
std::conditional_t<std::is_void<_Value>::value,
std::set<typename as_tuple<_Keys...>::type>,
std::map<typename as_tuple<_Keys...>::type, _Value>> {
};
// Non-resursive lambda type.
template <class _F, class = void> struct is_recursive : std::false_type {};
// Resursive lambda type.
template <class _F>
struct is_recursive<
_F, std::__void_t<decltype(&_F::template operator()<fixed_point<_F> &>)>>
: std::true_type {};
// Recursive ver.
template <class _F> class _recursive {
template <class...> struct _cache;
template <class _G, class _R, class _H, class... _Args>
struct _cache<_R (_G::*)(_H, _Args...)> : assoc<_R, _Args...> {};
template <class _G, class _R, class _H, class... _Args>
struct _cache<_R (_G::*)(_H, _Args...) const> : assoc<_R, _Args...> {};
template <class _G, class _R, class _H, class... _Args>
struct _cache<_R (_G::*)(_H, _Args...) noexcept> : assoc<_R, _Args...> {};
template <class _G, class _R, class _H, class... _Args>
struct _cache<_R (_G::*)(_H, _Args...) const noexcept> : assoc<_R, _Args...> {
};
public:
using cache_type =
_cache<decltype(&_F::template operator()<_recursive<_F> &>)>;
private:
_F __fn;
cache_type __c;
struct _wrapper {
_F &__fn;
cache_type &__c;
template <class... _Args>
decltype(auto) operator()(_Args &&...__args) noexcept(
noexcept(__fn(*this, std::forward<_Args>(__args)...))) {
typename cache_type::key_type __key{__args...};
auto __i = __c.lower_bound(__key);
if _CXX17_CONSTEXPR (cache_type::value) {
if (__i != __c.end() && __i->first == __key) return __i->second;
return __c
.emplace_hint(__i, std::move(__key),
__fn(*this, std::forward<_Args>(__args)...))
->second;
}
else if (__i == __c.end() || *__i != __key)
__c.emplace_hint(__i, std::move(__key)),
__fn(*this, std::forward<_Args>(__args)...);
}
};
public:
_recursive(_F &&__x) noexcept : __fn(__x) {}
// Function call.
template <class... _Args>
decltype(auto) operator()(_Args &&...__args) noexcept(noexcept(_wrapper{
__fn, __c}(std::forward<_Args>(__args)...))) {
return _wrapper{__fn, __c}(std::forward<_Args>(__args)...);
}
};
// Non-recursive ver.
template <class _F> class _non_recursive {
template <class _T, class = void> struct _get_func { using type = _T; };
template <class _T>
struct _get_func<_T, std::__void_t<decltype(&_T::operator())>> {
using type = decltype(&_T::operator());
};
template <class...> struct _cache;
template <class _R, class... _Args>
struct _cache<_R(_Args...)> : assoc<_R, _Args...> {};
template <class _R, class... _Args>
struct _cache<_R (*)(_Args...)> : assoc<_R, _Args...> {};
template <class _G, class _R, class... _Args>
struct _cache<_R (_G::*)(_Args...)> : assoc<_R, _Args...> {};
template <class _G, class _R, class... _Args>
struct _cache<_R (_G::*)(_Args...) const> : assoc<_R, _Args...> {};
template <class _R, class... _Args>
struct _cache<_R(_Args...) noexcept> : assoc<_R, _Args...> {};
template <class _R, class... _Args>
struct _cache<_R (*)(_Args...) noexcept> : assoc<_R, _Args...> {};
template <class _G, class _R, class... _Args>
struct _cache<_R (_G::*)(_Args...) noexcept> : assoc<_R, _Args...> {};
template <class _G, class _R, class... _Args>
struct _cache<_R (_G::*)(_Args...) const noexcept> : assoc<_R, _Args...> {};
public:
using cache_type = _cache<typename _get_func<_F>::type>;
private:
_F __fn;
cache_type __c;
public:
_non_recursive(_F &&__x) noexcept : __fn(__x) {}
// Function call.
template <class... _Args>
decltype(auto) operator()(_Args &&...__args) noexcept(
noexcept(__fn(std::forward<_Args>(__args)...))) {
typename cache_type::key_type __key{__args...};
auto __i = __c.lower_bound(__key);
if _CXX17_CONSTEXPR (cache_type::value) {
if (__i != __c.end() && __i->first == __key) return __i->second;
return __c
.emplace_hint(__i, std::move(__key),
__fn(std::forward<_Args>(__args)...))
->second;
}
else if (__i == __c.end() || *__i != __key)
__c.emplace_hint(__i, std::move(__key)),
__fn(std::forward<_Args>(__args)...);
}
};
template <class _F>
using _cached = std::conditional_t<is_recursive<_F>::value, _recursive<_F>,
_non_recursive<_F>>;
} // namespace _cached_impl
/**
* @brief Cached caller of function
*/
template <class _F> class cached : public _cached_impl::_cached<_F> {
public:
// Construct a new cached object.
cached() noexcept : _cached_impl::_cached<_F>(_F{}) {}
// Construct a new cached object.
cached(_F __x) noexcept : _cached_impl::_cached<_F>(std::move(__x)) {}
};
} // namespace workspace