CompactSuffixAutomatonTerminatingSymbol.h

Go to the documentation of this file.

 
#pragma once
 
#include <ext/iostream>
 
#include <alib/string>
#include <alib/map>
 
#include <common/DefaultSymbolType.h>
 
#include <sax/FromXMLParserHelper.h>
#include <core/xmlApi.hpp>
#include <primitive/xml/Unsigned.h>
#include <primitive/xml/UnsignedLong.h>
#include <container/xml/ObjectsVector.h>
#include <container/xml/ObjectsMap.h>
 
#include <alphabet/common/SymbolNormalize.h>
 
#include <automaton/FSM/CompactDFA.h>
 
namespace indexes {
 
namespace stringology {
 
class GeneralAlphabet;
 
template < class SymbolType = DefaultSymbolType >
class CompactSuffixAutomatonTerminatingSymbol {
    ext::vector < SymbolType > m_string;
    ext::vector < ext::map < ext::pair < size_t, size_t >, unsigned > > m_delta;
 
public:
    void setString(const ext::vector < SymbolType > & str) {
        m_string = str;
    }
 
    const ext::vector < SymbolType > & getString ( ) const & {
        return m_string;
    }
 
    ext::vector < SymbolType > && getString ( ) && {
        return std::move ( m_string );
    }
 
    void setNumberOfVertices(int n) {
        m_delta.resize(n);
    }
 
    void insertVertex(unsigned vertexNumber, const ext::map<ext::pair< int,int>,int> & edges) {
        for(const auto & edge : edges ) {
            m_delta[vertexNumber].insert({{edge.first.first - 1, edge.first.second - 1}, edge.second}); // to match indexing the string from 0
        }
    }
 
    const ext::vector < ext::map < ext::pair < size_t, size_t >, unsigned > > & getTransitions ( ) const & {
        return m_delta;
    }
 
    ext::vector < ext::map < ext::pair < size_t, size_t >, unsigned > > && getTransitions ( ) && {
        return std::move ( m_delta );
    }
 
    bool addTransition ( unsigned from, size_t startIndex, size_t endIndex, unsigned to ) {
        return m_delta [ from ].insert ( ext::make_pair ( ext::make_pair ( startIndex, endIndex ), to ) ).second;
    }
 
    void setTransitions ( ext::vector < ext::map < ext::pair < size_t, size_t >, unsigned > > delta ) {
        m_delta = std::move ( delta );
    }
 
/*  void print() {
        cout << "PRINT" << endl;
        cout << m_delta.size() << endl;
        for(int i = 0;i<m_delta.size();i++) {
            cout << "Vrchol " << i << endl;
            for(auto it = m_delta[i].begin(); it != m_delta[i].end(); ++it) {
                cout << it->first.first << "  " << it->first.second << endl;
                cout << "      -- ";
                for(int j = it->first.first;j<=it->first.second;j++) {
                    cout << m_string[j];
                }
                cout << " --> " << it->second << endl;
            }
        }
    }*/
 
    void GetAllPathsLen(unsigned state, unsigned curLen, ext::set < unsigned > & res) const {
        if(m_delta[state].empty ( ))
            res.insert(m_string.size ( ) - curLen);
 
        for(auto it = m_delta[state].begin();it!=m_delta[state].end();++it) {
            GetAllPathsLen(it->second,curLen+it->first.second-it->first.first+1,res);
        }
    }
 
    unsigned GetNextState(unsigned state,const ext::vector <SymbolType > & pattern, unsigned & index) const {
        for(auto it = m_delta[state].begin();it!=m_delta[state].end();++it) {
            if( m_string[it->first.first] != pattern[index])//hledám hranu, která má první znak stejný
                continue;
 
            for(unsigned i = it->first.first;i<=it->first.second;i++) { //chci projít všechny znaky, jestli se shodují se vzorem
                if(index == pattern.size()) {
                    index += (it->first.second-i+1);
                    return it->second;
                }
 
                if(m_string[i] != pattern[index++]) { //pokud se neshodují - konec
                    throw "notfound";
                }
            }
            return it->second;
        }
 
        throw "notfound";
    }
 
    friend ext::ostream & operator << ( ext::ostream & out, const CompactSuffixAutomatonTerminatingSymbol & instance ) {
        return out << "(CompactSuffixAutomatonTerminatingSymbol " << instance.m_string << ", " << instance.m_delta << ")";
    }
 
    auto operator <=> ( const CompactSuffixAutomatonTerminatingSymbol & other ) const {
        return std::tie ( getString ( ), getTransitions ( ) ) <=> std::tie ( other.getString ( ), other.getTransitions ( ) );
    }
 
    bool operator == ( const CompactSuffixAutomatonTerminatingSymbol & other ) const {
        return std::tie ( getString ( ), getTransitions ( ) ) == std::tie ( other.getString ( ), other.getTransitions ( ) );
    }
 
    explicit operator automaton::CompactDFA < SymbolType, unsigned > ( ) const;
};
 
template < class SymbolType >
CompactSuffixAutomatonTerminatingSymbol < SymbolType >::operator automaton::CompactDFA < SymbolType, unsigned > ( ) const {
    automaton::CompactDFA < SymbolType, unsigned > res ( 0 );
    res.setInputAlphabet ( ext::set < SymbolType > ( getString ( ).begin ( ), getString ( ).end ( ) ) );
 
    ext::set < unsigned > states;
    for ( size_t state = 0; state < getTransitions ( ).size ( ); ++ state )
        states.insert ( state );
    res.setStates ( std::move ( states ) );
 
    res.addFinalState ( 1 );
 
    for ( size_t state = 0; state < getTransitions ( ).size ( ); ++ state )
        for ( const std::pair < const ext::pair < size_t, size_t >, unsigned > & transition : getTransitions ( ) [ state ] )
            res.addTransition ( state, ext::vector < SymbolType > ( getString ( ).begin ( ) + transition.first.first, getString ( ).begin ( ) + transition.first.second + 1 ), transition.second );
 
    return res;
}
 
} /* namespace stringology */
 
} /* namespace indexes */
 
namespace core {
 
template < class SymbolType >
struct normalize < indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < SymbolType > > {
    static indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < > eval ( indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < SymbolType > && value ) {
        indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < DefaultStateType > res;
        res.setString ( alphabet::SymbolNormalize::normalizeSymbols ( std::move ( value ).getString ( ) ) );
        res.setTransitions ( std::move ( value ).getTransitions ( ) );
 
        return res;
    }
};
 
template < class SymbolType >
struct xmlApi < indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < SymbolType > > {
    static indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < SymbolType > parse ( ext::deque < sax::Token >::iterator & input );
    static bool first ( const ext::deque < sax::Token >::const_iterator & input );
    static std::string xmlTagName ( );
    static void compose ( ext::deque < sax::Token > & output, const indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < SymbolType > & index );
};
 
template < class SymbolType >
indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < SymbolType > xmlApi < indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < SymbolType > >::parse ( ext::deque < sax::Token >::iterator & input ) {
    sax::FromXMLParserHelper::popToken ( input, sax::Token::TokenType::START_ELEMENT, xmlTagName ( ) );
    ext::vector < SymbolType > string = core::xmlApi < ext::vector < SymbolType > >::parse ( input );
    ext::vector < ext::map < ext::pair < size_t, size_t >, unsigned > > delta = core::xmlApi < ext::vector < ext::map < ext::pair < size_t, size_t >, unsigned > > >::parse ( input );
    indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < SymbolType > res;
    res.setString ( std::move ( string ) );
    res.setTransitions ( std::move ( delta ) );
 
    sax::FromXMLParserHelper::popToken ( input, sax::Token::TokenType::END_ELEMENT, xmlTagName ( ) );
    return res;
}
 
template < class SymbolType >
bool xmlApi < indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < SymbolType > >::first ( const ext::deque < sax::Token >::const_iterator & input ) {
    return sax::FromXMLParserHelper::isToken ( input, sax::Token::TokenType::START_ELEMENT, xmlTagName ( ) );
}
 
template < class SymbolType >
std::string xmlApi < indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < SymbolType > >::xmlTagName ( ) {
    return "CompactSuffixAutomatonTerminatingSymbol";
}
 
template < class SymbolType >
void xmlApi < indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < SymbolType > >::compose ( ext::deque < sax::Token > & output, const indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < SymbolType > & index ) {
    output.emplace_back ( xmlTagName ( ), sax::Token::TokenType::START_ELEMENT );
    core::xmlApi < ext::vector < SymbolType > >::compose ( output, index.getString ( ) );
    core::xmlApi < ext::vector < ext::map < ext::pair < size_t, size_t >, unsigned > > >::compose ( output, index.getTransitions ( ) );
    output.emplace_back ( xmlTagName ( ), sax::Token::TokenType::END_ELEMENT );
}
 
} /* namespace core */