Line data Source code
1 : #pragma once
2 :
3 : #include "Vector.h"
4 :
5 : #include <absl/container/flat_hash_map.h>
6 : #include <absl/hash/hash.h>
7 : #include <experimental/mdspan>
8 : #include <fmt/ostream.h>
9 : #include <libassert/assert.hpp>
10 :
11 : #include <array>
12 : #include <iosfwd>
13 : #include <limits>
14 : #include <vector>
15 :
16 : namespace stdex = std::experimental;
17 :
18 : template <typename T> class Grid2d;
19 :
20 : template <typename T> class Grid2dSpan {
21 : public:
22 : static constexpr size_t numDimensions = 2u;
23 : using Span = stdex::mdspan<T, stdex::dextents<int, numDimensions>, stdex::layout_stride>;
24 : using ElementType = Span::element_type;
25 : using ExtentsType = Span::extents_type;
26 : using IndexType = Span::index_type;
27 : using Coord = Vec2<IndexType>;
28 : using SizeType = Span::size_type;
29 : using MappingType = Span::mapping_type;
30 :
31 219 : Grid2dSpan() = default;
32 : Grid2dSpan(ElementType *p, auto const xSize, auto const ySize)
33 258 : : _span(p,
34 258 : MappingType{ExtentsType{integerCast<IndexType>(xSize), integerCast<IndexType>(ySize)},
35 258 : std::array<IndexType, 2u>{1, integerCast<IndexType>(xSize)}}) {}
36 :
37 : Grid2dSpan(ElementType *p, auto const xSize, auto const ySize, auto const xStride,
38 : auto const yStride)
39 7078 : : _span(p,
40 7078 : MappingType{ExtentsType{integerCast<IndexType>(xSize), integerCast<IndexType>(ySize)},
41 7078 : std::array<IndexType, 2u>{integerCast<IndexType>(xStride),
42 7078 : integerCast<IndexType>(yStride)}}) {}
43 :
44 : Grid2dSpan(ElementType *p, auto const xSize, auto const ySize, auto const yStride)
45 1060 : : _span(p,
46 1060 : MappingType{ExtentsType{integerCast<IndexType>(xSize), integerCast<IndexType>(ySize)},
47 1060 : std::array<IndexType, 2u>{1, integerCast<IndexType>(yStride)}}) {}
48 :
49 4870 : Grid2dSpan(ElementType *p, MappingType const &mapping) : _span(p, mapping) {}
50 :
51 604 : template <typename U> Grid2dSpan(Grid2dSpan<U> const &other) : _span(other.span()) {}
52 :
53 : [[nodiscard]] ElementType &operator[](std::integral auto const x,
54 49467839 : std::integral auto const y) const {
55 49467839 : return _span[x, y];
56 49467839 : }
57 20368338 : template <std::integral U> [[nodiscard]] ElementType &operator[](Vec2<U> const &x) const {
58 20368338 : return _span[x.x(), x.y()];
59 20368338 : }
60 :
61 62368255 : [[nodiscard]] IndexType xSize() const { return _span.extent(0); }
62 2782211 : [[nodiscard]] IndexType ySize() const { return _span.extent(1); }
63 2 : [[nodiscard]] Vec2<IndexType> size() const { return {_span.extent(0), _span.extent(1)}; }
64 :
65 3434 : [[nodiscard]] Grid2dSpan column(IndexType const x) const {
66 3434 : return {&_span[x, 0], 1, ySize(), _span.mapping().strides()[0], _span.mapping().strides()[1]};
67 3434 : }
68 3142 : [[nodiscard]] Grid2dSpan line(IndexType const y) const {
69 3142 : return {&_span[0, y], xSize(), 1, 1, _span.mapping().strides()[1]};
70 3142 : }
71 :
72 1085 : template <class F> void forEach(F f) const {
73 214423 : for (int y = 0; y < ySize(); ++y)
74 48758416 : for (int x = 0; x < xSize(); ++x)
75 48545078 : f(_span[x, y]);
76 1085 : }
77 :
78 : void fill(ElementType const &e) const;
79 :
80 : [[nodiscard]] Coord find(ElementType const &e) const;
81 : [[nodiscard]] std::vector<Coord> findAll(ElementType const &e) const;
82 :
83 : [[nodiscard]] auto map(auto &&mapFunc) const -> Grid2d<decltype(mapFunc(' '))>;
84 : [[nodiscard]] size_t count(ElementType const &e) const;
85 : [[nodiscard]] size_t count_if(auto predicate) const;
86 :
87 : [[nodiscard]] ElementType max() const;
88 : [[nodiscard]] ElementType sum() const;
89 :
90 10344 : [[nodiscard]] Span const &span() const { return _span; }
91 600 : [[nodiscard]] Grid2dSpan subgrid(Coord const &begin, Coord const &end) const {
92 600 : return {&((*this)[begin]), end.x() - begin.x(), end.y() - begin.y(), _span.stride(1u)};
93 600 : }
94 :
95 : [[nodiscard]] Grid2dSpan flipX() const {
96 : return {&(*this)[xSize() - 1, 0], xSize(), ySize(), -_span.stride(0), _span.stride(1)};
97 : }
98 :
99 2 : [[nodiscard]] Grid2dSpan flipY() const {
100 2 : return {&(*this)[0, ySize() - 1], xSize(), ySize(), _span.stride(0), -_span.stride(1)};
101 2 : }
102 :
103 : private:
104 : Span _span;
105 : };
106 :
107 : template <typename T> class Grid2d {
108 : public:
109 : using SpanType = Grid2dSpan<T>;
110 : using ElementType = SpanType::ElementType;
111 : using IndexType = SpanType::IndexType;
112 : using Coord = SpanType::Coord;
113 : using SizeType = SpanType::SizeType;
114 :
115 8 : Grid2d() = default;
116 :
117 : Grid2d(std::integral auto const xSize, std::integral auto const ySize)
118 223 : : _data(xSize * ySize), _span(_data.data(), xSize, ySize) {}
119 :
120 : Grid2d(std::integral auto const xSize, std::integral auto const ySize, ElementType const &init)
121 35 : : _data(integerCast<size_t>(xSize * ySize), init), _span(_data.data(), xSize, ySize) {}
122 :
123 : Grid2d(std::integral auto const xSize, std::integral auto const ySize, ElementType const &init,
124 : std::integral auto const numGhostLayers)
125 460 : : _data(integerCast<size_t>((xSize + 2 * numGhostLayers) * (ySize + 2 * numGhostLayers)),
126 460 : init),
127 460 : _span(&_data[numGhostLayers * (xSize + 2 * numGhostLayers) + numGhostLayers], xSize, ySize,
128 460 : xSize + 2 * numGhostLayers) {}
129 :
130 : template <std::integral U> Grid2d(Vec2<U> const &size) : Grid2d(size.x(), size.y()) {}
131 :
132 : template <std::integral U>
133 : Grid2d(Vec2<U> const &size, ElementType const &init) : Grid2d(size.x(), size.y(), init) {}
134 :
135 : template <std::integral U>
136 : Grid2d(Vec2<U> const &size, ElementType const &init, auto const numGhostLayers)
137 2 : : Grid2d(size.x(), size.y(), init, numGhostLayers) {}
138 :
139 : Grid2d(Grid2d const &other)
140 4870 : : _data(other._data),
141 4870 : _span(_data.data() + other.pointerOffset(), other.span().span().mapping()) {} // NOLINT
142 :
143 74 : Grid2d(Grid2d &&other) noexcept : _data(std::move(other._data)), _span(std::move(other._span)) {
144 74 : other._span = SpanType{};
145 74 : }
146 :
147 : Grid2d &operator=(Grid2d const &other) {
148 : _data = other._data;
149 : _span = SpanType(_data.data() + other.pointerOffset(), other.span().span().mapping());
150 : return *this;
151 : }
152 :
153 137 : Grid2d &operator=(Grid2d &&other) noexcept {
154 137 : _data = std::move(other._data);
155 137 : _span = std::move(other._span);
156 137 : other._span = SpanType{};
157 137 : return *this;
158 137 : }
159 :
160 5670 : ~Grid2d() = default;
161 :
162 604 : operator Grid2dSpan<T const>() const { return _span; }
163 580 : operator Grid2dSpan<T>() { return _span; }
164 :
165 6080706 : [[nodiscard]] ElementType &operator[](std::integral auto const x, std::integral auto const y) {
166 6080706 : return _span[x, y];
167 6080706 : }
168 : [[nodiscard]] ElementType const &operator[](std::integral auto const x,
169 609047 : std::integral auto const y) const {
170 609047 : return _span[x, y];
171 609047 : }
172 :
173 20200347 : template <std::integral U> [[nodiscard]] ElementType &operator[](Vec2<U> const &x) {
174 20200347 : return _span[x.x(), x.y()];
175 20200347 : }
176 6278047 : template <std::integral U> [[nodiscard]] ElementType const &operator[](Vec2<U> const &x) const {
177 6278047 : return _span[x.x(), x.y()];
178 6278047 : }
179 :
180 6874413 : [[nodiscard]] IndexType xSize() const { return _span.xSize(); }
181 97983 : [[nodiscard]] IndexType ySize() const { return _span.ySize(); }
182 2 : [[nodiscard]] Vec2<IndexType> size() const { return _span.size(); }
183 :
184 2913 : [[nodiscard]] bool inBounds(Coord const &x) const {
185 2913 : return x.x() >= 0 && x.y() >= 0 && x.x() < xSize() && x.y() < ySize();
186 2913 : }
187 :
188 : [[nodiscard]] SpanType column(IndexType const x) const { return _span.column(x); }
189 : [[nodiscard]] SpanType line(IndexType const y) const { return _span.line(y); }
190 :
191 35 : void fill(ElementType const &e) { return _span.fill(e); }
192 :
193 12 : [[nodiscard]] Coord find(ElementType const &e) const { return _span.find(e); }
194 4 : [[nodiscard]] std::vector<Coord> findAll(ElementType const &e) const { return _span.findAll(e); }
195 :
196 9894 : [[nodiscard]] SpanType const &span() const { return _span; }
197 :
198 4 : [[nodiscard]] auto map(auto &&mapFunc) const -> Grid2d<decltype(mapFunc(' '))> {
199 4 : return _span.map(std::forward<decltype(mapFunc)>(mapFunc));
200 4 : }
201 7 : [[nodiscard]] size_t count(ElementType const &e) const { return _span.count(e); }
202 441 : [[nodiscard]] size_t count_if(auto predicate) const { return _span.count_if(predicate); }
203 1 : [[nodiscard]] ElementType max() const { return _span.max(); }
204 1 : [[nodiscard]] ElementType sum() const { return _span.sum(); }
205 :
206 600 : [[nodiscard]] Grid2dSpan<T> subgrid(Coord const &begin, Coord const &end) const {
207 600 : return _span.subgrid(begin, end);
208 600 : }
209 :
210 2 : [[nodiscard]] Grid2dSpan<T> flipY() const { return _span.flipY(); }
211 : [[nodiscard]] Grid2dSpan<T> flipX() const { return _span.flipX(); }
212 :
213 : private:
214 4870 : [[nodiscard]] size_t pointerOffset() const { return _span.span().data_handle() - _data.data(); }
215 : std::vector<T> _data;
216 : SpanType _span;
217 : };
218 :
219 788 : template <typename T> bool operator==(Grid2dSpan<T> const &lhs, Grid2dSpan<T> const &rhs) {
220 788 : if (lhs.xSize() != rhs.xSize() || lhs.ySize() != rhs.ySize())
221 0 : return false;
222 :
223 788 : using IndexType = Grid2dSpan<T>::IndexType;
224 6720 : for (IndexType y = 0; y < lhs.ySize(); ++y)
225 15430 : for (IndexType x = 0; x < lhs.xSize(); ++x)
226 9498 : if (lhs[x, y] != rhs[x, y])
227 0 : return false;
228 :
229 788 : return true;
230 788 : }
231 :
232 : template <typename T> bool operator==(Grid2d<T> const &lhs, Grid2d<T> const &rhs) {
233 : return lhs.span() == rhs.span();
234 : }
235 :
236 2512 : template <typename T> bool operator<(Grid2dSpan<T> const &lhs, Grid2dSpan<T> const &rhs) {
237 2512 : if (lhs.xSize() != rhs.xSize() || lhs.ySize() != rhs.ySize())
238 0 : return false;
239 :
240 2512 : using IndexType = Grid2dSpan<T>::IndexType;
241 41764 : for (IndexType y = 0; y < lhs.ySize(); ++y)
242 4102422 : for (IndexType x = 0; x < lhs.xSize(); ++x) {
243 4063170 : if (lhs[x, y] < rhs[x, y])
244 1170 : return true;
245 4062000 : if (lhs[x, y] > rhs[x, y])
246 1340 : return false;
247 4062000 : }
248 2 : return false;
249 2512 : }
250 :
251 2512 : template <typename T> bool operator<(Grid2d<T> const &lhs, Grid2d<T> const &rhs) {
252 2512 : return lhs.span() < rhs.span();
253 2512 : }
254 :
255 5000 : template <typename H, typename T> H AbslHashValue(H h, Grid2dSpan<T> const &s) {
256 5000 : H state = H::combine(std::move(h), s.xSize(), s.ySize());
257 5000 : using IndexType = Grid2dSpan<T>::IndexType;
258 38732 : for (IndexType y = 0; y < s.ySize(); ++y)
259 96196 : for (IndexType x = 0; x < s.xSize(); ++x)
260 62464 : state = H::combine(std::move(state), s[x, y]);
261 5000 : return state;
262 5000 : }
263 :
264 : template <typename H, typename T> H AbslHashValue(H h, Grid2d<T> const &s) {
265 : return AbslHashValue(std::move(h), s.span());
266 : }
267 :
268 35 : template <typename T> void Grid2dSpan<T>::fill(ElementType const &e) const {
269 176435 : forEach([&e](ElementType &ee) { ee = e; });
270 35 : }
271 :
272 12 : template <typename T> auto Grid2dSpan<T>::find(ElementType const &e) const -> Coord {
273 774 : for (Coord c{0, 0}; c[1] < ySize(); ++c[1])
274 103670 : for (c[0] = 0; c[0] < xSize(); ++c[0])
275 102908 : if ((*this)[c] == e)
276 12 : return c;
277 :
278 0 : return {xSize(), ySize()};
279 12 : }
280 :
281 : template <typename T>
282 8 : auto Grid2dSpan<T>::findAll(ElementType const &e) const -> std::vector<Coord> {
283 8 : std::vector<Coord> result;
284 688 : for (Coord c{0, 0}; c[1] < ySize(); ++c[1])
285 72380 : for (c[0] = 0; c[0] < xSize(); ++c[0])
286 71700 : if ((*this)[c] == e)
287 6432 : result.push_back(c);
288 :
289 8 : return result;
290 8 : }
291 :
292 : template <typename T>
293 4 : auto Grid2dSpan<T>::map(auto &&mapFunc) const -> Grid2d<decltype(mapFunc(' '))> {
294 4 : Grid2d<decltype(mapFunc(' '))> result(xSize(), ySize());
295 484 : for (int y = 0; y < ySize(); ++y)
296 59844 : for (int x = 0; x < xSize(); ++x)
297 59364 : result[x, y] = mapFunc(_span[x, y]);
298 4 : return result;
299 4 : }
300 :
301 448 : template <typename T> size_t Grid2dSpan<T>::count_if(auto predicate) const {
302 448 : size_t ctr = 0;
303 6363635 : forEach([&](ElementType const &e) {
304 6363635 : if (predicate(e))
305 2398237 : ++ctr;
306 6363635 : });
307 448 : return ctr;
308 448 : }
309 :
310 7 : template <typename T> size_t Grid2dSpan<T>::count(ElementType const &e) const {
311 1049660 : return count_if([&e](ElementType const &ee) { return ee == e; });
312 7 : }
313 :
314 1 : template <typename T> auto Grid2dSpan<T>::max() const -> ElementType {
315 1 : ElementType max = _span[0, 0];
316 9801 : forEach([&max](ElementType const &e) {
317 9801 : if (e > max)
318 9 : max = e;
319 9801 : });
320 :
321 1 : return max;
322 1 : }
323 :
324 1 : template <typename T> auto Grid2dSpan<T>::sum() const -> ElementType {
325 1 : ElementType sum = ElementType();
326 1000000 : forEach([&sum](ElementType const &e) { sum += e; });
327 :
328 1 : return sum;
329 1 : }
330 :
331 : std::ostream &operator<<(std::ostream &oss, Grid2dSpan<char> const &span);
332 0 : inline std::ostream &operator<<(std::ostream &oss, Grid2d<char> const &grid) {
333 0 : return oss << grid.span();
334 0 : }
335 :
336 : template <> struct fmt::formatter<Grid2dSpan<char>> : ostream_formatter {};
337 : template <> struct fmt::formatter<Grid2d<char>> : ostream_formatter {};
338 :
339 : template <typename T> class SparseGrid2d {
340 : public:
341 : using ElementType = T;
342 : using IndexType = int;
343 : using Coord = Vec2<IndexType>;
344 : using SizeType = size_t;
345 :
346 2 : SparseGrid2d(ElementType const &defaultValue) : _defaultValue(defaultValue) {}
347 :
348 : [[nodiscard]] ElementType operator[](auto const x, auto const y) const { (*this)[{x, y}]; }
349 11596 : [[nodiscard]] ElementType operator[](Coord const &x) const {
350 11596 : auto it = _map.find(x);
351 11596 : return it == _map.end() ? _defaultValue : it->second;
352 11596 : }
353 :
354 3316 : void set(Coord const &x, ElementType const &value) { _map[x] = value; }
355 : void set(int const x, int const y, ElementType const &value) { _map[{x, y}] = value; }
356 :
357 2 : [[nodiscard]] std::pair<Coord, Coord> nonDefaultCoordsInterval() const {
358 2 : Coord min(std::numeric_limits<IndexType>::max());
359 2 : Coord max(std::numeric_limits<IndexType>::min());
360 3316 : for (auto const &[coord, val] : _map) {
361 3316 : min = elementwiseMin(min, coord);
362 3316 : max = elementwiseMax(max, coord);
363 3316 : }
364 :
365 2 : return {min, max};
366 2 : }
367 :
368 2 : [[nodiscard]] std::tuple<Grid2d<T>, Coord> toGrid2d() const {
369 2 : auto const [min, max] = nonDefaultCoordsInterval();
370 2 : Coord const size = max - min + 1;
371 :
372 2 : Grid2d<T> grid(size.x(), size.y(), _defaultValue);
373 2 : for (auto const &[coord, val] : _map)
374 3316 : grid[coord - min] = val;
375 2 : return {std::move(grid), min};
376 2 : }
377 :
378 : private:
379 : ElementType _defaultValue;
380 : absl::flat_hash_map<Coord, ElementType> _map;
381 : };
382 :
383 : std::ostream &operator<<(std::ostream &oss, SparseGrid2d<char> const &span);
384 :
385 : template <> struct fmt::formatter<SparseGrid2d<char>> : ostream_formatter {};
|
