File indexing completed on 2024-04-06 12:09:48
0001 #ifndef RecoBTag_Analysis_Matching_h
0002 #define RecoBTag_Analysis_Matching_h
0003
0004 #include <algorithm>
0005 #include <vector>
0006 #include <set>
0007
0008 #include "SimpleMatrix.h"
0009
0010 namespace btag {
0011
0012 template <typename Delta>
0013 class Matching {
0014 public:
0015 typedef typename SimpleMatrix<Delta>::size_type index_type;
0016
0017 template <typename V1, typename V2, class Separation>
0018 Matching(const V1 &v1, const V2 &v2, Separation separation)
0019 : matrix(v1.size(), v2.size()), matched1(v1.size(), false), matched2(v2.size(), false) {
0020 index_type i = 0;
0021 for (typename V1::const_iterator iter1 = v1.begin(); iter1 != v1.end(); ++iter1, ++i) {
0022 index_type j = 0;
0023 for (typename V2::const_iterator iter2 = v2.begin(); iter2 != v2.end(); ++iter2, ++j)
0024 matrix(i, j) = separation(*iter1, *iter2);
0025 }
0026 }
0027
0028 struct Match {
0029 typedef typename Matching::index_type index_type;
0030
0031 inline Match(index_type i1, index_type i2) : index1(i1), index2(i2) {}
0032
0033 index_type index1, index2;
0034 };
0035
0036 inline Delta delta(index_type index1, index_type index2) const { return matrix(index1, index2); }
0037
0038 inline Delta delta(Match match) const { return matrix(match.index1, match.index2); }
0039
0040 private:
0041 template <class SortComparator>
0042 struct Comparator {
0043 typedef typename Matching::index_type index_type;
0044
0045 inline Comparator(const SimpleMatrix<Delta> &matrix, SortComparator &sort) : matrix(matrix), sort(sort) {}
0046
0047 inline bool operator()(index_type i1, index_type i2) const { return sort(matrix[i1], matrix[i2]); }
0048
0049 const SimpleMatrix<Delta> &matrix;
0050 SortComparator &sort;
0051 };
0052
0053 struct AlwaysTrue {
0054 inline bool operator()(Delta dummy) { return true; }
0055 };
0056
0057 public:
0058 template <class SortComparator, class CutCriterion>
0059 std::vector<Match> match(SortComparator sortComparator = SortComparator(),
0060 CutCriterion cutCriterion = CutCriterion()) {
0061 std::vector<index_type> matches(matrix.size());
0062 for (index_type i = 0; i != matrix.size(); ++i)
0063 matches[i] = i;
0064
0065 std::sort(matches.begin(), matches.end(), Comparator<SortComparator>(matrix, sortComparator));
0066
0067 std::vector<Match> result;
0068 result.reserve(std::min(matrix.rows(), matrix.cols()));
0069 for (typename std::vector<index_type>::const_iterator iter = matches.begin(); iter != matches.end(); ++iter) {
0070 index_type row = matrix.row(*iter);
0071 index_type col = matrix.col(*iter);
0072 if (matched1[row] || matched2[col])
0073 continue;
0074
0075 if (!cutCriterion(matrix[*iter]))
0076 continue;
0077
0078 matched1[row] = true;
0079 matched2[col] = true;
0080 result.push_back(Match(row, col));
0081 }
0082
0083 return result;
0084 }
0085
0086 template <class SortComparator>
0087 inline std::vector<Match> match() {
0088 return match<SortComparator, AlwaysTrue>();
0089 }
0090
0091 inline std::vector<Match> match() { return match<std::less<Delta>, AlwaysTrue>(); }
0092
0093 inline bool isMatched1st(index_type index) { return matched1[index]; }
0094 inline bool isMatched2nd(index_type index) { return matched2[index]; }
0095
0096 private:
0097 SimpleMatrix<Delta> matrix;
0098 std::vector<bool> matched1, matched2;
0099 };
0100
0101 }
0102
0103 #endif