Search code examples
c++quadtreeincomplete-type

Problems with c++ quadtree


I'm implementing a quadtree in a library, and the compiler keeps on throwing errors talking about an incomplete type: quadtree.h

template<int capacity,
         typename t,
         typename = std::enable_if<std::is_base_of<hasDim, t>::value && std::is_pointer<t>::value>>
struct quadtree {
    bool divided = false;
    quadtree<capacity, t>* nw,* ne,* sw,* se;
    std::vector<t> objs;
    rect2 b;

    quadtree(rect2 bounds): b(b) {}

    void addObj(t);
    void divide();
    void assign(t);
    void empty();
};

bin.cpp

#include "quadtree.h"

template<int capacity,
         typename t,
         typename = std::enable_if<std::is_base_of<hasDim, t>::value && std::is_pointer<t>::value>>
void quadtree<capacity, t>::addObj(t o) {
    if(!divided) {
        objs.push_back(o);
        if(objs.size() > capacity) {
            divide();
        }
    } else {
        assign(o);
    }
}

template<int capacity,
         typename t,
         typename = std::enable_if<std::is_base_of<hasDim, t>::value && std::is_pointer<t>::value>>
void quadtree<capacity, t>::divide() {
    divided = true;
    nw = new quadtree<capacity, t>(rect2(b.x(), b.y(), b.w()/2, b.h()/2));
    ne = new quadtree<capacity, t>(rect2(b.x()+b.w()/2, b.y(), b.w()/2, b.h()/2));
    sw = new quadtree<capacity, t>(rect2(b.x(), b.y()+b.h()/2, b.w()/2, b.h()/2));
    se = new quadtree<capacity, t>(rect2(b.x()+b.w(), b.y()+b.h(), b.w()/2, b.h()/2));
    for(auto o: objs) {
        assign(o);
    }
    objs.resize(0);
}

template<int capacity,
         typename t,
         typename = std::enable_if<std::is_base_of<hasDim, t>::value && std::is_pointer<t>::value>>
void quadtree<capacity, t>::assign(t o) {
    rect2 orect = o.makeRect();
    if(orect.intersects(nw.bounds)) {nw.addObj(o);}
    if(orect.intersects(ne.bounds)) {ne.addObj(o);}
    if(orect.intersects(sw.bounds)) {sw.addObj(o);}
    if(orect.intersects(se.bounds)) {se.addObj(o);}
}

template<int capacity,
         typename t,
         typename = std::enable_if<std::is_base_of<hasDim, t>::value && std::is_pointer<t>::value>>
void quadtree<capacity, t>::empty() {
    if(divided) {
        divided = false;
        nw.empty(); ne.empty(); sw.empty(); se.empty();
        delete nw, ne, sw, se;
    } else {
        objs.resize(0);
    }
}

According to microsoft, an incomplete type is one whose size can't be determined, but here I have no idea where this could come from: bool divided can be determined; the quadtree<capacity, t>*s are, well, pointers, whose size can be determined; std::vector<t> objs is a vector, which means it stores a dynamically allocated array, which means it's size can be determined as well; same goes for rect2 b which only stores 4 doubles. Any idea where the problem could come from?

EDIT:

Here's the error message:

bin.cpp:32:40: error: invalid use of incomplete type 'struct quadtree<capacity, t>'
   32 |  void quadtree<capacity, t>::addObj(t o) {
      |

Solution

  • Me from (quite a bit in) the future, the solution was to ditch the std::enable_ifs. It's still unclear to me why they were causing problems, but replacing those with one static_assert in the class body was enough to fix the problem. Anyway, kids, don't use this code. It's terrible.