Library
This documentation is automatically generated by online-judge-tools/verification-helper
Golden Section
(src/opt/golden_section.hpp)
- View this file on GitHub
- Last update: 2022-04-06 15:16:02+09:00
- Include:
#include "src/opt/golden_section.hpp"
Depends on
Operation Traits
(src/algebra/system/operation.hpp)
Code
#pragma once
/**
* @file golden_section.hpp
* @brief Golden Section
*/
#include <type_traits>
#include "src/algebra/system/operation.hpp"
namespace workspace {
/**
* @brief Golden section search.
*/
template <class _Iterator, class _Function>
std::enable_if_t<has_binary_minus<_Iterator>::value, _Iterator> golden_section(
_Iterator __first, _Iterator __last, _Function&& __f) {
if (__last - __first < 2) return __first;
decltype(__last - __first) __a{1}, __b{2};
while (__a + __b <= __last - __first) std::swap(__a += __b, __b);
auto __f1 = __f(__last - __b), __f2 = __f(__last - __a);
while (__a != 1) {
std::swap(__a, __b -= __a);
if (__f2 < __f1)
__f1 = __f2, __f2 = __f(__last - __a);
else if ((__last -= __b) - __first < __b)
std::swap(__a, __b -= __a), __f2 = __f(__last - __a);
else
__f2 = __f1, __f1 = __f(__last - __b);
}
return __f1 < __f2 ? __last - __b : __last - __a;
}
} // namespace workspace#line 2 "src/opt/golden_section.hpp"
/**
* @file golden_section.hpp
* @brief Golden Section
*/
#include <type_traits>
#line 2 "src/algebra/system/operation.hpp"
/**
* @file operation.hpp
* @brief Operation Traits
*/
#include <functional>
#line 10 "src/algebra/system/operation.hpp"
#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 12 "src/algebra/system/operation.hpp"
namespace workspace {
// Unary `+`
template <class _Tp>
using require_unary_plus = std::enable_if_t<
std::is_convertible<decltype(+std::declval<const _Tp &>()), _Tp>::value>;
template <class _Tp, class = void> struct has_unary_plus : std::false_type {};
template <class _Tp>
struct has_unary_plus<_Tp, require_unary_plus<_Tp>> : std::true_type {};
// Unary `-`
template <class _Tp>
using require_unary_minus = std::enable_if_t<
std::is_convertible<decltype(-std::declval<const _Tp &>()), _Tp>::value>;
template <class _Tp, class = void> struct has_unary_minus : std::false_type {};
template <class _Tp>
struct has_unary_minus<_Tp, require_unary_minus<_Tp>> : std::true_type {};
// Binary `+`
template <class _Tp1, class _Tp2 = _Tp1>
using require_binary_plus =
std::enable_if_t<std::is_convertible<decltype(std::declval<const _Tp1 &>() +
std::declval<const _Tp2 &>()),
_Tp1>::value>;
template <class _Tp1, class _Tp2 = _Tp1, class = void>
struct has_binary_plus : std::false_type {};
template <class _Tp1, class _Tp2>
struct has_binary_plus<_Tp1, _Tp2, require_binary_plus<_Tp1, _Tp2>>
: std::true_type {};
// Binary `-`
template <class _Tp1, class _Tp2 = _Tp1>
using require_binary_minus =
std::__void_t<decltype(std::declval<const _Tp1 &>() -
std::declval<const _Tp2 &>())>;
template <class _Tp1, class _Tp2 = _Tp1, class = void>
struct has_binary_minus : std::false_type {};
template <class _Tp1, class _Tp2>
struct has_binary_minus<_Tp1, _Tp2, require_binary_minus<_Tp1, _Tp2>>
: std::true_type {};
// Binary `*`
template <class _Tp1, class _Tp2 = _Tp1>
using require_binary_multiplies =
std::enable_if_t<std::is_convertible<decltype(std::declval<const _Tp1 &>() *
std::declval<const _Tp2 &>()),
_Tp1>::value>;
template <class _Tp1, class _Tp2 = _Tp1, class = void>
struct has_binary_multiplies : std::false_type {};
template <class _Tp1, class _Tp2>
struct has_binary_multiplies<_Tp1, _Tp2, require_binary_multiplies<_Tp1, _Tp2>>
: std::true_type {};
// Binary `/`
template <class _Tp1, class _Tp2 = _Tp1>
using require_binary_divides =
std::enable_if_t<std::is_convertible<decltype(std::declval<const _Tp1 &>() /
std::declval<const _Tp2 &>()),
_Tp1>::value>;
template <class _Tp1, class _Tp2 = _Tp1, class = void>
struct has_binary_divides : std::false_type {};
template <class _Tp1, class _Tp2>
struct has_binary_divides<_Tp1, _Tp2, require_binary_divides<_Tp1, _Tp2>>
: std::true_type {};
// Binary `%`
template <class _Tp1, class _Tp2 = _Tp1>
using require_binary_modulus =
std::enable_if_t<std::is_convertible<decltype(std::declval<const _Tp1 &>() %
std::declval<const _Tp2 &>()),
_Tp1>::value>;
template <class _Tp1, class _Tp2 = _Tp1, class = void>
struct has_binary_modulus : std::false_type {};
template <class _Tp1, class _Tp2>
struct has_binary_modulus<_Tp1, _Tp2, require_binary_modulus<_Tp1, _Tp2>>
: std::true_type {};
template <class _Tp1, class _Tp2 = _Tp1, class = void, class = void,
class = void, class = void>
struct has_arithmetic : std::false_type {};
template <class _Tp1, class _Tp2>
struct has_arithmetic<_Tp1, _Tp2, require_binary_plus<_Tp1, _Tp2>,
require_binary_minus<_Tp1, _Tp2>,
require_binary_multiplies<_Tp1, _Tp2>,
require_binary_divides<_Tp1, _Tp2>> : std::true_type {};
template <class _Tp1, class _Tp2 = _Tp1>
using require_arithmetic = std::enable_if_t<has_arithmetic<_Tp1, _Tp2>::value>;
// Binary `<`
template <class _Tp, class = void> struct is_comparable : std::false_type {};
template <class _Tp>
struct is_comparable<_Tp, std::__void_t<decltype(std::declval<const _Tp &>() <
std::declval<const _Tp &>())>>
: std::true_type {};
template <class _Tp, bool _Default = false> struct try_less : std::less<_Tp> {
constexpr bool operator()(const _Tp &__x, const _Tp &__y) noexcept {
if _CXX17_CONSTEXPR (is_comparable<_Tp>::value)
return std::less<_Tp>::operator()(__x, __y);
else
return _Default;
}
};
} // namespace workspace
#line 11 "src/opt/golden_section.hpp"
namespace workspace {
/**
* @brief Golden section search.
*/
template <class _Iterator, class _Function>
std::enable_if_t<has_binary_minus<_Iterator>::value, _Iterator> golden_section(
_Iterator __first, _Iterator __last, _Function&& __f) {
if (__last - __first < 2) return __first;
decltype(__last - __first) __a{1}, __b{2};
while (__a + __b <= __last - __first) std::swap(__a += __b, __b);
auto __f1 = __f(__last - __b), __f2 = __f(__last - __a);
while (__a != 1) {
std::swap(__a, __b -= __a);
if (__f2 < __f1)
__f1 = __f2, __f2 = __f(__last - __a);
else if ((__last -= __b) - __first < __b)
std::swap(__a, __b -= __a), __f2 = __f(__last - __a);
else
__f2 = __f1, __f1 = __f(__last - __b);
}
return __f1 < __f2 ? __last - __b : __last - __a;
}
} // namespace workspace