GlushkovSubstitutionMap.h

/*
 * GlushkovSubstitutionMap.h
 *
 *  Created on: 26. 7. 2017
 *	  Author: Tomas Pecka
 */

#ifndef RTE_GLUSHKOV_SUBSTITUTION_MAP_H_
#define RTE_GLUSHKOV_SUBSTITUTION_MAP_H_

#include <alib/map>
#include <alib/set>
#include <alib/vector>
#include <common/ranked_symbol.hpp>

#include <rte/formal/FormalRTE.h>
#include <rte/formal/FormalRTEElements.h>

#include "GlushkovFirst.h"
#include "GlushkovPos.h"

namespace rte {

class GlushkovSubstitutionMap {

private:
	template < class SymbolType, class RankType >
	using TSubstMap = ext::map < common::ranked_symbol < ext::pair < SymbolType, unsigned >, RankType >, ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned >, RankType > > >;

	template < class SymbolType, class RankType >
	using TSubstMapTree = ext::map < const rte::FormalRTEElement < ext::pair < SymbolType, unsigned >, RankType >*, TSubstMap < SymbolType, RankType > >;

	template < class SymbolType, class RankType >
	using TAlphabet = ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned >, RankType > >;

	// --------------------------------------------------------------------

	template < class SymbolType, class RankType >
	static void preprocessSubMap ( TSubstMap < SymbolType, RankType > & subMap, const TAlphabet < SymbolType, RankType > & alphabetK );

public:
	/**
	 * @param re rte to probe
	 * @return subst map for all RTE syntax tree elements
	 */
	template < class SymbolType, class RankType >
	static ext::map < const rte::FormalRTEElement < ext::pair < SymbolType, unsigned >, RankType >*, TSubstMap < SymbolType, RankType > > substMap ( const rte::FormalRTE < ext::pair < SymbolType, unsigned >, RankType > & re );

	template < class SymbolType, class RankType >
	class Formal {
	public:
		static void visit ( const rte::FormalRTEElement < ext::pair < SymbolType, unsigned >, RankType > & node, const TAlphabet < SymbolType, RankType > & alphabetK, TSubstMap < SymbolType, RankType > & subM, TSubstMapTree < SymbolType, RankType > & subMapTree );
		static void visit ( const rte::FormalRTEAlternation < ext::pair < SymbolType, unsigned >, RankType > & node, const TAlphabet < SymbolType, RankType > & alphabetK, TSubstMap < SymbolType, RankType > & subM, TSubstMapTree < SymbolType, RankType > & subMapTree );
		static void visit ( const rte::FormalRTESubstitution < ext::pair < SymbolType, unsigned >, RankType > & node, const TAlphabet < SymbolType, RankType > & alphabetK, TSubstMap < SymbolType, RankType > & subM, TSubstMapTree < SymbolType, RankType > & subMapTree );
		static void visit ( const rte::FormalRTEIteration < ext::pair < SymbolType, unsigned >, RankType > & node, const TAlphabet < SymbolType, RankType > & alphabetK, TSubstMap < SymbolType, RankType > & subM, TSubstMapTree < SymbolType, RankType > & subMapTree );
		static void visit ( const rte::FormalRTESymbolAlphabet < ext::pair < SymbolType, unsigned >, RankType > & node, const TAlphabet < SymbolType, RankType > & alphabetK, TSubstMap < SymbolType, RankType > & subM, TSubstMapTree < SymbolType, RankType > & subMapTree );
		static void visit ( const rte::FormalRTESymbolSubst < ext::pair < SymbolType, unsigned >, RankType > & node, const TAlphabet < SymbolType, RankType > & alphabetK, TSubstMap < SymbolType, RankType > & subM, TSubstMapTree < SymbolType, RankType > & subMapTree );
		static void visit ( const rte::FormalRTEEmpty < ext::pair < SymbolType, unsigned >, RankType > & node, const TAlphabet < SymbolType, RankType > & alphabetK, TSubstMap < SymbolType, RankType > & subM, TSubstMapTree < SymbolType, RankType > & subMapTree );
	};

};

// -----------------------------------------------------------------------------

/**
 * Preprocessing:
 *  - Let k1, k2 be elements of alphabet K.
 *  - If k1 is an element of substMap[k2], then copy content of substMap[k1] into substMap[k2]
 */
template < class SymbolType, class RankType >
void GlushkovSubstitutionMap::preprocessSubMap ( TSubstMap < SymbolType, RankType > & subMap, const TAlphabet < SymbolType, RankType > & alphabetK ) {
	for ( bool change = true; change; change = false )
		for ( std::pair < const common::ranked_symbol < ext::pair < SymbolType, unsigned >, RankType >, TAlphabet < SymbolType, RankType > > & kv : subMap ) {
			TAlphabet < SymbolType, RankType > & substSet = kv.second;

			for ( auto eIter = substSet.begin ( ); eIter != substSet.end ( ); ) {
				if ( alphabetK.count ( * eIter ) == 0 ) {
					++eIter;
				} else {
					auto it = subMap.find ( * eIter );
					size_t oldSize = substSet.size ( );
					substSet.insert ( it->second.begin ( ), it->second.end ( ) );
					change = ( oldSize != substSet.size ( ) ); // something was added
					eIter = substSet.erase ( eIter );
				}
			}
		}
}

// -----------------------------------------------------------------------------

template < class SymbolType, class RankType >
ext::map < const rte::FormalRTEElement < ext::pair < SymbolType, unsigned >, RankType >*, GlushkovSubstitutionMap::TSubstMap < SymbolType, RankType > > GlushkovSubstitutionMap::substMap ( const rte::FormalRTE < ext::pair < SymbolType, unsigned >, RankType > & rte ) {
	TSubstMap < SymbolType, RankType > subMap;
	ext::map < const rte::FormalRTEElement < ext::pair < SymbolType, unsigned >, RankType >*, TSubstMap  < SymbolType, RankType > > subMapTree;

	/* Init substitution map, ie \forall a \in K: sub[a] = \emptyset */
	for ( const common::ranked_symbol < ext::pair < SymbolType, unsigned >, RankType > & ssymb : rte.getSubstitutionAlphabet ( ) )
		subMap.insert ( std::make_pair ( ssymb, TAlphabet < SymbolType, RankType > { } ) );

	/* recursively compute substMap */
	rte.getRTE ( ).getStructure ( ).template accept < void, GlushkovSubstitutionMap::Formal < SymbolType, RankType > > ( rte.getSubstitutionAlphabet ( ), subMap, subMapTree );
	return subMapTree;
}

// -----------------------------------------------------------------------------

template < class SymbolType, class RankType >
void GlushkovSubstitutionMap::Formal < SymbolType, RankType >::visit ( const rte::FormalRTEAlternation < ext::pair < SymbolType, unsigned >, RankType > & node, const TAlphabet < SymbolType, RankType > & alphabetK, TSubstMap < SymbolType, RankType > & subMap, TSubstMapTree < SymbolType, RankType > & subMapTree ) {
	preprocessSubMap ( subMapTree.insert ( std::make_pair ( & node, subMap ) ).first->second, alphabetK );

	node.getLeftElement ( ).template accept < void, GlushkovSubstitutionMap::Formal < SymbolType, RankType > > ( alphabetK, subMap, subMapTree );
	node.getRightElement ( ).template accept < void, GlushkovSubstitutionMap::Formal < SymbolType, RankType > > ( alphabetK, subMap, subMapTree );
}

template < class SymbolType, class RankType >
void GlushkovSubstitutionMap::Formal < SymbolType, RankType >::visit ( const rte::FormalRTESubstitution < ext::pair < SymbolType, unsigned >, RankType > & node, const TAlphabet < SymbolType, RankType > & alphabetK, TSubstMap < SymbolType, RankType > & subMap, TSubstMapTree < SymbolType, RankType > & subMapTree ) {
	preprocessSubMap ( subMapTree.insert ( std::make_pair ( & node, subMap ) ).first->second, alphabetK );

	// prepare left map
	auto itMap = subMap.find ( node.getSubstitutionSymbol ( ).getSymbol ( ) );
	ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned >, RankType > > backup = std::move ( itMap->second );
	itMap->second.clear();

	for ( const auto & s : node.getRightElement ( ).template accept < ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned >, RankType > >, GlushkovFirst::Formal < ext::pair < SymbolType, unsigned >, RankType > > ( ) )
		itMap->second.insert ( s );

	node.getLeftElement ( ).template accept < void, GlushkovSubstitutionMap::Formal < SymbolType, RankType > > ( alphabetK, subMap, subMapTree );

	// restore original map
	itMap->second = std::move ( backup );
	node.getRightElement ( ).template accept < void, GlushkovSubstitutionMap::Formal < SymbolType, RankType > > ( alphabetK, subMap, subMapTree );
}

template < class SymbolType, class RankType >
void GlushkovSubstitutionMap::Formal < SymbolType, RankType >::visit ( const rte::FormalRTEIteration < ext::pair < SymbolType, unsigned >, RankType > & node, const TAlphabet < SymbolType, RankType > & alphabetK, TSubstMap < SymbolType, RankType > & subMap, TSubstMapTree < SymbolType, RankType > & subMapTree ) {
	preprocessSubMap ( subMapTree.insert ( std::make_pair ( & node, subMap ) ).first->second, alphabetK );

	for ( const auto & s : node.getElement ( ).template accept < TAlphabet < SymbolType, RankType >, GlushkovFirst::Formal < ext::pair < SymbolType, unsigned >, RankType > > ( ) )
		subMap[node.getSubstitutionSymbol ( ).getSymbol ( )].insert ( s );

	node.getElement ( ).template accept < void, GlushkovSubstitutionMap::Formal < SymbolType, RankType > > ( alphabetK, subMap, subMapTree );
}

template < class SymbolType, class RankType >
void GlushkovSubstitutionMap::Formal < SymbolType, RankType >::visit ( const rte::FormalRTESymbolAlphabet < ext::pair < SymbolType, unsigned >, RankType > & node, const TAlphabet < SymbolType, RankType > & alphabetK, TSubstMap < SymbolType, RankType > & subMap, TSubstMapTree < SymbolType, RankType > & subMapTree ) {
	preprocessSubMap ( subMapTree.insert ( std::make_pair ( & node, subMap ) ).first->second, alphabetK );

	for ( const auto & c : node.getElements ( ) ) {
		c . template accept < void, GlushkovSubstitutionMap::Formal < SymbolType, RankType > > ( alphabetK, subMap, subMapTree );
	}
}

template < class SymbolType, class RankType >
void GlushkovSubstitutionMap::Formal < SymbolType, RankType >::visit ( const rte::FormalRTESymbolSubst < ext::pair < SymbolType, unsigned >, RankType > & node, const TAlphabet < SymbolType, RankType > & alphabetK, TSubstMap < SymbolType, RankType > & subMap, TSubstMapTree < SymbolType, RankType > & subMapTree ) {
	preprocessSubMap ( subMapTree.insert ( std::make_pair ( & node, subMap ) ).first->second, alphabetK );
}

template < class SymbolType, class RankType >
void GlushkovSubstitutionMap::Formal < SymbolType, RankType >::visit ( const rte::FormalRTEEmpty < ext::pair < SymbolType, unsigned >, RankType > & node, const TAlphabet < SymbolType, RankType > & alphabetK, TSubstMap < SymbolType, RankType > & subMap, TSubstMapTree < SymbolType, RankType > & subMapTree ) {
	preprocessSubMap ( subMapTree.insert ( std::make_pair ( & node, subMap ) ).first->second, alphabetK );
}

} /* namespace rte */

#endif /* RTE_GLUSHKOV_SUBSTITUTION_MAP_H_ */