00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00037 #ifndef PARTITION_BOX_H
00038 #define PARTITION_BOX_H
00039
00040 using namespace std;
00041
00042 #include <iostream>
00043 #include <fstream>
00044 #include <vector>
00045 #include <cmath>
00046
00047 template <class Tpart> class Partition_box
00048 {
00049 protected :
00050
00052 vector< Tpart > _partition;
00053
00055 bool ** _possib;
00057 int _nbposs;
00059 int * _pow;
00060
00062 short _size;
00063
00065 long _cardinal;
00066
00068 long _currpart;
00069
00070
00072 void init_possib(){
00073 int i,j;
00074 short si;
00075 _pow = new int[_size+1];
00076 _pow[0] = 1;
00077 for (si=0; si<_size; si++){
00078 _pow[si+1] = 2*_pow[si];
00079 }
00080 _nbposs = _pow[_size-1];
00081
00082 _possib = new bool*[_nbposs];
00083 for (i=0; i<_nbposs; i++)
00084 _possib[i] = new bool[_size];
00085
00086 int pow1 = 1, pow2=_nbposs/2;
00087 for (i=0; i<_nbposs; i++)
00088 _possib[i][0] = false;
00089 for (si=1; si<_size; si++){
00090 for (i=0; i<pow1; i++)
00091 for (j=0; j<pow2; j++){
00092 _possib[(2*i+1)*pow2+j][si] = false;
00093 _possib[2*i*pow2+j][si] = true;
00094 }
00095 pow1 *= 2;
00096 pow2 /= 2;
00097 }
00098
00099
00100
00101
00102
00103
00104
00105 }
00106
00107
00109 void delete_possib(){
00110 int i;
00111 for (i=0; i<_nbposs; i++){
00112 delete [] _possib[i];
00113 }
00114 delete [] _possib;
00115 }
00116
00117 long approx_cardinal(){
00118 int maxIter = 30;
00119 double epsilon = 0.0001, test = 1., kpuiss, sum = 0, sumold;
00120 double i = 1, kfact = 1;
00121 while ((i<maxIter)&&(abs(test)>epsilon))
00122 {
00123 sumold = sum;
00124 kpuiss = pow(double(i), double(_size));
00125 kfact = kfact*i;
00126 sum = sum+kpuiss/kfact;
00127 test = sumold-sum;
00128 i++;
00129 }
00130 return ( long(sum*(exp(-1.))) +1);
00131 }
00132
00134 void cutoff_r( vector<short> & vec,
00135 short nbmaxfalse, short numfalse,
00136 short notaffected ){
00137 int i, j;
00138 short snif, newnbfalse=0;
00139
00140 if (notaffected==0){
00141
00142
00143 this->processing( numfalse, vec );
00144
00145
00146
00147
00148
00149
00150
00151
00152
00153 _cardinal++;
00154 }
00155 else{
00156
00157 int jump = _pow[_size-notaffected];
00158
00159 for ( i=0; i<_nbposs; i+=jump ){
00160
00161
00162
00163
00164
00165
00166
00167 snif = 0;
00168 newnbfalse = 0;
00169
00170 for ( j=0; j<_size; j++ ){
00171
00172 if ( vec[j]==0 ){
00173
00174 if ( _possib[i][snif++] == false ){
00175 vec[j] = numfalse;
00176 newnbfalse++;
00177 }
00178 }
00179 }
00180
00181 cutoff_r( vec,
00182 newnbfalse, numfalse+1,
00183 notaffected-newnbfalse );
00184
00185 for ( j=0; j<_size; j++ )
00186 if ( vec[j] == numfalse )
00187 vec[j] = 0;
00188 }
00189 }
00190 }
00191
00193 virtual void processing( short numfalse,
00194 const vector<short> & vec ) = 0;
00195
00196 public :
00197
00199 Partition_box( ){
00200 _size = 0;
00201 _currpart = 0;
00202 _cardinal = 0;
00203 _pow = NULL;
00204 _nbposs = 0;
00205 _possib = NULL;
00206 }
00207
00209 Partition_box( short size_ensemble ){
00210 _size = size_ensemble;
00211 _currpart = 0;
00212 if (size_ensemble<14){
00213 long card = approx_cardinal();
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223 _partition.reserve( card );
00224 }
00225 _cardinal = 0;
00226 _pow = NULL;
00227 }
00228
00230 Partition_box( const Partition_box & p ){
00231 _size = p._size;
00232 _currpart = p._currpart;
00233 _partition.reserve = p._partition;
00234 _cardinal = p._cardinal;
00235 _pow = NULL;
00236 }
00237
00239 virtual ~Partition_box(){
00240 if (_pow)
00241 delete [] _pow;
00242 };
00243
00245 void cutoff(){
00246 vector<short> v(_size, 0);
00247 this->init_possib();
00248 _cardinal = 0;
00249 cutoff_r(v, _size, 1, _size);
00250 this->delete_possib();
00251 }
00252
00254 long tell_cardinal() const{
00255 return _cardinal;
00256 }
00257
00259 long tell_size() const{
00260 return _size;
00261 }
00262
00264 const Tpart & element( int i) const{
00265 return _partition[i];
00266 }
00267
00268
00269 class const_iterator{
00270 private :
00271 const Partition_box<Tpart> * _part_box;
00272 long _currpart;
00273 protected :
00274 friend class Partition_box;
00275 const_iterator( const Partition_box<Tpart> & p, long currpart ){
00276 _part_box = &p;
00277 _currpart = currpart;
00278 if (p._cardinal == 0)
00279 cerr<<" cutoff required !"<<endl;
00280 }
00281 public :
00282 const_iterator( ){
00283 _currpart = -1;
00284 _part_box = NULL;
00285 }
00287 bool operator ++ () {
00288
00289 if ( _currpart<_part_box->_cardinal-1 ){
00290 _currpart++;
00291 return true;
00292 }
00293 else{
00294 _currpart++;
00295 return false;
00296 }
00297 }
00299 bool operator ++ (int) {
00300
00301 if ( _currpart<_part_box->_cardinal-1 ){
00302 _currpart++;
00303 return true;
00304 }
00305 else{
00306 _currpart++;
00307 return false;
00308 }
00309 }
00311 bool operator != ( const const_iterator & p ) const{
00312 return ( (p._part_box !=_part_box)
00313 || (p._currpart !=_currpart) );
00314 }
00316 bool operator == ( const const_iterator & p ) const{
00317 return ( (p._part_box ==_part_box)
00318 && (p._currpart ==_currpart) );
00319 }
00321 const Tpart& operator * () const{
00322 return _part_box->_partition[_currpart];
00323 }
00324
00325 const_iterator operator = ( const const_iterator & p ){
00326 if ( p != *this ){
00327 _part_box = p._part_box;
00328 _currpart = p._currpart;
00329 }
00330 return *this;
00331 }
00332 };
00333
00335 const_iterator begin() const{
00336 return const_iterator( *this, 0 );
00337 }
00339 const_iterator end() const{
00340 return const_iterator( *this, _cardinal );
00341 }
00342
00343 };
00344
00345
00346 #endif //PARTITION_BOX_H