LArSoft  v09_90_00
Liquid Argon Software toolkit - https://larsoft.org/
RangeSet.cc
Go to the documentation of this file.
2 // vim: set sw=2 expandtab :
3 
10 #include "cetlib/container_algorithms.h"
11 #include "cetlib/crc32.h"
12 
13 #include <algorithm>
14 #include <cstddef>
15 #include <ostream>
16 #include <string>
17 #include <utility>
18 #include <vector>
19 
20 using namespace std;
21 
22 namespace art {
23 
24  namespace {
25 
26  bool
27  disjoint(vector<EventRange> const& ranges)
28  {
29  if (ranges.size() < 2ull) {
30  return true;
31  }
32  auto it = ranges.cbegin();
33  auto const end = ranges.cend();
34  for (auto nxt = next(it); nxt != end; ++it, ++nxt) {
35  if (!it->is_disjoint(*nxt)) {
36  return false;
37  }
38  }
39  return true;
40  }
41 
42  } // unnamed namespace
43 
44  RangeSet
45  RangeSet::invalid()
46  {
47  return RangeSet{};
48  }
49 
50  RangeSet
51  RangeSet::forRun(RunID const rid)
52  {
53  return RangeSet{rid.run(), {detail::full_run_event_range()}};
54  }
55 
56  RangeSet
57  RangeSet::forSubRun(SubRunID const srid)
58  {
59  return RangeSet{srid.run(), {EventRange::forSubRun(srid.subRun())}};
60  }
61 
62  // The special member functions cannot be noexcept because ranges_
63  // is a vector.
64  RangeSet::~RangeSet() = default;
65  RangeSet::RangeSet() = default;
66  RangeSet::RangeSet(RangeSet const& rhs) = default;
67  RangeSet::RangeSet(RangeSet&& rhs) = default;
68  RangeSet& RangeSet::operator=(RangeSet const& rhs) = default;
69  RangeSet& RangeSet::operator=(RangeSet&& rhs) = default;
70 
71  RangeSet::RangeSet(RunNumber_t const r) : RangeSet{r, {}} {}
72 
73  RangeSet::RangeSet(RunNumber_t const r, vector<EventRange> const& eventRanges)
74  : run_{r}, ranges_{eventRanges}
75  {
76  sort();
77  collapse();
78  }
79 
82  {
83  static EventRange const range{
85  return range;
86  }
87 
89  RangeSet::run() const
90  {
91  return run_;
92  }
93 
94  vector<EventRange> const&
96  {
97  return ranges_;
98  }
99 
100  bool
102  SubRunNumber_t const s,
103  EventNumber_t const e) const
104  {
105  if (run_ != r) {
106  return false;
107  }
108  for (auto const& range : ranges_) {
109  if (range.contains(s, e)) {
110  return true;
111  }
112  }
113  return false;
114  }
115 
116  bool
118  {
120  }
121 
122  bool
124  {
125  return ranges_.size() == 1ull &&
127  }
128 
129  bool
131  {
132  return (ranges_.size() == 1ull) && ranges_.front().is_full_subRun();
133  }
134 
135  bool
137  {
138  return std::is_sorted(ranges_.cbegin(), ranges_.cend());
139  }
140 
141  bool
143  {
144  return isCollapsed_;
145  }
146 
147  string
149  {
150  using namespace std;
151  string s{to_string(run_)};
152  if (!ranges_.empty()) {
153  s += ":";
154  }
155  for (auto const& r : ranges_) {
156  s += to_string(r.subRun());
157  s += "[";
158  s += to_string(r.begin());
159  s += ",";
160  s += to_string(r.end());
161  s += ")";
162  }
163  return s;
164  }
165 
166  bool
168  {
169  if (isCollapsed_ || is_sorted()) {
170  return (ranges_.size() < 2ull) ? true : disjoint(ranges_);
171  }
172  RangeSet tmp{*this};
173  tmp.sort();
174  tmp.collapse();
175  return tmp.has_disjoint_ranges();
176  }
177 
178  bool
180  {
181  for (auto const& range : ranges_) {
182  if (!range.empty())
183  return false;
184  }
185  return true;
186  }
187 
188  size_t
190  {
191  return 0;
192  }
193 
194  size_t
196  {
197  return static_cast<size_t>(ranges_.cend() - ranges_.cbegin());
198  }
199 
202  {
203  return ranges_.cbegin();
204  }
205 
208  {
209  return ranges_.cend();
210  }
211 
212  unsigned
214  {
215  // Could cache checksums to improve performance when necessary.
216  return checksum_ = cet::crc32{to_compact_string()}.digest();
217  }
218 
219  size_t
221  {
222  if (b == end_idx()) {
223  return end_idx();
224  }
225  auto const sr = ranges_.at(b).subRun();
226  auto pos =
227  find_if(ranges_.cbegin() + b, ranges_.cend(), [sr](auto const& range) {
228  return range.subRun() != sr;
229  });
230  return static_cast<size_t>(pos - ranges_.cbegin());
231  }
232 
233  EventRange&
235  {
236  return ranges_.front();
237  }
238 
239  EventRange&
241  {
242  return ranges_.back();
243  }
244 
245  EventRange&
246  RangeSet::at(size_t idx)
247  {
248  return ranges_.at(idx);
249  }
250 
251  vector<EventRange>
252  RangeSet::extract_ranges(size_t const b, size_t const e)
253  {
254  vector<EventRange> result;
255  if (!ranges_.empty() && (e >= 1) && (e <= ranges_.size())) {
256  copy(ranges_.cbegin() + b, ranges_.cbegin() + e, back_inserter(result));
257  }
258  return result;
259  }
260 
261  RangeSet&
263  {
264  if (isCollapsed_) {
265  return *this;
266  }
267  if (ranges_.size() < 2) {
268  isCollapsed_ = true;
269  return *this;
270  }
271  if (!is_sorted())
272  throw art::Exception(art::errors::LogicError, "RangeSet::collapse()")
273  << "A range set must be sorted before it is collapsed.\n";
274 
275  auto processing = ranges_;
276  decltype(ranges_) result;
277  result.reserve(ranges_.size());
278  result.push_back(ranges_.front());
279  for (auto ir = ranges_.cbegin() + 1, e = ranges_.cend(); ir != e; ++ir) {
280  auto const& r = *ir;
281  auto& back = result.back();
282  if (back.is_adjacent(r)) {
283  back.merge(r);
284  } else {
286  result.push_back(r);
287  }
288  }
289  std::swap(ranges_, result);
290  isCollapsed_ = true;
291  return *this;
292  }
293 
294  RangeSet&
296  {
297  if (!other.is_valid()) {
298  return *this;
299  }
300  if (!is_valid()) {
301  run_ = other.run();
302  }
303  vector<EventRange> merged;
304  std::merge(ranges_.cbegin(),
305  ranges_.cend(),
306  other.ranges_.cbegin(),
307  other.ranges_.cend(),
308  back_inserter(merged));
309  unique(merged.begin(), merged.end());
310  std::swap(ranges_, merged);
311  isCollapsed_ = false;
312  collapse();
313  return *this;
314  }
315 
316  void
317  RangeSet::assign_ranges(RangeSet const& rs, size_t const b, size_t const e)
318  {
320  if (!rs.ranges_.empty() && (e >= 1) && (e <= rs.ranges_.size())) {
321  ranges_.assign(rs.ranges_.cbegin() + b, rs.ranges_.cbegin() + e);
322  }
323  }
324 
325  void
327  {
329  if (ranges_.empty()) {
330  run_ = id.run();
331  ranges_.emplace_back(id.subRun(), id.event(), id.next().event());
332  return;
333  }
334  auto& back = ranges_.back();
335  if (back.subRun() == id.subRun() && back.end() == id.event()) {
336  back.set_end(id.next().event());
337  } else {
338  ranges_.emplace_back(id.subRun(), id.event(), id.next().event());
339  }
340  }
341 
342  // For a range [1,6) split into [1,3) and [3,6) the specified
343  // event number is the new 'end' of the left range (3).
344  pair<std::size_t, bool>
346  {
348  bool did_split = false;
349  auto result = ranges_.end();
350  auto foundRange =
351  find_if(ranges_.cbegin(), ranges_.cend(), [s, e](auto const& r) {
352  return r.contains(s, e);
353  });
354  // Split only if:
355  // - the range is found (i.e. the event is contained by the found range)
356  // - the range is valid
357  // - the size of the range is greater than 1
358  if ((foundRange != ranges_.cend()) && foundRange->is_valid() &&
359  (foundRange->size() > 1ull)) {
360  auto const begin = foundRange->begin();
361  auto const end = foundRange->end();
362  auto leftIt = ranges_.emplace(foundRange, s, begin, e);
363  result = next(leftIt);
364  EventRange right{s, e, end};
365  std::swap(*result, right);
366  did_split = true;
367  }
368  return make_pair(static_cast<size_t>(result - ranges_.cbegin()), did_split);
369  }
370 
371  void
373  {
374  run_ = r;
375  }
376 
377  void
379  {
380  cet::sort_all(ranges_);
381  }
382 
383  void
385  {
386  ranges_.clear();
387  }
388 
389  void
391  {
392  if (is_full_run()) {
393  throw Exception(errors::LogicError, "RangeSet::require_not_full_run")
394  << "\nA RangeSet created using RangeSet::forRun cannot be modified.\n";
395  }
396  }
397 
398  bool
399  operator==(RangeSet const& l, RangeSet const& r)
400  {
401  if (!(l.is_valid() && r.is_valid())) {
402  return false;
403  }
404  return (l.run() == r.run()) && (l.ranges() == r.ranges());
405  }
406 
407  bool
408  same_ranges(RangeSet const& l, RangeSet const& r)
409  {
410  return l == r;
411  }
412 
413  bool
414  disjoint_ranges(RangeSet const& l, RangeSet const& r)
415  {
416  if (!(l.is_valid() && r.is_valid())) {
417  return false;
418  }
419  if (!l.has_disjoint_ranges() || !r.has_disjoint_ranges())
420  return false;
421 
422  if (l.run() != r.run())
423  return true;
424 
425  // If we get here, the run numbers of both ranges are guaranteed to
426  // be the same.
427 
428  // Empty RangeSets are disjoint wrt. other RangeSets. Must handle
429  // this case separately than l == r case.
430  if (l.empty() || r.empty())
431  return true;
432 
433  // If we get this far, then neither RangeSet is empty.
434  if (l == r)
435  return false;
436 
437  RangeSet ltmp{l};
438  RangeSet rtmp{r};
439  auto const& lranges = ltmp.collapse().ranges();
440  auto const& rranges = rtmp.collapse().ranges();
441 
442  std::vector<EventRange> merged;
443  std::merge(lranges.begin(),
444  lranges.end(),
445  rranges.begin(),
446  rranges.end(),
447  back_inserter(merged));
448 
449  return disjoint(merged);
450  }
451 
452  void
454  EventRange const& left,
455  EventRange const& right) noexcept(false)
456  {
457  if (left.is_disjoint(right))
458  return;
460  << "Attempt to merge event ranges that both contain one or more of the "
461  "same events\n"
462  << " Run: " << rn << '\n'
463  << " " << left << " vs.\n"
464  << " " << right << '\n';
465  }
466 
467  bool
469  {
470  if (!(l.is_valid() && r.is_valid())) {
471  return false;
472  }
473  return !disjoint_ranges(l, r);
474  }
475 
476  ostream&
477  operator<<(ostream& os, RangeSet const& rs)
478  {
479  os << " Run: " << rs.run();
480  if (rs.is_full_run()) {
481  os << " (full run)";
482  return os;
483  }
484  for (auto const& er : rs.ranges()) {
485  os << "\n " << er;
486  }
487  return os;
488  }
489 
490 } // namespace art
RunNumber_t run_
Definition: RangeSet.h:110
TRandom r
Definition: spectrum.C:23
bool operator==(Provenance const &a, Provenance const &b) noexcept
Definition: Provenance.cc:141
void set_end(EventNumber_t const e)
Definition: EventRange.cc:213
std::pair< std::size_t, bool > split_range(SubRunNumber_t, EventNumber_t)
Definition: RangeSet.cc:345
constexpr auto const & right(const_AssnsIter< L, R, D, Dir > const &a, const_AssnsIter< L, R, D, Dir > const &b)
Definition: AssnsIter.h:102
void clear()
Definition: RangeSet.cc:384
std::vector< EventRange >::const_iterator const_iterator
Definition: RangeSet.h:27
bool has_disjoint_ranges() const
Definition: RangeSet.cc:167
unsigned checksum_
Definition: RangeSet.h:115
std::vector< EventRange > const & ranges() const
Definition: RangeSet.cc:95
std::enable_if_t< detail::are_handles_v< T, U >, bool > overlapping_ranges(T const &a, U const &b)
std::vector< EventRange > ranges_
Definition: RangeSet.h:111
void set_run(RunNumber_t const r)
Definition: RangeSet.cc:372
STL namespace.
EventRange full_run_event_range()
Definition: RangeSet.cc:81
Float_t tmp
Definition: plot.C:35
void assign_ranges(RangeSet const &rs, std::size_t const b, std::size_t const e)
Definition: RangeSet.cc:317
bool is_valid() const
Definition: RangeSet.cc:117
RunNumber_t run() const
Definition: RunID.h:64
bool is_sorted() const
Definition: RangeSet.cc:136
EventNumber_t end() const noexcept
Definition: EventRange.cc:111
void throw_if_not_disjoint(RunNumber_t const rn, EventRange const &left, EventRange const &right) noexcept(false)
Definition: RangeSet.cc:453
RangeSet & collapse()
Definition: RangeSet.cc:262
RunNumber_t run() const
Definition: RangeSet.cc:89
decltype(auto) constexpr end(T &&obj)
ADL-aware version of std::end.
Definition: StdUtils.h:77
std::ostream & operator<<(std::ostream &os, const GroupSelector &gs)
std::enable_if_t< detail::are_handles_v< T, U >, bool > disjoint_ranges(T const &a, U const &b)
bool is_full_run() const
Definition: RangeSet.cc:123
bool isCollapsed_
Definition: RangeSet.h:114
RunNumber_t run() const
Definition: SubRunID.h:85
std::size_t end_idx() const
Definition: RangeSet.cc:195
IDNumber_t< Level::SubRun > SubRunNumber_t
Definition: IDNumber.h:119
EventRange & front()
Definition: RangeSet.cc:234
const_iterator end() const
Definition: RangeSet.cc:207
std::vector< EventRange > extract_ranges(std::size_t const b, std::size_t const e)
Definition: RangeSet.cc:252
bool contains(RunNumber_t, SubRunNumber_t, EventNumber_t) const
Definition: RangeSet.cc:101
std::string to_compact_string() const
Definition: RangeSet.cc:148
bool empty() const
Definition: RangeSet.cc:179
cet::coded_exception< errors::ErrorCodes, ExceptionDetail::translate > Exception
Definition: Exception.h:66
constexpr auto const & left(const_AssnsIter< L, R, D, Dir > const &a, const_AssnsIter< L, R, D, Dir > const &b)
Definition: AssnsIter.h:94
void require_not_full_run()
Definition: RangeSet.cc:390
std::enable_if_t< detail::are_handles_v< T, U >, bool > same_ranges(T const &a, U const &b)
void update(EventID const &)
Definition: RangeSet.cc:326
void sort()
Definition: RangeSet.cc:378
const_iterator begin() const
Definition: RangeSet.cc:201
SubRunNumber_t subRun() const noexcept
Definition: EventRange.cc:93
IDNumber_t< Level::Event > EventNumber_t
Definition: IDNumber.h:118
void swap(lar::deep_const_fwd_iterator_nested< CITER, INNERCONTEXTRACT > &a, lar::deep_const_fwd_iterator_nested< CITER, INNERCONTEXTRACT > &b)
Definition: MVAAlg.h:12
RangeSet & merge(RangeSet const &other)
Definition: RangeSet.cc:295
bool is_full_subRun() const
Definition: RangeSet.cc:130
bool merge(EventRange const &other)
Definition: EventRange.cc:199
SubRunNumber_t subRun() const
Definition: SubRunID.h:91
EventRange & back()
Definition: RangeSet.cc:240
std::size_t next_subrun_or_end(std::size_t const b) const
Definition: RangeSet.cc:220
Float_t e
Definition: plot.C:35
bool is_adjacent(EventRange const &other) const noexcept
Definition: EventRange.cc:152
EventRange & at(std::size_t)
Definition: RangeSet.cc:246
std::string to_string(ModuleType const mt)
Definition: ModuleType.h:34
unsigned checksum() const
Definition: RangeSet.cc:213
bool is_collapsed() const
Definition: RangeSet.cc:142
Event finding and building.
std::size_t begin_idx() const
Definition: RangeSet.cc:189
IDNumber_t< Level::Run > RunNumber_t
Definition: IDNumber.h:120