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