Words in lexicographic order (wilo)

The functions libsemigroups::cbegin_wilo() and libsemigroups::cend_wilo() can be used to iterate through words in lexicographic order in some range.

const_wilo_iterator libsemigroups::cbegin_wilo(size_t n, size_t upper_bound, word_type &&first, word_type &&last)

Returns a forward iterator pointing to the 3rd parameter first.

If incremented, the iterator will point to the next least lexicographic word after w over an n letter alphabet with length less than upper_bound. Iterators of the type returned by this function are equal whenever they are obtained by advancing the return value of any call to cbegin_wilo by the same amount, or they are both obtained by any call to cend_wilo.

See also

cend_wilo

Example
std::vector<word_type>(cbegin_wilo(2, 3, {0}, {1, 1, 1}),
                       cend_wilo(2, 3, {0}, {1, 1, 1}));
// {{0}, {0, 0}, {0, 1}, {1}, {1, 0}, {1, 1}};

Note

The parameter upper_bound is required because lexicographical ordering is not a well-ordering, and there might be infinitely many words between a given pair of words.

Warning

Copying iterators of this type is expensive. As a consequence, prefix incrementing ++it the iterator it returned by cbegin_wilo is significantly cheaper than postfix incrementing it++.

Warning

Iterators constructed using different parameters may not be equal, so best not to loop over them.

Parameters:

  • n – the number of letters in the alphabet;

  • upper_bound – only words of length less than this value are considered;

  • first – the starting point for the iteration;

  • last – the value one past the end of the last value in the iteration.

Throws:

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns:

An iterator of type const_wilo_iterator.

const_wilo_iterator libsemigroups::cend_wilo(size_t n, size_t upper_bound, word_type &&first, word_type &&last)

Returns a forward iterator pointing to one after the end of the range from first to last.

The iterator returned by this function is still dereferenceable and incrementable, but does not point to a word in the correct range.

See also

cbegin_wilo

const_wilo_iterator libsemigroups::cbegin_wilo(size_t n, size_t upper_bound, word_type const &first, word_type const &last)

Returns a forward iterator pointing to the 3rd parameter first.

If incremented, the iterator will point to the next least lexicographic word after w over an n letter alphabet with length less than upper_bound. Iterators of the type returned by this function are equal whenever they are obtained by advancing the return value of any call to cbegin_wilo by the same amount, or they are both obtained by any call to cend_wilo.

See also

cend_wilo

Example
std::vector<word_type>(cbegin_wilo(2, 3, {0}, {1, 1, 1}),
                       cend_wilo(2, 3, {0}, {1, 1, 1}));
// {{0}, {0, 0}, {0, 1}, {1}, {1, 0}, {1, 1}};

Note

The parameter upper_bound is required because lexicographical ordering is not a well-ordering, and there might be infinitely many words between a given pair of words.

Warning

Copying iterators of this type is expensive. As a consequence, prefix incrementing ++it the iterator it returned by cbegin_wilo is significantly cheaper than postfix incrementing it++.

Warning

Iterators constructed using different parameters may not be equal, so best not to loop over them.

Parameters:

  • n – the number of letters in the alphabet;

  • upper_bound – only words of length less than this value are considered;

  • first – the starting point for the iteration;

  • last – the value one past the end of the last value in the iteration.

Throws:

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns:

An iterator of type const_wilo_iterator.

const_wilo_iterator libsemigroups::cend_wilo(size_t n, size_t upper_bound, word_type const &first, word_type const &last)

Returns a forward iterator pointing to one after the end of the range from first to last.

The iterator returned by this function is still dereferenceable and incrementable, but does not point to a word in the correct range.

See also

cbegin_wilo