GenerateUpToLength.h

Go to the documentation of this file.

 
#pragma once
 
#include <grammar/Grammar.h>
#include <string/LinearString.h>
#include <alib/set>
#include <alib/deque>
#include <alib/trie>
#include <ext/iterator>
 
#include <grammar/ContextFree/EpsilonFreeCFG.h>
#include <grammar/ContextFree/GNF.h>
#include <grammar/ContextFree/CNF.h>
#include <grammar/Regular/LeftRG.h>
#include <grammar/Regular/RightRG.h>
 
#include <grammar/RawRules.h>
 
namespace grammar {
 
namespace generate {
 
class GenerateUpToLength {
    template < class TerminalSymbolType >
    static bool pruneTrie ( ext::trie < TerminalSymbolType, bool > & trie ) {
        for ( typename std::map < TerminalSymbolType, ext::trie < TerminalSymbolType, bool > >::iterator iter = trie.getChildren ( ).begin ( ); iter != trie.getChildren ( ).end ( ); )
            if ( pruneTrie ( iter->second ) )
                iter = trie.erase ( iter );
            else
                ++ iter;
 
        return trie.getData ( ) == false && trie.getChildren ( ).empty ( );
    }
 
public:
    template < class T, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T >, class NontermimnalSymbolType = typename grammar::NonterminalSymbolTypeOfGrammar < T > >
    static ext::trie < TerminalSymbolType, bool > generate ( const T & grammar, unsigned length );
};
 
template < class T, class TerminalSymbolType, class NonterminalSymbolType >
ext::trie < TerminalSymbolType, bool > GenerateUpToLength::generate ( const T & grammar, unsigned length ) {
    ext::trie < TerminalSymbolType, bool > res ( false );
 
    ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > rules = grammar::RawRules::getRawRules ( grammar );
    if ( grammar.getGeneratesEpsilon ( ) ) {
        res.getData ( ) = true; // TODO improve interface
        rules [ grammar.getInitialSymbol ( ) ].erase ( ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { } );
    }
 
    struct Node {
        ext::variant < TerminalSymbolType, NonterminalSymbolType > m_symbol;
        std::shared_ptr < Node > m_parent;
        unsigned m_depth;
 
        Node ( ext::variant < TerminalSymbolType, NonterminalSymbolType > symbol, std::shared_ptr < Node > parent, unsigned depth ) : m_symbol ( std::move ( symbol ) ), m_parent ( std::move ( parent ) ), m_depth ( depth ) {
        }
    };
 
    ext::deque < std::tuple < typename ext::trie < TerminalSymbolType, bool > *, unsigned, std::shared_ptr < Node > > > data;
    data.push_back ( std::make_tuple ( & res, 0, std::make_shared < Node > ( grammar.getInitialSymbol ( ), nullptr, 1 ) ) );
 
    while ( ! data.empty ( ) ) {
        unsigned generatedLen = std::get < 1 > ( data.back ( ) );
        typename ext::trie < TerminalSymbolType, bool > * trieNode = std::get < 0 > ( data.back ( ) );
 
        std::shared_ptr < Node > stackTop = std::get < 2 > ( data.back ( ) );
        ext::variant < TerminalSymbolType, NonterminalSymbolType > top = stackTop->m_symbol;
        unsigned stackSize = stackTop->m_depth - 1;
        stackTop = stackTop->m_parent;
 
        data.pop_back ( );
 
        if ( ! top.template is < NonterminalSymbolType > ( ) ) // maybe not needed
            continue;
        auto rule = rules.find ( top.template get < NonterminalSymbolType > ( ) );
        if ( rule == rules.end ( ) )
            continue;
 
        for ( const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rhs : rule->second ) {
            if ( generatedLen + stackSize + rhs.size ( ) > length )
                continue;
 
            std::shared_ptr < Node > newStackTop = stackTop;
            for ( const ext::variant < TerminalSymbolType, NonterminalSymbolType > & symbol : ext::make_reverse ( rhs ) )
                newStackTop = std::make_shared < Node > ( symbol, newStackTop, newStackTop ? newStackTop->m_depth + 1 : 1 );
 
            typename ext::trie < TerminalSymbolType, bool > * newTrieNode = trieNode;
            unsigned newGeneratedLen = generatedLen;
            while ( newStackTop != nullptr && grammar.getTerminalAlphabet ( ).count ( newStackTop->m_symbol ) ) {
                newTrieNode->insert ( newStackTop->m_symbol.template get < TerminalSymbolType > ( ), ext::trie < TerminalSymbolType, bool > ( false ) );
                newTrieNode = & newTrieNode->getChildren ( ).at ( newStackTop->m_symbol.template get < TerminalSymbolType > ( ) );
                newStackTop = newStackTop->m_parent;
                newGeneratedLen += 1;
            }
 
            if ( newStackTop == nullptr ) {
                newTrieNode->getData ( ) = true;
            } else {
                data.push_back ( std::make_tuple ( newTrieNode, newGeneratedLen, newStackTop ) );
            }
        }
    }
 
    pruneTrie ( res );
 
    return res;
}
 
} /* namespace generate */
 
} /* namespace grammar */