#include <stdlib.h>
#include "suffixTree.h"
#include "stack.h"
#include "alpha.h"
#include "text.h"
#include "gammaFunc.h"
#include "spacedef.h"
#include "debug.h"

Macros
#define	INFINITY -3
	Flag to indicate that the rightmost index of a label is the index of the last processed character of the input string. More...

#define	BOTTOM -2
	Flag to indicate a node is bottom. More...

#define	ROOT -1
	Flag to indicate a node is the root. More...

#define	GET_RIGHT(R, T)
	Gets the index of the rightmost character of this node label in the input string. More...

Functions
static void	canonize (suffixTree_t s, Uint k, Uint p, suffixTree_t retS, Uint retK)
	Given a reference for a (possibly implicit) state returns the canonical reference to the same state. More...

static BOOL	testAndSplit (suffixTree_t s, Uint k, Uint p, suffixTree_t *r)
	Tests if the input state is the end point. If it is not the end point, and it is not an explicit state it is made explicit by splitting a transition. More...

static void	addChild (suffixTree_t s, Uint i)
	Creates a new leaf on the tree. More...

static void	update (suffixTree_t s, Uint k, Uint i, suffixTree_t retS, Uint retK)
	Adds a new character of the input string to the evolving suffix tree. More...

static void	pruneSubTree (suffixTree_t tree)
	Delete a subtree from the complete tree. More...

suffixTree_t	initSuffixTree ()
	Creates and initializes a new suffix tree structure instance. More...

void	freeSuffixTree (suffixTree_t tree)
	Deletes a suffix tree structure instance. More...

void	buildSuffixTree (suffixTree_t tree)
	Builds a suffix tree based on the input string. More...

void	pruneSuffixTree (suffixTree_t tree)
	Prunes this suffix tree according to some cost function. More...

fsmTree_t	fsmSuffixTree (suffixTree_t tree)
	Transforms this tree in an equivalent fsm tree structure. More...

Macro Definition Documentation

#define BOTTOM -2

Flag to indicate a node is bottom.

Definition at line 33 of file suffixTree.c.

#define GET_RIGHT	(	R,
		T
	)

Value:

if (T->child) {\
          R = T->child->left-1;\
        }\
        else {\
          R = INFINITY;\
        }\

Gets the index of the rightmost character of this node label in the input string.

Parameters

[out]	R	the rightmost index.
[in]	T	tree node.

Definition at line 43 of file suffixTree.c.

#define INFINITY -3

Flag to indicate that the rightmost index of a label is the index of the last processed character of the input string.

Definition at line 30 of file suffixTree.c.

#define ROOT -1

Flag to indicate a node is the root.

Definition at line 36 of file suffixTree.c.

Function Documentation

static void addChild	(	suffixTree_t	s,
		Uint	i
	)

static

Creates a new leaf on the tree.

Parameters

[in]	s	parent of the new leaf to create.
[in]	i	index of the leftmost character of the new node label.

Definition at line 159 of file suffixTree.c.

void buildSuffixTree ( suffixTree_t tree )

Builds a suffix tree based on the input string.

Parameters

[in,out] tree an empty and initialized suffix tree.

Definition at line 325 of file suffixTree.c.

static void canonize	(	suffixTree_t	s,
		Uint	k,
		Uint	p,
		suffixTree_t *	retS,
		Uint *	retK
	)

static

Given a reference for a (possibly implicit) state returns the canonical reference to the same state.

Parameters

[in]	s	explicit state of the tree.
[in]	k	index of the leftmost character of the string from s to the state.
[in]	p	index of the rightmost character of the string from s to the state.
[out]	retS	new explicit state that is the closest ancestor of the state to canonize.
[out]	retK	index of the leftmost character of the string from retS to the state to canonize.

Definition at line 60 of file suffixTree.c.

void freeSuffixTree ( suffixTree_t tree )

Deletes a suffix tree structure instance.

Parameters

[in,out] tree the tree to delete.

Definition at line 317 of file suffixTree.c.

fsmTree_t fsmSuffixTree ( suffixTree_t tree )

Transforms this tree in an equivalent fsm tree structure.

Parameters

[in] tree the tree to transform.

Returns: a new fsm tree equivalent tho the input one.

Definition at line 422 of file suffixTree.c.

suffixTree_t initSuffixTree ( )

Creates and initializes a new suffix tree structure instance.

Returns: a new an initilized tree.

Definition at line 298 of file suffixTree.c.

static void pruneSubTree ( suffixTree_t tree )

static

Delete a subtree from the complete tree.

Parameters

[in] tree subtree to delete.

Definition at line 210 of file suffixTree.c.

void pruneSuffixTree ( suffixTree_t tree )

Prunes this suffix tree according to some cost function.

Parameters

[in,out] tree the tree to prune.

Definition at line 343 of file suffixTree.c.

static BOOL testAndSplit	(	suffixTree_t	s,
		Uint	k,
		Uint	p,
		suffixTree_t *	r
	)

static

Tests if the input state is the end point. If it is not the end point, and it is not an explicit state it is made explicit by splitting a transition.

Parameters

[in]	s	explicit state of the tree.
[in]	k	index of the leftmost character of the string from s to the state.
[in]	p	index of the rightmost character of the string from s to the state.
[out]	r	new explicit state created or s if a new node was not needed.

Returns: True if the input state is the end point.

Definition at line 102 of file suffixTree.c.

static void update	(	suffixTree_t	s,
		Uint	k,
		Uint	i,
		suffixTree_t *	retS,
		Uint *	retK
	)

static

Adds a new character of the input string to the evolving suffix tree.

Parameters

s	explicit node on the tree that is the closest ancestor to the active point.
k	index of the leftmost character of the string from s to the active point.
i	integer such that (i-1) is the index of the rightmost character of the string from s to the active point.
retS	explicit node on the tree that is an ancestor of the end point.
retK	index of the leftmost character of the string from retS to the end point.

Definition at line 184 of file suffixTree.c.

Macros

Functions

Macro Definition Documentation

Function Documentation