Method is being called on class with uninitialized attributes despite constructors

Question

Premise: suppose I have a rectangular subset of 2D space and a collection of points, all with different x-values, in this subset. In the interest of the optimization of an algorithm as yet unwritten, I want to split my box into cells according to the following process: I halve my rectangle into 2 equal parts along the x-axis. Then I repeatedly halve each sub-rectangle until every cell contains either 1 point or none at all.

In this illustration the vertical lines represent the “halving process” and the lines are ordered by darkness (darker is newer).

First I’ll define two basic classes:

class Point{
    private:
        double x;
        double y;
    public:
        // [...]
        // the relevant constructor and getter
        // overloaded operators +, -, * for vector calculations
};

class Box{
    private:
        Point bottom_left_point;
        double width;
        double height;
    public:
        Box(Point my_point, double my_x, double my_y) : // constructor
            bottom_left_point(my_point), width(my_x), height(my_y){}

        bool contains(const Point& p); // returns true iff the box contains p in the geometric sense
        Box halve(bool b) const; // takes a boolean as input and returns the left half-rectangle for false, and the right half-rectangle for true
};

Now to implement the “halving algorithm” I’ll need a binary tree-like structure. Each node will represent a sub-cell of the rectangle (with the root node representing the total rectangle). A node may have two children, in which case the children represent its left and right halves. A node may also have a pointer to a particle which exists in the cell. The ultimate idea will be to start with an empty tree and insert the points in, one by one using a method insert(Point* to_be_inserted).

So I’ll define the following recursive class, whose private attributes are rather self-explanatory:

class Node;

class Node{
    private:
        enum node_type{ INT, EXT, EMPTY };

        node_type type;
        // type == INT means that it is an interior node, i.e. has children
        // type == EXT means that it is an exterior node, i.e. has no children but contains a point
        // type == EMPTY means that it has no children and no point

        std::array<Node*,2> children;
        Box domain; // the geometric region which is being represented
        Point* tenant; // address of the particle that exists in this cell (if one such exists)

    public:
        Node(Box my_domain) :
            type(EMPTY), children({nullptr}), domain(my_domain){}
        //
        // to be continued...

The first order of business is to define a subdivide() method which endows my node with two children:

void Node::subdivide(void){
    type = INT;
    children[0] = new Node(domain.halve(false));
    children[1] = new Node(domain.halve(true));
}

Now everything is in place to write the crux of this whole affair, the insert method. Since it will be written recursively, the easiest solution is to have a boolean return type which tells us if the insertion was a success or failure. With this in mind, here’s the code:

bool Node::insert(Point* to_be_inserted){
    if(not domain.contains(*to_be_inserted)) return false;
    switch(type){
        case INT:{
            for(Node* child : children) if(child->insert(to_be_inserted)) return true;
            return false;
        }
        case EXT:{
            subdivide();

            for(Node* child : children) if(child->insert(to_be_inserted)) break;
            tenant = nullptr;

            for(Node* child : children) if(child->insert(to_be_inserted)) return true;
            break;
        }
        case EMPTY:{    
            type = EXT;
            tenant = to_be_inserted;
            return true;
        }
    }
    throw 1; // this line should not, in, theory ever be reached
}

(Note that, for the sake of abstraction and generality, I have used for loops on the array children when I could have simply written out the two cases.)

Explanation:

• First we check if to_be_inserted is in the geometric region represented by this. If not, return false.

• If this is an internal node, we pass the point on to the each child until it is successfully inserted.

• If this is an external node, that means that we have to split the node in two in order to be able to properly isolate to_be_inserted from the point that currently lives in the node.

  • First we call multiply().
  • Then we attempt to insert the current tenant into one of the children (please excuse how obscene this sounds, I assure you that it’s unintentional).
  • Once that is done, we do the same with to_be_inserted and return the result. (Note that a priori the insertion would be a success at this point because of the preliminary call to box::contains.

• Finally, if this is an EMPTY node, we simply have to assign tenant to *to_be_inserted and change type to EXT and we’re done.

Ok, so let's try it out with a simple main:

int main(void){
    Box my_box(ORIGIN, 1.0, 1.0); // rectangle of vertices (0,0),(0,1),(1,0),(1,1)
    Node tree(box); // initializes an empty tree representing the region of my_box
    Point p(0.1, 0.1);
    Point q(0.6, 0.7);
    tree.insert(&p);
    tree.insert(&q);

    return 0;
}

This compiles, but upon running the exception at the bottom of insert is thrown after a few calls. How is this possible, given that at no point a Node is constructed without a type value?

Edit: I have noticed, as well as this one, several possible errors which may also occur with small changes in the code:

• An inexplicable call to nullptr->insert(something)

• A call to insert by the address 0x0000000000000018 which doesn't point to an initialized Node.

---

The entirety of the code, including a makefile with the relevant debugging flags, can be found at https://github.com/raphael-vock/phantom-call.