#include <theta_tree.h>

Public Member Functions
	ThetaLambdaTree ()
	Builds a reusable tree. Initialization is done with Reset().

void	Reset (int num_events)

void	RecomputeTreeForDelayedOperations ()

void	AddOrUpdateEvent (int event, IntegerType initial_envelope, IntegerType energy_min, IntegerType energy_max)

void	DelayedAddOrUpdateEvent (int event, IntegerType initial_envelope, IntegerType energy_min, IntegerType energy_max)

void	AddOrUpdateOptionalEvent (int event, IntegerType initial_envelope_opt, IntegerType energy_max)

void	DelayedAddOrUpdateOptionalEvent (int event, IntegerType initial_envelope_opt, IntegerType energy_max)

void	RemoveEvent (int event)
	Makes event absent, compute the new envelope in O(log n).

void	DelayedRemoveEvent (int event)
	Delayed version of RemoveEvent(), see RecomputeTreeForDelayedOperations().

IntegerType	GetEnvelope () const

IntegerType	GetOptionalEnvelope () const

int	GetMaxEventWithEnvelopeGreaterThan (IntegerType target_envelope) const

IntegerType	GetEnvelopeOf (int event) const

void	GetEventsWithOptionalEnvelopeGreaterThan (IntegerType target_envelope, int critical_event, int optional_event, IntegerType *available_energy) const

IntegerType	EnergyMin (int event) const
	Getters.

Detailed Description

template<typename IntegerType>
class operations_research::sat::ThetaLambdaTree< IntegerType >

Definition at line 104 of file theta_tree.h.

Constructor & Destructor Documentation

◆ ThetaLambdaTree()

template<typename IntegerType >

operations_research::sat::ThetaLambdaTree< IntegerType >::ThetaLambdaTree ( )

default

Builds a reusable tree. Initialization is done with Reset().

Member Function Documentation

◆ AddOrUpdateEvent()

template<typename IntegerType >

void operations_research::sat::ThetaLambdaTree< IntegerType >::AddOrUpdateEvent	(	int	event,
		IntegerType	initial_envelope,
		IntegerType	energy_min,
		IntegerType	energy_max )

Makes event present and updates its initial envelope and min/max energies. The initial_envelope must be >= ThetaLambdaTreeNegativeInfinity(). This updates the tree in O(log n).

Definition at line 113 of file theta_tree.cc.

◆ AddOrUpdateOptionalEvent()

template<typename IntegerType >

void operations_research::sat::ThetaLambdaTree< IntegerType >::AddOrUpdateOptionalEvent	(	int	event,
		IntegerType	initial_envelope_opt,
		IntegerType	energy_max )

Adds event to the lambda part of the tree only. This will leave GetEnvelope() unchanged, only GetOptionalEnvelope() can be affected. This is done by setting envelope to IntegerTypeMinimumValue(), energy_min to 0, and initial_envelope_opt and energy_max to the parameters. This updates the tree in O(log n).

Definition at line 126 of file theta_tree.cc.

◆ DelayedAddOrUpdateEvent()

template<typename IntegerType >

void operations_research::sat::ThetaLambdaTree< IntegerType >::DelayedAddOrUpdateEvent	(	int	event,
		IntegerType	initial_envelope,
		IntegerType	energy_min,
		IntegerType	energy_max )

Delayed version of AddOrUpdateEvent(), see RecomputeTreeForDelayedOperations().

Definition at line 99 of file theta_tree.cc.

◆ DelayedAddOrUpdateOptionalEvent()

template<typename IntegerType >

void operations_research::sat::ThetaLambdaTree< IntegerType >::DelayedAddOrUpdateOptionalEvent	(	int	event,
		IntegerType	initial_envelope_opt,
		IntegerType	energy_max )

Delayed version of AddOrUpdateOptionalEvent(), see RecomputeTreeForDelayedOperations().

Definition at line 137 of file theta_tree.cc.

◆ DelayedRemoveEvent()

template<typename IntegerType >

void operations_research::sat::ThetaLambdaTree< IntegerType >::DelayedRemoveEvent ( int event )

Delayed version of RemoveEvent(), see RecomputeTreeForDelayedOperations().

Definition at line 159 of file theta_tree.cc.

◆ EnergyMin()

template<typename IntegerType >

IntegerType operations_research::sat::ThetaLambdaTree< IntegerType >::EnergyMin ( int event ) const

inline

Getters.

Definition at line 198 of file theta_tree.h.

◆ GetEnvelope()

template<typename IntegerType >

IntegerType operations_research::sat::ThetaLambdaTree< IntegerType >::GetEnvelope ( ) const

Returns the maximum envelope using all the energy_min in O(1). If theta is empty, returns ThetaLambdaTreeNegativeInfinity().

Definition at line 170 of file theta_tree.cc.

◆ GetEnvelopeOf()

template<typename IntegerType >

IntegerType operations_research::sat::ThetaLambdaTree< IntegerType >::GetEnvelopeOf ( int event ) const

Returns initial_envelope(event) + sum_{event' >= event} energy_min(event'), in time O(log n).

Definition at line 204 of file theta_tree.cc.

◆ GetEventsWithOptionalEnvelopeGreaterThan()

template<typename IntegerType >

void operations_research::sat::ThetaLambdaTree< IntegerType >::GetEventsWithOptionalEnvelopeGreaterThan	(	IntegerType	target_envelope,
		int *	critical_event,
		int *	optional_event,
		IntegerType *	available_energy ) const

Computes a pair of events (critical_event, optional_event) such that if optional_event was at its maximum energy, the envelope of critical_event would be greater than target_envelope.

This assumes that such a pair exists, i.e. GetOptionalEnvelope() should be greater than target_envelope. More formally, this finds events such that: initial_envelope(critical_event) + sum_{event' >= critical_event} energy_min(event') + max_{optional_event >= critical_event} energy_delta(optional_event) > target envelope.

For efficiency reasons, this also fills available_energy with the maximum energy the optional task can take such that the optional envelope of the pair would be target_envelope, i.e. target_envelope - GetEnvelopeOf(event) + energy_min(optional_event).

This operation is O(log n).

Definition at line 191 of file theta_tree.cc.

◆ GetMaxEventWithEnvelopeGreaterThan()

template<typename IntegerType >

int operations_research::sat::ThetaLambdaTree< IntegerType >::GetMaxEventWithEnvelopeGreaterThan ( IntegerType target_envelope ) const

Computes the maximum event s.t. GetEnvelopeOf(event) > envelope_max. There must be such an event, i.e. GetEnvelope() > envelope_max. This finds the maximum event e such that initial_envelope(e) + sum_{e' >= e} energy_min(e') > target_envelope. This operation is O(log n).

Definition at line 181 of file theta_tree.cc.

◆ GetOptionalEnvelope()

template<typename IntegerType >

IntegerType operations_research::sat::ThetaLambdaTree< IntegerType >::GetOptionalEnvelope ( ) const

Returns the maximum envelope using the energy min of all task but one and the energy max of the last one in O(1). If theta and lambda are empty, returns ThetaLambdaTreeNegativeInfinity().

Definition at line 175 of file theta_tree.cc.

◆ RecomputeTreeForDelayedOperations()

template<typename IntegerType >

void operations_research::sat::ThetaLambdaTree< IntegerType >::RecomputeTreeForDelayedOperations ( )

Recomputes the values of internal nodes of the tree from the values in the leaves. We enable batching modifications to the tree by providing DelayedXXX() methods that run in O(1), but those methods do not update internal nodes. This breaks tree invariants, so that GetXXX() methods will not reflect modifications made to events. RecomputeTreeForDelayedOperations() restores those invariants in O(n). Thus, batching operations can be done by first doing calls to DelayedXXX() methods, then calling RecomputeTreeForDelayedOperations() once.

Only recompute internal nodes.

Definition at line 85 of file theta_tree.cc.

◆ RemoveEvent()

template<typename IntegerType >

void operations_research::sat::ThetaLambdaTree< IntegerType >::RemoveEvent ( int event )

Makes event absent, compute the new envelope in O(log n).

Definition at line 149 of file theta_tree.cc.

◆ Reset()

template<typename IntegerType >

void operations_research::sat::ThetaLambdaTree< IntegerType >::Reset ( int num_events )

Initializes this class for events in [0, num_events) and makes all of them absent. Instead of allocating and de-allocating trees at every usage, i.e. at every Propagate() of the scheduling algorithms that uses it, this class allows to keep the same memory for each call.

Because the algorithm needs to access a node sibling (i.e. node_index ^ 1), our tree will always have an even number of leaves, just large enough to fit our number of events. And at least 2 for the empty tree case.

If num_leaves is not a power or two, the last depth of the tree will not be full, and the array will look like: [( num_leafs parents)(leaves at depth d - 1)(leaves at depth d) The first leaves at depth p will have power_of_two_ as index.

Definition at line 42 of file theta_tree.cc.

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

ortools/sat/theta_tree.h
ortools/sat/theta_tree.cc

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ ThetaLambdaTree()

Member Function Documentation

◆ AddOrUpdateEvent()

◆ AddOrUpdateOptionalEvent()

◆ DelayedAddOrUpdateEvent()

◆ DelayedAddOrUpdateOptionalEvent()

◆ DelayedRemoveEvent()

◆ EnergyMin()

◆ GetEnvelope()

◆ GetEnvelopeOf()

◆ GetEventsWithOptionalEnvelopeGreaterThan()

◆ GetMaxEventWithEnvelopeGreaterThan()

◆ GetOptionalEnvelope()

◆ RecomputeTreeForDelayedOperations()

◆ RemoveEvent()

◆ Reset()