Interval tree is what you need to efficiently handle intervals.
A simple implementation of interval tree in Solidity is provided below. Please note, it's not a balanced implementation, so in worst case it can degrade to a linked list (when you add intervals to it in ascending or descending order). It supports overlapping intervals, and search()
can easily be changed to deal with intervals as well instead of single values.
The worst case complexity of insertion and search is O(N), the best case, when the tree is relatively balanced (which is when intervals are added in random order), is O(log N). Most of the time it's somewhere in between.
You'll likely need to modify it to fit your purposes, see the Node
struct and the add()
function if you need to store other data besides addresses.
// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.7.0;
// Implements a binary interval tree.
library IntervalTree {
struct Interval {
uint a;
uint b;
}
struct Node {
Interval i;
address addr;
uint max;
// Indices of child nodes in the node array within a Tree instance.
uint left;
uint right;
}
// The tree itself.
// Uses an array for storage.
struct Tree {
Node[] nodes;
}
// Adds an interval to the tree.
function add(Tree storage tree, uint a, uint b, address addr) public {
tree.nodes.push(Node({
i: Interval({a: a, b: b}),
max: b,
left: 0, right: 0,
addr: addr
}));
fix(tree, tree.nodes[0], tree.nodes.length-1, a, b);
}
function max(uint a, uint b) private pure returns(uint) {
if (a > b)
return a;
return b;
}
// Finds a correct place for a newly inserted node.
function fix(Tree storage tree, Node storage node, uint nid, uint a, uint b) private {
node.max = max(node.max, b);
if (a < node.i.a) {
if (node.left != 0) {
fix(tree, tree.nodes[node.left], nid, a, b);
return;
}
node.left = nid;
} else {
if (node.right != 0) {
fix(tree, tree.nodes[node.right], nid, a, b);
return;
}
node.right = nid;
}
}
// Checks whether the interval i contains the value v.
function contains(Interval storage i, uint v) private view returns(bool) {
return (i.a <= v && v <= i.b);
}
// Traverses the tree and finds all intervals that contain v.
// Puts found intervals into the nodes array.
function search(Tree storage tree, uint v, Node[] storage nodes) public {
searchIntervals(tree, 0, v, nodes);
}
// DFS.
function searchIntervals(Tree storage tree, uint i, uint v, Node[] storage nodes) private {
if (contains(tree.nodes[i].i, v)) {
nodes.push(tree.nodes[i]);
}
if (tree.nodes[i].left != 0 && tree.nodes[tree.nodes[i].left].max >= v) {
searchIntervals(tree, tree.nodes[i].left, v, nodes);
}
if (tree.nodes[i].right != 0 && tree.nodes[tree.nodes[i].right].max >= v) {
searchIntervals(tree, tree.nodes[i].right, v, nodes);
}
}
function length(Tree storage tree) public view returns(uint) {
return tree.nodes.length;
}
}
And a contract to test it in action is below. It uses events to output the search()
results because Remix has issues with output form non-constant functions.
// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.7.0;
pragma experimental ABIEncoderV2;
import "IntervalTree.sol";
contract IntervalBets {
using IntervalTree for IntervalTree.Tree;
using IntervalTree for IntervalTree.Node;
IntervalTree.Tree tree;
IntervalTree.Node[] nodes;
event Interval(uint[2] interval);
constructor() {
tree.add(0, 50, msg.sender);
tree.add(51, 320, msg.sender);
tree.add(321, 500, msg.sender);
tree.add(11, 111, msg.sender);
tree.add(0, 3, msg.sender);
tree.add(33, 320, msg.sender);
tree.add(599, 9001, msg.sender);
tree.add(9, 9999, msg.sender);
tree.add(99, 8899, msg.sender);
tree.add(1, 42, msg.sender);
tree.add(13, 666, msg.sender);
tree.add(0, 2, msg.sender);
tree.add(3, 5, msg.sender);
tree.add(7, 9, msg.sender);
tree.add(9, 11, msg.sender);
tree.add(3, 12, msg.sender);
tree.add(3, 12, msg.sender);
tree.add(1001, 10001, msg.sender);
}
function bet(uint a, uint b) public {
tree.add(a, b, msg.sender);
}
function check(uint v) public {
tree.search(v, nodes);
for (uint i=0; i<nodes.length; i++) {
// Using events to monitor output in Remix
// since it won't decode output from non-constant functions.
emit Interval([nodes[i].i.a, nodes[i].i.b]);
}
delete nodes;
}
}