Debian Codegraph @

include/deal.II/grid/cell_id.h

raw
1 // ------------------------------------------------------------------------
2 //
3 // SPDX-License-Identifier: LGPL-2.1-or-later
4 // Copyright (C) 2013 - 2023 by the deal.II authors
5 //
6 // This file is part of the deal.II library.
7 //
8 // Part of the source code is dual licensed under Apache-2.0 WITH
9 // LLVM-exception OR LGPL-2.1-or-later. Detailed license information
10 // governing the source code and code contributions can be found in
11 // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
12 //
13 // ------------------------------------------------------------------------
14
15 #ifndef dealii_cell_id_h
16 #define dealii_cell_id_h
17
18 #include <deal.II/base/config.h>
19
20 #include <deal.II/base/array_view.h>
21 #include <deal.II/base/exceptions.h>
22
23 #include <array>
24 #include <cstdint>
25 #include <iostream>
26 #include <vector>
27
28 #ifdef DEAL_II_WITH_P4EST
29 # include <deal.II/distributed/p4est_wrappers.h>
30 #endif
31
32 DEAL_II_NAMESPACE_OPEN
33
34 // Forward declarations
35 #ifndef DOXYGEN
36 template <int dim, int spacedim>
37 DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
38 class Triangulation;
39 #endif
40
41 /**
42 * A class to represent a unique ID for a cell in a Triangulation. It is
43 * returned by `cell->id()` (i.e., CellAccessor::id()) where
44 * `cell` is assumed to be a cell iterator.
45 *
46 * This class stores the index of the coarse cell from which a cell is
47 * descendant (or, more specifically, the
48 * entry on
49 * @ref GlossCoarseCellId "coarse cell IDs"),
50 * together with information on how to reach the cell from that coarse cell
51 * (i.e., which child index to take on each level of the triangulation when
52 * moving from one cell to its children). The important point about this
53 * class is that an object of
54 * the current class uniquely identifies a cell in triangulation, and it even
55 * does so in the context of objects of type
56 * parallel::distributed::Triangulation where the local portion of a mesh may
57 * not store all cells. For example, the CellId computed for a ghost cell on
58 * one processor will be exactly the same as the CellId computed for the very
59 * same cell on the processor that actually owns the cell, although the level
60 * and index of the iterators pointing to that cell <i>within the
61 * triangulation stored on each of the processors</i> may (and in general
62 * will) be different. In other words, CellId provides the tool with which it
63 * is possible to globally and uniquely identify cells in a parallel
64 * triangulation, and consequently makes it possible to exchange, between
65 * processors, data tied to individual cells.
66 *
67 * @note How this data is internally represented is not of importance (and not
68 * exposed on purpose).
69 */
70 class CellId
71 {
72 public:
73 /**
74 * A type that is used to encode the CellId data in a compact and fast way
75 * (e.g. for MPI transfer to other processes). Note that it limits the
76 * number of children that can be transferred to 20 in 3d and 30 in 2d
77 * (using 2 times 32 bit for storage), a limitation that is identical to
78 * the one used by p4est.
79 */
80 using binary_type = std::array<unsigned int, 4>;
81
82 /**
83 * Construct a CellId object with a given @p coarse_cell_id and vector of
84 * child indices. @p child_indices is
85 * interpreted identical to the member variable with the same name, namely
86 * each entry denotes which child to pick from one refinement level to the
87 * next, starting with the coarse cell, until we get to the cell represented
88 * by the current object. Therefore, each entry should be a number between 0
89 * and the number of children of a cell in the current space dimension (i.e.,
90 * GeometryInfo<dim>::max_children_per_cell).
91 */
92 CellId(const types::coarse_cell_id coarse_cell_id,
93 const std::vector<std::uint8_t> &child_indices);
94
95 /**
96 * Construct a CellId object with a given @p coarse_cell_id and array of
97 * child indices provided in @p child_indices. @p child_indices is
98 * interpreted identical to the member variable with the same name, namely
99 * each entry denotes which child to pick from one refinement level to the
100 * next, starting with the coarse cell, until we get to the cell represented
101 * by the current object. Therefore, each entry should be a number between 0
102 * and the number of children of a cell in the current space dimension (i.e.,
103 * GeometryInfo<dim>::max_children_per_cell). The array
104 * @p child_indices must have at least @p n_child_indices valid entries.
105 */
106 CellId(const types::coarse_cell_id coarse_cell_id,
107 const unsigned int n_child_indices,
108 const std::uint8_t *child_indices);
109
110 /**
111 * Construct a CellId object with a given binary representation that was
112 * previously constructed by CellId::to_binary.
113 */
114 CellId(const binary_type &binary_representation);
115
116 /**
117 * Create a CellId from a string with the same format that is produced by
118 * to_string().
119 */
120 explicit CellId(const std::string &string_representation);
121
122 /**
123 * Construct an invalid CellId.
124 */
125 CellId();
126
127 /**
128 * Return a human-readable string representation of this CellId.
129 *
130 * The string returned by this function consists of only ASCII characters
131 * and will look, for example, like this: `"0_3:006"`. It *can* be
132 * interpreted by humans as saying "This cell originates from the zeroth
133 * coarse mesh cell, lives on refinement level 3, and the path from the
134 * coarse mesh cell to its children and grand children is given by 006".
135 * But it is not *meant* to be interpreted in any meaningful way: It's just
136 * a way of representing the internal state of the current object using
137 * only ASCII characters in the printable range.
138 */
139 std::string
140 to_string() const;
141
142 /**
143 * Return a compact and fast binary representation of this CellId.
144 */
145 template <int dim>
146 binary_type
147 to_binary() const;
148
149 /**
150 * Compare two CellId objects for equality.
151 */
152 bool
153 operator==(const CellId &other) const;
154
155 /**
156 * Compare two CellIds for inequality.
157 */
158 bool
159 operator!=(const CellId &other) const;
160
161 /**
162 * Compare two CellIds with regard to an ordering. The details of this
163 * ordering are unspecified except that the operation provides a
164 * total ordering among all cells.
165 */
166 bool
167 operator<(const CellId &other) const;
168
169 /**
170 * Determine if this cell id is the direct parent of the input cell id.
171 */
172 bool
173 is_parent_of(const CellId &other) const;
174
175 /**
176 * Determine if this cell id is the ancestor of the input cell id.
177 */
178 bool
179 is_ancestor_of(const CellId &other) const;
180
181 /**
182 * Read or write the data of this object to or from a stream for the
183 * purpose of serialization using the [BOOST serialization
184 * library](https://www.boost.org/doc/libs/1_74_0/libs/serialization/doc/index.html).
185 */
186 template <class Archive>
187 void
188 serialize(Archive &ar, const unsigned int version);
189
190 /**
191 * Return the id of the coarse cell.
192 */
193 types::coarse_cell_id
194 get_coarse_cell_id() const;
195
196 /**
197 * Return a read-only container of integers that denotes which child to pick
198 * from one refinement level to the next, starting with the coarse cell, until
199 * we get to the cell represented by the current object.
200 *
201 * The number of elements in this container corresponds to (level-1) of the
202 * current cell.
203 */
204 ArrayView<const std::uint8_t>
205 get_child_indices() const;
206
207 private:
208 /**
209 * The number of the coarse cell within whose tree the cell
210 * represented by the current object is located.
211 */
212 types::coarse_cell_id coarse_cell_id;
213
214 /**
215 * The number of child indices stored in the child_indices array. This is
216 * equivalent to (level-1) of the current cell.
217 */
218 unsigned int n_child_indices;
219
220 /**
221 * An array of integers that denotes which child to pick from one
222 * refinement level to the next, starting with the coarse cell,
223 * until we get to the cell represented by the current object.
224 * Only the first n_child_indices entries are used, but we use a statically
225 * allocated array instead of a vector of size n_child_indices to speed up
226 * creation of this object. If the given dimensions ever become a limitation
227 * the array can be extended.
228 */
229 #ifdef DEAL_II_WITH_P4EST
230 std::array<std::uint8_t, internal::p4est::functions<2>::max_level>
231 child_indices;
232 #else
233 std::array<std::uint8_t, 30> child_indices;
234 #endif
235
236 friend std::istream &
237 operator>>(std::istream &is, CellId &cid);
238 friend std::ostream &
239 operator<<(std::ostream &os, const CellId &cid);
240 };
241
242
243
244 /**
245 * Write a CellId object into a stream.
246 */
247 inline std::ostream &
248 operator<<(std::ostream &os, const CellId &cid)
249 {
250 os << cid.coarse_cell_id << '_' << cid.n_child_indices << ':';
251 for (unsigned int i = 0; i < cid.n_child_indices; ++i)
252 // write the child indices. because they are between 0 and 2^dim-1, they all
253 // just have one digit, so we could write them as one character
254 // objects. it's probably clearer to write them as one-digit characters
255 // starting at '0'
256 os << static_cast<unsigned char>('0' + cid.child_indices[i]);
257 return os;
258 }
259
260
261
262 /**
263 * Serialization function
264 */
265 template <class Archive>
266 void
267 CellId::serialize(Archive &ar, const unsigned int /*version*/)
268 {
269 ar &coarse_cell_id;
270 ar &n_child_indices;
271 ar &child_indices;
272 }
273
274 /**
275 * Read a CellId object from a stream.
276 */
277 inline std::istream &
278 operator>>(std::istream &is, CellId &cid)
279 {
280 unsigned int cellid;
281 is >> cellid;
282 if (is.eof())
283 return is;
284
285 cid.coarse_cell_id = cellid;
286 char dummy;
287 is >> dummy;
288 Assert(dummy == '_', ExcMessage("invalid CellId"));
289 is >> cid.n_child_indices;
290 is >> dummy;
291 Assert(dummy == ':', ExcMessage("invalid CellId"));
292
293 unsigned char value;
294 for (unsigned int i = 0; i < cid.n_child_indices; ++i)
295 {
296 // read the one-digit child index (as an integer number) and
297 // convert it back into unsigned integer type
298 is >> value;
299 cid.child_indices[i] = value - '0';
300 }
301 return is;
302 }
303
304
305
306 inline bool
307 CellId::operator==(const CellId &other) const
308 {
309 if (this->coarse_cell_id != other.coarse_cell_id)
310 return false;
311 if (n_child_indices != other.n_child_indices)
312 return false;
313
314 for (unsigned int i = 0; i < n_child_indices; ++i)
315 if (child_indices[i] != other.child_indices[i])
316 return false;
317
318 return true;
319 }
320
321
322
323 inline bool
324 CellId::operator!=(const CellId &other) const
325 {
326 return !(*this == other);
327 }
328
329
330
331 inline bool
332 CellId::operator<(const CellId &other) const
333 {
334 if (this->coarse_cell_id != other.coarse_cell_id)
335 return this->coarse_cell_id < other.coarse_cell_id;
336
337 unsigned int idx = 0;
338 while (idx < n_child_indices)
339 {
340 if (idx >= other.n_child_indices)
341 return false;
342
343 if (child_indices[idx] != other.child_indices[idx])
344 return child_indices[idx] < other.child_indices[idx];
345
346 ++idx;
347 }
348
349 if (n_child_indices == other.n_child_indices)
350 return false;
351 return true; // other.id is longer
352 }
353
354
355
356 inline bool
357 CellId::is_parent_of(const CellId &other) const
358 {
359 if (this->coarse_cell_id != other.coarse_cell_id)
360 return false;
361
362 if (n_child_indices + 1 != other.n_child_indices)
363 return false;
364
365 for (unsigned int idx = 0; idx < n_child_indices; ++idx)
366 if (child_indices[idx] != other.child_indices[idx])
367 return false;
368
369 return true; // other.id is longer
370 }
371
372
373
374 inline bool
375 CellId::is_ancestor_of(const CellId &other) const
376 {
377 if (this->coarse_cell_id != other.coarse_cell_id)
378 return false;
379
380 if (n_child_indices >= other.n_child_indices)
381 return false;
382
383 for (unsigned int idx = 0; idx < n_child_indices; ++idx)
384 if (child_indices[idx] != other.child_indices[idx])
385 return false;
386
387 return true; // other.id is longer
388 }
389
390
391
392 inline types::coarse_cell_id
393 CellId::get_coarse_cell_id() const
394 {
395 return coarse_cell_id;
396 }
397
398
399
400 inline ArrayView<const std::uint8_t>
401 CellId::get_child_indices() const
402 {
403 return {child_indices.data(), n_child_indices};
404 }
405
406
407 DEAL_II_NAMESPACE_CLOSE
408
409 #endif