CMS 3D CMS Logo

/data/refman/pasoursint/CMSSW_6_1_2_SLHC2/src/PhysicsTools/PatUtils/interface/GenericDuplicateRemover.h

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     }; // class
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; // if already marked bad
00048 
00049         for (size_t je = ie+1; je < size; ++je) {
00050 
00051             if (bad[je]) continue; // if already marked bad
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