| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /** | ||
| 2 | * @file | ||
| 3 | * @brief Closed interval of generic values | ||
| 4 | *//* | ||
| 5 | * Copyright 2011 Krzysztof Kosiński <tweenk.pl@gmail.com> | ||
| 6 | * | ||
| 7 | * This library is free software; you can redistribute it and/or | ||
| 8 | * modify it either under the terms of the GNU Lesser General Public | ||
| 9 | * License version 2.1 as published by the Free Software Foundation | ||
| 10 | * (the "LGPL") or, at your option, under the terms of the Mozilla | ||
| 11 | * Public License Version 1.1 (the "MPL"). If you do not alter this | ||
| 12 | * notice, a recipient may use your version of this file under either | ||
| 13 | * the MPL or the LGPL. | ||
| 14 | * | ||
| 15 | * You should have received a copy of the LGPL along with this library | ||
| 16 | * in the file COPYING-LGPL-2.1; if not, write to the Free Software | ||
| 17 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | ||
| 18 | * You should have received a copy of the MPL along with this library | ||
| 19 | * in the file COPYING-MPL-1.1 | ||
| 20 | * | ||
| 21 | * The contents of this file are subject to the Mozilla Public License | ||
| 22 | * Version 1.1 (the "License"); you may not use this file except in | ||
| 23 | * compliance with the License. You may obtain a copy of the License at | ||
| 24 | * http://www.mozilla.org/MPL/ | ||
| 25 | * | ||
| 26 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY | ||
| 27 | * OF ANY KIND, either express or implied. See the LGPL or the MPL for | ||
| 28 | * the specific language governing rights and limitations. | ||
| 29 | */ | ||
| 30 | |||
| 31 | #ifndef LIB2GEOM_SEEN_GENERIC_INTERVAL_H | ||
| 32 | #define LIB2GEOM_SEEN_GENERIC_INTERVAL_H | ||
| 33 | |||
| 34 | #include <cassert> | ||
| 35 | #include <iostream> | ||
| 36 | #include <optional> | ||
| 37 | #include <tuple> | ||
| 38 | #include <boost/functional/hash.hpp> | ||
| 39 | #include <2geom/coord.h> | ||
| 40 | |||
| 41 | namespace Geom { | ||
| 42 | |||
| 43 | template <typename C> | ||
| 44 | class GenericOptInterval; | ||
| 45 | |||
| 46 | /** | ||
| 47 | * @brief A range of numbers which is never empty. | ||
| 48 | * @ingroup Primitives | ||
| 49 | */ | ||
| 50 | template <typename C> | ||
| 51 | class GenericInterval | ||
| 52 | : CoordTraits<C>::IntervalOps | ||
| 53 | { | ||
| 54 | using CInterval = typename CoordTraits<C>::IntervalType; | ||
| 55 | using Self = GenericInterval<C>; | ||
| 56 | protected: | ||
| 57 | C _b[2] = { 0, 0 }; | ||
| 58 | public: | ||
| 59 | /// @name Create intervals. | ||
| 60 | /// @{ | ||
| 61 | /** @brief Create an interval that contains only zero. */ | ||
| 62 | ✗ | constexpr GenericInterval() = default; | |
| 63 | /** @brief Create an interval that contains a single point. */ | ||
| 64 | 1797516 | explicit constexpr GenericInterval(C u) { _b[0] = _b[1] = u; } | |
| 65 | /** @brief Create an interval that contains all points between @c u and @c v. */ | ||
| 66 | 288422 | constexpr GenericInterval(C u, C v) { | |
| 67 |
2/2✓ Branch 0 taken 281216 times.
✓ Branch 1 taken 7206 times.
|
288422 | if (u <= v) { |
| 68 | 281216 | _b[0] = u; _b[1] = v; | |
| 69 | } else { | ||
| 70 | 7206 | _b[0] = v; _b[1] = u; | |
| 71 | } | ||
| 72 | 288422 | } | |
| 73 | |||
| 74 | /** @brief Create an interval containing a range of values. | ||
| 75 | * The resulting interval will contain all values from the given range. | ||
| 76 | * The return type of iterators must be convertible to C. The given range | ||
| 77 | * must not be empty. For potentially empty ranges, see GenericOptInterval. | ||
| 78 | * @param start Beginning of the range | ||
| 79 | * @param end End of the range | ||
| 80 | * @return Interval that contains all values from [start, end). */ | ||
| 81 | template <typename InputIterator> | ||
| 82 | 1797516 | static CInterval from_range(InputIterator start, InputIterator end) { | |
| 83 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1797516 times.
|
1797516 | assert(start != end); |
| 84 |
1/2✓ Branch 2 taken 1797516 times.
✗ Branch 3 not taken.
|
1797516 | CInterval result(*start++); |
| 85 |
2/2✓ Branch 1 taken 1797832 times.
✓ Branch 2 taken 1797516 times.
|
3595348 | for (; start != end; ++start) result.expandTo(*start); |
| 86 | 1797516 | return result; | |
| 87 | } | ||
| 88 | /** @brief Create an interval from a C-style array of values it should contain. */ | ||
| 89 | 1797516 | static CInterval from_array(C const *c, unsigned n) { | |
| 90 | 1797516 | return from_range(c, c + n); | |
| 91 | } | ||
| 92 | /// @} | ||
| 93 | |||
| 94 | /// @name Inspect contained values. | ||
| 95 | /// @{ | ||
| 96 | 886084 | constexpr C min() const { return _b[0]; } | |
| 97 | 807184 | constexpr C max() const { return _b[1]; } | |
| 98 | 958460 | constexpr C extent() const { return max() - min(); } | |
| 99 | 468 | constexpr C middle() const { return (max() + min()) / 2; } | |
| 100 | ✗ | constexpr bool isSingular() const { return min() == max(); } | |
| 101 | C operator[](unsigned i) const { assert(i < 2); return _b[i]; } | ||
| 102 | constexpr C operator[](Dim2 d) const { return _b[d]; } | ||
| 103 | ✗ | constexpr C clamp(C val) const { | |
| 104 | ✗ | return std::clamp(val, min(), max()); | |
| 105 | } | ||
| 106 | /// Return the closer end of the interval. | ||
| 107 | C nearestEnd(C val) const { | ||
| 108 | C dmin = std::abs(val - min()), dmax = std::abs(val - max()); | ||
| 109 | return dmin <= dmax ? min() : max(); | ||
| 110 | } | ||
| 111 | // Structured binding support | ||
| 112 | template <size_t I> constexpr C get() const { static_assert(I < 2); return _b[I]; } | ||
| 113 | /// @} | ||
| 114 | |||
| 115 | /// @name Test coordinates and other intervals for inclusion. | ||
| 116 | /// @{ | ||
| 117 | /** @brief Check whether the interval includes this number. */ | ||
| 118 | 522125 | constexpr bool contains(C val) const { | |
| 119 |
4/4✓ Branch 1 taken 425452 times.
✓ Branch 2 taken 96673 times.
✓ Branch 4 taken 334032 times.
✓ Branch 5 taken 91420 times.
|
522125 | return min() <= val && val <= max(); |
| 120 | } | ||
| 121 | /** @brief Check whether the interval includes the given interval. */ | ||
| 122 | 31632 | constexpr bool contains(CInterval const &val) const { | |
| 123 |
4/4✓ Branch 2 taken 29707 times.
✓ Branch 3 taken 1925 times.
✓ Branch 6 taken 29206 times.
✓ Branch 7 taken 501 times.
|
31632 | return min() <= val.min() && val.max() <= max(); |
| 124 | } | ||
| 125 | /** @brief Check whether the intervals have any common elements. */ | ||
| 126 | 60362 | constexpr bool intersects(CInterval const &val) const { | |
| 127 |
8/8✓ Branch 2 taken 34469 times.
✓ Branch 3 taken 25893 times.
✓ Branch 6 taken 29232 times.
✓ Branch 7 taken 5237 times.
✓ Branch 11 taken 29155 times.
✓ Branch 12 taken 77 times.
✓ Branch 13 taken 29232 times.
✓ Branch 14 taken 31130 times.
|
60362 | return contains(val.min()) || contains(val.max()) || val.contains(*this); |
| 128 | } | ||
| 129 | /// @} | ||
| 130 | |||
| 131 | /// @name Modify the interval. | ||
| 132 | /// @{ | ||
| 133 | //TODO: NaN handleage for the next two? | ||
| 134 | /** @brief Set the lower boundary of the interval. | ||
| 135 | * When the given number is larger than the interval's largest element, | ||
| 136 | * it will be reduced to the single number @c val. */ | ||
| 137 | 241607 | constexpr void setMin(C val) { | |
| 138 |
2/2✓ Branch 0 taken 113485 times.
✓ Branch 1 taken 128122 times.
|
241607 | if (val > _b[1]) { |
| 139 | 113485 | _b[0] = _b[1] = val; | |
| 140 | } else { | ||
| 141 | 128122 | _b[0] = val; | |
| 142 | } | ||
| 143 | 241607 | } | |
| 144 | /** @brief Set the upper boundary of the interval. | ||
| 145 | * When the given number is smaller than the interval's smallest element, | ||
| 146 | * it will be reduced to the single number @c val. */ | ||
| 147 | 241607 | constexpr void setMax(C val) { | |
| 148 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 241607 times.
|
241607 | if (val < _b[0]) { |
| 149 | ✗ | _b[1] = _b[0] = val; | |
| 150 | } else { | ||
| 151 | 241607 | _b[1] = val; | |
| 152 | } | ||
| 153 | 241607 | } | |
| 154 | /// Set both ends of the interval simultaneously | ||
| 155 | 966 | constexpr void setEnds(C a, C b) { | |
| 156 |
1/2✓ Branch 0 taken 966 times.
✗ Branch 1 not taken.
|
966 | if (a <= b) { |
| 157 | 966 | _b[0] = a; | |
| 158 | 966 | _b[1] = b; | |
| 159 | } else { | ||
| 160 | ✗ | _b[0] = b; | |
| 161 | ✗ | _b[1] = a; | |
| 162 | } | ||
| 163 | 966 | } | |
| 164 | /** @brief Extend the interval to include the given number. */ | ||
| 165 | 1881366 | constexpr void expandTo(C val) { | |
| 166 |
2/2✓ Branch 0 taken 708648 times.
✓ Branch 1 taken 1172718 times.
|
1881366 | if (val < _b[0]) _b[0] = val; |
| 167 |
2/2✓ Branch 0 taken 714241 times.
✓ Branch 1 taken 1167125 times.
|
1881366 | if (val > _b[1]) _b[1] = val; // no else, as we want to handle NaN |
| 168 | 1881366 | } | |
| 169 | /** @brief Expand or shrink the interval in both directions by the given amount. | ||
| 170 | * After this method, the interval's length (extent) will be increased by | ||
| 171 | * <code>amount * 2</code>. Negative values can be given; they will shrink the interval. | ||
| 172 | * Shrinking by a value larger than half the interval's length will create a degenerate | ||
| 173 | * interval containing only the midpoint of the original. */ | ||
| 174 | ✗ | constexpr void expandBy(C amount) { | |
| 175 | ✗ | _b[0] -= amount; | |
| 176 | ✗ | _b[1] += amount; | |
| 177 | ✗ | if (_b[0] > _b[1]) { | |
| 178 | ✗ | C halfway = (_b[0] + _b[1]) / 2; | |
| 179 | ✗ | _b[0] = _b[1] = halfway; | |
| 180 | } | ||
| 181 | ✗ | } | |
| 182 | /** @brief Union the interval with another one. | ||
| 183 | * The resulting interval will contain all points of both intervals. | ||
| 184 | * It might also contain some points which didn't belong to either - this happens | ||
| 185 | * when the intervals did not have any common elements. */ | ||
| 186 | 23490 | constexpr void unionWith(CInterval const &a) { | |
| 187 |
2/2✓ Branch 0 taken 4502 times.
✓ Branch 1 taken 18988 times.
|
23490 | if (a._b[0] < _b[0]) _b[0] = a._b[0]; |
| 188 |
2/2✓ Branch 0 taken 12017 times.
✓ Branch 1 taken 11473 times.
|
23490 | if (a._b[1] > _b[1]) _b[1] = a._b[1]; |
| 189 | 23490 | } | |
| 190 | /// @} | ||
| 191 | |||
| 192 | /// @name Operators | ||
| 193 | /// @{ | ||
| 194 | //IMPL: OffsetableConcept | ||
| 195 | //TODO: rename output_type to something else in the concept | ||
| 196 | using output_type = C; | ||
| 197 | /** @brief Offset the interval by a specified amount */ | ||
| 198 | ✗ | constexpr Self &operator+=(C amnt) { | |
| 199 | ✗ | _b[0] += amnt; _b[1] += amnt; | |
| 200 | ✗ | return *this; | |
| 201 | } | ||
| 202 | /** @brief Offset the interval by the negation of the specified amount */ | ||
| 203 | ✗ | constexpr Self &operator-=(C amnt) { | |
| 204 | ✗ | _b[0] -= amnt; _b[1] -= amnt; | |
| 205 | ✗ | return *this; | |
| 206 | } | ||
| 207 | |||
| 208 | /** @brief Return an interval mirrored about 0 */ | ||
| 209 | ✗ | constexpr Self operator-() const { return { -_b[1], -_b[0] }; } | |
| 210 | // IMPL: AddableConcept | ||
| 211 | /** @brief Add two intervals. | ||
| 212 | * Sum is defined as the set of points that can be obtained by adding any two values | ||
| 213 | * from both operands: \f$S = \{x \in A, y \in B: x + y\}\f$ */ | ||
| 214 | ✗ | constexpr Self &operator+=(CInterval const &o) { | |
| 215 | ✗ | _b[0] += o._b[0]; | |
| 216 | ✗ | _b[1] += o._b[1]; | |
| 217 | ✗ | return *this; | |
| 218 | } | ||
| 219 | /** @brief Subtract two intervals. | ||
| 220 | * Difference is defined as the set of points that can be obtained by subtracting | ||
| 221 | * any value from the second operand from any value from the first operand: | ||
| 222 | * \f$S = \{x \in A, y \in B: x - y\}\f$ */ | ||
| 223 | ✗ | constexpr Self &operator-=(CInterval const &o) { | |
| 224 | // equal to *this += -o | ||
| 225 | ✗ | _b[0] -= o._b[1]; | |
| 226 | ✗ | _b[1] -= o._b[0]; | |
| 227 | ✗ | return *this; | |
| 228 | } | ||
| 229 | /** @brief Union two intervals. | ||
| 230 | * Note that the intersection-and-assignment operator is not defined, | ||
| 231 | * because the result of an intersection can be empty, while Interval cannot. */ | ||
| 232 | ✗ | constexpr Self &operator|=(CInterval const &o) { | |
| 233 | ✗ | unionWith(o); | |
| 234 | ✗ | return *this; | |
| 235 | } | ||
| 236 | /** @brief Test for interval equality. */ | ||
| 237 | ✗ | constexpr bool operator==(CInterval const &other) const { | |
| 238 | ✗ | return min() == other.min() && max() == other.max(); | |
| 239 | } | ||
| 240 | /// @} | ||
| 241 | }; | ||
| 242 | |||
| 243 | /** @brief Union two intervals | ||
| 244 | * @relates GenericInterval */ | ||
| 245 | template <typename C> | ||
| 246 | inline GenericInterval<C> unify(GenericInterval<C> const &a, GenericInterval<C> const &b) { | ||
| 247 | return a | b; | ||
| 248 | } | ||
| 249 | |||
| 250 | /** | ||
| 251 | * @brief A range of numbers that can be empty. | ||
| 252 | * @ingroup Primitives | ||
| 253 | */ | ||
| 254 | template <typename C> | ||
| 255 | class GenericOptInterval | ||
| 256 | : public std::optional<typename CoordTraits<C>::IntervalType> | ||
| 257 | , boost::orable< GenericOptInterval<C> | ||
| 258 | , boost::andable< GenericOptInterval<C> | ||
| 259 | >> | ||
| 260 | { | ||
| 261 | using CInterval = typename CoordTraits<C>::IntervalType; | ||
| 262 | using OptCInterval = typename CoordTraits<C>::OptIntervalType; | ||
| 263 | using Base = std::optional<CInterval>; | ||
| 264 | public: | ||
| 265 | /// @name Create optionally empty intervals. | ||
| 266 | /// @{ | ||
| 267 | /** @brief Create an empty interval. */ | ||
| 268 | 141 | constexpr GenericOptInterval() = default; | |
| 269 | /** @brief Wrap an existing interval. */ | ||
| 270 | 2095543 | constexpr GenericOptInterval(GenericInterval<C> const &a) : Base(CInterval(a)) {} | |
| 271 | /** @brief Create an interval containing a single point. */ | ||
| 272 | ✗ | constexpr GenericOptInterval(C u) : Base(CInterval(u)) {} | |
| 273 | /** @brief Create an interval containing a range of numbers. */ | ||
| 274 |
1/2✓ Branch 2 taken 318 times.
✗ Branch 3 not taken.
|
318 | constexpr GenericOptInterval(C u, C v) : Base(CInterval(u, v)) {} |
| 275 | |||
| 276 | /** @brief Create a possibly empty interval containing a range of values. | ||
| 277 | * The resulting interval will contain all values from the given range. | ||
| 278 | * The return type of iterators must be convertible to C. The given range | ||
| 279 | * may be empty. | ||
| 280 | * @param start Beginning of the range | ||
| 281 | * @param end End of the range | ||
| 282 | * @return Interval that contains all values from [start, end), or nothing if the range | ||
| 283 | * is empty. */ | ||
| 284 | template <typename InputIterator> | ||
| 285 | static GenericOptInterval<C> from_range(InputIterator start, InputIterator end) { | ||
| 286 | if (start == end) { | ||
| 287 | return {}; | ||
| 288 | } | ||
| 289 | return CInterval::from_range(start, end); | ||
| 290 | } | ||
| 291 | /// @} | ||
| 292 | |||
| 293 | /** @brief Check whether this interval is empty. */ | ||
| 294 | 773 | constexpr bool empty() const { return !*this; } | |
| 295 | |||
| 296 | /** @brief Union with another interval, gracefully handling empty ones. */ | ||
| 297 | ✗ | constexpr void unionWith(GenericOptInterval<C> const &a) { | |
| 298 | ✗ | if (a) { | |
| 299 | ✗ | if (*this) { // check that we are not empty | |
| 300 | ✗ | (*this)->unionWith(*a); | |
| 301 | } else { | ||
| 302 | ✗ | *this = *a; | |
| 303 | } | ||
| 304 | } | ||
| 305 | ✗ | } | |
| 306 | ✗ | constexpr void intersectWith(GenericOptInterval<C> const &o) { | |
| 307 | ✗ | if (o && *this) { | |
| 308 | ✗ | C u = std::max((*this)->min(), o->min()); | |
| 309 | ✗ | C v = std::min((*this)->max(), o->max()); | |
| 310 | ✗ | if (u <= v) { | |
| 311 | ✗ | *this = CInterval(u, v); | |
| 312 | ✗ | return; | |
| 313 | } | ||
| 314 | } | ||
| 315 | ✗ | *this = {}; | |
| 316 | } | ||
| 317 | constexpr GenericOptInterval<C> &operator|=(OptCInterval const &o) { | ||
| 318 | unionWith(o); | ||
| 319 | return *this; | ||
| 320 | } | ||
| 321 | ✗ | constexpr GenericOptInterval<C> &operator&=(OptCInterval const &o) { | |
| 322 | ✗ | intersectWith(o); | |
| 323 | ✗ | return *this; | |
| 324 | } | ||
| 325 | |||
| 326 | // The equality operators inherited from std::optional don't work with derived types, because | ||
| 327 | // the template overload ignores that the derived type is also an optional. It would result in | ||
| 328 | // `GenericInterval() != GenericInterval()` being true. | ||
| 329 | template <typename U, typename = std::enable_if_t<std::is_base_of_v<Base, U>>> | ||
| 330 | ✗ | constexpr bool operator==(U const &other) const { | |
| 331 | ✗ | return static_cast<Base const &>(*this) == static_cast<Base const &>(other); | |
| 332 | } | ||
| 333 | template <typename U, typename = std::enable_if_t<std::is_base_of_v<Base, U>>> | ||
| 334 | ✗ | constexpr bool operator!=(U const &other) const { | |
| 335 | ✗ | return static_cast<Base const &>(*this) != static_cast<Base const &>(other); | |
| 336 | } | ||
| 337 | }; | ||
| 338 | |||
| 339 | /** @brief Intersect two intervals and return a possibly empty range of numbers | ||
| 340 | * @relates GenericOptInterval */ | ||
| 341 | template <typename C> | ||
| 342 | inline GenericOptInterval<C> intersect(GenericInterval<C> const &a, GenericInterval<C> const &b) { | ||
| 343 | return GenericOptInterval<C>(a) & GenericOptInterval<C>(b); | ||
| 344 | } | ||
| 345 | /** @brief Intersect two intervals and return a possibly empty range of numbers | ||
| 346 | * @relates GenericOptInterval */ | ||
| 347 | template <typename C> | ||
| 348 | ✗ | inline GenericOptInterval<C> operator&(GenericInterval<C> const &a, GenericInterval<C> const &b) { | |
| 349 | ✗ | return GenericOptInterval<C>(a) & GenericOptInterval<C>(b); | |
| 350 | } | ||
| 351 | |||
| 352 | template <typename C> | ||
| 353 | inline std::ostream &operator<<(std::ostream &out, | ||
| 354 | GenericInterval<C> const &I) { | ||
| 355 | return out << "Interval(" << I.min() << ", " << I.max() << ")"; | ||
| 356 | } | ||
| 357 | |||
| 358 | template <typename C> | ||
| 359 | inline std::ostream &operator<<(std::ostream &out, | ||
| 360 | GenericOptInterval<C> const &I) { | ||
| 361 | return I ? (out << *I) : (out << "Interval (empty)"); | ||
| 362 | } | ||
| 363 | |||
| 364 | } // namespace Geom | ||
| 365 | |||
| 366 | // Structured binding support | ||
| 367 | template <typename C> struct std::tuple_size<Geom::GenericInterval<C>> : std::integral_constant<size_t, 2> {}; | ||
| 368 | template <size_t I, typename C> struct std::tuple_element<I, Geom::GenericInterval<C>> { using type = C; }; | ||
| 369 | |||
| 370 | // Hash support | ||
| 371 | template <typename C> struct std::hash<Geom::GenericInterval<C>> | ||
| 372 | { | ||
| 373 | size_t operator()(Geom::GenericInterval<C> const &a) const noexcept { | ||
| 374 | size_t hash = 0; | ||
| 375 | boost::hash_combine(hash, a.min()); | ||
| 376 | boost::hash_combine(hash, a.max()); | ||
| 377 | return hash; | ||
| 378 | } | ||
| 379 | }; | ||
| 380 | |||
| 381 | #endif // LIB2GEOM_SEEN_GENERIC_INTERVAL_H | ||
| 382 | |||
| 383 | /* | ||
| 384 | Local Variables: | ||
| 385 | mode:c++ | ||
| 386 | c-file-style:"stroustrup" | ||
| 387 | c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) | ||
| 388 | indent-tabs-mode:nil | ||
| 389 | fill-column:99 | ||
| 390 | End: | ||
| 391 | */ | ||
| 392 | // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : | ||
| 393 |