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