1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110 | #pragma once
#include <vector><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <numeric>
#include <algorithm><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <iterator><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <type_traits><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <concepts><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <ranges><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <bit><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include "snippet/aliases.hpp"
#include "snippet/iterations.hpp"
#include "internal/dev_env.hpp"
#include "internal/types.hpp"
#include "adaptor/valarray.hpp"
#include "adaptor/vector.hpp"
#include "numeric/bit.hpp"
#include "numeric/hilbert_order.hpp"
#include "numeric/arithmetic.hpp"
namespace uni {
template<class R, class EF, class PF, class EB = EF, class PB = PF>
class interval_plannner {
using size_type = internal::size_t;
public:
EF _expand_front; EB _expand_back;
PF _contract_front; PB _contract_back;
R _evaluate;
using evaluator_result_t = std::invoke_result_t<R>;
interval_plannner(
EF expand_front, EB expand_back,
PF contract_front, PB contract_back,
R evaluate
) noexcept(NO_EXCEPT)
: _expand_front(expand_front), _expand_back(expand_back),
_contract_front(contract_front), _contract_back(contract_back),
_evaluate(evaluate)
{}
interval_plannner(EF expand, PF contract, R evaluate) noexcept(NO_EXCEPT)
: interval_plannner(expand, expand, contract, contract, evaluate)
{}
template<
std::input_iterator QI, std::sentinel_for<QI> QS,
std::output_iterator<evaluator_result_t> RI
>
void scan(const QI query_first, const QS query_last, const RI res_first) noexcept(NO_EXCEPT) {
const auto q = std::ranges::distance(query_first, query_last);
size_type n = 0;
for(auto query=query_first; query!=query_last; ++query) {
chmax(n, std::ranges::max(query->first, query->second));
}
n = std::bit_ceil(uni::to_unsigned(n));
std::vector<i64> orders(q);
{
auto query = query_first;
auto order = orders.begin();
for(; query!=query_last; ++query, ++order) {
*order = hilbert_order<i64>(n, *query);
}
}
std::vector<size_type> indices(q); std::iota(ALL(indices), 0);
std::ranges::sort(
indices,
[&orders](const size_type i, const size_type j) { return orders[i] < orders[j]; }
);
size_type l = 0, r = 0;
ITR(i, indices) {
while(l > query_first[i].first) _expand_front(--l);
while(r < query_first[i].second) _expand_back(r++);
while(l < query_first[i].first) _contract_front(l++);
while(r > query_first[i].second) _contract_back(--r);
res_first[i] = _evaluate();
}
}
template<std::input_iterator QI, std::sentinel_for<QI> QS>
auto scan(const QI query_first, const QS query_last) noexcept(NO_EXCEPT) {
valarray<evaluator_result_t> res(std::ranges::distance(query_first, query_last));
this->scan(query_first, query_last, std::ranges::begin(res));
return res;
}
template<std::ranges::input_range Q>
auto scan(const Q& queries) noexcept(NO_EXCEPT) {
valarray<evaluator_result_t> res(std::ranges::distance(queries));
this->scan(std::ranges::begin(queries), std::ranges::end(queries), std::ranges::begin(res));
return res;
}
};
} // namespace uni
|