Go to the documentation of this file.00001 #ifndef PhysicsTools_PatUtils_GenericDuplicateRemover_h
00002 #define PhysicsTools_PatUtils_GenericDuplicateRemover_h
00003
00004 #include <memory>
00005 #include <vector>
00006 #include <sys/types.h>
00007
00008 namespace pat {
00009
00010 template <typename Comparator, typename Arbitrator>
00011 class GenericDuplicateRemover {
00012
00013 public:
00014
00015 GenericDuplicateRemover() {}
00016 GenericDuplicateRemover(const Comparator &comp) : comparator_(comp) {}
00017 GenericDuplicateRemover(const Comparator &comp, const Arbitrator &arbiter) : comparator_(comp), arbiter_(arbiter) {}
00018
00019 ~GenericDuplicateRemover() {}
00020
00026 template <typename Collection>
00027 std::auto_ptr< std::vector<size_t> >
00028 duplicates(const Collection &items) const ;
00029
00030 private:
00031 Comparator comparator_;
00032 Arbitrator arbiter_;
00033
00034 };
00035 }
00036
00037 template<typename Comparator, typename Arbitrator>
00038 template<typename Collection>
00039 std::auto_ptr< std::vector<size_t> >
00040 pat::GenericDuplicateRemover<Comparator,Arbitrator>::duplicates(const Collection &items) const
00041 {
00042 size_t size = items.size();
00043
00044 std::vector<bool> bad(size, false);
00045
00046 for (size_t ie = 0; ie < size; ++ie) {
00047 if (bad[ie]) continue;
00048
00049 for (size_t je = ie+1; je < size; ++je) {
00050
00051 if (bad[je]) continue;
00052
00053 if ( comparator_(items[ie], items[je]) ) {
00054 int toRemove = arbiter_(items[ie], items[je]) ? je : ie;
00055 bad[toRemove] = true;
00056 }
00057 }
00058 }
00059
00060 std::auto_ptr< std::vector<size_t> > ret(new std::vector<size_t>());
00061
00062 for (size_t i = 0; i < size; ++i) {
00063 if (bad[i]) ret->push_back(i);
00064 }
00065
00066 return ret;
00067 }
00068
00069
00070 #endif