1

I am trying to use an ordered statistics tree library in solidity based on this implementation https://github.com/drcode/ethereum-order-statistic-tree with some minor modifications to make it into a library. I have a second library that uses this ordered statistics tree library inserting and retrieving data.I am testing it with truffle using contract based tests. I am able to insert and retrieve up to 3 values in the tree with no issues. When I insert a 4th value the test fails with the error "Error: VM Exception while processing transaction: revert". I have no idea why this would be happening. The basic data structure in the tree library is defined by

struct Node {
    mapping (bool => uint) children; //false left child,true right child
    uint parent;
    bool side;  //side of the tree?
    uint height;
    uint count;
    uint dupes;  //duplicates
}




struct Index {

        mapping (uint => Node) nodes;
        uint numberofInserts;
}

The insert function is defined in two components

function insert(Index storage index,uint value) {
    if(index.numberofInserts==0){
     //index.nodes[0]=Node(0,true,0,0,0);

    }
     index.numberofInserts+=1;
    if (value==0){
        index.nodes[value].dupes++;
    }
    else{
        insert_helper(index,0,true,value);
    }
}
function insert_helper(Index storage index,uint p_value,bool side,uint value) private {
    Node root=index.nodes[p_value];
    uint c_value=root.children[side];
    if (c_value==0){
        root.children[side]=value;
        Node child=index.nodes[value];
        child.parent=p_value;
        child.side=side;
        child.height=1;
        child.count=1;
        update_counts(index,value);
        rebalance_insert(index,value);
    }
    else if (c_value==value){
        index.nodes[c_value].dupes++;
        update_count(index,value);
        update_counts(index,value);
    }
    else{
        bool side_new=(value >= c_value);
        insert_helper(index,c_value,side_new,value);
    }
}

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.