FormalRegExpElement.h

/*
 * FormalRegExpElement.h
 *
 * This file is part of Algorithms library toolkit.
 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)

 * Algorithms library toolkit is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.

 * Algorithms library toolkit is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.

 * You should have received a copy of the GNU General Public License
 * along with Algorithms library toolkit.  If not, see <http://www.gnu.org/licenses/>.
 *
 *  Created on: Nov 23, 2013
 *      Author: Jan Travnicek
 */

#ifndef FORMAL_REG_EXP_ELEMENT_H_
#define FORMAL_REG_EXP_ELEMENT_H_

#include <common/DefaultSymbolType.h>

namespace regexp {

template < class SymbolType >
class FormalRegExpElement;

} /* namespace regexp */

#include <alib/set>
#include <alib/tree>
#include <alib/compare>
#include <core/visitor.hpp>

#include "../unbounded/UnboundedRegExpElement.h"

namespace regexp {

template < class SymbolType >
class FormalRegExpAlternation;
template < class SymbolType >
class FormalRegExpConcatenation;
template < class SymbolType >
class FormalRegExpIteration;
template < class SymbolType >
class FormalRegExpSymbol;
template < class SymbolType >
class FormalRegExpEmpty;
template < class SymbolType >
class FormalRegExpEpsilon;

/**
 * Abstract class representing element in the formal regular expression. Can be an operator, special node, or a symbol.
 *
 * \tparam SymbolType used for the terminal alphabet
 */
template < class SymbolType >
class FormalRegExpElement : public ext::CompareOperators < FormalRegExpElement < SymbolType > >, public ext::BaseNode < FormalRegExpElement < SymbolType > > {
protected:
	/**
	 * Visitor interface of the element.
	 */
	class Visitor {
	public:
		virtual void visit ( const FormalRegExpAlternation < SymbolType > & ) = 0;
		virtual void visit ( const FormalRegExpConcatenation < SymbolType > & ) = 0;
		virtual void visit ( const FormalRegExpIteration < SymbolType > & ) = 0;
		virtual void visit ( const FormalRegExpSymbol < SymbolType > & ) = 0;
		virtual void visit ( const FormalRegExpEmpty < SymbolType > & ) = 0;
		virtual void visit ( const FormalRegExpEpsilon < SymbolType > & ) = 0;
	};

	/**
	 * Helper class interconnecting the visitor interface and visitor core logic.
	 *
	 * \tparam ReturnType the return type of the result of the visit
	 * \tparam Visitorr the type of the actuall visitor
	 * \tparam Params ... types of data passed with the visitor call
	 */
	template < class ReturnType, class Visitor, class ... Params >
	class VisitorContext : public core::VisitorContextAux < ReturnType, Visitor, Params ... >, public FormalRegExpElement::Visitor {
	public:
		/**
		 * Inherited constructor.
		 */
		using core::VisitorContextAux < ReturnType, Visitor, Params ... >::VisitorContextAux;

		/**
		 * Method passing the visit call to the visitor core logic.
		 */
		void visit ( const FormalRegExpAlternation < SymbolType > & inherit ) override {
			this->call ( inherit, std::make_index_sequence < sizeof ... ( Params ) > { } );
		}

		/**
		 * Method passing the visit call to the visitor core logic.
		 */
		void visit ( const FormalRegExpConcatenation < SymbolType > & inherit ) override {
			this->call ( inherit, std::make_index_sequence < sizeof ... ( Params ) > { } );
		}

		/**
		 * Method passing the visit call to the visitor core logic.
		 */
		void visit ( const FormalRegExpIteration < SymbolType > & inherit ) override {
			this->call ( inherit, std::make_index_sequence < sizeof ... ( Params ) > { } );
		}

		/**
		 * Method passing the visit call to the visitor core logic.
		 */
		void visit ( const FormalRegExpSymbol < SymbolType > & inherit ) override {
			this->call ( inherit, std::make_index_sequence < sizeof ... ( Params ) > { } );
		}

		/**
		 * Method passing the visit call to the visitor core logic.
		 */
		void visit ( const FormalRegExpEmpty < SymbolType > & inherit ) override {
			this->call ( inherit, std::make_index_sequence < sizeof ... ( Params ) > { } );
		}

		/**
		 * Method passing the visit call to the visitor core logic.
		 */
		void visit ( const FormalRegExpEpsilon < SymbolType > & inherit ) override {
			this->call ( inherit, std::make_index_sequence < sizeof ... ( Params ) > { } );
		}
	};

	/**
	 * \brief Accept method of the visitor pattern. This is where the actual type of this object is evaluated.
	 *
	 * \param visitor the accepted visitor.
	 */
	virtual void accept ( FormalRegExpElement::Visitor & visitor ) const = 0;

public:
	virtual FormalRegExpElement < SymbolType > * clone ( ) const & = 0;

	virtual FormalRegExpElement < SymbolType > * clone ( ) && = 0;

	/**
	 * Visitor interface method.
	 *
	 * \tparam ReturnType the return type of the result of the visit
	 * \tparam Visitorr the type of the actuall visitor
	 * \tparam Params ... types of data passed with the visitor call
	 *
	 * \params params ... Additional params passed to visited nodes
	 *
	 * \return result of the visit
	 */
	template < class ReturnType, class Visitor, class ... Params >
	ReturnType accept ( Params && ... params ) const {
		VisitorContext < ReturnType, Visitor, Params ... > context ( std::forward < Params > ( params ) ... );
		accept ( context );
		return context.getResult ( );
	}

	/**
	 * Creates copy of the element.
	 *
	 * \return copy of the element
	 */
	virtual ext::smart_ptr < UnboundedRegExpElement < SymbolType > > asUnbounded ( ) const = 0;

	/**
	 * Traverses the regexp tree looking if particular Symbol is used in the regexp.
	 *
	 * \param symbol to test if used in regexp element
	 * \return true if symbol is used by the element and its successor
	 */
	virtual bool testSymbol ( const SymbolType & symbol ) const = 0;

	/**
	 * Traverses the regexp tree computing minimal alphabet needed by regexp
	 *
	 * \param alphabet All alphabet symbols encountered are added into this set
	 */
	virtual void computeMinimalAlphabet ( ext::set < SymbolType > & alphabet ) const = 0;

	/**
	 * Traverses the regexp tree and checks whether all symbols in the regexp tree are in the alphabet
	 *
	 * \param alphabet
	 * \return true if symbols in the regexp are in the alphabet, false otherwise
	 */
	virtual bool checkAlphabet ( const ext::set < SymbolType > & alphabet ) const = 0;

	/**
	 * Traverses the regexp tree computing minimal alphabet needed by regexp
	 *
	 * \return the minimal alphabet needed by the regexp
	 */
	ext::set < SymbolType > computeMinimalAlphabet ( ) const;

	/**
	 * \brief Traverses the regexp tree and normalizes the symbols to DefaultSymbolType
	 *
	 * \return the cloned node including children representing the same content but with type of symbols normalized to DefaultSymbolType
	 */
	virtual ext::smart_ptr < FormalRegExpElement < DefaultSymbolType > > normalize ( ) && = 0;

	/**
	 * Print this object as raw representation to ostream.
	 *
	 * \param os ostream where to print
	 * \param instance object to print
	 *
	 * \returns modified output stream
	 */
	friend std::ostream & operator <<( std::ostream & os, const FormalRegExpElement < SymbolType > & instance ) {
		instance >> os;
		return os;
	}

	/**
	 * Print this instance as raw representation to ostream.
	 *
	 * \param os ostream where to print
	 */
	virtual void operator >>( std::ostream & ) const = 0;

	/**
	 * Casts this instance to as compact as possible string representation.
	 *
	 * \returns string representation of the object
	 */
	virtual explicit operator std::string ( ) const = 0;

	/**
	 * \brief Comparison helper method evaluating allowing possibly deeper comparison of this with other class of the same hierarchy.
	 *
	 * \details If the other class is of different type the relative order is computer by means of type_index.
	 *
	 * \param other the other class to compare with
	 *
	 * \returns result of actual comparison if type of this class and other class is the same, result of difference of type indexes othervise.
	 */
	virtual int compare ( const FormalRegExpElement < SymbolType > & other ) const = 0;
};

template < class SymbolType >
ext::set < SymbolType > FormalRegExpElement < SymbolType >::computeMinimalAlphabet ( ) const {
	ext::set < SymbolType > res;

	computeMinimalAlphabet ( res );
	return res;
}

} /* namespace regexp */

#endif /* FORMAL_REG_EXP_ELEMENT_H_ */