Finding values within an Array/Mapping based off min and max values

Question

I want a user to be able to place a bet on some number, between a range of numbers.

So the user wants to place a bet on the numbers 50-500. Then there is a function that sees if the number has been bet on - such as hasBet(uint256 number_to_check)

Lets say the user places a bet for the range of 50-500. Then someone wants to check that number 79 has a bet.

How would you store this data such that you can check (without a loop since the ranges could be from 0 to 2^255)?

Here is what I have:

Lets say 3 users have placed bets from 0-50, 51-320, 321-500.

So the value 79 would be bet on in the second bet - ranging from 51-320.

What type of structures/arrays/mappings would be useful to store the index of bets, and the values, such that you can find that 79 was stored. The key is to not use a loop, as the numbers could range into the millions or above.

Also, we know the min and max, so we know each batch is under 500 numbers and over 50. Also each bet would need to be consecutive, so if someone bet 0-50, next bet needs to be greater than 50.

So I feel this is helpful in finding the info. You can assume if the number was 7900, you know it couldn't be within the first X amount of bets, as its greater than 500.

The main operation after finding the struct containing the bet is a simple - "is 79 within the start and end values".

But the main question is how do you find that structure containing that bet, without having to do a loop?

edit:

One way I think would work, but not sure how to implement is storing the range of values in a mapping or array.

Such that an index would return the set value, ie: batchBets[1] returns [0, 50] and then the index would be stored in a separate mapping based off the max value or something similar?

Not really too sure.

Answer 1

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;
    }
}