#pragma once
#include <cassert>
#include <iterator>
#include <vector>
#include <utility>
#include <functional>
#include <valarray>
#include "snippet/iterations.hpp"
#include "internal/dev_env.hpp"
#include "internal/exception.hpp"
namespace uni {
namespace internal {
namespace interval_scanner_impl {
template<class T> using interval = std::pair<T, T>;
template<class T> using intervals = std::vector<std::pair<T, T>>;
template<class T>
struct base {
protected:
std::function<bool(T)> _validate;
public:
base(std::function<bool(T)> validate) : _validate(validate) {}
void scan(T, T, T) {
static_assert(internal::EXCEPTION_ON_TYPE<T>, "not implemented: scan()");
}
void split(const T first, const T last, intervals<T> *intervals) const {
std::valarray<bool> _valid(false, last - first);
for(auto itr=first,index=0; itr!=last; ++itr, ++index) _valid[index] = _validate(itr);
auto can_begin = [&](const T itr) {
const auto index = itr - first;
if(itr == first) return _valid[index];
if(itr == last) return false;
if(not _valid[index-1] and _valid[index]) return true;
return false;
};
auto is_end = [&](const T itr) {
const auto index = itr - first;
if(itr == first) return false;
if(itr == last) return _valid[index-1];
if(_valid[index-1] and not _valid[index]) return true;
return false;
};
{
intervals->clear();
T start = first;
for(auto itr=first; ; ++itr) {
if(can_begin(itr)) start = itr;
if(is_end(itr)) intervals->emplace_back(start, itr);
if(itr == last) break;
}
}
}
void scan_all(const T first, const T last) const {
intervals<T> targets;
this->split(first, last, &targets);
ITR(start, end, targets) this->scan(first, start, end);
}
};
} // namespace interval_scanner_impl
} // namespace internal
template<class T>
struct exclusive_interval_scanner : internal::interval_scanner_impl::base<T> {
private:
std::function<void(T)> _init;
std::function<bool(T)> _can_expand;
std::function<void(T)> _expand, _contract;
std::function<void(T, T)> _apply;
public:
using interval = internal::interval_scanner_impl::interval<T>;
using intervals = internal::interval_scanner_impl::intervals<T>;
exclusive_interval_scanner(
std::function<bool(T)> validate,
std::function<void(T)> init,
std::function<bool(T)> can_expand,
std::function<void(T)> expand,
std::function<void(T)> contract,
std::function<void(T, T)> apply
)
: internal::interval_scanner_impl::base<T>(validate), _init(init), _can_expand(can_expand),
_expand(expand), _contract(contract), _apply(apply)
{}
template<const bool FOLLOWING = true>
void scan(const T start, const T end) const {
T l_itr=start, r_itr=start;
while(l_itr < end) {
if (FOLLOWING and r_itr <= l_itr) {
r_itr = l_itr+1;
_init(l_itr);
}
while(r_itr < end && _can_expand(r_itr)) {
_expand(r_itr++);
}
_apply(l_itr, r_itr);
_contract(l_itr++);
}
};
template<const bool FOLLOWING = true>
void scan_all(const T first, const T last) const {
intervals targets;
this->split(first, last, &targets);
ITR(start, end, targets) this->scan<FOLLOWING>(start, end);
}
};
template<class T>
struct inclusive_interval_scanner : internal::interval_scanner_impl::base<T> {
protected:
std::function<void()> _init;
std::function<bool()> _valid;
std::function<void(T)> _expand, _contract;
std::function<void(T, T)> _apply;
public:
using interval = internal::interval_scanner_impl::interval<T>;
using intervals = internal::interval_scanner_impl::intervals<T>;
inclusive_interval_scanner(
std::function<bool(T)> validate,
std::function<void()> init,
std::function<bool()> valid,
std::function<void(T)> expand,
std::function<void(T)> contract,
std::function<void(T, T)> apply
) : internal::interval_scanner_impl::base<T>(validate), _init(init), _valid(valid), _expand(expand), _contract(contract), _apply(apply) {}
template<const bool INVERSE = false, const bool FOLLOWING = true, const bool CONFIRMATION = true>
void scan(const T start, const T end) const {
T l_itr = start, r_itr = start;
_init();
while(l_itr < end) {
if(FOLLOWING and r_itr < l_itr) {
r_itr = l_itr;
_init();
}
if(r_itr < end and (INVERSE ^ _valid())) {
_expand(r_itr++);
}
else {
_contract(l_itr++);
}
if(!CONFIRMATION or _valid()) _apply(l_itr, r_itr);
}
}
template<const bool INVERSE = false, const bool FOLLOWING = true, const bool CONFIRMATION = true>
void scan_all(const T first, const T last) const {
intervals targets;
this->split(first, last, &targets);
ITR(start, end, targets) this->scan<INVERSE,FOLLOWING,CONFIRMATION>(start, end);
}
};
} // namespace uni
#line 2 "numeric/internal/two_pointer_technique.hpp"
#include <cassert>
#include <iterator>
#include <vector>
#include <utility>
#include <functional>
#include <valarray>
#line 2 "snippet/iterations.hpp"
#include <type_traits>
#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 12 "numeric/internal/two_pointer_technique.hpp"
#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 "internal/exception.hpp"
namespace uni {
namespace internal {
template<class... T> inline constexpr bool EXCEPTION_ON_TYPE = false;
template<auto T> inline constexpr bool EXCEPTION_ON_VALUE = false;
} // namespace internal
} // namespace uni
#line 15 "numeric/internal/two_pointer_technique.hpp"
namespace uni {
namespace internal {
namespace interval_scanner_impl {
template<class T> using interval = std::pair<T, T>;
template<class T> using intervals = std::vector<std::pair<T, T>>;
template<class T>
struct base {
protected:
std::function<bool(T)> _validate;
public:
base(std::function<bool(T)> validate) : _validate(validate) {}
void scan(T, T, T) {
static_assert(internal::EXCEPTION_ON_TYPE<T>, "not implemented: scan()");
}
void split(const T first, const T last, intervals<T> *intervals) const {
std::valarray<bool> _valid(false, last - first);
for(auto itr=first,index=0; itr!=last; ++itr, ++index) _valid[index] = _validate(itr);
auto can_begin = [&](const T itr) {
const auto index = itr - first;
if(itr == first) return _valid[index];
if(itr == last) return false;
if(not _valid[index-1] and _valid[index]) return true;
return false;
};
auto is_end = [&](const T itr) {
const auto index = itr - first;
if(itr == first) return false;
if(itr == last) return _valid[index-1];
if(_valid[index-1] and not _valid[index]) return true;
return false;
};
{
intervals->clear();
T start = first;
for(auto itr=first; ; ++itr) {
if(can_begin(itr)) start = itr;
if(is_end(itr)) intervals->emplace_back(start, itr);
if(itr == last) break;
}
}
}
void scan_all(const T first, const T last) const {
intervals<T> targets;
this->split(first, last, &targets);
ITR(start, end, targets) this->scan(first, start, end);
}
};
} // namespace interval_scanner_impl
} // namespace internal
template<class T>
struct exclusive_interval_scanner : internal::interval_scanner_impl::base<T> {
private:
std::function<void(T)> _init;
std::function<bool(T)> _can_expand;
std::function<void(T)> _expand, _contract;
std::function<void(T, T)> _apply;
public:
using interval = internal::interval_scanner_impl::interval<T>;
using intervals = internal::interval_scanner_impl::intervals<T>;
exclusive_interval_scanner(
std::function<bool(T)> validate,
std::function<void(T)> init,
std::function<bool(T)> can_expand,
std::function<void(T)> expand,
std::function<void(T)> contract,
std::function<void(T, T)> apply
)
: internal::interval_scanner_impl::base<T>(validate), _init(init), _can_expand(can_expand),
_expand(expand), _contract(contract), _apply(apply)
{}
template<const bool FOLLOWING = true>
void scan(const T start, const T end) const {
T l_itr=start, r_itr=start;
while(l_itr < end) {
if (FOLLOWING and r_itr <= l_itr) {
r_itr = l_itr+1;
_init(l_itr);
}
while(r_itr < end && _can_expand(r_itr)) {
_expand(r_itr++);
}
_apply(l_itr, r_itr);
_contract(l_itr++);
}
};
template<const bool FOLLOWING = true>
void scan_all(const T first, const T last) const {
intervals targets;
this->split(first, last, &targets);
ITR(start, end, targets) this->scan<FOLLOWING>(start, end);
}
};
template<class T>
struct inclusive_interval_scanner : internal::interval_scanner_impl::base<T> {
protected:
std::function<void()> _init;
std::function<bool()> _valid;
std::function<void(T)> _expand, _contract;
std::function<void(T, T)> _apply;
public:
using interval = internal::interval_scanner_impl::interval<T>;
using intervals = internal::interval_scanner_impl::intervals<T>;
inclusive_interval_scanner(
std::function<bool(T)> validate,
std::function<void()> init,
std::function<bool()> valid,
std::function<void(T)> expand,
std::function<void(T)> contract,
std::function<void(T, T)> apply
) : internal::interval_scanner_impl::base<T>(validate), _init(init), _valid(valid), _expand(expand), _contract(contract), _apply(apply) {}
template<const bool INVERSE = false, const bool FOLLOWING = true, const bool CONFIRMATION = true>
void scan(const T start, const T end) const {
T l_itr = start, r_itr = start;
_init();
while(l_itr < end) {
if(FOLLOWING and r_itr < l_itr) {
r_itr = l_itr;
_init();
}
if(r_itr < end and (INVERSE ^ _valid())) {
_expand(r_itr++);
}
else {
_contract(l_itr++);
}
if(!CONFIRMATION or _valid()) _apply(l_itr, r_itr);
}
}
template<const bool INVERSE = false, const bool FOLLOWING = true, const bool CONFIRMATION = true>
void scan_all(const T first, const T last) const {
intervals targets;
this->split(first, last, &targets);
ITR(start, end, targets) this->scan<INVERSE,FOLLOWING,CONFIRMATION>(start, end);
}
};
} // namespace uni
numeric/internal/two_pointer_technique.hpp