Créer une matrice multi-dimensionnelle avec l'algorithme Utilisation des données dans Tableau unidimensionnelles

Question

I ai un réseau mono-dimensionnel d'objets PHP. Chaque objet possède deux attributs, un attribut est unique ID de l'objet et l'autre est l'identifiant unique d'un autre objet dans le tableau qui est son parent. Par exemple:

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

Je dois convertir ce tableau une seule dimension dans un tableau multidimensionnel. J'ai pris quelques coups de couteau à cela, mais je ne peux pas trouver un moyen pour le faire sans avoir une boucle pour chaque niveau d'imbrication. L'algorithme doit être en mesure de s'adapter à des niveaux infinis hypothétiquement d'imbrication. Je l'ai essayé d'utiliser des techniques de récursion mais je ne l'ai jamais eu tout à fait raison.

Pour ajouter un peu de complexité, les objets du tableau que je reçois ne sont pas toujours dans un ordre sensical. J'ai essayé de reproduire dans mon exemple ci-dessus; vous remarquerez que l'objet avec l'ID de 3 vient dans le tableau avant que l'objet avec l'ID de 2. Ainsi, leur sera probablement un algorithme de tri impliqués.

Idéalement, l'exemple ci-dessus tournerait quelque chose comme ceci:

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

                )

        )

)

Answer 1

Essayez cet algorithme:

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

I utilisé une table de consultation (de $idtable) pour les ID pour accéder directement aux noeuds.

Answer 2

Alors, comme un précurseur - Je ne sais pas php, vraiment du tout. Je suis avant tout un développeur de langage c style (alias c, c et objectif Java). Donc, une partie de cela peut être plus difficile à faire en php, mais voici la tentative que je ferais:

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

Quelques notes: Je suppose que vous passez tout autour avec des pointeurs. Si vous faites des copies des objets, il est plus difficile, mais pas impossible. Je suis aussi en supposant que vous pouvez modifier dynamiquement la taille du tableau. Encore une fois, je ne suis pas trop au courant de php - si vous ne pouvez pas faire cela, vous aurez alors besoin d'une manière procédurale de faire ce comportement. En Java j'utiliser un type de liste, ou tout simplement copier le tableau et le réinitialiser à nouveau.

La clé de ce travail d'algorithme est que les enfants sont placés sous leurs parents - où qu'ils se trouvent - en un seul passage. Cela signifie que, peu importe l'ordre, la hiérarchie sera créé dans ce seul passage. Si vous avez besoin du tableau d'emballage autour du parent que vous présentez dans votre exemple, vous pouvez simplement ajouter quelque chose comme ceci à la fin du code:

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

Hope this helps.