OperatorUtilizationHeap

Git Source

The OperatorUtilizationHeap library provides functionality for managing an in-memory heap data structure that organizes operators based on their utilization. The heap allows for efficient insertion, removal, and update of operator utilizations, as well as retrieval of the operators with the minimum or maximum utilizations. https://people.scs.carleton.ca/~santoro/Reports/MinMaxHeap.pdf

State Variables

ROOT_INDEX

The root index of the heap.

uint8 constant ROOT_INDEX = 1;

Functions

initialize

Initializes the heap.

function initialize(uint8 maxSize) internal pure returns (Data memory);

Parameters

Name	Type	Description
maxSize	uint8	The maximum number of operators that can be stored in the heap.

isEmpty

Returns whether the heap is empty.

function isEmpty(Data memory self) internal pure returns (bool);

Parameters

Name	Type	Description
self	Data	The heap.

isFull

Returns whether the heap is full.

function isFull(Data memory self) internal pure returns (bool);

Parameters

Name	Type	Description
self	Data	The heap.

store

Inserts the heap into storage.

function store(Data memory self, LibMap.Uint8Map storage heapStore, uint256 maxOperatorsInHeap) internal;

Parameters

Name	Type	Description
self	Data	The heap.
heapStore	LibMap.Uint8Map	The stored heap.
maxOperatorsInHeap	uint256	The maximum number of operators that can currently be stored in the heap.

insert

Inserts an operator into the heap.

function insert(Data memory self, Operator memory o) internal pure;

Parameters

Name	Type	Description
self	Data	The heap.
o	Operator	The operator to insert.

remove

Removes an operator from the heap.

function remove(Data memory self, uint8 index) internal pure;

Parameters

Name	Type	Description
self	Data	The heap.
index	uint8	The index of the operator to remove.

removeByID

Removes an operator from the heap by its ID.

function removeByID(Data memory self, uint8 id) internal pure;

Parameters

Name	Type	Description
self	Data	The heap.
id	uint8	The ID of the operator to remove.

updateUtilization

Updates the utilization of an operator in the heap.

function updateUtilization(Data memory self, uint8 index, uint256 newUtilization) internal pure;

Parameters

Name	Type	Description
self	Data	The heap.
index	uint8	The index of the operator to update.
newUtilization	uint256	The new utilization of the operator.

updateUtilizationByID

Updates the utilization of an operator in the heap by its ID.

function updateUtilizationByID(Data memory self, uint8 id, uint256 newUtilization) internal pure;

Parameters

Name	Type	Description
self	Data	The heap.
id	uint8	The ID of the operator to update.
newUtilization	uint256	The new utilization of the operator.

extractMin

Extracts the minimum operator from the heap.

function extractMin(Data memory self) internal pure returns (Operator memory o);

Parameters

Name	Type	Description
self	Data	The heap.

extractMax

Extracts the maximum operator from the heap.

function extractMax(Data memory self) internal pure returns (Operator memory o);

Parameters

Name	Type	Description
self	Data	The heap.

getMin

Returns the minimum operator from the heap.

function getMin(Data memory self) internal pure returns (Operator memory);

Parameters

Name	Type	Description
self	Data	The heap.

getMax

Returns the maximum operator from the heap.

function getMax(Data memory self) internal pure returns (Operator memory);

Parameters

Name	Type	Description
self	Data	The heap.

getMaxIndex

Returns the index of the maximum operator from the heap.

function getMaxIndex(Data memory self) internal pure returns (uint8);

Parameters

Name	Type	Description
self	Data	The heap.

_bubbleDown

Adjusts the position of an operator downwards in the heap to ensure the heap's properties are maintained.

function _bubbleDown(Data memory self, uint8 i) internal pure;

Parameters

Name	Type	Description
self	Data	The heap.
i	uint8	The index of the operator to bubble down.

_bubbleDownMin

Adjusts the position of an operator downwards in the heap to ensure the heap's properties are maintained. The operator is assumed to be on a min level.

function _bubbleDownMin(Data memory self, uint8 i) internal pure;

Parameters

Name	Type	Description
self	Data	The heap.
i	uint8	The index of the operator to bubble down.

_bubbleDownMax

Adjusts the position of an operator downwards in the heap to ensure the heap's properties are maintained. The operator is assumed to be on a max level.

function _bubbleDownMax(Data memory self, uint8 i) internal pure;

Parameters

Name	Type	Description
self	Data	The heap.
i	uint8	The index of the operator to bubble down.

_bubbleUp

Adjusts the position of an operator upwards in the heap to ensure the heap's properties are maintained.

function _bubbleUp(Data memory self, uint8 i) internal pure;

Parameters

Name	Type	Description
self	Data	The heap.
i	uint8	The index of the operator to bubble up.

_bubbleUpMin

Adjusts the position of an operator upwards in the heap to ensure the heap's properties are maintained. The operator is assumed to be on a min level.

function _bubbleUpMin(Data memory self, uint8 i) internal pure;

Parameters

Name	Type	Description
self	Data	The heap.
i	uint8	The index of the operator to bubble up.

_bubbleUpMax

Adjusts the position of an operator upwards in the heap to ensure the heap's properties are maintained. The operator is assumed to be on a max level.

function _bubbleUpMax(Data memory self, uint8 i) internal pure;

Parameters

Name	Type	Description
self	Data	The heap.
i	uint8	The index of the operator to bubble up.

_hasGrandparent

Returns whether the node at the specified index has a grandparent.

function _hasGrandparent(uint8 i) internal pure returns (bool);

Parameters

Name	Type	Description
i	uint8	The index of the node in the heap.

_hasParent

Returns whether the node at the specified index has a parent.

function _hasParent(uint8 i) internal pure returns (bool);

Parameters

Name	Type	Description
i	uint8	The index of the node in the heap.

_hasChildren

Returns whether the node at the specified index has children.

function _hasChildren(Data memory self, uint8 i) internal pure returns (bool);

Parameters

Name	Type	Description
self	Data
i	uint8	The index of the node in the heap.

_isGrandchild

Returns whether the node at m is a grandchild of the node at i.

function _isGrandchild(uint8 i, uint8 m) internal pure returns (bool);

Parameters

Name	Type	Description
i	uint8	The index of the node in the heap.
m	uint8	The index of the child or grandchild of the node at index i.

_findOperatorIndex

Finds the index of the operator with the specified ID in the heap.

function _findOperatorIndex(Data memory self, uint8 id) internal pure returns (uint8, bool);

Parameters

Name	Type	Description
self	Data	The heap.
id	uint8	The ID of the operator to find.

_swap

Swaps the operators at the specified indices in the heap.

function _swap(Data memory self, uint8 index1, uint8 index2) internal pure;

Parameters

Name	Type	Description
self	Data	The heap.
index1	uint8	The index of the first operator to swap.
index2	uint8	The index of the second operator to swap.

_push

Pushes an operator onto the end of the heap.

function _push(Data memory self, Operator memory o) internal pure;

Parameters

Name	Type	Description
self	Data	The heap.
o	Operator	The operator to push.

_remove

Removes the operator at the specified index from the heap by swapping it with the last operator in the heap.

function _remove(Data memory self, uint8 i) internal pure;

Parameters

Name	Type	Description
self	Data	The heap.
i	uint8	The index of the operator to extract.

_getSmallestChildIndexOrGrandchild

Returns the index of the smallest child or grandchild of the node at index i.

function _getSmallestChildIndexOrGrandchild(Data memory self, uint8 i) internal pure returns (uint8);

Parameters

Name	Type	Description
self	Data	The heap.
i	uint8	The index of the node whose children and grandchildren are to be compared.

_getLargestChildIndexOrGrandchild

Returns the index of the largest child or grandchild of the node at index i.

function _getLargestChildIndexOrGrandchild(Data memory self, uint8 i) internal pure returns (uint8);

Parameters

Name	Type	Description
self	Data	The heap.
i	uint8	The index of the node whose children and grandchildren are to be compared.

_getExtremeChildIndexOrGrandchild

Returns the index of the extreme child or grandchild of the node at index i.

function _getExtremeChildIndexOrGrandchild(
    Data memory self,
    uint8 i,
    function(uint256, uint256) pure returns (bool) compare
) internal pure returns (uint8);

Parameters

Name	Type	Description
self	Data	The heap.
i	uint8	The index of the node whose children and grandchildren are to be compared.
compare	function (uint256, uint256) pure returns (bool)	The comparison function to use.

_isSmaller

Comparison function to determine if the first value is smaller than the second.

function _isSmaller(uint256 a, uint256 b) private pure returns (bool);

Parameters

Name	Type	Description
a	uint256	The first value.
b	uint256	The second value.

Returns

Name	Type	Description
<none>	bool	bool True if a is smaller than b, false otherwise.

_isLarger

Comparison function to determine if the first value is larger than the second.

function _isLarger(uint256 a, uint256 b) private pure returns (bool);

Parameters

Name	Type	Description
a	uint256	The first value.
b	uint256	The second value.

Returns

Name	Type	Description
<none>	bool	bool True if a is larger than b, false otherwise.

_isOnMinLevel

Returns whether the node at the specified index is on a min level.

function _isOnMinLevel(uint8 index) private pure returns (bool);

Parameters

Name	Type	Description
index	uint8	The index of the node in the heap.

_getLevel

Determines the level of a node in a binary heap.

function _getLevel(uint8 index) private pure returns (uint8 level);

Parameters

Name	Type	Description
index	uint8	The index of the node in the heap.

Errors

OPERATOR_NOT_FOUND

Thrown when an operator is not found in the heap.

error OPERATOR_NOT_FOUND();

INVALID_HEAP_SIZE

Thrown when attempting to initialize a heap with a size of 0.

error INVALID_HEAP_SIZE();

INVALID_INDEX

Thrown when attempting an operation on an invalid operator index.

error INVALID_INDEX();

HEAP_OVERFLOW

Thrown when attempting to insert an operator into a full heap.

error HEAP_OVERFLOW();

HEAP_UNDERFLOW

Thrown when attempting to fetch an operator from an empty heap.

error HEAP_UNDERFLOW();

Structs

Operator

The data structure representing an operator and its utilization.

struct Operator {
    uint8 id;
    uint256 utilization;
}

Data

The data structure representing the heap.

struct Data {
    Operator[] operators;
    uint8 count;
}