SortitionSumTreeFactory

Author: Enrique Piqueras - epiquerass@gmail.com

A factory of trees that keep track of staked values for sortition.

Functions

createTree

Public

Create a sortition sum tree at the specified key.

function createTree(SortitionSumTrees storage self, bytes32 _key, uint256 _K) public;

Parameters

Name	Type	Description
`self`	`SortitionSumTrees`
`_key`	`bytes32`	The key of the new tree.
`_K`	`uint256`	The number of children each node in the tree should have.

set

Set a value of a tree.

function set(SortitionSumTrees storage self, bytes32 _key, uint256 _value, bytes32 _ID) public;

Parameters

Name	Type	Description
`self`	`SortitionSumTrees`
`_key`	`bytes32`	The key of the tree.
`_value`	`uint256`	The new value.
`_ID`	`bytes32`	The ID of the value. `O(log_k(n))` where `k` is the maximum number of childs per node in the tree, and `n` is the maximum number of nodes ever appended.

queryLeafs

Public Views

Query the leaves of a tree. Note that if startIndex == 0, the tree is empty and the root node will be returned.

function queryLeafs(SortitionSumTrees storage self, bytes32 _key, uint256 _cursor, uint256 _count)
    public
    view
    returns (uint256 startIndex, uint256[] memory values, bool hasMore);

Parameters

Name	Type	Description
`self`	`SortitionSumTrees`
`_key`	`bytes32`	The key of the tree to get the leaves from.
`_cursor`	`uint256`	The pagination cursor.
`_count`	`uint256`	The number of items to return.

Returns

Name	Type	Description
`startIndex`	`uint256`	The index at which leaves start.
`values`	`uint256[]`	The values of the returned leaves.
`hasMore`	`bool`	Whether there are more for pagination. `O(n)` where `n` is the maximum number of nodes ever appended.

draw

Draw an ID from a tree using a number. Note that this function reverts if the sum of all values in the tree is 0.

function draw(SortitionSumTrees storage self, bytes32 _key, uint256 _drawnNumber) public view returns (bytes32 ID);

Parameters

Name	Type	Description
`self`	`SortitionSumTrees`
`_key`	`bytes32`	The key of the tree.
`_drawnNumber`	`uint256`	The drawn number.

Returns

Name	Type	Description
`ID`	`bytes32`	The drawn ID. `O(k * log_k(n))` where `k` is the maximum number of childs per node in the tree, and `n` is the maximum number of nodes ever appended.

stakeOf

Gets a specified ID's associated value.

function stakeOf(SortitionSumTrees storage self, bytes32 _key, bytes32 _ID) public view returns (uint256 value);

Parameters

Name	Type	Description
`self`	`SortitionSumTrees`
`_key`	`bytes32`	The key of the tree.
`_ID`	`bytes32`	The ID of the value.

Returns

Name	Type	Description
`value`	`uint256`	The associated value.

updateParents

Private

Update all the parents of a node.

function updateParents(
    SortitionSumTrees storage self,
    bytes32 _key,
    uint256 _treeIndex,
    bool _plusOrMinus,
    uint256 _value
) private;

Parameters

Name	Type	Description
`self`	`SortitionSumTrees`
`_key`	`bytes32`	The key of the tree to update.
`_treeIndex`	`uint256`	The index of the node to start from.
`_plusOrMinus`	`bool`	Wether to add (true) or substract (false).
`_value`	`uint256`	The value to add or substract. `O(log_k(n))` where `k` is the maximum number of childs per node in the tree, and `n` is the maximum number of nodes ever appended.

Structs

SortitionSumTree

Structs

struct SortitionSumTree {
    uint256 K;
    uint256[] stack;
    uint256[] nodes;
    mapping(bytes32 => uint256) IDsToNodeIndexes;
    mapping(uint256 => bytes32) nodeIndexesToIDs;
}

SortitionSumTrees

Storage

struct SortitionSumTrees {
    mapping(bytes32 => SortitionSumTree) sortitionSumTrees;
}