SlpTk: BidirectionalTrie - Bidirectional lexical tree structure module

LexicalEntry bidirectionalTrieAccess	(	const BidirectionalTrie *	bd_trie,
		const LexicalEntryIndex	index
	)

Return the lexical entry associated to a given key

Remarks:: The function returns NULL if the specified key is not used

Parameters:

`[in]`	bd_trie	The related bidirectional lexical tree
`[in]`	index	The key value

Returns:: The lexical entry indexed by the given key

TreeMemPos bidirectionalTrieAdd	(	BidirectionalTrie *	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()

See also:: bidirectionalTrieInsert()

gboolean bidirectionalTrieCharIsChild	(	const BidirectionalTrie *	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

BidirectionalTrie * bidirectionalTrieCreate ( 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:: bidirectionalTrieFree()

LexicalCharacter bidirectionalTrieDecodeNode	(	const BidirectionalTrie *	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 bidirectionalTrieDecodeNodeStack	(	const BidirectionalTrie *	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 bidirectionalTrieDump	(	const BidirectionalTrie *	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

Remarks:: Each entry stored is printed on a new line, its key followed by the lexical entry itself.

int bidirectionalTrieExport	(	const BidirectionalTrie *	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:: bidirectionalTrieImport()

Remarks:

The files created are:

a file (named filename + ".map") that contains on each line the keys of the stored lexical entries;
a file (name filename) that contains on each line the values of the corresponding lexical entries.

void bidirectionalTrieFree ( BidirectionalTrie * 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:: bidirectionalTrieCreate()

size_t bidirectionalTrieGetCurrentGraphyLength ( const BidirectionalTrie * 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 bidirectionalTrieGetCurrentGraphyUniqId ( const BidirectionalTrie * 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:: bidirectionalTrieIsAtEndOfGraphy()

LexicalDataType bidirectionalTrieGetDataType ( const BidirectionalTrie * 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:: bidirectionalTrieCreate()

TreeMemPos bidirectionalTrieGetFirstChild	(	const BidirectionalTrie *	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 bidirectionalTrieGetFirstSibling	(	const BidirectionalTrie *	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 bidirectionalTrieGetGraphyFromUniqId	(	const BidirectionalTrie *	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

LexicalCharacter bidirectionalTrieGetNextAvailableCharacter ( BidirectionalTrie * 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:: bidirectionalTrieGoCharacterForward() bidirectionalTrieGetCurrentGraphyLength() bidirectionalTrieGoToRoot()

gboolean bidirectionalTrieGetNextChild	(	const BidirectionalTrie *	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 bidirectionalTrieGetNextEntry ( BidirectionalTrie * 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:: bidirectionalTrieGoToFirstEntry()

size_t bidirectionalTrieGetSize ( const BidirectionalTrie * 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 bidirectionalTrieGoCharacterBackward ( BidirectionalTrie * 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:: bidirectionalTrieGoCharacterForward() bidirectionalTrieGoToRoot()

void bidirectionalTrieGoCharacterForward ( BidirectionalTrie * 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:: bidirectionalTrieIsAtEndOfGraphy() bidirectionalTrieGoToRoot()

void bidirectionalTrieGoToFirstEntry ( BidirectionalTrie * 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:: bidirectionalTrieGetNextEntry()

void bidirectionalTrieGoToRoot ( BidirectionalTrie * 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 bidirectionalTrieImplementAssociativeMemory ( LexicalAssocMem * lam )

Implement a lexical associative memory instance with a bidirectional trie data structure

Parameters:

[out] lam The lexical associative memory instance to implement

int bidirectionalTrieImport	(	BidirectionalTrie *	lexical_memory,
		const char *	filename
	)

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:: bidirectionalTrieExport()

TreeMemPos bidirectionalTrieInsert	(	BidirectionalTrie *	trie,
		const LexicalEntry	entry,
		const LexicalEntryIndex	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

See also:: bidirectionalTrieAdd()

gboolean bidirectionalTrieIsAtEndOfGraphy ( const BidirectionalTrie * 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:: bidirectionalTrieGoToRoot()

int bidirectionalTrieLoad	(	BidirectionalTrie *	lexical_memory,
		const char *	filename
	)

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:: bidirectionalTrieSave()

gboolean bidirectionalTrieNodeIsFinal	(	const BidirectionalTrie *	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 bidirectionalTrieSave	(	const BidirectionalTrie *	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:: bidirectionalTrieLoad()

Remarks:

The files created are:

a file (named filename + ".map") that stores the contents of the BidirectionalTrie::inversion_code_array field;
a file (name filename) that stores the BidirectionalTrie::trie field using the trieSave function.

LexicalSearch bidirectionalTrieSearchFirst	(	const BidirectionalTrie *	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:: bidirectionalTrieSearchNext()

gboolean bidirectionalTrieSearchNext ( 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:: bidirectionalTrieSearchFirst()

void bidirectionalTrieUniqIdToLexicalSearch	(	const BidirectionalTrie *	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:: bidirectionalSearchFirst()


Data Structures
struct	BidirectionalTrie
	Bidirectional lexical tree data structure. More...
Functions
void	bidirectionalTrieDump (const BidirectionalTrie lexical_memory, int(print)(const char *,...))
BidirectionalTrie *	bidirectionalTrieCreate (const LexicalDataType type)
void	bidirectionalTrieFree (BidirectionalTrie *lexical_memory)
int	bidirectionalTrieExport (const BidirectionalTrie lexical_memory, const char filename)
int	bidirectionalTrieImport (BidirectionalTrie lexical_memory, const char filename)
int	bidirectionalTrieSave (const BidirectionalTrie lexical_memory, const char filename)
int	bidirectionalTrieLoad (BidirectionalTrie lexical_memory, const char filename)
TreeMemPos	bidirectionalTrieInsert (BidirectionalTrie *trie, const LexicalEntry entry, const LexicalEntryIndex key)
TreeMemPos	bidirectionalTrieAdd (BidirectionalTrie *lexical_memory, const LexicalEntry entry)
LexicalDataType	bidirectionalTrieGetDataType (const BidirectionalTrie *lexical_memory)
void	bidirectionalTrieImplementAssociativeMemory (LexicalAssocMem *lam)
LexicalEntry	bidirectionalTrieAccess (const BidirectionalTrie *bd_trie, const LexicalEntryIndex index)
gboolean	bidirectionalTrieCharIsChild (const BidirectionalTrie trie, TreeMemPos actual_node_mempos, const LexicalCharacter character, TreeMemPos next_node_mempos)
gboolean	bidirectionalTrieNodeIsFinal (const BidirectionalTrie *trie, TreeMemPos node_mempos)
TreeMemPos	bidirectionalTrieGetFirstChild (const BidirectionalTrie *trie, const TreeMemPos node_mempos)
gboolean	bidirectionalTrieGetNextChild (const BidirectionalTrie trie, TreeMemPos parent_node_mempos, TreeMemPos child_node_mempos, LexicalCharacter *character)
TreeMemPos	bidirectionalTrieGetFirstSibling (const BidirectionalTrie *trie, const TreeMemPos node_mempos)
LexicalSearch	bidirectionalTrieSearchFirst (const BidirectionalTrie *lexical_memory, const LexicalEntry entry)
gboolean	bidirectionalTrieSearchNext (LexicalSearch *search)
LexicalCharacter	bidirectionalTrieDecodeNode (const BidirectionalTrie *trie, const TreeMemPos node_mempos)
LexicalEntry	bidirectionalTrieDecodeNodeStack (const BidirectionalTrie trie, const LongStack node_mempos_stack)
size_t	bidirectionalTrieGetSize (const BidirectionalTrie *lexical_memory)
void	bidirectionalTrieGoToRoot (BidirectionalTrie *lexical_memory)
gboolean	bidirectionalTrieIsAtEndOfGraphy (const BidirectionalTrie *lexical_memory)
LexicalCharacter	bidirectionalTrieGetNextAvailableCharacter (BidirectionalTrie *lexical_memory)
void	bidirectionalTrieGoCharacterForward (BidirectionalTrie *lexical_memory)
LexicalEntry	bidirectionalTrieGetNextEntry (BidirectionalTrie *lexical_memory)
void	bidirectionalTrieGoToFirstEntry (BidirectionalTrie *lexical_memory)
LexicalEntry	bidirectionalTrieGetGraphyFromUniqId (const BidirectionalTrie *lexical_memory, const UniqId identifier)
void	bidirectionalTrieGoCharacterBackward (BidirectionalTrie *lexical_memory)
size_t	bidirectionalTrieGetCurrentGraphyLength (const BidirectionalTrie *lexical_memory)
UniqId	bidirectionalTrieGetCurrentGraphyUniqId (const BidirectionalTrie *lexical_memory)
void	bidirectionalTrieUniqIdToLexicalSearch (const BidirectionalTrie lexical_memory, const UniqId uid, LexicalSearch output)

BidirectionalTrie - Bidirectional lexical tree structure module
[Lexical tools level]

Data Structures

Functions

Detailed Description

Function Documentation

BidirectionalTrie - Bidirectional lexical tree structure module [Lexical tools level]

Data Structures

Functions

Detailed Description

Function Documentation

BidirectionalTrie - Bidirectional lexical tree structure module
[Lexical tools level]