Deterministic prefix tree automata. More...

#include <gfsmAutomaton.h>

Include dependency graph for gfsmTrie.h:

This graph shows which files directly or indirectly include this file:

Macros
Constructors etc.
#define	gfsm_trie_new() gfsm_automaton_new_full(gfsmTrieDefaultFlags, gfsmTrieDefaultSRType, gfsmAutomatonDefaultSize)

Typedefs
typedef gfsmAutomaton	gfsmTrie

Functions
Manipulation
gfsmStateId	gfsm_trie_add_path (gfsmTrie trie, gfsmLabelVector lo, gfsmLabelVector *hi, gfsmWeight w)
gfsmStateId	gfsm_trie_add_path_full (gfsmTrie trie, gfsmLabelVector lo, gfsmLabelVector hi, gfsmWeight w, gboolean add_to_arcs, gboolean add_to_state_final, gboolean add_to_path_final, gfsmStateIdVector path_states)
gfsmStateId	gfsm_trie_find_prefix (gfsmTrie trie, gfsmLabelVector lo, gfsmLabelVector hi, guint lo_i, guint hi_i, gfsmWeight w_last, gfsmStateIdVector *path_states)
gfsmArc *	gfsm_trie_find_arc_lower (gfsmTrie *trie, gfsmStateId qid, gfsmLabelVal lab)
gfsmArc *	gfsm_trie_find_arc_upper (gfsmTrie *trie, gfsmStateId qid, gfsmLabelVal lab)
gfsmArc *	gfsm_trie_find_arc_both (gfsmTrie *trie, gfsmStateId qid, gfsmLabelVal lo, gfsmLabelVal hi)
gfsmStateId	gfsm_trie_get_arc_lower (gfsmTrie *trie, gfsmStateId qid, gfsmLabelVal lab, gfsmWeight w, gboolean add_weight)
gfsmStateId	gfsm_trie_get_arc_upper (gfsmTrie *trie, gfsmStateId qid, gfsmLabelVal lab, gfsmWeight w, gboolean add_weight)
gfsmStateId	gfsm_trie_get_arc_both (gfsmTrie *trie, gfsmStateId qid, gfsmLabelVal lo, gfsmLabelVal hi, gfsmWeight w, gboolean add_weight)

Variables
const gfsmAutomatonFlags	gfsmTrieDefaultFlags
const gfsmSRType	gfsmTrieDefaultSRType

Detailed Description

Macro Definition Documentation

#define gfsm_trie_new ( ) gfsm_automaton_new_full(gfsmTrieDefaultFlags, gfsmTrieDefaultSRType, gfsmAutomatonDefaultSize)

Create a new gfsmTrie automaton

Typedef Documentation

typedef gfsmAutomaton gfsmTrie

Alias for gfsmAutomaton

Function Documentation

gfsmStateId gfsm_trie_add_path	(	gfsmTrie *	trie,
		gfsmLabelVector *	lo,
		gfsmLabelVector *	hi,
		gfsmWeight	w
	)

Add a string-pair (lo,hi) to the trie with weight w

Parameters

trie	Trie
lo	lower string (NULL for epsilon)
trie	upper string (NULL for epsilon)
w	weight which is added (gfsm_sr_plus) to all arcs for this pair

Returns: Id of the final state of the added path

Note: really just a wrapper for gfsm_trie_add_path_full() with add_to_arcs=true , add_to_state_final=true, add_to_path_final=true.

gfsmStateId gfsm_trie_add_path_full	(	gfsmTrie *	trie,
		gfsmLabelVector *	lo,
		gfsmLabelVector *	hi,
		gfsmWeight	w,
		gboolean	add_to_arcs,
		gboolean	add_to_state_final,
		gboolean	add_to_path_final,
		gfsmStateIdVector *	path_states
	)

Add a string-pair (lo,hi) to the trie with weight w

Parameters

trie	Trie
lo	lower string (NULL for epsilon)
hi	upper string (NULL for epsilon)
w	weight associated with this pair
add_to_arcs	whether to add (gfsm_sr_plus) w to all arc-weights
add_to_state_final	whether to add (gfsm_sr_plus) w to all intermediate state final-weights; implies that all states will be marked as final in the resulting automaton
add_to_path_final	whether to add (gfsm_sr_plus) w to the final weight for the last node in the path
path_states	If non-NULL, contains the state-path corresponding to (lo,hi) on return

Returns: Id of the final state of the added path

gfsmStateId gfsm_trie_find_prefix	(	gfsmTrie *	trie,
		gfsmLabelVector *	lo,
		gfsmLabelVector *	hi,
		guint *	lo_i,
		guint *	hi_i,
		gfsmWeight *	w_last,
		gfsmStateIdVector *	path_states
	)

Find state of longest prefix for a string-pair (lo,hi) in the trie.

Parameters

trie	Trie
lo	lower string (NULL for epsilon)
hi	upper string (NULL for epsilon)
lo_i	on return holds number of labels in lo which were matched
hi_i	on return holds number of labels in hi which were matched
w_last	pointer to weight of last arc followed or final weight
path_states	if non-NULL, contains the state-path corresponding to the prefix on return

Returns: Id of the state matching the longest prefix of (lo,hi)

gfsmArc* gfsm_trie_find_arc_lower	(	gfsmTrie *	trie,
		gfsmStateId	qid,
		gfsmLabelVal	lab
	)

Find an arc from state qid with lower label lab in trie trie.

Parameters

trie	Trie
qid	outgoing state qid
lab	lower label

Returns: gfsmArc* or NULL on failure

gfsmArc* gfsm_trie_find_arc_upper	(	gfsmTrie *	trie,
		gfsmStateId	qid,
		gfsmLabelVal	lab
	)

Find an arc from state qid with upper label lab in trie trie.

Parameters

trie	Trie
qid	outgoing state qid
lab	upper label id

Returns: gfsmArc* or NULL on failure

gfsmArc* gfsm_trie_find_arc_both	(	gfsmTrie *	trie,
		gfsmStateId	qid,
		gfsmLabelVal	lo,
		gfsmLabelVal	hi
	)

Find an arc from state qid with lower label lo and upper label hi in trie trie.

Parameters

trie	Trie
qid	outgoing state qid
lo	lower label id
hi	upper label id

Returns: gfsmArc* or NULL on failure

gfsmStateId gfsm_trie_get_arc_lower	(	gfsmTrie *	trie,
		gfsmStateId	qid,
		gfsmLabelVal	lab,
		gfsmWeight	w,
		gboolean	add_weight
	)

Find or insert an arc from state qid with lower label lab in trie trie; adding weight w.

Parameters

trie	Trie
qid	outgoing state qid
lab	lower label
w	arc weight
add_weight	whether to add weight to the arc

Returns: gfsmStateId of the (unique) destination state

gfsmStateId gfsm_trie_get_arc_upper	(	gfsmTrie *	trie,
		gfsmStateId	qid,
		gfsmLabelVal	lab,
		gfsmWeight	w,
		gboolean	add_weight
	)

Find or insert an arc from state qid with upper label lab in trie trie; adding weight w.

Parameters

trie	Trie
qid	outgoing state qid
lab	upper label
w	arc weight
add_weight	whether to add weight to the arc

Returns: gfsmStateId of the (unique) destination state

gfsmStateId gfsm_trie_get_arc_both	(	gfsmTrie *	trie,
		gfsmStateId	qid,
		gfsmLabelVal	lo,
		gfsmLabelVal	hi,
		gfsmWeight	w,
		gboolean	add_weight
	)

Find or insert an arc from state qid with lower label lo and upper label hi with weight w in trie trie.

Parameters

trie	Trie
qid	outgoing state qid
lo	lower label id
hi	upper label id
w	arc weight
add_weight	whether to add weight to the arc

Returns: gfsmStateId of the (unique) destination state

Variable Documentation

const gfsmAutomatonFlags gfsmTrieDefaultFlags

Default initial Trie flags

const gfsmSRType gfsmTrieDefaultSRType

Default initial Trie semiring

Macros

Typedefs

Functions

Variables

Detailed Description

Macro Definition Documentation

Typedef Documentation

Function Documentation

Variable Documentation