SlpTk: Trie - Lexical tree structure module

typedef unsigned long TrieLeaf

Lexical tree terminal node.

Associate a cardinal information (for example an index) to a lexical entry

TreeMemPos trieAdd	(	Trie *	lexical_memory,
		const LexicalEntry	entry
	)

Insert a new entry in a lexical memory.

Insert a new lexical entry (graphy) into lexical memory. The function returns an insertion result whose nature may vary from one implementation to another.

Parameters:

`[in]`	lexical_memory	The lexical memory
`[in]`	entry	The graphy of the entry to insert

Returns:: The insertion result

See also:: getSize()

Remarks:: The entries inserted with this function are indexed with a key value between 0 and the trie size minus one.

See also:: trieGetSize() trieInsert()

gboolean trieCharIsChild	(	const Trie *	trie,
		TreeMemPos	actual_node_mempos,
		const LexicalCharacter	character,
		TreeMemPos *	next_node_mempos
	)

Check if a lexical character is child of a trie node. If it's the case, the next_node_mempos parameter is set to the found node.

Parameters:

`[in]`	trie	The lexical tree
`[in]`	actual_node_mempos	The parent node memory address
`[in]`	character	The lexical character to check
`[out]`	next_node_mempos	The potential child node memory address

Returns:: A boolean flag informing that such node has been found (TRUE) or not (FALSE)

See also:: trieGetNextChild()

Former(s) function(s):: C_Est_Fils & Ulong_Est_Fils

Trie * trieCreate ( const LexicalDataType type )

Lexical memory constructor.

Allocate the memory and initialize a new lexical memory implementation.

Parameters:

[in] type The data type entries to store in the memory

Returns:: The new lexical memory instance

See also:: free()

See also:: trieFree()

Former(s) function(s):: Init_Arbre_Lexico

LexicalCharacter trieDecodeNode	(	const Trie *	trie,
		const TreeMemPos	node_mempos
	)

Decode the lexical character coded (with overflow bit) into a lexical tree node

Parameters:

`[in]`	trie	The lexical tree
`[in]`	node_mempos	The memory address of the node to decode

Returns:: The decoded lexical character

Former(s) function(s):: Decode_Char

LexicalEntry trieDecodeNodeStack	(	const Trie *	trie,
		const LongStack *	node_mempos_stack
	)

Return the lexical entry whose characters correspond to a given sequence of lexical tree nodes

Parameters:

`[in]`	trie	The lexical tree
`[in]`	node_mempos_stack	The stack that contains the node memory address to decode

Returns:: The corresponding lexical entry

Former(s) function(s):: Convert_Lexico_Pile_Int & Convert_Lexico_Ulong_Pile_Int

void trieDump	(	const Trie *	lexical_memory,
		int()(const char ,...)	print
	)

Dump the content of a lexical memory.

Dump the content of a lexical memory using a given print function. The function returns a not null error code if operation fails.

Parameters:

`[in]`	lexical_memory	The lexical memory to dump
`[in]`	print	The print function to use

Returns:: An error code

See also:: trieExtendedDump()

int trieExport	(	Trie *	lexical_memory,
		const char *	filename
	)

Export the content of a lexical memory.

Save the content of a lexical memory in a textual (human readable) file. The function returns a not null error code if operation fails.

Parameters:

`[in]`	lexical_memory	The lexical memory to export
`[in]`	filename	The name of the output file

Returns:: An error code

See also:: import()

See also:: trieImport()

Former(s) function(s):: Exporte_Arbre_Lexico

void trieExtendedDump	(	const Trie *	trie,
		int()(const char ,...)	print,
		gboolean	show_index,
		gboolean	inversion_code
	)

Dump the contents of a lexical tree

Parameters:

`[in]`	trie	The lexical tree to dump
`[in]`	print	The printing function
`[in]`	show_index	Specify if index are also dumped
`[in]`	inversion_code	Specify if inversion codes are also dumped

See also:: trieDump()

Former(s) function(s):: Liste_Lexico

void trieFree ( Trie * lexical_memory )

Free and destroy a lexical memory (destructor).

Destroy and free the memory allocated to a lexical memory

Parameters:

[in] lexical_memory The lexical memory to free

See also:: create()

See also:: trieCreate()

Former(s) function(s):: Libere_Arbre_Lexico

size_t trieGetCurrentGraphyLength ( const Trie * lexical_memory )

Return the length of the current word.

Return the length of the word associated to the current exploring position

Remarks:: The value returned is increment at every valid goCharacterForward call, decremented at every valid goCharacterBackward call, and reset to 0 at every goToRoot call.

Parameters:

[in] lexical_memory The lexical memory to explore

Returns:: The length of the word corresponding to the current exploring position

UniqId trieGetCurrentGraphyUniqId ( const Trie * lexical_memory )

Return the unique identifier associated to the current position.

Return the identifier of the word corresponding to the current exploring position.

Remarks:: A call to this function makes sense only if the current position corresponds to the end of a stored word. The user must check this condition by using the isAtEndOfGraphy function. If the parsed word is not stored by the lexical memory, this function returns 0.

Parameters:

[in] lexical_memory The lexical memory to explore

Returns:: The identifier from currently explored word

See also:: isAtEndOfGraphy()

See also:: trieIsAtEndOfGraphy()

LexicalDataType trieGetDataType ( const Trie * lexical_memory )

Tell the kind of lexical memory.

Return the data type of the entries stored in the lexical memory

Parameters:

[in] lexical_memory The lexical memory to identify

Returns:: The type of the stored entries

See also:: create()

See also:: trieCreate()

TreeMemPos trieGetFirstChildLeaf	(	const Trie *	trie,
		const TreeMemPos	node_mempos
	)

Check if the lexical tree node is parent of at least one leaf. Return the node memory address of the first leaf found

Parameters:

`[in]`	trie	The lexical tree
`[in]`	node_mempos	The parent node memory address

Returns:: The node memory address of the first leaf (0 if not found)

See also:: trieGetNextChild() trieGetFirstSibling()

Former(s) function(s):: Pere_Feuille

TreeMemPos trieGetFirstSibling	(	const Trie *	trie,
		const TreeMemPos	node_mempos
	)

Check if the lexical tree node is sibling of at least one leaf. Return the node memory address of the first leaf found

Parameters:

`[in]`	trie	The lexical tree
`[in]`	node_mempos	The sibling node memory address

Returns:: The node memory address of the first leaf (0 if not found)

See also:: trieGetFirstChildLeaf()

Former(s) function(s):: Frere_Feuille

LexicalEntry trieGetGraphyFromUniqId	(	const Trie *	lexical_memory,
		const UniqId	identifier
	)

Return the graphy corresponding to its unique identifier.

Return the lexical entry given by its unique corresponding identifier.

Remarks:: In a given lexical memory, any stored entry corresponds to a unique identifier and any valid identifier corresponds to a unique stored entry.

Parameters:

`[in]`	lexical_memory	The lexical memory
`[in]`	identifier	The entry identifier

Returns:: The corresponding entry

See also:: trieDecodeInversionCode()

LexicalCharacter trieGetNextAvailableCharacter ( Trie * lexical_memory )

Return the next character available at the current position.

Iteratively return all the lexical characters available from the current exploring position. This function can be called until its returns NO_CHARACTER, signifying that all possible characters have been returned. At this point, a further call to getNextAvailableCharacter goes back to the first lexical character available.

Parameters:

[in] lexical_memory The lexical memory to explore

See also:: goCharacterForward() getCurrentGraphyLength() goToRoot()

See also:: trieGoCharacterForward() trieGetCurrentGraphyLength() trieGoToRoot()

gboolean trieGetNextChild	(	const Trie *	trie,
		TreeMemPos	parent_node_mempos,
		TreeMemPos *	child_node_mempos,
		LexicalCharacter *	character
	)

Search the next child of a given lexical tree node and decode the corresponding lexical character if such node is found. This function considers the current value of the child_node_mempos to determine the next child that is then assigned to this same parameter.

Remarks:: To find the first child, one gives a child_node_mempos parameter that points on a null value

Parameters:

`[in]`	trie	The lexical tree
`[in]`	parent_node_mempos	The potential parent node memory address
`[out]`	child_node_mempos	The current/next child node memory address
`[out]`	character	The lexical character corresponding to the child node

Returns:: A boolean flag informing that such node has been found (TRUE) or not (FALSE)

See also:: trieCharIsChild()

Former(s) function(s):: Cherche_Fils & Get_Fils

LexicalEntry trieGetNextEntry ( Trie * lexical_memory )

Return the next graphy stored in a lexical memory.

Iteratively return all the graphies stored in a lexical memory. This function can be called until its returns NULL, signifying that all stored graphies have been returned.

Parameters:

[in] lexical_memory The lexical memory to make an inventory of

Returns:: The graphy of the next word stored

See also:: goToFirstEntry()

See also:: trieGoToFirstEntry()

size_t trieGetSize ( const Trie * lexical_memory )

Return the size of a lexical memory.

Return the number of entries stored in a lexical memory

Parameters:

[in] lexical_memory The lexical memory

Returns:: The number of entries stored

void trieGoCharacterBackward ( Trie * lexical_memory )

Step one lexical character backward the current position.

Step backward the current exploring position from one lexical character. The exploring informations of the position before the call are lost so that when one goes back to that position, available characters inventory start again from the beginning.

Remarks:: This function has no effect if the current position is the root of the lexical memory

Parameters:

[in] lexical_memory The lexical memory to explore

See also:: goCharacterForward() goToRoot()

See also:: trieGoCharacterForward() trieGoToRoot()

void trieGoCharacterForward ( Trie * lexical_memory )

Step one lexical character forward the current position.

Step forward the current exploring position from one lexical character, that is the value returned by the last call of getNextAvailableCharacter from the current exploring position. Each time this function is called, the current state is saved so that when one go back to a given exploring position using goCharacterBackward, the available characters inventory with getNextAvailableCharacter carries on as if the current position had not been left.

Remarks:: This function has no effect if getNextAvailableCharacter has not been called at least one time or no character is available from the current exploring position

Parameters:

[in] lexical_memory The lexical memory to explore

See also:: isAtEndOfGraphy() goToRoot()

See also:: trieIsAtEndOfGraphy() trieGoToRoot()

void trieGoToFirstEntry ( Trie * lexical_memory )

Go back to the first graphy stored in a lexical memory.

This function can be called anytime to order to start again the lexical memory inventory (with getNextEntry) from the beginning.

Parameters:

[in] lexical_memory The lexical memory to make an inventory of

See also:: trieGetNextEntry()

void trieGoToRoot ( Trie * lexical_memory )

Set the current position to the root of the lexical memory.

Assign the current exploring position to the root of the lexical memory, i.e. before the first lexical character.

Parameters:

[in] lexical_memory The lexical memory to explore

See also:: goCharacterForward() goCharacterBackward()

See also:: trieGoCharacterForward() trieGoCharacterBackward()

void trieImplementAccessTable ( LexicalAccessTable * lat )

Implement a lexical access table instance with a lexical tree data structure

Parameters:

[out] lat The lexical access table instance to implement

int trieImport	(	Trie *	lexical_memory,
		const char *	filename
	)

Load a lexical tree from a list of sequences stored in a textual file

Import the content of a lexical memory.

Load a lexical memory with the content of a textual (human readable) file. The function returns a not null error code if operation fails.

Parameters:

`[out]`	lexical_memory	The lexical memory where to import
`[in]`	filename	The name of the input file

Returns:: An error code

See also:: export()

See also:: trieExport()

Former(s) function(s):: Importe_Arbre_Lexico

TreeMemPos trieInsert	(	Trie *	trie,
		const LexicalEntry	entry,
		const TrieLeaf	key
	)

Insert a lexical entry and its associated key into the lexical tree

Parameters:

`[in]`	trie	The lexical tree
`[in]`	entry	The lexical entry to insert
`[in]`	key	The key associated to the lexical entry

Returns:: The node memory address of the inserted entry inversion code

See also:: trieAdd()

Former(s) function(s):: Insere_Lexico & Insere_Lexico_Ulong

gboolean trieIsAtEndOfGraphy ( const Trie * lexical_memory )

Tell if the current position corresponds to a stored entry.

Remarks:: The fact that the current position coincide with the end of a stored word doesn't imply that one can't carry on the exploration deeper (with goCharacterForward)

Parameters:

[in] lexical_memory The lexical memory to explore

Returns:: The current exploring position corresponds to the end of stoted word yes or not

See also:: getCurrentGraphyUniqId()

See also:: trieGetCurrentGraphyUniqId()

int trieLoad	(	Trie *	lexical_memory,
		const char *	filename
	)

Load the lexical tree from a binary file

Load a lexical memory from a file.

Load a lexical memory from a binary (machine readable) save file. The function returns a not null error code if operation fails.

Parameters:

`[out]`	lexical_memory	The lexical memory where to load
`[in]`	filename	The name of the output file

Returns:: An error code

See also:: save()

See also:: trieSave()

Former(s) function(s):: Read_Arbre_Lexico

gboolean trieNodeIsFinal	(	const Trie *	trie,
		TreeMemPos	node_mempos
	)

Specify if a lexical tree node is the parent of leafs only, that is the node corresponds to the last character of the explored lexical entry

Parameters:

`[in]`	trie	The lexical tree
`[in]`	node_mempos	The node memory address

Returns:: The given node is final (TRUE) or not (FALSE)

See also:: trieGetFirstChildLeaf() trieGetFirstSibling()

Former(s) function(s):: Fin_Arbre

int trieSave	(	Trie *	lexical_memory,
		const char *	filename
	)

Save a lexical memory in a file.

Save the content of a lexical memory in a binary (machine readable) file. The function returns a not null error code if operation fails.

Remarks:: The binary file format is dependant of the lexical memory implementation and of the used platform

Parameters:

`[in]`	lexical_memory	The lexical memory to save
`[in]`	filename	The name of the output file

Returns:: An error code

See also:: load()

See also:: trieLoad()

Former(s) function(s):: Write_Arbre_Lexico

LexicalSearch trieSearchFirst	(	const Trie *	lexical_memory,
		const LexicalEntry	entry
	)

Search the first occurence of a graphy in a lexical memory.

Search the information related to the first entry corresponding to a given graphy. The LexicalSearch::found field informs if such graphy has been found or not. If yes, other corresponding entries can be iteratively recovered using searchNext.

Parameters:

`[in]`	lexical_memory	The lexical memory where to search
`[in]`	entry	The graphy to search

Returns:: The search result

See also:: trieSearchNext()

Former(s) function(s):: GetFirst_Valeur_Lexico, GetFirst_Valeur_Lexico_Ulong, Recherche_Lexico & Recherche_Lexico_Ulong

gboolean trieSearchNext ( LexicalSearch * search )

Search the next occurence of a graphy in a lexical memory.

Carry on a search process initiate by searchFirst. This function can be iteratively called until its returns FALSE, signifying that all relevant entries have been returned.

Parameters:

[in] search The search result to update

Returns:: A new entry has been found yes or not

Remarks:: If operation fails, the inversion_code field is set to the last matching node.

See also:: trieSearchFirst()

Former(s) function(s):: GetNext_Valeur_Lexico

void trieUniqIdToLexicalSearch	(	const Trie *	lexical_memory,
		const UniqId	uid,
		LexicalSearch *	output
	)

Converts a UniqId to a LexicalSearch.

Converts an entry uniq identifier to the first corresponding LexicalSearch information. Notice however that the fields "found_length" and "specific.code" of the corresponding LexicalSearch are undefined in this context (and should thus not be used after).

Parameters:

`[in]`	lexical_memory	The corresponding lexical memory
`[in]`	uid	The UniqId to be converted
`[in]`	output	The LexicalSearch value to be updated

See also:: searchFirst()

See also:: trieSearchFirst()

Trie - Lexical tree structure module
[Lexical tools level]

Data Structures

Typedefs

Functions

Detailed Description

Typedef Documentation

Function Documentation


Data Structures
struct	Trie
	Lexical tree data structure. More...
Typedefs
typedef unsigned long	TrieLeaf
	Lexical tree terminal node.
Functions
void	trieExtendedDump (const Trie trie, int(print)(const char *,...), gboolean show_index, gboolean inversion_code)
Trie *	trieCreate (const LexicalDataType type)
void	trieFree (Trie *lexical_memory)
int	trieExport (Trie lexical_memory, const char filename)
int	trieSave (Trie lexical_memory, const char filename)
int	trieLoad (Trie lexical_memory, const char filename)
gboolean	trieSearchNext (LexicalSearch *search)
gboolean	trieNodeIsFinal (const Trie *trie, TreeMemPos node_mempos)
TreeMemPos	trieGetFirstChildLeaf (const Trie *trie, const TreeMemPos node_mempos)
TreeMemPos	trieGetFirstSibling (const Trie *trie, const TreeMemPos node_mempos)
void	trieDump (const Trie lexical_memory, int(print)(const char *,...))
TreeMemPos	trieAdd (Trie *lexical_memory, const LexicalEntry entry)
TreeMemPos	trieInsert (Trie *trie, const LexicalEntry entry, const TrieLeaf key)
int	trieImport (Trie lexical_memory, const char filename)
size_t	trieGetSize (const Trie *lexical_memory)
void	trieUniqIdToLexicalSearch (const Trie lexical_memory, const UniqId uid, LexicalSearch output)
LexicalSearch	trieSearchFirst (const Trie *lexical_memory, const LexicalEntry entry)
LexicalCharacter	trieDecodeNode (const Trie *trie, const TreeMemPos node_mempos)
LexicalEntry	trieGetGraphyFromUniqId (const Trie *lexical_memory, const UniqId identifier)
gboolean	trieGetNextChild (const Trie trie, TreeMemPos parent_node_mempos, TreeMemPos child_node_mempos, LexicalCharacter *character)
gboolean	trieCharIsChild (const Trie trie, TreeMemPos actual_node_mempos, const LexicalCharacter character, TreeMemPos next_node_mempos)
void	trieGoToRoot (Trie *lexical_memory)
void	trieGoCharacterForward (Trie *lexical_memory)
void	trieGoCharacterBackward (Trie *lexical_memory)
LexicalCharacter	trieGetNextAvailableCharacter (Trie *lexical_memory)
gboolean	trieIsAtEndOfGraphy (const Trie *lexical_memory)
size_t	trieGetCurrentGraphyLength (const Trie *lexical_memory)
UniqId	trieGetCurrentGraphyUniqId (const Trie *lexical_memory)
void	trieGoToFirstEntry (Trie *lexical_memory)
LexicalEntry	trieGetNextEntry (Trie *lexical_memory)
LexicalEntry	trieDecodeNodeStack (const Trie trie, const LongStack node_mempos_stack)
LexicalDataType	trieGetDataType (const Trie *lexical_memory)
void	trieImplementAccessTable (LexicalAccessTable *lat)

Trie - Lexical tree structure module [Lexical tools level]

Data Structures

Typedefs

Functions

Detailed Description

Typedef Documentation

Function Documentation

Trie - Lexical tree structure module
[Lexical tools level]