Jpp test-rotations-new
the software that should make you happy
Loading...
Searching...
No Matches
JAlgorithm.hh
Go to the documentation of this file.
1#ifndef __JTRIGGER__JALGORITHM__
2#define __JTRIGGER__JALGORITHM__
3
4#include <vector>
5#include <algorithm>
6#include <iterator>
7
8
9/**
10 * \file
11 *
12 * Algorithms for hit clustering and sorting.
13 * \author mdejong
14 */
15namespace JTRIGGER {}
16namespace JPP { using namespace JTRIGGER; }
17
18namespace JTRIGGER {
19
20 /**
21 * Partition data according given binary match operator.
22 *
23 * The underlying algorithm is known in literature as 'clique'.
24 * The result is (likely to be) the maximal sub-set with all elements matched to each other.
25 * The complexity is quadratic, i.e.\ at most (number of elements x number of elements) operations.
26 * The algorithm will sort the data such that all clusterized hits are at the front.
27 * The return value points the first non clusterized hit.
28 *
29 * The hit iterator refers to a data structure which should conform with the match operator.
30 *
31 * \param __begin begin of data
32 * \param __end end of data
33 * \param match binary match operator
34 * \param Nmin minimum cluster size
35 * \return end of data
36 */
37 template<class JHitIterator_t, class JMatch_t>
38 inline JHitIterator_t clusterize(JHitIterator_t __begin,
39 JHitIterator_t __end,
40 const JMatch_t& match,
41 const int Nmin = 1)
42 {
43 using namespace std;
44
45 const int N = distance(__begin,__end);
46
47 JHitIterator_t buffer = __begin;
48
49 if (N >= Nmin) {
50
51 int i, j;
52 int n = N;
53
54 // Determine number of associated hits for each hit.
55
56 std::vector<int> count(N, 1); // Assume always a match with itself.
57
58 for (i = 0; i != N; ++i) {
59 for (j = i; ++j != N; ) {
60 if (match(buffer[i], buffer[j])) {
61 ++count[i];
62 ++count[j];
63 }
64 }
65 }
66
67 // Remove hit with the smallest number of associated hits.
68 // This procedure stops when:
69 // 1) number of associated hits is equal to the number of (remaining) hits or
70 // 2) maximal number of associated hits is less than the specified minimum.
71
72 for ( ; ; ) {
73
74 int M = (count[0] >= Nmin ? 1 : 0);
75
76 j = 0;
77
78 for (i = 1; i != n; ++i) {
79 if (count[i] < count[j]) {
80 j = i;
81 }
82 if (count[i] >= Nmin) {
83 ++M;
84 }
85 }
86
87 // Ready?
88
89 if (count[j] == n) {
90 return buffer + n;
91 }
92
93 if (M < Nmin) {
94 return buffer;
95 }
96
97 // Reduce effective size.
98
99 --n;
100
101 // Swap the selected hit to end.
102
103 swap(buffer[j], buffer[n]);
104 swap(count [j], count [n]);
105
106 // Decrease number of associated hits for each associated hit.
107
108 for (i = 0; i != n && count[n] != 1; ++i) {
109 if (match(buffer[i], buffer[n])) {
110 --count[i];
111 --count[n];
112 }
113 }
114 }
115 }
116
117 return buffer;
118 }
119
120
121 /**
122 * Select best root hit according given comparator and partition remaining data
123 * according given binary match operator and this root hit.
124 * The complexity is linear, i.e.\ at most number of elements operations.
125 * The algorithm will sort the data such that all selected hits are at the front.
126 *
127 * \param __begin begin of data
128 * \param __end end of data
129 * \param comparator comparator
130 * \param match binary match operator
131 * \return end of data
132 */
133 template<class JHitIterator_t, class JComparator_t, class JMatch_t>
134 inline JHitIterator_t clusterize(JHitIterator_t __begin,
135 JHitIterator_t __end,
136 const JComparator_t& comparator,
137 const JMatch_t& match)
138 {
139 if (__begin != __end) {
140
141 std::sort(__begin, __end, comparator);
142
143 JHitIterator_t root = __begin;
144
145 return std::partition(++__begin, __end, JBind2nd(match, *root));
146
147 } else {
148
149 return __end;
150 }
151 }
152
153
154 /**
155 * Partition data according given binary match operator.
156 *
157 * The underlying algorithm is known in literature as reverse 'clique'.
158 * The result is (likely to be) the maximal sub-set with all elements matched to each other.
159 * The complexity is quadratic, i.e.\ at most (number of elements x number of elements) operations.
160 * The algorithm will sort the data such that all clusterized hits are at the front.
161 * The return value points the first non clusterized hit.
162 *
163 * The hit iterator refers to a data structure which should conform with the match operator.
164 *
165 * \param __begin begin of data
166 * \param __end end of data
167 * \param match binary match operator
168 * \return end of data
169 */
170 template<class JHitIterator_t, class JMatch_t>
171 inline JHitIterator_t reverse_clusterize(JHitIterator_t __begin,
172 JHitIterator_t __end,
173 const JMatch_t& match)
174 {
175 using namespace std;
176
177 const int N = distance(__begin,__end);
178
179 JHitIterator_t buffer = __begin;
180
181 if (N != 0) {
182
183 int i, j;
184
185 // Determine number of associated hits for each hit.
186
187 std::vector<int> count(N, 1); // Assume always a match with itself.
188
189 for (i = 0; i != N; ++i) {
190 for (j = 0; j != i; ++j) {
191 if (match(buffer[i], buffer[j])) {
192 ++count[i];
193 ++count[j];
194 }
195 }
196 }
197
198 // Keep hit with the largest number of associated hits.
199 // This procedure stops when the number of associated hits is equal to one.
200
201 for (int n = 0; ; ++n) {
202
203 j = n;
204
205 for (i = j; ++i != N; ) {
206 if (count[i] > count[j]) {
207 j = i;
208 }
209 }
210
211 // Ready?
212
213 if (count[j] == 1) {
214 return buffer + n;
215 }
216
217 // Swap the selected hit to begin.
218
219 swap(buffer[j], buffer[n]);
220 swap(count [j], count [n]);
221
222 // Decrease number of associated hits for each associated hit.
223
224 for (i = n; ++i != N; ) {
225 if (match(buffer[i], buffer[n])) {
226 --count[i];
227 --count[n];
228 }
229 }
230 }
231 }
232
233 return buffer;
234 }
235
236
237 /**
238 * Partition data according given binary match operator.
239 *
240 * The underlying algorithm is known in literature as reverse 'clique'.
241 * The result is (likely to be) the maximal sub-set with all elements matched to each other.
242 * The complexity is quadratic, i.e.\ at most (number of elements x number of elements) operations.
243 * The algorithm will sort the data such that all clusterized hits are at the front.
244 * The return value points the first non clusterized hit.
245 * Note that the weight is assumed to be positive definite and the larger the weight the better.
246 *
247 * The hit iterator refers to a data structure which should conform with the match operator.
248 * In addition, it should have the following member method:
249 * - double %getW(); // [a.u.]
250 *
251 * \param __begin begin of data
252 * \param __end end of data
253 * \param match binary match operator
254 * \return end of data
255 */
256 template<class JHitIterator_t, class JMatch_t>
257 inline JHitIterator_t clusterizeWeight(JHitIterator_t __begin,
258 JHitIterator_t __end,
259 const JMatch_t& match)
260 {
261 using namespace std;
262
263 const int N = distance(__begin,__end);
264
265 JHitIterator_t buffer = __begin;
266
267 if (N != 0) {
268
269 int i, j;
270
271 // Determine weight of each hit.
272
273 std::vector<double> weight(N);
274
275 for (i = 0; i != N; ++i) {
276 weight[i] = buffer[i].getW(); // Assume always a match with itself.
277 }
278
279 for (i = 0; i != N; ++i) {
280 for (j = i; ++j != N; ) {
281 if (match(buffer[i], buffer[j])) {
282 weight[i] += buffer[j].getW();
283 weight[j] += buffer[i].getW();
284 }
285 }
286 }
287
288 // Remove hit with the smallest weight of associated hits.
289 // This procedure stops when the weight of associated hits
290 // is equal to the maximal weight of (remaining) hits.
291
292 int n = N;
293 double W;
294
295 for ( ; ; ) {
296
297 j = 0;
298 W = weight[j];
299
300 for (i = 1; i != n; ++i) {
301 if (weight[i] < weight[j])
302 j = i;
303 else if (weight[i] > W)
304 W = weight[i];
305 }
306
307 // Ready?
308
309 if (weight[j] == W) {
310 return buffer + n;
311 }
312
313 // Reduce effective size.
314
315 --n;
316
317 // Swap the selected hit to end.
318
319 swap(buffer[j], buffer[n]);
320 swap(weight[j], weight[n]);
321
322 // Decrease weight of associated hits for each associated hit.
323
324 for (i = 0; i != n && weight[n] > buffer[n].getW(); ++i) {
325 if (match(buffer[i], buffer[n])) {
326 weight[i] -= buffer[n].getW();
327 weight[n] -= buffer[i].getW();
328 }
329 }
330 }
331 }
332
333 return buffer;
334 }
335
336
337 /**
338 * Compare two hits by weight.
339 *
340 * The template argument <tt>JHit_t</tt> refers to a data structure which should have the following member method:
341 * - double %getW(); // [a.u.]
342 *
343 * \param first first hit
344 * \param second second hit
345 * \return true if first hit has larger weight than second; else false
346 */
347 template<class JHit_t>
348 inline bool weightSorter(const JHit_t& first, const JHit_t& second)
349 {
350 return first.getW() > second.getW();
351 }
352
353
354 /**
355 * Compare two hits by weight.
356 *
357 * The template argument <tt>JHit_t</tt> refers to a data structure which should have the following member methods:
358 * - double %getT(); // [a.u.]
359 *
360 * \param first first hit
361 * \param second second hit
362 * \return true if first hit earlier than second; else false
363 */
364 template<class JHit_t>
365 inline bool timeSorter(const JHit_t& first, const JHit_t& second)
366 {
367 return first.getT() < second.getT();
368 }
369}
370
371#endif
std::vector< T >::difference_type distance(typename std::vector< T >::const_iterator first, typename PhysicsEvent::const_iterator< T > second)
Specialisation of STL distance.
This name space includes all other name spaces (except KM3NETDAQ, KM3NET and ANTARES).
Auxiliary classes and methods for triggering.
JBinder2nd< JHit_t > JBind2nd(const JMatch< JHit_t > &match, const JHit_t &second)
Auxiliary method to create JBinder2nd object.
Definition JBind2nd.hh:66
JHitIterator_t clusterize(JHitIterator_t __begin, JHitIterator_t __end, const JMatch_t &match, const int Nmin=1)
Partition data according given binary match operator.
Definition JAlgorithm.hh:38
JHitIterator_t reverse_clusterize(JHitIterator_t __begin, JHitIterator_t __end, const JMatch_t &match)
Partition data according given binary match operator.
JHitIterator_t clusterizeWeight(JHitIterator_t __begin, JHitIterator_t __end, const JMatch_t &match)
Partition data according given binary match operator.
bool weightSorter(const JHit_t &first, const JHit_t &second)
Compare two hits by weight.
bool timeSorter(const JHit_t &first, const JHit_t &second)
Compare two hits by weight.
Definition root.py:1