Skip to content
Snippets Groups Projects
Normal view Permalink
ExactNonlinearTreePatternAutomaton.h 8.72 KiB
Newer Older
Jan Trávníček's avatar
implementation of nonlinear tree pattern automaton construction algorithm
Jan Trávníček committed
1 2 3 4 5 6 7 8 9 10 
/*
 * ExactNonlinearTreePatternAutomaton.h
 *
 *  Created on: 7. 4. 2015
 *      Author: Jan Travnicek
 */

#ifndef _EXACT_NONLINEAR_TREE_PATTERN_AUTOMATON_H__
#define _EXACT_NONLINEAR_TREE_PATTERN_AUTOMATON_H__
Jan Trávníček's avatar
update includes in algo  
Jan Trávníček committed
11 12 13 
#include <alib/pair>
#include <alib/deque>
#include <alib/vector>
Jan Trávníček's avatar
templatize construction of (Nonlinear)TreePatternAutomaton  
Jan Trávníček committed
14
Jan Trávníček's avatar
optimize includes  
Jan Trávníček committed
15 
#include <common/ranked_symbol.hpp>
Jan Trávníček's avatar
implementation of nonlinear tree pattern automaton construction algorithm
Jan Trávníček committed
16
Jan Trávníček's avatar
templatize construction of (Nonlinear)TreePatternAutomaton  
Jan Trávníček committed
17 18 19 20 21 
#include <tree/ranked/PrefixRankedTree.h>
#include <automaton/PDA/InputDrivenNPDA.h>

#include <tree/properties/ExactSubtreeRepeatsNaive.h>
Jan Trávníček's avatar
implementation of nonlinear tree pattern automaton construction algorithm
Jan Trávníček committed
22 23 24 25 
namespace arbology {

namespace exact {
Jan Trávníček's avatar
use cli in aarbology binary  
Jan Trávníček committed
26 
class ExactNonlinearTreePatternAutomaton {
Jan Trávníček's avatar
templatize construction of (Nonlinear)TreePatternAutomaton  
Jan Trávníček committed
27 28 
	template < class SymbolType, class RankType >
	static automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType, RankType >, char, ext::pair < unsigned, unsigned > > constructInternal ( const tree::PrefixRankedTree < SymbolType, RankType > & tree, const common::ranked_symbol < SymbolType, RankType > & subtreeWildcard, const common::ranked_symbol < SymbolType, RankType > & currentNonlinearVariable, const ext::set < common::ranked_symbol < SymbolType, RankType > > & nonlinearVariables );
Jan Trávníček's avatar
implementation of nonlinear tree pattern automaton construction algorithm
Jan Trávníček committed
29
Jan Trávníček's avatar
templatize construction of (Nonlinear)TreePatternAutomaton  
Jan Trávníček committed
30 31 
	template < class SymbolType, class RankType >
	static void constructTail ( automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType, RankType >, char, ext::pair < unsigned, unsigned > > & res, const tree::PrefixRankedTree < SymbolType, RankType > & tree, const common::ranked_symbol < SymbolType, RankType > & subtreeWildcard, const common::ranked_symbol < SymbolType, RankType > & currentNonlinearVariable, const ext::set < common::ranked_symbol < SymbolType, RankType > > & nonlinearVariables, unsigned subtreeId, typename ext::vector < common::ranked_symbol < SymbolType, RankType > >::const_iterator rankedSymbolsIter, int i, typename ext::vector < common::ranked_symbol < unsigned, RankType > >::const_iterator subtreeRepeatsIter );
Jan Trávníček's avatar
implementation of nonlinear tree pattern automaton construction algorithm
Jan Trávníček committed
32 33 34 35 36 37 

public:
	/**
	 * Performs conversion.
	 * @return left regular grammar equivalent to source automaton.
	 */
Jan Trávníček's avatar
templatize construction of (Nonlinear)TreePatternAutomaton  
Jan Trávníček committed
38 39 
	template < class SymbolType, class RankType >
	static automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType, RankType >, char, ext::pair < unsigned, unsigned > > construct ( const tree::PrefixRankedTree < SymbolType, RankType > & tree, const common::ranked_symbol < SymbolType, RankType > & subtreeWildcard, const ext::set < common::ranked_symbol < SymbolType, RankType > > & nonlinearVariables );
Jan Trávníček's avatar
implementation of nonlinear tree pattern automaton construction algorithm
Jan Trávníček committed
40 41 
};
Jan Trávníček's avatar
templatize construction of (Nonlinear)TreePatternAutomaton  
Jan Trávníček committed
42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 
template < class SymbolType, class RankType >
void ExactNonlinearTreePatternAutomaton::constructTail ( automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType, RankType >, char, ext::pair < unsigned, unsigned > > & res, const tree::PrefixRankedTree < SymbolType, RankType > & tree, const common::ranked_symbol < SymbolType, RankType > & subtreeWildcard, const common::ranked_symbol < SymbolType, RankType > & currentNonlinearVariable, const ext::set < common::ranked_symbol < SymbolType, RankType > > & nonlinearVariables, unsigned subtreeId, typename ext::vector < common::ranked_symbol < SymbolType, RankType > >::const_iterator rankedSymbolsIter, int i, typename ext::vector < common::ranked_symbol < unsigned, RankType > >::const_iterator subtreeRepeatsIter ) {
	ext::deque < std::pair < size_t, int > > subtreeJumps;
	ext::deque < unsigned > subtreeRepeatsStack;

	for (++ rankedSymbolsIter, ++ subtreeRepeatsIter, ++i; rankedSymbolsIter != tree.getContent ( ).end ( ); ++ rankedSymbolsIter, ++ subtreeRepeatsIter, ++i ) {
		common::ranked_symbol < SymbolType, RankType > symbol = * rankedSymbolsIter;
		subtreeJumps.push_back ( std::make_pair ( ( size_t ) symbol.getRank ( ), i - 1 ) );
		subtreeRepeatsStack.push_back ( subtreeRepeatsIter->getSymbol ( ) );

		ext::pair < unsigned, unsigned > currentState = ext::make_pair ( i, subtreeId + 1 );
		ext::pair < unsigned, unsigned > previousState = ext::make_pair ( i - 1, subtreeId + 1 );

		res.addState ( currentState );

		res.addTransition ( previousState, std::move ( symbol ), currentState );

		while ( subtreeJumps.size ( ) && subtreeJumps.back ( ).first == 0 ) {
			ext::pair < unsigned, unsigned > jumpSource = ext::make_pair ( subtreeJumps.back ( ).second, subtreeId + 1 );
			res.addTransition ( jumpSource, subtreeWildcard, currentState );

			for ( const common::ranked_symbol < SymbolType, RankType > & nonlinearVariable : nonlinearVariables )
				if ( nonlinearVariable != currentNonlinearVariable || subtreeId == subtreeRepeatsStack.back ( ) )
					res.addTransition ( jumpSource, nonlinearVariable, currentState );

			if ( subtreeJumps.size ( ) ) {
				subtreeJumps.pop_back ( );
				subtreeRepeatsStack.pop_back ( );
			}
		}

		if ( subtreeJumps.size ( ) ) subtreeJumps.back ( ).first--;
	}
}

template < class SymbolType, class RankType >
automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType, RankType >, char, ext::pair < unsigned, unsigned > > ExactNonlinearTreePatternAutomaton::constructInternal ( const tree::PrefixRankedTree < SymbolType, RankType > & tree, const common::ranked_symbol < SymbolType, RankType > & subtreeWildcard, const common::ranked_symbol < SymbolType, RankType > & currentNonlinearVariable, const ext::set < common::ranked_symbol < SymbolType, RankType > > & nonlinearVariables ) {
	char S = alphabet::SubtreeWildcardSymbol::instance < char > ( );
	automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType, RankType >, char, ext::pair < unsigned, unsigned > > res ( ext::make_pair ( 0u, 0u ), S );

	tree::PrefixRankedTree < unsigned, DefaultRankType > repeats = tree::properties::ExactSubtreeRepeatsNaive::repeats ( tree );

	for ( const common::ranked_symbol < > & symbol : tree.getAlphabet ( ) ) {
		res.addInputSymbol ( symbol );
		res.setPushdownStoreOperation ( symbol, ext::vector < char > ( 1, S ), ext::vector < char > ( ( size_t ) symbol.getRank ( ), S ) );
	}

	res.addInputSymbol ( subtreeWildcard );
	res.setPushdownStoreOperation ( subtreeWildcard, ext::vector < char > ( 1, S ), ext::vector < char > { } );

	for ( const common::ranked_symbol < SymbolType, RankType > & nonlinearVariable : nonlinearVariables ) {
		res.addInputSymbol ( nonlinearVariable );
		res.setPushdownStoreOperation ( nonlinearVariable, ext::vector < char > ( 1, S ), ext::vector < char > { } );
	}

	unsigned i = 1;
	ext::deque < std::pair < size_t, int > > subtreeJumps;
	ext::deque < unsigned > subtreeRepeatsStack;

	ext::vector < common::ranked_symbol < > >::const_iterator rankedSymbolsIter;
	ext::vector < common::ranked_symbol < unsigned, DefaultRankType > >::const_iterator subtreeRepeatsIter;
	for ( rankedSymbolsIter = tree.getContent ( ).begin(), subtreeRepeatsIter = repeats.getContent ( ).begin ( ); rankedSymbolsIter != tree.getContent ( ).end ( ); ++ rankedSymbolsIter, ++ subtreeRepeatsIter, ++ i ) {
		common::ranked_symbol < SymbolType, RankType > symbol = * rankedSymbolsIter;
		subtreeJumps.push_back ( std::make_pair ( ( size_t ) symbol.getRank ( ), i - 1 ) );
		subtreeRepeatsStack.push_back ( subtreeRepeatsIter->getSymbol ( ) );

		ext::pair < unsigned, unsigned > currentState = ext::make_pair ( i, 0u );
		ext::pair < unsigned, unsigned > previousState = ext::make_pair ( i - 1, 0u );

		res.addState ( currentState );

		res.addTransition ( previousState, symbol, currentState );
		res.addTransition ( res.getInitialState ( ), std::move ( symbol ), currentState );

		while ( subtreeJumps.size ( ) && subtreeJumps.back ( ).first == 0 ) {
			ext::pair < unsigned, unsigned > jumpSource = ext::make_pair ( subtreeJumps.back ( ).second, 0u );
			res.addTransition ( jumpSource, subtreeWildcard, currentState );

			for ( const common::ranked_symbol < SymbolType, RankType > & nonlinearVariable : nonlinearVariables )
				if ( nonlinearVariable != currentNonlinearVariable )
					res.addTransition ( jumpSource, nonlinearVariable, currentState );
				else {
					unsigned subtreeId = subtreeRepeatsStack.back ( );
					ext::pair < unsigned, unsigned > targetState = ext::make_pair ( i, subtreeId + 1 );

					res.addState ( targetState );
					res.addTransition ( jumpSource, nonlinearVariable, targetState );

					constructTail ( res, tree, subtreeWildcard, currentNonlinearVariable, nonlinearVariables, subtreeId, rankedSymbolsIter, i, subtreeRepeatsIter );
				}

			subtreeJumps.pop_back ( );
			subtreeRepeatsStack.pop_back ( );
		}

		if ( subtreeJumps.size ( ) ) subtreeJumps.back ( ).first--;
	}

	return res;
}

template < class SymbolType, class RankType >
automaton::InputDrivenNPDA < common::ranked_symbol < SymbolType, RankType >, char, ext::pair < unsigned, unsigned > > ExactNonlinearTreePatternAutomaton::construct ( const tree::PrefixRankedTree < SymbolType, RankType > & tree, const common::ranked_symbol < SymbolType, RankType > & subtreeWildcard, const ext::set < common::ranked_symbol < SymbolType, RankType > > & nonlinearVariables ) {
	return constructInternal ( tree, subtreeWildcard, * nonlinearVariables.begin ( ), nonlinearVariables );
}
Jan Trávníček's avatar
implementation of nonlinear tree pattern automaton construction algorithm
Jan Trávníček committed
148 149 150 151 152 
} /* namespace exact */

} /* namespace arbology */

#endif /* _EXACT_NONLINEAR_TREE_PATTERN_AUTOMATON_H__ */