numeric/extremum_seeker.hpp

View this file on GitHub
Last update: 2024-07-27 23:01:00+09:00
Include: #include "numeric/extremum_seeker.hpp"

Depends on

Required by

Verified with

verify/aizu-online-judge/itp1_1_a/0001.test.cpp

Code

#pragma once


#include <functional>
#include <type_traits>


#include "snippet/aliases.hpp"
#include "snippet/iterations.hpp"

#include "internal/dev_env.hpp"
#include "internal/types.hpp"

#include "adaptor/gnu/hash_table.hpp"

#include "numeric/limits.hpp"


namespace uni {


template<class Signature>
struct extremum_seeker;


template<class T, std::floating_point Arg>
struct extremum_seeker<T(Arg)> {
    using value_type = T;
    using arg_type = Arg;

  private:
    std::function<T(Arg)> _f;


    template<const internal::size_t ITERATIONS>
    std::pair<arg_type, arg_type> search(arg_type low, arg_type high, const auto comp) const noexcept(NO_EXCEPT) {
        REP(ITERATIONS) {
            const auto p = low + (high - low) / 3;
            const auto q = high - (high - low) / 3;

            if(comp(p, q)) high = q;
            else low = p;
        }

        return { low, high };
    }

  public:
    template<class F>
        requires std::same_as<std::invoke_result_t<F, Arg>, T>
    extremum_seeker(F&& f) noexcept(NO_EXCEPT) : _f(std::forward<F>(f)) {};


    template<const internal::size_t ITERATIONS = 100'000>
    std::pair<arg_type, arg_type> arg_min(
        arg_type low = uni::numeric_limits<arg_type>::arithmetic_negative_infinity(),
        arg_type high = uni::numeric_limits<arg_type>::arithmetic_infinity()
    ) const noexcept(NO_EXCEPT) {
        const auto comp = [&](const arg_type lhs, const arg_type rhs) noexcept(NO_EXCEPT) {
            return this->_f(lhs) < this->_f(rhs);
        };
        return this->search<ITERATIONS>(low, high, comp);
    }

    template<const internal::size_t ITERATIONS = 100'000>
    std::pair<arg_type, arg_type> arg_max(
        arg_type low = uni::numeric_limits<arg_type>::arithmetic_negative_infinity(),
        arg_type high = uni::numeric_limits<arg_type>::arithmetic_infinity()
    ) const noexcept(NO_EXCEPT) {
        const auto comp = [&](const arg_type lhs, const arg_type rhs) noexcept(NO_EXCEPT) {
            return this->_f(lhs) > this->_f(rhs);
        };
        return this->search<ITERATIONS>(low, high, comp);
    }


    template<const internal::size_t ITERATIONS = 100'000>
    auto min(
        const arg_type _low = uni::numeric_limits<arg_type>::arithmetic_negative_infinity(),
        const arg_type _high = uni::numeric_limits<arg_type>::arithmetic_infinity()
    ) const noexcept(NO_EXCEPT) {
        const auto [ low, high ] = this->arg_min<ITERATIONS>(_low, _high);
        auto res = std::min(this->_f(low), this->_f(high));
        FOR(x, low, high) chmin(res, this->_f(x));
        return res;
    }

    template<const internal::size_t ITERATIONS = 100'000>
    auto max(
        const arg_type _low = uni::numeric_limits<arg_type>::arithmetic_negative_infinity(),
        const arg_type _high = uni::numeric_limits<arg_type>::arithmetic_infinity()
    ) const noexcept(NO_EXCEPT) {
        const auto [ low, high ] = this->arg_max<ITERATIONS>(_low, _high);
        auto res = std::max(this->_f(low), this->_f(high));
        FOR(x, low, high) chmax(res, this->_f(x));
        return res;
    }
};


template<class T, std::integral Arg>
struct extremum_seeker<T(Arg)> {
    using value_type = T;
    using arg_type = Arg;

  private:
    std::function<T(Arg)> _f;

    std::vector<arg_type> _fib = { 0, 1 };
    gnu::gp_hash_table<arg_type, value_type> _cache;


    auto _expand(const arg_type size) noexcept(NO_EXCEPT) {
        assert(size >= 0);
        this->_fib.reserve(std::bit_width(to_unsigned(size)));

        if(this->_fib.back() < size) {
            do {
                this->_fib.emplace_back(
                    this->_fib[std::ranges::size(this->_fib) - 1] +
                    this->_fib[std::ranges::size(this->_fib) - 2]
                );
            } while(this->_fib.back() < size);

            return std::ranges::prev(this->_fib.end());
        }

        return std::ranges::lower_bound(this->_fib, size);
    }

    auto _func(const arg_type size) noexcept(NO_EXCEPT) {
        if(this->_cache.contains(size)) return this->_cache[size];
        return this->_cache[size] = this->_f(size);
    }

    auto _search(arg_type low, const arg_type high, const auto comp) noexcept(NO_EXCEPT) {
        if(low == high) return low;

        auto _low = low - 1;
        const auto itr = this->_expand(high - _low + 1);
        auto _high = *itr + _low;
        auto diff = *std::ranges::prev(itr);

        while(true) {
            const auto p = _high - diff;
            const auto q = _low + diff;

            if(p == q) return p;

            if(comp(p, q)) _high = q;
            else _low = p;

            diff = diff - (q - p);
        }
    }

  public:
    template<class F>
        requires std::same_as<std::invoke_result_t<F, Arg>, T>
    extremum_seeker(F&& f, const arg_type init_size = 0) noexcept(NO_EXCEPT)
      : _f(std::forward<F>(f))
    {
        this->_expand(init_size);
    }


    auto arg_min(
        const arg_type low = uni::numeric_limits<arg_type>::arithmetic_negative_infinity(),
        const arg_type high = uni::numeric_limits<arg_type>::arithmetic_infinity()
    ) noexcept(NO_EXCEPT) {
        const auto comp = [&](const arg_type lhs, const arg_type rhs) noexcept(NO_EXCEPT) {
            if(high < rhs) return true;
            return this->_func(lhs) < this->_func(rhs);
        };
        return this->_search(low, high, comp);
    }

    auto arg_max(
        const arg_type low = uni::numeric_limits<arg_type>::arithmetic_negative_infinity(),
        const arg_type high = uni::numeric_limits<arg_type>::arithmetic_infinity()
    ) noexcept(NO_EXCEPT) {
        const auto comp = [&](const arg_type lhs, const arg_type rhs) noexcept(NO_EXCEPT) {
            if(high < rhs) return true;
            return this->_func(lhs) > this->_func(rhs);
        };
        return this->_search(low, high, comp);
    }


    inline auto min(
        const arg_type _low = uni::numeric_limits<arg_type>::arithmetic_negative_infinity(),
        const arg_type high = uni::numeric_limits<arg_type>::arithmetic_infinity()
    ) noexcept(NO_EXCEPT) {
        return this->_func(this->arg_min(_low, high));
    }

    inline auto max(
        const arg_type _low = uni::numeric_limits<arg_type>::arithmetic_negative_infinity(),
        const arg_type high = uni::numeric_limits<arg_type>::arithmetic_infinity()
    ) noexcept(NO_EXCEPT) {
        return this->_func(this->arg_max(_low, high));
    }
};


} // namespace uni

#line 2 "numeric/extremum_seeker.hpp"


#include <functional>
#include <type_traits>


#line 2 "snippet/aliases.hpp"


#include <cstdint>
#include <utility>
#include <vector>
#include <ranges>


#line 2 "internal/dev_env.hpp"


#ifdef LOCAL_JUDGE
    inline constexpr bool DEV_ENV = true;
    inline constexpr bool NO_EXCEPT = false;
#else
    inline constexpr bool DEV_ENV = false;
    inline constexpr bool NO_EXCEPT = true;
#endif // LOCAL_JUDGE


#if __cplusplus >= 202100L
    #define CPP20 true
    #define CPP23 true
#elif __cplusplus >= 202002L
    #define CPP20 true
    #define CPP23 false
#else
    #define CPP20 false
    #define CPP23 false
#endif
#line 2 "snippet/internal/types.hpp"

#line 4 "snippet/internal/types.hpp"

namespace uni {


using i16 = std::int16_t;
using u16 = std::uint16_t;

using i32 = std::int32_t;
using u32 = std::uint32_t;

using i64 = std::int64_t;
using u64 = std::uint64_t;

#ifdef __GNUC__

using i128 = __int128_t;
using u128 = __uint128_t;

using f128 = __float128;

#endif

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;


} // namespace uni
#line 12 "snippet/aliases.hpp"


#define until(...) while(!(__VA_ARGS__))

#define CONTINUE(...) { __VA_ARGS__; continue; }
#define BREAK(...) { __VA_ARGS__; break; }

#define ALL(x) std::ranges::begin((x)),std::ranges::end((x))
#define RALL(x) std::ranges::rbegin((x)),std::ranges::rend((x))


#define $F first
#define $S second


namespace uni {


constexpr char LN = '\n';
constexpr char SPC = ' ';


constexpr std::pair<int,int> DIRS4[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
constexpr std::pair<int,int> DIRS4P[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }, { 0, 0 } };
constexpr std::pair<int,int> DIRS8[] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } };
constexpr std::pair<int,int> DIRS8P[] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 }, { 0, 0 } };


template<class T> using spair = std::pair<T,T>;


}  // namespace uni


namespace std {

using bit_reference = std::vector<bool>::reference;

bit_reference operator |= (bit_reference a, const bool b) noexcept(NO_EXCEPT) { return a = a | b; }
bit_reference operator &= (bit_reference a, const bool b) noexcept(NO_EXCEPT) { return a = a & b; }

}
#line 2 "snippet/iterations.hpp"

#line 2 "macro/overload.hpp"

#define $OVERLOAD2(arg0, arg1, cmd, ...) cmd
#define $OVERLOAD3(arg0, arg1, arg2, cmd, ...) cmd
#define $OVERLOAD4(arg0, arg1, arg2, arg3, cmd, ...) cmd
#define $OVERLOAD5(arg0, arg1, arg2, arg3, arg4, cmd, ...) cmd
#define $OVERLOAD6(arg0, arg1, arg2, arg3, arg4, arg5, cmd, ...) cmd
#line 2 "macro/basic.hpp"

#define TO_STRING_AUX(x) #x
#define TO_STRING(x) TO_STRING_AUX(x)

#define CONCAT_AUX(x, y) x##y
#define CONCAT(x, y) CONCAT_AUX(x, y)

#define UNPAREN_AUX(...) __VA_ARGS__
#define UNPAREN(...) __VA_ARGS__
#line 6 "snippet/iterations.hpp"


#define LOOP(n) REPI(CONCAT(_$, __COUNTER__), n)

#define REPI(i,n) for(std::remove_cvref_t<decltype(n)> i=0, CONCAT(i, $)=(n); i<CONCAT(i, $); ++i)
#define REPF(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(l), CONCAT(i, $)=(r); i<CONCAT(i, $); ++i)
#define REPIS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l), CONCAT(i, $)=(r); i<CONCAT(i, $); i+=(s))

#define REPR(i,n) for(auto i=(n); --i>=0;)
#define REPB(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(r), CONCAT(i, $)=(l); --i>=CONCAT(i, $);)
#define REPRS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l)+((r)-(l)-1)/(s)*(s), CONCAT(i, $)=(l); i>=CONCAT(i, $); (i-=(s)))

#define REP(...) $OVERLOAD4(__VA_ARGS__, REPIS, REPF, REPI, LOOP)(__VA_ARGS__)
#define REPD(...) $OVERLOAD4(__VA_ARGS__, REPRS, REPB, REPR)(__VA_ARGS__)

#define FORO(i,n) for(int i=0, CONCAT(i, $)=static_cast<int>(n); i<=CONCAT(i, $); ++i)
#define FORI(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(l), CONCAT(i, $)=(r); i<=CONCAT(i, $); ++i)
#define FORIS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l), CONCAT(i, $)=(r); i<=CONCAT(i, $); i+=(s))

#define FORRO(i,n) for(auto i=(n); i>=0; --i)
#define FORR(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(r), CONCAT(i, $)=(l); i>=CONCAT(i, $); --i)
#define FORRS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l)+((r)-(l))/(s)*(s), CONCAT(i, $)=(l); i>=CONCAT(i, $); i-=(s))

#define FOR(...) $OVERLOAD4(__VA_ARGS__, FORIS, FORI, FORO)(__VA_ARGS__)
#define FORD(...) $OVERLOAD4(__VA_ARGS__, FORRS, FORR, FORRO)(__VA_ARGS__)

#define ITR1(e0,v) for(const auto &e0 : (v))
#define ITRP1(e0,v) for(auto e0 : (v))
#define ITRR1(e0,v) for(auto &e0 : (v))

#define ITR2(e0,e1,v) for(const auto [e0, e1] : (v))
#define ITRP2(e0,e1,v) for(auto [e0, e1] : (v))
#define ITRR2(e0,e1,v) for(auto &[e0, e1] : (v))

#define ITR3(e0,e1,e2,v) for(const auto [e0, e1, e2] : (v))
#define ITRP3(e0,e1,e2,v) for(auto [e0, e1, e2] : (v))
#define ITRR3(e0,e1,e2,v) for(auto &[e0, e1, e2] : (v))

#define ITR4(e0,e1,e2,e3,v) for(const auto [e0, e1, e2, e3] : (v))
#define ITRP4(e0,e1,e2,e3,v) for(auto [e0, e1, e2, e3] : (v))
#define ITRR4(e0,e1,e2,e3,v) for(auto &[e0, e1, e2, e3] : (v))

#define ITR5(e0,e1,e2,e3,e4,v) for(const auto [e0, e1, e2, e3, e4] : (v))
#define ITRP5(e0,e1,e2,e3,e4,v) for(auto [e0, e1, e2, e3, e4] : (v))
#define ITRR5(e0,e1,e2,e3,e4,v) for(auto &[e0, e1, e2, e3, e4] : (v))

#define ITR(...) $OVERLOAD6(__VA_ARGS__, ITR5, ITR4, ITR3, ITR2, ITR1)(__VA_ARGS__)
#define ITRP(...) $OVERLOAD6(__VA_ARGS__, ITRP5, ITRP4, ITRP3, ITRP2, ITRP1)(__VA_ARGS__)
#define ITRR(...) $OVERLOAD6(__VA_ARGS__, ITRR5, ITRR4, ITRR3, ITRR2, ITRR1)(__VA_ARGS__)
#line 10 "numeric/extremum_seeker.hpp"

#line 2 "internal/types.hpp"

#line 4 "internal/types.hpp"

namespace uni {

namespace internal {


using size_t = std::int64_t;

using int128_t = __int128_t;
using uint128_t = __uint128_t;


} // namesapce internal

} // namespace uni
#line 13 "numeric/extremum_seeker.hpp"

#line 2 "adaptor/gnu/hash_table.hpp"


#line 5 "adaptor/gnu/hash_table.hpp"
#include <stdexcept>

#include <ext/pb_ds/assoc_container.hpp>


#line 11 "adaptor/gnu/hash_table.hpp"



namespace uni {

namespace gnu {


template<class Base>
struct hash_table : Base {
    using key_type = typename Base::key_type;
    using value_type = typename Base::value_type;
    using mapped_type = typename Base::mapped_type;

    inline bool contains(const key_type& key) const noexcept(NO_EXCEPT) {
        return this->Base::find(key) != this->Base::end();
    }

    template<class K, class T>
    inline decltype(auto) emplace(K&& key, T&& val) noexcept(NO_EXCEPT) {
        return this->Base::insert({ std::forward<K>(key), std::forward<T>(val) });
    }

    mapped_type& at(const key_type& key) {
        auto itr = this->Base::find(key);
        if(itr == this->Base::end()) throw std::out_of_range("hash_table::at()");
        return itr->second;
    };

    const mapped_type& at(const key_type & key) const {
        auto itr = this->Base::find(key);
        if(itr == this->Base::end()) throw std::out_of_range("hash_table::at()");
        return itr->second;
    };
};


template<class Key, class T, class Hash = void>
struct cc_hash_table : hash_table<__gnu_pbds::cc_hash_table<Key, T, Hash>> {
    using hash_table<__gnu_pbds::cc_hash_table<Key, T, Hash>>::hash_table;
};

template<class Key, class T>
struct cc_hash_table<Key, T, void> : hash_table<__gnu_pbds::cc_hash_table<Key, T>> {
    using hash_table<__gnu_pbds::cc_hash_table<Key, T>>::hash_table;
};


template<class Key, class T, class Hash = void>
struct gp_hash_table : hash_table<__gnu_pbds::gp_hash_table<Key, T, Hash>> {
    using hash_table<__gnu_pbds::gp_hash_table<Key, T, Hash>>::hash_table;
};

template<class Key, class T>
struct gp_hash_table<Key, T, void> : hash_table<__gnu_pbds::gp_hash_table<Key, T>> {
    using hash_table<__gnu_pbds::gp_hash_table<Key, T>>::hash_table;
};


} // namespace gnu

} // namespace uni
#line 15 "numeric/extremum_seeker.hpp"

#line 2 "numeric/limits.hpp"


#include <limits>
#line 6 "numeric/limits.hpp"


#line 9 "numeric/limits.hpp"

#line 11 "numeric/limits.hpp"


namespace uni {


template<class T>
struct numeric_limits : std::numeric_limits<T> {
    static constexpr long double FLOAT_EPSILON = 1E-14;

    static constexpr T arithmetic_infinity() noexcept(NO_EXCEPT) {
        return std::numeric_limits<T>::max() / 2 - 1;
    }

    static constexpr T arithmetic_negative_infinity() noexcept(NO_EXCEPT) {
        return std::numeric_limits<T>::lowest() / 2 + 1;
    }

    static constexpr T arithmetic_epsilon() noexcept(NO_EXCEPT) {
        if constexpr(std::is_floating_point_v<T>) {
            return numeric_limits::FLOAT_EPSILON;
        }
        else {
            return 0;
        }
    }
};


constexpr i32 INF32 = numeric_limits<i32>::arithmetic_infinity();
constexpr i64 INF64 = numeric_limits<i64>::arithmetic_infinity();

template<class T>
constexpr T INF = numeric_limits<T>::arithmetic_infinity();

template<class T>
constexpr T EPSILON = numeric_limits<T>::arithmetic_epsilon();


} // namespace uni
#line 17 "numeric/extremum_seeker.hpp"


namespace uni {


template<class Signature>
struct extremum_seeker;


template<class T, std::floating_point Arg>
struct extremum_seeker<T(Arg)> {
    using value_type = T;
    using arg_type = Arg;

  private:
    std::function<T(Arg)> _f;


    template<const internal::size_t ITERATIONS>
    std::pair<arg_type, arg_type> search(arg_type low, arg_type high, const auto comp) const noexcept(NO_EXCEPT) {
        REP(ITERATIONS) {
            const auto p = low + (high - low) / 3;
            const auto q = high - (high - low) / 3;

            if(comp(p, q)) high = q;
            else low = p;
        }

        return { low, high };
    }

  public:
    template<class F>
        requires std::same_as<std::invoke_result_t<F, Arg>, T>
    extremum_seeker(F&& f) noexcept(NO_EXCEPT) : _f(std::forward<F>(f)) {};


    template<const internal::size_t ITERATIONS = 100'000>
    std::pair<arg_type, arg_type> arg_min(
        arg_type low = uni::numeric_limits<arg_type>::arithmetic_negative_infinity(),
        arg_type high = uni::numeric_limits<arg_type>::arithmetic_infinity()
    ) const noexcept(NO_EXCEPT) {
        const auto comp = [&](const arg_type lhs, const arg_type rhs) noexcept(NO_EXCEPT) {
            return this->_f(lhs) < this->_f(rhs);
        };
        return this->search<ITERATIONS>(low, high, comp);
    }

    template<const internal::size_t ITERATIONS = 100'000>
    std::pair<arg_type, arg_type> arg_max(
        arg_type low = uni::numeric_limits<arg_type>::arithmetic_negative_infinity(),
        arg_type high = uni::numeric_limits<arg_type>::arithmetic_infinity()
    ) const noexcept(NO_EXCEPT) {
        const auto comp = [&](const arg_type lhs, const arg_type rhs) noexcept(NO_EXCEPT) {
            return this->_f(lhs) > this->_f(rhs);
        };
        return this->search<ITERATIONS>(low, high, comp);
    }


    template<const internal::size_t ITERATIONS = 100'000>
    auto min(
        const arg_type _low = uni::numeric_limits<arg_type>::arithmetic_negative_infinity(),
        const arg_type _high = uni::numeric_limits<arg_type>::arithmetic_infinity()
    ) const noexcept(NO_EXCEPT) {
        const auto [ low, high ] = this->arg_min<ITERATIONS>(_low, _high);
        auto res = std::min(this->_f(low), this->_f(high));
        FOR(x, low, high) chmin(res, this->_f(x));
        return res;
    }

    template<const internal::size_t ITERATIONS = 100'000>
    auto max(
        const arg_type _low = uni::numeric_limits<arg_type>::arithmetic_negative_infinity(),
        const arg_type _high = uni::numeric_limits<arg_type>::arithmetic_infinity()
    ) const noexcept(NO_EXCEPT) {
        const auto [ low, high ] = this->arg_max<ITERATIONS>(_low, _high);
        auto res = std::max(this->_f(low), this->_f(high));
        FOR(x, low, high) chmax(res, this->_f(x));
        return res;
    }
};


template<class T, std::integral Arg>
struct extremum_seeker<T(Arg)> {
    using value_type = T;
    using arg_type = Arg;

  private:
    std::function<T(Arg)> _f;

    std::vector<arg_type> _fib = { 0, 1 };
    gnu::gp_hash_table<arg_type, value_type> _cache;


    auto _expand(const arg_type size) noexcept(NO_EXCEPT) {
        assert(size >= 0);
        this->_fib.reserve(std::bit_width(to_unsigned(size)));

        if(this->_fib.back() < size) {
            do {
                this->_fib.emplace_back(
                    this->_fib[std::ranges::size(this->_fib) - 1] +
                    this->_fib[std::ranges::size(this->_fib) - 2]
                );
            } while(this->_fib.back() < size);

            return std::ranges::prev(this->_fib.end());
        }

        return std::ranges::lower_bound(this->_fib, size);
    }

    auto _func(const arg_type size) noexcept(NO_EXCEPT) {
        if(this->_cache.contains(size)) return this->_cache[size];
        return this->_cache[size] = this->_f(size);
    }

    auto _search(arg_type low, const arg_type high, const auto comp) noexcept(NO_EXCEPT) {
        if(low == high) return low;

        auto _low = low - 1;
        const auto itr = this->_expand(high - _low + 1);
        auto _high = *itr + _low;
        auto diff = *std::ranges::prev(itr);

        while(true) {
            const auto p = _high - diff;
            const auto q = _low + diff;

            if(p == q) return p;

            if(comp(p, q)) _high = q;
            else _low = p;

            diff = diff - (q - p);
        }
    }

  public:
    template<class F>
        requires std::same_as<std::invoke_result_t<F, Arg>, T>
    extremum_seeker(F&& f, const arg_type init_size = 0) noexcept(NO_EXCEPT)
      : _f(std::forward<F>(f))
    {
        this->_expand(init_size);
    }


    auto arg_min(
        const arg_type low = uni::numeric_limits<arg_type>::arithmetic_negative_infinity(),
        const arg_type high = uni::numeric_limits<arg_type>::arithmetic_infinity()
    ) noexcept(NO_EXCEPT) {
        const auto comp = [&](const arg_type lhs, const arg_type rhs) noexcept(NO_EXCEPT) {
            if(high < rhs) return true;
            return this->_func(lhs) < this->_func(rhs);
        };
        return this->_search(low, high, comp);
    }

    auto arg_max(
        const arg_type low = uni::numeric_limits<arg_type>::arithmetic_negative_infinity(),
        const arg_type high = uni::numeric_limits<arg_type>::arithmetic_infinity()
    ) noexcept(NO_EXCEPT) {
        const auto comp = [&](const arg_type lhs, const arg_type rhs) noexcept(NO_EXCEPT) {
            if(high < rhs) return true;
            return this->_func(lhs) > this->_func(rhs);
        };
        return this->_search(low, high, comp);
    }


    inline auto min(
        const arg_type _low = uni::numeric_limits<arg_type>::arithmetic_negative_infinity(),
        const arg_type high = uni::numeric_limits<arg_type>::arithmetic_infinity()
    ) noexcept(NO_EXCEPT) {
        return this->_func(this->arg_min(_low, high));
    }

    inline auto max(
        const arg_type _low = uni::numeric_limits<arg_type>::arithmetic_negative_infinity(),
        const arg_type high = uni::numeric_limits<arg_type>::arithmetic_infinity()
    ) noexcept(NO_EXCEPT) {
        return this->_func(this->arg_max(_low, high));
    }
};


} // namespace uni