lst_algorithms

libstree Manual
Prev		Next

Details

LST_NodeVisitCB ()

int         (*LST_NodeVisitCB)              (LST_Node *node,
                                             void *data);

This is the signature of the callbacks used in several of the algorithms below, that iterate over the tree. They call a callback of this signature for every node they visit.

node :: node currently visited.
data :: arbitrary data passed through.
Returns :: value > 0 if the iteration algorithm that called this node is to proceed beyond this node, or 0 if not. Note that this does not necessarily mean that an algorithm will abort when the return value is 0.

lst_alg_bfs ()

void        lst_alg_bfs                     (LST_STree *tree,
                                             LST_NodeVisitCB callback,
                                             void *data);

The algorithm iterates the tree in breadth-first order, calling callback for each node visited.

tree :: suffix tree to iterate.
callback :: callback to call for each node.
data :: user data passed through to callback.

lst_alg_dfs ()

void        lst_alg_dfs                     (LST_STree *tree,
                                             LST_NodeVisitCB callback,
                                             void *data);

The algorithm iterates the tree in depth-first order, calling callback for each node visited.

tree :: suffix tree to iterate.
callback :: callback to call for each node.
data :: user data passed through to callback.

lst_alg_bus ()

void        lst_alg_bus                     (LST_STree *tree,
                                             LST_NodeVisitCB callback,
                                             void *data);

The algorithm iterates the tree in bottom-up order, calling callback for each node visited. This algorithm ignores the return value of callback.

tree :: suffix tree to iterate.
callback :: callback to call for each node.
data :: user data passed through to callback.

lst_alg_leafs ()

void        lst_alg_leafs                   (LST_STree *tree,
                                             LST_NodeVisitCB callback,
                                             void *data);

The algorithm iterates over all leafs in the tree, calling callback for each node visited. If callback returns 0, it stops.

tree :: suffix tree to visit.
callback :: callback to call for each node.
data :: user data passed through to callback.

lst_alg_set_visitors ()

u_int       lst_alg_set_visitors            (LST_STree *tree);

The algorithm updates the visitor elements in each node of tree to contain a one-bit for each string index that is contained in the tree.

tree :: tree to update.
Returns :: bitstring representing a node visited by all strings.

lst_alg_longest_common_substring ()

LST_StringSet* lst_alg_longest_common_substring
                                            (LST_STree *tree,
                                             u_int min_len,
                                             u_int max_len);

The algorithm computes the longest common substring(s) in tree and returns them as a new string set. This is currently a suboptimal O(n^2) implementation until I have time for the more sophisticated O(n) implementation available. If you want to limit the string length, pass an appropriate value for max_len, or pass 0 if you want the longest string(s) possible. Similarly, if you want to receive only longest common substrings of at least a certain number of items, use min_len for that, or pass 0 to indicate interest in everything.

tree :: tree to use in computation.
min_len :: minimum length that common substrings must have to be returned.
max_len :: don't return strings longer than max_len items.
Returns :: new string set, or NULL when no strings were found.

lst_alg_longest_repeated_substring ()

LST_StringSet* lst_alg_longest_repeated_substring
                                            (LST_STree *tree,
                                             u_int min_len,
                                             u_int max_len);

The algorithm computes the longest repeated substring(s) in tree and returns them as a new string set. This is currently a suboptimal O(n^2) implementation until I have time for the more sophisticated O(n) implementation available. If you want to limit the string length, pass an appropriate value for max_len, or pass 0 if you want the longest string(s) possible. Similarly, if you want to receive only longest repeated substrings of at least a certain number of items, use min_len for that, or pass 0 to indicate interest in everything.

tree :: tree to use in computation.
min_len :: minimum length that repeated substrings must have to be returned.
max_len :: don't return strings longer than max_len items.
Returns :: new string set, or NULL when no strings were found.

Prev	Home	Next
libstree API Reference	Up	lst_stree