[5] | 1 | #ifndef __NNH_HH__ |
---|
| 2 | #define __NNH_HH__ |
---|
| 3 | |
---|
| 4 | //STARTHEADER |
---|
| 5 | // $Id: NNH.hh 2891 2012-06-15 12:47:59Z soyez $ |
---|
| 6 | // |
---|
| 7 | // Copyright (c) 2009, Matteo Cacciari, Gavin Salam and Gregory Soyez |
---|
| 8 | // |
---|
| 9 | //---------------------------------------------------------------------- |
---|
| 10 | // This file is part of FastJet. |
---|
| 11 | // |
---|
| 12 | // FastJet is free software; you can redistribute it and/or modify |
---|
| 13 | // it under the terms of the GNU General Public License as published by |
---|
| 14 | // the Free Software Foundation; either version 2 of the License, or |
---|
| 15 | // (at your option) any later version. |
---|
| 16 | // |
---|
| 17 | // The algorithms that underlie FastJet have required considerable |
---|
| 18 | // development and are described in hep-ph/0512210. If you use |
---|
| 19 | // FastJet as part of work towards a scientific publication, please |
---|
| 20 | // include a citation to the FastJet paper. |
---|
| 21 | // |
---|
| 22 | // FastJet is distributed in the hope that it will be useful, |
---|
| 23 | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
| 24 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
---|
| 25 | // GNU General Public License for more details. |
---|
| 26 | // |
---|
| 27 | // You should have received a copy of the GNU General Public License |
---|
| 28 | // along with FastJet. If not, see <http://www.gnu.org/licenses/>. |
---|
| 29 | //---------------------------------------------------------------------- |
---|
| 30 | //ENDHEADER |
---|
| 31 | |
---|
| 32 | #include<fastjet/ClusterSequence.hh> |
---|
| 33 | |
---|
| 34 | |
---|
| 35 | FASTJET_BEGIN_NAMESPACE // defined in fastjet/internal/base.hh |
---|
| 36 | |
---|
| 37 | /// @ingroup advanced_usage |
---|
| 38 | /// \class _NoInfo |
---|
| 39 | /// dummy class, used as a default template argument |
---|
| 40 | class _NoInfo {}; |
---|
| 41 | |
---|
| 42 | /// @ingroup advanced_usage |
---|
| 43 | /// \class NNHInfo |
---|
| 44 | /// template that will help initialise a BJ with a PseudoJet and extra information |
---|
| 45 | template<class I> class NNHInfo { |
---|
| 46 | public: |
---|
| 47 | NNHInfo() : _info(NULL) {} |
---|
| 48 | NNHInfo(I * info) : _info(info) {} |
---|
| 49 | template<class NNBJ> void init_jet(NNBJ * briefjet, const fastjet::PseudoJet & jet, int index) { briefjet->init(jet, index, _info);} |
---|
| 50 | private: |
---|
| 51 | I * _info; |
---|
| 52 | }; |
---|
| 53 | |
---|
| 54 | /// @ingroup advanced_usage |
---|
| 55 | /// Specialisation of NNHInfo for cases where there is no extra info |
---|
| 56 | template<> class NNHInfo<_NoInfo> { |
---|
| 57 | public: |
---|
| 58 | NNHInfo() {} |
---|
| 59 | NNHInfo(_NoInfo * ) {} |
---|
| 60 | template<class NNBJ> void init_jet(NNBJ * briefjet, const fastjet::PseudoJet & jet, int index) { briefjet->init(jet, index);} |
---|
| 61 | }; |
---|
| 62 | |
---|
| 63 | |
---|
| 64 | //---------------------------------------------------------------------- |
---|
| 65 | /// @ingroup advanced_usage |
---|
| 66 | /// \class NNH |
---|
| 67 | /// Help solve closest pair problems with generic interparticle and |
---|
| 68 | /// beam distance. |
---|
| 69 | /// |
---|
| 70 | /// Class to help solve closest pair problems with generic interparticle |
---|
| 71 | /// distances and a beam distance, using Anderberg's Nearest Neighbour |
---|
| 72 | /// Heuristic. |
---|
| 73 | /// |
---|
| 74 | /// It is templated with a BJ (brief jet) class --- BJ should |
---|
| 75 | /// basically cache the minimal amount of information that is needed |
---|
| 76 | /// to efficiently calculate interparticle distances and particle-beam |
---|
| 77 | /// distances. |
---|
| 78 | /// |
---|
| 79 | /// This class can be used with or without an extra "Information" template, |
---|
| 80 | /// i.e. NNB<BJ> or NNH<BJ,I> |
---|
| 81 | /// |
---|
| 82 | /// For the NNH<BJ> version of the class to function, BJ must provide |
---|
| 83 | /// three member functions |
---|
| 84 | /// |
---|
| 85 | /// - void BJ::init(const PseudoJet & jet); // initialise with a PseudoJet |
---|
| 86 | /// - double BJ::distance(const BJ * other_bj_jet); // distance between this and other_bj_jet |
---|
| 87 | /// - double BJ::beam_distance() ; // distance to the beam |
---|
| 88 | /// |
---|
| 89 | /// For the NNH<BJ,I> version to function, the BJ::init(...) member |
---|
| 90 | /// must accept an extra argument |
---|
| 91 | /// |
---|
| 92 | /// - void BJ::init(const PseudoJet & jet, I * info); // initialise with a PseudoJet + info |
---|
| 93 | /// |
---|
| 94 | /// where info might be a pointer to a class that contains, e.g., information |
---|
| 95 | /// about R, or other parameters of the jet algorithm |
---|
| 96 | /// |
---|
| 97 | /// For an example of how the NNH<BJ> class is used, see the Jade (and |
---|
| 98 | /// EECambridge) plugins |
---|
| 99 | /// |
---|
| 100 | /// NB: the NNH algorithm is expected N^2, but has a worst case of |
---|
| 101 | /// N^3. Many QCD problems tend to place one closer to the N^3 end of |
---|
| 102 | /// the spectrum than one would like. There is scope for further |
---|
| 103 | /// progress (cf Eppstein, Cardinal & Eppstein), nevertheless the |
---|
| 104 | /// current class is already significantly faster than standard N^3 |
---|
| 105 | /// implementations. |
---|
| 106 | /// |
---|
| 107 | /// |
---|
| 108 | /// Implementation note: this class derives from NNHInfo, which deals |
---|
| 109 | /// with storing any global information that is needed during the clustering |
---|
| 110 | |
---|
| 111 | template<class BJ, class I = _NoInfo> class NNH : public NNHInfo<I> { |
---|
| 112 | public: |
---|
| 113 | |
---|
| 114 | /// constructor with an initial set of jets (which will be assigned indices |
---|
| 115 | /// 0 ... jets.size()-1 |
---|
| 116 | NNH(const std::vector<PseudoJet> & jets) {start(jets);} |
---|
| 117 | NNH(const std::vector<PseudoJet> & jets, I * info) : NNHInfo<I>(info) {start(jets);} |
---|
| 118 | |
---|
| 119 | void start(const std::vector<PseudoJet> & jets); |
---|
| 120 | |
---|
| 121 | /// return the dij_min and indices iA, iB, for the corresponding jets. |
---|
| 122 | /// If iB < 0 then iA recombines with the beam |
---|
| 123 | double dij_min(int & iA, int & iB); |
---|
| 124 | |
---|
| 125 | /// remove the jet pointed to by index iA |
---|
| 126 | void remove_jet(int iA); |
---|
| 127 | |
---|
| 128 | /// merge the jets pointed to by indices A and B and replace them with |
---|
| 129 | /// jet, assigning it an index jet_index. |
---|
| 130 | void merge_jets(int iA, int iB, const PseudoJet & jet, int jet_index); |
---|
| 131 | |
---|
| 132 | /// a destructor |
---|
| 133 | ~NNH() { |
---|
| 134 | delete[] briefjets; |
---|
| 135 | } |
---|
| 136 | |
---|
| 137 | private: |
---|
| 138 | class NNBJ; // forward declaration |
---|
| 139 | |
---|
| 140 | /// establish the nearest neighbour for jet, and cross check constistency |
---|
| 141 | /// of distances for the other jets that are encountered. Assumes |
---|
| 142 | /// jet not contained within begin...end |
---|
| 143 | void set_NN_crosscheck(NNBJ * jet, NNBJ * begin, NNBJ * end); |
---|
| 144 | |
---|
| 145 | /// establish the nearest neighbour for jet; don't cross check other jets' |
---|
| 146 | /// distances and allow jet to be contained within begin...end |
---|
| 147 | void set_NN_nocross (NNBJ * jet, NNBJ * begin, NNBJ * end); |
---|
| 148 | |
---|
| 149 | /// contains the briefjets |
---|
| 150 | NNBJ * briefjets; |
---|
| 151 | |
---|
| 152 | /// semaphores for the current extent of our structure |
---|
| 153 | NNBJ * head, * tail; |
---|
| 154 | |
---|
| 155 | /// currently active number of jets |
---|
| 156 | int n; |
---|
| 157 | |
---|
| 158 | /// where_is[i] contains a pointer to the jet with index i |
---|
| 159 | std::vector<NNBJ *> where_is; |
---|
| 160 | |
---|
| 161 | /// a class that wraps around the BJ, supplementing it with extra information |
---|
| 162 | /// such as pointers to neighbours, etc. |
---|
| 163 | class NNBJ : public BJ { |
---|
| 164 | public: |
---|
| 165 | void init(const PseudoJet & jet, int index_in) { |
---|
| 166 | BJ::init(jet); |
---|
| 167 | other_init(index_in); |
---|
| 168 | } |
---|
| 169 | void init(const PseudoJet & jet, int index_in, I * info) { |
---|
| 170 | BJ::init(jet, info); |
---|
| 171 | other_init(index_in); |
---|
| 172 | } |
---|
| 173 | void other_init(int index_in) { |
---|
| 174 | _index = index_in; |
---|
| 175 | NN_dist = BJ::beam_distance(); |
---|
| 176 | NN = NULL; |
---|
| 177 | } |
---|
| 178 | int index() const {return _index;} |
---|
| 179 | |
---|
| 180 | double NN_dist; |
---|
| 181 | NNBJ * NN; |
---|
| 182 | |
---|
| 183 | private: |
---|
| 184 | int _index; |
---|
| 185 | }; |
---|
| 186 | |
---|
| 187 | }; |
---|
| 188 | |
---|
| 189 | |
---|
| 190 | |
---|
| 191 | //---------------------------------------------------------------------- |
---|
| 192 | template<class BJ, class I> void NNH<BJ,I>::start(const std::vector<PseudoJet> & jets) { |
---|
| 193 | n = jets.size(); |
---|
| 194 | briefjets = new NNBJ[n]; |
---|
| 195 | where_is.resize(2*n); |
---|
| 196 | |
---|
| 197 | NNBJ * jetA = briefjets; |
---|
| 198 | |
---|
| 199 | // initialise the basic jet info |
---|
| 200 | for (int i = 0; i< n; i++) { |
---|
| 201 | //jetA->init(jets[i], i); |
---|
| 202 | this->init_jet(jetA, jets[i], i); |
---|
| 203 | where_is[i] = jetA; |
---|
| 204 | jetA++; // move on to next entry of briefjets |
---|
| 205 | } |
---|
| 206 | tail = jetA; // a semaphore for the end of briefjets |
---|
| 207 | head = briefjets; // a nicer way of naming start |
---|
| 208 | |
---|
| 209 | // now initialise the NN distances: jetA will run from 1..n-1; and |
---|
| 210 | // jetB from 0..jetA-1 |
---|
| 211 | for (jetA = head + 1; jetA != tail; jetA++) { |
---|
| 212 | // set NN info for jetA based on jets running from head..jetA-1, |
---|
| 213 | // checking in the process whether jetA itself is an undiscovered |
---|
| 214 | // NN of one of those jets. |
---|
| 215 | set_NN_crosscheck(jetA, head, jetA); |
---|
| 216 | } |
---|
| 217 | //std::cout << "OOOO " << briefjets[1].NN_dist << " " << briefjets[1].NN - briefjets << std::endl; |
---|
| 218 | } |
---|
| 219 | |
---|
| 220 | |
---|
| 221 | //---------------------------------------------------------------------- |
---|
| 222 | template<class BJ, class I> double NNH<BJ,I>::dij_min(int & iA, int & iB) { |
---|
| 223 | // find the minimum of the diJ on this round |
---|
| 224 | double diJ_min = briefjets[0].NN_dist; |
---|
| 225 | int diJ_min_jet = 0; |
---|
| 226 | for (int i = 1; i < n; i++) { |
---|
| 227 | if (briefjets[i].NN_dist < diJ_min) { |
---|
| 228 | diJ_min_jet = i; |
---|
| 229 | diJ_min = briefjets[i].NN_dist; |
---|
| 230 | } |
---|
| 231 | } |
---|
| 232 | |
---|
| 233 | // return information to user about recombination |
---|
| 234 | NNBJ * jetA = & briefjets[diJ_min_jet]; |
---|
| 235 | //std::cout << jetA - briefjets << std::endl; |
---|
| 236 | iA = jetA->index(); |
---|
| 237 | iB = jetA->NN ? jetA->NN->index() : -1; |
---|
| 238 | return diJ_min; |
---|
| 239 | } |
---|
| 240 | |
---|
| 241 | |
---|
| 242 | //---------------------------------------------------------------------- |
---|
| 243 | // remove jetA from the list |
---|
| 244 | template<class BJ, class I> void NNH<BJ,I>::remove_jet(int iA) { |
---|
| 245 | NNBJ * jetA = where_is[iA]; |
---|
| 246 | // now update our nearest neighbour info and diJ table |
---|
| 247 | // first reduce size of table |
---|
| 248 | tail--; n--; |
---|
| 249 | // Copy last jet contents and diJ info into position of jetA |
---|
| 250 | *jetA = *tail; |
---|
| 251 | // update the info on where the given index is stored |
---|
| 252 | where_is[jetA->index()] = jetA; |
---|
| 253 | |
---|
| 254 | for (NNBJ * jetI = head; jetI != tail; jetI++) { |
---|
| 255 | // see if jetI had jetA or jetB as a NN -- if so recalculate the NN |
---|
| 256 | if (jetI->NN == jetA) set_NN_nocross(jetI, head, tail); |
---|
| 257 | |
---|
| 258 | // if jetI's NN is the new tail then relabel it so that it becomes jetA |
---|
| 259 | if (jetI->NN == tail) {jetI->NN = jetA;} |
---|
| 260 | } |
---|
| 261 | } |
---|
| 262 | |
---|
| 263 | |
---|
| 264 | //---------------------------------------------------------------------- |
---|
| 265 | template<class BJ, class I> void NNH<BJ,I>::merge_jets(int iA, int iB, |
---|
| 266 | const PseudoJet & jet, int index) { |
---|
| 267 | |
---|
| 268 | NNBJ * jetA = where_is[iA]; |
---|
| 269 | NNBJ * jetB = where_is[iB]; |
---|
| 270 | |
---|
| 271 | // If necessary relabel A & B to ensure jetB < jetA, that way if |
---|
| 272 | // the larger of them == newtail then that ends up being jetA and |
---|
| 273 | // the new jet that is added as jetB is inserted in a position that |
---|
| 274 | // has a future! |
---|
| 275 | if (jetA < jetB) std::swap(jetA,jetB); |
---|
| 276 | |
---|
| 277 | // initialise jetB based on the new jet |
---|
| 278 | //jetB->init(jet, index); |
---|
| 279 | this->init_jet(jetB, jet, index); |
---|
| 280 | // and record its position (making sure we have the space) |
---|
| 281 | if (index >= int(where_is.size())) where_is.resize(2*index); |
---|
| 282 | where_is[jetB->index()] = jetB; |
---|
| 283 | |
---|
| 284 | // now update our nearest neighbour info |
---|
| 285 | // first reduce size of table |
---|
| 286 | tail--; n--; |
---|
| 287 | // Copy last jet contents into position of jetA |
---|
| 288 | *jetA = *tail; |
---|
| 289 | // update the info on where the tail's index is stored |
---|
| 290 | where_is[jetA->index()] = jetA; |
---|
| 291 | |
---|
| 292 | for (NNBJ * jetI = head; jetI != tail; jetI++) { |
---|
| 293 | // see if jetI had jetA or jetB as a NN -- if so recalculate the NN |
---|
| 294 | if (jetI->NN == jetA || jetI->NN == jetB) { |
---|
| 295 | set_NN_nocross(jetI, head, tail); |
---|
| 296 | } |
---|
| 297 | |
---|
| 298 | // check whether new jetB is closer than jetI's current NN and |
---|
| 299 | // if need be update things |
---|
| 300 | double dist = jetI->distance(jetB); |
---|
| 301 | if (dist < jetI->NN_dist) { |
---|
| 302 | if (jetI != jetB) { |
---|
| 303 | jetI->NN_dist = dist; |
---|
| 304 | jetI->NN = jetB; |
---|
| 305 | } |
---|
| 306 | } |
---|
| 307 | if (dist < jetB->NN_dist) { |
---|
| 308 | if (jetI != jetB) { |
---|
| 309 | jetB->NN_dist = dist; |
---|
| 310 | jetB->NN = jetI; |
---|
| 311 | } |
---|
| 312 | } |
---|
| 313 | |
---|
| 314 | // if jetI's NN is the new tail then relabel it so that it becomes jetA |
---|
| 315 | if (jetI->NN == tail) {jetI->NN = jetA;} |
---|
| 316 | } |
---|
| 317 | } |
---|
| 318 | |
---|
| 319 | |
---|
| 320 | //---------------------------------------------------------------------- |
---|
| 321 | // this function assumes that jet is not contained within begin...end |
---|
| 322 | template <class BJ, class I> void NNH<BJ,I>::set_NN_crosscheck(NNBJ * jet, |
---|
| 323 | NNBJ * begin, NNBJ * end) { |
---|
| 324 | double NN_dist = jet->beam_distance(); |
---|
| 325 | NNBJ * NN = NULL; |
---|
| 326 | for (NNBJ * jetB = begin; jetB != end; jetB++) { |
---|
| 327 | double dist = jet->distance(jetB); |
---|
| 328 | if (dist < NN_dist) { |
---|
| 329 | NN_dist = dist; |
---|
| 330 | NN = jetB; |
---|
| 331 | } |
---|
| 332 | if (dist < jetB->NN_dist) { |
---|
| 333 | jetB->NN_dist = dist; |
---|
| 334 | jetB->NN = jet; |
---|
| 335 | } |
---|
| 336 | } |
---|
| 337 | jet->NN = NN; |
---|
| 338 | jet->NN_dist = NN_dist; |
---|
| 339 | } |
---|
| 340 | |
---|
| 341 | |
---|
| 342 | //---------------------------------------------------------------------- |
---|
| 343 | // set the NN for jet without checking whether in the process you might |
---|
| 344 | // have discovered a new nearest neighbour for another jet |
---|
| 345 | template <class BJ, class I> void NNH<BJ,I>::set_NN_nocross( |
---|
| 346 | NNBJ * jet, NNBJ * begin, NNBJ * end) { |
---|
| 347 | double NN_dist = jet->beam_distance(); |
---|
| 348 | NNBJ * NN = NULL; |
---|
| 349 | // if (head < jet) { |
---|
| 350 | // for (NNBJ * jetB = head; jetB != jet; jetB++) { |
---|
| 351 | if (begin < jet) { |
---|
| 352 | for (NNBJ * jetB = begin; jetB != jet; jetB++) { |
---|
| 353 | double dist = jet->distance(jetB); |
---|
| 354 | if (dist < NN_dist) { |
---|
| 355 | NN_dist = dist; |
---|
| 356 | NN = jetB; |
---|
| 357 | } |
---|
| 358 | } |
---|
| 359 | } |
---|
| 360 | // if (tail > jet) { |
---|
| 361 | // for (NNBJ * jetB = jet+1; jetB != tail; jetB++) { |
---|
| 362 | if (end > jet) { |
---|
| 363 | for (NNBJ * jetB = jet+1; jetB != end; jetB++) { |
---|
| 364 | double dist = jet->distance (jetB); |
---|
| 365 | if (dist < NN_dist) { |
---|
| 366 | NN_dist = dist; |
---|
| 367 | NN = jetB; |
---|
| 368 | } |
---|
| 369 | } |
---|
| 370 | } |
---|
| 371 | jet->NN = NN; |
---|
| 372 | jet->NN_dist = NN_dist; |
---|
| 373 | } |
---|
| 374 | |
---|
| 375 | |
---|
| 376 | |
---|
| 377 | |
---|
| 378 | FASTJET_END_NAMESPACE // defined in fastjet/internal/base.hh |
---|
| 379 | |
---|
| 380 | |
---|
| 381 | #endif // __NNH_HH__ |
---|