SubtreeJumpTable.h

/*
 * SubtreeJumpTable.h
 *
 *  Created on: 5. 11. 2014
 *      Author: Jan Travnicek
 */

#ifndef _SUBTREE_JUMP_TABLE_H_
#define _SUBTREE_JUMP_TABLE_H_

#include <alib/vector>

#include <tree/ranked/PrefixRankedTree.h>
#include <tree/ranked/PrefixRankedPattern.h>
#include <tree/ranked/PrefixRankedNonlinearPattern.h>
#include <tree/ranked/PrefixRankedBarTree.h>
#include <tree/ranked/PrefixRankedBarPattern.h>
#include <tree/ranked/PrefixRankedBarNonlinearPattern.h>

namespace tree {

namespace properties {

class SubtreeJumpTable {
	template < class T >
	static int buildDataPointersBar ( ext::vector < int > & res, const T & subject, int begin );
	template < class T >
	static int buildDataPointersPrefixRanked ( ext::vector < int > & res, const T & subject, int begin );
	template < class T >
	static int buildDataPointersPrefixRankedInternal ( ext::vector < int > & res, const T & subject, int begin );

public:
	template < class SymbolType, class RankType >
	static ext::vector < int > compute ( const tree::PrefixRankedBarTree < SymbolType, RankType > & subject );
	template < class SymbolType, class RankType >
	static ext::vector < int > compute ( const tree::PrefixRankedBarPattern < SymbolType, RankType > & pattern );
	template < class SymbolType, class RankType >
	static ext::vector < int > compute ( const tree::PrefixRankedBarNonlinearPattern < SymbolType, RankType > & pattern );
	template < class SymbolType, class RankType >
	static ext::vector < int > compute ( const tree::PrefixRankedTree < SymbolType, RankType > & subject );
	template < class SymbolType, class RankType >
	static ext::vector < int > compute ( const tree::PrefixRankedPattern < SymbolType, RankType > & pattern );
	template < class SymbolType, class RankType >
	static ext::vector < int > compute ( const tree::PrefixRankedNonlinearPattern < SymbolType, RankType > & pattern );

};

template < class SymbolType, class RankType >
ext::vector < int > SubtreeJumpTable::compute ( const tree::PrefixRankedBarTree < SymbolType, RankType > & subject ) {
	ext::vector < int > res;

	buildDataPointersBar ( res, subject, 0 );

	return res;
}

template < class SymbolType, class RankType >
ext::vector < int > SubtreeJumpTable::compute ( const tree::PrefixRankedBarPattern < SymbolType, RankType > & pattern ) {
	ext::vector < int > res;

	buildDataPointersBar ( res, pattern, 0 );

	return res;
}

template < class SymbolType, class RankType >
ext::vector < int > SubtreeJumpTable::compute ( const tree::PrefixRankedBarNonlinearPattern < SymbolType, RankType > & pattern ) {
	ext::vector < int > res;

	buildDataPointersBar ( res, pattern, 0 );

	return res;
}

template < class SymbolType, class RankType >
ext::vector < int > SubtreeJumpTable::compute ( const tree::PrefixRankedTree < SymbolType, RankType > & subject ) {
	ext::vector < int > res;

	buildDataPointersPrefixRanked ( res, subject, 0 );

	return res;
}

template < class SymbolType, class RankType >
ext::vector < int > SubtreeJumpTable::compute ( const tree::PrefixRankedPattern < SymbolType, RankType > & pattern ) {
	ext::vector < int > res;

	buildDataPointersPrefixRanked ( res, pattern, 0 );

	return res;
}

template < class SymbolType, class RankType >
ext::vector < int > SubtreeJumpTable::compute ( const tree::PrefixRankedNonlinearPattern < SymbolType, RankType > & pattern ) {
	ext::vector < int > res;

	buildDataPointersPrefixRanked ( res, pattern, 0 );

	return res;
}

/**
 * used to compute subtree jump table.
 * @param begin - index of a root node of a complete subtree to process
 * @return index, increased by one, of the last node in the subtree starting at index begin
 */
template < class T >
int SubtreeJumpTable::buildDataPointersBar ( ext::vector < int > & res, const T & subject, int begin ) {
	res.push_back ( 0 );
	int index = begin + 1;

	if ( ! subject.getBars ( ).count ( subject.getContent ( )[begin] ) )
		for ( unsigned i = 0; i < ( unsigned ) subject.getContent ( )[begin].getRank ( ); i++ )
			index = buildDataPointersBar ( res, subject, index );

	index++;
	res[begin] = index;
	res.push_back ( begin - 1 );
	return index;
}

/**
 * used to compute subtree jump table.
 * @param begin - index of a root node of a complete subtree to process
 * @return index, increased by one, of the last node in the subtree starting at index begin
 */
template < class T >
int SubtreeJumpTable::buildDataPointersPrefixRanked ( ext::vector < int > & res, const T & subject, int begin ) {
	for ( size_t i = 0; i < subject.getContent ( ).size ( ); i++ )
		res.push_back ( 0 );

	return buildDataPointersPrefixRankedInternal ( res, subject, begin );
}

template < class T >
int SubtreeJumpTable::buildDataPointersPrefixRankedInternal ( ext::vector < int > & res, const T & subject, int begin ) {
	int index = begin + 1;

	for ( unsigned i = 0; i < ( unsigned ) subject.getContent ( )[begin].getRank ( ); i++ )
		index = buildDataPointersPrefixRankedInternal ( res, subject, index );

	res[begin] = index;
	return index;
}

} /* namespace properties */

} /* namespace tree */

#endif /* _SUBTREE_JUMP_TABLE_H_ */