operations_research::MonoidOperationTree< T > Class Template Reference

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. More...

#include <monoid_operation_tree.h>

List of all members.

Public Member Functions
	MonoidOperationTree (int size)
	Constructs a MonoidOperationTree able to store 'size' operands.
virtual	~MonoidOperationTree ()
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 *diver) const
	Dive down a branch of the operation tree, and then come back up.
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 that 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 Set(const T& value) 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 57 of file monoid_operation_tree.h.

---

Constructor & Destructor Documentation

template<class T>

operations_research::MonoidOperationTree< T >::MonoidOperationTree

(

int

size

)

[inline, explicit]

Constructs a MonoidOperationTree able to store 'size' operands.

Definition at line 168 of file monoid_operation_tree.h.

template<class T>

virtual operations_research::MonoidOperationTree< T >::~MonoidOperationTree

(

)

[inline, virtual]

Definition at line 61 of file monoid_operation_tree.h.

---

Member Function Documentation

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 64 of file monoid_operation_tree.h.

template<class T>

void operations_research::MonoidOperationTree< T >::Reset

(

int

argument_index

)

[inline]

Resets the argument of given index.

Definition at line 192 of file monoid_operation_tree.h.

template<class T>

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

Sets the argument of given index.

Definition at line 197 of file monoid_operation_tree.h.

template<class T>

void operations_research::MonoidOperationTree< T >::Clear

(

)

[inline]

Resets all arguments.

Definition at line 183 of file monoid_operation_tree.h.

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 76 of file monoid_operation_tree.h.

template<class T>

template<class Diver>

void operations_research::MonoidOperationTree< T >::DiveInTree

(

Diver *

diver

)

const [inline]

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

Definition at line 82 of file monoid_operation_tree.h.

template<class T>

string operations_research::MonoidOperationTree< T >::DebugString

(

)

const [inline]

Definition at line 222 of file monoid_operation_tree.h.

---

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

• or-tools/src/util/monoid_operation_tree.h