CMS 3D CMS Logo

/data/refman/pasoursint/CMSSW_5_3_1/src/RecoTauTag/RecoTau/interface/CombinatoricGenerator.h

Go to the documentation of this file.
00001 #ifndef RecoTauTag_RecoTau_CombinatoricGenerator_h
00002 #define RecoTauTag_RecoTau_CombinatoricGenerator_h
00003 
00004 #include <boost/iterator/iterator_facade.hpp>
00005 #include <boost/iterator/filter_iterator.hpp>
00006 #include <boost/iterator/transform_iterator.hpp>
00007 #include <vector>
00008 #include <set>
00009 #include <memory>
00010 #include <iostream>
00011 
00012 /*
00013  * CombinatoricGenerator
00014  *
00015  * Author: Evan K. Friis (UC Davis)
00016  *
00017  * Generic classes to compute combinatoric subsets of collections.
00018  *
00019  * Example of use:
00020  *
00021  * vector<int> collection = [0, 1, 2, 3, 4, 5];
00022  *
00023  * typedef CombinatoricGenerator<std::vector<int> Generator;
00024  *
00025  * // Select three element combinations of collection
00026  * Generator generator(collection.begin(), collection.end(), 3);
00027  *
00028  * for(Generator::iterator combo = generator.begin(); combo != generator.end(); ++combo)
00029  * {
00030  *     for(Generator::combo_iterator element = combo->begin(); element != combo->end(); ++element)
00031  *     {
00032  *         cout << *element << " ";
00033  *     }
00034  *     cout << endl;
00035  * }
00036  *
00037  * Outputs:
00038  * 0 1 2
00039  * 0 1 3
00040  * 0 1 4
00041  * ...
00042  * 3 4 5
00043  *
00044  * $Id $
00045  *
00046  */
00047 
00048 namespace reco { namespace tau {
00049 
00050 template <typename T>
00051   class Combinatoric
00052   {
00053     /* Combinatoric<T>
00054      *
00055      * Class that represents a subset of values from a collection of type T.
00056      *
00057      * The values belonging to the current combination subset can be accessed with the iterators
00058      * combo_begin() and combo_end()
00059      *
00060      * The values in the collection not in the subset can be accessed with
00061      * remainder_begin() and remainder_end()
00062      *
00063      */
00064 
00065     // Iterator over input collection
00066     typedef typename T::const_iterator value_iter;
00067     typedef typename T::value_type value_type;
00068     typedef size_t index_type;
00069     typedef typename std::vector<index_type> indices_collection;
00070     typedef typename indices_collection::const_iterator index_iter;
00071     typedef typename std::set<index_type> indices_set;
00072 
00073     class IndexInSet {
00074       /* Determine if a given index is in a set of indices */
00075       public:
00076         IndexInSet(const indices_set& combo, bool negate):
00077           combo_(combo),negate_(negate){}
00078         bool operator()(const index_type& index) const {
00079           return (negate_) ? !combo_.count(index) : combo_.count(index);
00080         }
00081       private:
00082         indices_set combo_;
00083         bool negate_;
00084     };
00085 
00086     class ValueAccessor : public std::unary_function<index_type const&, const value_type&>
00087     {
00088       /* Class to extract a value from a collection given the beginning of the collection
00089        * and the index into the colleciton */
00090       public:
00091         ValueAccessor(const value_iter& begin):
00092           begin_(begin){}
00093         const value_type& operator()(index_type const & index) const {
00094           return *(begin_+index);
00095         }
00096       private:
00097         value_iter begin_;
00098     };
00099 
00100     public:
00101 
00102     Combinatoric(const value_iter& begin, const indices_collection& indices,
00103         indices_collection combo, bool done):
00104       begin_(begin), combo_(combo.begin(), combo.end()),
00105       comboSet_(combo.begin(), combo.end()),
00106       indices_(indices),
00107       done_(done),
00108       valueAccessor_(begin), inChoice_(comboSet_, false),
00109       notInChoice_(comboSet_, true) {}
00110 
00111     typedef typename boost::filter_iterator<IndexInSet, index_iter> ComboIter;
00112     typedef typename boost::transform_iterator<ValueAccessor, ComboIter> ValueIter;
00113 
00115     ValueIter combo_begin() const { return ValueIter(ComboIter(inChoice_, indices_.begin(), indices_.end()), valueAccessor_); }
00117     ValueIter combo_end() const { return ValueIter(ComboIter(inChoice_, indices_.end(), indices_.end()), valueAccessor_); }
00118 
00120     ValueIter remainder_end() const { return ValueIter(ComboIter(notInChoice_, indices_.end(), indices_.end()), valueAccessor_); }
00122     ValueIter remainder_begin() const { return ValueIter(ComboIter(notInChoice_, indices_.begin(), indices_.end()), valueAccessor_); }
00123 
00125     Combinatoric<T> next() const
00126     {
00127       //std::cout << "building next: " << std::endl;
00128       //std::cout << "current " << std::endl;
00129       //std::copy(combo_.begin(), combo_.end(), std::ostream_iterator<int>(std::cout, " "));
00130       //std::cout << std::endl;
00131 
00132       indices_collection newCombo(combo_);
00133 
00134       // Find the first value that can be updated (starting from the back
00135       // max value for index is (nElements-1) - (distance from end)
00136       // Examples:
00137       //    189 -> 289 (will be updated to 234)
00138       //    179 -> 189
00139       //    123 -> 124
00140       size_t distanceFromEnd = 0;
00141       size_t nElements = indices_.size();
00142       indices_collection::reverse_iterator pos = newCombo.rbegin();
00143       for(; pos != newCombo.rend(); ++pos, ++distanceFromEnd)
00144       {
00145         // Check if we can update this element to the next value (without overflow)
00146         // If so, increment it it, then quit
00147         if( *pos < (nElements - 1 - distanceFromEnd) )
00148         {
00149           (*pos)++;
00150           break;
00151         } else {
00152           // Set to 'unset value' - we need to update it!
00153           (*pos) = nElements;
00154         }
00155       }
00156 
00157       //std::cout << "after update " << std::endl;
00158       //std::copy(newCombo.begin(), newCombo.end(), std::ostream_iterator<int>(std::cout, " "));
00159       //std::cout << std::endl;
00160 
00161       // forward_pos points to the element *after* pos
00162       indices_collection::iterator forward_pos = pos.base();
00163       // Only do the updates if we have not reached all the way to the beginning!
00164       // this indicates we are at the end of the iteration.  We return a combo
00165       // with all values at nElements to flag that we are at the end
00166       bool done = true;
00167       if (forward_pos != newCombo.begin()) {
00168         // Everything after pos needs to be updated.  i.e. 159 -> 167
00169         index_type next_pos_value = (*pos)+1;
00170         //std::cout << "next pos: " << next_pos_value << std::endl;
00171         done = false;
00172         for (; forward_pos != newCombo.end(); ++forward_pos, ++next_pos_value) {
00173           *forward_pos = next_pos_value;
00174         }
00175       }
00176 
00177       //std::cout << "final " << std::endl;
00178       //std::copy(newCombo.begin(), newCombo.end(), std::ostream_iterator<int>(std::cout, " "));
00179       //std::cout << std::endl;
00180 
00181       //return std::auto_ptr<Combinatoric<T> >(new Combinatoric<T>(begin_, indices_, newCombo));
00182       return Combinatoric<T>(begin_, indices_, newCombo, done);
00183     }
00184 
00185     // Check if iteration is done
00186     bool done() const { return done_; }
00187 
00189     const indices_set& combo() const { return comboSet_; }
00190 
00192     bool operator==(const Combinatoric<T>& rhs) const
00193     {
00194       return (this->combo() == rhs.combo() && this->done() == rhs.done());
00195     }
00196 
00197     private:
00198     // Beginning and ending of the vector of iterators that point to our
00199     // input collection
00200     value_iter begin_;
00201     indices_collection combo_;
00202     indices_set comboSet_;
00203     indices_collection indices_;
00204     bool done_;
00205     ValueAccessor valueAccessor_;
00206     IndexInSet inChoice_;
00207     IndexInSet notInChoice_;
00208   };
00209 
00210 template<typename T>
00211   class CombinatoricIterator : public boost::iterator_facade<
00212                                CombinatoricIterator<T>,
00213                                const Combinatoric<T>,
00214                                boost::forward_traversal_tag>
00215 {
00216   /* An iterator over Combinatorics */
00217   public:
00218     typedef Combinatoric<T> value_type;
00219     explicit CombinatoricIterator(const Combinatoric<T>& c):node_(c) {}
00220 
00221   private:
00222     friend class boost::iterator_core_access;
00223 
00224     bool equal(CombinatoricIterator const& other) const {
00225       return this->node_ == other.node_;
00226     }
00227 
00228     void increment() {
00229       node_ = node_.next();
00230     }
00231 
00232     const Combinatoric<T>& dereference() const {
00233       return node_;
00234     }
00235 
00236     Combinatoric<T> node_;
00237 };
00238 
00239 template<typename T>
00240   class CombinatoricGenerator
00241   {
00242     /* CombinatoricGenerator
00243      *
00244      * Generate combinatoric subsets of a collection of type T.
00245      *
00246      * This classes begin() and end() functions return iterators of size
00247      * <choose> the first and last combinatoric subsets in the input collection
00248      * range defined by <begin> and <end>.
00249      */
00250 
00251     // Iterator over input collection
00252     typedef typename T::const_iterator value_iter;
00253     typedef typename T::value_type value_type;
00254     typedef size_t index_type;
00255     typedef typename std::vector<index_type> indices_collection;
00256     typedef typename indices_collection::iterator index_iter;
00257     typedef typename std::set<index_type> indices_set;
00258 
00259     public:
00260 
00261     typedef std::auto_ptr<CombinatoricIterator<T> > CombIterPtr;
00262     typedef CombinatoricIterator<T> iterator;
00263     typedef typename iterator::value_type::ValueIter combo_iterator;
00264 
00265     explicit CombinatoricGenerator(const value_iter& begin, const value_iter& end, size_t choose)
00266     {
00267       // Make beginning and ending index collections
00268       indices_collection initialCombo(choose);
00269       indices_collection finalCombo(choose);
00270 
00271       size_t totalElements = end-begin;
00272 
00273       if (choose <= totalElements) {
00274         indices_collection allIndices(totalElements);
00275         for(size_t i=0; i < totalElements; ++i)
00276         {
00277           allIndices[i] = i;
00278         }
00279 
00280         for(size_t i=0; i < choose; ++i)
00281         {
00282           initialCombo[i] = i;
00283           // End conditions each is set at nElements
00284           finalCombo[i] = totalElements;
00285         }
00286 
00287         beginning_ = CombIterPtr(new CombinatoricIterator<T>(Combinatoric<T>(
00288                 begin, allIndices, initialCombo, false)));
00289 
00290         ending_ = CombIterPtr(new CombinatoricIterator<T>(Combinatoric<T>(
00291                 begin, allIndices, finalCombo, true)));
00292       } else {
00293         // We don't have enough in the collection to return [choose] items.
00294         // Return an empty collection
00295         beginning_ = CombIterPtr(new CombinatoricIterator<T>(Combinatoric<T>(
00296                 begin, indices_collection(), indices_collection(), true)));
00297 
00298         ending_ = CombIterPtr(new CombinatoricIterator<T>(Combinatoric<T>(
00299                 begin, indices_collection(), indices_collection(), true)));
00300       }
00301     }
00302 
00303     CombinatoricIterator<T> begin() {
00304       return *beginning_;
00305     }
00306 
00307     CombinatoricIterator<T> end() {
00308       return *ending_;
00309     }
00310 
00311     private:
00312     CombIterPtr beginning_;
00313     CombIterPtr ending_;
00314   };
00315 
00316 } } // end namespace reco::tau
00317 #endif