libthai
0.1.19
|
Double-array trie structure. More...
Macros | |
#define | da_is_walkable(d, s, c) (da_get_check ((d), da_get_base ((d), (s)) + (c)) == (s)) |
Test walkability in double-array structure. More... | |
Typedefs | |
typedef struct _Symbols | Symbols |
Symbol set structure type. | |
typedef struct _DArray | DArray |
Double-array structure type. | |
Functions | |
DArray * | da_new () |
Create a new double-array object. More... | |
DArray * | da_fread (FILE *file) |
Read double-array data from file. More... | |
void | da_free (DArray *d) |
Free double-array data. More... | |
int | da_fwrite (const DArray *d, FILE *file) |
Write double-array data. More... | |
TrieIndex | da_get_root (const DArray *d) |
Get root state. More... | |
TrieIndex | da_get_base (const DArray *d, TrieIndex s) |
Get BASE cell. More... | |
TrieIndex | da_get_check (const DArray *d, TrieIndex s) |
Get CHECK cell. More... | |
void | da_set_base (DArray *d, TrieIndex s, TrieIndex val) |
Set BASE cell. More... | |
void | da_set_check (DArray *d, TrieIndex s, TrieIndex val) |
Set CHECK cell. More... | |
Bool | da_walk (const DArray *d, TrieIndex *s, TrieChar c) |
Walk in double-array structure. More... | |
TrieIndex | da_insert_branch (DArray *d, TrieIndex s, TrieChar c) |
Insert a branch from trie node. More... | |
void | da_prune (DArray *d, TrieIndex s) |
Prune the single branch. More... | |
void | da_prune_upto (DArray *d, TrieIndex p, TrieIndex s) |
Prune the single branch up to given parent. More... | |
TrieIndex | da_first_separate (DArray *d, TrieIndex root, TrieString *keybuff) |
Find first separate node in a sub-trie. More... | |
TrieIndex | da_next_separate (DArray *d, TrieIndex root, TrieIndex sep, TrieString *keybuff) |
Find next separate node in a sub-trie. More... | |
Double-array trie structure.
#define da_is_walkable | ( | d, | |
s, | |||
c | |||
) | (da_get_check ((d), da_get_base ((d), (s)) + (c)) == (s)) |
Test walkability in double-array structure.
d | : the double-array structure |
s | : current state |
c | : the input character |
Test if there is a transition from state s with input character c.
Find first separate node in a sub-trie.
d | : the double-array structure |
root | : the sub-trie root to search from |
keybuff | : the TrieString buffer for incrementally calcuating key |
Find the first separate node under a sub-trie rooted at root.
On return, keybuff is appended with the key characters which walk from root to the separate node. This is for incrementally calculating the transition key, which is more efficient than later totally reconstructing key from the given separate node.
Available since: 0.2.6
DArray* da_fread | ( | FILE * | file) |
Read double-array data from file.
file | : the file to read |
Read double-array data from the opened file, starting from the current file pointer until the end of double array data block. On return, the file pointer is left at the position after the read block.
void da_free | ( | DArray * | d) |
Free double-array data.
d | : the double-array data |
Free the given double-array data.
int da_fwrite | ( | const DArray * | d, |
FILE * | file | ||
) |
Write double-array data.
d | : the double-array data |
file | : the file to write to |
Write double-array data to the given file, starting from the current file pointer. On return, the file pointer is left after the double-array data block.
Get BASE cell.
d | : the double-array data |
s | : the double-array state to get data |
Get BASE cell value for the given state.
Get CHECK cell.
d | : the double-array data |
s | : the double-array state to get data |
Get CHECK cell value for the given state.
Get root state.
d | : the double-array data |
Get root state for stepwise walking.
Insert a branch from trie node.
d | : the double-array structure |
s | : the state to add branch to |
c | : the character for the branch label |
Insert a new arc labelled with character c from the trie node represented by index s in double-array structure d. Note that it assumes that no such arc exists before inserting.
DArray* da_new | ( | ) |
Create a new double-array object.
Create a new empty doubla-array object.
Find next separate node in a sub-trie.
d | : the double-array structure |
root | : the sub-trie root to search from |
sep | : the current separate node |
keybuff | : the TrieString buffer for incrementally calcuating key |
Find the next separate node under a sub-trie rooted at root starting from the current separate node sep.
On return, keybuff is incrementally updated from the key which walks to previous separate node to the one which walks to the new separate node. So, it is assumed to be initialized by at least one da_first_separate() call before. This incremental key calculation is more efficient than later totally reconstructing key from the given separate node.
Available since: 0.2.6
Prune the single branch.
d | : the double-array structure |
s | : the dangling state to prune off |
Prune off a non-separate path up from the final state s. If s still has some children states, it does nothing. Otherwise, it deletes the node and all its parents which become non-separate.
Prune the single branch up to given parent.
d | : the double-array structure |
p | : the parent up to which to be pruned |
s | : the dangling state to prune off |
Prune off a non-separate path up from the final state s to the given parent p. The prunning stop when either the parent p is met, or a first non-separate node is found.
Set BASE cell.
d | : the double-array data |
s | : the double-array state to get data |
val | : the value to set |
Set BASE cell for the given state to the given value.
Set CHECK cell.
d | : the double-array data |
s | : the double-array state to get data |
val | : the value to set |
Set CHECK cell for the given state to the given value.
Walk in double-array structure.
d | : the double-array structure |
s | : current state |
c | : the input character |
Walk the double-array trie from state *s, using input character c. If there exists an edge from *s with arc labeled c, this function returns TRUE and *s is updated to the new state. Otherwise, it returns FALSE and *s is left unchanged.