RegExpOptimizeUnboundedPart.hpp

Go to the documentation of this file.

 
#include <iostream>
 
namespace regexp::simplify {
 
template < class SymbolType >
void RegExpOptimize::optimize( UnboundedRegExpAlternation < SymbolType > & alt, bool recursive ) {
    while ( Unbounded < SymbolType >::A1( alt ) || Unbounded < SymbolType >::A2( alt ) || Unbounded < SymbolType >::A3( alt ) || Unbounded < SymbolType >::A4( alt ) );
 
    while ( Unbounded < SymbolType >::A8( alt ) || Unbounded < SymbolType >::A9( alt ) || Unbounded < SymbolType >::A10 ( alt ) || Unbounded < SymbolType >::V2 ( alt ) || Unbounded < SymbolType >::V5 ( alt ) || Unbounded < SymbolType >::V6 ( alt ) );
 
    for( size_t i = 0; i < alt.getChildren ( ).size ( ); i++ )
        alt.setChild ( std::move ( alt.getChild ( i ) ).template accept < ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > >, RegExpOptimize::Unbounded < SymbolType > > ( recursive ), i );
 
    while ( Unbounded < SymbolType >::A1( alt ) || Unbounded < SymbolType >::A2( alt ) || Unbounded < SymbolType >::A3( alt ) || Unbounded < SymbolType >::A4( alt ) || Unbounded < SymbolType >::A8( alt ) || Unbounded < SymbolType >::A9( alt ) || Unbounded < SymbolType >::A10( alt ) || Unbounded < SymbolType >::V2( alt ) || Unbounded < SymbolType >::V5( alt ) || Unbounded < SymbolType >::V6( alt ) || Unbounded < SymbolType >::X1( alt ) );
 
    for( size_t i = 0; i < alt.getChildren ( ).size ( ); i++ )
        alt.setChild ( std::move ( alt.getChild ( i ) ).template accept < ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > >, RegExpOptimize::Unbounded < SymbolType > > ( false ), i );
}
 
template < class SymbolType >
void RegExpOptimize::optimize( UnboundedRegExpConcatenation < SymbolType > & concat, bool recursive ) {
    while ( Unbounded < SymbolType >::A5( concat ) || Unbounded < SymbolType >::A6( concat ) || Unbounded < SymbolType >::A7( concat ) );
 
    while ( Unbounded < SymbolType >::V8 ( concat ) || Unbounded < SymbolType >::V8R ( concat ) || Unbounded < SymbolType >::V9( concat ) );
 
    for( size_t i = 0; i < concat.getChildren ( ).size ( ); i++ )
        concat.setChild ( std::move ( concat.getChild ( i ) ).template accept < ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > >, RegExpOptimize::Unbounded < SymbolType > > ( recursive ), i );
 
    while ( Unbounded < SymbolType >::A5( concat ) || Unbounded < SymbolType >::A6( concat ) || Unbounded < SymbolType >::A7( concat ) || Unbounded < SymbolType >::V8( concat ) || Unbounded < SymbolType >::V8R( concat ) || Unbounded < SymbolType >::V9( concat ) );
 
    for( size_t i = 0; i < concat.getChildren ( ).size ( ); i++ )
        concat.setChild ( std::move ( concat.getChild ( i ) ).template accept < ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > >, RegExpOptimize::Unbounded < SymbolType > > ( false ), i );
}
 
template < class SymbolType >
void RegExpOptimize::optimize( UnboundedRegExpIteration < SymbolType > & iter, bool recursive ) {
    iter.setChild ( std::move ( iter.getChild ( ) ).template accept < ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > >, RegExpOptimize::Unbounded < SymbolType > > ( recursive ) );
 
    while ( Unbounded < SymbolType >::A11( iter ) || Unbounded < SymbolType >::V1( iter ) || Unbounded < SymbolType >::V3( iter ) || Unbounded < SymbolType >::V4( iter ) || Unbounded < SymbolType >::V10( iter ) );
 
    iter.setChild ( std::move ( iter.getChild ( ) ).template accept < ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > >, RegExpOptimize::Unbounded < SymbolType > > ( false ) );
}
 
template < class SymbolType >
ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > RegExpOptimize::Unbounded < SymbolType >::visit ( UnboundedRegExpAlternation < SymbolType > && alt, bool recursive ) {
    optimize ( alt, recursive );
 
    if( alt.getElements ( ).size( ) == 1 )
        return ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > ( std::move ( alt.getChildren ( ).front ( ) ) );
 
    if( alt.getElements ( ).empty ( ) )
        return ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > ( UnboundedRegExpEmpty < SymbolType > ( ) );
 
    return ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > ( std::move ( alt ) );
}
 
template < class SymbolType >
ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > RegExpOptimize::Unbounded < SymbolType >::visit( UnboundedRegExpConcatenation < SymbolType > && concat, bool recursive ) {
    optimize ( concat, recursive );
 
    if( concat.getElements ( ).size( ) == 1 )
        return ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > ( std::move ( concat.getChildren ( ).front ( ) ) );
 
    if( concat.getElements ( ).empty ( ) )
        return ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > ( UnboundedRegExpEpsilon < SymbolType > ( ) );
 
    return ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > ( std::move ( concat ) );
}
 
template < class SymbolType >
ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > RegExpOptimize::Unbounded < SymbolType >::visit( UnboundedRegExpIteration < SymbolType > && iter, bool recursive ) {
    optimize ( iter, recursive );
 
    // V1 is implemented right here
    if( dynamic_cast < UnboundedRegExpEmpty < SymbolType > * > ( & iter.getChild ( ) ) )
        return ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > ( UnboundedRegExpEpsilon < SymbolType > ( ) );
 
    // T1 is implemented right here \e* = \e
    if ( dynamic_cast < UnboundedRegExpEpsilon < SymbolType > * > ( & iter.getChild ( ) ) )
        return ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > ( UnboundedRegExpEpsilon < SymbolType > ( ) );
 
    return ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > ( iter );
}
 
template < class SymbolType >
ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > RegExpOptimize::Unbounded < SymbolType >::visit( UnboundedRegExpSymbol < SymbolType > && node, bool ) {
    return ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > ( node );
}
 
template < class SymbolType >
ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > RegExpOptimize::Unbounded < SymbolType >::visit( UnboundedRegExpEmpty < SymbolType > && node, bool ) {
    return ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > ( node );
}
 
template < class SymbolType >
ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > RegExpOptimize::Unbounded < SymbolType >::visit( UnboundedRegExpEpsilon < SymbolType > && node, bool ) {
    return ext::ptr_value < regexp::UnboundedRegExpElement < SymbolType > > ( node );
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::A1( UnboundedRegExpAlternation < SymbolType > & node ) {
    bool optimized = false;
 
    for( auto it = node.begin( ); it != node.end( ); ) {
        if( dynamic_cast < UnboundedRegExpAlternation < SymbolType > * > ( & * it ) ) {
            UnboundedRegExpAlternation < SymbolType > childAlt ( static_cast < UnboundedRegExpAlternation < SymbolType > && > ( std::move ( * it ) ) );
            it = node.erase( it );
 
            it = node.insert ( it, std::make_move_iterator ( childAlt.begin ( ) ), std::make_move_iterator ( childAlt.end ( ) ) );
 
            optimized = true;
        } else
            it ++;
    }
 
    return optimized;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::A2( UnboundedRegExpAlternation < SymbolType > & node ) {
 
    auto cmp = [ ]( const UnboundedRegExpElement < SymbolType > * a, const UnboundedRegExpElement < SymbolType > * b ) -> bool { return * a < * b; };
 
    if ( std::is_sorted ( node.begin( ).base ( ), node.end( ).base ( ), cmp ) )
        return false;
 
    std::sort ( node.begin ( ).base ( ), node.end ( ).base ( ), cmp );
    return true;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::A3( UnboundedRegExpAlternation < SymbolType > & node ) {
    bool optimized = false;
 
    // alternation with no children is efectively \0
 
    for( auto it = node.begin ( ); it != node.end ( ); ) {
        if( dynamic_cast < UnboundedRegExpEmpty < SymbolType > * >( & * it ) ) {
            it = node.erase ( it );
 
            optimized = true;
        } else
            it ++;
    }
 
    return optimized;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::A4( UnboundedRegExpAlternation < SymbolType > & node ) {
 
    /*
     * two ways of implementing this opitimization:
     * - sort and call std::unique ( O(n lg n) + O(n) ), but it also sorts...
     * - check every element against other ( O(n*n) )
     *
     * As we always sort in optimization, we can use the first version, but A4 must be __always__ called __after__ A2
     */
    auto cmp = [ ]( const UnboundedRegExpElement < SymbolType > * a, const UnboundedRegExpElement < SymbolType > * b ) -> bool { return * a == * b; };
 
    size_t size = node.getChildren ( ).size ( );
    node.erase ( dereferencer ( ext::unique ( node.begin ( ).base ( ), node.end ( ).base ( ), cmp ) ), node.end( ) );
 
    return size != node.getChildren ( ).size ( );
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::A5( UnboundedRegExpConcatenation < SymbolType > & node ) {
    bool optimized = false;
 
    for( auto it = node.begin( ); it != node.end( ); ) {
        if( dynamic_cast < UnboundedRegExpConcatenation < SymbolType > * > ( & * it ) ) {
 
            UnboundedRegExpConcatenation < SymbolType > childConcat = static_cast < UnboundedRegExpConcatenation < SymbolType > && > ( std::move ( * it ) );
            it = node.erase ( it );
 
            it = node.insert ( it, std::make_move_iterator ( childConcat.begin( ) ), std::make_move_iterator ( childConcat.end( ) ) );
 
            optimized = true;
        } else
            ++ it;
    }
 
    return optimized;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::A6( UnboundedRegExpConcatenation < SymbolType > & node ) {
    bool optimized = false;
 
    // concatenation with no children is efectively \e
 
    for( auto it = node.begin( ); it != node.end( ); ) {
        if ( dynamic_cast < UnboundedRegExpEpsilon < SymbolType > * > ( & * it ) ) {
            it = node.erase ( it );
 
            optimized = true;
        } else
            ++ it;
    }
 
    return optimized;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::A7( UnboundedRegExpConcatenation < SymbolType > & node ) {
 
    if(node.getChildren ( ).size() == 1) return false;
 
    if( std::any_of ( node.begin( ), node.end( ), [ ] ( const UnboundedRegExpElement < SymbolType > & a ) -> bool { return dynamic_cast < const UnboundedRegExpEmpty < SymbolType > * > ( & a ); } ) ) {
        node.clear( );
        node.pushBackChild ( UnboundedRegExpEmpty < SymbolType > ( ) );
 
        return true;
    }
 
    return false;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::A8( UnboundedRegExpAlternation < SymbolType > & node ) {
    ext::map < ext::reference_wrapper < UnboundedRegExpElement < SymbolType > >, ext::vector < ext::reference_wrapper < UnboundedRegExpElement < SymbolType > > > > data;
 
    for ( UnboundedRegExpElement < SymbolType > & element : node ) {
        if ( UnboundedRegExpConcatenation < SymbolType > * childConcat = dynamic_cast < UnboundedRegExpConcatenation < SymbolType > * > ( & element ); childConcat ) {
            data [ ext::reference_wrapper < UnboundedRegExpElement < SymbolType > > ( childConcat->getChild ( 0 ) ) ].push_back ( ext::reference_wrapper < UnboundedRegExpElement < SymbolType > > ( element ) );
        } else {
            data [ ext::reference_wrapper < UnboundedRegExpElement < SymbolType > > ( element ) ].push_back ( ext::reference_wrapper < UnboundedRegExpElement < SymbolType > > ( element ) );
        }
    }
 
    if ( data.size ( ) == node.getChildren ( ).size ( ) )
        return false;
 
    UnboundedRegExpAlternation < SymbolType > res;
    for ( std::pair < ext::reference_wrapper < UnboundedRegExpElement < SymbolType > >, ext::vector < ext::reference_wrapper < UnboundedRegExpElement < SymbolType > > > > && entry : ext::make_mover ( data ) ) {
        if ( entry.second.size ( ) == 1 ) {
            res.appendElement ( std::move ( entry.second.front ( ).get ( ) ) );
        } else {
            UnboundedRegExpConcatenation < SymbolType > innerConcat;
            innerConcat.appendElement ( std::move ( entry.first.get ( ) ) );
            UnboundedRegExpAlternation < SymbolType > innerAlt;
            for ( ext::reference_wrapper < UnboundedRegExpElement < SymbolType > > & innerEntry : entry.second ) {
                UnboundedRegExpElement < SymbolType > & innerEntryElement = innerEntry.get ( );
                if ( UnboundedRegExpConcatenation < SymbolType > * innerEntryConcat = dynamic_cast < UnboundedRegExpConcatenation < SymbolType > * > ( & innerEntryElement ); innerEntryConcat ) {
                    if ( innerEntryConcat->getElements ( ).size ( ) == 1 ) {
                        innerAlt.appendElement ( UnboundedRegExpEpsilon < SymbolType > ( ) );
                    } else {
                        innerEntryConcat->erase ( innerEntryConcat->begin ( ) );
                        innerAlt.appendElement ( std::move ( * innerEntryConcat ) );
                    }
                } else {
                    innerAlt.appendElement ( UnboundedRegExpEpsilon < SymbolType > ( ) );
                }
            }
            innerConcat.insert ( innerConcat.end ( ), std::move ( innerAlt ) );
            res.appendElement ( Unbounded < SymbolType >::visit ( std::move ( innerConcat ), true ) );
        }
    }
 
    node = std::move ( res );
 
    return true;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::A9( UnboundedRegExpAlternation < SymbolType > & node ) {
    ext::map < ext::reference_wrapper < UnboundedRegExpElement < SymbolType > >, ext::vector < ext::reference_wrapper < UnboundedRegExpElement < SymbolType > > > > data;
 
    for ( UnboundedRegExpElement < SymbolType > & element : node ) {
        if ( UnboundedRegExpConcatenation < SymbolType > * childConcat = dynamic_cast < UnboundedRegExpConcatenation < SymbolType > * > ( & element ); childConcat ) {
            data [ ext::reference_wrapper < UnboundedRegExpElement < SymbolType > > ( childConcat->getChild ( childConcat->getElements ( ).size ( ) - 1 ) ) ].push_back ( ext::reference_wrapper < UnboundedRegExpElement < SymbolType > > ( element ) );
        } else {
            data [ ext::reference_wrapper < UnboundedRegExpElement < SymbolType > > ( element ) ].push_back ( ext::reference_wrapper < UnboundedRegExpElement < SymbolType > > ( element ) );
        }
    }
 
    if ( data.size ( ) == node.getChildren ( ).size ( ) )
        return false;
 
    UnboundedRegExpAlternation < SymbolType > res;
    for ( std::pair < ext::reference_wrapper < UnboundedRegExpElement < SymbolType > >, ext::vector < ext::reference_wrapper < UnboundedRegExpElement < SymbolType > > > > && entry : ext::make_mover ( data ) ) {
        if ( entry.second.size ( ) == 1 ) {
            res.appendElement ( std::move ( entry.second.front ( ).get ( ) ) );
        } else {
            UnboundedRegExpConcatenation < SymbolType > innerConcat;
            innerConcat.appendElement ( std::move ( entry.first.get ( ) ) );
            UnboundedRegExpAlternation < SymbolType > innerAlt;
            for ( ext::reference_wrapper < UnboundedRegExpElement < SymbolType > > & innerEntry : entry.second ) {
                UnboundedRegExpElement < SymbolType > & innerEntryElement = innerEntry.get ( );
                if ( UnboundedRegExpConcatenation < SymbolType > * innerEntryConcat = dynamic_cast < UnboundedRegExpConcatenation < SymbolType > * > ( & innerEntryElement ); innerEntryConcat ) {
                    if ( innerEntryConcat->getElements ( ).size ( ) == 1 ) {
                        innerAlt.appendElement ( UnboundedRegExpEpsilon < SymbolType > ( ) );
                    } else {
                        innerEntryConcat->erase ( innerEntryConcat->rbegin ( ) );
                        innerAlt.appendElement ( std::move ( * innerEntryConcat ) );
                    }
                } else {
                    innerAlt.appendElement ( UnboundedRegExpEpsilon < SymbolType > ( ) );
                }
            }
            innerConcat.insert ( innerConcat.begin ( ), std::move ( innerAlt ) );
            res.appendElement ( Unbounded < SymbolType >::visit ( std::move ( innerConcat ), true ) );
        }
    }
 
    node = std::move ( res );
 
    return true;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::A10( UnboundedRegExpAlternation < SymbolType > & node ) {
    bool optimized = false;
 
    /*
     * problem:
     * - \e + x*x = x*
     * - but if we do not have the eps, but we do have node that generates epsilon... It can actually be the x*x itself...
     */
 
    // check if we have some epsilon or iteration left, else nothing to do
    auto eps = find_if( node.getElements().begin( ), node.getElements().end( ), [ ]( const UnboundedRegExpElement < SymbolType > & a ) -> bool {
        return regexp::properties::RegExpEpsilon::languageContainsEpsilon ( a );
    });
 
    if( eps == node.getElements().end( ) )
        return false;
 
    for( size_t i = 0; i < node.getChildren ( ).size ( ); i++ ) {
        const UnboundedRegExpConcatenation < SymbolType > * childConcat = dynamic_cast < const UnboundedRegExpConcatenation < SymbolType > * > ( & node.getChildren ( ) [ i ]  );
        if( ! childConcat || childConcat->getElements ( ).size ( ) < 2 )
            continue;
 
        // if iteration is first element of concatenation
        const UnboundedRegExpIteration < SymbolType > * iter = dynamic_cast < const UnboundedRegExpIteration < SymbolType > * > ( & childConcat->getElements ( ).front( ) );
        if( ! iter )
            continue;
 
        // if element of iteration is concatenation, we need to check this specially
        const UnboundedRegExpConcatenation < SymbolType > * concat = dynamic_cast < const UnboundedRegExpConcatenation < SymbolType > * > ( & iter->getChild ( ) );
 
        if ( ( concat && equal ( concat->getChildren ( ).begin( ), concat->getChildren ( ).end ( ), childConcat->begin ( ) + 1 , childConcat->end ( ) ) ) || ( childConcat->getElements ( ).size ( ) == 2 && iter->getChild ( ) == childConcat->getElements ( ) [ 1 ] ) ) {
            optimized = true;
 
            node.setChild ( std::move ( childConcat->getElements().front() ), i );
        }
    }
 
    return optimized;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::A11( UnboundedRegExpIteration < SymbolType > & node ) {
 
    UnboundedRegExpAlternation < SymbolType > * childAlt = dynamic_cast<UnboundedRegExpAlternation < SymbolType > * >( & node.getChild ( ) );
 
    if( childAlt ) {
        // check if eps inside iteration's alternation
        auto eps = find_if ( childAlt->begin( ), childAlt->end( ), [ ] ( const UnboundedRegExpElement < SymbolType > & a ) -> bool {
            return dynamic_cast < const UnboundedRegExpEpsilon < SymbolType > * > ( & a );
        });
 
        // if no eps
        if ( eps == childAlt->end( ) )
            return false;
 
        // remove eps from alternation
        childAlt->erase ( eps );
        return true;
    }
 
    return false;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::V1( UnboundedRegExpIteration < SymbolType > &) {
    // implemented in optimize( UnboundedRegExpIteration < SymbolType > )
 
    return false;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::V2( UnboundedRegExpAlternation < SymbolType > & node ) {
    bool optimized = false;
 
    /*
     * Bit tricky
     * We need also to cover the cases like ( a + b + d )* + ( e )* + a + b + c + e = ( a + b + d )* + ( e )* + c
     */
 
    ext::vector < const UnboundedRegExpElement < SymbolType > * > iterElements;
    // cache iter elements because of operator invalidation after erase only cache nodes that are not iterations (the nodes omitted may only come from situation like x** where the double iteration wil get optimized out elsewhere).
    for( const UnboundedRegExpElement < SymbolType > & n : node.getElements ( ) ) {
        if ( const UnboundedRegExpIteration < SymbolType > * iter = dynamic_cast < const UnboundedRegExpIteration < SymbolType > * > ( & n ); iter ) {
            if ( const UnboundedRegExpAlternation < SymbolType > * inner = dynamic_cast < const UnboundedRegExpAlternation < SymbolType > * > ( & iter->getChild ( ) ); inner ) {
                for ( const UnboundedRegExpElement < SymbolType > & innerElement : inner->getElements ( ) ) {
                    if ( ! dynamic_cast < const UnboundedRegExpIteration < SymbolType > * > ( & innerElement ) )
                        iterElements.push_back ( & innerElement );
                }
            }
            else if ( ! dynamic_cast < const UnboundedRegExpIteration < SymbolType > * > ( & iter->getChild ( ) ) ) {
                    iterElements.push_back ( & iter->getChild ( ) );
            }
        }
    }
 
    for( const UnboundedRegExpElement < SymbolType > * n : iterElements ) {
        auto it = find_if ( node.getChildren ( ).begin ( ), node.getChildren ( ).end ( ), [ n ] ( const UnboundedRegExpElement < SymbolType > & a ) -> bool {
            return a == *n;
        });
 
        if( it == node.getChildren ( ).end ( ) ) {
            continue;
        }
 
        optimized = true;
        node.erase( it );
    }
 
    return optimized;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::V3 ( UnboundedRegExpIteration < SymbolType > & node ) {
 
    if ( UnboundedRegExpIteration < SymbolType > * childIter = dynamic_cast < UnboundedRegExpIteration < SymbolType > * > ( & node.getChild ( ) ); childIter ) {
        node.setChild ( std::move ( childIter->getChild ( ) ) );
 
        return true;
    }
 
    return false;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::V4( UnboundedRegExpIteration < SymbolType > & node ) {
 
    // interpretation: if iteration's element is concat and every concat's element is iteration
    // or if iteration's element is alternation and inside it, there is a concat wher every concat's element is iteration
    auto areAllItersInConcat = [] ( UnboundedRegExpElement < SymbolType > & testedNode ) {
        UnboundedRegExpConcatenation < SymbolType > * cont = dynamic_cast < UnboundedRegExpConcatenation < SymbolType > * > ( & testedNode );
        return cont && all_of ( cont->begin( ), cont->end ( ), [ ] ( const UnboundedRegExpElement < SymbolType > & a ) -> bool { return dynamic_cast < const UnboundedRegExpIteration < SymbolType > * > ( & a ); } );
    };
 
    auto toAlternationOfChildren = [] ( UnboundedRegExpConcatenation < SymbolType > & cont ) {
        UnboundedRegExpAlternation < SymbolType > newAlt;
 
        for ( UnboundedRegExpElement < SymbolType > & n : cont )
            newAlt.pushBackChild ( std::move ( static_cast < UnboundedRegExpIteration < SymbolType > & > ( n ).getChild ( ) ) );
 
        return Unbounded < SymbolType >::visit ( std::move ( newAlt ), true );
    };
 
    if ( areAllItersInConcat ( node.getChild ( ) ) ) {
        node.setChild ( toAlternationOfChildren ( static_cast < UnboundedRegExpConcatenation < SymbolType > & > ( node.getChild ( ) ) ) );
        return true;
    } else if ( dynamic_cast < UnboundedRegExpAlternation < SymbolType > * > ( & node.getChild ( ) ) ) {
        UnboundedRegExpAlternation < SymbolType > & alt = static_cast < UnboundedRegExpAlternation < SymbolType > & > ( node.getChild ( ) );
        bool res = false;
        for ( size_t i = 0; i < alt.getChildren ( ).size ( ); ++ i ) {
            if ( areAllItersInConcat ( alt.getChild ( i ) ) ) {
                alt.setChild ( toAlternationOfChildren ( static_cast < UnboundedRegExpConcatenation < SymbolType > & > ( alt.getChild ( i ) ) ), i );
                res = true;
            }
        }
        return res;
    }
 
    return false;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::V5( UnboundedRegExpAlternation < SymbolType > & /* node */ ) {
    // implemented by combination of A9 and A10
 
    return false;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::V6( UnboundedRegExpAlternation < SymbolType > & /* node */ ) {
    // implemented by combination of A9 and A10R
 
    return false;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::V8( UnboundedRegExpConcatenation < SymbolType > & node ) {
    bool optimized = false;
 
    // interpretation: if there is iteration in concatenation node, and element of iteration contains eps and is straight before this iteration, then this element can be omitted
 
    if ( node.getChildren ( ).empty ( ) )
        return false;
 
    for( auto it = node.getChildren ( ).begin( ); it != node.getChildren ( ).end( ); ) {
        const UnboundedRegExpIteration < SymbolType > * iter = dynamic_cast < const UnboundedRegExpIteration < SymbolType > * > ( & * it );
 
        if( ! iter ) {
            ++ it;
            continue;
        }
 
        // if element of iteration is concatenation, we need to check this specially
        const UnboundedRegExpConcatenation < SymbolType > * concat = dynamic_cast < const UnboundedRegExpConcatenation < SymbolType > * > ( & iter->getChild ( ) );
 
        if( concat ) {
            // check if not out of bounds
            if( static_cast < size_t > ( distance( node.getChildren ( ).begin( ), it ) ) < concat->getChildren ( ).size ( ) ) {
                it ++;
                continue;
            }
 
            auto it2 = it;
            ext::retract ( it2, concat->getChildren ( ).size ( ) );
 
            if( regexp::properties::RegExpEpsilon::languageContainsEpsilon ( * concat ) &&
                concat->getChildren().size ( ) == static_cast < size_t > ( distance ( it2, node.getChildren ( ).end ( ) ) ) &&
                equal ( concat->getChildren ( ).begin( ), concat->getChildren ( ).end( ), it2 ) ) {
                optimized = true;
 
                it = node.erase ( it2, it );
            } else
                ++ it;
        } else {
            // check if not at the first node
            if ( it == node.getChildren ( ).begin ( ) ) {
                it ++;
                continue;
            }
 
            auto prev = std::prev ( it );
 
            if ( regexp::properties::RegExpEpsilon::languageContainsEpsilon ( iter->getElement ( ) ) && iter->getElement ( ) == * prev ) {
                it = node.erase ( prev );
                optimized = true;
            } else
                ++ it;
        }
    }
 
    return optimized;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::V8R( UnboundedRegExpConcatenation < SymbolType > & node ) {
    bool optimized = false;
 
    // interpretation: if there is iteration in concatenation node, and element of iteration contains eps and is straight before this iteration, then this element can be omitted
 
    if ( node.getChildren ( ).empty ( ) )
        return false;
 
    for( auto it = node.getChildren ( ).rbegin( ); it != node.getChildren ( ).rend( ); ) {
        const UnboundedRegExpIteration < SymbolType > * iter = dynamic_cast < const UnboundedRegExpIteration < SymbolType > * > ( & * it );
 
        if( ! iter ) {
            ++ it;
            continue;
        }
 
        // if element of iteration is concatenation, we need to check this specially
        if ( const UnboundedRegExpConcatenation < SymbolType > * concat = dynamic_cast < const UnboundedRegExpConcatenation < SymbolType > * > ( & iter->getChild ( ) ); concat ) {
            // check if not out of bounds
            if( static_cast < size_t > ( distance( node.getChildren ( ).rbegin( ), it ) ) < concat->getChildren ( ).size ( ) ) {
                it ++;
                continue;
            }
 
            auto it2 = it;
            ext::retract ( it2, concat->getChildren ( ).size ( ) );
 
            if( regexp::properties::RegExpEpsilon::languageContainsEpsilon ( * concat ) &&
                concat->getChildren().size ( ) == static_cast < size_t > ( distance ( it2, node.getChildren ( ).rend ( ) ) ) &&
                equal ( concat->getChildren ( ).rbegin( ), concat->getChildren ( ).rend( ), it2 ) ) {
                optimized = true;
 
                it = node.erase ( it2, it );
            } else
                ++ it;
        } else {
            // check if not at the first node
            if ( it == node.getChildren ( ).rbegin ( ) ) {
                it ++;
                continue;
            }
 
            auto prev = std::prev ( it );
 
            if ( regexp::properties::RegExpEpsilon::languageContainsEpsilon ( iter->getElement ( ) ) && iter->getElement ( ) == * prev ) {
                it = node.erase ( prev );
                optimized = true;
            } else
                ++ it;
        }
    }
 
    return optimized;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::V9( UnboundedRegExpConcatenation < SymbolType > & node ) {
    bool optimized = false;
 
    // interpretation: if concat (C1) with iter && iteration's element is concat (C2), then:
    //    simultaneously iterate through C1 and C2. (axy)*axz=ax(yax)*z -> get ax that is same and relocate them...
 
    for( auto it = node.begin( ) ; it != node.end( ) ; ) {
        UnboundedRegExpIteration < SymbolType > * iter = dynamic_cast < UnboundedRegExpIteration < SymbolType > * > ( & * it );
        if ( ! iter ) {
            ++ it;
            continue;
        }
        UnboundedRegExpConcatenation < SymbolType > * concat = dynamic_cast < UnboundedRegExpConcatenation < SymbolType > * > ( & iter->getChild( ) );
        if( ! concat ) {
            auto cIter = std::next ( it );
            if ( cIter == node.end ( ) || * cIter != iter->getChild ( ) ) {
                ++ it;
                continue;
            }
 
            it = node.insert ( it, std::move ( * std::next ( it ) ) );
            it = std::next ( it );
            it = node.erase ( std::next ( it ) );
            it = std::prev ( it );
        } else {
            // find range from <it+1;sth> and <concat.begin;sth> that is equal
            auto c1Iter = std::next( it );
            auto c2Iter = concat->begin( );
            while( c1Iter != node.end() && c2Iter != concat->end( ) && *c1Iter == * c2Iter ) {
                ++ c1Iter;
                ++ c2Iter;
            }
 
            if( c1Iter == std::next( it ) ) {
                ++ it;
                continue;
            }
 
            // common::Streams::out << "xy" << std::endl;
            // UnboundedRegExpConcatenation < SymbolType >* tmp = new UnboundedRegExpConcatenation < SymbolType >( );
            // tmp->insert( tmp->getChildren().end( ), std::next( it ), c1Iter );
            // common::Streams::out << RegExp( tmp ) << std::endl;
 
            // copy the range <it;sth>, delete it and go back to the iter node
            ext::ptr_vector < UnboundedRegExpElement < SymbolType > > copyRange;
            copyRange.insert ( copyRange.end(), std::make_move_iterator ( std::next( it ) ), std::make_move_iterator ( c1Iter ) );
            it = node.erase ( std::next ( it ), c1Iter );
            it = std::prev( it );
 
            // insert that range before it position
            it = node.insert( it, std::make_move_iterator ( copyRange.begin( ) ), std::make_move_iterator ( copyRange.end( ) ) );
 
            // alter the iteration's concat node
            copyRange.clear( );
            copyRange.insert ( copyRange.end(), std::make_move_iterator ( concat->begin( ) ), std::make_move_iterator ( c2Iter ) );
            concat->erase ( concat->begin( ), c2Iter );
            concat->insert ( concat->end(), std::make_move_iterator ( copyRange.begin( ) ), std::make_move_iterator ( copyRange.end( ) ) );
        }
    }
 
    return optimized;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::V10( UnboundedRegExpIteration < SymbolType > & node ) {
 
    // interpretation: if iter's child is alternation where some of its children are iteration, then they do not have to be iterations
    UnboundedRegExpAlternation < SymbolType > * alt = dynamic_cast < UnboundedRegExpAlternation < SymbolType > * > ( & node.getChild ( ) );
    if ( ! alt || ! any_of ( alt->begin( ), alt->end( ), [] ( const UnboundedRegExpElement < SymbolType > & a ) -> bool { return dynamic_cast < const UnboundedRegExpIteration < SymbolType > * > ( & a ); } ) )
        return false;
 
    for ( auto it = alt->begin( ); it != alt->end ( ); ++ it ) {
        if ( dynamic_cast < UnboundedRegExpIteration < SymbolType > * > ( & * it ) )
            alt->setChild ( std::move ( static_cast < UnboundedRegExpIteration < SymbolType > & > ( * it ).getChild ( ) ), it );
    }
 
    node.setChild ( Unbounded < SymbolType >::visit ( std::move ( * alt ), false ) );
 
    return true;
}
 
template < class SymbolType >
bool RegExpOptimize::Unbounded < SymbolType >::X1( UnboundedRegExpAlternation < SymbolType > & node ) {
 
    // theorem: In regexp like a* + \e, \e is described twice, first in a*, second in \e.
    //  therefore we can delete the \e as it is redundant
 
    auto iter = find_if ( node.begin( ), node.end( ), [] ( const UnboundedRegExpElement < SymbolType > & a ) -> bool { return dynamic_cast < const UnboundedRegExpIteration < SymbolType > * > ( & a );} );
    auto eps = find_if ( node.begin( ), node.end( ), [] ( const UnboundedRegExpElement < SymbolType > & a ) -> bool { return dynamic_cast < const UnboundedRegExpEpsilon < SymbolType > * > ( & a );} );
 
    if( iter != node.end( ) && eps != node.end( ) ) {
        node.erase( eps );
        return true;
    }
 
    return false;
}
 
} /* namespace regexp::simplify */