operations_research::MonoidOperationTree< T > Class Template Reference

#include <monoid_operation_tree.h>

Public Member Functions
	MonoidOperationTree (int size)
	Constructs a MonoidOperationTree able to store 'size' operands.
	MonoidOperationTree (const MonoidOperationTree &)=delete
	This type is neither copyable nor movable.
MonoidOperationTree &	operator= (const MonoidOperationTree &)=delete
const T &	result () const
	Returns the root of the tree, containing the result of the operation.
void	Reset (int argument_index)
	Resets the argument of given index.
void	Set (int argument_index, const T &argument)
	Sets the argument of given index.
void	Clear ()
	Resets all arguments.
const T &	GetOperand (int argument_index) const
	Returns the leaf node corresponding to the given argument index.
template<class Diver >
void	DiveInTree (Diver *const diver) const
	Dive down a branch of the operation tree, and then come back up.
std::string	DebugString () const

Detailed Description

template<class T>
class operations_research::MonoidOperationTree< T >

A monoid is an algebraic structure consisting of a set S with an associative binary operation * :S x S -> S that has an identity element. Associative means a*(b*c) = (a*b)*c for all a,b,c in S. An identity element is an element e in S such that for all a in S, e*a = a*e = a. See http://en.wikipedia.org/wiki/Monoid for more details.

A MonoidOperationTree is a data structure that maintains a product a_1 * a_2 * ... * a_n for a given (fixed) n, and that supports the following functions:

• Setting the k-th operand to a given value in O(log n) calls to the * operation
• Querying the result in O(1)

Note

the monoid is not required to be commutative.

The parameter class T represents an element of the set S. It must:

• Have a public no-argument constructor producing the identity element.
• Have a = operator method that sets its value to the given one.
• Have a Compute(const T& left, const T& right) method that sets its value to the result of the binary operation for the two given operands.
• Have a string DebugString() const method.

Possible use cases are:

• Maintain a sum or a product of doubles, with a guarantee that the queried result is independent of the order of past numerical issues
• Maintain a product of identically sized square matrices, which is an example of use with non-commutative operations.

Definition at line 56 of file monoid_operation_tree.h.

Constructor & Destructor Documentation

MonoidOperationTree() [1/2]

template<class T >

operations_research::MonoidOperationTree< T >::MonoidOperationTree ( int size )

explicit

Constructs a MonoidOperationTree able to store 'size' operands.

Definition at line 165 of file monoid_operation_tree.h.

MonoidOperationTree() [2/2]

template<class T >

operations_research::MonoidOperationTree< T >::MonoidOperationTree ( const MonoidOperationTree< T > & )

delete

This type is neither copyable nor movable.

Member Function Documentation

Clear()

template<class T >

void operations_research::MonoidOperationTree< T >::Clear

(

)

Resets all arguments.

Definition at line 173 of file monoid_operation_tree.h.

DebugString()

template<class T >

std::string operations_research::MonoidOperationTree< T >::DebugString

(

)

const

New layer

Definition at line 209 of file monoid_operation_tree.h.

DiveInTree()

template<class T >

template<class Diver >

void operations_research::MonoidOperationTree< T >::DiveInTree ( Diver *const diver ) const

inline

Dive down a branch of the operation tree, and then come back up.

Definition at line 84 of file monoid_operation_tree.h.

GetOperand()

template<class T >

const T & operations_research::MonoidOperationTree< T >::GetOperand ( int argument_index ) const

inline

Returns the leaf node corresponding to the given argument index.

Definition at line 78 of file monoid_operation_tree.h.

operator=()

template<class T >

MonoidOperationTree & operations_research::MonoidOperationTree< T >::operator= ( const MonoidOperationTree< T > & )

delete

Reset()

template<class T >

void operations_research::MonoidOperationTree< T >::Reset

(

int

argument_index

)

Resets the argument of given index.

Definition at line 179 of file monoid_operation_tree.h.

result()

template<class T >

const T & operations_research::MonoidOperationTree< T >::result ( ) const

inline

Returns the root of the tree, containing the result of the operation.

Definition at line 66 of file monoid_operation_tree.h.

Set()

template<class T >

void operations_research::MonoidOperationTree< T >::Set	(	int	argument_index,
		const T &	argument )

Sets the argument of given index.

Definition at line 184 of file monoid_operation_tree.h.

---

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

• ortools/util/monoid_operation_tree.h