PatUtils/interface/GenericDuplicateRemover.h

0001 #ifndef PhysicsTools_PatUtils_GenericDuplicateRemover_h
0002 #define PhysicsTools_PatUtils_GenericDuplicateRemover_h
0003
0004 #include <memory>
0005 #include <vector>
0006 #include <sys/types.h>
0007
0008 namespace pat {
0009
0010   template <typename Comparator, typename Arbitrator>
0011   class GenericDuplicateRemover {
0012   public:
0013     GenericDuplicateRemover() {}
0014     GenericDuplicateRemover(const Comparator &comp) : comparator_(comp) {}
0015     GenericDuplicateRemover(const Comparator &comp, const Arbitrator &arbiter) : comparator_(comp), arbiter_(arbiter) {}
0016
0017     ~GenericDuplicateRemover() {}
0018
0019     /// Indices of duplicated items to remove
0020     /// Comparator is used to check for duplication, Arbiter to pick the best one
0021     /// e.g. comparator(x1, x2) should return true if they are duplicates
0022     ///      arbitrator(x1, x2) should return true if x1 is better, that is we want to keep x1 and delete x2
0023     /// Collection can be vector, View, or anything with the same interface
0024     template <typename Collection>
0025     std::unique_ptr<std::vector<size_t>> duplicates(const Collection &items) const;
0026
0027   private:
0028     Comparator comparator_;
0029     Arbitrator arbiter_;
0030
0031   };  // class
0032 }  // namespace pat
0033
0034 template <typename Comparator, typename Arbitrator>
0035 template <typename Collection>
0036 std::unique_ptr<std::vector<size_t>> pat::GenericDuplicateRemover<Comparator, Arbitrator>::duplicates(
0037     const Collection &items) const {
0038   size_t size = items.size();
0039
0040   std::vector<bool> bad(size, false);
0041
0042   for (size_t ie = 0; ie < size; ++ie) {
0043     if (bad[ie])
0044       continue;  // if already marked bad
0045
0046     for (size_t je = ie + 1; je < size; ++je) {
0047       if (bad[je])
0048         continue;  // if already marked bad
0049
0050       if (comparator_(items[ie], items[je])) {
0051         int toRemove = arbiter_(items[ie], items[je]) ? je : ie;
0052         bad[toRemove] = true;
0053       }
0054     }
0055   }
0056
0057   auto ret = std::make_unique<std::vector<size_t>>();
0058
0059   for (size_t i = 0; i < size; ++i) {
0060     if (bad[i])
0061       ret->push_back(i);
0062   }
0063
0064   return ret;
0065 }
0066
0067 #endif