Matching.h

Go to the documentation of this file.

#ifndef RecoBTag_Analysis_Matching_h
#define RecoBTag_Analysis_Matching_h
 
#include <algorithm>
#include <vector>
#include <set>
 
#include "SimpleMatrix.h"
 
namespace btag {
 
  template <typename Delta>
  class Matching {
  public:
    typedef typename SimpleMatrix<Delta>::size_type index_type;
 
    template <typename V1, typename V2, class Separation>
    Matching(const V1 &v1, const V2 &v2, Separation separation)
        : matrix(v1.size(), v2.size()), matched1(v1.size(), false), matched2(v2.size(), false) {
      index_type i = 0;
      for (typename V1::const_iterator iter1 = v1.begin(); iter1 != v1.end(); ++iter1, ++i) {
        index_type j = 0;
        for (typename V2::const_iterator iter2 = v2.begin(); iter2 != v2.end(); ++iter2, ++j)
          matrix(i, j) = separation(*iter1, *iter2);
      }
    }
 
    struct Match {
      typedef typename Matching::index_type index_type;
 
      inline Match(index_type i1, index_type i2) : index1(i1), index2(i2) {}
 
      index_type index1, index2;
    };
 
    inline Delta delta(index_type index1, index_type index2) const { return matrix(index1, index2); }
 
    inline Delta delta(Match match) const { return matrix(match.index1, match.index2); }
 
  private:
    template <class SortComparator>
    struct Comparator {
      typedef typename Matching::index_type index_type;
 
      inline Comparator(const SimpleMatrix<Delta> &matrix, SortComparator &sort) : matrix(matrix), sort(sort) {}
 
      inline bool operator()(index_type i1, index_type i2) const { return sort(matrix[i1], matrix[i2]); }
 
      const SimpleMatrix<Delta> &matrix;
      SortComparator &sort;
    };
 
    struct AlwaysTrue {
      inline bool operator()(Delta dummy) { return true; }
    };
 
  public:
    template <class SortComparator, class CutCriterion>
    std::vector<Match> match(SortComparator sortComparator = SortComparator(),
                             CutCriterion cutCriterion = CutCriterion()) {
      std::vector<index_type> matches(matrix.size());
      for (index_type i = 0; i != matrix.size(); ++i)
        matches[i] = i;
 
      std::sort(matches.begin(), matches.end(), Comparator<SortComparator>(matrix, sortComparator));
 
      std::vector<Match> result;
      result.reserve(std::min(matrix.rows(), matrix.cols()));
      for (typename std::vector<index_type>::const_iterator iter = matches.begin(); iter != matches.end(); ++iter) {
        index_type row = matrix.row(*iter);
        index_type col = matrix.col(*iter);
        if (matched1[row] || matched2[col])
          continue;
 
        if (!cutCriterion(matrix[*iter]))
          continue;
 
        matched1[row] = true;
        matched2[col] = true;
        result.push_back(Match(row, col));
      }
 
      return result;
    }
 
    template <class SortComparator>
    inline std::vector<Match> match() {
      return match<SortComparator, AlwaysTrue>();
    }
 
    inline std::vector<Match> match() { return match<std::less<Delta>, AlwaysTrue>(); }
 
    inline bool isMatched1st(index_type index) { return matched1[index]; }
    inline bool isMatched2nd(index_type index) { return matched2[index]; }
 
  private:
    SimpleMatrix<Delta> matrix;
    std::vector<bool> matched1, matched2;
  };
 
}  // namespace btag
 
#endif  // GeneratorEvent_Analysis_Matching_h