00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00015
00016
00017 #ifndef __defined_libdai_index_h
00018 #define __defined_libdai_index_h
00019
00020
00021 #include <vector>
00022 #include <algorithm>
00023 #include <map>
00024 #include <dai/varset.h>
00025
00026
00027 namespace dai {
00028
00029
00031
00052 class IndexFor {
00053 private:
00055 long _index;
00056
00058 std::vector<long> _sum;
00059
00061 std::vector<size_t> _state;
00062
00064 std::vector<size_t> _ranges;
00065
00066 public:
00068 IndexFor() : _index(-1) {}
00069
00071 IndexFor( const VarSet& indexVars, const VarSet& forVars ) : _state( forVars.size(), 0 ) {
00072 long sum = 1;
00073
00074 _ranges.reserve( forVars.size() );
00075 _sum.reserve( forVars.size() );
00076
00077 VarSet::const_iterator j = forVars.begin();
00078 for( VarSet::const_iterator i = indexVars.begin(); i != indexVars.end(); ++i ) {
00079 for( ; j != forVars.end() && *j <= *i; ++j ) {
00080 _ranges.push_back( j->states() );
00081 _sum.push_back( (*i == *j) ? sum : 0 );
00082 }
00083 sum *= i->states();
00084 }
00085 for( ; j != forVars.end(); ++j ) {
00086 _ranges.push_back( j->states() );
00087 _sum.push_back( 0 );
00088 }
00089 _index = 0;
00090 }
00091
00093 IndexFor& reset() {
00094 fill( _state.begin(), _state.end(), 0 );
00095 _index = 0;
00096 return( *this );
00097 }
00098
00100 operator size_t() const {
00101 DAI_ASSERT( valid() );
00102 return( _index );
00103 }
00104
00106 IndexFor& operator++ () {
00107 if( _index >= 0 ) {
00108 size_t i = 0;
00109
00110 while( i < _state.size() ) {
00111 _index += _sum[i];
00112 if( ++_state[i] < _ranges[i] )
00113 break;
00114 _index -= _sum[i] * _ranges[i];
00115 _state[i] = 0;
00116 i++;
00117 }
00118
00119 if( i == _state.size() )
00120 _index = -1;
00121 }
00122 return( *this );
00123 }
00124
00126 void operator++( int ) {
00127 operator++();
00128 }
00129
00131 bool valid() const {
00132 return( _index >= 0 );
00133 }
00134 };
00135
00136
00138
00141 class Permute {
00142 private:
00144 std::vector<size_t> _ranges;
00146 std::vector<size_t> _sigma;
00147
00148 public:
00150 Permute() : _ranges(), _sigma() {}
00151
00153 Permute( const std::vector<size_t> &rs, const std::vector<size_t> &sigma ) : _ranges(rs), _sigma(sigma) {
00154 DAI_ASSERT( _ranges.size() == _sigma.size() );
00155 }
00156
00158
00161 Permute( const std::vector<Var> &vars ) : _ranges(vars.size()), _sigma(vars.size()) {
00162 for( size_t i = 0; i < vars.size(); ++i )
00163 _ranges[i] = vars[i].states();
00164 VarSet vs( vars.begin(), vars.end(), vars.size() );
00165 VarSet::const_iterator vs_i = vs.begin();
00166 for( size_t i = 0; i < vs.size(); ++i, ++vs_i )
00167 _sigma[i] = find( vars.begin(), vars.end(), *vs_i ) - vars.begin();
00168 }
00169
00171
00174 size_t convertLinearIndex( size_t li ) const {
00175 size_t N = _ranges.size();
00176
00177
00178 std::vector<size_t> vi;
00179 vi.reserve( N );
00180 size_t prod = 1;
00181 for( size_t k = 0; k < N; k++ ) {
00182 vi.push_back( li % _ranges[k] );
00183 li /= _ranges[k];
00184 prod *= _ranges[k];
00185 }
00186
00187
00188 prod = 1;
00189 size_t sigma_li = 0;
00190 for( size_t k = 0; k < N; k++ ) {
00191 sigma_li += vi[_sigma[k]] * prod;
00192 prod *= _ranges[_sigma[k]];
00193 }
00194
00195 return sigma_li;
00196 }
00197
00199 const std::vector<size_t>& sigma() const { return _sigma; }
00200
00202 std::vector<size_t>& sigma() { return _sigma; }
00203
00205 size_t operator[]( size_t i ) const {
00206 #ifdef DAI_DEBUG
00207 return _sigma.at(i);
00208 #else
00209 return _sigma[i];
00210 #endif
00211 }
00212 };
00213
00214
00216
00234 class multifor {
00235 private:
00237 std::vector<size_t> _ranges;
00239 std::vector<size_t> _indices;
00241 long _linear_index;
00242
00243 public:
00245 multifor() : _ranges(), _indices(), _linear_index(0) {}
00246
00248 multifor( const std::vector<size_t> &d ) : _ranges(d), _indices(d.size(),0), _linear_index(0) {}
00249
00251 operator size_t() const {
00252 DAI_DEBASSERT( valid() );
00253 return( _linear_index );
00254 }
00255
00257 size_t operator[]( size_t k ) const {
00258 DAI_DEBASSERT( valid() );
00259 DAI_DEBASSERT( k < _indices.size() );
00260 return _indices[k];
00261 }
00262
00264 multifor & operator++() {
00265 if( valid() ) {
00266 _linear_index++;
00267 size_t i;
00268 for( i = 0; i != _indices.size(); i++ ) {
00269 if( ++(_indices[i]) < _ranges[i] )
00270 break;
00271 _indices[i] = 0;
00272 }
00273 if( i == _indices.size() )
00274 _linear_index = -1;
00275 }
00276 return *this;
00277 }
00278
00280 void operator++( int ) {
00281 operator++();
00282 }
00283
00285 bool valid() const {
00286 return( _linear_index >= 0 );
00287 }
00288 };
00289
00290
00292
00318 class State {
00319 private:
00321 typedef std::map<Var, size_t> states_type;
00322
00324 long state;
00325
00327 states_type states;
00328
00329 public:
00331 State() : state(0), states() {}
00332
00334 State( const VarSet &vs, size_t linearState=0 ) : state(linearState), states() {
00335 if( linearState == 0 )
00336 for( VarSet::const_iterator v = vs.begin(); v != vs.end(); v++ )
00337 states[*v] = 0;
00338 else {
00339 for( VarSet::const_iterator v = vs.begin(); v != vs.end(); v++ ) {
00340 states[*v] = linearState % v->states();
00341 linearState /= v->states();
00342 }
00343 DAI_ASSERT( linearState == 0 );
00344 }
00345 }
00346
00348 State( const std::map<Var, size_t> &s ) : state(0), states() {
00349 insert( s.begin(), s.end() );
00350 }
00351
00353 typedef states_type::const_iterator const_iterator;
00354
00356 const_iterator begin() const { return states.begin(); }
00357
00359 const_iterator end() const { return states.end(); }
00360
00362 operator size_t() const {
00363 DAI_ASSERT( valid() );
00364 return( state );
00365 }
00366
00368 template<typename InputIterator>
00369 void insert( InputIterator b, InputIterator e ) {
00370 states.insert( b, e );
00371 VarSet vars;
00372 for( const_iterator it = begin(); it != end(); it++ )
00373 vars |= it->first;
00374 state = 0;
00375 state = this->operator()( vars );
00376 }
00377
00379 const std::map<Var,size_t>& get() const { return states; }
00380
00382 operator const std::map<Var,size_t>& () const { return states; }
00383
00385 size_t operator() ( const Var &v ) const {
00386 DAI_ASSERT( valid() );
00387 states_type::const_iterator entry = states.find( v );
00388 if( entry == states.end() )
00389 return 0;
00390 else
00391 return entry->second;
00392 }
00393
00395 size_t operator() ( const VarSet &vs ) const {
00396 DAI_ASSERT( valid() );
00397 size_t vs_state = 0;
00398 size_t prod = 1;
00399 for( VarSet::const_iterator v = vs.begin(); v != vs.end(); v++ ) {
00400 states_type::const_iterator entry = states.find( *v );
00401 if( entry != states.end() )
00402 vs_state += entry->second * prod;
00403 prod *= v->states();
00404 }
00405 return vs_state;
00406 }
00407
00409 void operator++( ) {
00410 if( valid() ) {
00411 state++;
00412 states_type::iterator entry = states.begin();
00413 while( entry != states.end() ) {
00414 if( ++(entry->second) < entry->first.states() )
00415 break;
00416 entry->second = 0;
00417 entry++;
00418 }
00419 if( entry == states.end() )
00420 state = -1;
00421 }
00422 }
00423
00425 void operator++( int ) {
00426 operator++();
00427 }
00428
00430 bool valid() const {
00431 return( state >= 0 );
00432 }
00433
00435 void reset() {
00436 state = 0;
00437 for( states_type::iterator s = states.begin(); s != states.end(); s++ )
00438 s->second = 0;
00439 }
00440 };
00441
00442
00443 }
00444
00445
00456 #endif