php - Simple recursive object hierarchy in PHP, how to get ancestors avoiding infinite loop?

Question

Property parent returns the parent of the current item (or null). I need to avoid infinite recursion with an item that it's parent of itself.

// An item is considered without parent if parent is null or itself
$item1 = new Item();
$item1->setParent($item1);

$item2 = new Item();
$item2->setParent($item1);

$item3 = new Item();
$item3->setParent($item2);

$item1->getAncestors(); // Empty
$item2->getAncestors(); // Item 1
$item2->getAncestors(); // Item 1, Item 2

The following won't work because the first condition is true for "problematic" $item (thus the second isn't evaluated):

/**
 * Gets all ancestors of this item, sorted in a way that the farthest ancestor
 * comes first.
 *
 * @return \Doctrine\Common\Collections\ArrayCollection
 */
public function getAncestors()
{
    $parent = $this;
    $ancestors = array();

    while ($parent = $parent->parent && $this !== $parent) {
        $ancestors[] = $parent;
    }

    return new ArrayCollection(array_reverse($ancestors));
}

This won't work too because on loop 1 $this is $parent:

while ($this !== $parent && $parent = $parent->parent) {
    $ancestors[] = $parent;
}

I'm sure this is a common problem but I can't find a solution by myself.

Answer 1

正如您所说，您正在遍历的结构不是一棵树。这是一个带循环的有向图。避免无限循环的一种方法是通过传递包含所有已访问顶点的数组列表来跟踪已访问顶点。当您访问每个顶点时，您首先检查它是否在列表中，如果为真则返回，否则将其添加到列表中并继续。您不需要递归。一个while循环就可以了。