O_state Class Reference
[Factor Oracle structure]

Factor Oracle state class. More...

#include <Oracle_classes.hpp>

Collaboration diagram for O_state:

Protected Attributes
int	statenb
	Number of the state in FO.
list< O_state * >	trans
	List of transitions of the state.
pair< O_state *, int >	suff
	Suffix link of the state.
list< pair< O_state *, int > >	rsuff
	List of reverse suffix links of the state.
Public Member Functions
Constructors & Destructors

	O_state ()
	Default constructor.
	O_state (int)
	Create a state with its number.
	O_state (const O_state &)
	Copy constructor.
	~O_state ()
	Standard destructor.
Set & Get

int	get_statenb ()
	Return the number of the state in FO.
void	set_statenb (int)
	Set the number of the state in FO.
list< O_state * >	get_trans ()
	Return the list transitions.
pair< O_state *, int >	get_suffix ()
	Return the suffix link and the associated lrs.
void	set_suffix (O_state *, int)
	Set the suffix link and associated lrs.
list< pair< O_state *, int > >	get_rsuff ()
	Return the list of reverse suffix links.
Transitions & Suffixes

void	add_trans (O_state *)
	Add a transition to the transition list.
void	add_rsuff (const pair< O_state *, int > &rsuffin)
	Add a link to the reverse suffix links list.
Suffix Tree Functions

O_state *	rec_upSLT (list< O_state * > *, int=0)
	Recursive function to follow suffix links.
list< pair< O_state , int > >	rec_downSLT (list< pair< O_state , int > > , int=0)
	Recursive function to follow reverse suffix links.
list< pair< O_state , int > >	rec_sortSLT (list< pair< O_state , int > > , int=0, int=INT_MAX)
	Recursive function to list & sort nodes in a subSLT.
list< pair< O_state , int > >	sortedSLT (int=0, int=INT_MAX)
	Function to collect and sort all jump candidates from a state.
Friends
Operators Overload

ostream &	operator<< (ostream &, O_state &)
	Output the attributes of the state on a standard stream.

Detailed Description

Factor Oracle state class.

This class implements the basic structure of an Factor Oracle state with transitions, suffix link and reverse suffix links. The Length of Repeated Suffix (lrs) is the length of the common suffix between both ends of a link.

Definition at line 27 of file Oracle_classes.hpp.

Member Data Documentation

list<pair<O_state*,int> > O_state::rsuff [protected]

List of reverse suffix links of the state.

That a list of every suffix link pointing to the state with their origin and lrs.

Definition at line 40 of file Oracle_classes.hpp.

pair<O_state*,int> O_state::suff [protected]

Suffix link of the state.

The first element of the pair is the destination of the link, the second element is the lrs.

Definition at line 37 of file Oracle_classes.hpp.

list<O_state*> O_state::trans [protected]

List of transitions of the state.

Each pointer in the list represents a transition from the state to the pointed state.

Definition at line 34 of file Oracle_classes.hpp.

Constructor & Destructor Documentation

O_state::O_state ( )

Default constructor.

Remarks:: State number is initialised to 0 and suffix (suff) to <NULL,-1>

Definition at line 12 of file Oracle_classes.cpp.

O_state::O_state ( int nb )

Create a state with its number.

Remarks:: Suffix (suff) is initialise to <NULL,-1>

Definition at line 20 of file Oracle_classes.cpp.

Member Function Documentation

list< pair< O_state *, int > > O_state::get_rsuff ( )

Return the list of reverse suffix links.

Remarks:: Each element of the list is a pair of a pointer to the origin of the link and the associated lrs

Definition at line 63 of file Oracle_classes.cpp.

list< O_state * > O_state::get_trans ( )

Return the list transitions.

Remarks:: Each pointer in the list is the destination state of a transition. Transitions labels are given by destinations labels (see Data Sequence structure).

Definition at line 46 of file Oracle_classes.cpp.

list< pair< O_state , int > > O_state::rec_downSLT	(	list< pair< O_state , int > >	SLTlist,
		int	ctxtmin = `0`
	)

Recursive function to follow reverse suffix links.

Starting from the current state, this function recursively follows reverse suffix links. It pushes on the froont of the list SLTlist every state it visited. Reverse suffix links are visited if lrs<ctxtmin. Recursion stops when every link has been followed.

Remarks:: This function correspond to a recursive preorder traversal algorithm for the tree rooted at the starting state and constituted by all the states linked by a reverse suffix links with lrs>=ctxtmin.

Parameters:

	SLTlist	A pointer to an empy list of pairs of state reference and lrs to push every state along the path
	ctxtmin	A minimal context (lrs) to select reverse suffix links (default is 0 and the algorithm visites all the states of FO).

Returns:: The pointer to the list which contains, after the running of the function, every visited state in the traversal order.

Definition at line 101 of file Oracle_classes.cpp.

list< pair< O_state , int > > O_state::rec_sortSLT	(	list< pair< O_state , int > >	SLTlist,
		int	ctxtmin = `0`,
		int	ctxt = `INT_MAX`
	)

Recursive function to list & sort nodes in a subSLT.

Parameters:

	SLTlist	A pointer to a list of pairs of state reference and lrs to push every state along the path
	ctxtmin	A minimal context (lrs) to select reverse suffix links (default is 0 and the algorithm visites all the states of FO).

Returns:: The pointer to the list which contains, after the running of the function, every visited state in decreasing lrs order.

Definition at line 119 of file Oracle_classes.cpp.

O_state * O_state::rec_upSLT	(	list< O_state * > *	path,
		int	ctxtmin = `0`
	)

Recursive function to follow suffix links.

Starting from the current state, this function recursively follows suffix links. It pushes on the front of the list path every state it visited. Recursion stops when a suffix link with an lrs<ctxtmin is encounterd.

Parameters:

	path	A pointer to an empty list of state references to push the path of suffix links
	ctxtmin	A minimal context (lrs) to stop the recursion (default is 0 and the recursion goes to the very first state of FO).

Returns:: A pointer to the last visited state.

Definition at line 85 of file Oracle_classes.cpp.

Here is the call graph for this function:

list< pair< O_state , int > > O_state::sortedSLT	(	int	ctxtmin = `0`,
		int	nbMaxSol = `INT_MAX`
	)

Function to collect and sort all jump candidates from a state.

Parameters:

	ctxtmin	A minimal context (lrs) to select reverse suffix links (default is 0 and the algorithm visites all the states of FO).
	nbMaxSol	A maximal number of solution to collect (default is INT_MAX and the algorithm collects all the solutions)

Definition at line 141 of file Oracle_classes.cpp.

Here is the call graph for this function:

The documentation for this class was generated from the following files:

O_state Class Reference [Factor Oracle structure]

Protected Attributes

Public Member Functions

Friends

Detailed Description

Member Data Documentation

Constructor & Destructor Documentation

Member Function Documentation

O_state Class Reference
[Factor Oracle structure]