резьбовые комментарии — групповые сообщения в темах в переполнении стека

Question

резьбовые комментарии — групповые сообщения в темах в переполнении стека

У меня есть массив сообщений с их ссылками на родительское сообщение (я), это выглядит примерно так:

array (
'm1' => array ('m9'),
'm5' => array ('m3', 'm4', 'm2'),
'm2' => array ('m1'),
'm3' => array ('m2', 'm1', 'm8'),
'm6' => array ('m7'),
'm4' => array ('m3', 'm2'),
)

Ключи этого массива являются идентификаторами сообщений, а значения являются ссылками на ноль или больше идентификаторы родителей (в любом порядке). Порядок идентификаторов может быть случайным, и не гарантируется, что указанный родительский идентификатор находится в данном наборе сообщений.

Что мне нужно сделать, это сгруппировать эти сообщения в «многопоточном представлении». В общем, мне нужно преобразовать этот массив в нечто вроде этого:

array(
'm1' => array('m1', 'm2', 'm3', 'm4', 'm5'),
'm6' => array('m6')
);

Каждое сообщение должно быть назначено потоку, сгруппированному по сообщению верхнего уровня. Сообщение считается высокоуровневым, когда оно не имеет ссылки на родителя или когда указанный родительский элемент не существует в наборе.
Сообщения «m1» и «m6» являются верхними уровнями, потому что «m9» и «m7» не находятся в данном наборе. Сообщение «m3» находится в потоке «m1», несмотря на ссылку на несуществующий «m8» — оно имеет других существующих родителей, которые связывают его с «m1».

У меня вопрос, как это сделать, и как это сделать эффективно? Любая помощь будет оценена.

ОБНОВИТЬ:

Я придумал, чтобы сначала поменять эти отношения, чтобы получилось так:

array (
'm9' => array ('m1'), # this would be rejected
'm3' => array ('m5', 'm4'),
'm4' => array ('m5'),
'm2' => array ('m5', 'm3', 'm4'),
'm1' => array ('m2', 'm3'),
'm8' => array ('m3'), # this would be rejected
'm7' => array ('m6'), # this would be rejected
)

Затем я бы добавил ключи «m6» и «m5» без дочерних элементов, поскольку они существуют во входных ключах, но не в преобразованном массиве.

Теперь у меня есть все отношения parent => children, которые можно найти во входных данных. После сравнения ключей этого массива с входным массивом я могу отклонить ключи «m9», «m8» и «m7» как несуществующие.

Наконец, массив будет выглядеть так:

array (
'm3' => array ('m5', 'm4'),
'm4' => array ('m5'),
'm2' => array ('m5', 'm3', 'm4'),
'm1' => array ('m2', 'm3'),
'm6' => array(),
'm5' => array()
)

Что мне нужно сделать сейчас, так это как-то сгладить эту структуру. Мне нужно найти каждого родителя p1 это тоже ребенок от другого родителя p2 и добавить p1 дети в p2 дети.
Я не знаю, как сделать это иначе, чем многократно повторять эти массивы, но здесь это не вариант.

0

php threaded-comments

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Это казалось интересным испытанием для меня. Чего я добился до сих пор:

Прежде всего, можно избавиться от сирот:

$a = array (
'm1' => array ('m9'),
'm5' => array ('m3', 'm4', 'm2'),
'm2' => array ('m1'),
'm3' => array ('m2', 'm1', 'm8'),
'm6' => array ('m7'),
'm4' => array ('m3', 'm2'),
);

$f = array_map(function($v) use (&$a) {
$k = key($a); next($a);
$vals = array_filter($v, function($el) use ($a) {
return isset($a[$el]);
});
return empty($vals) ? [$k] : $vals;
}, $a);

Последний дает отображение массива родители в массивы детей.

Если у вас есть любимый array_flatten функция под рукой:

function array_flatten($array, $return) {
for($x = 0; $x <= count($array); $x++) {
if(isset($array[$x]) && is_array($array[$x])) {
$return = array_flatten($array[$x], $return);
} else {
if(isset($array[$x])) {
$return[] = $array[$x];
}
}
}
return $return;
}

Теперь мы можем использовать функцию ниже, чтобы пройтись по дереву:

function resolve_parents(&$f) {
array_walk($f, function(&$v, $k) use(&$f) {
if(!is_array($v)) { // great! that’s what we needed
$f[$k] = $v;
} else if(count($v) > 1) { // many children left
$f[$k] = array_unique(
array_flatten(
array_map(function($v) use(&$f) {
return $f[$v];
}, $v),
array())
);
} else {  // great, one child left, store it as result
$f[$k] = $v[0];
};
});
}

Ну, это дает нам разрешение на один шаг вверх. Запустив его столько раз, сколько необходимо (проверьте, что нет array как значения ⇒ все решено):

function check_result($arr) {
return array_reduce($arr, function($memo, $v) {
return $memo = $memo && !is_array($v); }, true);
}
while(!check_result($f)) resolve_parents($f);

в итоге мы получим массив:

// Array
// (
//    [m1] => m1
//    [m5] => m1
//    [m2] => m1
//    [m3] => m1
//    [m6] => m6
//    [m4] => m1
// )

Что, по-видимому, является ответом на ваш вопрос.

К сожалению, путь выше не является ни элегантным, ни доказанным, чтобы быть эффективным. Я просто оставил это здесь на случай, если код может намекнуть вам.

Если у вас есть какие-либо вопросы, не стесняйтесь спрашивать.

0