Back to home page

Project CMSSW displayed by LXR

 
 

    


File indexing completed on 2021-02-14 14:27:01

0001 #ifndef RecoTauTag_RecoTau_CombinatoricGenerator_h
0002 #define RecoTauTag_RecoTau_CombinatoricGenerator_h
0003 
0004 #include <boost/iterator/iterator_facade.hpp>
0005 #include <boost/iterator/filter_iterator.hpp>
0006 #include <boost/iterator/transform_iterator.hpp>
0007 #include <vector>
0008 #include <set>
0009 #include <memory>
0010 #include <iostream>
0011 
0012 /*
0013  * CombinatoricGenerator
0014  *
0015  * Author: Evan K. Friis (UC Davis)
0016  *
0017  * Generic classes to compute combinatoric subsets of collections.
0018  *
0019  * Example of use:
0020  *
0021  * vector<int> collection = [0, 1, 2, 3, 4, 5];
0022  *
0023  * typedef CombinatoricGenerator<std::vector<int> Generator;
0024  *
0025  * // Select three element combinations of collection
0026  * Generator generator(collection.begin(), collection.end(), 3);
0027  *
0028  * for(Generator::iterator combo = generator.begin(); combo != generator.end(); ++combo)
0029  * {
0030  *     for(Generator::combo_iterator element = combo->begin(); element != combo->end(); ++element)
0031  *     {
0032  *         cout << *element << " ";
0033  *     }
0034  *     cout << endl;
0035  * }
0036  *
0037  * Outputs:
0038  * 0 1 2
0039  * 0 1 3
0040  * 0 1 4
0041  * ...
0042  * 3 4 5
0043  *
0044  *
0045  */
0046 
0047 namespace reco {
0048   namespace tau {
0049 
0050     template <typename T>
0051     class Combinatoric {
0052       /* Combinatoric<T>
0053      *
0054      * Class that represents a subset of values from a collection of type T.
0055      *
0056      * The values belonging to the current combination subset can be accessed with the iterators
0057      * combo_begin() and combo_end()
0058      *
0059      * The values in the collection not in the subset can be accessed with
0060      * remainder_begin() and remainder_end()
0061      *
0062      */
0063 
0064       // Iterator over input collection
0065       typedef typename T::const_iterator value_iter;
0066       typedef typename T::value_type value_type;
0067       typedef size_t index_type;
0068       typedef typename std::vector<index_type> indices_collection;
0069       typedef typename indices_collection::const_iterator index_iter;
0070       typedef typename std::set<index_type> indices_set;
0071 
0072       class IndexInSet {
0073         /* Determine if a given index is in a set of indices */
0074       public:
0075         IndexInSet(const indices_set& combo, bool negate) : combo_(combo), negate_(negate) {}
0076         bool operator()(const index_type& index) const {
0077           return (negate_) ? !combo_.count(index) : combo_.count(index);
0078         }
0079 
0080       private:
0081         indices_set combo_;
0082         bool negate_;
0083       };
0084 
0085       class ValueAccessor {
0086         /* Class to extract a value from a collection given the beginning of the collection
0087        * and the index into the colleciton */
0088       public:
0089         ValueAccessor(const value_iter& begin) : begin_(begin) {}
0090         const value_type& operator()(index_type const& index) const { return *(begin_ + index); }
0091 
0092       private:
0093         value_iter begin_;
0094       };
0095 
0096     public:
0097       Combinatoric(const value_iter& begin,
0098                    const indices_collection& indices,
0099                    const indices_collection& combo,
0100                    bool done)
0101           : begin_(begin),
0102             combo_(combo.begin(), combo.end()),
0103             comboSet_(combo.begin(), combo.end()),
0104             indices_(indices),
0105             done_(done),
0106             valueAccessor_(begin),
0107             inChoice_(comboSet_, false),
0108             notInChoice_(comboSet_, true) {}
0109 
0110       typedef typename boost::filter_iterator<IndexInSet, index_iter> ComboIter;
0111       typedef typename boost::transform_iterator<ValueAccessor, ComboIter> ValueIter;
0112 
0113       /// The first element in the selected subset
0114       ValueIter combo_begin() const {
0115         return ValueIter(ComboIter(inChoice_, indices_.begin(), indices_.end()), valueAccessor_);
0116       }
0117       /// One past the last element in the selected subset
0118       ValueIter combo_end() const {
0119         return ValueIter(ComboIter(inChoice_, indices_.end(), indices_.end()), valueAccessor_);
0120       }
0121 
0122       /// The first element in the non-selected subset
0123       ValueIter remainder_end() const {
0124         return ValueIter(ComboIter(notInChoice_, indices_.end(), indices_.end()), valueAccessor_);
0125       }
0126       /// One past the last element in the non-selected subset
0127       ValueIter remainder_begin() const {
0128         return ValueIter(ComboIter(notInChoice_, indices_.begin(), indices_.end()), valueAccessor_);
0129       }
0130 
0131       /// Build the next cominatoric subset after the current one
0132       Combinatoric<T> next() const {
0133         //std::cout << "building next: " << std::endl;
0134         //std::cout << "current " << std::endl;
0135         //std::copy(combo_.begin(), combo_.end(), std::ostream_iterator<int>(std::cout, " "));
0136         //std::cout << std::endl;
0137 
0138         indices_collection newCombo(combo_);
0139 
0140         // Find the first value that can be updated (starting from the back
0141         // max value for index is (nElements-1) - (distance from end)
0142         // Examples:
0143         //    189 -> 289 (will be updated to 234)
0144         //    179 -> 189
0145         //    123 -> 124
0146         size_t distanceFromEnd = 0;
0147         size_t nElements = indices_.size();
0148         indices_collection::reverse_iterator pos = newCombo.rbegin();
0149         for (; pos != newCombo.rend(); ++pos, ++distanceFromEnd) {
0150           // Check if we can update this element to the next value (without overflow)
0151           // If so, increment it it, then quit
0152           if (*pos < (nElements - 1 - distanceFromEnd)) {
0153             (*pos)++;
0154             break;
0155           } else {
0156             // Set to 'unset value' - we need to update it!
0157             (*pos) = nElements;
0158           }
0159         }
0160 
0161         //std::cout << "after update " << std::endl;
0162         //std::copy(newCombo.begin(), newCombo.end(), std::ostream_iterator<int>(std::cout, " "));
0163         //std::cout << std::endl;
0164 
0165         // forward_pos points to the element *after* pos
0166         indices_collection::iterator forward_pos = pos.base();
0167         // Only do the updates if we have not reached all the way to the beginning!
0168         // this indicates we are at the end of the iteration.  We return a combo
0169         // with all values at nElements to flag that we are at the end
0170         bool done = true;
0171         if (forward_pos != newCombo.begin()) {
0172           // Everything after pos needs to be updated.  i.e. 159 -> 167
0173           index_type next_pos_value = (*pos) + 1;
0174           //std::cout << "next pos: " << next_pos_value << std::endl;
0175           done = false;
0176           for (; forward_pos != newCombo.end(); ++forward_pos, ++next_pos_value) {
0177             *forward_pos = next_pos_value;
0178           }
0179         }
0180 
0181         //std::cout << "final " << std::endl;
0182         //std::copy(newCombo.begin(), newCombo.end(), std::ostream_iterator<int>(std::cout, " "));
0183         //std::cout << std::endl;
0184 
0185         //return std::unique_ptr<Combinatoric<T> >(new Combinatoric<T>(begin_, indices_, newCombo));
0186         return Combinatoric<T>(begin_, indices_, newCombo, done);
0187       }
0188 
0189       // Check if iteration is done
0190       bool done() const { return done_; }
0191 
0192       /// Return the set of selected indices
0193       const indices_set& combo() const { return comboSet_; }
0194 
0195       /// Comparison to another combination
0196       bool operator==(const Combinatoric<T>& rhs) const {
0197         return (this->combo() == rhs.combo() && this->done() == rhs.done());
0198       }
0199 
0200     private:
0201       // Beginning and ending of the vector of iterators that point to our
0202       // input collection
0203       value_iter begin_;
0204       indices_collection combo_;
0205       indices_set comboSet_;
0206       indices_collection indices_;
0207       bool done_;
0208       ValueAccessor valueAccessor_;
0209       IndexInSet inChoice_;
0210       IndexInSet notInChoice_;
0211     };
0212 
0213     template <typename T>
0214     class CombinatoricIterator
0215         : public boost::iterator_facade<CombinatoricIterator<T>, const Combinatoric<T>, boost::forward_traversal_tag> {
0216       /* An iterator over Combinatorics */
0217     public:
0218       typedef Combinatoric<T> value_type;
0219       explicit CombinatoricIterator(const Combinatoric<T>& c) : node_(c) {}
0220 
0221     private:
0222       friend class boost::iterator_core_access;
0223 
0224       bool equal(CombinatoricIterator const& other) const { return this->node_ == other.node_; }
0225 
0226       void increment() { node_ = node_.next(); }
0227 
0228       const Combinatoric<T>& dereference() const { return node_; }
0229 
0230       Combinatoric<T> node_;
0231     };
0232 
0233     template <typename T>
0234     class CombinatoricGenerator {
0235       /* CombinatoricGenerator
0236      *
0237      * Generate combinatoric subsets of a collection of type T.
0238      *
0239      * This classes begin() and end() functions return iterators of size
0240      * <choose> the first and last combinatoric subsets in the input collection
0241      * range defined by <begin> and <end>.
0242      */
0243 
0244       // Iterator over input collection
0245       typedef typename T::const_iterator value_iter;
0246       typedef typename T::value_type value_type;
0247       typedef size_t index_type;
0248       typedef typename std::vector<index_type> indices_collection;
0249       typedef typename indices_collection::iterator index_iter;
0250       typedef typename std::set<index_type> indices_set;
0251 
0252     public:
0253       typedef std::unique_ptr<CombinatoricIterator<T> > CombIterPtr;
0254       typedef CombinatoricIterator<T> iterator;
0255       typedef typename iterator::value_type::ValueIter combo_iterator;
0256 
0257       explicit CombinatoricGenerator(const value_iter& begin, const value_iter& end, size_t choose) {
0258         // Make beginning and ending index collections
0259         indices_collection initialCombo(choose);
0260         indices_collection finalCombo(choose);
0261 
0262         size_t totalElements = end - begin;
0263 
0264         if (choose <= totalElements) {
0265           indices_collection allIndices(totalElements);
0266           for (size_t i = 0; i < totalElements; ++i) {
0267             allIndices[i] = i;
0268           }
0269 
0270           for (size_t i = 0; i < choose; ++i) {
0271             initialCombo[i] = i;
0272             // End conditions each is set at nElements
0273             finalCombo[i] = totalElements;
0274           }
0275 
0276           beginning_ =
0277               CombIterPtr(new CombinatoricIterator<T>(Combinatoric<T>(begin, allIndices, initialCombo, false)));
0278 
0279           ending_ = CombIterPtr(new CombinatoricIterator<T>(Combinatoric<T>(begin, allIndices, finalCombo, true)));
0280         } else {
0281           // We don't have enough in the collection to return [choose] items.
0282           // Return an empty collection
0283           beginning_ = CombIterPtr(
0284               new CombinatoricIterator<T>(Combinatoric<T>(begin, indices_collection(), indices_collection(), true)));
0285 
0286           ending_ = CombIterPtr(
0287               new CombinatoricIterator<T>(Combinatoric<T>(begin, indices_collection(), indices_collection(), true)));
0288         }
0289       }
0290 
0291       CombinatoricIterator<T> begin() { return *beginning_; }
0292 
0293       CombinatoricIterator<T> end() { return *ending_; }
0294 
0295     private:
0296       CombIterPtr beginning_;
0297       CombIterPtr ending_;
0298     };
0299 
0300   }  // namespace tau
0301 }  // namespace reco
0302 #endif