C++ Reference: class ThetaLambdaTree

Note: This documentation is automatically generated.

Method
AddOrUpdateEvent	Return type: void Arguments: 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).
AddOrUpdateOptionalEvent	Return type: void Arguments: 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).
DelayedAddOrUpdateEvent	Return type: void Arguments: int event, IntegerType initial_envelope, IntegerType energy_min, IntegerType energy_max Delayed version of AddOrUpdateEvent(), see RecomputeTreeForDelayedOperations().
DelayedAddOrUpdateOptionalEvent	Return type: void Arguments: int event, IntegerType initial_envelope_opt, IntegerType energy_max Delayed version of AddOrUpdateOptionalEvent(), see RecomputeTreeForDelayedOperations().
DelayedRemoveEvent	Return type: void Arguments: int event Delayed version of RemoveEvent(), see RecomputeTreeForDelayedOperations().
EnergyMin	Return type: IntegerType Arguments: int event Getters.
GetEnvelope	Return type: IntegerType Returns the maximum envelope using all the energy_min in O(1). If theta is empty, returns ThetaLambdaTreeNegativeInfinity().
GetEnvelopeOf	Return type: IntegerType Arguments: int event Returns initial_envelope(event) + sum_{event' >= event} energy_min(event'), in time O(log n).
GetEventsWithOptionalEnvelopeGreaterThan	Return type: void Arguments: IntegerType target_envelope, int* critical_event, int* optional_event, IntegerType* available_energy 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).
GetMaxEventWithEnvelopeGreaterThan	Return type: int Arguments: IntegerType target_envelope 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).
GetOptionalEnvelope	Return type: IntegerType 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().
RecomputeTreeForDelayedOperations	Return type: void 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.
RemoveEvent	Return type: void Arguments: int event Makes event absent, compute the new envelope in O(log n).
Reset	Return type: void Arguments: 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.
ThetaLambdaTree	Builds a reusable tree. Initialization is done with Reset().