C++ Reference: class ThetaLambdaTree

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().