PatUtils/interface/GenericOverlapFinder.h

0001 #ifndef PhysicsTools_PatUtils_GenericOverlapFinder_h
0002 #define PhysicsTools_PatUtils_GenericOverlapFinder_h
0003
0004 #include "DataFormats/Math/interface/deltaR.h"
0005
0006 #include <memory>
0007 #include <vector>
0008 #include <algorithm>
0009
0010 namespace pat {
0011
0012   /// A vector of pairs of indices <i1,i2>, for each i1 that overlaps,
0013   /// i2 is the "best" overlap match.
0014   /// if an element of does not overlap with anyone, it will not end up in this list.
0015   typedef std::vector<std::pair<size_t, size_t> > OverlapList;
0016
0017   /// Turn a comparator in a distance for uses of overlap
0018   ///    comparator(x,y) = true <-> x and y overlap
0019   /// the associated distance would work as
0020   ///     dist(x,y) = 1.0 - comparator(x,y)   [0 if overlap, 1 otherwise]
0021   /// if the constructor of your Comparator does not need parameters,
0022   /// then the associated distance will not need parameters too.
0023   template <typename Comparator>
0024   struct OverlapDistance {
0025   public:
0026     OverlapDistance() {}
0027     OverlapDistance(const Comparator &comp) : comp_(comp) {}
0028     template <typename T1, typename T2>
0029     double operator()(const T1 &t1, const T2 &t2) const {
0030       return 1.0 - comp_(t1, t2);
0031     }
0032
0033   private:
0034     Comparator comp_;
0035   };  //struct
0036
0037   /// Distance with deltaR metrics and a fixed maximum for the overlap deltaR
0038   ///   dist(x,y) = deltaR2(x,y) / deltaR2cut;
0039   struct OverlapByDeltaR {
0040   public:
0041     OverlapByDeltaR(double deltaR) : scale_(1.0 / (deltaR * deltaR)) {}
0042     template <typename T1, typename T2>
0043     double operator()(const T1 &t1, const T2 &t2) const {
0044       return deltaR2(t1, t2) * scale_;
0045     }
0046
0047   private:
0048     double scale_;
0049   };  //struct
0050
0051   template <typename Distance>
0052   class GenericOverlapFinder {
0053   public:
0054     GenericOverlapFinder() {}
0055     GenericOverlapFinder(const Distance &dist) : distance_(dist) {}
0056
0057     /// Indices of overlapped items, and of the nearest item on they overlap with
0058     /// Items are considered to overlap if distance(x1,x2) < 1
0059     /// both Collections can be vectors, Views, or anything with the same interface
0060     template <typename Collection, typename OtherCollection>
0061     std::unique_ptr<OverlapList> find(const Collection &items, const OtherCollection &other) const;
0062
0063   private:
0064     Distance distance_;
0065
0066   };  // class
0067 }  // namespace pat
0068
0069 template <typename Distance>
0070 template <typename Collection, typename OtherCollection>
0071 std::unique_ptr<pat::OverlapList> pat::GenericOverlapFinder<Distance>::find(const Collection &items,
0072                                                                             const OtherCollection &other) const {
0073   size_t size = items.size(), size2 = other.size();
0074
0075   auto ret = std::make_unique<OverlapList>();
0076
0077   for (size_t ie = 0; ie < size; ++ie) {
0078     double dmin = 1.0;
0079     size_t match = 0;
0080
0081     for (size_t je = 0; je < size2; ++je) {
0082       double dist = distance_(items[ie], other[je]);
0083       if (dist < dmin) {
0084         match = je;
0085         dmin = dist;
0086       }
0087     }
0088
0089     if (dmin < 1.0) {
0090       ret->push_back(std::make_pair(ie, match));
0091     }
0092   }
0093
0094   return ret;
0095 }
0096
0097 #endif