Crear una matriz multidimensional con el algoritmo Uso de Datos en Array unidimensional

Question

I tiene una matriz unidimensional de los objetos de PHP. Cada objeto tiene dos atributos, uno es único de identificación del objeto y el otro es el ID exclusivo de otro objeto de la matriz que es su padre. Por ejemplo:

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

Necesito convertir esta matriz unidimensional en una matriz multidimensional. Me he tomado unas cuantas puñaladas en esto, pero no puedo encontrar una manera de lograr que se haga sin tener un bucle para cada nivel de anidamiento. El algoritmo tiene que ser capaz de adaptarse a hipotéticamente infinitos niveles de anidamiento. He intentado usar algunas técnicas de recursividad, pero nunca he conseguido bastante bien.

Para añadir un poco de complejidad, los objetos de la matriz que estoy recibiendo no siempre están en un orden sensical. Traté de replicar esto en el ejemplo anterior; se dará cuenta de que el objeto con el ID de 3 viene en la matriz antes de que el objeto con el identificador de 2. Por lo que su probable que haya un algoritmo de ordenación involucrados también.

Lo ideal sería que el ejemplo anterior puede resultar algo como esto:

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

                )

        )

)

Answer 1

Trate de 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);

I utilizado una tabla de búsqueda ($idtable) para los identificadores para saltar directamente a los nodos.

Answer 2

Entonces, así como un precursor - No sé php, realmente en absoluto. Soy ante todo un desarrollador de lenguaje C-estilo (también conocido como C, C Objetivo y Java). Así que algo de esto puede ser más difícil de hacer en php, pero aquí es el intento que haría:

//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 par de notas: Estoy asumiendo que usted está pasando todo a su alrededor con los punteros. Si va a realizar copias de los objetos, es más difícil, pero no imposible. También estoy asumiendo que usted puede cambiar el tamaño de la matriz dinámica. Una vez más, no estoy muy al tanto de php - si usted no puede hacer eso, entonces se necesitaría una forma de procedimiento para hacer este comportamiento. En Java Me gustaría utilizar un tipo de lista, o simplemente copiar la matriz y reiniciarlo de nuevo.

La clave de este trabajo algoritmo es que los niños son colocados bajo su padre - dondequiera que estén - en una sola pasada. Esto significa que, sin importar el orden, la jerarquía se creará en esa sola pasada. Si necesita la matriz envoltura alrededor de los padres que mostrar en su ejemplo, sólo tiene que añadir algo como esto al final del código:

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

Espero que esto ayude.