[Articolo] Strutture gerarchiche su database (Articolo completo)

[mircov]

Non è applicabile a meno che non si crei un apposito metodo move. Quando viene inserito un nuovo nodo lo stesso non viene inserito nel mezzo dell'albero ma alla fine. Il tuo metodo sarebbe applicabile eliminando tutte le categorie che vengono immediatamente dopo quella da spostare ed inseirle nuovamente nelle nuove posizioni.

[skidx]

Originariamente inviato da mircov
Quando viene inserito un nuovo nodo lo stesso non viene inserito nel mezzo dell'albero ma alla fine.

Come ho detto prima, non ho visto le vostre librerie, ma ci sono metodi di inserimento per inserire un nodo tranquillamente all'interno dell'albero, nella posizione prescelta. Io facevo riferimento a questi metodi.

[skidx]

Non ho letto tutte le librerie citate, ho dato solo uno sguardo alla classe che Andrea ha messo su PHPClasses.
Per spostare un nodo ho visto che crea una tabella temporanea, siccome non mi piaceva ho perso un po' di tempo a scrivere un altro metodo (che sicuramente qualcuno altrove avrà già trovato, non penso di aver inventato nulla).

In ogni modo, con il metodo che ho scritto si può spostare un qualsiasi sottoalbero (un nodo con tutti gli eventuali discendenti) in qualsiasi posizione (prima di un altro nodo, dopo un altro nodo, come figlio di un nodo foglia) utilizzando solo una SELECT (senza JOIN o Subquery) e 4 UPDATE.

Considerando che per l'inserimento servono UNA INSERT e 2 UPDATE, mi sembra sia abbastanza buono, come risultato.

Se può interessare posto il codice, così magari mi aiutate a trovare eventuali bug.
Se non interessa... pazienza

[Fabio Heller]

A me interessa

[skidx]

Originariamente inviato da Fabio Heller
A me interessa

Posto il pezzo di codice.
Unico requisito è che i campi tree_left e tree_right devono essere interi con segno, non UNSIGNED come nel modello originale.

In $catId ho l'id del sottoalbero da spostare, in $destId quello di destinazione.
La variabile $pos identifica il tipo di spostamento.
- 'parent' indica che il sottoalbero deve essere spostato come figlio del nodo destinazione (che deve essere una foglia).
'after' indica l'inserimento nella posizione successiva al nodo destinazione.
'before' indica l'inserimento prima del nodo destinazione.
Ci sono 8 casi, a seconda della posizione del nodo da spostare rispetto alla destinazione. Molto probabilmente si possono accorpare e generalizzare, questa è una prima stesura, non ho badato a ottimizzare nient'altro che il numero e il peso delle query.

[supersaibal]

$dest = array();
$cat = array();
$st = $this->DB->query("SELECT tree_id, tree_left, tree_right, (tree_right - tree_left + 1) AS tree_width FROM ".$this->treeTable." WHERE tree_id = ".$this->DB->quote($catId)." OR  tree_id = ".$this->DB->quote($destId));
while($row = $st->fetch(PDO::FETCH_ASSOC))
{
	if($row['tree_id'] == $catId)
		$cat = $row;
	elseif($row['tree_id'] == $destId)
		$dest = $row;
}
if(!$cat)
{
	$this->error = array('category:E_NODE_NOT_FOUND', $catId);
	$this->DB->rollBack();
	return FALSE;
}
if(!$dest)
{
	$this->error = array('category:E_NODE_NOT_FOUND', $destId);
	$this->DB->rollBack();
	return FALSE;
}

if($dest['tree_left'] > $cat['tree_left'] && $dest['tree_left'] < $cat['tree_right'])
{
	$this->error = array('category:E_MOVE_IN_LOOP');
	$this->DB->rollBack();
	return FALSE;
}

switch($pos)
{
	case 'parent':
		if($dest['tree_right'] != ($dest['tree_left'] + 1))
		{
			$this->error = array('category:E_NODE_NOT_GOOD_PARENT', $destId);
			$this->DB->rollBack();
			return FALSE;
		}
		
		if($dest['tree_left'] < $cat['tree_left'])
		{
			// caso A
			$offset = $cat['tree_left'] - $dest['tree_left'] - 1;
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = -(tree_left - ".$offset."), tree_right = -(tree_right - ".$offset.") WHERE tree_left BETWEEN ".$cat['tree_left']." AND ".$cat['tree_right']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = tree_left + ".$cat['tree_width']." WHERE tree_left > 0 AND tree_left > ".$dest['tree_left']." AND tree_left < ".$cat['tree_left']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_right = tree_right + ".$cat['tree_width']." WHERE tree_left > 0 AND tree_right >= ".$dest['tree_right']." AND tree_right < ".$cat['tree_left']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = -(tree_left), tree_right = -(tree_right) WHERE tree_left < 0");
		}
		else
		{
			// caso B
			$offset = $dest['tree_left'] - $cat['tree_left'] + 1 - $cat['tree_width'];
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = -(tree_left + ".$offset."), tree_right = -(tree_right + ".$offset.") WHERE tree_left BETWEEN ".$cat['tree_left']." AND ".$cat['tree_right']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = tree_left - ".$cat['tree_width']." WHERE tree_left > 0 AND tree_left > ".$cat['tree_left']." AND tree_left <= ".$dest['tree_left']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_right = tree_right - ".$cat['tree_width']." WHERE tree_left > 0 AND tree_right > ".$cat['tree_right']." AND tree_right < ".$dest['tree_left']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = -(tree_left), tree_right = -(tree_right) WHERE tree_left < 0");
		}
	break;

	case 'after':
		if($dest['tree_right'] < $cat['tree_left'])
		{
			// caso C
			$offset = $cat['tree_left'] - $dest['tree_right'] - 1;
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = -(tree_left - ".$offset."), tree_right = -(tree_right - ".$offset.") WHERE tree_left BETWEEN ".$cat['tree_left']." AND ".$cat['tree_right']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = tree_left + ".$cat['tree_width']." WHERE tree_left > 0 AND tree_left > ".$dest['tree_right']." AND tree_left < ".$cat['tree_left']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_right = tree_right + ".$cat['tree_width']." WHERE tree_left > 0 AND tree_right > ".$dest['tree_right']." AND tree_right < ".$cat['tree_left']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = -(tree_left), tree_right = -(tree_right) WHERE tree_left < 0");
		}
		elseif($dest['tree_right'] > $cat['tree_left'] && $dest['tree_left'] < $cat['tree_left'])
		{
			// caso D
			$offset = $dest['tree_right'] - $cat['tree_left'] + 1 - $cat['tree_width'];
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = -(tree_left + ".$offset."), tree_right = -(tree_right + ".$offset.") WHERE tree_left BETWEEN ".$cat['tree_left']." AND ".$cat['tree_right']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = tree_left - ".$cat['tree_width']." WHERE tree_left > 0 AND tree_left > ".$cat['tree_right']." AND tree_right < ".$dest['tree_right']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_right = tree_right - ".$cat['tree_width']." WHERE tree_left > 0 AND tree_right > ".$cat['tree_right']." AND tree_right <= ".$dest['tree_right']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = -(tree_left), tree_right = -(tree_right) WHERE tree_left < 0");
		}
		else
		{
			// caso E
			$offset = $dest['tree_right'] - $cat['tree_left'] + 1 - $cat['tree_width'];
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = -(tree_left + ".$offset."), tree_right = -(tree_right + ".$offset.") WHERE tree_left BETWEEN ".$cat['tree_left']." AND ".$cat['tree_right']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = tree_left - ".$cat['tree_width']." WHERE tree_left > 0 AND tree_left > ".$cat['tree_right']." AND tree_left <= ".$dest['tree_right']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_right = tree_right - ".$cat['tree_width']." WHERE tree_left > 0 AND tree_right > ".$cat['tree_right']." AND tree_right <= ".$dest['tree_right']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = -(tree_left), tree_right = -(tree_right) WHERE tree_left < 0");
		}
	break;
	
	case 'before':
		if($dest['tree_left'] < $cat['tree_left'] && $dest['tree_right'] < $cat['tree_left'])
		{
			// caso F
			$offset = $cat['tree_left'] - $dest['tree_left'];
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = -(tree_left - ".$offset."), tree_right = -(tree_right - ".$offset.") WHERE tree_left BETWEEN ".$cat['tree_left']." AND ".$cat['tree_right']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = tree_left + ".$cat['tree_width']." WHERE tree_left > 0 AND tree_left >= ".$dest['tree_left']." AND tree_left < ".$cat['tree_left']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_right = tree_right + ".$cat['tree_width']." WHERE tree_left > 0 AND tree_right >= ".$dest['tree_left']." AND tree_right < ".$cat['tree_right']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = -(tree_left), tree_right = -(tree_right) WHERE tree_left < 0");
		}
		elseif($dest['tree_left'] < $cat['tree_left'] && $dest['tree_right'] > $cat['tree_left'])
		{
			// caso G
			$offset = $cat['tree_left'] - $dest['tree_left'];
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = -(tree_left - ".$offset."), tree_right = -(tree_right - ".$offset.") WHERE tree_left BETWEEN ".$cat['tree_left']." AND ".$cat['tree_right']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = tree_left + ".$cat['tree_width']." WHERE tree_left > 0 AND tree_left >= ".$dest['tree_left']." AND tree_left < ".$cat['tree_left']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_right = tree_right + ".$cat['tree_width']." WHERE tree_left > 0 AND tree_right < ".$dest['tree_right']." AND tree_right < ".$cat['tree_right']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = -(tree_left), tree_right = -(tree_right) WHERE tree_left < 0");
		}
		else
		{
			// caso H
			$offset = $dest['tree_left'] - $cat['tree_left'] - $cat['tree_width'];
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = -(tree_left + ".$offset."), tree_right = -(tree_right + ".$offset.") WHERE tree_left BETWEEN ".$cat['tree_left']." AND ".$cat['tree_right']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = tree_left - ".$cat['tree_width']." WHERE tree_left > 0 AND tree_left > ".$cat['tree_left']." AND tree_left < ".$dest['tree_left']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_right = tree_right - ".$cat['tree_width']." WHERE tree_left > 0 AND tree_right > ".$cat['tree_right']." AND tree_right < ".$dest['tree_left']);
			$this->DB->exec("UPDATE ".$this->treeTable." SET tree_left = -(tree_left), tree_right = -(tree_right) WHERE tree_left < 0");
		}
	break;
}

[/supersaibal]

[mircov]

Onestamente non ho leto il metodo perchè ora non sono proprio in grado di capire. Però ho notato che usi un metodo DB. Che classe è?

[skidx]

Originariamente inviato da mircov
Onestamente non ho leto il metodo perchè ora non sono proprio in grado di capire. Però ho notato che usi un metodo DB. Che classe è?

E' una classe derivata di PDO, funziona nello stesso modo.

Il metodo è molto semplice concettualmente: invece che spostare il sottoalbero su una tabella temporanea, gli assegno temporaneamente i campi left e right negativi, rendendo quindi quei nodi "invisibili" agli altri 2 update, per poi ripristinarli con l'ultimo.