libDAI
index.h
Go to the documentation of this file.
1 /* This file is part of libDAI - http://www.libdai.org/
2  *
3  * Copyright (c) 2006-2011, The libDAI authors. All rights reserved.
4  *
5  * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
6  */
7 
8 
11 
12 
13 #ifndef __defined_libdai_index_h
14 #define __defined_libdai_index_h
15 
16 
17 #include <vector>
18 #include <algorithm>
19 #include <map>
20 #include <dai/varset.h>
21 
22 
23 namespace dai {
24 
25 
27 
48 class IndexFor {
49  private:
51  long _index;
52 
54  std::vector<long> _sum;
55 
57  std::vector<size_t> _state;
58 
60  std::vector<size_t> _ranges;
61 
62  public:
64  IndexFor() : _index(-1) {}
65 
67  IndexFor( const VarSet& indexVars, const VarSet& forVars ) : _state( forVars.size(), 0 ) {
68  long sum = 1;
69 
70  _ranges.reserve( forVars.size() );
71  _sum.reserve( forVars.size() );
72 
73  VarSet::const_iterator j = forVars.begin();
74  for( VarSet::const_iterator i = indexVars.begin(); i != indexVars.end(); ++i ) {
75  for( ; j != forVars.end() && *j <= *i; ++j ) {
76  _ranges.push_back( j->states() );
77  _sum.push_back( (*i == *j) ? sum : 0 );
78  }
79  sum *= i->states();
80  }
81  for( ; j != forVars.end(); ++j ) {
82  _ranges.push_back( j->states() );
83  _sum.push_back( 0 );
84  }
85  _index = 0;
86  }
87 
90  fill( _state.begin(), _state.end(), 0 );
91  _index = 0;
92  return( *this );
93  }
94 
96  operator size_t() const {
97  DAI_ASSERT( valid() );
98  return( _index );
99  }
100 
103  if( _index >= 0 ) {
104  size_t i = 0;
105 
106  while( i < _state.size() ) {
107  _index += _sum[i];
108  if( ++_state[i] < _ranges[i] )
109  break;
110  _index -= _sum[i] * _ranges[i];
111  _state[i] = 0;
112  i++;
113  }
114 
115  if( i == _state.size() )
116  _index = -1;
117  }
118  return( *this );
119  }
120 
122  void operator++( int ) {
123  operator++();
124  }
125 
127  bool valid() const {
128  return( _index >= 0 );
129  }
130 };
131 
132 
134 
137 class Permute {
138  private:
140  std::vector<size_t> _ranges;
142  std::vector<size_t> _sigma;
143 
144  public:
146  Permute() : _ranges(), _sigma() {}
147 
149  Permute( const std::vector<size_t> &rs, const std::vector<size_t> &sigma ) : _ranges(rs), _sigma(sigma) {
150  DAI_ASSERT( _ranges.size() == _sigma.size() );
151  }
152 
154 
158  Permute( const std::vector<Var> &vars, bool reverse=false ) : _ranges(), _sigma() {
159  size_t N = vars.size();
160 
161  // construct ranges
162  _ranges.reserve( N );
163  for( size_t i = 0; i < N; ++i )
164  if( reverse )
165  _ranges.push_back( vars[N - 1 - i].states() );
166  else
167  _ranges.push_back( vars[i].states() );
168 
169  // construct VarSet out of vars
170  VarSet vs( vars.begin(), vars.end(), N );
171  DAI_ASSERT( vs.size() == N );
172 
173  // construct sigma
174  _sigma.reserve( N );
175  for( VarSet::const_iterator vs_i = vs.begin(); vs_i != vs.end(); ++vs_i ) {
176  size_t ind = find( vars.begin(), vars.end(), *vs_i ) - vars.begin();
177  if( reverse )
178  _sigma.push_back( N - 1 - ind );
179  else
180  _sigma.push_back( ind );
181  }
182  }
183 
185 
188  size_t convertLinearIndex( size_t li ) const {
189  size_t N = _ranges.size();
190 
191  // calculate vector index corresponding to linear index
192  std::vector<size_t> vi;
193  vi.reserve( N );
194  size_t prod = 1;
195  for( size_t k = 0; k < N; k++ ) {
196  vi.push_back( li % _ranges[k] );
197  li /= _ranges[k];
198  prod *= _ranges[k];
199  }
200 
201  // convert permuted vector index to corresponding linear index
202  prod = 1;
203  size_t sigma_li = 0;
204  for( size_t k = 0; k < N; k++ ) {
205  sigma_li += vi[_sigma[k]] * prod;
206  prod *= _ranges[_sigma[k]];
207  }
208 
209  return sigma_li;
210  }
211 
213  const std::vector<size_t>& sigma() const { return _sigma; }
214 
216  std::vector<size_t>& sigma() { return _sigma; }
217 
219  const std::vector<size_t>& ranges() { return _ranges; }
220 
222  size_t operator[]( size_t i ) const {
223 #ifdef DAI_DEBUG
224  return _sigma.at(i);
225 #else
226  return _sigma[i];
227 #endif
228  }
229 
231  Permute inverse() const {
232  size_t N = _ranges.size();
233  std::vector<size_t> invRanges( N, 0 );
234  std::vector<size_t> invSigma( N, 0 );
235  for( size_t i = 0; i < N; i++ ) {
236  invSigma[_sigma[i]] = i;
237  invRanges[i] = _ranges[_sigma[i]];
238  }
239  return Permute( invRanges, invSigma );
240  }
241 };
242 
243 
245 
263 class multifor {
264  private:
266  std::vector<size_t> _ranges;
268  std::vector<size_t> _indices;
271 
272  public:
275 
277  multifor( const std::vector<size_t> &d ) : _ranges(d), _indices(d.size(),0), _linear_index(0) {}
278 
280  operator size_t() const {
281  DAI_DEBASSERT( valid() );
282  return( _linear_index );
283  }
284 
286  size_t operator[]( size_t k ) const {
287  DAI_DEBASSERT( valid() );
288  DAI_DEBASSERT( k < _indices.size() );
289  return _indices[k];
290  }
291 
294  if( valid() ) {
295  _linear_index++;
296  size_t i;
297  for( i = 0; i != _indices.size(); i++ ) {
298  if( ++(_indices[i]) < _ranges[i] )
299  break;
300  _indices[i] = 0;
301  }
302  if( i == _indices.size() )
303  _linear_index = -1;
304  }
305  return *this;
306  }
307 
309  void operator++( int ) {
310  operator++();
311  }
312 
315  fill( _indices.begin(), _indices.end(), 0 );
316  _linear_index = 0;
317  return( *this );
318  }
319 
321  bool valid() const {
322  return( _linear_index >= 0 );
323  }
324 };
325 
326 
328 
352 class State {
353  private:
355  typedef std::map<Var, size_t> states_type;
356 
359 
362 
363  public:
365  State() : state(0), states() {}
366 
368  State( const VarSet &vs, BigInt linearState=0 ) : state(linearState), states() {
369  if( linearState == 0 )
370  for( VarSet::const_iterator v = vs.begin(); v != vs.end(); v++ )
371  states[*v] = 0;
372  else {
373  for( VarSet::const_iterator v = vs.begin(); v != vs.end(); v++ ) {
374  states[*v] = BigInt_size_t( linearState % (BigInt)v->states() );
375  linearState /= (BigInt)v->states();
376  }
377  DAI_ASSERT( linearState == 0 );
378  }
379  }
380 
382  State( const std::map<Var, size_t> &s ) : state(0), states() {
383  insert( s.begin(), s.end() );
384  }
385 
387  typedef states_type::const_iterator const_iterator;
388 
390  const_iterator begin() const { return states.begin(); }
391 
393  const_iterator end() const { return states.end(); }
394 
396  operator size_t() const {
397  DAI_ASSERT( valid() );
398  return( BigInt_size_t( state ) );
399  }
400 
402  template<typename InputIterator>
403  void insert( InputIterator b, InputIterator e ) {
404  states.insert( b, e );
405  VarSet vars;
406  for( const_iterator it = begin(); it != end(); it++ )
407  vars |= it->first;
408  state = 0;
409  state = this->operator()( vars );
410  }
411 
413  const std::map<Var,size_t>& get() const { return states; }
414 
416  operator const std::map<Var,size_t>& () const { return states; }
417 
419  size_t operator() ( const Var &v ) const {
420  states_type::const_iterator entry = states.find( v );
421  if( entry == states.end() )
422  return 0;
423  else
424  return entry->second;
425  }
426 
428  BigInt operator() ( const VarSet &vs ) const {
429  BigInt vs_state = 0;
430  BigInt prod = 1;
431  for( VarSet::const_iterator v = vs.begin(); v != vs.end(); v++ ) {
432  states_type::const_iterator entry = states.find( *v );
433  if( entry != states.end() )
434  vs_state += (BigInt)entry->second * prod;
435  prod *= (BigInt)v->states();
436  }
437  return vs_state;
438  }
439 
441  void operator++( ) {
442  if( valid() ) {
443  state++;
444  states_type::iterator entry = states.begin();
445  while( entry != states.end() ) {
446  if( ++(entry->second) < entry->first.states() )
447  break;
448  entry->second = 0;
449  entry++;
450  }
451  if( entry == states.end() )
452  state = -1;
453  }
454  }
455 
457  void operator++( int ) {
458  operator++();
459  }
460 
462  bool valid() const {
463  return( state >= 0 );
464  }
465 
467  void reset() {
468  state = 0;
469  for( states_type::iterator s = states.begin(); s != states.end(); s++ )
470  s->second = 0;
471  }
472 };
473 
474 
475 } // end of namespace dai
476 
477 
488 #endif