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
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048 namespace reco { namespace tau {
00049
00050 template <typename T>
00051 class Combinatoric
00052 {
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
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
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
00089
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
00128
00129
00130
00131
00132 indices_collection newCombo(combo_);
00133
00134
00135
00136
00137
00138
00139
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
00146
00147 if( *pos < (nElements - 1 - distanceFromEnd) )
00148 {
00149 (*pos)++;
00150 break;
00151 } else {
00152
00153 (*pos) = nElements;
00154 }
00155 }
00156
00157
00158
00159
00160
00161
00162 indices_collection::iterator forward_pos = pos.base();
00163
00164
00165
00166 bool done = true;
00167 if (forward_pos != newCombo.begin()) {
00168
00169 index_type next_pos_value = (*pos)+1;
00170
00171 done = false;
00172 for (; forward_pos != newCombo.end(); ++forward_pos, ++next_pos_value) {
00173 *forward_pos = next_pos_value;
00174 }
00175 }
00176
00177
00178
00179
00180
00181
00182 return Combinatoric<T>(begin_, indices_, newCombo, done);
00183 }
00184
00185
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
00199
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
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
00243
00244
00245
00246
00247
00248
00249
00250
00251
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
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
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
00294
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 } }
00317 #endif