Структура вложенного набора данных в PHP - PullRequest
0 голосов
/ 27 декабря 2018

Я пытаюсь реализовать объектно-ориентированную версию структуры вложенного набора данных в 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);

Ответы [ 2 ]

0 голосов
/ 28 декабря 2018

После выходного и одного кофе, наконец, удалось это сделать.Это не так просто, как кажется, потому что при добавлении нового узла необходимо переписать все дерево:

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.

0 голосов
/ 27 декабря 2018

Вы не должны определять родителя или ссылку на него, потому что вы можете оказаться в цикле ссылок, что не плохо в коде, но в дизайне и может в конечном итоге сделать ваш код невозможным для понимания, когда вещипойти не так.

Что касается функции 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 хотя.но я предполагаю, что верхний родительский путь расположен слева, а нижний дочерний - справа.В этом случае я бы просто дифференцировал его от уровня.

Я бы также не использовал приватный и использовал защищенный, в основном я сделал это здесь, так что я могу пройти весь путь без использования добытчиков исеттеры, чтобы сделать код более компактным, но сделать это так, как вам хочется:

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));
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...