<refentry id="libstree-lst-algorithms">
<refmeta>
<refentrytitle>lst_algorithms</refentrytitle>
<manvolnum>3</manvolnum>
<refmiscinfo>LIBSTREE Library</refmiscinfo>
</refmeta>

<refnamediv>
<refname>lst_algorithms</refname><refpurpose></refpurpose>
</refnamediv>

<refsynopsisdiv><title>Synopsis</title>

<synopsis>



<link linkend="int">int</link>         (<link linkend="LST-NodeVisitCB">*LST_NodeVisitCB</link>)              (<link linkend="LST-Node">LST_Node</link> *node,
                                             <link linkend="void">void</link> *data);
<link linkend="void">void</link>        <link linkend="lst-alg-bfs">lst_alg_bfs</link>                     (<link linkend="LST-STree">LST_STree</link> *tree,
                                             <link linkend="LST-NodeVisitCB">LST_NodeVisitCB</link> callback,
                                             <link linkend="void">void</link> *data);
<link linkend="void">void</link>        <link linkend="lst-alg-dfs">lst_alg_dfs</link>                     (<link linkend="LST-STree">LST_STree</link> *tree,
                                             <link linkend="LST-NodeVisitCB">LST_NodeVisitCB</link> callback,
                                             <link linkend="void">void</link> *data);
<link linkend="void">void</link>        <link linkend="lst-alg-bus">lst_alg_bus</link>                     (<link linkend="LST-STree">LST_STree</link> *tree,
                                             <link linkend="LST-NodeVisitCB">LST_NodeVisitCB</link> callback,
                                             <link linkend="void">void</link> *data);
<link linkend="void">void</link>        <link linkend="lst-alg-leafs">lst_alg_leafs</link>                   (<link linkend="LST-STree">LST_STree</link> *tree,
                                             <link linkend="LST-NodeVisitCB">LST_NodeVisitCB</link> callback,
                                             <link linkend="void">void</link> *data);
<link linkend="u-int">u_int</link>       <link linkend="lst-alg-set-visitors">lst_alg_set_visitors</link>            (<link linkend="LST-STree">LST_STree</link> *tree);
<link linkend="LST-StringSet">LST_StringSet</link>* <link linkend="lst-alg-longest-common-substring">lst_alg_longest_common_substring</link>
                                            (<link linkend="LST-STree">LST_STree</link> *tree,
                                             <link linkend="u-int">u_int</link> min_len,
                                             <link linkend="u-int">u_int</link> max_len);
<link linkend="LST-StringSet">LST_StringSet</link>* <link linkend="lst-alg-longest-repeated-substring">lst_alg_longest_repeated_substring</link>
                                            (<link linkend="LST-STree">LST_STree</link> *tree,
                                             <link linkend="u-int">u_int</link> min_len,
                                             <link linkend="u-int">u_int</link> max_len);
</synopsis>
</refsynopsisdiv>









<refsect1>
<title>Description</title>
<para>

</para>
</refsect1>

<refsect1>
<title>Details</title>
<refsect2>
<title><anchor id="LST-NodeVisitCB">LST_NodeVisitCB ()</title>
<indexterm><primary>LST_NodeVisitCB</primary></indexterm><programlisting><link linkend="int">int</link>         (*LST_NodeVisitCB)              (<link linkend="LST-Node">LST_Node</link> *node,
                                             <link linkend="void">void</link> *data);</programlisting>
<para>
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.</para>
<para>

</para><variablelist role="params">
<varlistentry><term><parameter>node</parameter>&nbsp;:</term>
<listitem><simpara> node currently visited.
</simpara></listitem></varlistentry>
<varlistentry><term><parameter>data</parameter>&nbsp;:</term>
<listitem><simpara> arbitrary data passed through.
</simpara></listitem></varlistentry>
<varlistentry><term><emphasis>Returns</emphasis>&nbsp;:</term><listitem><simpara> value &gt; 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.
</simpara></listitem></varlistentry>
</variablelist></refsect2>
<refsect2>
<title><anchor id="lst-alg-bfs">lst_alg_bfs ()</title>
<indexterm><primary>lst_alg_bfs</primary></indexterm><programlisting><link linkend="void">void</link>        lst_alg_bfs                     (<link linkend="LST-STree">LST_STree</link> *tree,
                                             <link linkend="LST-NodeVisitCB">LST_NodeVisitCB</link> callback,
                                             <link linkend="void">void</link> *data);</programlisting>
<para>
The algorithm iterates the tree in breadth-first order, calling
<parameter>callback</parameter> for each node visited.</para>
<para>

</para><variablelist role="params">
<varlistentry><term><parameter>tree</parameter>&nbsp;:</term>
<listitem><simpara> suffix tree to iterate.
</simpara></listitem></varlistentry>
<varlistentry><term><parameter>callback</parameter>&nbsp;:</term>
<listitem><simpara> callback to call for each node.
</simpara></listitem></varlistentry>
<varlistentry><term><parameter>data</parameter>&nbsp;:</term>
<listitem><simpara> user data passed through to callback.
</simpara></listitem></varlistentry>
</variablelist></refsect2>
<refsect2>
<title><anchor id="lst-alg-dfs">lst_alg_dfs ()</title>
<indexterm><primary>lst_alg_dfs</primary></indexterm><programlisting><link linkend="void">void</link>        lst_alg_dfs                     (<link linkend="LST-STree">LST_STree</link> *tree,
                                             <link linkend="LST-NodeVisitCB">LST_NodeVisitCB</link> callback,
                                             <link linkend="void">void</link> *data);</programlisting>
<para>
The algorithm iterates the tree in depth-first order, calling
<parameter>callback</parameter> for each node visited.</para>
<para>

</para><variablelist role="params">
<varlistentry><term><parameter>tree</parameter>&nbsp;:</term>
<listitem><simpara> suffix tree to iterate.
</simpara></listitem></varlistentry>
<varlistentry><term><parameter>callback</parameter>&nbsp;:</term>
<listitem><simpara> callback to call for each node.
</simpara></listitem></varlistentry>
<varlistentry><term><parameter>data</parameter>&nbsp;:</term>
<listitem><simpara> user data passed through to callback.
</simpara></listitem></varlistentry>
</variablelist></refsect2>
<refsect2>
<title><anchor id="lst-alg-bus">lst_alg_bus ()</title>
<indexterm><primary>lst_alg_bus</primary></indexterm><programlisting><link linkend="void">void</link>        lst_alg_bus                     (<link linkend="LST-STree">LST_STree</link> *tree,
                                             <link linkend="LST-NodeVisitCB">LST_NodeVisitCB</link> callback,
                                             <link linkend="void">void</link> *data);</programlisting>
<para>
The algorithm iterates the tree in bottom-up order, calling <parameter>callback</parameter>
for each node visited. This algorithm ignores the return value
of <parameter>callback</parameter>.</para>
<para>

</para><variablelist role="params">
<varlistentry><term><parameter>tree</parameter>&nbsp;:</term>
<listitem><simpara> suffix tree to iterate.
</simpara></listitem></varlistentry>
<varlistentry><term><parameter>callback</parameter>&nbsp;:</term>
<listitem><simpara> callback to call for each node.
</simpara></listitem></varlistentry>
<varlistentry><term><parameter>data</parameter>&nbsp;:</term>
<listitem><simpara> user data passed through to callback.
</simpara></listitem></varlistentry>
</variablelist></refsect2>
<refsect2>
<title><anchor id="lst-alg-leafs">lst_alg_leafs ()</title>
<indexterm><primary>lst_alg_leafs</primary></indexterm><programlisting><link linkend="void">void</link>        lst_alg_leafs                   (<link linkend="LST-STree">LST_STree</link> *tree,
                                             <link linkend="LST-NodeVisitCB">LST_NodeVisitCB</link> callback,
                                             <link linkend="void">void</link> *data);</programlisting>
<para>
The algorithm iterates over all leafs in the tree, calling <parameter>callback</parameter>
for each node visited. If <parameter>callback</parameter> returns 0, it stops.</para>
<para>

</para><variablelist role="params">
<varlistentry><term><parameter>tree</parameter>&nbsp;:</term>
<listitem><simpara> suffix tree to visit.
</simpara></listitem></varlistentry>
<varlistentry><term><parameter>callback</parameter>&nbsp;:</term>
<listitem><simpara> callback to call for each node.
</simpara></listitem></varlistentry>
<varlistentry><term><parameter>data</parameter>&nbsp;:</term>
<listitem><simpara> user data passed through to callback.
</simpara></listitem></varlistentry>
</variablelist></refsect2>
<refsect2>
<title><anchor id="lst-alg-set-visitors">lst_alg_set_visitors ()</title>
<indexterm><primary>lst_alg_set_visitors</primary></indexterm><programlisting><link linkend="u-int">u_int</link>       lst_alg_set_visitors            (<link linkend="LST-STree">LST_STree</link> *tree);</programlisting>
<para>
The algorithm updates the visitor elements in each node of <parameter>tree</parameter>
to contain a one-bit for each string index that is contained
in the tree.</para>
<para>

</para><variablelist role="params">
<varlistentry><term><parameter>tree</parameter>&nbsp;:</term>
<listitem><simpara> tree to update.
</simpara></listitem></varlistentry>
<varlistentry><term><emphasis>Returns</emphasis>&nbsp;:</term><listitem><simpara> bitstring representing a node visited by all strings.
</simpara></listitem></varlistentry>
</variablelist></refsect2>
<refsect2>
<title><anchor id="lst-alg-longest-common-substring">lst_alg_longest_common_substring ()</title>
<indexterm><primary>lst_alg_longest_common_substring</primary></indexterm><programlisting><link linkend="LST-StringSet">LST_StringSet</link>* lst_alg_longest_common_substring
                                            (<link linkend="LST-STree">LST_STree</link> *tree,
                                             <link linkend="u-int">u_int</link> min_len,
                                             <link linkend="u-int">u_int</link> max_len);</programlisting>
<para>
The algorithm computes the longest common substring(s) in <parameter>tree</parameter>
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 <parameter>max_len</parameter>, 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
<parameter>min_len</parameter> for that, or pass 0 to indicate interest in everything.</para>
<para>

</para><variablelist role="params">
<varlistentry><term><parameter>tree</parameter>&nbsp;:</term>
<listitem><simpara> tree to use in computation.
</simpara></listitem></varlistentry>
<varlistentry><term><parameter>min_len</parameter>&nbsp;:</term>
<listitem><simpara> minimum length that common substrings must have to be returned.
</simpara></listitem></varlistentry>
<varlistentry><term><parameter>max_len</parameter>&nbsp;:</term>
<listitem><simpara> don't return strings longer than <parameter>max_len</parameter> items.
</simpara></listitem></varlistentry>
<varlistentry><term><emphasis>Returns</emphasis>&nbsp;:</term><listitem><simpara> new string set, or <literal>NULL</literal> when no strings were found.
</simpara></listitem></varlistentry>
</variablelist></refsect2>
<refsect2>
<title><anchor id="lst-alg-longest-repeated-substring">lst_alg_longest_repeated_substring ()</title>
<indexterm><primary>lst_alg_longest_repeated_substring</primary></indexterm><programlisting><link linkend="LST-StringSet">LST_StringSet</link>* lst_alg_longest_repeated_substring
                                            (<link linkend="LST-STree">LST_STree</link> *tree,
                                             <link linkend="u-int">u_int</link> min_len,
                                             <link linkend="u-int">u_int</link> max_len);</programlisting>
<para>
The algorithm computes the longest repeated substring(s) in <parameter>tree</parameter>
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 <parameter>max_len</parameter>, 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
<parameter>min_len</parameter> for that, or pass 0 to indicate interest in everything.</para>
<para>

</para><variablelist role="params">
<varlistentry><term><parameter>tree</parameter>&nbsp;:</term>
<listitem><simpara> tree to use in computation.
</simpara></listitem></varlistentry>
<varlistentry><term><parameter>min_len</parameter>&nbsp;:</term>
<listitem><simpara> minimum length that repeated substrings must have to be returned.
</simpara></listitem></varlistentry>
<varlistentry><term><parameter>max_len</parameter>&nbsp;:</term>
<listitem><simpara> don't return strings longer than <parameter>max_len</parameter> items.
</simpara></listitem></varlistentry>
<varlistentry><term><emphasis>Returns</emphasis>&nbsp;:</term><listitem><simpara> new string set, or <literal>NULL</literal> when no strings were found.
</simpara></listitem></varlistentry>
</variablelist></refsect2>

</refsect1>




</refentry>
