// -*- mode: c++; c-indent-level: 4; c++-member-init-indent: 8; c++-electric-colon: 1; c-auto-newline: 1;comment-column: 45; -*- // RAWGENE.CC : Function implementation for raw bits chromosome functions #include // header file for this one... #include "rawgene.hpp" const unsigned LENGTH_0 = 1, SIZE_0 = 2; const unsigned RAND_INTERVAL = 10000; const float RAND_DENOM = 10000.0; // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- void rawGene::mutate( double _mutationRate ) { // -- mutates genome string with given probability // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- for ( unsigned i = 0; i < length*BITSINBYTE; i ++ ) if ( ( myrand(RAND_INTERVAL)/RAND_DENOM ) < _mutationRate) changeBit( i ); } // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- void rawGene::checkNassign( unsigned _len) { // -- Checks number of alleles and size, and assigns values to the instance // variables // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- if (!_len) { cerr << "Null number of alleles\n"; exit( LENGTH_0 ); } length = _len; str = new char[ length ]; if (!str) { cerr << "New failed in rawGene::rawGene(u,u) - str\n"; exit(1); } } // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- rawGene::rawGene( unsigned _len ) { // -- constructor and conversion operator, from an unsigned integer // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- checkNassign( _len); for ( int i = 0; i < length; i ++ ) str[i] = myrand(MAX8BITS); } // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- rawGene::rawGene( char *_str ){ // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- unsigned tmp = strlen( _str); checkNassign( tmp ); memcpy( str, _str, length ); // already assigned in C&A } // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- // rawGene::rawGene( char *_str, float mutationRate ); // -- builds a chromosome from a string, with a fixed mutation rate // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- rawGene::rawGene( char *_str, unsigned _length, float _mutationRate ) { length = _length; str = new char[length]; if (!str) { cerr << "New failed in rawGene::rawGene - str\n"; exit( 3 ); } memcpy( str, _str, length ); // now performs mutation mutate( _mutationRate); } // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- rawGene::rawGene(rawGene &rawGene1, rawGene &rawGene2, double xOverRate, double MutationRate) { // -- Builds a rawGenee from rawGenee1 applying multipoint crossover // and mutation with given probabilities (over 1) // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- // Starting with gene 1 unsigned auxL = length = rawGene1.length; // computes length if (!(str = new char[auxL])) { // allocs memory cerr << "New failed in rawGene::rawGene 2 - str\n"; exit(1); } memcpy( str, rawGene1.getGenome(), length); // copies into genoome mutate( MutationRate ); // changes bits randomly unsigned auxL2 = rawGene2.length; if ( auxL2 < auxL ) // take smaller one auxL = auxL2; for ( unsigned long i = 0; i < auxL*BITSINBYTE; i ++ ) if ( ( myrand(RAND_INTERVAL)/RAND_DENOM ) < xOverRate) swapBit( i, rawGene2.getGenome() ); // changes bits randomly } // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- rawGene::rawGene( rawGene &rawGene1, rawGene &rawGene2, double xOverRate) { // -- Builds a gene from rawGenee1 applying only multipoint crossover // (uniform crossover) // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- // Starting with rawGenee1 unsigned auxL = length = rawGene1.length; // computes length if (!(str = new char[auxL])) { // allocs memory cerr << "New failed in rawGene::rawGene 2 - str\n"; exit(3); } memcpy( str, rawGene1.getGenome(), length); // copies into rawGeneome unsigned auxL2 = rawGene2.length; if ( auxL2 < auxL ) // take smaller one auxL = auxL2; for ( int i = 0; i < auxL*BITSINBYTE; i ++ ) if ( ( myrand(RAND_INTERVAL)/RAND_DENOM ) < xOverRate) swapBit( i, rawGene2.getGenome() ); // changes bits randomly } // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- rawGene::rawGene( rawGene &rawGene1, rawGene &rawGene2, unsigned _startPoint, unsigned _endPoint, double _mutationRate ) // -- Builds a genome from 2 others using 2 point crossover with the said // points. These 2 points could have been generated inside, but had no // "function" formats left // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- { // Starting with gene1 == parent A unsigned auxL = length = rawGene1.length; // computes length if (!(str = new char[auxL])) { // allocs memory cerr << "New failed in rawGene::rawGene 2 - str\n"; exit(3); } memcpy( str, rawGene1.getGenome(), length); // copies into genome unsigned auxL2 = rawGene2.length; if ( auxL2 < auxL ) // take smaller one auxL = auxL2; // swapping as needed if ( _startPoint > _endPoint ) swap( _startPoint, _endPoint ); // check bounds; auxL is the smaller of the two if (_endPoint > auxL*BITSINBYTE ) _endPoint = auxL*BITSINBYTE; // now perform interchange swapChunk( _startPoint, _endPoint, rawGene2.getGenome() ); // and then mutate mutate( _mutationRate ); } // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= rawGene::rawGene( rawGene &rawGene1, double MutationRate) // -- Builds a rawGeneome by mutating rawGenee1, with given // MutationRate // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- { unsigned auxL = rawGene1.length; // computes length str = new char[auxL]; // allocs memory if (!str) { cerr << "No more Memory in rawGene( genVAr, double )\n"; exit(3); } length= auxL; memcpy( str, rawGene1.getGenome(), length); // copies into genome mutate( MutationRate ); } // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= rawGene::rawGene( rawGene& _inRGen ) { // -- Copy constructor // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= length= _inRGen.length; str = new char [length]; if ( str == 0 ) { cerr << "New failed when copying gene\n"; exit (3 ); } memcpy( str, _inRGen.str, length); } // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= void rawGene::changeBit ( unsigned long chBit) { // -- changes a single bit in the string // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= unsigned long chByte = chBit >> 3; // bit in chBit position is altered (by XORing it) str[chByte] ^= Wgts[(chBit & LASTBYTEN )+1]; } // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- void rawGene::swapBit (unsigned long swBit, const char* inStr){ // -- swaps a single bit in the string with the internal string // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- unsigned long swByte = swBit >> 3; // Se altera el bit de la posicion rnd (se le hace XOR) // bit in swBit position is altered (by XORing it) str[swByte] &= ~Wgts[(swBit & LASTBYTEN)+1]; // pone a 0 el bit que quieres copiar // sets to 0 the bit to copy str[swByte] |= (inStr[swByte] & Wgts [(swBit & LASTBYTEN)+1]); // copia el bit -- copies bit } // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- void rawGene::swapChunkByte ( unsigned char _scbStart, unsigned char _scbEnd, unsigned _idxByte, char _scbByte) { // -- swaps a chunk of bits between the internal byte of index idxByte // and the input byte // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- // first; creation of the mask unsigned char mask=0; unsigned char oneLeft = MAX8BITS/2; unsigned char oneRight = 1; // first, create mask from left for ( unsigned char i = 0; i < _scbStart; i ++ ) { mask |= oneLeft; oneLeft >>=1; } // now, from right for ( i = LASTBYTEN; i> _scbEnd; i-- ) { mask |= oneRight; oneRight <<=1; } // mask created :-) Now interchange. str[_idxByte] &= mask; _scbByte &= ~mask; str[_idxByte]|=_scbByte; } // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- void rawGene::swapChunk ( unsigned long _swBitStart, unsigned long _swBitEnd, const char *inStr ) { // -- swaps all the bytes between the start bit and the end bit; // ie. from 0 to _swBit_start from the inside string; from _swBitStart // to _swBitEnd from the second string, and from _swBitEnd to the final // bit from the inside string // Good for 2-point crossover // Boundary check is on the user // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- unsigned long byteStart = _swBitStart / BITSINBYTE; unsigned long byteEnd = _swBitEnd / BITSINBYTE; if ( byteStart == byteEnd ) swapChunkByte(_swBitStart%BITSINBYTE, _swBitEnd %BITSINBYTE, byteStart, inStr[byteStart]); else { // different // start byte swapChunkByte(_swBitStart%BITSINBYTE, LASTBYTEN, byteStart, inStr[byteStart] ); // middle bytes for (unsigned long i = byteStart + 1; i < byteEnd; i ++ ) str[i] = inStr[i]; // end byte swapChunkByte( 0, _swBitEnd %BITSINBYTE, byteEnd, inStr[byteEnd]); } } //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- void rawGene::transposeChunk(unsigned long _trBitStart, unsigned long _trBitEnd, unsigned long _lenBits ) { // -- Intercharges _lenBits between Start position and End position //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- unsigned long trChStart = _trBitStart / BITSINBYTE; unsigned long trChEnd = _trBitEnd / BITSINBYTE; // create chunks of strings to perform swapping unsigned lenBytesChunk = (_trBitStart % BITSINBYTE + _lenBits )/BITSINBYTE +1 ; // If the bits are at the end, // several bytes will have to // be copied char* savedChunk = new char [lenBytesChunk]; memcpy( savedChunk, str+trChStart, lenBytesChunk); spliceInto( _trBitStart, str + trChEnd, _trBitEnd % BITSINBYTE, _lenBits ); spliceInto( _trBitEnd, savedChunk, _trBitStart % BITSINBYTE, _lenBits ); delete [] savedChunk; // almost forgot } // functions for splicing-=-=-=-=-=-=-=-=-=-=-=-=-=-= //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- void rawGene::shRight(char * _inStr, unsigned _pos, unsigned _len ) { // -- shifts the whole string some bits to the right, supposing that // _pos, or number of positions, is less than 7. Bits to the // right are lost. _len is the char array length //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- if ( ( _pos > LASTBYTEN ) || ( _pos == 0 ) ) return; // Now shifts are done in bul; first one byte is shifted // right and then a chunk of the preceding byte is copied // onto it for ( int i = _len - 1; i >= 0; i -- ) { _inStr[i] >>= _pos; // byte shifted right if ( i != 0) { // copies chunk from prev byte unsigned char tmp = _inStr[i-1]; tmp <<= ( BITSINBYTE - _pos ); // leaves last _pos bits to 0 _inStr[i] |= tmp; // concats both } } } //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- void rawGene::shLeft( char * _inStr, unsigned _pos, unsigned _len ) { // -- shifts the whole string some bits to the left, supposing that // _pos, or number of positions, is less than 7. Bits to the // right are lost. Len must be included, since there is binary info //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- if ( ( _pos > LASTBYTEN ) || ( _pos == 0 ) ) return; // Now shifts are done in bul; first one byte is shifted // right and then a chunk of the preceding byte is copied // onto it for ( int i = 0; i < _len ; i ++ ) { _inStr[i] <<= _pos; // byte shifted right if ( i < (_len -1) ) { // copies chunk from prev byte unsigned char tmp = _inStr[i+1]; tmp >>= ( BITSINBYTE - _pos ); // leaves last _pos bits to 0 _inStr[i] |= tmp; // concats both } } } //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- void rawGene::splice(unsigned long _insertBit, const char* _inStr, unsigned _numBits ) { // -- Insert a string of bits inside the genome. First the incoming // string is aligned, and then swapChunkByte is called //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- unsigned thisLen = _numBits/BITSINBYTE + 1;// length in bytes // compute if it spills over right boundary if ( ( _insertBit % BITSINBYTE + _numBits ) > (thisLen*BITSINBYTE ) ) thisLen++; char *tmpStr = new char [thisLen]; // Do not trust the length memcpy( tmpStr, _inStr, thisLen ); // To not alter the "constness" unsigned bitInByte = _insertBit % BITSINBYTE; // Position of the bit inside byte // counted from the left; first=0 shRight( tmpStr, bitInByte, thisLen ); // tmpStr is aligned unsigned long thisByte = _insertBit / BITSINBYTE; unsigned long lastBit = _insertBit + _numBits; unsigned long lastByte = lastBit / BITSINBYTE; if ( thisLen == 1 ) { swapChunkByte( _insertBit%BITSINBYTE, lastBit, thisByte, tmpStr[0] ); }else { swapChunkByte( _insertBit%BITSINBYTE, LASTBYTEN, thisByte, tmpStr[0] ); for ( unsigned i = thisByte + 1; i < lastByte; i ++ ) str[i] = tmpStr[ i - thisByte ]; swapChunkByte( 0, lastBit%BITSINBYTE, lastByte, tmpStr[thisLen - 1] ); } delete[] tmpStr; } //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- void rawGene::spliceInto(unsigned long _insertBit, const char* _inStr, unsigned long _insertBit2, unsigned _numBits ) { // -- Inserts from _insertBit2 of the _inStr string inside the // inner string, smashing what is below it. _numBits bits // are inserted; the second string must be aligned before // the insertion. _numBits must be less than 8, so that // alignment will not involve several bytes at once //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- unsigned bitInByte = _insertBit % BITSINBYTE; // Position of the bit inside byte // counted from the left; first=0 int diffBit = (int) _insertBit2 - bitInByte; // byte difference between // insertion points; typecasting // to avoid problems unsigned thisLen = (_insertBit2 + _numBits + abs(diffBit ) )/BITSINBYTE + 1;// length in bytes char *tmpStr = new char [thisLen]; // Do not trust the length memcpy( tmpStr, _inStr, thisLen ); // To not alter the "constness" // alignation (or however it is said) of both if ( diffBit > 0) // shift to the left shLeft( tmpStr, diffBit, thisLen ); // tmpStr is aligned else shRight( tmpStr, -diffBit, thisLen ); unsigned long thisByte = _insertBit / BITSINBYTE; unsigned long lastBit = _insertBit + _numBits; unsigned long lastByte = lastBit / BITSINBYTE; // recompute effective length of the string, based on the shifts it // has suffered if ( diffBit > 0 ) { // string has shrunk thisLen = ( _numBits - diffBit + _insertBit2 )/BITSINBYTE + 1; } if ( thisLen == 1 ) { swapChunkByte(_insertBit%BITSINBYTE, ( lastBit -1 )% BITSINBYTE, thisByte, tmpStr[0] ); }else { swapChunkByte( _insertBit%BITSINBYTE, LASTBYTEN, thisByte, tmpStr[0]); for ( unsigned i = thisByte + 1; i < lastByte; i ++ ) str[i] = tmpStr[ i - thisByte ]; swapChunkByte(0, ( lastBit - 1) %BITSINBYTE, lastByte, tmpStr[thisLen - 1] ); } delete[] tmpStr; } // variable-length operators-=-=-=-=-=-=-=-=-=-=-=-=-=-= //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- void rawGene:: addChunkEnd( unsigned _size ) { // -- adds a chunk of bytes at the end //-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- char *tmp = new char[length+_size]; if ( !tmp ) { cerr << "New failed in addAllele - tmp\n"; exit(3); } memcpy( tmp, str, length ); // copies old string delete []str; // deallocs memory and allocs again str = new char[length + _size]; if (!str) { cerr << "New failed in addAllele - str\n"; exit(3); } memcpy( str, tmp, length ); length+=_size; delete []tmp; for ( unsigned i = 1; i <= _size; i ++ ) str[ length - i ] = myrand( MAX8BITS ); // assigns random values } // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=--- void rawGene::dupChunk( unsigned _size, unsigned _pos ) { // -- eliminates a chunk of bytes, starting at the said position // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=--- if ( _pos * _size > length ) return; // everything is fine; now go on char *tmp = new char[length + _size]; if (!tmp) { cerr << "New failed in dupAllele - tmp\n"; return; } unsigned charIdx = _pos; memcpy( tmp, str, charIdx ); // copies old string, up to _pos memcpy( tmp + charIdx, str+ charIdx, _size ); // dups allele memcpy( tmp + charIdx + _size, str + charIdx, length - charIdx ); delete []str; // deallocs memory and allocs again length += _size; str = new char[length]; if (str == 0) { cerr << "New failed in dupAllele - str\n"; exit(3); } memcpy( str, tmp, length ); // with new length delete []tmp; // deallocs temp var } // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=--- void rawGene::killChunk( unsigned _size, unsigned _pos ) { // -- Eliminates _size bytes from the genome // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=--- if ( _pos * _size > length ) return; if ( length <= _size ) { // return if there is nothing left cerr << "Small enough, thanks\n"; return; } // everything is fine; now go on char *tmp = new char[length]; if (!tmp) { cerr << "New failed in killAllele - tmp\n"; return; } unsigned charIdx = _pos; memcpy( tmp, str, charIdx ); // copies old string, up to idx memcpy( tmp + charIdx, str + charIdx + _size, length - charIdx - _size); // and from idx delete []str; // deallocs memory and allocs again length -= _size; str = new char[length]; if (str == 0) { cerr<< "New failed in killAllele - str\n"; exit ( 0 ); } memcpy( str, tmp, length ); // with new length delete []tmp; // deallocs temp var } // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=--- // Friendly operators // -=-=-=-=-=-=-=-=-- // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=--- ostream& operator << ( ostream& s, const rawGene & _inGen ) { // -- to print a rawGene to stdout // -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=--- for ( unsigned long i = 0; i < _inGen.getNumBytes(); i ++ ) s << (int) (unsigned char) _inGen[i] << " "; return s; }