Toon posts:

[MySQL] boomstuctuur - probleem bij nodes verplaatsen

Pagina: 1
Acties:

dinsdag 18 mei 2004 22:37

Acties:
  • 0 Henk 'm!

Verwijderd

Topicstarter
Ik ben bezig met het schrijven van een PHP-class voor het maken/verwerken van een boomstuctuur, opgeslagen in mysql.
Hier bij maak ik gebruik van een zgn. Modified Preorder Tree Traversal - constructie (ik kon er niks overvinden op got, ik vraag me af of er veel mensen zijn die dit kennen :? )
Een groot voordeel hiervan is dat je niet te maken hebt met recursie, wat ik probber te vermijden.
Nadeel is dat bij het aanpassen van de boom er veel waardes geupdate moeten worden waardoor het programeren vrij ingewikkeld wordt (vandaar mijn poging tot deze class)

Ik ben al een heel eind, ik heb al methodes voor het toevoegen, verwijderen en verwisselen van nodes, het verkrijgen van het path van de root naar een node en het 'tekenen' van de boom

het probleem ligt bij het verplaatsen van nodes. Ik zit hier al 2 dagen op te ploeteren, maar ik loop nu echt vast en kom ten einde raad hier hulp zoeken :)

Hier onder wat ik totnutoe heb:
PHP:
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157

  function moveNode ($srcnode, $dstnode) {
    $src = $this->getNodeInfo ($srcnode);
    $dst = $this->getNodeInfo ($dstnode);
        
    if (!$src && !$dst) return false;
    if ($srcnode == $dstnode || ($dst[$this->getCol('LFT')] >= $src[$this->getCol('LFT')] and $dst[$this->getCol('LFT')] <= $src[$this->getCol('RGT')]) || $src[$this->getCol('PID')] == $dstnode) {
            return false;
        }

        $pts = $this->getPath ($srcnode, $this->getCol('NID').', '.$this->getCol('LFT').', '.$this->getCol('RGT'));
        $ptd = $this->getPath ($dstnode, $this->getCol('NID').', '.$this->getCol('LFT').', '.$this->getCol('RGT'));

        $key=0; 
        while ($pts[$key][$this->getCol('NID')] == $ptd[$key][$this->getCol('NID')]) $key++;
        $limit1 = (!$pts[$key][$this->getCol('NID')])?$pts[$key-1]:$pts[$key];
        $limit2 = (!$ptd[$key][$this->getCol('NID')])?$ptd[$key-1]:$ptd[$key];
        
        $lftlimit = min ($limit1[$this->getCol('LFT')], $limit1[$this->getCol('RGT')], $limit2[$this->getCol('LFT')], $limit2[$this->getCol('RGT')]);
        $rgtlimit = max ($limit1[$this->getCol('LFT')], $limit1[$this->getCol('RGT')], $limit2[$this->getCol('LFT')], $limit2[$this->getCol('RGT')]);
                
        
    if ($dst[$this->getCol('LFT')] < $src[$this->getCol('LFT')]) { //leftmove
                    
      $tomove = $src[$this->getCol('LFT')]-$dst[$this->getCol('LFT')]-1;
      $moving = $src[$this->getCol('RGT')]-$src[$this->getCol('LFT')]+1;

        $sql = 'UPDATE ' . $this->getTreeTable(). ' ';
      $sql.= 'SET ';
// (...) regel voor het updaten van de level van de node, deze werkt
      $sql.= $this->getCol('LFT').' = IF('.$this->getCol('LFT').' <= '.$dst[$this->getCol('LFT')].', ';
      $sql.=                            $this->getCol('LFT').', ';
      $sql.=                            'IF('.$this->getCol('LFT').' >= '.$src[$this->getCol('LFT')].', ';
      $sql.=                              $this->getCol('LFT').'-'.$tomove.', ';
      $sql.=                              $this->getCol('LFT').'+'.$moving.')), ';
      $sql.= $this->getCol('RGT').' = IF('.$this->getCol('RGT').' > '.$src[$this->getCol('RGT')].', ';
      $sql.=                            $this->getCol('RGT').', ';
      $sql.=                            'IF('.$this->getCol('RGT').' > '.$src[$this->getCol('LFT')].', ';
      $sql.=                              $this->getCol('RGT').'-'.$tomove.', ';
      $sql.=                              $this->getCol('RGT').'+'.$moving.')) ';
      $sql.= 'WHERE ';
      $sql.= $this->getCol('LFT').' BETWEEN '.$lftlimit.' AND '.$rgtlimit;

    } else { #right
//bij een rightmove heb k nog geen problemen gevonden.
    }
    $sql2 = 'UPDATE ' . $this->getTreeTable(). ' ';
    $sql2.= 'SET ';
    $sql2.= $this->getCol('PID').' = '.$dst[$this->getCol('NID')].' ';
    $sql2.= 'WHERE ';
    $sql2.= $this->getCol('NID').' = '.$src[$this->getCol('NID')];
    $this->DB->runQuery ( $sql2 );
        return $this->DB->runQuery ( $sql );
        //echo $sql;
  }


8)7

In de meeste gevallen werkt dit zoals het hoort, het probleem ligt vooral bij het uitsluiten van nodes die niet geupdate hoeven te/mogen worden.
Nu worden de nodes die links van de destination-node, maar wel in dezelfde tak liggen ook geupdate; deze moeten uitgesloten worden.

Ik vraag me af of het zo duidlijk is :? maar toch maar een poging:
Zijn er hier mensen die een oplossing/voorbeeld script hebben. Of weet iemand een goede manier om dit probleem aan te pakken want ik zie door de bomen het bos niet meer :X

[ Voor 21% gewijzigd door Verwijderd op 18-05-2004 22:39 ]

woensdag 19 mei 2004 13:01

Acties:
  • 0 Henk 'm!
  • bigbeng
  • Registratie: Augustus 2000
  • Laatst online: 26-11-2021

bigbeng

Ik heb even zitten kijken onder die link en het ziet er interessant uit.

Nu vraag ik me een beetje af wat je met een move bedoelt Is het de bedoeling dat de gewraakte node van zijn positie in de boom verwijderd wordt en vervolgens op een andere plek er weer ingehangen? Zo ja, dan zie ik niet in waarom je daar een andere functie voor moet schrijven als je de verwijderfunctie en de toevoegfunctie al hebt.

Gaat het om het verplaatsen van een node en al zijn subnodes dan kun je niet anders dan een rebuild tree (zie ook die link van jou) uit te voeren. Dit zou je kunnen localiseren op de eerste node die parent is van zowel de source als de destination node. Of als source of destination een parent van de ander is, dan neem je die als uitgangspunt.

woensdag 19 mei 2004 13:20

Acties:
  • 0 Henk 'm!
  • ACM
  • Registratie: Januari 2000
  • Niet online

ACM

Software Architect

Werkt hier

Zoek es op 'nested set' of 'celko tree', Joe Celko noemt bovenstaande (min of meer zijn vinding/door hem populair gemaakt) namelijk Nested Set.
Joe Celko heeft overigens ook een boek hierover geschreven "Joe Celko's SQL for Smarties : Trees and Hierarchies" (isbn 1558609202 ). Hoeveel daar over het wijzigen van deze bomen staat (verschuiven enzo) weet ik niet, maar wellicht heb je er wat aan of aan de andere zoektermen.

Ik denk alleen wel dat bigbeng gelijk heeft, toen ik met nested sets aan het werk ging hield ik ook de "gewone" boomstructuur (een parentid per child) bij, waardoor ik de boom naar believen kon herbouwen. Nadeel was de extra opslag, voordeel was dat dit soort dingen iets handiger konden (niet sneller ofzo, maar wel handiger).

[ Voor 29% gewijzigd door ACM op 19-05-2004 13:21 ]

woensdag 19 mei 2004 13:54

Acties:
  • 0 Henk 'm!
  • vargo
  • Registratie: Januari 2001
  • Laatst online: 21-09 09:35

vargo

Mag ik je ook adviseren om even naar een PEAR package genaamd Tree te kijken: http://pear.php.net/package/Tree
" The trees can be stored in the DB either as nested trees.
Or as simple trees ('brain dead method'), which use parentId-like structure."

donderdag 20 mei 2004 12:27

Acties:
  • 0 Henk 'm!

Verwijderd

Topicstarter
hier voor werkte ik idd nog met het veranderen van parentID's waarna ik de tree opnieuw liet bouwen.
Maar daar wilde ik nu dus vanaf.

Gisteren ben ik van scratch begonnen met mn functie, en nu weet ik wat ik fout deed.

Er zijn 4 situaties te bedenken, namelijk:
-de nodes voor de te verplaatsen tak (blijven hetzelfde)
-de nodes in de te verplaatsten tak (moeten naar links of rechts)
-de nodes tussen de teverplaatsen tak en de destination-node (moeten naar rechts of links)
-de nodes na de destination node (blijven hetzelfde)

ik had er maar 3, namelijk nodes die hetzelfde moeten blijven, nodes die naar links moeten en nodes die naar rechts moeten |:(

tot nu toe werkt alles zoals het hoort met het volgende code:

PHP:
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

 function moveNode ($srcnode, $dstnode) {
    $src = $this->getNodeInfo ($srcnode);
    $dst = $this->getNodeInfo ($dstnode);
        
    if (!$src && !$dst) return false;
    if ($srcnode == $dstnode || ($dst[$this->getCol('LFT')] >= $src[$this->getCol('LFT')] and $dst[$this->getCol('LFT')] <= $src[$this->getCol('RGT')]) || $src[$this->getCol('PID')] == $dstnode) {
            return false;
        }

        $pts = $this->getPath ($srcnode, $this->getCol('NID').', '.$this->getCol('LFT').', '.$this->getCol('RGT'));
        $ptd = $this->getPath ($dstnode, $this->getCol('NID').', '.$this->getCol('LFT').', '.$this->getCol('RGT'));

        $key=0; 
        while ($pts[$key][$this->getCol('NID')] == $ptd[$key][$this->getCol('NID')]) $key++;
        $limit1 = (!$pts[$key][$this->getCol('NID')])?$pts[$key-1]:$pts[$key];
        $limit2 = (!$ptd[$key][$this->getCol('NID')])?$ptd[$key-1]:$ptd[$key];
        
        $lftlimit = min ($limit1[$this->getCol('LFT')], $limit1[$this->getCol('RGT')], $limit2[$this->getCol('LFT')], $limit2[$this->getCol('RGT')]);
        $rgtlimit = max ($limit1[$this->getCol('LFT')], $limit1[$this->getCol('RGT')], $limit2[$this->getCol('LFT')], $limit2[$this->getCol('RGT')]);
    $moving = $src[$this->getCol('RGT')]-$src[$this->getCol('LFT')]+1;              
        
    if ($dst[$this->getCol('LFT')] < $src[$this->getCol('LFT')]) { //leftmove
                    
      $tomove = $src[$this->getCol('LFT')]-$dst[$this->getCol('LFT')]-1;
            
        $sql = 'UPDATE ' . $this->getTreeTable(). ' ';
      $sql.= 'SET ';
      $sql.= $this->getCol('LVL').' = IF('.$this->getCol('LFT').' BETWEEN '.$src[$this->getCol('LFT')].' AND '. $src[$this->getCol('RGT')].   ', '.$this->getCol('LVL').'-'. $src[$this->getCol('LVL')] . ' + 1 + ' . $dst[$this->getCol('LVL')] . ', '.$this->getCol('LVL').'), ';
            $sql.= $this->getCol('LFT').' = IF('.$this->getCol('LFT').' <= '.$dst[$this->getCol('LFT')].', ';
            $sql.=                                                $this->getCol('LFT').', ';
            $sql.=                                                   'IF('.$this->getCol('LFT').' < '.$src[$this->getCol('LFT')].', ';
            $sql.=                                                      $this->getCol('LFT').'+'.$moving.', ';
            $sql.=                                                       'IF('.$this->getCol('LFT').' < '.$src[$this->getCol('RGT')].', ';
            $sql.=                                                              $this->getCol('LFT').'-'.$tomove.', ';
            $sql.=                                                              $this->getCol('LFT').'))), ';
            $sql.= $this->getCol('RGT').' = IF('.$this->getCol('RGT').' > '.$src[$this->getCol('RGT')].', ';
            $sql.=                                                    $this->getCol('RGT').', ';
            $sql.=                                                   'IF('.$this->getCol('RGT').' > '.$src[$this->getCol('LFT')].', ';
            $sql.=                                                      $this->getCol('RGT').'-'.$tomove.', ';
            $sql.=                                                       'IF('.$this->getCol('RGT').' > '.$dst[$this->getCol('LFT')].', ';
            $sql.=                                                          $this->getCol('RGT').'+'.$moving.', ';
            $sql.=                                                              $this->getCol('RGT').'))) ';                                                                                
      $sql.= 'WHERE ';
      $sql.= $this->getCol('LFT').' BETWEEN '.$lftlimit.' AND '.$rgtlimit;
            
    } else { #right
        
      $tomove = $dst[$this->getCol('LFT')]-$src[$this->getCol('RGT')];
    
        $sql = 'UPDATE ' . $this->getTreeTable(). ' ';
      $sql.= 'SET ';
      $sql.= $this->getCol('LVL').' = IF('.$this->getCol('LFT').' BETWEEN '.$src[$this->getCol('LFT')].'   AND '. $src[$this->getCol('RGT')].   ', '.$this->getCol('LVL').'-'. $src[$this->getCol('LVL')] . ' + 1 + ' . $dst[$this->getCol('LVL')] . ', '.$this->getCol('LVL').'), ';
            $sql.= $this->getCol('LFT').' = IF('.$this->getCol('LFT').' < '.$src[$this->getCol('LFT')].', ';
            $sql.=                                                  $this->getCol('LFT').', ';
            $sql.=                                                   'IF('.$this->getCol('LFT').' < '.$src[$this->getCol('RGT')].', ';
            $sql.=                                                      $this->getCol('LFT').'+'.$tomove.', ';
            $sql.=                                                       'IF('.$this->getCol('LFT').' <= '.$dst[$this->getCol('LFT')].', ';
            $sql.=                                                          $this->getCol('LFT').'-'.$moving.', ';
            $sql.=                                                              $this->getCol('LFT').'))), ';
            $sql.= $this->getCol('RGT').' = IF('.$this->getCol('RGT').' > '.$dst[$this->getCol('LFT')].', ';
            $sql.=                                                  $this->getCol('RGT').', ';
            $sql.=                                                   'IF('.$this->getCol('RGT').' > '.$src[$this->getCol('RGT')].', ';
            $sql.=                                                      $this->getCol('RGT').'-'.$moving.', ';
            $sql.=                                                       'IF('.$this->getCol('RGT').' > '.$src[$this->getCol('LFT')].', ';
            $sql.=                                                          $this->getCol('RGT').'+'.$tomove.', ';
            $sql.=                                                            $this->getCol('RGT').'))) ';
      $sql.= 'WHERE ';
      $sql.= $this->getCol('LFT').' BETWEEN '.$lftlimit.' AND '.$rgtlimit;
    }
    $sql2 = 'UPDATE ' . $this->getTreeTable(). ' ';
    $sql2.= 'SET ';
    $sql2.= $this->getCol('PID').' = '.$dst[$this->getCol('NID')].' ';
    $sql2.= 'WHERE ';
    $sql2.= $this->getCol('NID').' = '.$src[$this->getCol('NID')];
    $this->DB->runQuery ( $sql2 );
        return $this->DB->runQuery ( $sql );
        //echo $sql;
  }
vargo schreef op 19 mei 2004 @ 13:54:
Mag ik je ook adviseren om even naar een PEAR package genaamd Tree te kijken: http://pear.php.net/package/Tree

[...]
hmhm... ook vrij nuttig om te weten idd ;) tnx

donderdag 20 mei 2004 12:47

Acties:
  • 0 Henk 'm!
  • ACM
  • Registratie: Januari 2000
  • Niet online

ACM

Software Architect

Werkt hier

Tipje, je kan je code (veel) leesbaarder, compacter en sneller maken door al die $this->getCol's te vervangen door variabelen, ala:
$lftc = $this->getCol('LFT');

en dan die $lftc gebruiken in je code.
Ter illustratie:
PHP:
1
2
3
4
5
6

if ($srcnode == $dstnode || ($dst[$this->getCol('LFT')] >= $src[$this->getCol('LFT')] 
&& $dst[$this->getCol('LFT')] <= $src[$this->getCol('RGT')]) || $src[$this->getCol('PID')] == $dstnode) { }

// vs:
if ($srcnode == $dstnode || ($dst[$lftc] >= $src[$lftc] && $dst[$lftc] <= $src[$rgtc]) || $src[$pidc] == $dstnode) 
{ }


Die $sql .= is trouwens ook nergens voor nodig, alleen een . is voldoende (of gewoon de string op de volgende regel door laten gaan).

[ Voor 11% gewijzigd door ACM op 20-05-2004 13:09 ]

Pagina: 1
Reageer

Apple iPhone 16e LG OLED evo G5 Google Pixel 10 Samsung Galaxy S25 Star Wars: Outlaws Nintendo Switch 2 Apple AirPods Pro (2e generatie) Sony PlayStation 5 Pro

Tweakers is onderdeel van DPG Media B.V.
Alle rechten voorbehouden - Auteursrecht © 1998 - 2025 • Hosting door TrueFullstaq