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 and last is one of the words that the suffix tree contains (the words added to the suffix tree via add_word or add_word_no_checks, then this function returns the index of that word. If the word corresponding to first and last is not one of the words that the suffix tree represents, then UNDEFINED is returned.

Complexity: Linear in the distance from first to last.

Warning

This function does no checks on its arguments whatsoever. In particular, if the word corresponding to first and last 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 state st 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 if l 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 and last. 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 to last.

Warning

This function does no checks on its arguments whatsoever. In particular, if the word corresponding to first and last 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 to first and last. The suffix tree is traversed until the end of the word is reached, or a letter not corresponding to an edge is encountered. The state st 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 to last.

Warning

This function does no checks on its arguments whatsoever. In particular, if the word corresponding to first and last 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 node n corresponds to the i-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 the Ukkonen::begin() + i points to a character in the j-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.