PathsToRoots

Defined in forest.hpp.

This class represents a range object that facilitates iterating through the paths from every node to the root of its subtree in a Forest object. These nodes are taken in numerical order, so the first value returned by get is the word to a root from node 0, after next is called, get returns the word to a root from node 1, and so on.

The point of this class is to permit more efficient iteration over many paths in a Forest object than path_to_root_no_checks (and its associated helper functions). path_to_root_no_checks traverses the Forest from the given node to the root of its tree. If the path from nodes m and n to the root of their tree share a long common suffix, then this suffix will be traversed twice in two calls to path_to_root_no_checks. PathsToRoots avoids this by finding the least common ancestor of m and n, so that the suffix is not re-traversed. This works best when the nodes in the Forest are specified in a sensible order (such as via a depth-first or breadth-first traversal).

So that the PathsToRoots class can be used efficiently with the functionality of rx::ranges, the usual naming conventions in libsemigroups are not used for the member functions:

• get
• next
• at_end
• size_hint
• count

of PathsToRoots. In particular, none of these member functions check their arguments, but they do not have the suffix _no_checks.

Public Types
using	node_type = Forest::node_type
	The type of nodes in the underlying Forest.
using	output_type = word_type const&
	The type of the output of a PathsToRoots object.
using	size_type = typename std::vector<word_type>::size_type
	Alias for the size type.

Static Public Attributes
static constexpr bool	is_finite = true
	Value indicating that the range is finite.
static constexpr bool	is_idempotent = true

Public Member Functions
bool	at_end () const noexcept
	Check if the range is exhausted.
auto	begin () noexcept
	Returns an input iterator pointing to the first word in the range.
size_type	count () const noexcept
	Get the size of the range.
auto	end () noexcept
	Returns an input iterator pointing one beyond the last word in the range.
Forest const &	forest () const noexcept
	Returns the underlying Forest object.
output_type	get () const noexcept
	Returns a reference to the current path.
PathsToRoots &	init (Forest const &f)
	Re-initialize from a Forest.
void	next ()
	Advance to the next path in the range.
	PathsToRoots ()=delete
	Deleted.
	PathsToRoots (Forest const &f)
	Construct from a Forest.
	PathsToRoots (PathsToRoots &&)=default
	Default move constructor.
	PathsToRoots (PathsToRoots const &)=default
	Default copy constructor.
size_type	size_hint () const noexcept
	Get the size of the range.
PathsToRoots &	skip_n (size_type n)
	Skip a number of paths in the range.
node_type	target () const noexcept
	Get the current target of the path.
Public Member Functions inherited from PathsToRoots
	PathsToRoots ()=delete
	Deleted.
	PathsToRoots (Forest const &f)
	Construct from a Forest.
	PathsToRoots (PathsToRoots &&)=default
	Default move constructor.
	PathsToRoots (PathsToRoots const &)=default
	Default copy constructor.
bool	at_end () const noexcept
	Check if the range is exhausted.
size_type	count () const noexcept
	Get the size of the range.
Forest const &	forest () const noexcept
	Returns the underlying Forest object.
output_type	get () const noexcept
	Returns a reference to the current path.
PathsToRoots &	init (Forest const &f)
	Re-initialize from a Forest.
PathsToRoots &	operator= (PathsToRoots &&)=default
	Default move assignment operator.
PathsToRoots &	operator= (PathsToRoots const &)=default
	Default copy assignment operator.
size_type	size_hint () const noexcept
	Get the size of the range.
node_type	target () const noexcept
	Get the current target of the path.

Member Function Documentation

at_end()

bool at_end ( ) const

inlinenodiscardnoexcept

This function returns true if there are no more paths in the range, and false otherwise.

Returns

Whether or not the range is exhausted.

begin()

auto begin ( )

inlinenodiscardnoexcept

This function returns an input iterator pointing to the first word in a PathsToRoots object.

Returns

An input iterator.

Exceptions

This function is noexcept and is guaranteed never to throw.

Note

The return type of end might be different from the return type of begin.

Warning

If using a PathsToRoots object paths in a range-based for-loop such as:

for (auto const& path : paths) {
  ...
}

the object paths is copied, and so will be constant inside the for-loop. For example, in

for (auto const& path : paths) {
  auto t = paths.target();
}

The value of t will be constant, even though the value of path may change.

See also

end.

count()

size_type count ( ) const

inlinenodiscardnoexcept

This function returns the number of paths in the range.

Returns

the number of paths in the range.

end()

auto end ( )

inlinenodiscardnoexcept

This function returns an input iterator pointing one beyond the last word in a PathsToRoots object.

Returns

An input iterator.

Exceptions

This function is noexcept and is guaranteed never to throw.

Note

The return type of end might be different from the return type of begin.

Warning

Please read the warning in begin.

See also

begin.

forest()

Forest const & forest ( ) const

inlinenodiscardnoexcept

This function returns the Forest object used to constructor or initialise a PathsToRoots object.

Returns

A const reference to a Forest object.

Exceptions

This function is noexcept and is guaranteed never to throw.

get()

output_type get ( ) const

inlinenodiscardnoexcept

This function returns a const reference to the current path from the root of the tree containing target to target.

Returns

A const reference to the current path.

Exceptions

This function is noexcept and is guaranteed never to throw.

init()

PathsToRoots & init

(

Forest const &

f

)

This function re-initializes a PathsToRoots so that its underlying Forest object is f. This puts the PathsToRoots object back into the same state it would have been in if it had been newly constructed from f.

Parameters

f	the Forest.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

next()

void next

(

)

This function advances to the current path in the range. If at_end returns true, then this function does nothing.

PathsToRoots() [1/2]

PathsToRoots ( )

delete

A Forest object is required to construct or initialise a PathsToRoots object.

PathsToRoots() [2/2]

PathsToRoots ( Forest const & f )

explicit

This function constructs a new PathsToRoots for the Forest f. The newly constructed object does not copy f and is not valid if f is destroyed.

Parameters

f	the Forest.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

size_hint()

size_type size_hint ( ) const

inlinenodiscardnoexcept

This function returns the number of paths in the range. The output is identical to that of count, and is included for compatibility with rx::ranges.

Returns

the number of paths in the range.

skip_n()

PathsToRoots & skip_n

(

size_type

n

)

This function skips n paths in the range. If n is 1, then this is the same as calling next. If n is 0, then this function does nothing.

Parameters

n	the number of paths to skip.

Returns

A reference to *this.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

target()

node_type target ( ) const

inlinenodiscardnoexcept

This function returns the current target of the path returned by get.

Returns

The target of the current path.

Exceptions

This function is noexcept and is guaranteed never to throw.

Member Data Documentation

is_idempotent

bool is_idempotent = true

staticconstexpr

Value indicating that if get() is called twice on a PathsToRoots object that is not changed between the two calls, then the return value of get() is the same both times.

---

The documentation for this class was generated from the following file:

• /Users/jdm3/libsemigroups/include/libsemigroups/forest.hpp