]>
Commit | Line | Data |
---|---|---|
370be031 | 1 | //STARTHEADER |
2 | // $Id: ClusterSequence.hh 1435 2009-02-12 21:11:04Z salam $ | |
3 | // | |
4 | // Copyright (c) 2005-2006, Matteo Cacciari and Gavin Salam | |
5 | // | |
6 | //---------------------------------------------------------------------- | |
7 | // This file is part of FastJet. | |
8 | // | |
9 | // FastJet is free software; you can redistribute it and/or modify | |
10 | // it under the terms of the GNU General Public License as published by | |
11 | // the Free Software Foundation; either version 2 of the License, or | |
12 | // (at your option) any later version. | |
13 | // | |
14 | // The algorithms that underlie FastJet have required considerable | |
15 | // development and are described in hep-ph/0512210. If you use | |
16 | // FastJet as part of work towards a scientific publication, please | |
17 | // include a citation to the FastJet paper. | |
18 | // | |
19 | // FastJet is distributed in the hope that it will be useful, | |
20 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
21 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
22 | // GNU General Public License for more details. | |
23 | // | |
24 | // You should have received a copy of the GNU General Public License | |
25 | // along with FastJet; if not, write to the Free Software | |
26 | // Foundation, Inc.: | |
27 | // 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
28 | //---------------------------------------------------------------------- | |
29 | //ENDHEADER | |
30 | ||
31 | ||
32 | //---------------------------------------------------------------------- | |
33 | // here's where we put the main page for fastjet (as explained in the | |
34 | // Doxygen faq) | |
35 | //...................................................................... | |
36 | /*! \mainpage FastJet code documentation | |
37 | * | |
38 | * These pages provide automatically generated documentation for the | |
39 | * FastJet package. | |
40 | * | |
41 | * For further information and normal documentation, see the main <a | |
42 | * href="http://www.lpthe.jussieu.fr/~salam/fastjet">FastJet</a> page. | |
43 | */ | |
44 | //---------------------------------------------------------------------- | |
45 | ||
46 | #ifndef __FASTJET_CLUSTERSEQUENCE_HH__ | |
47 | #define __FASTJET_CLUSTERSEQUENCE_HH__ | |
48 | ||
49 | #include<vector> | |
50 | #include<map> | |
51 | #include "fastjet/internal/DynamicNearestNeighbours.hh" | |
52 | #include "fastjet/PseudoJet.hh" | |
53 | #include<memory> | |
54 | #include<cassert> | |
55 | #include<iostream> | |
56 | #include<string> | |
57 | #include<set> | |
58 | #include<cmath> // needed to get double std::abs(double) | |
59 | #include "fastjet/Error.hh" | |
60 | #include "fastjet/JetDefinition.hh" | |
61 | ||
62 | namespace fastjet { // defined in fastjet/internal/base.hh | |
63 | ||
64 | ||
65 | /// deals with clustering | |
66 | class ClusterSequence { | |
67 | ||
68 | ||
69 | public: | |
70 | ||
71 | /// default constructor | |
72 | ClusterSequence () {} | |
73 | ||
74 | /// create a clustersequence starting from the supplied set | |
75 | /// of pseudojets and clustering them with the long-invariant | |
76 | /// kt algorithm (E-scheme recombination) with the supplied | |
77 | /// value for R. | |
78 | /// | |
79 | /// If strategy=DumbN3 a very stupid N^3 algorithm is used for the | |
80 | /// clustering; otherwise strategy = NlnN* uses cylinders algorithms | |
81 | /// with some number of pi coverage. If writeout_combinations=true a | |
82 | /// summary of the recombination sequence is written out | |
83 | template<class L> ClusterSequence (const std::vector<L> & pseudojets, | |
84 | const double & R = 1.0, | |
85 | const Strategy & strategy = Best, | |
86 | const bool & writeout_combinations = false); | |
87 | ||
88 | ||
89 | /// create a clustersequence starting from the supplied set | |
90 | /// of pseudojets and clustering them with jet definition specified | |
91 | /// by jet_def (which also specifies the clustering strategy) | |
92 | template<class L> ClusterSequence ( | |
93 | const std::vector<L> & pseudojets, | |
94 | const JetDefinition & jet_def, | |
95 | const bool & writeout_combinations = false); | |
96 | ||
97 | // virtual ClusterSequence destructor, in case any derived class | |
98 | // thinks of needing a destructor at some point | |
99 | virtual ~ClusterSequence (); //{} | |
100 | ||
101 | // NB: in the routines that follow, for extracting lists of jets, a | |
102 | // list structure might be more efficient, if sometimes a little | |
103 | // more awkward to use (at least for old fortran hands). | |
104 | ||
105 | /// return a vector of all jets (in the sense of the inclusive | |
106 | /// algorithm) with pt >= ptmin. Time taken should be of the order | |
107 | /// of the number of jets returned. | |
108 | std::vector<PseudoJet> inclusive_jets (const double & ptmin = 0.0) const; | |
109 | ||
110 | /// return the number of jets (in the sense of the exclusive | |
111 | /// algorithm) that would be obtained when running the algorithm | |
112 | /// with the given dcut. | |
113 | int n_exclusive_jets (const double & dcut) const; | |
114 | ||
115 | /// return a vector of all jets (in the sense of the exclusive | |
116 | /// algorithm) that would be obtained when running the algorithm | |
117 | /// with the given dcut. | |
118 | std::vector<PseudoJet> exclusive_jets (const double & dcut) const; | |
119 | ||
120 | /// return a vector of all jets when the event is clustered (in the | |
121 | /// exclusive sense) to exactly njets. | |
122 | std::vector<PseudoJet> exclusive_jets (const int & njets) const; | |
123 | ||
124 | /// return the dmin corresponding to the recombination that went from | |
125 | /// n+1 to n jets (sometimes known as d_{n n+1}). | |
126 | double exclusive_dmerge (const int & njets) const; | |
127 | ||
128 | /// return the maximum of the dmin encountered during all recombinations | |
129 | /// up to the one that led to an n-jet final state; identical to | |
130 | /// exclusive_dmerge, except in cases where the dmin do not increase | |
131 | /// monotonically. | |
132 | double exclusive_dmerge_max (const int & njets) const; | |
133 | ||
134 | /// return the ymin corresponding to the recombination that went from | |
135 | /// n+1 to n jets (sometimes known as y_{n n+1}). | |
136 | double exclusive_ymerge (int njets) const {return exclusive_dmerge(njets) / Q2();} | |
137 | ||
138 | /// same as exclusive_dmerge_max, but normalised to squared total energy | |
139 | double exclusive_ymerge_max (int njets) const {return exclusive_ymerge_max(njets)/Q2();} | |
140 | ||
141 | /// the number of exclusive jets at the given ycut | |
142 | int n_exclusive_jets_ycut (double ycut) const {return n_exclusive_jets(ycut*Q2());} | |
143 | ||
144 | /// the exclusive jets obtained at the given ycut | |
145 | std::vector<PseudoJet> exclusive_jets_ycut (double ycut) const { | |
146 | int njets = n_exclusive_jets_ycut(ycut); | |
147 | return exclusive_jets(njets); | |
148 | } | |
149 | ||
150 | ||
151 | //int n_exclusive_jets (const PseudoJet & jet, const double & dcut) const; | |
152 | ||
153 | /// return a vector of all subjets of the current jet (in the sense | |
154 | /// of the exclusive algorithm) that would be obtained when running | |
155 | /// the algorithm with the given dcut. | |
156 | /// | |
157 | /// Time taken is O(m ln m), where m is the number of subjets that | |
158 | /// are found. If m gets to be of order of the total number of | |
159 | /// constituents in the jet, this could be substantially slower than | |
160 | /// just getting that list of constituents. | |
161 | std::vector<PseudoJet> exclusive_subjets (const PseudoJet & jet, | |
162 | const double & dcut) const; | |
163 | ||
164 | /// return the size of exclusive_subjets(...); still n ln n with same | |
165 | /// coefficient, but marginally more efficient than manually taking | |
166 | /// exclusive_subjets.size() | |
167 | int n_exclusive_subjets(const PseudoJet & jet, | |
168 | const double & dcut) const; | |
169 | ||
170 | /// return the list of subjets obtained by unclustering the supplied | |
171 | /// jet down to n subjets (or all constituents if there are fewer | |
172 | /// than n). | |
173 | /// | |
174 | /// requires n ln n time | |
175 | std::vector<PseudoJet> exclusive_subjets (const PseudoJet & jet, | |
176 | int nsub) const; | |
177 | ||
178 | /// return the dij that was present in the merging nsub+1 -> nsub | |
179 | /// subjets inside this jet. | |
180 | double exclusive_subdmerge(const PseudoJet & jet, int nsub) const; | |
181 | ||
182 | /// return the maximum dij that occurred in the whole event at the | |
183 | /// stage that the nsub+1 -> nsub merge of subjets occurred inside | |
184 | /// this jet. | |
185 | double exclusive_subdmerge_max(const PseudoJet & jet, int nsub) const; | |
186 | ||
187 | //std::vector<PseudoJet> exclusive_jets (const PseudoJet & jet, | |
188 | // const int & njets) const; | |
189 | //double exclusive_dmerge (const PseudoJet & jet, const int & njets) const; | |
190 | ||
191 | /// returns the sum of all energies in the event (relevant mainly for e+e-) | |
192 | double Q() const {return _Q;} | |
193 | /// return Q()^2 | |
194 | double Q2() const {return _Q*_Q;} | |
195 | ||
196 | /// returns true iff the object is included in the jet. | |
197 | /// | |
198 | /// NB: this is only sensible if the object is already registered | |
199 | /// within the cluster sequence, so you cannot use it with an input | |
200 | /// particle to the CS (since the particle won't have the history | |
201 | /// index set properly). | |
202 | /// | |
203 | /// For nice clustering structures it should run in O(ln(N)) time | |
204 | /// but in worst cases (certain cone plugins) it can take O(n) time, | |
205 | /// where n is the number of particles in the jet. | |
206 | bool object_in_jet(const PseudoJet & object, const PseudoJet & jet) const; | |
207 | ||
208 | /// if the jet has parents in the clustering, it returns true | |
209 | /// and sets parent1 and parent2 equal to them. | |
210 | /// | |
211 | /// if it has no parents it returns false and sets parent1 and | |
212 | /// parent2 to zero | |
213 | bool has_parents(const PseudoJet & jet, PseudoJet & parent1, | |
214 | PseudoJet & parent2) const; | |
215 | ||
216 | /// if the jet has a child then return true and give the child jet | |
217 | /// otherwise return false and set the child to zero | |
218 | bool has_child(const PseudoJet & jet, PseudoJet & child) const; | |
219 | ||
220 | /// Version of has_child that sets a pointer to the child if the child | |
221 | /// exists; | |
222 | bool has_child(const PseudoJet & jet, const PseudoJet * & childp) const; | |
223 | ||
224 | /// if this jet has a child (and so a partner) return true | |
225 | /// and give the partner, otherwise return false and set the | |
226 | /// partner to zero | |
227 | bool has_partner(const PseudoJet & jet, PseudoJet & partner) const; | |
228 | ||
229 | ||
230 | /// return a vector of the particles that make up jet | |
231 | std::vector<PseudoJet> constituents (const PseudoJet & jet) const; | |
232 | ||
233 | ||
234 | /// output the supplied vector of jets in a format that can be read | |
235 | /// by an appropriate root script; the format is: | |
236 | /// jet-n jet-px jet-py jet-pz jet-E | |
237 | /// particle-n particle-rap particle-phi particle-pt | |
238 | /// particle-n particle-rap particle-phi particle-pt | |
239 | /// ... | |
240 | /// #END | |
241 | /// ... [i.e. above repeated] | |
242 | void print_jets_for_root(const std::vector<PseudoJet> & jets, | |
243 | std::ostream & ostr = std::cout) const; | |
244 | ||
245 | /// print jets for root to the file labelled filename, with an | |
246 | /// optional comment at the beginning | |
247 | void print_jets_for_root(const std::vector<PseudoJet> & jets, | |
248 | const std::string & filename, | |
249 | const std::string & comment = "") const; | |
250 | ||
251 | // Not yet. Perhaps in a future release. | |
252 | // /// print out all inclusive jets with pt > ptmin | |
253 | // virtual void print_jets (const double & ptmin=0.0) const; | |
254 | ||
255 | /// add on to subjet_vector the constituents of jet (for internal use mainly) | |
256 | void add_constituents (const PseudoJet & jet, | |
257 | std::vector<PseudoJet> & subjet_vector) const; | |
258 | ||
259 | /// return the enum value of the strategy used to cluster the event | |
260 | inline Strategy strategy_used () const {return _strategy;} | |
261 | std::string strategy_string () const; | |
262 | ||
263 | /// return a reference to the jet definition | |
264 | const JetDefinition & jet_def() const {return _jet_def;} | |
265 | ||
266 | /// returns the scale associated with a jet as required for this | |
267 | /// clustering algorithm (kt^2 for the kt-algorithm, 1 for the | |
268 | /// Cambridge algorithm). [May become virtual at some point] | |
269 | double jet_scale_for_algorithm(const PseudoJet & jet) const; | |
270 | ||
271 | //----- next follow functions designed specifically for plugins, which | |
272 | // may only be called when plugin_activated() returns true | |
273 | ||
274 | /// record the fact that there has been a recombination between | |
275 | /// jets()[jet_i] and jets()[jet_k], with the specified dij, and | |
276 | /// return the index (newjet_k) allocated to the new jet, whose | |
277 | /// momentum is assumed to be the 4-vector sum of that of jet_i and | |
278 | /// jet_j | |
279 | void plugin_record_ij_recombination(int jet_i, int jet_j, double dij, | |
280 | int & newjet_k) { | |
281 | assert(plugin_activated()); | |
282 | _do_ij_recombination_step(jet_i, jet_j, dij, newjet_k); | |
283 | } | |
284 | ||
285 | /// as for the simpler variant of plugin_record_ij_recombination, | |
286 | /// except that the new jet is attributed the momentum and | |
287 | /// user_index of newjet | |
288 | void plugin_record_ij_recombination(int jet_i, int jet_j, double dij, | |
289 | const PseudoJet & newjet, | |
290 | int & newjet_k); | |
291 | ||
292 | /// record the fact that there has been a recombination between | |
293 | /// jets()[jet_i] and the beam, with the specified diB; when looking | |
294 | /// for inclusive jets, any iB recombination will returned to the user | |
295 | /// as a jet. | |
296 | void plugin_record_iB_recombination(int jet_i, double diB) { | |
297 | assert(plugin_activated()); | |
298 | _do_iB_recombination_step(jet_i, diB); | |
299 | } | |
300 | ||
301 | /// a class intended to serve as a base in case a plugin needs to | |
302 | /// associate extra information with a ClusterSequence (see | |
303 | /// SISConePlugin.* for an example). | |
304 | class Extras { | |
305 | public: | |
306 | virtual ~Extras() {} | |
307 | virtual std::string description() const {return "This is a dummy extras class that contains no extra information! Derive from it if you want to use it to provide extra information from a plugin jet finder";} | |
308 | }; | |
309 | ||
310 | /// the plugin can associated some extra information with the | |
311 | /// ClusterSequence object by calling this function | |
312 | inline void plugin_associate_extras(std::auto_ptr<Extras> extras_in) { | |
313 | _extras = extras_in; | |
314 | } | |
315 | ||
316 | /// returns true when the plugin is allowed to run the show. | |
317 | inline bool plugin_activated() const {return _plugin_activated;} | |
318 | ||
319 | /// returns a pointer to the extras object (may be null) | |
320 | const Extras * extras() const {return _extras.get();} | |
321 | ||
322 | /// allows a plugin to run a templated clustering (nearest-neighbour heuristic) | |
323 | /// | |
324 | /// This has N^2 behaviour on "good" distance, but a worst case behaviour | |
325 | /// of N^3 (and many algs trigger the worst case behaviour) | |
326 | /// | |
327 | /// | |
328 | /// For more details on how this works, see GenBriefJet below | |
329 | template<class GBJ> void plugin_simple_N2_cluster () { | |
330 | assert(plugin_activated()); | |
331 | _simple_N2_cluster<GBJ>(); | |
332 | } | |
333 | ||
334 | //---------------------------------------------------------------------- | |
335 | /// class to help with a generic clustering sequence | |
336 | class GenBriefJet { | |
337 | public: | |
338 | /// function that initialises the GenBriefJet given a PseudoJet. | |
339 | /// | |
340 | /// In a derived class, this member has a responsability to call | |
341 | /// | |
342 | /// - set_scale_squared | |
343 | /// - set_geom_iB | |
344 | /// | |
345 | /// The clustering will be performed by finding the minimum of | |
346 | /// | |
347 | /// diB = scale_squared[i] * geom_iB * _invR2 | |
348 | /// dij = min(scale_squared[i],scale_squared[j]) * geom_ij * _invR2 | |
349 | /// | |
350 | virtual void init(const PseudoJet & jet) = 0; | |
351 | ||
352 | /// Returns the "geometric" part of distance between this jet | |
353 | /// and jet_j | |
354 | virtual double geom_ij(const GenBriefJet * jet_j) const = 0; | |
355 | ||
356 | void set_scale_squared(double scale_squared) {kt2 = scale_squared;} | |
357 | void set_geom_iB(double diB) {NN_dist = diB; NN = NULL;} | |
358 | ||
359 | public: // formally public: but users should think of it as private! | |
360 | double NN_dist; // dij | |
361 | double kt2; // squared scale | |
362 | GenBriefJet * NN; // pointer to nearest neighbour | |
363 | int _jets_index; // index of this jet | |
364 | }; | |
365 | ||
366 | ||
367 | public: | |
368 | /// set the default (static) jet finder across all current and future | |
369 | /// ClusterSequence objects -- deprecated and obsolescent (i.e. may be | |
370 | /// suppressed in a future release). | |
371 | static void set_jet_algorithm (JetAlgorithm jet_algorithm) {_default_jet_algorithm = jet_algorithm;} | |
372 | /// same as above for backward compatibility | |
373 | static void set_jet_finder (JetAlgorithm jet_algorithm) {_default_jet_algorithm = jet_algorithm;} | |
374 | ||
375 | ||
376 | /// a single element in the clustering history (see vector _history | |
377 | /// below). | |
378 | struct history_element{ | |
379 | int parent1; /// index in _history where first parent of this jet | |
380 | /// was created (InexistentParent if this jet is an | |
381 | /// original particle) | |
382 | ||
383 | int parent2; /// index in _history where second parent of this jet | |
384 | /// was created (InexistentParent if this jet is an | |
385 | /// original particle); BeamJet if this history entry | |
386 | /// just labels the fact that the jet has recombined | |
387 | /// with the beam) | |
388 | ||
389 | int child; /// index in _history where the current jet is | |
390 | /// recombined with another jet to form its child. It | |
391 | /// is Invalid if this jet does not further | |
392 | /// recombine. | |
393 | ||
394 | int jetp_index; /// index in the _jets vector where we will find the | |
395 | /// PseudoJet object corresponding to this jet | |
396 | /// (i.e. the jet created at this entry of the | |
397 | /// history). NB: if this element of the history | |
398 | /// corresponds to a beam recombination, then | |
399 | /// jetp_index=Invalid. | |
400 | ||
401 | double dij; /// the distance corresponding to the recombination | |
402 | /// at this stage of the clustering. | |
403 | ||
404 | double max_dij_so_far; /// the largest recombination distance seen | |
405 | /// so far in the clustering history. | |
406 | }; | |
407 | ||
408 | enum JetType {Invalid=-3, InexistentParent = -2, BeamJet = -1}; | |
409 | ||
410 | /// allow the user to access the internally stored _jets() array, | |
411 | /// which contains both the initial particles and the various | |
412 | /// intermediate and final stages of recombination. | |
413 | /// | |
414 | /// The first n_particles() entries are the original particles, | |
415 | /// in the order in which they were supplied to the ClusterSequence | |
416 | /// constructor. It can be useful to access them for example when | |
417 | /// examining whether a given input object is part of a specific | |
418 | /// jet, via the objects_in_jet(...) member function (which only takes | |
419 | /// PseudoJets that are registered in the ClusterSequence). | |
420 | /// | |
421 | /// One of the other (internal uses) is related to the fact | |
422 | /// because we don't seem to be able to access protected elements of | |
423 | /// the class for an object that is not "this" (at least in case where | |
424 | /// "this" is of a slightly different kind from the object, both | |
425 | /// derived from ClusterSequence). | |
426 | const std::vector<PseudoJet> & jets() const; | |
427 | ||
428 | /// allow the user to access the raw internal history. | |
429 | /// | |
430 | /// This is present (as for jets()) in part so that protected | |
431 | /// derived classes can access this information about other | |
432 | /// ClusterSequences. | |
433 | /// | |
434 | /// A user who wishes to follow the details of the ClusterSequence | |
435 | /// can also make use of this information (and should consult the | |
436 | /// history_element documentation for more information), but should | |
437 | /// be aware that these internal structures may evolve in future | |
438 | /// FastJet versions. | |
439 | const std::vector<history_element> & history() const; | |
440 | ||
441 | /// returns the number of particles that were provided to the | |
442 | /// clustering algorithm (helps the user find their way around the | |
443 | /// history and jets objects if they weren't paying attention | |
444 | /// beforehand). | |
445 | unsigned int n_particles() const; | |
446 | ||
447 | /// returns a vector of size n_particles() which indicates, for | |
448 | /// each of the initial particles (in the order in which they were | |
449 | /// supplied), which of the supplied jets it belongs to; if it does | |
450 | /// not belong to any of the supplied jets, the index is set to -1; | |
451 | std::vector<int> particle_jet_indices(const std::vector<PseudoJet> &) const; | |
452 | ||
453 | /// routine that returns an order in which to read the history | |
454 | /// such that clusterings that lead to identical jet compositions | |
455 | /// but different histories (because of degeneracies in the | |
456 | /// clustering order) will have matching constituents for each | |
457 | /// matching entry in the unique_history_order. | |
458 | /// | |
459 | /// The order has the property that an entry's parents will always | |
460 | /// appear prior to that entry itself. | |
461 | /// | |
462 | /// Roughly speaking the order is such that we first provide all | |
463 | /// steps that lead to the final jet containing particle 1; then we | |
464 | /// have the steps that lead to reconstruction of the jet containing | |
465 | /// the next-lowest-numbered unclustered particle, etc... | |
466 | /// [see GPS CCN28-12 for more info -- of course a full explanation | |
467 | /// here would be better...] | |
468 | std::vector<int> unique_history_order() const; | |
469 | ||
470 | /// return the set of particles that have not been clustered. For | |
471 | /// kt and cam/aachen algorithms this should always be null, but for | |
472 | /// cone type algorithms it can be non-null; | |
473 | std::vector<PseudoJet> unclustered_particles() const; | |
474 | ||
475 | /// transfer the sequence contained in other_seq into our own; | |
476 | /// any plugin "extras" contained in the from_seq will be lost | |
477 | /// from there. | |
478 | void transfer_from_sequence(ClusterSequence & from_seq); | |
479 | ||
480 | ||
481 | protected: | |
482 | static JetAlgorithm _default_jet_algorithm; | |
483 | JetDefinition _jet_def; | |
484 | ||
485 | /// returns true if the jet has a history index contained within | |
486 | /// the range of this CS | |
487 | bool _potentially_valid(const PseudoJet & jet) const { | |
488 | return jet.cluster_hist_index() >= 0 | |
489 | && jet.cluster_hist_index() < int(_history.size()); | |
490 | } | |
491 | ||
492 | /// transfer the vector<L> of input jets into our own vector<PseudoJet> | |
493 | /// _jets (with some reserved space for future growth). | |
494 | template<class L> void _transfer_input_jets( | |
495 | const std::vector<L> & pseudojets); | |
496 | ||
497 | /// This is the routine that will do all the initialisation and | |
498 | /// then run the clustering (may be called by various constructors). | |
499 | /// It assumes _jets contains the momenta to be clustered. | |
500 | void _initialise_and_run (const JetDefinition & jet_def, | |
501 | const bool & writeout_combinations); | |
502 | ||
503 | /// This is an alternative routine for initialising and running the | |
504 | /// clustering, provided for legacy purposes. The jet finder is that | |
505 | /// specified in the static member _default_jet_algorithm. | |
506 | void _initialise_and_run (const double & R, | |
507 | const Strategy & strategy, | |
508 | const bool & writeout_combinations); | |
509 | ||
510 | /// fills in the various member variables with "decanted" options from | |
511 | /// the jet_definition and writeout_combinations variables | |
512 | void _decant_options(const JetDefinition & jet_def, | |
513 | const bool & writeout_combinations); | |
514 | ||
515 | /// fill out the history (and jet cross refs) related to the initial | |
516 | /// set of jets (assumed already to have been "transferred"), | |
517 | /// without any clustering | |
518 | void _fill_initial_history(); | |
519 | ||
520 | /// carry out the recombination between the jets numbered jet_i and | |
521 | /// jet_j, at distance scale dij; return the index newjet_k of the | |
522 | /// result of the recombination of i and j. | |
523 | void _do_ij_recombination_step(const int & jet_i, const int & jet_j, | |
524 | const double & dij, int & newjet_k); | |
525 | ||
526 | /// carry out an recombination step in which _jets[jet_i] merges with | |
527 | /// the beam, | |
528 | void _do_iB_recombination_step(const int & jet_i, const double & diB); | |
529 | ||
530 | ||
531 | /// This contains the physical PseudoJets; for each PseudoJet one | |
532 | /// can find the corresponding position in the _history by looking | |
533 | /// at _jets[i].cluster_hist_index(). | |
534 | std::vector<PseudoJet> _jets; | |
535 | ||
536 | ||
537 | /// this vector will contain the branching history; for each stage, | |
538 | /// _history[i].jetp_index indicates where to look in the _jets | |
539 | /// vector to get the physical PseudoJet. | |
540 | std::vector<history_element> _history; | |
541 | ||
542 | /// set subhist to be a set pointers to history entries corresponding to the | |
543 | /// subjets of this jet; one stops going working down through the | |
544 | /// subjets either when | |
545 | /// - there is no further to go | |
546 | /// - one has found maxjet entries | |
547 | /// - max_dij_so_far <= dcut | |
548 | /// By setting maxjet=0 one can use just dcut; by setting dcut<0 | |
549 | /// one can use jet maxjet | |
550 | void get_subhist_set(std::set<const history_element*> & subhist, | |
551 | const PseudoJet & jet, double dcut, int maxjet) const; | |
552 | ||
553 | bool _writeout_combinations; | |
554 | int _initial_n; | |
555 | double _Rparam, _R2, _invR2; | |
556 | double _Q; | |
557 | Strategy _strategy; | |
558 | JetAlgorithm _jet_algorithm; | |
559 | ||
560 | ||
561 | private: | |
562 | ||
563 | bool _plugin_activated; | |
564 | std::auto_ptr<Extras> _extras; // things the plugin might want to add | |
565 | ||
566 | void _really_dumb_cluster (); | |
567 | void _delaunay_cluster (); | |
568 | //void _simple_N2_cluster (); | |
569 | template<class BJ> void _simple_N2_cluster (); | |
570 | void _tiled_N2_cluster (); | |
571 | void _faster_tiled_N2_cluster (); | |
572 | ||
573 | // | |
574 | void _minheap_faster_tiled_N2_cluster(); | |
575 | ||
576 | // things needed specifically for Cambridge with Chan's 2D closest | |
577 | // pairs method | |
578 | void _CP2DChan_cluster(); | |
579 | void _CP2DChan_cluster_2pi2R (); | |
580 | void _CP2DChan_cluster_2piMultD (); | |
581 | void _CP2DChan_limited_cluster(double D); | |
582 | void _do_Cambridge_inclusive_jets(); | |
583 | ||
584 | void _add_step_to_history(const int & step_number, const int & parent1, | |
585 | const int & parent2, const int & jetp_index, | |
586 | const double & dij); | |
587 | ||
588 | /// internal routine associated with the construction of the unique | |
589 | /// history order (following children in the tree) | |
590 | void _extract_tree_children(int pos, std::valarray<bool> &, | |
591 | const std::valarray<int> &, std::vector<int> &) const; | |
592 | ||
593 | /// internal routine associated with the construction of the unique | |
594 | /// history order (following parents in the tree) | |
595 | void _extract_tree_parents (int pos, std::valarray<bool> &, | |
596 | const std::valarray<int> &, std::vector<int> &) const; | |
597 | ||
598 | ||
599 | // these will be useful shorthands in the Voronoi-based code | |
600 | typedef std::pair<int,int> TwoVertices; | |
601 | typedef std::pair<double,TwoVertices> DijEntry; | |
602 | typedef std::multimap<double,TwoVertices> DistMap; | |
603 | ||
604 | /// currently used only in the Voronoi based code | |
605 | void _add_ktdistance_to_map(const int & ii, | |
606 | DistMap & DijMap, | |
607 | const DynamicNearestNeighbours * DNN); | |
608 | ||
609 | /// for making sure the user knows what it is they're running... | |
610 | void _print_banner(); | |
611 | /// will be set by default to be true for the first run | |
612 | static bool _first_time; | |
613 | ||
614 | /// record the number of warnings provided about the exclusive | |
615 | /// algorithm -- so that we don't print it out more than a few | |
616 | /// times. | |
617 | static int _n_exclusive_warnings; | |
618 | ||
619 | //---------------------------------------------------------------------- | |
620 | /// the fundamental structure which contains the minimal info about | |
621 | /// a jet, as needed for our plain N^2 algorithm -- the idea is to | |
622 | /// put all info that will be accessed N^2 times into an array of | |
623 | /// BriefJets... | |
624 | struct BriefJet { | |
625 | double eta, phi, kt2, NN_dist; | |
626 | BriefJet * NN; | |
627 | int _jets_index; | |
628 | }; | |
629 | ||
630 | ||
631 | /// structure analogous to BriefJet, but with the extra information | |
632 | /// needed for dealing with tiles | |
633 | class TiledJet { | |
634 | public: | |
635 | double eta, phi, kt2, NN_dist; | |
636 | TiledJet * NN, *previous, * next; | |
637 | int _jets_index, tile_index, diJ_posn; | |
638 | // routines that are useful in the minheap version of tiled | |
639 | // clustering ("misuse" the otherwise unused diJ_posn, so as | |
640 | // to indicate whether jets need to have their minheap entries | |
641 | // updated). | |
642 | inline void label_minheap_update_needed() {diJ_posn = 1;} | |
643 | inline void label_minheap_update_done() {diJ_posn = 0;} | |
644 | inline bool minheap_update_needed() const {return diJ_posn==1;} | |
645 | }; | |
646 | ||
647 | //-- some of the functions that follow are templates and will work | |
648 | //as well for briefjet and tiled jets | |
649 | ||
650 | /// set the kinematic and labelling info for jeta so that it corresponds | |
651 | /// to _jets[_jets_index] | |
652 | template <class J> void _bj_set_jetinfo( J * const jet, | |
653 | const int _jets_index) const; | |
654 | ||
655 | /// "remove" this jet, which implies updating links of neighbours and | |
656 | /// perhaps modifying the tile structure | |
657 | void _bj_remove_from_tiles( TiledJet * const jet) const; | |
658 | ||
659 | /// return the distance between two BriefJet objects | |
660 | template <class J> double _bj_dist(const J * const jeta, | |
661 | const J * const jetb) const; | |
662 | ||
663 | // return the diJ (multiplied by _R2) for this jet assuming its NN | |
664 | // info is correct | |
665 | template <class J> double _bj_diJ(const J * const jeta) const; | |
666 | ||
667 | /// for testing purposes only: if in the range head--tail-1 there is a | |
668 | /// a jet which corresponds to hist_index in the history, then | |
669 | /// return a pointer to that jet; otherwise return tail. | |
670 | template <class J> inline J * _bj_of_hindex( | |
671 | const int hist_index, | |
672 | J * const head, J * const tail) | |
673 | const { | |
674 | J * res; | |
675 | for(res = head; res<tail; res++) { | |
676 | if (_jets[res->_jets_index].cluster_hist_index() == hist_index) {break;} | |
677 | } | |
678 | return res; | |
679 | } | |
680 | ||
681 | ||
682 | //-- remaining functions are different in various cases, so we | |
683 | // will use templates but are not sure if they're useful... | |
684 | ||
685 | /// updates (only towards smaller distances) the NN for jeta without checking | |
686 | /// whether in the process jeta itself might be a new NN of one of | |
687 | /// the jets being scanned -- span the range head to tail-1 with | |
688 | /// assumption that jeta is not contained in that range | |
689 | template <class J> void _bj_set_NN_nocross(J * const jeta, | |
690 | J * const head, const J * const tail) const; | |
691 | ||
692 | /// reset the NN for jeta and DO check whether in the process jeta | |
693 | /// itself might be a new NN of one of the jets being scanned -- | |
694 | /// span the range head to tail-1 with assumption that jeta is not | |
695 | /// contained in that range | |
696 | template <class J> void _bj_set_NN_crosscheck(J * const jeta, | |
697 | J * const head, const J * const tail) const; | |
698 | ||
699 | ||
700 | ||
701 | /// number of neighbours that a tile will have (rectangular geometry | |
702 | /// gives 9 neighbours). | |
703 | static const int n_tile_neighbours = 9; | |
704 | //---------------------------------------------------------------------- | |
705 | /// The fundamental structures to be used for the tiled N^2 algorithm | |
706 | /// (see CCN27-44 for some discussion of pattern of tiling) | |
707 | struct Tile { | |
708 | /// pointers to neighbouring tiles, including self | |
709 | Tile * begin_tiles[n_tile_neighbours]; | |
710 | /// neighbouring tiles, excluding self | |
711 | Tile ** surrounding_tiles; | |
712 | /// half of neighbouring tiles, no self | |
713 | Tile ** RH_tiles; | |
714 | /// just beyond end of tiles | |
715 | Tile ** end_tiles; | |
716 | /// start of list of BriefJets contained in this tile | |
717 | TiledJet * head; | |
718 | /// sometimes useful to be able to tag a tile | |
719 | bool tagged; | |
720 | }; | |
721 | std::vector<Tile> _tiles; | |
722 | double _tiles_eta_min, _tiles_eta_max; | |
723 | double _tile_size_eta, _tile_size_phi; | |
724 | int _n_tiles_phi,_tiles_ieta_min,_tiles_ieta_max; | |
725 | ||
726 | // reasonably robust return of tile index given ieta and iphi, in particular | |
727 | // it works even if iphi is negative | |
728 | inline int _tile_index (int ieta, int iphi) const { | |
729 | // note that (-1)%n = -1 so that we have to add _n_tiles_phi | |
730 | // before performing modulo operation | |
731 | return (ieta-_tiles_ieta_min)*_n_tiles_phi | |
732 | + (iphi+_n_tiles_phi) % _n_tiles_phi; | |
733 | } | |
734 | ||
735 | // routines for tiled case, including some overloads of the plain | |
736 | // BriefJet cases | |
737 | int _tile_index(const double & eta, const double & phi) const; | |
738 | void _tj_set_jetinfo ( TiledJet * const jet, const int _jets_index); | |
739 | void _bj_remove_from_tiles(TiledJet * const jet); | |
740 | void _initialise_tiles(); | |
741 | void _print_tiles(TiledJet * briefjets ) const; | |
742 | void _add_neighbours_to_tile_union(const int tile_index, | |
743 | std::vector<int> & tile_union, int & n_near_tiles) const; | |
744 | void _add_untagged_neighbours_to_tile_union(const int tile_index, | |
745 | std::vector<int> & tile_union, int & n_near_tiles); | |
746 | ||
747 | ||
748 | //---------------------------------------------------------------------- | |
749 | /// fundamental structure for e+e- clustering | |
750 | struct EEBriefJet { | |
751 | double NN_dist; // obligatorily present | |
752 | double kt2; // obligatorily present == E^2 in general | |
753 | EEBriefJet * NN; // must be present too | |
754 | int _jets_index; // must also be present! | |
755 | //........................................................... | |
756 | double nx, ny, nz; // our internal storage for fast distance calcs | |
757 | }; | |
758 | ||
759 | /// to help instantiation | |
760 | void _dummy_N2_cluster_instantiation(); | |
761 | ||
762 | }; | |
763 | ||
764 | ||
765 | //********************************************************************** | |
766 | //************** START OF INLINE MATERIAL ****************** | |
767 | //********************************************************************** | |
768 | ||
769 | ||
770 | //---------------------------------------------------------------------- | |
771 | // Transfer the initial jets into our internal structure | |
772 | template<class L> void ClusterSequence::_transfer_input_jets( | |
773 | const std::vector<L> & pseudojets) { | |
774 | ||
775 | // this will ensure that we can point to jets without difficulties | |
776 | // arising. | |
777 | _jets.reserve(pseudojets.size()*2); | |
778 | ||
779 | // insert initial jets this way so that any type L that can be | |
780 | // converted to a pseudojet will work fine (basically PseudoJet | |
781 | // and any type that has [] subscript access to the momentum | |
782 | // components, such as CLHEP HepLorentzVector). | |
783 | for (unsigned int i = 0; i < pseudojets.size(); i++) { | |
784 | _jets.push_back(pseudojets[i]);} | |
785 | ||
786 | } | |
787 | ||
788 | //---------------------------------------------------------------------- | |
789 | // initialise from some generic type... Has to be made available | |
790 | // here in order for it the template aspect of it to work... | |
791 | template<class L> ClusterSequence::ClusterSequence ( | |
792 | const std::vector<L> & pseudojets, | |
793 | const double & R, | |
794 | const Strategy & strategy, | |
795 | const bool & writeout_combinations) { | |
796 | ||
797 | // transfer the initial jets (type L) into our own array | |
798 | _transfer_input_jets(pseudojets); | |
799 | ||
800 | // run the clustering | |
801 | _initialise_and_run(R,strategy,writeout_combinations); | |
802 | } | |
803 | ||
804 | ||
805 | //---------------------------------------------------------------------- | |
806 | /// constructor of a jet-clustering sequence from a vector of | |
807 | /// four-momenta, with the jet definition specified by jet_def | |
808 | template<class L> ClusterSequence::ClusterSequence ( | |
809 | const std::vector<L> & pseudojets, | |
810 | const JetDefinition & jet_def, | |
811 | const bool & writeout_combinations) { | |
812 | ||
813 | // transfer the initial jets (type L) into our own array | |
814 | _transfer_input_jets(pseudojets); | |
815 | ||
816 | // run the clustering | |
817 | _initialise_and_run(jet_def,writeout_combinations); | |
818 | } | |
819 | ||
820 | ||
821 | inline const std::vector<PseudoJet> & ClusterSequence::jets () const { | |
822 | return _jets; | |
823 | } | |
824 | ||
825 | inline const std::vector<ClusterSequence::history_element> & ClusterSequence::history () const { | |
826 | return _history; | |
827 | } | |
828 | ||
829 | inline unsigned int ClusterSequence::n_particles() const {return _initial_n;} | |
830 | ||
831 | ||
832 | ||
833 | //---------------------------------------------------------------------- | |
834 | template <class J> inline void ClusterSequence::_bj_set_jetinfo( | |
835 | J * const jetA, const int _jets_index) const { | |
836 | jetA->eta = _jets[_jets_index].rap(); | |
837 | jetA->phi = _jets[_jets_index].phi_02pi(); | |
838 | jetA->kt2 = jet_scale_for_algorithm(_jets[_jets_index]); | |
839 | jetA->_jets_index = _jets_index; | |
840 | // initialise NN info as well | |
841 | jetA->NN_dist = _R2; | |
842 | jetA->NN = NULL; | |
843 | } | |
844 | ||
845 | ||
846 | ||
847 | ||
848 | //---------------------------------------------------------------------- | |
849 | template <class J> inline double ClusterSequence::_bj_dist( | |
850 | const J * const jetA, const J * const jetB) const { | |
851 | double dphi = std::abs(jetA->phi - jetB->phi); | |
852 | double deta = (jetA->eta - jetB->eta); | |
853 | if (dphi > pi) {dphi = twopi - dphi;} | |
854 | return dphi*dphi + deta*deta; | |
855 | } | |
856 | ||
857 | //---------------------------------------------------------------------- | |
858 | template <class J> inline double ClusterSequence::_bj_diJ(const J * const jet) const { | |
859 | double kt2 = jet->kt2; | |
860 | if (jet->NN != NULL) {if (jet->NN->kt2 < kt2) {kt2 = jet->NN->kt2;}} | |
861 | return jet->NN_dist * kt2; | |
862 | } | |
863 | ||
864 | ||
865 | //---------------------------------------------------------------------- | |
866 | // set the NN for jet without checking whether in the process you might | |
867 | // have discovered a new nearest neighbour for another jet | |
868 | template <class J> inline void ClusterSequence::_bj_set_NN_nocross( | |
869 | J * const jet, J * const head, const J * const tail) const { | |
870 | double NN_dist = _R2; | |
871 | J * NN = NULL; | |
872 | if (head < jet) { | |
873 | for (J * jetB = head; jetB != jet; jetB++) { | |
874 | double dist = _bj_dist(jet,jetB); | |
875 | if (dist < NN_dist) { | |
876 | NN_dist = dist; | |
877 | NN = jetB; | |
878 | } | |
879 | } | |
880 | } | |
881 | if (tail > jet) { | |
882 | for (J * jetB = jet+1; jetB != tail; jetB++) { | |
883 | double dist = _bj_dist(jet,jetB); | |
884 | if (dist < NN_dist) { | |
885 | NN_dist = dist; | |
886 | NN = jetB; | |
887 | } | |
888 | } | |
889 | } | |
890 | jet->NN = NN; | |
891 | jet->NN_dist = NN_dist; | |
892 | } | |
893 | ||
894 | ||
895 | //---------------------------------------------------------------------- | |
896 | template <class J> inline void ClusterSequence::_bj_set_NN_crosscheck(J * const jet, | |
897 | J * const head, const J * const tail) const { | |
898 | double NN_dist = _R2; | |
899 | J * NN = NULL; | |
900 | for (J * jetB = head; jetB != tail; jetB++) { | |
901 | double dist = _bj_dist(jet,jetB); | |
902 | if (dist < NN_dist) { | |
903 | NN_dist = dist; | |
904 | NN = jetB; | |
905 | } | |
906 | if (dist < jetB->NN_dist) { | |
907 | jetB->NN_dist = dist; | |
908 | jetB->NN = jet; | |
909 | } | |
910 | } | |
911 | jet->NN = NN; | |
912 | jet->NN_dist = NN_dist; | |
913 | } | |
914 | ||
915 | ||
916 | ||
917 | } // fastjet namespace | |
918 | ||
919 | #endif // __FASTJET_CLUSTERSEQUENCE_HH__ |