TreeAuxiliary.h

Go to the documentation of this file.

 
#pragma once
 
#include <stack>
 
#include <ext/algorithm>
 
#include <alib/set>
#include <alib/tree>
#include <alib/list>
#include <common/ranked_symbol.hpp>
 
namespace tree {
 
class TreeAuxiliary {
    template < class SymbolType >
    static void postfixToPrefixInt ( const ext::vector < common::ranked_symbol < SymbolType > > & src, ext::vector < common::ranked_symbol < SymbolType > > & dest, unsigned & readIndex );
 
    template < class SymbolType >
    static ext::tree < common::ranked_symbol < SymbolType > > prefixToTreeInt ( const ext::vector < common::ranked_symbol < SymbolType > > & from, unsigned & index );
 
    template < class SymbolType >
    static void sortInt ( ext::tree < SymbolType > & tree );
public:
    template < class SymbolType >
    static ext::tree < SymbolType > sort ( ext::tree < SymbolType > tree );
    template < class SymbolType >
    static ext::set < SymbolType > unrankSymbols ( const ext::set < common::ranked_symbol < SymbolType > > & alphabet );
    template < class SymbolType >
    static ext::set < common::ranked_symbol < SymbolType > > computeBars ( const ext::set < common::ranked_symbol < SymbolType > > & alphabet, const SymbolType & barBase );
 
    template < class SymbolType >
    static ext::tree < common::ranked_symbol < SymbolType > > unrankedToRanked ( const ext::tree < SymbolType > & tree );
    template < class SymbolType >
    static ext::tree < SymbolType > rankedToUnranked ( const ext::tree < common::ranked_symbol < SymbolType > > & tree );
 
    template < class SymbolType >
    static ext::tree < common::ranked_symbol < SymbolType > > postfixToTree (const ext::vector < common::ranked_symbol < SymbolType > > & from);
    template < class SymbolType >
    static ext::tree < common::ranked_symbol < SymbolType > > prefixToTree (const ext::vector < common::ranked_symbol < SymbolType > > & from);
 
    template < class SymbolType >
    static ext::vector < common::ranked_symbol < SymbolType > > postfixToPrefix ( const ext::vector < common::ranked_symbol < SymbolType > > & src );
 
    template < class SymbolType >
    static ext::vector < common::ranked_symbol < SymbolType > > treeToPrefix ( const ext::tree < common::ranked_symbol < SymbolType > > & tree );
    template < class SymbolType >
    static ext::vector < SymbolType > treeToPrefix ( const ext::tree < SymbolType > & tree, const SymbolType & bar );
    template < class SymbolType >
    static ext::vector < common::ranked_symbol < SymbolType > > treeToPrefix ( const ext::tree < common::ranked_symbol < SymbolType > > & tree, const SymbolType & barBase );
    template < class SymbolType >
    static ext::vector < common::ranked_symbol < SymbolType > > treeToPrefix ( const ext::tree < common::ranked_symbol < SymbolType > > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const SymbolType & barBase, const common::ranked_symbol < SymbolType > & variablesBar );
    template < class SymbolType >
    static ext::vector < common::ranked_symbol < SymbolType > > treeToPrefix ( const ext::tree < common::ranked_symbol < SymbolType > > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const ext::set < common::ranked_symbol < SymbolType > > & nonlinearVariables, const SymbolType & barBase, const common::ranked_symbol < SymbolType > & variablesBar );
 
    template < class SymbolType >
    static ext::vector < common::ranked_symbol < SymbolType > > treeToPostfix ( const ext::tree < common::ranked_symbol < SymbolType > > & tree );
};
 
template < class SymbolType >
void TreeAuxiliary::sortInt ( ext::tree < SymbolType > & tree ) {
    for ( ext::tree < SymbolType > & child : tree.getChildren ( ) ) {
        sortInt ( child );
    }
    std::sort ( tree.getChildren ( ).begin ( ), tree.getChildren ( ).end ( ) );
}
 
template < class SymbolType >
ext::tree < SymbolType > TreeAuxiliary::sort ( ext::tree < SymbolType > tree ) {
    sortInt ( tree );
    return tree;
}
 
template < class SymbolType >
ext::set < SymbolType > TreeAuxiliary::unrankSymbols ( const ext::set < common::ranked_symbol < SymbolType > > & alphabet ) {
    return ext::transform < SymbolType > ( alphabet, [&] ( const common::ranked_symbol < SymbolType > & symbol ) {
            return symbol.getSymbol ( );
    } );
}
 
template < class SymbolType >
ext::set < common::ranked_symbol < SymbolType > > TreeAuxiliary::computeBars ( const ext::set < common::ranked_symbol < SymbolType > > & alphabet, const SymbolType & barBase ) {
    return ext::transform < common::ranked_symbol < SymbolType > > ( alphabet, [&] ( const common::ranked_symbol < SymbolType > & symbol ) {
            return common::ranked_symbol < SymbolType > ( barBase, symbol.getRank ( ) );
    } );
}
 
template < class SymbolType >
ext::tree < common::ranked_symbol < SymbolType > > TreeAuxiliary::unrankedToRanked ( const ext::tree < SymbolType > & tree ) {
    ext::vector < ext::tree < common::ranked_symbol < SymbolType > > > children;
 
    for ( const ext::tree < SymbolType > & child : tree ) {
        children.push_back ( unrankedToRanked < SymbolType > ( child ) );
    }
 
    unsigned size = children.size ( );
    return ext::tree < common::ranked_symbol < SymbolType > > ( common::ranked_symbol < SymbolType > ( tree.getData ( ), size ), std::move ( children ) );
}
 
template < class SymbolType >
ext::tree < common::ranked_symbol < SymbolType > > TreeAuxiliary::postfixToTree ( const ext::vector < common::ranked_symbol < SymbolType > > & from ) {
    std::stack < ext::tree < common::ranked_symbol < SymbolType > > > tree_stack;
 
    for ( const common::ranked_symbol < SymbolType > & x : from ) {
        if ( x.getRank ( ) == 0 ) {
            tree_stack.push ( ext::tree < common::ranked_symbol < SymbolType > > ( x, ext::vector < ext::tree < common::ranked_symbol < SymbolType > > > ( ) ) );
        } else {
            ext::vector < ext::tree < common::ranked_symbol < SymbolType > > > children;
 
            for ( unsigned i = 0; i < x.getRank ( ); ++i ) {
                children.push_back ( tree_stack.top ( ) );
                tree_stack.pop ( );
            }
 
            std::reverse ( children.begin ( ), children.end ( ) );
 
            tree_stack.push ( ext::tree < common::ranked_symbol < SymbolType > > ( x, std::move ( children ) ) );
        }
    }
 
    return tree_stack.top ( );
}
 
template < class SymbolType >
ext::tree < common::ranked_symbol < SymbolType > > TreeAuxiliary::prefixToTreeInt ( const ext::vector < common::ranked_symbol < SymbolType > > & from, unsigned & index ) {
    const common::ranked_symbol < SymbolType > & x = from [ index ++ ];
 
    ext::vector < ext::tree < common::ranked_symbol < SymbolType > > > children;
 
    for ( unsigned i = 0; i < x.getRank ( ); ++i ) {
        children.push_back ( prefixToTreeInt ( from, index ) );
    }
 
    return ext::tree < common::ranked_symbol < SymbolType > > ( x, std::move ( children ) );
}
 
template < class SymbolType >
ext::tree < common::ranked_symbol < SymbolType > > TreeAuxiliary::prefixToTree ( const ext::vector < common::ranked_symbol < SymbolType > > & from ) {
    unsigned index = 0;
    return prefixToTreeInt ( from, index );
}
 
template < class SymbolType >
ext::tree < SymbolType > TreeAuxiliary::rankedToUnranked ( const ext::tree < common::ranked_symbol < SymbolType > > & tree ) {
    ext::vector < ext::tree < SymbolType > > children;
 
    for ( const ext::tree < common::ranked_symbol < SymbolType > > & child : tree ) {
        children.push_back ( rankedToUnranked < SymbolType > ( child ) );
    }
 
    return ext::tree < SymbolType > ( tree.getData ( ).getSymbol ( ), std::move ( children ) );
}
 
template < class SymbolType >
ext::vector < common::ranked_symbol < SymbolType > > TreeAuxiliary::postfixToPrefix ( const ext::vector < common::ranked_symbol < SymbolType > > & src ) {
    unsigned readIndex = src.size ( ) - 1;
 
    ext::vector < common::ranked_symbol < SymbolType > > dest;
    postfixToPrefixInt ( src, dest, readIndex );
 
    std::reverse ( dest.begin ( ), dest.end ( ) );
 
    return dest;
}
 
template < class SymbolType >
void TreeAuxiliary::postfixToPrefixInt ( const ext::vector < common::ranked_symbol < SymbolType > > & src, ext::vector < common::ranked_symbol < SymbolType > > & dest, unsigned & readIndex ) {
    unsigned root = readIndex --;
    unsigned rank = src [ root ].getRank ( );
 
    for ( unsigned i = 0; i < rank; ++ i )
        postfixToPrefixInt ( src, dest, readIndex );
 
    dest.push_back ( src [ root ] );
}
 
template < class SymbolType >
ext::vector < common::ranked_symbol < SymbolType > > TreeAuxiliary::treeToPrefix ( const ext::tree < common::ranked_symbol < SymbolType > > & tree ) {
    ext::vector < common::ranked_symbol < SymbolType > > res;
 
    for ( typename ext::tree < common::ranked_symbol < SymbolType > >::const_prefix_iterator iter = tree.prefix_begin ( ); iter != tree.prefix_end ( ); ++iter )
        res.push_back ( * iter );
 
    return res;
}
 
template < class SymbolType >
ext::vector < SymbolType > TreeAuxiliary::treeToPrefix ( const ext::tree < SymbolType > & tree, const SymbolType & bar ) {
    ext::vector < SymbolType > res;
 
    for ( typename ext::tree < SymbolType >::const_structure_iterator iter = tree.structure_begin ( ); iter != tree.structure_end ( ); ++iter )
        if ( iter.getVirtual ( ) )
            res.push_back ( bar );
        else
            res.push_back ( * iter );
 
    return res;
}
 
template < class SymbolType >
ext::vector < common::ranked_symbol < SymbolType > > TreeAuxiliary::treeToPrefix ( const ext::tree < common::ranked_symbol < SymbolType > > & tree, const SymbolType & barBase ) {
    ext::vector < common::ranked_symbol < SymbolType > > res;
 
    for ( typename ext::tree < common::ranked_symbol < SymbolType > >::const_structure_iterator iter = tree.structure_begin ( ); iter != tree.structure_end ( ); ++iter )
        if ( iter.getVirtual ( ) )
            res.push_back ( common::ranked_symbol < SymbolType > ( barBase, iter->getRank ( ) ) );
        else
            res.push_back ( * iter );
 
    return res;
}
 
template < class SymbolType >
ext::vector < common::ranked_symbol < SymbolType > > TreeAuxiliary::treeToPrefix ( const ext::tree < common::ranked_symbol < SymbolType > > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const SymbolType & barBase, const common::ranked_symbol < SymbolType > & variablesBar ) {
    ext::vector < common::ranked_symbol < SymbolType > > res;
 
    for ( typename ext::tree < common::ranked_symbol < SymbolType > >::const_structure_iterator iter = tree.structure_begin ( ); iter != tree.structure_end ( ); ++iter )
        if ( iter.getVirtual ( ) )
            if ( ( * iter == subtreeWildcard ) )
                res.push_back ( variablesBar );
            else
                res.push_back ( common::ranked_symbol < SymbolType > ( barBase, iter->getRank ( ) ) );
        else
            res.push_back ( * iter );
 
    return res;
}
 
template < class SymbolType >
ext::vector < common::ranked_symbol < SymbolType > > TreeAuxiliary::treeToPrefix ( const ext::tree < common::ranked_symbol < SymbolType > > & tree, const common::ranked_symbol < SymbolType > & subtreeWildcard, const ext::set < common::ranked_symbol < SymbolType > > & nonlinearVariables, const SymbolType & barBase, const common::ranked_symbol < SymbolType > & variablesBar ) {
    ext::vector < common::ranked_symbol < SymbolType > > res;
 
    for ( typename ext::tree < common::ranked_symbol < SymbolType > >::const_structure_iterator iter = tree.structure_begin ( ); iter != tree.structure_end ( ); ++iter )
        if ( iter.getVirtual ( ) )
            if ( ( * iter == subtreeWildcard ) || nonlinearVariables.count ( * iter ) )
                res.push_back ( variablesBar );
            else
                res.push_back ( common::ranked_symbol < SymbolType > ( barBase, iter->getRank ( ) ) );
        else
            res.push_back ( * iter );
 
    return res;
}
 
template < class SymbolType >
ext::vector < common::ranked_symbol < SymbolType > > TreeAuxiliary::treeToPostfix ( const ext::tree < common::ranked_symbol < SymbolType > > & tree ) {
    ext::vector < common::ranked_symbol < SymbolType > > res;
 
    for ( typename ext::tree < common::ranked_symbol < SymbolType > >::const_postfix_iterator iter = tree.postfix_begin ( ); iter != tree.postfix_end ( ); ++iter )
        res.push_back ( * iter );
 
    return res;
}
 
} /* namespace tree */