Как обойти дерево с циклическими ссылками?

[ksnk]

А вот сравнение адресов в PHP есть? Как решить, что два указателя смотрят на один и тот же объект?

Сама задача:
Есть древообразный объект. Вообще говоря, неопределеного содержания. Объект имеет множество ссылок на другие такие же. Эти, в свою очередь, могут ссылаться на него. Случай запущенный. Не дерево, просто клубок... "Постарайтесь избегать держать его таким образом" уже не проходит.

Пишется рекурсивная функция обхода этого "дерева". Хочется каким-то образом не заходить в уже посещенные листочки.

По идее - если убедить объекты хранить дополнительное свойство - "уже просмотрели", то несложно по содержимому этого свойства решить выводить его или нет. Есть ли возможность ходить по такому дереву без модификации свойств объекта?

 

[Вурдалак]

http://php.net/manual/en/class.splobjectstorage.php

 

[fixxxer]

если заранее известен refcount (скажем, изначально везде 1), можно его увеличивать и смотреть в debug_dump_zval

 

[ksnk]

fixxxer, хотелось бы избежать дополнительного свойства в объектах. Этот refcount, для текущего акта просмотра, придется хранить в самом теле листочков. место для хранения будет актуально только на момент просмотра и никогда больше.
Или я что-то не так понял?
В принципе, ответ от Вурдалак, вполне подходит, хотя простое сравнение адресов было бы значительно проще, imho...

 

[fixxxer]

не, ну тогда бери spl_object_hash и сравнивай, только памяти не хватит, если объектов много

 

[fixxxer]

хотелось бы избежать дополнительного свойства в объектах. Этот refcount, для текущего акта просмотра, придется хранить в самом теле листочков. место для хранения будет актуально только на момент просмотра и никогда больше.
Или я что-то не так понял?

Не понял это такой адский хак, который сработает, только если мы заранее знаем, что это дерево "свежее" и там нет лишних ссылок, на его объекты, т.е. refcount==1.
Заводим в скоупе обходилки скажем массив $tmp, делаем на каждое посещенное $tmp[] = $walked, имеем refcount=2, знаем, что оно посещено, а при выходе из скоупа gc подберет.

 

[ksnk]

O! Спасибо. spl_object_hash будет решением для 5.2.
Про хак - не понял. Что такое "лишние ссылки"?
Пусть объектов 3 штуки, $a,$b,$c замкнуты в кольцо $a->ref=$b; $b->ref=$c;$c->ref=$a;
просматриваем, начиная с $a... Ежели на пальцах, то как оно будет выглядеть?

 

[fixxxer]

А, заранее такое - так тогда вообще проще, рекурсию сразу видно

php > $a = new stdclass; $b = new stdclass; $c = new stdclass;
php > $a->ref=$b; $b->ref=$c;$c->ref=$a;
php > debug_zval_dump($a);
object(stdClass)#4 (1) refcount(3){
  ["ref"]=>
  object(stdClass)#5 (1) refcount(2){
    ["ref"]=>
    object(stdClass)#6 (1) refcount(2){
      ["ref"]=>
      object(stdClass)#4 (1) refcount(3){
        ["ref"]=>
        object(stdClass)#5 (1) refcount(2){
          ["ref"]=>
          object(stdClass)#6 (1) refcount(2){
            ["ref"]=>
            *RECURSION*
          }
        }
      }
    }
  }
}

(тут тысяча проклятий в адрес бездумно выпиливших call by ref - рефкаунт лишний)

 

[fixxxer]

5.2

жесть какая

 

[ksnk]

debug_zval_dump два раза зашел в веточки? Не считово

 

[С.]

Объекты можно тупо сравнивать. Они равны если указывают на одну и ту же копию.
При обходе помещать объект в пул пройденных объектов и искать дупликаты обычным array_search().

 

[hell0w0rd]

http://php.net/manual/en/class.splobjectstorage.php

Если данные берутся из базы, или еще откуда-то, где есть PK известный - лучше его брать. splobjectstorage использует spl_object_hash, а это грозит возможностью повтора, в случае, если объекты подчистятся gc.

 

[Вурдалак]

hell0w0rd, так SplObjectStorage не дает GC удалить объект, насколько я понимаю. Его не используют в Doctrine из-за соображений производительности, насколько я помню.

 

[fixxxer]

так SplObjectStorage не дает GC удалить объект, насколько я понимаю

Ага. Вообще отсутствие weak refs это большая проблема в частности для orm. Есть rfc, но на него поклали

 

[fixxxer]

Объекты можно тупо сравнивать. Они равны если указывают на одну и ту же копию.
При обходе помещать объект в пул пройденных объектов и искать дупликаты обычным array_search().

Так будет полный перебор, а хэши можно сложить ключами массива. Ну как всегда выбор между расходом памяти и cpu

 

[WMix]

скушные вы...

print_r( unserialize(preg_replace('/;R:[\d]+;/i', ';N;', serialize($a))) );