main page namespaces classes files
BIU home

src/biu/Alphabet.cc

Go to the documentation of this file.

#include <biu/Alphabet.hh>
#include <biu/assertbiu.hh>

#include <iostream>
#include <math.h>

namespace biu {
    
    Alphabet::Alphabet( const std::string& alphabetString, 
                        const size_t _elementLength)
     : elementLength(_elementLength) 
    {
        assertbiu (alphabetString.length() % elementLength == 0,
    "length of the alphabetstring has to be multiple of the element length");
            
             // initialisieren
        alph2string = std::vector<std::string>( 
                            alphabetString.length() / elementLength, "");
        AlphElem actElem = 0;
        std::string actStr = "";
        for (std::string::size_type i = 0; i<alphabetString.length(); 
                    i+= elementLength) {
            actStr = alphabetString.substr(i,elementLength);
            string2alph[actStr] = actElem;
            alph2string[actElem] = actStr;
            actElem++;
        }
    }

    Alphabet::Alphabet(const std::vector<std::string> & alphabetStrings) {

        size_t alphabetSize=alphabetStrings.size();

        assertbiu (alphabetSize>0,"No init of empty alphabet allowed");
        
        elementLength = alphabetStrings[0].length();
        
#ifdef NDEBUG
        {
            size_t i;
            for(i=0; i<alphabetSize; i++) {
                assertbiu(alphabetStrings[i].length() == elementLength, 
                          "All strings must have equal length");
            }
        }
#endif
        
        alph2string = std::vector<std::string>(alphabetSize, "");
        
        AlphElem actElem = 0;
        std::string actStr = "";
        for (std::string::size_type i = 0; i<alphabetSize; i++) {
            actStr = alphabetStrings[i];
            string2alph[actStr] = actElem;
            alph2string[actElem] = actStr;
            actElem++;
        }
    }

    Alphabet::~Alphabet() {     
    }

    bool            
    Alphabet::operator== (const Alphabet& alph2) const {
        return string2alph == alph2.string2alph
            && alph2string == alph2.alph2string
            && elementLength == alph2.elementLength;
    }

    bool            
    Alphabet::operator!= (const Alphabet& alph2) const {
        return string2alph != alph2.string2alph
            && alph2string != alph2.alph2string
            && elementLength != alph2.elementLength;
    }

    // string to sequence to string

    Alphabet::Sequence 
    Alphabet::getSequence(const std::string& seqString) const {
        assertbiu (seqString.length() % elementLength == 0,
            "the sequence length has to be a multiple of the element length");
            
        Alphabet::Sequence seq(seqString.length() / elementLength,0);
        Alphabet::Sequence::size_type seqPos = 0; 
        for (std::string::size_type i=0; i<seqString.length(); 
                    i+= elementLength) {
            seq[seqPos++] = getElement(seqString.substr(i,elementLength));
        }
        return seq;
    }
    
    std::string 
    Alphabet::getString(const Alphabet::Sequence& sequence) const {
        std::string str(sequence.size()*elementLength,' ');
        std::string::size_type i = 0, j = 0; 
        for (Alphabet::Sequence::const_iterator it = sequence.begin(); 
                    it != sequence.end(); it++) {
            for (j=0; j<elementLength; j++) {
                str[i++] = alph2string.at(*it)[j];
            }
        }
        return str;
    }
    
    std::string 
    Alphabet::getString(const Alphabet::AlphElem& elem) const {
        assertbiu( elem < alph2string.size(), 
            "elem is no valid element of the alphabet");
        return alph2string.at(elem);
    }

    Alphabet::AlphElem 
    Alphabet::getElement(const std::string& alphElemStr) const {
        STR2ALPH_TYPE::const_iterator member = string2alph.find(alphElemStr);
        assertbiu(member != string2alph.end(),
            "element '"+alphElemStr+"' is no member of the alphabet");
        return member->second;
    }

    bool    
    Alphabet::isAlphabetString(const std::string& str) const {
                // muss vielfaches der elementlaenge sein
        bool retVal = (str.length() % elementLength == 0);
        for (std::string::size_type i = 0; retVal && i< str.size(); 
                i+=elementLength) {
            retVal =    string2alph.find(str.substr(i,elementLength)) 
                        != string2alph.end();
        }
        return retVal;
    }

    size_t 
    Alphabet::getIndex(const AlphElem& elem) const {
        return (size_t)elem;
    }
    
    size_t 
    Alphabet::getIndex(const std::string& elemStr) const {
        return getIndex(getElement(elemStr));
    }
    
    Alphabet::AlphElem 
    Alphabet::getElement(const size_t index) const {
        assertbiu(index < getAlphabetSize(), 
            "the index leaves the valid indices of the alphabet");
        return index;
    }
    
    
    Alphabet::CSequence
    Alphabet::compress(const Alphabet::Sequence& seq) const 
    {
            // base of the number system used for the compression
        size_t base = this->getAlphabetSize();
            // the number of positions that can be saved in a byte
        size_t numOfPos = (size_t) (log(256.) / log((double) base));
            // ceil (s->size() / numOfPos) bytes are necessary to save the
            // sequence
        CSequence cs(
         (size_t) ceil((double) seq.size() / (double) numOfPos), 0);

            // 1 byte = seq[0] * base^0 + ... + seq[numOfPos] * base^numOfPos
        for (size_t i = 0; i < seq.size(); i++) {
            cs[i/numOfPos] += seq.at(i) * (int) pow(base, i%numOfPos);
        }
        return cs;
    }

    Alphabet::Sequence
    Alphabet::decompress(const Alphabet::CSequence & seq, 
        const size_t seqLength) const 
    {
            // base of the number system used for the compression
        size_t base = this->getAlphabetSize();
            // the number of positions that can be saved in a byte
        size_t numOfPos = (size_t) (log(256.) / log((double) base));
        Sequence uncompressedSeq(seqLength, this->getElement(0));
            // element of cs which is currently processed
        unsigned char c = seq[0];

        assertbiu(seqLength <= seq.size()*numOfPos,
         "The compressed sequence can't hold <seqLength> many elements.");

            // 1 byte = s[0] * base^0 + ... + s[numOfPos-1] * base^(numOfPos-1)
        for (size_t i = 0; i < seqLength; i++) {
                // update c if new element of cs is processed
            if (i%numOfPos == 0) {
                c = seq[i/numOfPos];
            }
            uncompressedSeq[i] = this->getElement( c % base );
            c /= base;
        }

        return uncompressedSeq;
    }
    
    bool 
    Alphabet::isAlphabetSequence(const Alphabet::Sequence& seq) const {
        const size_t size  = getAlphabetSize();
        for (Sequence::const_iterator it = seq.begin(); it != seq.end(); it++) {
            if ((size_t)*it > size)
                return false;
        }
        return true;
    }
    
    
    
} // namespace biu