RandomTreeFactory.cpp

#include "RandomTreeFactory.h"

#include <alib/vector>
#include <alib/map>
#include <alib/set>
#include <alib/algorithm>
#include <cstdlib>
#include <ctime>
#include <cmath>

#include <common/ranked_symbol.hpp>

#include <alib/iostream>
#include <alib/random>

#include <alphabet/WildcardSymbol.h>
#include <alphabet/NonlinearVariableSymbol.h>
#include <exception/CommonException.h>

#include <registration/AlgoRegistration.hpp>

#include <global/GlobalData.h>

namespace tree {

namespace generate {

struct Node {
	char symbol;
	int depth;
	Node * right;
	Node * child = nullptr;
	size_t rank = 0;

	Node ( ) : depth ( 0 ) { }
	Node ( Node * parent ) : depth ( parent->depth + 1 ) {
		if ( parent->child == nullptr ) {
			parent->child = this;
			right = this;
		} else {
			right = parent->child->right;
			parent->child->right = this;
		}

		parent->rank++;
	}

	~Node ( ) {
		if ( child == nullptr ) return;

		Node * ch = child;

		do {
			Node * tmp = ch->right;
			delete ch;
			ch = tmp;
		} while ( ch != child );
	}

	void rotateLeftBranch ( ) {
		if ( child != nullptr ) child->rotateLeftBranch ( );

		if ( rank > 1 ) {
			int angle = ext::random_devices::semirandom ( ) % rank;
			Node * newChild = child;

			for ( int i = 0; i < angle; i++ )
				newChild = newChild->right;

			child = newChild;
		}
	}

	void generateUnrankedSymbols ( const ext::vector < char > & alphabet ) {
		symbol = alphabet[ext::random_devices::semirandom ( ) % alphabet.size ( )];
		Node * nextChild = child;

		for ( size_t i = 0; i < rank; i++ ) {
			nextChild->generateUnrankedSymbols ( alphabet );
			nextChild = nextChild->right;
		}
	}

	void generateRankedSymbols ( const ext::map < int, ext::vector < char > > & rankedAlphabet ) {
		const ext::vector < char > & alphabet = rankedAlphabet.at ( rank );

		symbol = alphabet[ext::random_devices::semirandom ( ) % alphabet.size ( )];
		Node * nextChild = child;

		for ( size_t i = 0; i < rank; i++ ) {
			nextChild->generateRankedSymbols ( rankedAlphabet );
			nextChild = nextChild->right;
		}
	}

	void fillRanks ( ext::map < int, ext::vector < char > > & rankedAlphabet ) {
		rankedAlphabet[rank];
		Node * nextChild = child;

		for ( size_t i = 0; i < rank; i++ ) {
			nextChild->fillRanks ( rankedAlphabet );
			nextChild = nextChild->right;
		}
	}

	ext::tree < DefaultSymbolType > createUnrankedNode ( ) {
		ext::vector < ext::tree < DefaultSymbolType > > children;
		Node * nextChild = child;

		for ( size_t i = 0; i < rank; i++ ) {
			children.emplace_back ( ext::tree < DefaultSymbolType > ( nextChild->createUnrankedNode ( ) ) );
			nextChild = nextChild->right;
		}

		return ext::tree < DefaultSymbolType > ( DefaultSymbolType ( symbol ), std::move ( children ) );
	}

	ext::tree < DefaultSymbolType > createUnrankedPatternNode ( ) {
		if ( rank == 0 ) {
			return ext::tree < DefaultSymbolType > ( alphabet::WildcardSymbol::instance < DefaultSymbolType > ( ), { } );
		} else {
			ext::vector < ext::tree < DefaultSymbolType > > children;
			Node * nextChild = child;

			for ( size_t i = 0; i < rank; i++ ) {
				children.emplace_back ( ext::tree < DefaultSymbolType > ( nextChild->createUnrankedPatternNode ( ) ) );
				nextChild = nextChild->right;
			}

			return ext::tree < DefaultSymbolType > ( DefaultSymbolType ( symbol ), std::move ( children ) );
		}
	}

	ext::tree < common::ranked_symbol < > > createRankedNode ( ) {
		ext::vector < ext::tree < common::ranked_symbol < > > > children;
		Node * nextChild = child;

		for ( size_t i = 0; i < rank; i++ ) {
			children.emplace_back ( ext::tree < common::ranked_symbol < > > ( nextChild->createRankedNode ( ) ) );
			nextChild = nextChild->right;
		}

		return ext::tree < common::ranked_symbol < > > ( common::ranked_symbol < > ( DefaultSymbolType ( symbol ), rank ), std::move ( children ) );
	}

	ext::tree < common::ranked_symbol < > > createRankedPatternNode ( ) {
		if ( rank == 0 ) {
			return ext::tree < common::ranked_symbol < > > ( common::ranked_symbol < > ( alphabet::WildcardSymbol::instance < DefaultSymbolType > ( ), 0 ), { } );
		} else {
			ext::vector < ext::tree < common::ranked_symbol < > > > children;
			Node * nextChild = child;

			for ( size_t i = 0; i < rank; i++ ) {
				children.emplace_back ( ext::tree < common::ranked_symbol < > > ( nextChild->createRankedPatternNode ( ) ) );
				nextChild = nextChild->right;
			}

			return ext::tree < common::ranked_symbol < > > ( common::ranked_symbol < > ( DefaultSymbolType ( symbol ), rank ), std::move ( children ) );
		}
	}

	ext::tree < common::ranked_symbol < > > createRankedNonlinearPatternNode ( bool singleNonlinearVariable ) {
		if ( rank == 0 ) {
			if ( singleNonlinearVariable )
				return ext::tree < common::ranked_symbol < > > ( common::ranked_symbol < > ( DefaultSymbolType ( alphabet::NonlinearVariableSymbol < > ( DefaultSymbolType ( "A" ) ) ), 0 ), { } );
			else
				return ext::tree < common::ranked_symbol < > > ( common::ranked_symbol < > ( DefaultSymbolType ( alphabet::NonlinearVariableSymbol < > ( DefaultSymbolType ( symbol ) ) ), 0 ), { } );
		} else {
			ext::vector < ext::tree < common::ranked_symbol < > > > children;
			Node * nextChild = child;

			for ( size_t i = 0; i < rank; i++ ) {
				children.emplace_back ( ext::tree < common::ranked_symbol < > > ( nextChild->createRankedNonlinearPatternNode ( singleNonlinearVariable ) ) );
				nextChild = nextChild->right;
			}

			return ext::tree < common::ranked_symbol < > > ( common::ranked_symbol < > ( DefaultSymbolType ( symbol ), rank ), std::move ( children ) );
		}
	}

	void nicePrint ( std::ostream & os = common::Streams::out, const std::string & prefix = "", const bool last = true ) const {
		os << prefix;

		std::string nextPrefix ( prefix );

		if ( last ) {
			os << "\\-";
			nextPrefix += "  ";
		} else {
			os << "|-";
			nextPrefix += "| ";
		}

		os << symbol << " (" << rank << ")" << std::endl;

		Node * nextChild = child;

		for ( size_t i = 0; i < rank; i++ ) {
			 // os << nextPrefix << "|" << std::endl;
			nextChild->nicePrint ( os, nextPrefix, i == rank - 1 );
			nextChild = nextChild->right;
		}
	}

};

ext::vector < char > generateUnrankedAlphabet ( size_t maxAlphabetSize, bool randomizedAlphabet ) {
	ext::vector < char > symbols ( 26 );

	for ( unsigned i = 0; i < 26; i++ ) symbols[i] = i + 'a';

	if ( randomizedAlphabet ) shuffle ( symbols.begin ( ), symbols.end ( ), ext::random_devices::semirandom );

	return ext::vector < char > ( symbols.begin ( ), symbols.begin ( ) + maxAlphabetSize );
}

void generateRankedAlphabet ( ext::map < int, ext::vector < char > > & rankedAlphabet, size_t maxAlphabetSize, bool randomizedAlphabet ) {
	size_t ranksCount = rankedAlphabet.size ( );
	ext::vector < char > unrankedAlphabet = generateUnrankedAlphabet ( maxAlphabetSize > ranksCount ? maxAlphabetSize : ranksCount, randomizedAlphabet );

	ext::set < size_t > rankSeparators;

	rankSeparators.insert ( 0 );
	rankSeparators.insert ( unrankedAlphabet.size ( ) );

	while ( rankSeparators.size ( ) != ranksCount + 1 /*&& rankSeparators.size() != maxRank + 2*/ ) rankSeparators.insert ( ext::random_devices::semirandom ( ) % unrankedAlphabet.size ( ) );

	ext::set < size_t >::iterator it = rankSeparators.begin ( );

	for ( ext::map < int, ext::vector < char > >::iterator i = rankedAlphabet.begin ( ); i != rankedAlphabet.end ( ); ++i ) {
		ext::set < size_t >::iterator prevIt = it++;
		i->second.insert ( i->second.begin ( ), unrankedAlphabet.begin ( ) + * prevIt, unrankedAlphabet.begin ( ) + * it );
	}
}

Node * generateTreeStructure ( int depth, int nodesCount, size_t maxRank = std::numeric_limits < size_t >::max ( ) ) {
	if ( depth >= nodesCount ) throw exception::CommonException ( "number of nodes is too small" );

	if ( ( maxRank != std::numeric_limits < size_t >::max ( ) ) && ( pow ( maxRank, depth + 1 ) - 1 < nodesCount ) ) throw exception::CommonException ( "number of nodes is too small" );

	ext::vector < Node * > nodes ( nodesCount );

	 // generate path depth long
	Node * root = nodes[0] = new Node ( );

	for ( int i = 1; i <= depth; i++ ) nodes[i] = new Node ( nodes[i - 1] );

	 // move final leaf to end
	nodes[nodesCount - 1] = nodes[depth];

	int availableNodesIndex = depth;
	int finalNodesIndex = nodesCount - 2;

	while ( finalNodesIndex >= availableNodesIndex ) {
		int randomIndex = ext::random_devices::semirandom ( ) % availableNodesIndex;
		Node * parent = nodes[randomIndex];
		Node * node = new Node ( parent );

		 // put node to end if it reached depth limit
		if ( node->depth < depth ) {
			nodes[availableNodesIndex] = node;
			availableNodesIndex++;
		} else {
			nodes[finalNodesIndex] = node;
			finalNodesIndex--;
		}

		 // put parent node to end if it reached rank limit
		if ( parent->rank >= maxRank ) {
			nodes[randomIndex] = nodes[availableNodesIndex - 1];
			nodes[finalNodesIndex] = parent;
			availableNodesIndex--;
			finalNodesIndex--;
		}
	}

	 // move generated path to random branch
	root->rotateLeftBranch ( );

	return root;
}

UnrankedTree < > RandomUnrankedTreeFactory::generateUnrankedTree ( int depth, int nodesCount, size_t maxAlphabetSize, bool randomizedAlphabet, size_t maxRank ) {
	Node * root = generateTreeStructure ( depth, nodesCount, maxRank );
	ext::vector < char > alphabet = generateUnrankedAlphabet ( maxAlphabetSize, randomizedAlphabet );

	root->generateUnrankedSymbols ( alphabet );

	ext::set < DefaultSymbolType > treeAlphabet;

	for ( char it : alphabet )
		treeAlphabet.insert ( DefaultSymbolType ( it ) );

	UnrankedTree < > tree ( treeAlphabet, root->createUnrankedNode ( ) );
	delete root;
	return tree;
}

auto GenerateUnrankedTree = registration::AbstractRegister < RandomUnrankedTreeFactory, tree::UnrankedTree < >, int, int, size_t, bool, size_t > ( RandomUnrankedTreeFactory::generateUnrankedTree, abstraction::AlgorithmCategories::AlgorithmCategory::DEFAULT, "depth", "nodesCount", "maxAlphabetSize", "randomizedAlphabet", "maxRank" );

UnrankedPattern < > RandomUnrankedPatternFactory::generateUnrankedPattern ( int depth, int nodesCount, size_t maxAlphabetSize, bool randomizedAlphabet, size_t maxRank ) {
	Node * root = generateTreeStructure ( depth, nodesCount, maxRank );
	ext::vector < char > alphabet = generateUnrankedAlphabet ( maxAlphabetSize, randomizedAlphabet );

	root->generateUnrankedSymbols ( alphabet );

	ext::set < DefaultSymbolType > treeAlphabet;

	for ( ext::vector < char >::const_iterator it = alphabet.begin ( ); it != alphabet.end ( ); ++it )
		treeAlphabet.insert ( DefaultSymbolType ( * it ) );

	DefaultSymbolType subtreeWildcard = alphabet::WildcardSymbol::instance < DefaultSymbolType > ( );
	treeAlphabet.insert ( subtreeWildcard );
	UnrankedPattern < > tree ( std::move ( subtreeWildcard ), treeAlphabet, root->createUnrankedPatternNode ( ) );
	delete root;
	return tree;
}

auto GenerateUnrankedPattern = registration::AbstractRegister < RandomUnrankedPatternFactory, tree::UnrankedPattern < >, int, int, size_t, bool, size_t > ( RandomUnrankedPatternFactory::generateUnrankedPattern, abstraction::AlgorithmCategories::AlgorithmCategory::DEFAULT, "depth", "nodesCount", "maxAlphabetSize", "randomizedAlphabet", "maxRank" );

RankedTree < > RandomRankedTreeFactory::generateRankedTree ( int depth, int nodesCount, size_t maxAlphabetSize, bool randomizedAlphabet, size_t maxRank ) {
	Node * root = generateTreeStructure ( depth, nodesCount, maxRank );
	ext::map < int, ext::vector < char > > rankedAlphabet;

	root->fillRanks ( rankedAlphabet );
	generateRankedAlphabet ( rankedAlphabet, maxAlphabetSize, randomizedAlphabet );
	root->generateRankedSymbols ( rankedAlphabet );

	ext::set < common::ranked_symbol < > > treeRankedAlphabet;

	for ( const std::pair < const int, ext::vector < char > > & it : rankedAlphabet )
		for ( char i : it.second )
			treeRankedAlphabet.insert ( common::ranked_symbol < > ( DefaultSymbolType ( i ), it.first ) );

	RankedTree < > tree ( treeRankedAlphabet, root->createRankedNode ( ) );
	delete root;
	return tree;
}

auto GenerateRankedTree = registration::AbstractRegister < RandomRankedTreeFactory, tree::RankedTree < >, int, int, size_t, bool, size_t > ( RandomRankedTreeFactory::generateRankedTree, abstraction::AlgorithmCategories::AlgorithmCategory::DEFAULT, "depth", "nodesCount", "maxAlphabetSize", "randomizedAlphabet", "maxRank" );

RankedPattern < > RandomRankedPatternFactory::generateRankedPattern ( int depth, int nodesCount, size_t maxAlphabetSize, bool randomizedAlphabet, size_t maxRank ) {
	Node * root = generateTreeStructure ( depth, nodesCount, maxRank );
	ext::map < int, ext::vector < char > > rankedAlphabet;

	root->fillRanks ( rankedAlphabet );
	generateRankedAlphabet ( rankedAlphabet, maxAlphabetSize, randomizedAlphabet );
	root->generateRankedSymbols ( rankedAlphabet );

	ext::set < common::ranked_symbol < > > treeRankedAlphabet;

	for ( const std::pair < const int, ext::vector < char > > & it : rankedAlphabet )
		for ( char i : it.second )
			treeRankedAlphabet.insert ( common::ranked_symbol < > ( DefaultSymbolType ( i ), it.first ) );

	common::ranked_symbol < > subtreeWildcard = alphabet::WildcardSymbol::instance < common::ranked_symbol < > > ( );
	treeRankedAlphabet.insert ( subtreeWildcard );
	RankedPattern < > tree ( std::move ( subtreeWildcard ), treeRankedAlphabet, root->createRankedPatternNode ( ) );
	delete root;
	return tree;
}

auto GenerateRankedPattern = registration::AbstractRegister < RandomRankedPatternFactory, tree::RankedPattern < >, int, int, size_t, bool, size_t > ( RandomRankedPatternFactory::generateRankedPattern, abstraction::AlgorithmCategories::AlgorithmCategory::DEFAULT, "depth", "nodesCount", "randomizedAlphabet", "maxAlphabetSize", "maxRank" );

RankedNonlinearPattern < > RandomRankedNonlinearPatternFactory::generateRankedNonlinearPattern ( int depth, int nodesCount, size_t maxAlphabetSize, bool randomizedAlphabet, bool singleNonlinearVariable, size_t maxRank ) {
	Node * root = generateTreeStructure ( depth, nodesCount, maxRank );
	ext::map < int, ext::vector < char > > rankedAlphabet;

	root->fillRanks ( rankedAlphabet );
	generateRankedAlphabet ( rankedAlphabet, maxAlphabetSize, randomizedAlphabet );
	root->generateRankedSymbols ( rankedAlphabet );

	ext::set < common::ranked_symbol < > > treeRankedAlphabet;
	ext::set < common::ranked_symbol < > > nonlinearVariables;

	for ( const std::pair < const int, ext::vector < char > > & it : rankedAlphabet )
		for ( char i : it.second )
			treeRankedAlphabet.insert ( common::ranked_symbol < > ( DefaultSymbolType ( i ), it.first ) );

	if ( singleNonlinearVariable )
		nonlinearVariables.insert ( common::ranked_symbol < > ( DefaultSymbolType ( alphabet::NonlinearVariableSymbol < > ( DefaultSymbolType ( "A" ) ) ), 0 ) );
	else
		for ( char i : rankedAlphabet [ 0 ] )
			nonlinearVariables.insert ( common::ranked_symbol < > ( DefaultSymbolType ( alphabet::NonlinearVariableSymbol < > ( DefaultSymbolType ( i ) ) ), 0 ) );

	common::ranked_symbol < > subtreeWildcard = alphabet::WildcardSymbol::instance < common::ranked_symbol < > > ( );
	treeRankedAlphabet.insert ( subtreeWildcard );
	treeRankedAlphabet.insert ( nonlinearVariables.begin ( ), nonlinearVariables.end ( ) );
	RankedNonlinearPattern < > tree ( std::move ( subtreeWildcard ), nonlinearVariables, treeRankedAlphabet, root->createRankedNonlinearPatternNode ( singleNonlinearVariable ) );
	delete root;
	return tree;
}

} /* namespace generate */

} /* namespace tree */

namespace {

auto GenerateRankedNonlinearPattern = registration::AbstractRegister < tree::generate::RandomRankedNonlinearPatternFactory, tree::RankedNonlinearPattern < >, int, int, size_t, bool, bool, size_t > ( tree::generate::RandomRankedNonlinearPatternFactory::generateRankedNonlinearPattern, abstraction::AlgorithmCategories::AlgorithmCategory::DEFAULT, "depth", "nodesCount", "maxAlphabetSize", "randomizedAlphabet", "singleNonlinearVariable", "maxRank" );

} /* namespace */