Criar array multi-dimensional com o algoritmo Usando dados na matriz unidimensional

Question

Eu tenho uma matriz unidimensional de PHP objetos. Cada objeto tem dois atributos, um atributo é identificação única do objeto e a outra é a identificação única de outro objeto na matriz que é seu pai. Por exemplo:

array(3) {
  [0]=>
  object(stdClass)#1 (2) {
    ["ID"]=>
    int(1)
    ["parentID"]=>
    int(0)
  }
  [1]=>
  object(stdClass)#2 (2) {
    ["ID"]=>
    int(3)
    ["parentID"]=>
    int(2)
  }
  [2]=>
  object(stdClass)#3 (2) {
    ["ID"]=>
    int(2)
    ["parentID"]=>
    int(1)
  }
}

Eu preciso converter essa matriz unidimensional em uma matriz multi-dimensional. Tomei alguns golpes neste, mas não consigo encontrar uma maneira de fazê-lo sem ter um loop para cada nível de aninhamento. As necessidades algoritmo para ser capaz de se adaptar a níveis hipoteticamente infinito de aninhamento. Eu tentei usar algumas técnicas de recursão, mas eu nunca tive isso muito bem.

Para adicionar um pouco de complexidade, os objetos na matriz que eu estou recebendo não são sempre em uma ordem sensical. Eu tentei replicar isso no meu exemplo acima; você vai perceber que o objeto com o ID de 3 vem na matriz antes de o objeto com o ID de 2. Portanto, seu provavelmente será um algoritmo de ordenação envolvidos.

O ideal é o exemplo acima iria revelar-se algo como isto:

Array
(
    [0] => Array
        (
            [ID] => 1
            [parentID] => 0
            [0] => Array
                (
                    [ID] => 2
                    [parentID] => 1
                    [0] => Array
                        (
                            [ID] => 3
                            [parentID] => 2
                        )

                )

        )

)

Answer 1

Tente este algoritmo:

// sort objects by parentID
function cmpNodes($a, $b) {
    return $a->parentID - $b->parentID;
}
usort($objects, 'cmpNodes');

// define first node as root of tree
$tree = (array) array_shift($objects);
// lookup table for direct jumps
$idTable = array($tree['ID'] => &$tree);
foreach ($objects as $object) {
    $node = (array) $object;
    // test if parent node exists
    if (!isset($idTable[$node['parentID']])) {
        // Error: parent node does not exist
        break;
    }
    // append new node to the parent node
    $idTable[$node['parentID']][] = $node;
    // set a reference in the lookup table to the new node
    $idTable[$node['ID']] = &$idTable[$node['parentID']][count($idTable[$node['parentID']])-3];
}
// unset($idTable);
var_dump($tree);

Eu usei uma tabela de pesquisa ($idtable) para os IDs de saltar diretamente para os nós.

Answer 2

Assim, apenas como um precursor - Eu não sei php, muito em tudo. Eu sou essencialmente um desenvolvedor linguagem c-estilo (aka c, Objective C e Java). Então, algumas delas podem ser mais difícil de fazer em php, mas aqui é a tentativa que gostaria de fazer:

//the original input array
oldArray;
//the output array
array[] newArray = new array[];

foreach (element : oldArray) {
    //if the element is at the top, put it at the top of the array
    if (element.parentId == 0) {
        newArray.add(element);
    } else {
        //otherwise, find it's parent and put it in the child array of the parent
        for (potentialParent : oldArray) {
            if (potentialParent.id = element.parentId) {
                potentialParent.array.add(element);
                break;
            }
        }
    }
}

Um par de notas: Eu estou supondo que você está passando tudo ao seu redor com ponteiros. Se você estiver fazendo cópias dos objetos, é mais difícil, mas não impossível. Eu também estou supondo que você pode mudar o tamanho da matriz dinamicamente. Novamente, eu não estou muito ciente do php - se você não pode fazer isso, então você precisa encontrar uma maneira processual para fazer esse comportamento. Em Java eu ??iria usar um tipo de lista, ou apenas copiar a matriz e redefini-la novamente.

A chave para este algoritmo de trabalho é que as crianças são colocadas sob o seu pai - onde quer que estejam - em uma passagem. Isto significa que, não importa a ordem, a hierarquia será criada naquele única passagem. Se você precisar a matriz invólucro em torno do pai que você mostra no seu exemplo, você pode simplesmente adicionar algo assim para o fim do código:

finalArray = new array[];
finalArray[0] = newArray;

Espero que isso ajude.