Skip to content

Commit 59afca4

Browse files
pbuehlerpbuehler
authored
Data structure to hold and manipulate a list of BC ranges (#8423)
* BCRanges is a structure to hold a list of BC ranges * Include BCRange.h in CMakeLists.txt * Introduced using limits = o2::dataformats::Pair<uint64_t, uint64_t>; * clang-format
1 parent 076d8f6 commit 59afca4

2 files changed

Lines changed: 221 additions & 0 deletions

File tree

‎DataFormats/Reconstruction/CMakeLists.txt‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -59,6 +59,7 @@ o2_target_root_dictionary(
5959
include/ReconstructionDataFormats/TrackCosmics.h
6060
include/ReconstructionDataFormats/TrackMCHMID.h
6161
include/ReconstructionDataFormats/MatchInfoFwd.h
62+
include/ReconstructionDataFormats/BCRange.h
6263
)
6364

6465
o2_add_test(Vertex

‎DataFormats/Reconstruction/include/ReconstructionDataFormats/BCRange.h‎

Lines changed: 220 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,220 @@
1+
// Copyright 2019-2020 CERN and copyright holders of ALICE O2.
2+
// See https://alice-o2.web.cern.ch/copyright for details of the copyright holders.
3+
// All rights not expressly granted are reserved.
4+
//
5+
// This software is distributed under the terms of the GNU General Public
6+
// License v3 (GPL Version 3), copied verbatim in the file "COPYING".
7+
//
8+
// In applying this license CERN does not waive the privileges and immunities
9+
// granted to it by virtue of its status as an Intergovernmental Organization
10+
// or submit itself to any jurisdiction.
11+
#ifndef ALICEO2_BCRANGE_H
12+
#define ALICEO2_BCRANGE_H
13+
14+
#include "CommonDataFormat/Pair.h"
15+
16+
namespace o2
17+
{
18+
namespace dataformats
19+
{
20+
// .............................................................................
21+
struct bcRanges {
22+
23+
using limits = o2::dataformats::Pair<uint64_t, uint64_t>;
24+
25+
// members
26+
const char* mlistName;
27+
std::vector<limits> mbcRangesList;
28+
bool isSorted;
29+
bool isMerged;
30+
bool isExtended;
31+
32+
public:
33+
// constructor
34+
bcRanges(const char* label)
35+
{
36+
mlistName = label;
37+
reset();
38+
}
39+
40+
// reset list
41+
void reset()
42+
{
43+
isSorted = false;
44+
isMerged = false;
45+
isExtended = false;
46+
mbcRangesList.clear();
47+
}
48+
49+
char status()
50+
{
51+
return isSorted * (1 << 0) + isMerged * (1 << 1) + isExtended * (1 << 2);
52+
}
53+
54+
// return number of BC ranges in list
55+
auto size()
56+
{
57+
return mbcRangesList.size();
58+
}
59+
60+
// add BC range
61+
void add(uint64_t first, uint64_t last)
62+
{
63+
mbcRangesList.push_back(limits(first, last));
64+
isSorted = false;
65+
isMerged = false;
66+
isExtended = false;
67+
}
68+
69+
// sort mbcRangesList according to first entries
70+
void sort()
71+
{
72+
std::sort(mbcRangesList.begin(), mbcRangesList.end(), [](limits a, limits b) {
73+
return a.first < b.first;
74+
});
75+
isSorted = true;
76+
}
77+
78+
// get number of BCs not included in ranges
79+
template <typename BCs>
80+
uint64_t getnNotCompBCs(BCs bcs)
81+
{
82+
// needs to be merged
83+
if (!isMerged) {
84+
merge();
85+
}
86+
87+
// loop over ranges and count number of BCs not contained in a range
88+
uint64_t nNotCompBCs = 0;
89+
uint64_t ilast = 1, inext;
90+
for (auto iter = mbcRangesList.begin(); iter != mbcRangesList.end(); ++iter) {
91+
inext = iter->first;
92+
if (iter == mbcRangesList.begin()) {
93+
nNotCompBCs += (inext - ilast);
94+
} else {
95+
nNotCompBCs += (inext - ilast - 1);
96+
}
97+
ilast = iter->second;
98+
}
99+
auto bclast = bcs.rawIteratorAt(bcs.size());
100+
nNotCompBCs += (bclast.globalIndex() - ilast);
101+
LOGF(debug, "Number of BCs not in range of compatible BCs: %i", nNotCompBCs);
102+
103+
return nNotCompBCs;
104+
}
105+
106+
// merge overlaping ranges
107+
void merge(bool toForce = false)
108+
{
109+
if (!isMerged || toForce) {
110+
std::vector<limits> tmpList;
111+
uint64_t ifirst = 0, ilast;
112+
113+
// apply sorting of the ranges
114+
if (!isSorted) {
115+
sort();
116+
}
117+
118+
// run over elements of mbcRangesList and merge lines where possible
119+
for (auto iter = mbcRangesList.begin(); iter != mbcRangesList.end(); ++iter) {
120+
if (iter == mbcRangesList.begin()) {
121+
ifirst = iter->first;
122+
ilast = iter->second;
123+
continue;
124+
}
125+
126+
if (iter->first > (ilast + 1)) {
127+
// update tmpList
128+
tmpList.push_back(limits(ifirst, ilast));
129+
ifirst = iter->first;
130+
ilast = iter->second;
131+
} else {
132+
if (iter->second > ilast) {
133+
ilast = iter->second;
134+
}
135+
}
136+
}
137+
tmpList.push_back(limits(ifirst, ilast));
138+
139+
mbcRangesList.clear();
140+
mbcRangesList = tmpList;
141+
isMerged = true;
142+
}
143+
}
144+
145+
// add a factor fillFac of BCs not yet included in the BC ranges
146+
template <typename BCs>
147+
void compact(BCs bcs, Double_t fillFac, bool toForce = false)
148+
{
149+
if (!isExtended || toForce) {
150+
// apply merging of the ranges
151+
if (!isMerged || toForce) {
152+
merge(toForce);
153+
}
154+
155+
// find out number of BCs not in a compatible range
156+
auto nBCs = bcs.size();
157+
auto nNotCompBCs = getnNotCompBCs(bcs);
158+
159+
// keep adding BCs until the required number has been added
160+
auto nToAdd = (uint64_t)(nNotCompBCs * fillFac);
161+
int cnt = 0;
162+
while (nToAdd > 0) {
163+
// add BC at the beginning
164+
if (mbcRangesList[0].first > 1) {
165+
mbcRangesList[0].first--;
166+
nToAdd--;
167+
}
168+
169+
// number of BCs to add in this round
170+
auto nr = mbcRangesList.size();
171+
if (nr > nToAdd) {
172+
nr = nToAdd;
173+
}
174+
175+
// add BC after each range
176+
for (auto ii = 0; ii < nr; ii++) {
177+
if (mbcRangesList[ii].second < nBCs) {
178+
mbcRangesList[ii].second++;
179+
nToAdd--;
180+
}
181+
}
182+
merge(true);
183+
}
184+
isExtended = true;
185+
}
186+
}
187+
188+
// get BC range
189+
auto operator[](int index)
190+
{
191+
return mbcRangesList[index];
192+
}
193+
auto begin()
194+
{
195+
return mbcRangesList.begin();
196+
}
197+
auto end()
198+
{
199+
return mbcRangesList.end();
200+
}
201+
202+
// return list name
203+
auto name()
204+
{
205+
return mlistName;
206+
}
207+
208+
// return the list
209+
auto list()
210+
{
211+
return mbcRangesList;
212+
}
213+
};
214+
215+
// .............................................................................
216+
} // namespace dataformats
217+
218+
} // namespace o2
219+
220+
#endif // ALICEO2__BCRANGE_H

0 commit comments

Comments
 (0)