A Red-Black tree based Navigable Order Static TreeMap in Solidity
A Solidity library which implements a navigable order static sorted treemap using Red Black Tree.
The treemap enables storage of (uint -> uint) mapping that further provides a total ordering by keys and navigation functions returning closest matches for any given keys.
Such map has a wide range of use cases in smart contracts, for example:
The map is backed by a Red-Black tree where all lookup operations can be efficiently completed in O(log n)
time. Due to lack of generics in Solidity, both keys and values take forms in uint256
. The value class can be easily extended to support any type by mantaining an additional mapping (uint => myStruct)
at the use site.
Install the library code as a regular npm package:
npm install -save solidity-treemap
You can then import the TreeMap.sol
like so:
import "solidity-treemap/contracts/TreeMap.sol";
contract TreeMapMock {
using TreeMap for TreeMap.Map;
TreeMap.Map sortedMap1;
TreeMap.Map sortedMap2;
...
}
Because Solidity does not support inheritence between library
, all functions currently live in the TreeMap.sol
together. The following documentation group functions logically.
item(key, value)
and returns value
associated with key
after insertionitem(key, value)
and replace any existing value if key
is already in the treekey
from the map if it is presentkey
is associated, or not found if the map does not contain such mappingkey
is associated, or defaultValue
if the map does not contain such mappingThis feature is still a work in progress.
To iterate through all map entries in O(n)
time, one has to maintain a stack to facilitate the in-order tree traversal.
There are two ways to iterate through map entires: internally in smart contracts and externally using web3.js.
When using web3.js, one could simply keep track of the state using arrays in Javascript.
TODO: provide an example iterate entires with web3.js
For iteration in smart contract, because memory array is not resizble in Solidity, we need to allocate stack ahead of time.
The TreeMapIterator.sol
provides a convenient wrapper for such access pattern where stack size is automatically determined and next()
conforms with the iterator interface.
TODO: finish TreeMapIterator
implementation.
The code has reasonably good test coverage but has not been audited. Since the code is provided as a library instead of contract, all operation on the TreeMap is private by default and please exercise good judgement on what mutability you expose externally in the contract. I take no responsibility for your use of this library and any security problem it might expose.
Red Black Trees by Eternally Confuzzled
Java NavigableMap