A Red-Black tree based Navigable Sorted Order Static Map in Solidity
npm install solidity-treemap
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:
1. Order book matching (by price)
2. Calendar scheduling (by time)
3. TCR reputation ranking (by score)
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:
``bash`
npm install -save solidity-treemap
You can then import the TreeMap.sol like so:
`solidity
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.
- putIfAbsent: attempt to insert item(key, value) and returns value associated with key after insertionitem(key, value)
- put: insert and replace any existing value if key is already in the treekey
- remove: remove mapping associated with from the map if it is presentkey
- get: find the value to which the is associated, or not found if the map does not contain such mappingkey
- getOrDefault: find the value to which the is associated, or defaultValue if the map does not contain such mapping
- size: returns the size of the tree
- floorEntry: returns an entry associated with the greatest key less than or equal to the given key
- lowerEntry: returns an entry associated with the greatest key less than the given key
- ceilingEntry: returns an entry associated with the least key greater than or equal to the given key
- higherEntry: returns an entry associated with the least key greater than the given key
- firstEntry: returns the entry associated with the lowest key
- lastEntry: returns the entry associated with the highest key
- select: find the i'th smallest element stored in the tree
- rank: find the rank of element x in the tree
This 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.
#### 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
#### Smart Contract
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.
- [ ] Enable in-order iteration over entries
- [ ] Implement more efficient bulk operations
Red Black Trees by Eternally Confuzzled
Java NavigableMap