FFTJetAlgorithms/interface/matchOneToOne.h

0001 //
0002 // Utility function for matching elements of one vector to another
0003 // using best matching distance. All pairwise distances are calculated
0004 // and then sorted; the best match corresponds to the smallest
0005 // distance. Both matched elements are removed from the pool,
0006 // then the best match is found among the remaining elements, etc.
0007 //
0008 // I. Volobouev
0009 // April 2008
0010
0011 #ifndef RecoJets_FFTJetAlgorithms_matchOneToOne_h
0012 #define RecoJets_FFTJetAlgorithms_matchOneToOne_h
0013
0014 #include <vector>
0015 #include <algorithm>
0016
0017 namespace fftjetcms {
0018   namespace Private {
0019     struct matchOneToOne_MatchInfo {
0020       double distance;
0021       unsigned i1;
0022       unsigned i2;
0023
0024       inline bool operator<(const matchOneToOne_MatchInfo& r) const { return distance < r.distance; }
0025
0026       inline bool operator>(const matchOneToOne_MatchInfo& r) const { return distance > r.distance; }
0027     };
0028   }  // namespace Private
0029
0030   //
0031   // (*matchFrom1To2)[idx] will be set to the index of the element in v2
0032   // which corresponds to the element at index "idx" in v1. If no match
0033   // to the element at index "idx" in v1 is found, (*matchFrom1To2)[idx]
0034   // is set to -1. All non-negative (*matchFrom1To2)[idx] values will be
0035   // unique. The function returns the total number of matches made.
0036   //
0037   template <class T1, class T2, class DistanceCalculator>
0038   unsigned matchOneToOne(const std::vector<T1>& v1,
0039                          const std::vector<T2>& v2,
0040                          const DistanceCalculator& calc,
0041                          std::vector<int>* matchFrom1To2,
0042                          const double maxMatchingDistance = 1.0e300) {
0043     unsigned nused = 0;
0044     matchFrom1To2->clear();
0045
0046     const unsigned n1 = v1.size();
0047     if (n1) {
0048       matchFrom1To2->reserve(n1);
0049       for (unsigned i1 = 0; i1 < n1; ++i1)
0050         matchFrom1To2->push_back(-1);
0051
0052       const unsigned n2 = v2.size();
0053       if (n2) {
0054         const unsigned nmatches = n1 * n2;
0055         std::vector<Private::matchOneToOne_MatchInfo> distanceTable(nmatches);
0056         std::vector<int> taken2(n2);
0057
0058         for (unsigned i2 = 0; i2 < n2; ++i2)
0059           taken2[i2] = 0;
0060
0061         Private::matchOneToOne_MatchInfo* m;
0062         for (unsigned i1 = 0; i1 < n1; ++i1)
0063           for (unsigned i2 = 0; i2 < n2; ++i2) {
0064             m = &distanceTable[i1 * n2 + i2];
0065             m->distance = calc(v1[i1], v2[i2]);
0066             m->i1 = i1;
0067             m->i2 = i2;
0068           }
0069
0070         std::sort(distanceTable.begin(), distanceTable.end());
0071         for (unsigned i = 0; i < nmatches && nused < n1 && nused < n2; ++i) {
0072           m = &distanceTable[i];
0073           if (m->distance > maxMatchingDistance)
0074             break;
0075           if ((*matchFrom1To2)[m->i1] < 0 && !taken2[m->i2]) {
0076             (*matchFrom1To2)[m->i1] = static_cast<int>(m->i2);
0077             taken2[m->i2] = 1;
0078             ++nused;
0079           }
0080         }
0081       }
0082     }
0083
0084     return nused;
0085   }
0086 }  // namespace fftjetcms
0087
0088 #endif  // RecoJets_FFTJetAlgorithms_matchOneToOne_h