Total.h

Go to the documentation of this file.

 
/*
 * This file is part of Algorithms library toolkit.
 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
 
 * Algorithms library toolkit is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 
 * Algorithms library toolkit is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 
 * You should have received a copy of the GNU General Public License
 * along with Algorithms library toolkit.  If not, see <http://www.gnu.org/licenses/>.
 */
 
#pragma once
 
#include <exception/CommonException.h>
 
#include <automaton/FSM/NFA.h>
#include <automaton/FSM/DFA.h>
#include <automaton/TA/DFTA.h>
#include <automaton/TA/NFTA.h>
 
#include <label/FailStateLabel.h>
#include <common/createUnique.hpp>
 
namespace automaton {
 
namespace simplify {
 
class Total {
    template < class StateType, class Callback >
    static void CombinationRepetitionUtil ( const ext::set < StateType > & states, ext::vector < StateType > & stateList, size_t length, Callback callback ) {
        if ( stateList.size ( ) == length )
            callback ( stateList );
        else for ( const StateType & state : states ) {
            stateList.push_back ( state );
            CombinationRepetitionUtil ( states, stateList, length, callback );
            stateList.pop_back ( );
        }
    }
 
    template < class StateType, class Callback >
    static void CombinationRepetition ( ext::set < StateType > states, size_t length, Callback callback ) {
        ext::vector < StateType > stateList;
        CombinationRepetitionUtil ( states, stateList, length, callback );
    }
 
public:
    template < class T >
    requires isDFA < T > || isNFA < T >
    static T total ( const T & automaton );
 
    template < class T >
    requires isDFTA < T > || isNFTA < T >
    static T total ( const T & automaton );
};
 
template < class T >
requires isDFA < T > || isNFA < T >
T Total::total ( const T & automaton ) {
    using StateType = typename T::StateType;
 
    if ( automaton.isTotal ( ) )
        return automaton;
 
    T res ( automaton );
    StateType nullState = common::createUnique ( label::FailStateLabel::instance < StateType > ( ), automaton.getStates ( ) );
    res.addState ( nullState );
 
    for ( const auto & q : res.getStates ( ) ) {
        for ( const auto & a : res.getInputAlphabet ( ) ) {
            if ( ! res.getTransitions ( ).contains ( ext::make_pair ( q, a ) ) ) {
                res.addTransition ( q, a, nullState );
            }
        }
    }
 
    return res;
}
 
template < class T >
requires isDFTA < T > || isNFTA < T >
T Total::total ( const T & automaton ) {
    using StateType = typename T::StateType;
 
    T res ( automaton );
    StateType nullState = common::createUnique ( label::FailStateLabel::instance < StateType > ( ), automaton.getStates ( ) );
    res.addState ( nullState );
 
    for ( const auto & a : res.getInputAlphabet ( ) ) {
        unsigned rank = a.getRank ( );
        CombinationRepetition ( res.getStates ( ), rank, [ & ] ( const ext::vector < StateType > & stateList ) {
            if ( ! res.getTransitions ( ).contains ( ext::make_pair ( a, stateList ) ) ) {
                res.addTransition ( a, stateList, nullState );
            }
        } );
    }
 
    return res;
}
 
} /* namespace simplify */
 
} /* namespace automaton */