[tree] nested set naar adjacency

[Genoil]

ik heb een tree in m'n database opgeslagen volgens de nested set methode. nu ben ik bezig met een manier om de lijst die ik terug krijg als ik de tree met 1 query ophaal om te zetten naar een geneste set objecten, die ik dan later bijvoorbeeld gemakkelijk kan omzetten naar een geneste <ul> in html, waarbij ik bijvoorbeeld meerdere niveau's kan expanden of collapsen. Dit laatste gaat nml. lastig als je de lijst niet omzet en de boomstructuur visualiseert door in te springen ipv <ul>'s te nesten.

op internet genoeg te vinden over adjacency naar nested, maar andersom ho maar.

nou heb ik wel een ranzige oplossing gevonden mbv PHP's eval():

PHP:

<?
function get_tree($root_name = "root", $node_table = "node", $leaf_table = "page", $root_field = "name") {
    $root   = db_select_one("SELECT * ".
                            "FROM $node_table AS n, $leaf_table as p ".
                            "WHERE p.node_id = n.id AND p.$root_field = '$root_name'");
    
    if($root) { 
        $nodes  = db_select("SELECT * ".
                            "FROM $node_table AS n, $leaf_table as p ".
                            "WHERE p.node_id = n.id AND n.lft >= $root->lft AND n.rgt <= $root->rgt ".
                            "ORDER BY n.lft ASC");
        
    }
    else {
        $nodes = array();
    } 
    
    return is_array($nodes) ? $nodes : array();
} 

function nested_to_adjacency($nodes) {
    $stack   = array();
    $tree    = array();
    echo "\n";
    foreach($nodes as $node) {
        $right = $node->rgt;
        if (count($stack) > 0) {
           
           while ($stack[count($stack)-1] < $right) {
               array_pop($stack);
           }
        }
        
        $label = $node->title;
        echo str_repeat("\t",count($stack)).$label."\n";
        
        if (count($stack) > 0) {
            $stackIndex = implode("][",$stack);
            eval("if(!isset(\$tree[".$stackIndex."])) \$tree[".$stackIndex."] = array();");
        }
        
        array_push($stack, $right);
        eval("\$tree[".implode("][",$stack)."]['node'] = \$node;"); 
    }
    print_r($tree);
}
?>

regel 35 laat (in text, geen html) zien hoe je met inspringen de tree visualiseert. deze methode heb ik gewoon gejat van Celko en het beruchte sitepoint document hierover. op regels 39 en 43 wordt er met de botte bijl een geneste array van gemaakt. maar ik zoek dus een wat nettere methode om dit te doen...

[ Voor 10% gewijzigd door Genoil op 16-03-2006 16:32 ]

[Soultaker]

Ik heb de code niet bij de hand, maar ik heb dit zelf ook eens gedaan. Dan sloeg ik behalve die 'lft' en 'rgt' (de pre-order resp. post-order id) ook een parent id op en sloeg ik references naar arrays op. Dit is misschien wat lastig in PHP; daarin kun je waarschijnlijk een hele andere aanpak gebruiken door van achteren naar voren werken:

code:

children = [ ]
voor elke rij r:
    construeer node n met children[r.id] als kinderen
    (optioneel: verwijder children[r.id])
    voeg n toe aan children[r.parent_id]

Op het eind zit je boom dan in children[root_id] (of als je tussendoor entries verwijderd hebt, is het gewoon het eerste en enige element). Let op dat deze constructiemethode alleen werkt als je de rijen van achteren naar voren hebt geordend (dus op r.rgt aflopend). Als je in de boom de rijen wel in de goede volgorde wil hebben moet je ze op de laatste regel in de lus voorin invoegen in plaats van achterin, of (wat misschien efficienter is) op het einde een pass door de hele boom maken om alle siblings om te draaien.

Heel veel efficiënter kan het niet, denk ik. Je hebt altijd het probleem dat er platte data uit de database komt en je die zelf naar een recursieve datastructuur om moet zetten.

[ Voor 15% gewijzigd door Soultaker op 19-03-2006 16:52 ]