Version 4.0.0
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;
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       for (i=0; i<_nbposs; i++){
00100       for (si=0; si<_size; si++)
00101       cout<<_possib[i][si]<<" ";
00102       cout<<endl;
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       // processing of the successfull possibility
00142       //------------------------------------------
00143       this->processing( numfalse, vec );
00144 
00145       /*
00146         cout<<"-----> Proposition : ";
00147         for ( j=0; j<_size; j++ )
00148         cout<<vec[j]<<" ";
00149         cout<<endl;
00150       */
00151       // end processing of the successfull possibility
00152       //----------------------------------------------
00153       _cardinal++;
00154     }
00155     else{
00156       // jump to avoid synonymous possibilities
00157       int jump = _pow[_size-notaffected];
00158       // all the possibilities
00159       for ( i=0; i<_nbposs; i+=jump ){
00160         /*
00161           cout<<"Possibility : ";
00162           for ( j=0; j<notaffected; j++ )
00163           cout<<_possib[i][j]<<" ";
00164           cout<<endl;
00165         */
00166 
00167         snif = 0;
00168         newnbfalse = 0;
00169         // "copy" of the possibility in the vector
00170         for ( j=0; j<_size; j++ ){      
00171           // if not affected
00172           if ( vec[j]==0 ){
00173             // FOR EACH FALSE, you put a NUMFALSE
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          cout<<"max: "<<_partition.max_size()<<endl;      
00216          cout<<"card: "<<card<<endl;   
00217          if (card > _partition.max_size()){
00218          cerr<<"Partition_box: No space left -> alphabet too wide -> too many possible partitions"
00219          <<endl;
00220          exit(1);
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       // check if the next is the end()
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       // check if the next is the end()
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



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


Generated on Wed Mar 23 09:25:57 2005 for seqpp by doxygen 1.3.9.1