Other member functions¶
This page contains information about the remaining member functions of the Ukkonen
class.
-
size_t libsemigroups::Ukkonen::distance_from_root(Node const &n) const¶
Returns the distance of a node from the root.
- Complexity
At worst the distance of the node
n
from the root.
- Parameters
n – the node
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type
size_t
.
-
template<typename Iterator>
inline word_index_type libsemigroups::Ukkonen::index(Iterator first, Iterator last) const¶ See index_no_checks.
- Throws
LibsemigroupsException – if
validate_word(first, last)
throws.
-
template<typename Iterator>
word_index_type libsemigroups::Ukkonen::index_no_checks(Iterator first, Iterator last) const¶ Find the index of a word in the suffix tree.
If the word corresponding to
first
andlast
is one of the words that the suffix tree contains (the words added to the suffix tree viaadd_word
oradd_word_no_checks
, then this function returns the index of that word. If the word corresponding tofirst
andlast
is not one of the words that the suffix tree represents, then UNDEFINED is returned.- Complexity
Linear in the distance from
first
tolast
.
Warning
This function does no checks on its arguments whatsoever. In particular, if the word corresponding to
first
andlast
contains any of the unique letters appended to the end of any existing word in the tree, then bad things will happen.- Template Parameters
Iterator – the type of the arguments
- Parameters
first – iterator pointing to the first letter of the word to check
last – one beyond the last letter of the word to check
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type
word_index_type
.
-
word_index_type libsemigroups::Ukkonen::is_suffix(State const &st) const¶
Check if a state corresponds to a suffix.
This function returns a
word_index_type
if the statest
corresponds to a suffix of any word in the suffix tree. The value returned is the index of the word which the state is a suffix of.- Complexity
At worst the distance of the node
n
from the root.
- Parameters
st – the state
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type
word_index_type
.
-
inline bool libsemigroups::Ukkonen::is_unique_letter(letter_type l) const noexcept¶
Check if a letter is a unique letter added to the end of a word in the suffix tree.
Returns
true
ifl
is one of the unique letters added to the end of a word in the suffix tree.- Complexity
Constant.
- Parameters
l – the letter_type to check.
- Throws
(None) – This function is
noexcept
and is guaranteed never to throw.- Returns
A value of type
bool
.
-
size_t libsemigroups::Ukkonen::multiplicity(word_index_type i) const¶
Returns the multiplicity of a word by index.
This function returns the number of times that the word corresponding to the index
i
was added to the suffix tree.- Complexity
Constant.
- Parameters
i – the node
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type
size_t
.
-
template<typename Iterator>
inline std::pair<State, Iterator> libsemigroups::Ukkonen::traverse(Iterator first, Iterator last) const¶ See traverse_no_checks.
- Throws
LibsemigroupsException – if
validate_word(first, last)
throws.
-
template<typename Iterator>
inline Iterator libsemigroups::Ukkonen::traverse(State &st, Iterator first, Iterator last) const¶ See traverse_no_checks.
- Throws
LibsemigroupsException – if
validate_word(first, last)
throws.
-
template<typename Iterator>
inline std::pair<State, Iterator> libsemigroups::Ukkonen::traverse_no_checks(Iterator first, Iterator last) const¶ Traverse the suffix tree from the root.
This function traverses the edges in the suffix tree, starting at the root node, that are labelled by the letters in the word corresponding to
first
andlast
. The suffix tree is traversed until the end of the word is reached, or a letter not corresponding to an edge is encountered. A pair consisting of the state reached, and one past the last letter consumed in the traversal is returned.- Complexity
Linear in the distance from
first
tolast
.
Warning
This function does no checks on its arguments whatsoever. In particular, if the word corresponding to
first
andlast
contains any of the unique letters appended to the end of any existing word in the tree, then bad things will happen.- Template Parameters
Iterator – the type of the arguments.
- Parameters
first – iterator pointing to the first letter of the word.
last – one beyond the last letter of the word.
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type
std::pair<State, Iterator>
.
-
template<typename Iterator>
Iterator libsemigroups::Ukkonen::traverse_no_checks(State &st, Iterator first, Iterator last) const¶ Traverse the suffix tree from the root.
This function traverses the edges in the suffix tree, starting at the state
st
, that are labelled by the letters in the word corresponding tofirst
andlast
. The suffix tree is traversed until the end of the word is reached, or a letter not corresponding to an edge is encountered. The statest
is modified in-place to contain the last state in the tree reached in the traversal. The returned iterator points one past the last letter consumed in the traversal.- Complexity
Linear in the distance from
first
tolast
.
Warning
This function does no checks on its arguments whatsoever. In particular, if the word corresponding to
first
andlast
contains any of the unique letters appended to the end of any existing word in the tree, then bad things will happen.- Template Parameters
Iterator – the type of the 2nd and 3rd arguments.
- Parameters
st – the initial state.
first – iterator pointing to the first letter of the word.
last – one beyond the last letter of the word.
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type
Iterator
.
-
inline unique_letter_type libsemigroups::Ukkonen::unique_letter(word_index_type i) const noexcept¶
Returns the unique letter added to the end of a word in the suffix tree.
Returns the unique letter added to the end of the
i-th
distinct word added to the suffix tree.- Complexity
Constant.
- Parameters
i – the index of an added word
- Throws
(None) – This function is
noexcept
and is guaranteed never to throw.- Returns
A value of type
unique_letter_type
.
-
inline word_index_type libsemigroups::Ukkonen::word_index(Node const &n) const¶
Returns the index of the word corresponding to a node.
This function returns the least non-negative integer
i
such that the noden
corresponds to thei
-th word added to the suffix tree.- Complexity
Constant.
- Parameters
n – the node
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type
word_index_type
.
-
inline word_index_type libsemigroups::Ukkonen::word_index(index_type i) const¶
Returns the index of the word corresponding to a position.
This function returns the least non-negative integer
j
such that theUkkonen::begin() + i
points to a character in thej
-th word added to the suffix tree.- Complexity
Constant.
Warning
This function does no checks on its arguments whatsoever. In particular, if
i
is greater than length_of_words + number_of_distinct_words, then bad things will happen.- Parameters
i – the position.
- Throws
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns
A value of type
word_index_type
.