LSST Applications 27.0.0,g0265f82a02+469cd937ee,g02d81e74bb+21ad69e7e1,g1470d8bcf6+cbe83ee85a,g2079a07aa2+e67c6346a6,g212a7c68fe+04a9158687,g2305ad1205+94392ce272,g295015adf3+81dd352a9d,g2bbee38e9b+469cd937ee,g337abbeb29+469cd937ee,g3939d97d7f+72a9f7b576,g487adcacf7+71499e7cba,g50ff169b8f+5929b3527e,g52b1c1532d+a6fc98d2e7,g591dd9f2cf+df404f777f,g5a732f18d5+be83d3ecdb,g64a986408d+21ad69e7e1,g858d7b2824+21ad69e7e1,g8a8a8dda67+a6fc98d2e7,g99cad8db69+f62e5b0af5,g9ddcbc5298+d4bad12328,ga1e77700b3+9c366c4306,ga8c6da7877+71e4819109,gb0e22166c9+25ba2f69a1,gb6a65358fc+469cd937ee,gbb8dafda3b+69d3c0e320,gc07e1c2157+a98bf949bb,gc120e1dc64+615ec43309,gc28159a63d+469cd937ee,gcf0d15dbbd+72a9f7b576,gdaeeff99f8+a38ce5ea23,ge6526c86ff+3a7c1ac5f1,ge79ae78c31+469cd937ee,gee10cc3b42+a6fc98d2e7,gf1cff7945b+21ad69e7e1,gfbcc870c63+9a11dc8c8f
LSST Data Management Base Package
Loading...
Searching...
No Matches
RangeSet.cc
Go to the documentation of this file.
1/*
2 * This file is part of sphgeom.
3 *
4 * Developed for the LSST Data Management System.
5 * This product includes software developed by the LSST Project
6 * (http://www.lsst.org).
7 * See the COPYRIGHT file at the top-level directory of this distribution
8 * for details of code ownership.
9 *
10 * This software is dual licensed under the GNU General Public License and also
11 * under a 3-clause BSD license. Recipients may choose which of these licenses
12 * to use; please see the files gpl-3.0.txt and/or bsd_license.txt,
13 * respectively. If you choose the GPL option then the following text applies
14 * (but note that there is still no warranty even if you opt for BSD instead):
15 *
16 * This program is free software: you can redistribute it and/or modify
17 * it under the terms of the GNU General Public License as published by
18 * the Free Software Foundation, either version 3 of the License, or
19 * (at your option) any later version.
20 *
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * You should have received a copy of the GNU General Public License
27 * along with this program. If not, see <http://www.gnu.org/licenses/>.
28 */
29
32
34
35#include <algorithm>
36#include <ostream>
37
38
39namespace lsst {
40namespace sphgeom {
41
42namespace {
43
44// `roundUpToEven` returns the smallest multiple of 2
45// greater than or equal to i.
46inline ptrdiff_t roundUpToEven(ptrdiff_t i) { return i + (i & 1); }
47
48
49// `RangeIter` is a stride-2 iterator over uint64_t values
50// in an underlying array.
51struct RangeIter {
52
53 // For std::iterator_traits
54 using difference_type = ptrdiff_t;
55 using value_type = uint64_t;
56 using pointer = uint64_t *;
57 using reference = uint64_t &;
58 using iterator_category = std::random_access_iterator_tag;
59
60 RangeIter() = default;
61 explicit RangeIter(uint64_t * p) : ptr{p} {}
62
63 friend void swap(RangeIter & a, RangeIter & b) { std::swap(a.ptr, b.ptr); }
64
65 // Arithmetic
66 RangeIter & operator++() { ptr += 2; return *this; }
67 RangeIter & operator--() { ptr -= 2; return *this; }
68
69 RangeIter operator++(int) { RangeIter i(*this); ptr += 2; return i; }
70 RangeIter operator--(int) { RangeIter i(*this); ptr -= 2; return i; }
71
72 RangeIter operator+(ptrdiff_t n) const { return RangeIter(ptr + 2 * n); }
73 RangeIter operator-(ptrdiff_t n) const { return RangeIter(ptr + 2 * n); }
74
75 RangeIter & operator+=(ptrdiff_t n) { ptr += 2 * n; return *this; }
76 RangeIter & operator-=(ptrdiff_t n) { ptr -= 2 * n; return *this; }
77
78 friend RangeIter operator+(ptrdiff_t n, RangeIter const & i) { return i + n; }
79
80 ptrdiff_t operator-(RangeIter const & i) const { return (ptr - i.ptr) / 2; }
81
82 // Comparison
83 bool operator==(RangeIter const & i) const { return ptr == i.ptr; }
84 bool operator!=(RangeIter const & i) const { return ptr != i.ptr; }
85 bool operator<(RangeIter const & i) const { return ptr < i.ptr; }
86 bool operator>(RangeIter const & i) const { return ptr > i.ptr; }
87 bool operator<=(RangeIter const & i) const { return ptr <= i.ptr; }
88 bool operator>=(RangeIter const & i) const { return ptr >= i.ptr; }
89
90 // Dereferencing
91 uint64_t & operator*() const { return *ptr; }
92 uint64_t * operator->() const { return ptr; }
93 uint64_t & operator[](ptrdiff_t n) const { return ptr[2 * n]; }
94
95 uint64_t * ptr = nullptr;
96};
97
98} // unnamed namespace
99
100
102 RangeSet(list.begin(), list.end())
103{}
104
106 for (auto t: list) {
107 insert(std::get<0>(t), std::get<1>(t));
108 }
109}
110
111void RangeSet::insert(uint64_t first, uint64_t last) {
112 if (first == last) {
113 fill();
114 } else {
115 // Ensure that there is enough space for 2 new values in _ranges.
116 // Afterwards, none of the possible modifications of _ranges will throw,
117 // so the strong exception safety guarantee is provided.
118 _ranges.reserve(_ranges.size() + 2);
119 if (first <= last - 1) {
120 _insert(first, last);
121 } else {
122 _insert(0, last);
123 _insert(first, 0);
124 }
125 }
126}
127
128void RangeSet::erase(uint64_t first, uint64_t last) {
129 // To erase [first, last), insert it into the complement of this set,
130 // then complement the result. The complements are performed in the
131 // constructor and destructor of a local object, so that the second
132 // complement is executed even if insert throws.
133 struct Complementor {
134 RangeSet & set;
135 Complementor(RangeSet & s) : set(s) { set.complement(); }
136 ~Complementor() { set.complement(); }
137 };
138 Complementor c(*this);
139 insert(first, last);
140}
141
144 if (this == &s) {
145 result = s;
146 } else {
147 result._intersect(_begin(), _end(), s._begin(), s._end());
148 }
149 return result;
150}
151
154 if (this == &s) {
155 result = s;
156 } else {
157 // A ∪ B = ¬(¬A ∩ ¬B)
158 result._intersect(_beginc(), _endc(), s._beginc(), s._endc());
159 result.complement();
160 }
161 return result;
162}
163
166 if (this != &s) {
167 // A ∖ B = A ∩ ¬B
168 result._intersect(_begin(), _end(), s._beginc(), s._endc());
169 }
170 return result;
171}
172
175 if (this != &s) {
176 if (empty()) {
177 result = s;
178 } else if (s.empty()) {
179 result = *this;
180 } else {
181 // Sweep through the beginning and end points of the ranges from
182 // sets A and B in ascending order.
183 //
184 // Passing through the beginning of a range toggles the
185 // corresponding state (astate or bstate) from 0 to 1, and passing
186 // through the end toggles it from 1 to 0. The XOR of astate and
187 // bstate determines whether or not the current position of the
188 // sweep is inside the symmetric set difference of A and B.
189 //
190 // Merging the sorted lists of ranges from each set is complicated
191 // by trailing zero bookends. These compare less than or equal to
192 // all other values, even though logically they are greater than
193 // them all.
194 //
195 // To handle this, leading zero bookends are dealt with outside of
196 // the main loop. Then, 1 is subtracted from all other values prior
197 // to comparison, yielding the proper ordering (since subtracting
198 // 1 from a trailing zero bookend results in 2^64 - 1).
199 uint64_t const * a = _begin();
200 uint64_t const * aend = _end();
201 uint64_t const * b = s._begin();
202 uint64_t const * bend = s._end();
203 int astate = (*a == 0);
204 int bstate = (*b == 0);
205 a += astate;
206 b += bstate;
207 // state is 0 if the next value to output is the beginning
208 // of a range, and 1 otherwise.
209 int state = astate ^ bstate;
210 // Start with a vector containing just the leading bookend.
211 result._ranges = {0};
212 // If 0 is contained in exactly one of the two sets, it is
213 // in their symmetric difference.
214 result._offset = (state == 0);
215 // Merge lists until one or both are exhausted.
216 while (a != aend && b != bend) {
217 uint64_t av = *a - 1;
218 uint64_t bv = *b - 1;
219 // The pointer(s) yielding the minimal value will be
220 // incremented.
221 bool ainc = (av <= bv);
222 bool binc = (bv <= av);
223 uint64_t minval = ainc ? av : bv;
224 astate ^= ainc;
225 bstate ^= binc;
226 // Output the minimum value if the output state changes.
227 if (state != (astate ^ bstate)) {
228 result._ranges.push_back(minval + 1);
229 state ^= 1;
230 }
231 a += ainc;
232 b += binc;
233 }
234 // The sweep has exhausted at least one list. Each remaining
235 // beginning and end point in the other list will toggle the
236 // output state, so they can simply be appended to the result.
237 result._ranges.insert(result._ranges.end(), a, aend);
238 result._ranges.insert(result._ranges.end(), b, bend);
239 // Append a trailing bookend if necessary.
240 if ((aend[-1] == 0) == (bend[-1] == 0)) {
241 result._ranges.push_back(0);
242 }
243 }
244 }
245 return result;
246}
247
248bool RangeSet::intersects(uint64_t first, uint64_t last) const {
249 if (empty()) {
250 return false;
251 }
252 if (first == last) {
253 return true;
254 }
255 if (first <= last - 1) {
256 uint64_t r[2] = {first, last};
257 return _intersectsOne(r, _begin(), _end());
258 }
259 uint64_t r[4] = {0, last, first, 0};
260 return _intersectsOne(r, _begin(), _end()) ||
261 _intersectsOne(r + 2, _begin(), _end());
262}
263
264bool RangeSet::intersects(RangeSet const & s) const {
265 if (empty() || s.empty()) {
266 return false;
267 }
268 return _intersects(_begin(), _end(), s._begin(), s._end());
269}
270
271bool RangeSet::contains(uint64_t first, uint64_t last) const {
272 if (full()) {
273 return true;
274 }
275 if (first == last) {
276 return false;
277 }
278 if (first <= last - 1) {
279 uint64_t r[2] = {first, last};
280 return !_intersectsOne(r, _beginc(), _endc());
281 }
282 uint64_t r[4] = {0, last, first, 0};
283 return !_intersectsOne(r, _beginc(), _endc()) &&
284 !_intersectsOne(r + 2, _beginc(), _endc());
285}
286
287bool RangeSet::contains(RangeSet const & s) const {
288 if (s.empty() || full()) {
289 return true;
290 }
291 return !_intersects(_beginc(), _endc(), s._begin(), s._end());
292}
293
294bool RangeSet::isWithin(uint64_t first, uint64_t last) const {
295 if (empty() || first == last) {
296 return true;
297 }
298 if (last <= first - 1) {
299 uint64_t r[2] = {last, first};
300 return !_intersectsOne(r, _begin(), _end());
301 }
302 uint64_t r[4] = {0, first, last, 0};
303 return !_intersectsOne(r, _begin(), _end()) &&
304 !_intersectsOne(r + 2, _begin(), _end());
305}
306
307uint64_t RangeSet::cardinality() const {
308 uint64_t sz = 0;
309 for (auto r = _begin(), e = _end(); r != e; r += 2) {
310 sz += r[1] - r[0];
311 }
312 return sz;
313}
314
316 if (empty() || n == 0) {
317 return *this;
318 } else if (n >= 64) {
319 fill();
320 return *this;
321 }
322 // Compute m, the integer with n LSBs set to 1. Then, (x & ~m) is x
323 // rounded down to the nearest multiple of 2^n, and (x + m) & ~m is
324 // x rounded up to the nearest multiple of 2^n.
325 uint64_t const m = (static_cast<uint64_t>(1) << n) - 1;
326 uint64_t * r = const_cast<uint64_t *>(_begin());
327 uint64_t * rend = const_cast<uint64_t *>(_end());
328 uint64_t * out = r;
329 // Expand the first range.
330 uint64_t first = r[0] & ~m;
331 uint64_t last = (r[1] + m) & ~m;
332 if (r[0] != 0 && first == 0) {
333 // The expanded first range now contains the leading bookend.
334 _offset = false;
335 --out;
336 }
337 out[0] = first;
338 out[1] = last;
339 // Expand the remaining ranges.
340 for (r += 2; last != 0 && r != rend; r += 2) {
341 uint64_t u = r[0] & ~m;
342 uint64_t v = (r[1] + m) & ~m;
343 if (u > last) {
344 out += 2;
345 out[0] = u;
346 }
347 out[1] = v;
348 last = v;
349 }
350 out += 2;
351 if (last != 0) {
352 // Append a trailing bookend if necessary.
353 *out = 0;
354 ++out;
355 }
356 // Erase everything after the location of the new trailing bookend.
357 _ranges.erase(_ranges.begin() + (out - _ranges.data()), _ranges.end());
358 return *this;
359}
360
362 if (empty() || i == 1) {
363 return *this;
364 } else if (i == 0) {
365 clear();
366 return *this;
367 }
368 uint64_t overflowThreshold = static_cast<uint64_t>(-1) / i;
369 auto r = _ranges.begin();
370 auto rend = _ranges.end();
371 for (; r < rend; ++r) {
372 uint64_t value = *r;
373 if (value > overflowThreshold) {
374 *r = 0;
375 ++r;
376 break;
377 }
378 *r = value * i;
379 }
380 _ranges.erase(r, rend);
381 return *this;
382}
383
384bool RangeSet::isValid() const {
385 // Bookends are mandatory.
386 if (_ranges.size() < 2) {
387 return false;
388 }
389 if (_ranges.front() != 0 || _ranges.back() != 0) {
390 return false;
391 }
392 // Values except the last one must be monotonically increasing.
393 for (auto i = _ranges.begin() + 1, e = _ranges.end() - 1; i != e; ++i) {
394 if (i[0] <= i[-1]) {
395 return false;
396 }
397 }
398 return true;
399}
400
401void RangeSet::_insert(uint64_t first, uint64_t last) {
402 // First, check if this set is empty, or if [first, last) extends
403 // or comes after the last range in this set.
404 //
405 // It is assumed that first <= last - 1; that is, first and last
406 // do not correspond to a full range, or one that wraps.
407 uint64_t * r = const_cast<uint64_t *>(_begin());
408 uint64_t * rend = const_cast<uint64_t *>(_end());
409 if (r == rend) {
410 // This set is empty.
411 uint64_t array[4] = {0, first, last, 0};
412 _ranges.assign(array + (first == 0), array + (4 - (last == 0)));
413 _offset = (first != 0);
414 } else if (first >= rend[-2]) {
415 if (rend[-1] != 0) {
416 if (first <= rend[-1]) {
417 // [first, last) extends the last range in this set.
418 rend[-1] = std::max(last - 1, rend[-1] - 1) + 1;
419 if (last == 0) {
420 _ranges.pop_back();
421 }
422 } else {
423 // [first, last) follows the last range in this set.
424 rend[0] = first;
425 _ranges.push_back(last);
426 if (last != 0) {
427 _ranges.push_back(0);
428 }
429 }
430 }
431 } else {
432 // Find a, the first range with end point a[1] >= first, and b,
433 // the first range with beginning point b[0] > last.
434 uint64_t * a;
435 uint64_t * b;
436 if (first == 0) {
437 a = r;
438 } else {
439 // Subtract one from values before comparisons so that the
440 // trailing zero bookend is ordered properly.
441 a = std::lower_bound(RangeIter(r + 1), RangeIter(rend + 1), first,
442 [](uint64_t u, uint64_t v) {
443 return u - 1 < v - 1;
444 }).ptr - 1;
445 }
446 if (last == 0) {
447 b = rend;
448 } else {
449 b = std::upper_bound(RangeIter(a), RangeIter(rend), last).ptr;
450 }
451 // Perform the insert. Inserts involving a leading or trailing bookend
452 // are special cased.
453 if (first == 0) {
454 _offset = false;
455 if (b == r) {
456 _ranges.insert(_ranges.begin() + (r - _ranges.data()), last);
457 } else {
458 --b;
459 *b = std::max(last - 1, *b - 1) + 1;
460 _ranges.erase(_ranges.begin() + 1,
461 _ranges.begin() + (b - _ranges.data()));
462 }
463 } else if (last == 0) {
464 *a = std::min(first, *a);
465 ++a;
466 _ranges.erase(_ranges.begin() + (a - _ranges.data()),
467 _ranges.end() - 1);
468 } else {
469 if (a == b) {
470 _ranges.insert(_ranges.begin() + (a - _ranges.data()),
471 {first, last});
472 } else {
473 --b;
474 *b = std::max(last - 1, *b - 1) + 1;
475 *a = std::min(first, *a);
476 ++a;
477 _ranges.erase(_ranges.begin() + (a - _ranges.data()),
478 _ranges.begin() + (b - _ranges.data()));
479 }
480 }
481 }
482}
483
486void RangeSet::_intersectOne(std::vector<uint64_t> & v,
487 uint64_t const * a,
488 uint64_t const * b,
489 uint64_t const * bend)
490{
491 // The range B = [b[0], bend[-1]) contains all the ranges
492 // [b[0], b[1]), ... , [bend[-2], bend[-1]). If [a[0], a[1])
493 // does not intersect B, it does not intersect any of them.
494 //
495 // Note that one is subtracted from range end-points prior to
496 // comparison - otherwise, trailing zero bookends would not be
497 // ordered properly with respect to other values.
498 if (a[0] > bend[-1] - 1 || a[1] - 1 < b[0]) {
499 return;
500 }
501 if (b + 2 == bend) {
502 // Output the intersection of the ranges pointed to by a and b.
503 uint64_t u = std::max(a[0], b[0]);
504 if (u != 0) {
505 v.push_back(u);
506 }
507 v.push_back(std::min(a[1] - 1, b[1] - 1) + 1);
508 } else if (a[0] <= b[0] && a[1] - 1 >= bend[-1] - 1) {
509 // [a[0], a[1]) contains [b[0], bend[-1]), so it contains
510 // [b[0], b[1]), [b[2], b[3]), ... , [bend[-2], bend[-1]).
511 v.insert(v.end(), b + (b[0] == 0), bend);
512 } else {
513 // Divide and conquer - split the list of ranges pointed
514 // to by b in half and recurse.
515 uint64_t const * bmid = b + roundUpToEven((bend - b) >> 1);
516 _intersectOne(v, a, b, bmid);
517 _intersectOne(v, a, bmid, bend);
518 }
519}
520
523void RangeSet::_intersect(std::vector<uint64_t> & v,
524 uint64_t const * a,
525 uint64_t const * aend,
526 uint64_t const * b,
527 uint64_t const * bend)
528{
529 // The range A = [a[0], aend[-1]) contains all the ranges
530 // [a[0], a[1]), ... , [aend[-2], aend[-1]), and similarly,
531 // B = [b[0], bend[-1]) contains all the ranges pointed to by b.
532 // A and B must intersect if any of the ranges pointed to by
533 // a and b do, so if A and B are disjoint there is nothing to do.
534 //
535 // Note that one is subtracted from range end-points prior to
536 // comparison - otherwise, trailing zero bookends would not be
537 // ordered properly with respect to other values.
538 if (a + 2 == aend) {
539 _intersectOne(v, a, b, bend);
540 } else if (b + 2 == bend) {
541 _intersectOne(v, b, a, aend);
542 } else if (a[0] <= bend[-1] - 1 && aend[-1] - 1 >= b[0]) {
543 // Divide and conquer - split the lists of ranges pointed to by a and b
544 // in half and recurse. This is a depth first dual-tree traversal of
545 // implicit balanced binary trees, where a sorted list of ranges forms
546 // the bottom level of a tree, and level N - 1 is obtained from level N
547 // by joining adjacent ranges.
548 //
549 // Note that the order of the recursive calls matters -
550 // output must be generated in sorted order.
551 uint64_t const * amid = a + roundUpToEven((aend - a) >> 1);
552 uint64_t const * bmid = b + roundUpToEven((bend - b) >> 1);
553 _intersect(v, a, amid, b, bmid);
554 _intersect(v, a, amid, bmid, bend);
555 _intersect(v, amid, aend, b, bmid);
556 _intersect(v, amid, aend, bmid, bend);
557 }
558}
559
560void RangeSet::_intersect(uint64_t const * a,
561 uint64_t const * aend,
562 uint64_t const * b,
563 uint64_t const * bend)
564{
565 if (a == aend || b == bend) {
566 clear();
567 } else {
568 // Start with a vector containing just the leading bookend.
569 _ranges = {0};
570 // If both a and b contain 0, their intersection contains 0,
571 // and _offset must be 0 (false).
572 _offset = ((*a != 0) || (*b != 0));
573 // Compute the intersection and append a trailing bookend if necessary.
574 _intersect(_ranges, a, aend, b, bend);
575 if ((aend[-1] != 0) || (bend[-1] != 0)) {
576 _ranges.push_back(0);
577 }
578 }
579}
580
583bool RangeSet::_intersectsOne(uint64_t const * a,
584 uint64_t const * b,
585 uint64_t const * bend)
586{
587 // See the comments in _intersectOne for an explanation.
588 if (a[0] > bend[-1] - 1 || a[1] - 1 < b[0]) {
589 return false;
590 }
591 if (b + 2 == bend || a[0] <= b[0] || a[1] - 1 >= bend[-1] - 1) {
592 return true;
593 }
594 uint64_t const * bmid = b + roundUpToEven((bend - b) >> 1);
595 return _intersectsOne(a, b, bmid) || _intersectsOne(a, bmid, bend);
596}
597
600bool RangeSet::_intersects(uint64_t const * a,
601 uint64_t const * aend,
602 uint64_t const * b,
603 uint64_t const * bend)
604{
605 // See the comments in _intersect for an explanation.
606 if (a + 2 == aend) {
607 return _intersectsOne(a, b, bend);
608 }
609 if (b + 2 == bend) {
610 return _intersectsOne(b, a, aend);
611 }
612 if (a[0] > bend[-1] - 1 || aend[-1] - 1 < b[0]) {
613 return false;
614 }
615 uint64_t const * amid = a + roundUpToEven((aend - a) >> 1);
616 uint64_t const * bmid = b + roundUpToEven((bend - b) >> 1);
617 return _intersects(a, amid, b, bmid) ||
618 _intersects(a, amid, bmid, bend) ||
619 _intersects(amid, aend, b, bmid) ||
620 _intersects(amid, aend, bmid, bend);
621}
622
624 os << "{\"RangeSet\": [";
625 bool first = true;
626 for (auto const & t: s) {
627 if (!first) {
628 os << ", ";
629 }
630 first = false;
631 os << '[' << std::get<0>(t) << ", " << std::get<1>(t) << ']';
632 }
633 os << "]}";
634 return os;
635}
636
637}} // namespace lsst::sphgeom
py::object result
Definition _schema.cc:429
int end
uint64_t * ptr
Definition RangeSet.cc:95
This file provides a type for representing integer sets.
std::ostream * os
Definition Schema.cc:557
int m
Definition SpanSet.cc:48
table::Key< int > b
table::Key< int > a
T assign(T... args)
T back(T... args)
T begin(T... args)
A RangeSet is a set of unsigned 64 bit integers.
Definition RangeSet.h:106
RangeSet intersection(RangeSet const &s) const
intersection returns the intersection of this set and s.
Definition RangeSet.cc:142
bool intersects(uint64_t u) const
Definition RangeSet.h:432
void clear()
clear removes all integers from this set.
Definition RangeSet.h:508
bool isValid() const
isValid checks that this RangeSet is in a valid state.
Definition RangeSet.cc:384
bool isWithin(uint64_t u) const
Definition RangeSet.h:452
void insert(uint64_t u)
Definition RangeSet.h:292
bool full() const
full checks whether all integers in the universe of range sets, [0, 2^64), are in this set.
Definition RangeSet.h:518
bool contains(uint64_t u) const
Definition RangeSet.h:442
RangeSet join(RangeSet const &s) const
join returns the union of this set and s.
Definition RangeSet.cc:152
RangeSet & scale(uint64_t i)
scale multiplies the endpoints of each range in this set by the given integer.
Definition RangeSet.cc:361
bool empty() const
empty checks whether there are any integers in this set.
Definition RangeSet.h:514
RangeSet()=default
The default constructor creates an empty set.
void fill()
fill adds all the unsigned 64 bit integers to this set.
Definition RangeSet.h:511
void erase(uint64_t u)
Definition RangeSet.h:313
RangeSet difference(RangeSet const &s) const
difference returns the difference between this set and s.
Definition RangeSet.cc:164
RangeSet & simplify(uint32_t n)
simplify simplifies this range set by "coarsening" its ranges.
Definition RangeSet.cc:315
uint64_t cardinality() const
cardinality returns the number of integers in this set.
Definition RangeSet.cc:307
RangeSet symmetricDifference(RangeSet const &s) const
symmetricDifference returns the symmetric difference of this set and s.
Definition RangeSet.cc:173
T data(T... args)
T end(T... args)
T erase(T... args)
daf::base::PropertyList * list
Definition fits.cc:932
daf::base::PropertySet * set
Definition fits.cc:931
T front(T... args)
T insert(T... args)
T lower_bound(T... args)
T max(T... args)
T min(T... args)
std::shared_ptr< Image< PixelT > > operator+(Image< PixelT > const &img, ImageSlice< PixelT > const &slc)
Overload operator+()
Definition ImageSlice.cc:69
Image< LhsPixelT > & operator+=(Image< LhsPixelT > &lhs, Image< RhsPixelT > const &rhs)
Add lhs to Image rhs (i.e. pixel-by-pixel addition) where types are different.
Definition Image.cc:658
Image< LhsPixelT > & operator-=(Image< LhsPixelT > &lhs, Image< RhsPixelT > const &rhs)
Subtract lhs from Image rhs (i.e. pixel-by-pixel subtraction) where types are different.
Definition Image.cc:664
std::shared_ptr< Image< PixelT > > operator-(Image< PixelT > const &img, ImageSlice< PixelT > const &slc)
Overload operator-()
Definition ImageSlice.cc:89
void swap(RangeSet &a, RangeSet &b)
Definition RangeSet.h:615
std::ostream & operator<<(std::ostream &, Angle const &)
Definition Angle.cc:41
Angle operator*(double a, Angle const &b)
Definition Angle.h:105
T operator!=(T... args)
T pop_back(T... args)
T push_back(T... args)
T reserve(T... args)
T size(T... args)
T swap(T... args)
T upper_bound(T... args)