Erstellen Sie Multi-Dimensional Array mit Algorithmus Daten in eindimensionales Array

Question

Ich habe ein eindimensionales Array von PHP-Objekten. Jedes Objekt hat zwei Attribute, ein Attribut ist, das Objekt eindeutige ID und die andere ist die eindeutige ID eines anderen Objekts in dem Array, das der übergeordneten ist. Zum Beispiel:

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

Ich brauche dieses eindimensionale Array in ein mehrdimensionales Array zu konvertieren. Ich habe ein paar Stichen auf diese genommen, aber ich kann nicht einen Weg finden, um es ohne eine Schleife für jede Ebene der Verschachtelung getan. Der Algorithmus muss in der Lage sein, zu hypothetisch unendlich Verschachtelungsebenen anzupassen. Ich habe versucht, einige Rekursion Techniken, aber ich habe es nie ganz richtig bekommen.

Um ein wenig mehr Komplexität, die Objekte in der Anordnung, die ich erhalte nicht immer in einer sensical Ordnung. Ich habe versucht, das oben in meinem Beispiel zu replizieren; werden Sie feststellen, dass das Objekt mit der ID 3 vor dem Objekt in dem Array kommt mit der ID 2. So ihren Willen wahrscheinlich ein Sortieralgorithmus als auch beteiligt sein.

Im Idealfall der obige Beispiel würde wie folgt ausfallen:

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

                )

        )

)

Answer 1

Versuchen Sie diesen Algorithmus:

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

ich eine Lookup-Tabelle verwendet ($idtable) für die IDs direkt an den Knoten zu springen.

Answer 2

Also, nur als Vorläufer - ich weiß nicht, php, wirklich überhaupt nicht. Ich bin in erster Linie ein c-style Sprache Entwickler (auch bekannt als c, Objective C und Java). So einige dieser kann schwieriger sein, in PHP zu tun, aber hier ist der Versuch, den ich machen könnte:

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

Ein paar Anmerkungen: Ich gehe davon aus Sie sind vorbei alles um mit Zeigern. Wenn Sie Kopien der Objekte machen, ist es schwieriger, aber nicht unmöglich. Ich gehe davon aus können Sie auch die Größe des Arrays dynamisch ändern. Auch hier bin ich nicht zu wissen, php - wenn Sie das nicht tun, dann würden Sie eine Verfahrensweise benötigen, dieses Verhalten zu tun. In Java würde ich eine Liste Typen verwenden, oder einfach nur das Array kopieren und setzen Sie es erneut.

Der Schlüssel zu diesem Algorithmus Arbeits ist, dass die Kinder unter ihren Eltern gestellt werden - wo immer sie sind - in einem Durchgang. Das bedeutet, dass, unabhängig von der Reihenfolge, wird die Hierarchie in diesem Arbeitsgang erstellt werden. Wenn Sie den Wrapper-Array um die Eltern brauchen, die Sie in Ihrem Beispiel zeigen, können Sie einfach so etwas wie dies bis zum Ende des Codes hinzu:

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

Hope, das hilft.