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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125 | #pragma once
#include <cassert><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <vector><--- Include file: not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <map><--- Include file:
#include <tuple><--- 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 "snippet/iterations.hpp"
#include "internal/dev_env.hpp"
#include "internal/types.hpp"
#include "adaptor/vector.hpp"
#include "data_structure/disjoint_set.hpp"
#include "structure/graph.hpp"
#include "graph/spanning_tree.hpp"
namespace uni {
// TODO: Vector View
template <
std::input_iterator I0, std::input_iterator I1,
std::sentinel_for<I0> S0, std::sentinel_for<I1> S1
>
auto manhattan_mst_candidate_edges(
I0 x_first, S0 x_last, I1 y_first, S1 y_last
) noexcept(NO_EXCEPT) {
using size_type = internal::size_t;
using cost_type = std::common_type_t<std::iter_value_t<I0>, std::iter_value_t<I1>>;
std::vector<cost_type> xs(x_first, x_last), ys(y_first, y_last);
assert(xs.size() == ys.size());
std::vector<size_type> indices(xs.size());
std::iota(ALL(indices), 0);
vector<std::tuple<size_type, size_type, cost_type>> res;
REP(_0, 2) {
REP(_1, 2) {
std::ranges::sort(indices, [&](const auto i, const auto j) { return xs[i] + ys[i] < xs[j] + ys[j]; });
std::map<cost_type,size_type> scan;
ITR(i, indices) {
for(auto itr = scan.lower_bound(-ys[i]); itr!=scan.end(); itr=scan.erase(itr)) {
const auto j = itr->second;
if(xs[i] - xs[j] < ys[i] - ys[j]) break;
res.emplace_back(i, j, std::abs(xs[i] - xs[j]) + std::abs(ys[i] - ys[j]));
}
scan[-ys[i]] = i;
}
std::swap(xs, ys);
}
ITRR(x, xs) x *= -1;<--- Consider using std::transform algorithm instead of a raw loop.
}
std::ranges::sort(res, [&](const auto& p, const auto& q) { return std::get<2>(p) < std::get<2>(q); });
return res;
}
template <
std::input_iterator I0, std::input_iterator I1,
std::sentinel_for<I0> S0, std::sentinel_for<I1> S1
>
auto manhattan_mst_edges(
I0 x_first, S0 x_last, I1 y_first, S1 y_last,
std::common_type_t<std::iter_value_t<I0>, std::iter_value_t<I1>> *const cost_sum = nullptr
) noexcept(NO_EXCEPT) {
using cost_type = std::common_type_t<std::iter_value_t<I0>, std::iter_value_t<I1>>;
using size_type = internal::size_t;
assert(std::ranges::distance(x_first, x_last) == std::ranges::distance(y_first, y_last));
if(cost_sum) *cost_sum = 0;
vector<std::tuple<size_type, size_type, cost_type>> res;
disjoint_set uf(std::ranges::distance(x_first, x_last));
ITR(u, v, w, (manhattan_mst_candidate_edges<I0,I1>(x_first, x_last, y_first, y_last))) {
if(not uf.same(u, v)) {
uf.merge(u, v);
res.emplace_back(u, v, w);
if(cost_sum) *cost_sum += w;
}
}
return res;
}
template<class Graph>
template<
std::input_iterator I0, std::input_iterator I1,
std::sentinel_for<I0> S0, std::sentinel_for<I1> S1
>
typename Graph::cost_type internal::graph_impl::mixin<Graph>::build_manhattan_mst(
I0 x_first, S0 x_last, I1 y_first, S1 y_last
) noexcept(NO_EXCEPT)
{
assert(std::ranges::distance(x_first, x_last) == std::ranges::distance(y_first, y_last));
cost_type res = 0;
const auto edges = manhattan_mst_edges<I0, I1, S0, S1>(x_first, x_last, y_first, y_last);
ITR(u, v, w, edges) {
this->add_edge_bidirectionally(u, v, w);
}
return res;
}
} // namespace uni
|