Crea array multi-dimensionale con l'algoritmo Utilizzo di dati in array monodimensionale

Question

Ho un array monodimensionale di oggetti PHP. Ogni oggetto ha due attributi, un attributo è ID univoco dell'oggetto e l'altro è l'ID univoco di un altro oggetto nella matrice che è suo genitore. Ad esempio:

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)
  }
}

Ho bisogno di convertire questo array monodimensionale in un array multi-dimensionale. Ho preso un paio di colpi in questo, ma non riesco a trovare un modo per farlo fare senza avere un ciclo per ogni livello di nidificazione. L'algoritmo deve essere in grado di adattarsi a ipoteticamente infiniti livelli di nidificazione. Ho provato con alcune tecniche di ricorsione ma non ho mai ottenuto è abbastanza di destra.

Per aggiungere un po 'di complessità, gli oggetti nella matrice che sto ottenendo non sono sempre in un ordine sensical. Ho cercato di replicare questo nel mio esempio di cui sopra; si noterà che l'oggetto con l'ID del 3 arriva nella matrice prima che l'oggetto con l'ID di 2. Così il loro sarà probabilmente un algoritmo di ordinamento coinvolti pure.

Idealmente l'esempio precedente risulterebbe qualcosa di simile:

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

                )

        )

)

Answer 1

Prova questo 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);

Ho usato una tabella di ricerca ($idtable) per gli ID per accedere direttamente ai nodi.

Answer 2

Così, proprio come un precursore - Non lo so php, davvero a tutti. Sono principalmente uno sviluppatore linguaggio C-style (aka c, c Obiettivo e Java). Così alcuni di questo può essere più difficile da fare in PHP, ma qui è il tentativo che vorrei fare:

//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;
            }
        }
    }
}

Un paio di note: Io parto dal presupposto che si sta passando tutto intorno con i puntatori. Se si eseguono copie degli oggetti, è più difficile, ma non impossibile. Sono anche supponendo che si può modificare la dimensione della matrice in modo dinamico. Anche in questo caso, io non sono troppo consapevole di php - se non è possibile farlo, allora si avrebbe bisogno di un modo procedurale per fare questo comportamento. In Java vorrei utilizzare un tipo di elenco, o semplicemente copiare la matrice e ripristinare di nuovo.

La chiave di questo lavoro algoritmo è che i bambini sono sottoposti a loro genitore - ovunque si trovino - in una sola passata. Ciò significa che, non importa l'ordine, la gerarchia verrà creato in quel singolo passaggio. Se avete bisogno della matrice wrapper il genitore che si mostra nel tuo esempio, si può semplicemente aggiungere qualcosa di simile alla fine del codice:

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

Spero che questo aiuti.