SegmentId.hpp
Go to the documentation of this file.
1 // Distributed under the MIT License.
2 // See LICENSE.txt for details.
3 
4 /// \file
5 /// Defines class SegmentId.
6 
7 #pragma once
8 
9 #include <cstddef>
10 #include <iosfwd>
11 #include <limits>
12 
13 #include "Domain/Side.hpp"
14 #include "ErrorHandling/Assert.hpp"
16 
17 namespace PUP {
18 class er;
19 } // namespace PUP
20 
21 /*!
22  * \ingroup ComputationalDomainGroup
23  * \brief A SegmentId labels a segment of the interval [-1,1] and is used to
24  * identify the bounds of an Element in a Block in each dimension.
25  *
26  * In \f$d\f$ dimensions, \f$d\f$ SegmentId%s are used to identify an Element.
27  * In each dimension, a segment spans the subinterval \f$[-1 + 2 \frac{i}{N}, -1
28  * + 2 \frac{i+1}{N}]\f$ of the logical coordinates of a Block, where \f$i \f$=
29  * `index` and \f$N = 2^L\f$ where \f$L\f$ = `refinement_level`.
30  *
31  * \image html SegmentId.svg "SegmentIds"
32  *
33  * In the figure, The `index` of segments increase from the `lower side` to the
34  * `upper side` in each dimension of a Block, while the `refinement level`
35  * increases as the segments are subdivided. For example, let the segment
36  * labeled `self` be on `refinement level` \f$L\f$, with `index` \f$i\f$. Its
37  * `parent` segment is on `refinement level` \f$L-1\f$ with `index`
38  * \f$\frac{i-1}{2}\f$. The `children` of `self` are on `refinement level`
39  * \f$L+1\f$, and have `index` \f$2i\f$ and \f$2i+1\f$ for the lower and upper
40  * child respectively. Also labeled on the figure are the `sibling` and
41  * `abutting nibling` (child of sibling) of `self`. These relationships between
42  * segments are important for h-refinement, since in each dimension an Element
43  * can be flagged to split into its two `children` segments, or join with its
44  * `sibling` segment to form its `parent` segment. As refinement levels of
45  * neighboring elements are kept within one, in the direction of its `sibling`,
46  * a segment can only abut its `sibling` or `abutting nibling`, while on the
47  * opposite side, it can abut a segment on its level, the next-lower, or the
48  * next-higher level.
49  */
50 class SegmentId {
51  public:
52  /// Default constructor needed for Charm++ serialization.
53  constexpr SegmentId() noexcept = default;
54  constexpr SegmentId(const SegmentId& segment_id) noexcept = default;
55  constexpr SegmentId(SegmentId&& segment_id) noexcept = default;
56  ~SegmentId() noexcept = default;
57  SegmentId& operator=(const SegmentId& segment_id) noexcept = default;
58  SegmentId& operator=(SegmentId&& segment_id) noexcept = default;
59 
60  SegmentId(size_t refinement_level, size_t index) noexcept;
61 
62  constexpr size_t refinement_level() const noexcept {
63  return refinement_level_;
64  }
65 
66  constexpr size_t index() const noexcept { return index_; }
67 
68  SegmentId id_of_parent() const noexcept;
69 
70  SegmentId id_of_child(Side side) const noexcept;
71 
72  /// The other child of the parent of this segment
73  SegmentId id_of_sibling() const noexcept;
74 
75  /// The child of the sibling of this segment that shares an endpoint with it
76  SegmentId id_of_abutting_nibling() const noexcept;
77 
78  /// The side on which this segment shares an endpoint with its sibling
79  Side side_of_sibling() const noexcept;
80 
81  /// The id this segment would have if the coordinate axis were flipped.
82  SegmentId id_if_flipped() const noexcept;
83 
84  /// The logical coordinate of the endpoint of the segment on the given Side.
85  double endpoint(Side side) const noexcept;
86 
87  /// The logical coordinate of the midpoint of the segment
88  double midpoint() const noexcept {
89  return -1.0 + (1.0 + 2.0 * index_) / two_to_the(refinement_level_);
90  }
91 
92  /// Does the segment overlap with another?
93  bool overlaps(const SegmentId& other) const noexcept;
94 
95  /// Serialization for Charm++
96  void pup(PUP::er& p) noexcept; // NOLINT
97 
98  private:
99  size_t refinement_level_ = std::numeric_limits<size_t>::max();
100  size_t index_ = std::numeric_limits<size_t>::max();
101 };
102 
103 /// Output operator for SegmentId.
104 std::ostream& operator<<(std::ostream& os, const SegmentId& id) noexcept;
105 
106 /// Equivalence operator for SegmentId.
107 bool operator==(const SegmentId& lhs, const SegmentId& rhs) noexcept;
108 
109 /// Inequivalence operator for SegmentId.
110 bool operator!=(const SegmentId& lhs, const SegmentId& rhs) noexcept;
111 
112 //##############################################################################
113 // INLINE DEFINITIONS
114 //##############################################################################
115 
116 inline SegmentId SegmentId::id_of_parent() const noexcept {
117  ASSERT(0 != refinement_level_,
118  "Cannot call id_of_parent() on root refinement level!");
119  // The parent has half as many segments as the child.
120  return {refinement_level_ - 1, index_ / 2};
121 }
122 
123 inline SegmentId SegmentId::id_of_child(Side side) const noexcept {
124  // We cannot ASSERT on the maximum level because it's only known at runtime
125  // and only known elsewhere in the code, not by SegmentId. I.e. SegmentId is
126  // too low-level to know about this.
127  // The child has twice as many segments as the parent, so for a particular
128  // parent segment, there is both an upper and lower child segment.
129  if (Side::Lower == side) {
130  return {refinement_level_ + 1, index_ * 2};
131  }
132  return {refinement_level_ + 1, 1 + index_ * 2};
133 }
134 
135 inline SegmentId SegmentId::id_of_sibling() const noexcept {
136  ASSERT(0 != refinement_level_,
137  "The segment on the root refinement level has no sibling");
138  return {refinement_level_, (0 == index_ % 2 ? index_ + 1 : index_ - 1)};
139 }
140 
142  ASSERT(0 != refinement_level_,
143  "The segment on the root refinement level has no abutting nibling");
144  return {refinement_level_ + 1,
145  (0 == index_ % 2 ? 2 * index_ + 2 : 2 * index_ - 1)};
146 }
147 
148 inline Side SegmentId::side_of_sibling() const noexcept {
149  ASSERT(0 != refinement_level_,
150  "The segment on the root refinement level has no sibling");
151  return 0 == index_ % 2 ? Side::Upper : Side::Lower;
152 }
153 
154 inline SegmentId SegmentId::id_if_flipped() const noexcept {
155  return {refinement_level_, two_to_the(refinement_level_) - 1 - index_};
156 }
157 
158 inline double SegmentId::endpoint(Side side) const noexcept {
159  if (Side::Lower == side) {
160  return -1.0 + (2.0 * index_) / two_to_the(refinement_level_);
161  }
162  return -1.0 + (2.0 * index_ + 2.0) / two_to_the(refinement_level_);
163 }
164 
165 inline bool SegmentId::overlaps(const SegmentId& other) const noexcept {
166  const size_t this_denom = two_to_the(refinement_level_);
167  const size_t other_denom = two_to_the(other.refinement_level_);
168  return index_ * other_denom < (other.index_ + 1) * this_denom and
169  other.index_ * this_denom < (index_ + 1) * other_denom;
170 }
171 
172 // These are defined so that a SegmentId can be used as part of a key of an
173 // unordered_set or unordered_map.
174 
175 // hash_value is called by boost::hash and related functions.
176 size_t hash_value(const SegmentId& s) noexcept;
177 
178 inline bool operator==(const SegmentId& lhs, const SegmentId& rhs) noexcept {
179  return (lhs.refinement_level() == rhs.refinement_level() and
180  lhs.index() == rhs.index());
181 }
182 
183 inline bool operator!=(const SegmentId& lhs, const SegmentId& rhs) noexcept {
184  return not(lhs == rhs);
185 }
Side side_of_sibling() const noexcept
The side on which this segment shares an endpoint with its sibling.
Definition: SegmentId.hpp:148
Definition: Strahlkorper.hpp:14
A SegmentId labels a segment of the interval [-1,1] and is used to identify the bounds of an Element ...
Definition: SegmentId.hpp:50
double endpoint(Side side) const noexcept
The logical coordinate of the endpoint of the segment on the given Side.
Definition: SegmentId.hpp:158
#define ASSERT(a, m)
Assert that an expression should be true.
Definition: Assert.hpp:49
Side
A label for the side of a manifold.
Definition: Side.hpp:17
SegmentId id_of_abutting_nibling() const noexcept
The child of the sibling of this segment that shares an endpoint with it.
Definition: SegmentId.hpp:141
bool overlaps(const SegmentId &other) const noexcept
Does the segment overlap with another?
Definition: SegmentId.hpp:165
SegmentId id_of_sibling() const noexcept
The other child of the parent of this segment.
Definition: SegmentId.hpp:135
bool operator==(const SegmentId &lhs, const SegmentId &rhs) noexcept
Equivalence operator for SegmentId.
Definition: SegmentId.hpp:178
std::ostream & operator<<(std::ostream &os, const SegmentId &id) noexcept
Output operator for SegmentId.
Definition: SegmentId.cpp:21
T max(T... args)
constexpr T two_to_the(T n)
Compute 2 to the n for integral types.
Definition: ConstantExpressions.hpp:34
Define simple functions for constant expressions.
Defines macro ASSERT.
bool operator!=(const SegmentId &lhs, const SegmentId &rhs) noexcept
Inequivalence operator for SegmentId.
Definition: SegmentId.hpp:183
SegmentId id_if_flipped() const noexcept
The id this segment would have if the coordinate axis were flipped.
Definition: SegmentId.hpp:154
double midpoint() const noexcept
The logical coordinate of the midpoint of the segment.
Definition: SegmentId.hpp:88
Defines enum class Side.