-
Notifications
You must be signed in to change notification settings - Fork 24
/
TestBokkyPooBahsRedBlackTree.sol
63 lines (57 loc) · 2.22 KB
/
TestBokkyPooBahsRedBlackTree.sol
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
pragma solidity ^0.6.0;
import "BokkyPooBahsRedBlackTreeLibrary.sol";
// ----------------------------------------------------------------------------
// BokkyPooBah's Red-Black Tree Library v1.0-pre-release-a - Contract for testing
//
// A Solidity Red-Black Tree binary search library to store and access a sorted
// list of unsigned integer data. The Red-Black algorithm rebalances the binary
// search tree, resulting in O(log n) insert, remove and search time (and ~gas)
//
// https://github.com/bokkypoobah/BokkyPooBahsRedBlackTreeLibrary
//
//
// Enjoy. (c) BokkyPooBah / Bok Consulting Pty Ltd 2020. The MIT Licence.
// ----------------------------------------------------------------------------
contract TestBokkyPooBahsRedBlackTree {
using BokkyPooBahsRedBlackTreeLibrary for BokkyPooBahsRedBlackTreeLibrary.Tree;
BokkyPooBahsRedBlackTreeLibrary.Tree tree;
mapping(uint => uint) values;
event Log(string where, uint key, uint value);
constructor() public {
}
function root() public view returns (uint _key) {
_key = tree.root;
}
function first() public view returns (uint _key) {
_key = tree.first();
}
function last() public view returns (uint _key) {
_key = tree.last();
}
function next(uint key) public view returns (uint _key) {
_key = tree.next(key);
}
function prev(uint key) public view returns (uint _key) {
_key = tree.prev(key);
}
function exists(uint key) public view returns (bool _exists) {
_exists = tree.exists(key);
}
function getNode(uint _key) public view returns (uint key, uint parent, uint left, uint right, bool red, uint value) {
if (tree.exists(_key)) {
BokkyPooBahsRedBlackTreeLibrary.Node memory node = tree.getNode(_key);
(key, parent, left, right, red) = (_key, node.parent, node.left, node.right, node.red);
value = values[_key];
}
}
function insert(uint _key, uint _value) public {
tree.insert(_key);
values[_key] = _value;
emit Log("insert", _key, _value);
}
function remove(uint _key) public {
tree.remove(_key);
emit Log("remove", _key, values[_key]);
delete values[_key];
}
}