Я пытаюсь перейти через кучу объектов со ссылками на другие объекты. Я хочу начать с id из 1 и перемещаться по каждому из объектов. Некоторые из объектов будут возвращаться к предыдущим объектам, поэтому я хочу убедиться, что каждый раз смотрю на них, иначе я застрял бы в бесконечном цикле. Я также хочу узнать, к каким объектам нельзя получить доступ, перемещаясь по ссылкам. Я не думаю, что порядок навигации имеет значение.
Вот пример набора данных, с которым я мог бы столкнуться (мои фактические данные будут поступать из базы данных):
<?php $obj_array = [] ; $obj = new stdClass; $obj->id = 1; $obj->name = "Apple"; $obj->link = array(14, 5); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 3; $obj->name = "Carrot"; $obj->link = array(1, 14, 3); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 4; $obj->name = "Dill"; $obj->link = array(1, 5); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 5; $obj->name = "Egg"; $obj->link = array(6); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 6; $obj->name = "Fred"; $obj->link = array(7); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 7; $obj->name = "Goat"; $obj->link = array(7, 8); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 8; $obj->name = "Harry"; $obj_array[] = $obj; $obj = new stdClass; $obj->id = 9; $obj->name = "Igloo"; $obj->link = array(14, 5); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 10; $obj->name = "Jason"; $obj->link = array(1, 5, 8); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 11; $obj->name = "Klaus"; $obj->link = array(1, 5, 10); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 14; $obj->name = "Banana"; $obj->link = array(3); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 15; $obj->name = "Oyster1"; $obj->link = array(16); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 16; $obj->name = "Oyster2"; $obj->link = array(15); $obj_array[] = $obj; Я бы ожидал увидеть что-то вроде этого (порядок не имеет значения):
Обработанный:
Apple Banana Carrot Egg Fred Goat Harry
Не связано:
Dill Igloo Jason Klaus Oyster1 Oyster2
Как я могу создать цикл для прокрутки такой структуры, особенно когда каждый объект может иметь несколько ссылок?
Хотя ответ @wizards работал, я чувствовал, что хочу сделать версию с более четким кодом. Ниже версия возвращает объект со связанными и неизолированными элементами, и я считаю, что очень ясно, как это работает.
Причина, по которой я хочу работать так, заключается в том, чтобы продлить ее на будущие вопросы. Например, «Сколько раз связан элемент» или «У кого больше ссылок». Он также может быть легко адаптирован для ответа на эти вопросы.
Другим преимуществом является то, что он использует как можно более ограниченные циклы, что может ускорить процесс, когда размер увеличивается.
<?php error_reporting(E_ALL); $obj_array = [] ; $obj = new stdClass; $obj->id = 1; $obj->name = "Apple"; $obj->link = array(14, 5); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 3; $obj->name = "Carrot"; $obj->link = array(1, 14, 3); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 4; $obj->name = "Dill"; $obj->link = array(1, 5); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 5; $obj->name = "Egg"; $obj->link = array(6); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 6; $obj->name = "Fred"; $obj->link = array(7); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 7; $obj->name = "Goat"; $obj->link = array(7, 8); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 8; $obj->name = "Harry"; $obj_array[] = $obj; $obj = new stdClass; $obj->id = 9; $obj->name = "Igloo"; $obj->link = array(14, 5); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 10; $obj->name = "Jason"; $obj->link = array(1, 5, 8); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 11; $obj->name = "Klaus"; $obj->link = array(1, 5, 10); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 14; $obj->name = "Banana"; $obj->link = array(3); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 15; $obj->name = "Oyster1"; $obj->link = array(16); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 16; $obj->name = "Oyster2"; $obj->link = array(15); $obj_array[] = $obj; /* * CALL */ $parser = new ObjectLinker($obj_array, 1); //dump found //decode/encode to only show public values print_r(json_decode(json_encode($parser))); /* * ACTUAL CODE */ class ObjectLinker { private $_array; private $_start; public $LinkedElements = array(); public $UnLinkedElements = array(); final public function __construct($ar, $start) { $this->_array = $ar; $this->_start = $start; $this->getElementsArray(); $this->findLinked($this->_start); } final private function getElementsArray() { //since each Id is unique, i'm using the ID as the key in the array. this will allow faster access //Ofcourse it would be better if you would create the array like this in the first place, then you can skip this step foreach($this->_array as $obj) { if (!is_null($obj) && property_exists($obj, 'id')) { //I add everything to the unlinked elements. We will remove the linked once, to have once less loop $this->UnLinkedElements[$obj->id] = $obj; } } } final private function findLinked($id) { //If the key is not in the array, it's already loaded if (!array_key_exists($id, $this->UnLinkedElements)) { return; } //get obj //Because of the getElementsArray() step, I'm already sure the object exists. //If you change the input array, you might want to check for invalid obj $obj = $this->UnLinkedElements[$id]; //add to linked $this->LinkedElements[$id] = $obj; //remove from unlinked unset($this->UnLinkedElements[$id]); //no links if (!property_exists($obj, 'link')) { return; } $links = $obj->link; //Invalid links if (!is_array($links)) { return; } //check links foreach($links as $link) { $this->findLinked($link); } } } ?>не<?php error_reporting(E_ALL); $obj_array = [] ; $obj = new stdClass; $obj->id = 1; $obj->name = "Apple"; $obj->link = array(14, 5); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 3; $obj->name = "Carrot"; $obj->link = array(1, 14, 3); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 4; $obj->name = "Dill"; $obj->link = array(1, 5); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 5; $obj->name = "Egg"; $obj->link = array(6); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 6; $obj->name = "Fred"; $obj->link = array(7); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 7; $obj->name = "Goat"; $obj->link = array(7, 8); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 8; $obj->name = "Harry"; $obj_array[] = $obj; $obj = new stdClass; $obj->id = 9; $obj->name = "Igloo"; $obj->link = array(14, 5); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 10; $obj->name = "Jason"; $obj->link = array(1, 5, 8); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 11; $obj->name = "Klaus"; $obj->link = array(1, 5, 10); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 14; $obj->name = "Banana"; $obj->link = array(3); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 15; $obj->name = "Oyster1"; $obj->link = array(16); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 16; $obj->name = "Oyster2"; $obj->link = array(15); $obj_array[] = $obj; /* * CALL */ $parser = new ObjectLinker($obj_array, 1); //dump found //decode/encode to only show public values print_r(json_decode(json_encode($parser))); /* * ACTUAL CODE */ class ObjectLinker { private $_array; private $_start; public $LinkedElements = array(); public $UnLinkedElements = array(); final public function __construct($ar, $start) { $this->_array = $ar; $this->_start = $start; $this->getElementsArray(); $this->findLinked($this->_start); } final private function getElementsArray() { //since each Id is unique, i'm using the ID as the key in the array. this will allow faster access //Ofcourse it would be better if you would create the array like this in the first place, then you can skip this step foreach($this->_array as $obj) { if (!is_null($obj) && property_exists($obj, 'id')) { //I add everything to the unlinked elements. We will remove the linked once, to have once less loop $this->UnLinkedElements[$obj->id] = $obj; } } } final private function findLinked($id) { //If the key is not in the array, it's already loaded if (!array_key_exists($id, $this->UnLinkedElements)) { return; } //get obj //Because of the getElementsArray() step, I'm already sure the object exists. //If you change the input array, you might want to check for invalid obj $obj = $this->UnLinkedElements[$id]; //add to linked $this->LinkedElements[$id] = $obj; //remove from unlinked unset($this->UnLinkedElements[$id]); //no links if (!property_exists($obj, 'link')) { return; } $links = $obj->link; //Invalid links if (!is_array($links)) { return; } //check links foreach($links as $link) { $this->findLinked($link); } } } ?>
Вывод:
stdClass Object ( [LinkedElements] => stdClass Object ( [1] => stdClass Object ( [id] => 1 [name] => Apple [link] => Array ( [0] => 14 [1] => 5 ) ) [14] => stdClass Object ( [id] => 14 [name] => Banana [link] => Array ( [0] => 3 ) ) [3] => stdClass Object ( [id] => 3 [name] => Carrot [link] => Array ( [0] => 1 [1] => 14 [2] => 3 ) ) [5] => stdClass Object ( [id] => 5 [name] => Egg [link] => Array ( [0] => 6 ) ) [6] => stdClass Object ( [id] => 6 [name] => Fred [link] => Array ( [0] => 7 ) ) [7] => stdClass Object ( [id] => 7 [name] => Goat [link] => Array ( [0] => 7 [1] => 8 ) ) [8] => stdClass Object ( [id] => 8 [name] => Harry ) ) [UnLinkedElements] => stdClass Object ( [4] => stdClass Object ( [id] => 4 [name] => Dill [link] => Array ( [0] => 1 [1] => 5 ) ) [9] => stdClass Object ( [id] => 9 [name] => Igloo [link] => Array ( [0] => 14 [1] => 5 ) ) [10] => stdClass Object ( [id] => 10 [name] => Jason [link] => Array ( [0] => 1 [1] => 5 [2] => 8 ) ) [11] => stdClass Object ( [id] => 11 [name] => Klaus [link] => Array ( [0] => 1 [1] => 5 [2] => 10 ) ) [15] => stdClass Object ( [id] => 15 [name] => Oyster1 [link] => Array ( [0] => 16 ) ) [16] => stdClass Object ( [id] => 16 [name] => Oyster2 [link] => Array ( [0] => 15 ) ) ) )
Вы можете пропустить печать и работать с $obj_array , $obj_array данные в два массива, чтобы их можно было легко распечатать:
$linked_ids = array(); $processed_objects = array(); $unlinked_objects = array(); foreach ( $obj_array as $obj ) { if ( isset($obj->link) && $obj->link ) { $linked_ids = array_merge($linked_ids, $obj->link); } } $linked_ids = array_unique( $linked_ids ); foreach ($obj_array as $obj) { if ( !in_array($obj->id, $linked_ids) ) { $unlinked_objects[] = $obj; } else { $processed_objects[] = $obj; } } /* Printing */ echo '<b>Processed:</b><br>'; foreach ( $processed_objects as $obj ) { echo $obj->name . '<br>'; } echo '<b>Not Linked:</b><br>'; foreach ( $unlinked_objects as $obj ) { echo $obj->name . '<br>'; }
Я предположил, что в процессе производства полная сеть объектов слишком велика для хранения в памяти. Это означает, что правильный подход должен принимать только один корневой узел и обнаруживать все связанные объекты без дублирования
Я предположил, что каждый идентификатор в $obj->link может быть разрешен связанному объекту с использованием БД или другого запроса. Чтобы упростить код (поэтому мне не нужно писать функцию getObjAtID() ), я изменил интерфейс ссылки из $obj->link = [id1, id2] на $obj->link = [objectRef1, objectRef2]
Мой код:
function processObjNetwork(stdClass $rootObj){ $linkedObjects = []; $process = function(stdClass $obj) use(&$linkedObjects, &$process){ if(isset($linkedObjects[$obj->id])) return; // already processed else $linkedObjects[$obj->id] = $obj; // add to linked if(empty($obj->link)) return; // nothing linked; no recursion needed foreach($obj->link as $child) $process($child); // recursion to linked objs }; $process($rootObj); // start with the root node return $linkedObjects; }
То, что возвращается, представляет собой совокупность всех связанных объектов:
$linkedObjects = processObjNetwork($rootObject); // root here is 'Apple'
Демо-версия
Учитывая мое предположение – в частности, что карта слишком велика, поэтому мы начинаем с только корневого узла – невозможно обнаружить несвязанные узлы, поскольку по определению они не связаны с корнем.
Если у вас есть все узлы в хранилище, вы можете найти несвязанные узлы, просто повторяя каждый узел и проверяя, найден ли он среди связанных. Если нет, то он не подключен.
$unlinkedObjects = []; foreach($obj_array as $obj){ // add to $unlinkedObjects anything not found in $linkedObjects if(!isset($linkedObjects[$obj->id])) $unlinkedObjects[$obj->id] = $obj; }
Ответ обновлен, теперь код проходит через массив, начинающийся с ID = 1, собирает все ссылки «соединения», которые встречаются в прогоне и показывают имена объектов. Я надеюсь, что желаемый результат будет достигнут.
Первый список (до строки тире) – это список, который может быть доступен из объекта с ID = 1 через подключенные ссылки.
Второй – пропущенные имена.
Код:
<?php $obj_array = [] ; $obj = new stdClass; $obj->id = 1; $obj->name = "Apple"; $obj->link = array(14, 5); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 3; $obj->name = "Carrot"; $obj->link = array(1, 14, 3); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 4; $obj->name = "Dill"; $obj->link = array(1, 5); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 5; $obj->name = "Egg"; $obj->link = array(6); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 6; $obj->name = "Fred"; $obj->link = array(7); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 7; $obj->name = "Goat"; $obj->link = array(7, 8); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 8; $obj->name = "Harry"; $obj_array[] = $obj; $obj = new stdClass; $obj->id = 9; $obj->name = "Igloo"; $obj->link = array(14, 5); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 10; $obj->name = "Jason"; $obj->link = array(1, 5, 8); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 11; $obj->name = "Klaus"; $obj->link = array(1, 5, 10); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 14; $obj->name = "Banana"; $obj->link = array(3); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 15; $obj->name = "Oyster1"; $obj->link = array(16); $obj_array[] = $obj; $obj = new stdClass; $obj->id = 16; $obj->name = "Oyster2"; $obj->link = array(15); $obj_array[] = $obj; function findObject($objects, $id) { foreach ($objects as $object) { if ($object->id === $id) { return $object; } } return null; } function getLinkedIds($objects, $startId=1) { $idQueue = [$startId]; $linkedIds = []; while (count($idQueue)) { $id = array_pop($idQueue); $obj = findObject($objects, $id); if (!is_null($obj) && property_exists($obj, 'link')) { $linksToAdd = array_filter($obj->link, function($linkedId) use ($linkedIds) { return !in_array($linkedId, $linkedIds); }); $idQueue = array_merge($idQueue, $linksToAdd); } $linkedIds[] = $id; } return array_unique($linkedIds); } function getNotLinkedObjects($objects, $startId=1) { $linked = getLinkedIds($objects, $startId); return array_filter($objects, function($obj) use ($linked) { return !in_array($obj->id, $linked); }); } function getLinkedObjects($objects, $startId=1) { $linked = getLinkedIds($objects, $startId); return array_filter($objects, function($obj) use ($linked) { return in_array($obj->id, $linked); }); } function listNames($objects) { foreach ($objects as $obj) { echo $obj->name.PHP_EOL; } } listNames(getLinkedObjects($obj_array)); echo '----'.PHP_EOL; listNames(getNotLinkedObjects($obj_array));
результат:
Apple Carrot Egg Fred Goat Harry Banana --- Dill Igloo Jason Klaus Oyster1 Oyster2