CMS 3D CMS Logo

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Pages
matchOneToOne.h
Go to the documentation of this file.
1 //
2 // Utility function for matching elements of one vector to another
3 // using best matching distance. All pairwise distances are calculated
4 // and then sorted; the best match corresponds to the smallest
5 // distance. Both matched elements are removed from the pool,
6 // then the best match is found among the remaining elements, etc.
7 //
8 // I. Volobouev
9 // April 2008
10 
11 #ifndef RecoJets_FFTJetAlgorithms_matchOneToOne_h
12 #define RecoJets_FFTJetAlgorithms_matchOneToOne_h
13 
14 #include <vector>
15 #include <algorithm>
16 
17 namespace fftjetcms {
18  namespace Private {
20  {
21  double distance;
22  unsigned i1;
23  unsigned i2;
24 
25  inline bool operator<(const matchOneToOne_MatchInfo& r) const
26  {return distance < r.distance;}
27 
28  inline bool operator>(const matchOneToOne_MatchInfo& r) const
29  {return distance > r.distance;}
30  };
31  }
32 
33  //
34  // (*matchFrom1To2)[idx] will be set to the index of the element in v2
35  // which corresponds to the element at index "idx" in v1. If no match
36  // to the element at index "idx" in v1 is found, (*matchFrom1To2)[idx]
37  // is set to -1. All non-negative (*matchFrom1To2)[idx] values will be
38  // unique. The function returns the total number of matches made.
39  //
40  template <class T1, class T2, class DistanceCalculator>
41  unsigned matchOneToOne(const std::vector<T1>& v1, const std::vector<T2>& v2,
42  const DistanceCalculator& calc,
43  std::vector<int>* matchFrom1To2,
44  const double maxMatchingDistance = 1.0e300)
45  {
46  unsigned nused = 0;
47  matchFrom1To2->clear();
48 
49  const unsigned n1 = v1.size();
50  if (n1)
51  {
52  matchFrom1To2->reserve(n1);
53  for (unsigned i1=0; i1<n1; ++i1)
54  matchFrom1To2->push_back(-1);
55 
56  const unsigned n2 = v2.size();
57  if (n2)
58  {
59  const unsigned nmatches = n1*n2;
60  std::vector<Private::matchOneToOne_MatchInfo> distanceTable(nmatches);
61  std::vector<int> taken2(n2);
62 
63  for (unsigned i2=0; i2<n2; ++i2)
64  taken2[i2] = 0;
65 
67  for (unsigned i1=0; i1<n1; ++i1)
68  for (unsigned i2=0; i2<n2; ++i2)
69  {
70  m = &distanceTable[i1*n2+i2];
71  m->distance = calc(v1[i1], v2[i2]);
72  m->i1 = i1;
73  m->i2 = i2;
74  }
75 
76  std::sort(distanceTable.begin(), distanceTable.end());
77  for (unsigned i=0; i<nmatches && nused<n1 && nused<n2; ++i)
78  {
79  m = &distanceTable[i];
80  if (m->distance > maxMatchingDistance)
81  break;
82  if ((*matchFrom1To2)[m->i1] < 0 && !taken2[m->i2])
83  {
84  (*matchFrom1To2)[m->i1] = static_cast<int>(m->i2);
85  taken2[m->i2] = 1;
86  ++nused;
87  }
88  }
89  }
90  }
91 
92  return nused;
93  }
94 }
95 
96 #endif // RecoJets_FFTJetAlgorithms_matchOneToOne_h
unsigned matchOneToOne(const std::vector< T1 > &v1, const std::vector< T2 > &v2, const DistanceCalculator &calc, std::vector< int > *matchFrom1To2, const double maxMatchingDistance=1.0e300)
Definition: matchOneToOne.h:41
bool operator<(const matchOneToOne_MatchInfo &r) const
Definition: matchOneToOne.h:25
bool operator>(const matchOneToOne_MatchInfo &r) const
Definition: matchOneToOne.h:28