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.