BorderArrayNaive.h

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

#ifndef _ARBOLOGY_BORDER_ARRAY_NAIVE_H_
#define _ARBOLOGY_BORDER_ARRAY_NAIVE_H_

#include <vector>

#include <core/multipleDispatch.hpp>
#include <global/GlobalData.h>

#include "SubtreeJumpTable.h"

#include <tree/Tree.h>
#include <tree/TreeFeatures.h>
#include <tree/ranked/PrefixRankedBarPattern.h>
#include <tree/ranked/PrefixRankedPattern.h>

namespace tree {

namespace properties {

/**
 * Computation of BCS table for BMH from MI(E+\eps)-EVY course 2014
 * To get rid of zeros in BCS table we ignore last haystack character
 */
class BorderArrayNaive : public alib::SingleDispatch < BorderArrayNaive, ext::vector < size_t >, const tree::TreeBase & > {
	template < class SymbolType, class RankType >
	static bool matches ( const tree::PrefixRankedBarPattern < SymbolType, RankType > & pattern, const ext::vector < int > & subtreeJumpTable, int stop, int offset );

	template < class SymbolType, class RankType >
	static bool matches ( const tree::PrefixRankedPattern < SymbolType, RankType > & pattern, const ext::vector < int > & subtreeJumpTable, int stop, int offset );

public:
	/**
	 * Search for pattern in linear string.
	 * @return set set of occurences
	 */
	static ext::vector < size_t > ba ( const tree::Tree & pattern );

	/**
	 * Search for pattern in linear string.
	 * @return set set of occurences
	 */
	template < class SymbolType, class RankType >
	static ext::vector < size_t > ba ( const tree::PrefixRankedBarPattern < SymbolType, RankType > & pattern );

	/**
	 * Search for pattern in linear string.
	 * @return set set of occurences
	 */
	template < class SymbolType, class RankType >
	static ext::vector < size_t > ba ( const tree::PrefixRankedPattern < SymbolType, RankType > & pattern );

};

template < class SymbolType, class RankType >
bool BorderArrayNaive::matches ( const tree::PrefixRankedBarPattern < SymbolType, RankType > & pattern, const ext::vector < int > & subtreeJumpTable, int stop, int offset ) {
	unsigned i = 0;

	while ( offset < stop && i < pattern.getContent ( ).size ( ) )
		if ( pattern.getContent ( )[i] == pattern.getContent ( )[offset] ) {
			i++;
			offset++;
		} else if ( ( pattern.getContent ( )[i] == pattern.getSubtreeWildcard ( ) ) || ( pattern.getContent ( )[offset] == pattern.getSubtreeWildcard ( ) ) ) {
			i = subtreeJumpTable[i];
			offset = subtreeJumpTable[offset];
		} else {
			return false;
		}

	return true;
}

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

	for ( unsigned i = 0; i <= pattern.getContent ( ).size ( ); i++ )
		res.push_back ( 0 );

	res[0] = -1;

	for ( unsigned i = 1; i <= pattern.getContent ( ).size ( ); i++ ) {
		int min = i;

		for ( unsigned j = 1; j < i; j++ )
			if ( matches ( pattern, patternSubtreeJumpTable, i, j ) ) {
				min = j;
				break;
			}

		res[i] = i - min;
	}

	if ( common::GlobalData::verbose )
		std::clog << res << std::endl;

	return res;
}

template < class SymbolType, class RankType >
bool BorderArrayNaive::matches ( const tree::PrefixRankedPattern < SymbolType, RankType > & pattern, const ext::vector < int > & subtreeJumpTable, int stop, int offset ) {
	unsigned i = 0;

	while ( offset < stop && i < pattern.getContent ( ).size ( ) )
		if ( pattern.getContent ( )[i] == pattern.getContent ( )[offset] ) {
			i++;
			offset++;
		} else if ( ( pattern.getContent ( )[i] == pattern.getSubtreeWildcard ( ) ) || ( pattern.getContent ( )[offset] == pattern.getSubtreeWildcard ( ) ) ) {
			i = subtreeJumpTable[i];
			offset = subtreeJumpTable[offset];
		} else {
			return false;
		}

	return true;
}

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

	for ( unsigned i = 0; i <= pattern.getContent ( ).size ( ); i++ )
		res.push_back ( 0 );

	res[0] = -1;

	for ( unsigned i = 1; i <= pattern.getContent ( ).size ( ); i++ ) {
		int min = i;

		for ( unsigned j = 1; j < i; j++ )
			if ( matches ( pattern, patternSubtreeJumpTable, i, j ) ) {
				min = j;
				break;
			}

		res[i] = i - min;
	}

	if ( common::GlobalData::verbose )
		std::clog << res << std::endl;

	return res;
}

} /* namespace properties */

} /* namespace tree */

#endif /* _ARBOLOGY_BORDER_ARRAY_NAIVE_H_ */