I'm developing a structure that is like a binary tree but generalized across dimensions so you can set whether it is a binary tree, quadtree, octree, etc by setting the dimension parameter during initialization.
Here is the definition of it:
template <uint Dimension, typename StateType>
class NDTree {
public:
std::array<NDTree*, cexp::pow(2, Dimension)> * nodes;
NDTree * parent;
StateType state;
char position; //position in parents node list
bool leaf;
NDTree const &operator[](const int i) const
{
return (*(*nodes)[i]);
}
NDTree &operator[](const int i)
{
return (*(*nodes)[i]);
}
}
So, to initialize it- I set a dimension and then subdivide. I am going for a quadtree of depth 2 for illustration here:
const uint Dimension = 2;
NDTree<Dimension, char> tree;
tree.subdivide();
for(int i=0; i<tree.size(); i++)
tree[i].subdivide();
for(int y=0; y<cexp::pow(2, Dimension); y++) {
for(int x=0; x<cexp::pow(2, Dimension); x++) {
tree[y][x].state = ((y)*10)+(x);
}
}
std::cout << tree << std::endl;
This will result in a quadtree, the state of each of the values are initialized to [0-4][0-4].
([{0}{1}{2}{3}][{10}{11}{12}{13}][{20}{21}{22}{23}][{30}{31}{32}{33}])
I am having trouble finding adjacent nodes from any piece. What it needs to do is take a direction and then (if necessary) traverse up the tree if the direction goes off of the edge of the nodes parent (e.g. if we were on the bottom right of the quadtree square and we needed to get the piece to the right of it). My algorithm returns bogus values.
Here is how the arrays are laid out:
And here are the structures necessary to know for it:
This just holds the direction for items.
enum orientation : signed int {LEFT = -1, CENTER = 0, RIGHT = 1};
This holds a direction and whether or not to go deeper.
template <uint Dimension>
struct TraversalHelper {
std::array<orientation, Dimension> way;
bool deeper;
};
node_orientation_table holds the orientations in the structure. So in 2d, 0 0 refers to the top left square (or left left square).
[[LEFT, LEFT], [RIGHT, LEFT], [LEFT, RIGHT], [RIGHT, RIGHT]]
And the function getPositionFromOrientation
would take LEFT, LEFT and return 0. It is just basically the opposite of the node_orientation_table above.
TraversalHelper<Dimension> traverse(const std::array<orientation, Dimension> dir, const std::array<orientation, Dimension> cmp) const
{
TraversalHelper<Dimension> depth;
for(uint d=0; d < Dimension; ++d) {
switch(dir[d]) {
case CENTER:
depth.way[d] = CENTER;
goto cont;
case LEFT:
if(cmp[d] == RIGHT) {
depth.way[d] = LEFT;
} else {
depth.way[d] = RIGHT;
depth.deeper = true;
}
break;
case RIGHT:
if(cmp[d] == LEFT) {
depth.way[d] = RIGHT;
} else {
depth.way[d] = LEFT;
depth.deeper = true;
}
break;
}
cont:
continue;
}
return depth;
}
std::array<orientation, Dimension> uncenter(const std::array<orientation, Dimension> dir, const std::array<orientation, Dimension> cmp) const
{
std::array<orientation, Dimension> way;
for(uint d=0; d < Dimension; ++d)
way[d] = (dir[d] == CENTER) ? cmp[d] : dir[d];
return way;
}
NDTree * getAdjacentNode(const std::array<orientation, Dimension> direction) const
{
//our first traversal pass
TraversalHelper<Dimension> pass = traverse(direction, node_orientation_table[position]);
//if we are lucky the direction results in one of our siblings
if(!pass.deeper)
return (*(*parent).nodes)[getPositionFromOrientation<Dimension>(pass.way)];
std::vector<std::array<orientation, Dimension>> up; //holds our directions for going up the tree
std::vector<std::array<orientation, Dimension>> down; //holds our directions for going down
NDTree<Dimension, StateType> * tp = parent; //tp is our tree pointer
up.push_back(pass.way); //initialize with our first pass we did above
while(true) {
//continue going up as long as it takes, baby
pass = traverse(up.back(), node_orientation_table[tp->position]);
std::cout << pass.way << " :: " << uncenter(pass.way, node_orientation_table[tp->position]) << std::endl;
if(!pass.deeper) //we've reached necessary top
break;
up.push_back(pass.way);
//if we don't have any parent we must explode upwards
if(tp->parent == nullptr)
tp->reverseBirth(tp->position);
tp = tp->parent;
}
//line break ups and downs
std::cout << std::endl;
//traverse upwards combining the matrices to get our actual position in cube
tp = const_cast<NDTree *>(this);
for(int i=1; i<up.size(); i++) {
std::cout << up[i] << " :: " << uncenter(up[i], node_orientation_table[tp->position]) << std::endl;
down.push_back(uncenter(up[i], node_orientation_table[tp->parent->position]));
tp = tp->parent;
}
//make our way back down (tp is still set to upmost parent from above)
for(const auto & i : down) {
int pos = 0; //we need to get the position from an orientation list
for(int d=0; d<i.size(); d++)
if(i[d] == RIGHT)
pos += cexp::pow(2, d); //consider left as 0 and right as 1 << dimension
//grab the child of treepointer via position we just calculated
tp = (*(*tp).nodes)[pos];
}
return tp;
}
For an example of this:
std::array<orientation, Dimension> direction;
direction[0] = LEFT; //x
direction[1] = CENTER; //y
NDTree<Dimension> * result = tree[3][0]->getAdjacentNode(direction);
This should grab the top right square within bottom left square, e.g. tree[2][1]
which would have a value of 21 if we read its state. Which works since my last edit (algorithm is modified). Still, however, many queries do not return correct results.
//Should return tree[3][1], instead it gives back tree[2][3]
NDTree<Dimension, char> * result = tree[1][2].getAdjacentNode({ RIGHT, RIGHT });
//Should return tree[1][3], instead it gives back tree[0][3]
NDTree<Dimension, char> * result = tree[3][0].getAdjacentNode({ RIGHT, LEFT });
There are more examples of incorrect behavior such as tree[0][0](LEFT, LEFT), but many others work correctly.
Here is the folder of the git repo I am working from with this. Just run g++ -std=c++11 main.cpp
from that directory if it is necessary.