oop — структура вложенного набора данных в переполнении стека
Я пытаюсь реализовать объектно-ориентированную версию структура вложенного набора данных в PHP (другое описание структуры). Я уже создал реализацию узла:
class Node
{
private $parent;
private $nodes = [];
private $level = 1;
private $left = 1;
private $right = 2;
/**
* @return self|null
*/
public function getParent()
{
return $this->parent;
}
private function setParent(self $parent = null)
{
$this->parent = $parent;
}
public function getLevel(): int
{
return $this->level;
}
private function setLevel(int $level)
{
$this->level = $level;
}
public function getLeft(): int
{
return $this->left;
}
private function setLeft(int $left)
{
$this->left = $left;
}
public function getRight(): int
{
return $this->right;
}
private function setRight(int $right)
{
$this->right = $right;
}
/**
* @return static[]
*/
public function getNodes(): array
{
return $this->nodes;
}
public function addNode(Node $new)
{
$new->setLevel($this->getLevel() + 1);
$this->nodes[] = $new;
// @todo
}
}
тем не мение Мне нужна помощь в реализации addNode метод, который должен добавить новый узел к текущему и обновить все дерево, особенно недавно добавленный узел, родительский узел, дочерние узлы и т. д.
Чтобы упростить все, я создал простой тестовый пример, который проверит, все ли правильно реализовано:
$country = new Node();
$state = new Node();
$city = new Node();
$country->addNode($state);
$state->addNode($city);
assert($country->getLeft() === 1);
assert($country->getRight() === 6);
assert($country->getLevel() === 1);
assert($state->getLeft() === 2);
assert($state->getRight() === 5);
assert($state->getLevel() === 2);
assert($city->getLeft() === 3);
assert($city->getRight() === 4);
assert($city->getLevel() === 3);
Решение
Вы не должны определять родителя или ссылку на него, потому что вы можете оказаться в цикле ссылок, что не плохо в коде, но в дизайне и может в конечном итоге сделать ваш код невозможным для понимания, когда что-то пойдет не так.
Для addNode Похоже, вы на правильном пути,
public function addNode(Node $new)
{
//no need for getters and setters from inside the class
$new->level = $this->level + 1;
$this->nodes[] = $new;
return $this;
}
Я не уверен, что вы пытаетесь сделать left а также right хоть. но я предполагаю, что верхний родительский путь расположен слева, а нижний дочерний — справа. В этом случае я бы просто дифференцировал это от уровня.
Я бы также не использовал private и использовал protected, я в основном сделал это здесь, так что я могу пройти весь путь без необходимости в методах получения и установки, чтобы сделать код более компактным, но делайте это так, как вам хочется:
class Node
{
/**
* @var static
*/
protected $parent;
/**
* @var static[]
*/
protected $nodes = [];
/**
* @var int
*/
protected $level = 1;
/**
* @var int
*/
protected $left = 0;
/**
* @var int
*/
protected $right = 0;
public function addNode(Node $new)
{
$new->level = $this->level + 1;
$new->parent = $this;
$new->left = $new->level - 1;
if (empty($this->nodes)) {
$this->right = 1;
}
$curr = $this;
while (null !== $curr->parent) {
//walking up to the current parent and telling it there is a new level added
$curr->parent->right++;
//setting the current level 1 up
$curr = $curr->parent;
}
$this->nodes[] = $new;
return $this;
}
}
И потому что я вернусь $this, Я могу связать все, или вложенные вызовы addNode, как
$country = new Node();
$state = new Node();
$city = new Node();
$country->addNode($state->addNode($city));
Другие решения
После выходного и одного кофе, наконец, удалось это сделать. Это не так просто, как кажется, потому что все дерево должно быть переписано при добавлении нового узла:
public function addChild(Node $new): void
{
$this->nodes[] = $new;
$new->setParent($this);
$new->setLevel($this->getLevel() + 1);
$new->setLeft($this->getLeft() + 1);
$new->setRight($this->getLeft() + 2);
$rootNode = $this;
while (!empty($rootNode->getParent())) {
$rootNode = $this->getParent();
}
$rootNode->setLeft(1);
$this->updateTree($rootNode);
}
private function updateTree(Node $node): void
{
$startIndex = $node->getLeft();
foreach ($node->getChildren() as $child) {
$child->setLeft(++$startIndex);
$child->setRight(++$startIndex);
if (count($child->getChildren())) {
$this->updateTree($child);
$startIndex = $this->getLastChild($child)->getRight();
}
}
$node->setRight($this->getLastChild($node)->getRight() + 1);
}
private function getLastChild(Node $node): Node
{
return $node->getChildren()[count($node->getChildren()) - 1];
}
Класс скоро будет опубликован на GitHub.