Нахождение соседних узлов в дереве

Я разрабатываю структуру, которая похожа на двоичное дерево, но обобщена по измерениям, поэтому вы можете установить, является ли это двоичным деревом, квадродеревом, октавным деревом и т. Д., Установив параметр измерения во время инициализации.

Вот определение этого:

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

Итак, чтобы инициализировать его, я устанавливаю измерение, а затем делю. Я собираюсь для дерева глубины 2 для иллюстрации здесь:

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;

Это приведет к созданию дерева квадрантов, состояние каждого из значений которого будет установлено в [0-4] [0-4].

([{0}{1}{2}{3}][{10}{11}{12}{13}][{20}{21}{22}{23}][{30}{31}{32}{33}])

У меня проблемы с поиском соседних узлов из любого куска. Что нужно сделать, это взять направление, а затем (при необходимости) пройти вверх по дереву, если направление выходит за пределы края родительского узла (например, если мы были в правом нижнем углу квадрата дерева квадрантов, и нам нужно было получить часть справа от этого). Мой алгоритм возвращает фиктивные значения.

Вот как устроены массивы:

И вот структуры, которые необходимо знать для этого:

Это просто держит направление для предметов.

enum orientation : signed int {LEFT = -1, CENTER = 0, RIGHT = 1};

Это держит направление и стоит ли идти глубже.

template <uint Dimension>
struct TraversalHelper {
std::array<orientation, Dimension> way;
bool deeper;
};

node_orientation_table содержит ориентации в структуре. Таким образом, в 2d, 0 0 относится к верхнему левому квадрату (или левому левому квадрату).
[[ВЛЕВО, ВЛЕВО], [ВПРАВО, ВЛЕВО], [ВЛЕВО, ВПРАВО], [ВПРАВО, ВПРАВО]]

И функция getPositionFromOrientation примет LEFT, LEFT и вернет 0. Это просто принципиальная противоположность node_orientation_table выше.

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

Для примера этого:

std::array<orientation, Dimension> direction;
direction[0] = LEFT; //x
direction[1] = CENTER; //y

NDTree<Dimension> * result = tree[3][0]->getAdjacentNode(direction);

Это должно захватить верхний правый квадрат в нижнем левом квадрате, например tree[2][1] который будет иметь значение 21, если мы прочитаем его состояние. Который работает с момента моего последнего редактирования (алгоритм изменен). Тем не менее, многие запросы не дают правильных результатов.

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

Есть и другие примеры некорректного поведения, такие как tree [0] [0] (LEFT, LEFT), но многие другие работают правильно.

Вот это папка с git-репо, с которой я работаю Просто беги g++ -std=c++11 main.cpp из этого каталога, если это необходимо.