Version 4.1.5
Main Page | Class Hierarchy | Class List | File List | Class Members | Related Pages

Partition_box.h

Go to the documentation of this file.
00001 /* Partition_box.h
00002  *
00003  * Copyright (C) 2003 Laboratoire Statistique & Génome
00004  *
00005  * This program is free software; you can redistribute it and/or modify
00006  * it under the terms of the GNU General Public License as published by
00007  * the Free Software Foundation; either version 2 of the License, or (at
00008  * your option) any later version.
00009  *
00010  * This program is distributed in the hope that it will be useful, but
00011  * WITHOUT ANY WARRANTY; without even the implied warranty of
00012  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013  * General Public License for more details.
00014  *
00015  * You should have received a copy of the GNU General Public License
00016  * along with this program; if not, write to the Free Software
00017  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
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;
00054   vector< int > _nbpartition_with_nbelement;
00055 
00057   bool ** _possib;
00059   int _nbposs;
00061   int * _pow;
00062 
00064   short _size;
00065 
00067   long _cardinal;
00068 
00070   long _currpart;
00071 
00072   //_________________________________________//
00073 
00074 
00075 
00077   void init_possib(){
00078     int i,j;
00079     short si;
00080     _pow = new int[_size+1];
00081     _pow[0] = 1;
00082     for (si=0; si<_size; si++){
00083       _pow[si+1] = 2*_pow[si];
00084     }
00085     _nbposs = _pow[_size-1];
00086     
00087     _possib = new bool*[_nbposs];
00088     for (i=0; i<_nbposs; i++)
00089       _possib[i] = new bool[_size]; 
00090     
00091     int pow1 = 1, pow2=_nbposs/2;
00092     for (i=0; i<_nbposs; i++)
00093       _possib[i][0] = false;
00094     for (si=1; si<_size; si++){
00095       for (i=0; i<pow1; i++)
00096         for (j=0; j<pow2; j++){
00097           _possib[(2*i+1)*pow2+j][si] = false;
00098           _possib[2*i*pow2+j][si] = true;
00099         }
00100       pow1 *= 2;
00101       pow2 /= 2;
00102     }
00103     /*
00104       for (i=0; i<_nbposs; i++){
00105       for (si=0; si<_size; si++)
00106       cout<<_possib[i][si]<<" ";
00107       cout<<endl;
00108       }
00109     */
00110   }
00111 
00112   
00114   void delete_possib(){
00115     int i;
00116     for (i=0; i<_nbposs; i++){
00117       delete [] _possib[i];
00118     }
00119     delete [] _possib;
00120   }  
00121 
00122   long approx_cardinal(){
00123     int maxIter = 30;
00124     double  epsilon = 0.0001, test = 1., kpuiss, sum = 0, sumold;
00125     double i = 1, kfact = 1;
00126     while  ((i<maxIter)&&(abs(test)>epsilon))
00127       {
00128         sumold = sum;
00129         kpuiss = pow(double(i), double(_size));
00130         kfact = kfact*i;
00131         sum = sum+kpuiss/kfact;
00132         test = sumold-sum;
00133         i++;
00134       }
00135     return  ( long(sum*(exp(-1.))) +1);
00136   }
00137   
00139   void cutoff_r( vector<short> & vec, 
00140                  short nbmaxfalse, short numfalse,
00141                  short notaffected ){
00142     int i, j;
00143     short snif, newnbfalse=0;
00144   
00145     if (notaffected==0){
00146       // processing of the successfull possibility
00147       //------------------------------------------
00148       this->processing( numfalse, vec );
00149 
00150       /*
00151         cout<<"-----> Proposition : ";
00152         for ( j=0; j<_size; j++ )
00153         cout<<vec[j]<<" ";
00154         cout<<endl;
00155       */
00156       // end processing of the successfull possibility
00157       //----------------------------------------------
00158       _cardinal++;
00159     }
00160     else{
00161       // jump to avoid synonymous possibilities
00162       int jump = _pow[_size-notaffected];
00163       // all the possibilities
00164       for ( i=0; i<_nbposs; i+=jump ){
00165         /*
00166           cout<<"Possibility : ";
00167           for ( j=0; j<notaffected; j++ )
00168           cout<<_possib[i][j]<<" ";
00169           cout<<endl;
00170         */
00171 
00172         snif = 0;
00173         newnbfalse = 0;
00174         // "copy" of the possibility in the vector
00175         for ( j=0; j<_size; j++ ){      
00176           // if not affected
00177           if ( vec[j]==0 ){
00178             // FOR EACH FALSE, you put a NUMFALSE
00179             if ( _possib[i][snif++] == false ){
00180               vec[j] = numfalse;
00181               newnbfalse++;
00182             }
00183           }
00184         }
00185   
00186         cutoff_r( vec, 
00187                   newnbfalse,  numfalse+1,
00188                   notaffected-newnbfalse );
00189  
00190         for ( j=0; j<_size; j++ )
00191           if ( vec[j] == numfalse )
00192             vec[j] = 0;
00193       }
00194     }
00195   }
00196 
00198   virtual void processing( short numfalse,
00199                            const vector<short> & vec ) = 0;
00200 
00201  public :   
00202 
00204   Partition_box( ){
00205     _size = 0;
00206     _currpart = 0;
00207     _cardinal = 0;
00208     _pow = NULL;
00209     _nbposs = 0;
00210     _possib = NULL;
00211   }
00212 
00214   Partition_box( short size_ensemble ){
00215     _size = size_ensemble;
00216     _currpart = 0;
00217     if (size_ensemble<14){
00218       long card = approx_cardinal();  
00219       /* 
00220          cout<<"max: "<<_partition.max_size()<<endl;      
00221          cout<<"card: "<<card<<endl;   
00222          if (card > _partition.max_size()){
00223          cerr<<"Partition_box: No space left -> alphabet too wide -> too many possible partitions"
00224          <<endl;
00225          exit(1);
00226          }
00227       */
00228       _partition.reserve( card );
00229     } 
00230     _cardinal = 0;
00231     _pow = NULL; 
00232     _nbpartition_with_nbelement.assign(_size,0);
00233   }
00234 
00236   Partition_box( const Partition_box & p ){
00237     _size = p._size;
00238     _currpart = p._currpart;
00239     _partition.reserve = p._partition;    
00240     _cardinal = p._cardinal;
00241     _pow = NULL;
00242   }
00243   
00245   virtual ~Partition_box(){
00246     if (_pow)
00247       delete [] _pow;
00248   };
00249 
00251   void cutoff(){
00252     vector<short> v(_size, 0);
00253     this->init_possib();
00254     _cardinal = 0;
00255     cutoff_r(v, _size, 1, _size);
00256     this->delete_possib();
00257   }
00258 
00260   long tell_cardinal() const{
00261     return _cardinal;
00262   }
00263   
00265   long tell_size() const{
00266     return _size;
00267   }
00268 
00270   const Tpart & element( int i) const{
00271     return _partition[i];
00272   }
00273 
00275   const vector< int >& nbpartition_with_nbelement() const{
00276     return _nbpartition_with_nbelement;
00277   } 
00278 
00280   const vector< int >& compute_nbpartition_with_nbelement(){
00281     int i, s= _partition.size();
00282     _nbpartition_with_nbelement.clear();
00283     _nbpartition_with_nbelement.assign(_size,0);
00284     for (i=0; i<s; i++)
00285       _nbpartition_with_nbelement[ _partition[i].size()-1 ]++;
00286     return _nbpartition_with_nbelement;
00287   }
00288 
00289   //_________________________________________// 
00290   class const_iterator{
00291   private :
00292     const Partition_box<Tpart> * _part_box; 
00293     long _currpart;
00294   protected : 
00295     friend class Partition_box;
00296     const_iterator( const Partition_box<Tpart> & p, long currpart ){
00297       _part_box = &p;
00298       _currpart = currpart;
00299       if (p._cardinal == 0)
00300         cerr<<" cutoff required !"<<endl;
00301     }
00302   public :
00303     const_iterator( ){
00304       _currpart = -1;
00305       _part_box = NULL;
00306     } 
00308     bool operator ++ () {
00309       // check if the next is the end()
00310       if ( _currpart<_part_box->_cardinal-1 ){
00311         _currpart++;
00312         return true;
00313       }
00314       else{
00315         _currpart++;
00316         return false;
00317       } 
00318     }
00320     bool operator ++ (int) {
00321       // check if the next is the end()
00322       if ( _currpart<_part_box->_cardinal-1 ){
00323         _currpart++;
00324         return true;
00325       }
00326       else{
00327         _currpart++;
00328         return false;
00329       }
00330     }
00332     bool operator != ( const const_iterator & p ) const{
00333       return ( (p._part_box !=_part_box) 
00334                || (p._currpart !=_currpart) );
00335     }
00337     bool operator == ( const const_iterator & p ) const{
00338       return ( (p._part_box ==_part_box) 
00339                && (p._currpart ==_currpart) );
00340     }
00342     const Tpart& operator * () const{
00343       return _part_box->_partition[_currpart];
00344     }
00345 
00346     const_iterator operator = (  const const_iterator & p ){
00347       if (  p != *this ){
00348         _part_box =  p._part_box;
00349         _currpart = p._currpart;
00350       }
00351      return *this;
00352     }
00353   };
00354 
00356   const_iterator begin() const{
00357     return const_iterator( *this, 0 );
00358   }
00360   const_iterator end() const{
00361     return const_iterator( *this, _cardinal );
00362   }  
00363   //_________________________________________//
00364 };
00365 
00366 
00367 #endif //PARTITION_BOX_H



Download seq++ 4.1.5
Download previous versions
Statistique & Genome Home


Generated on Thu Aug 4 20:33:12 2005 for seqpp by doxygen 1.3.9.1