Solidity TreeMap

0.0.1

TreeMap

library TreeMap

Source: TreeMap.sol

Index

Reference

Functions

  • _applyColorInRemove

    function _applyColorInRemove(Map _self, Entry _current, Entry _grandParent, uint8 _parentDirection) internal

    Apply colors as necessary after rotation in top-down deletion factored out to avoid `CompilerError: Stack too deep, try removing local variables.`.

    Parameters:
    _self - Map
    _current - Entry
    _grandParent - Entry
    _parentDirection - uint8

  • _child

    function _child(Map _self, Entry _entry, uint8 _direction) internal view returns (Entry)

    Returns an entry's child in a direction.

    Parameters:
    _self - Map
    _entry - Entry
    _direction - uint8
    Returns:
    Entry

  • _decrementTreeSize

    function _decrementTreeSize(Map _self, uint _key) internal

    Decrement tree size when entry is removed in `remove`.

    Parameters:
    _self - Map
    _key - uint

  • _flipColorInProbe

    function _flipColorInProbe(Map _self, Entry _current) internal

    Flip color if applicable during probe() factored out to avoid `CompilerError: Stack too deep, try removing local variables.`.

    Parameters:
    _self - Map
    _current - Entry

  • _incrementTreeSize

    function _incrementTreeSize(Map _self, uint _key) internal

    Increment tree size when new entry is added in `probe`.

    Parameters:
    _self - Map
    _key - uint

  • _isChildRed

    function _isChildRed(Map _self, Entry _entry, uint8 _direction) internal view returns (bool)

    Check whether a entry's child is not NULL and its color is RED.

    Parameters:
    _self - Map
    _entry - Entry
    _direction - uint8
    Returns:
    bool

  • _isRed

    function _isRed(Entry _entry) internal view returns (bool)

    Check whether a entry is not NULL and its color is RED.

    Parameters:
    _entry - Entry
    Returns:
    bool

  • _leftChild

    function _leftChild(Map _self, Entry _entry) internal view returns (Entry)

    Returns an entry's left child.

    Parameters:
    _self - Map
    _entry - Entry
    Returns:
    Entry

  • _makeEntry

    function _makeEntry(Map _self, uint _key, uint _value) internal returns (uint, Entry)

    Creates a new entry and put it into `entries`.

    Parameters:
    _self - Map
    _key - key with which the specified value is to be associated
    _value - value to be associated with the specified key
    Returns:
    (index of the newly created entry, its storage pointer)

  • _rightChild

    function _rightChild(Map _self, Entry _entry) internal view returns (Entry)

    Returns an entry's right child.

    Parameters:
    _self - Map
    _entry - Entry
    Returns:
    Entry

  • _rotateDouble

    function _rotateDouble(Map _self, Entry _root, uint _rootIdx, uint8 _direction) internal returns (uint)

    Apply tree rotation around a root node in a specified direction twice. Inline code documentation assumes `direction` = `RIGHT` for simplicity and one can see both cases are symmetric.

    Parameters:
    _self - Map
    _root - root node to be rotated around
    _rootIdx - entry index of the root node
    _direction - rotation direction
    Returns:
    entry index of the new root node

  • _rotateSingle

    function _rotateSingle(Map _self, Entry _root, uint _rootIdx, uint8 _direction) internal returns (uint)

    Single tree rotation around a root node in a specified direction. old root is colored red and new root is colored black. /// Inline code documentation assumes `direction` = `RIGHT` for simplicity and one can see both cases are symmetric. /// Illustration omits color for simplicity: 3(root) 1(newRoot) /// / \ / \ /// 1(newRoot) 4(*) -> 0(*) 3(root) /// / \ / \ /// 0(*) 2(*) 2(*) 4(*) (*) means node preserve its previous children if applicable /// @param _root root node to be rotated around.

    Parameters:
    _self - Map
    _root - Entry
    _rootIdx - entry index of the root node
    _direction - rotation direction
    Returns:
    entry index of the new root node

  • _setRootToBlack

    function _setRootToBlack(Map _self) internal

    Set root node to BLACK color factored out to avoid `CompilerError: Stack too deep, try removing local variables.`.

    Parameters:
    _self - Map

  • blackHeight

    function blackHeight(Map _self) internal view returns (uint)

    This is useful to determine the size of stack to allocate for iterators implemented in contract since memory array cannot be resized NB: RBT guarantees the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf. O(log n), returns the black height of the tree: the uniform number of black nodes in all paths from root to the leaves.

    Parameters:
    _self - Map
    Returns:
    uint

  • ceilingEntry

    function ceilingEntry(Map _self, uint _key) internal view returns (bool, uint, uint)

    O(log n), returns an entry associated with the least key greater than or equal to the given key.

    Parameters:
    _self - Map
    _key - uint
    Returns:
    whether such entry exists and its key and value

  • firstEntry

    function firstEntry(Map _self) internal view returns (bool, uint, uint)

    O(log n), returns the entry associated with the lowest key.

    Parameters:
    _self - Map
    Returns:
    whether such entry exists and its key and value

  • floorEntry

    function floorEntry(Map _self, uint _key) internal view returns (bool, uint, uint)

    O(log n), returns an entry associated with the greatest key less than or equal to the given key.

    Parameters:
    _self - Map
    _key - uint
    Returns:
    whether such entry exists and its key and value

  • get

    function get(Map _self, uint _key) internal view returns (bool, uint)

    Find the value to which the `key` is associated, or not found if the map does not contain such mapping.

    Parameters:
    _self - Map
    _key - key whose associated value is to be returned
    Returns:
    (whether a mapping with `key` exists, the value associated with the `key`)

  • getOrDefault

    function getOrDefault(Map _self, uint _key, uint _defaultValue) internal view returns (uint)

    Find the value to which the `key` is associated, or `defaultValue` if the map does not contain such mapping.

    Parameters:
    _self - Map
    _key - key whose associated value is to be returned
    _defaultValue - fallback value to be returned
    Returns:
    the value associated with the `key` or `defaultValue` if not found

  • higherEntry

    function higherEntry(Map _self, uint _key) internal view returns (bool, uint, uint)

    O(log n), returns an entry associated with the least key greater than the given key.

    Parameters:
    _self - Map
    _key - uint
    Returns:
    whether such entry exists and its key and value

  • lastEntry

    function lastEntry(Map _self) internal view returns (bool, uint, uint)

    O(log n), returns the entry associated with the highest key.

    Parameters:
    _self - Map
    Returns:
    whether such entry exists and its key and value

  • lowerEntry

    function lowerEntry(Map _self, uint _key) internal view returns (bool, uint, uint)

    O(log n), returns an entry associated with the greatest key less than the given key.

    Parameters:
    _self - Map
    _key - uint
    Returns:
    whether such entry exists and its key and value

  • probe

    function probe(Map _self, uint _key, uint _value) internal returns (Entry)

    New entry is eventaully inserted as `RED` at the bottom of the tree. The insertion never triggers a black violation. Color flip, single and double rotation is used to address red violation. Color flip guarantees siblings are never both red and enables rotation to fix red violation in one go., Insert `entry(key, value)` and returns a storage pointer to the `entry` corresponding to `key`. If a duplicate key is found, returns a storage pointer to the duplicate without replacement.

    Parameters:
    _self - Map
    _key - key with which the specified value is to be associated
    _value - value to be associated with the specified key
    Returns:
    storage pointer to entry corresponding to the key

  • put

    function put(Map _self, uint _key, uint _value) internal returns (bool, uint)

    Insert `item(key, value)` and replace any existing value if `key` is already in the tree. return whether replacement occurred and value that was replaced.

    Parameters:
    _self - Map
    _key - key with which the specified value is to be associated
    _value - value to be associated with the specified key
    Returns:
    (wether value is replaced, value associated with the key before replacement)

  • putIfAbsent

    function putIfAbsent(Map _self, uint _key, uint _value) internal returns (uint)

    Attempt to insert `item(key, value)` and returns `value` associated with `key` after insertion. If `key` already existed in the tree, its original value is returned and no replacement of the item occurs.

    Parameters:
    _self - Map
    _key - key with which the specified value is to be associated
    _value - value to be associated with the specified key
    Returns:
    value associated with the specified key

  • rank

    function rank(Map _self, uint _key) internal view returns (bool, uint)

    Find the rank of element x in the tree, i.e. its index in the sorted list of elements of the tree.

    Parameters:
    _self - Map
    _key - uint
    Returns:
    whether `_key` already existed in the map and its index (or insertion index if not found)

  • remove

    function remove(Map _self, uint _key) internal returns (bool, uint)

    Deletion can be made easy by a few observations: 1. A RED leaf can be removed without any violations 2. A RED node can be removed without any violations if it only has at most one branch by attaching that branch to the node's parent 3. If the node to be removed has more than one branch, it can be swapped with an easy-to-remove red node first /// The swap candidate must be the largest element of left branch or the smallest element of right branch. Here we choose to use the largest element of left branch. We create a false root node colored RED first and iterate down the tree. We "push" this red color down along the iterator such that we guarantee the node to be swapped is colored RED. /// Inline code documentation assumes `direction` = `RIGHT` for simplicity and one can see both cases are symmetric. "RIGHT" is picked also because we are looking for largest element after we found the matching entry. The rest of the search always traverse down to the right direction., remove mapping associated with `key` from the map if it is present and returns old `value` associated with the `key` if found.

    Parameters:
    _self - Map
    _key - key whose mapping is to be removed
    Returns:
    (whether a mapping has been removed, the value associated with the `key` before removal)

  • select

    function select(Map _self, uint _i) internal view returns (bool, uint, uint)

    Find the i'th smallest element stored in the tree.

    Parameters:
    _self - Map
    _i - uint
    Returns:
    bool
    uint
    uint

  • size

    function size(Map _self) internal view returns (uint)

    O(1), returns the size of the tree.

    Parameters:
    _self - Map
    Returns:
    uint
← MathUtilTreeMapIterator →