GenericDuplicateRemover.h

Go to the documentation of this file.

#ifndef PhysicsTools_PatUtils_GenericDuplicateRemover_h
#define PhysicsTools_PatUtils_GenericDuplicateRemover_h
 
#include <memory>
#include <vector>
#include <sys/types.h>
 
namespace pat {
 
  template <typename Comparator, typename Arbitrator>
  class GenericDuplicateRemover {
  public:
    GenericDuplicateRemover() {}
    GenericDuplicateRemover(const Comparator &comp) : comparator_(comp) {}
    GenericDuplicateRemover(const Comparator &comp, const Arbitrator &arbiter) : comparator_(comp), arbiter_(arbiter) {}
 
    ~GenericDuplicateRemover() {}
 
    template <typename Collection>
    std::unique_ptr<std::vector<size_t>> duplicates(const Collection &items) const;
 
  private:
    Comparator comparator_;
    Arbitrator arbiter_;
 
  };  // class
}  // namespace pat
 
template <typename Comparator, typename Arbitrator>
template <typename Collection>
std::unique_ptr<std::vector<size_t>> pat::GenericDuplicateRemover<Comparator, Arbitrator>::duplicates(
    const Collection &items) const {
  size_t size = items.size();
 
  std::vector<bool> bad(size, false);
 
  for (size_t ie = 0; ie < size; ++ie) {
    if (bad[ie])
      continue;  // if already marked bad
 
    for (size_t je = ie + 1; je < size; ++je) {
      if (bad[je])
        continue;  // if already marked bad
 
      if (comparator_(items[ie], items[je])) {
        int toRemove = arbiter_(items[ie], items[je]) ? je : ie;
        bad[toRemove] = true;
      }
    }
  }
 
  auto ret = std::make_unique<std::vector<size_t>>();
 
  for (size_t i = 0; i < size; ++i) {
    if (bad[i])
      ret->push_back(i);
  }
 
  return ret;
}
 
#endif