Interval class#
-
template<class TValue, class TIndex = default_config::index_t>
class Interval# An interval \([\![ a, b [\![\) of integral coordinates with step and storage index.
The index is used to associate each discrete coordinate c within the interval to a value in a storage, at the position given by index + c
It implies that index may be negative but it allows to shrink the interval (e.g. during a intersection operation) without the need to recalculate the index.
In the context of finite volume schemes, an interval is mapped to a span of cells: considering that the cell of index \(i\) and level \(l\) is associated to the real interval \(\left[\frac{i}{2^l}, \frac{i + 1}{2^l}\right]\), then an
Interval
\([\![ a, b [\![\) at level \(l\) is associated to the real interval \(\left[\frac{a}{2^l}, \frac{b}{2^l}\right]\).Thus, any operation like space shifting (using
+
or-
), space scaling (using*
or/
) or level change (using>>
or<<
) applied on anInterval
should result in the smallestInterval
that contains the result of the same operation applied on the real interval.- Template Parameters:
TValue – The coordinate type (must be signed).
TIndex – The index type (must be signed).
Public Functions
-
inline bool contains(value_t x) const#
Returns true if the given coordinate lies within the interval.
-
inline std::size_t size() const#
Returns the size (number of discrete coordinates) of the interval.
-
inline bool is_valid() const#
Returns if the interval has a valid state (i.e.
not empty).
-
inline Interval even_elements() const#
Returns the even elements of the interval.
Warning
the result could be an invalid interval.
-
inline Interval odd_elements() const#
Returns the odd elements of the interval.
Warning
the result could be an invalid interval.
-
inline Interval &operator>>=(std::size_t i)#
Decreases level by given non-negative shift.
Given an
Interval
\([\![ a, b [\![\) at level \(l\), and a non-negative shift \(i <= l\) (subsequent shifts are ignored), it should return the smallestInterval
\([\![ a', b' [\![\) at level \(l - i\) such that \(\left[\frac{a}{2^l}, \frac{b}{2^l}\right] \subseteq \left[\frac{a'}{2^{l - i}}, \frac{b'}{2^{l - i}}\right] \).This is equivalent to:
find the greatest integer \(a'\) so that \(\frac{a'}{2^{l - i}} \le \frac{a}{2^l} \Longleftrightarrow a' = \left \lfloor \frac{a}{2^i} \right \rfloor\),
find the smallest integer \(b'\) so that \(\frac{b'}{2^{l - i}} \ge \frac{b}{2^l} \Longleftrightarrow b' = \left \lceil \frac{b}{2^i} \right \rceil\).
Using the property that, for an integer \(n\) and a positive integer \(m\), \( \left\lceil \frac{n}{m} \right\rceil = \left\lfloor \frac{n - 1}{m} \right\rfloor + 1 \) then \(b' = \left\lfloor \frac{b - 1}{2^i} \right\rfloor + 1\).
Since C++20, \( \left\lfloor \frac{n}{2^i} \right\rfloor \) is equal to
n >> i
, so that the update of theInterval
should look like:Before that, the result on a negative integer is implementation-defined but compilers seem to be consistent with the C++20 norm.start >>= i; end = ((end - 1) >> i) + 1;
-
inline Interval &operator<<=(std::size_t i)#
Increases level by given non-negative shift.
Given an
Interval
\([\![ a, b [\![\) at level \(l\), it should return the smallestInterval
\([\![ a', b' [\![\) at level \(l + i\) such that \(\left[\frac{a}{2^l}, \frac{b}{2^l}\right] \subseteq \left[\frac{a'}{2^{l + i}}, \frac{b'}{2^{l + i}}\right] \).This is equivalent to:
find the greatest integer \(a'\) so that \(\frac{a'}{2^{l + i}} \le \frac{a}{2^l} \Longleftrightarrow a' = \left \lfloor a 2^i \right \rfloor = a 2^i\),
find the smallest integer \(b'\) so that \(\frac{b'}{2^{l + i}} \ge \frac{b}{2^l} \Longleftrightarrow b' = \left \lceil b 2^i \right \rceil = b 2^i\).
Since C++20, it is equal to respectively
a << i
andb << i
. Before that, the result on a negative integer is undefined but compilers seem to be consistent with the C++20 norm.