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

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

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

Send feedback about...