Drzewko left-right, Klasa, PHP 5 Opcje

[bela]

[PHP] pobierz, plaintext 
<?php
class Tree {
	/**
	 * Instance of Creole
	 */
	private $db;
 
	/**
	 * Constructor, initialize Creole
	 *
	 * @param $dsn
	 */
	public function __construct($dsn) {
		$this->db = Creole::getConnection($dsn);;
	}
 
	/**
	 * Adds node to tree
	 *
	 * @param object_id Id of object in system (this is not db id)
	 * @param parent Id of parent - db id
	 */
	public function addNode($object_id, $parent) {
		$rs = $this->db->executeQuery('SELECT `id`, `left`, `right` FROM tree WHERE `id`="' . $parent . '"');
		if($rs->getRecordCount() == 0) {
			$left = 1;
			$right = 2;
		} else {
			while($rs->next()) {
				$left = $rs->getInt('left');
				$right = $rs->getInt('right');
				$parentId = $rs->getInt('id');
			}
		}
		$sql = 'UPDATE tree SET `right` = `right` +2 WHERE `right` >' . ($right - 1);
		$this->db->executeQuery($sql);
 
		$sql = 'UPDATE tree SET `left` = `left` +2 WHERE `left` > '. ($right - 1);
		$this->db->executeQuery($sql);
 
		$sql = 'INSERT INTO tree SET `left`=' . ($right - 1) .', `right`=' . $right . ', `object_id`="'. $object_id .'", `parent_id`="' . $parentId .'";';
		$this->db->executeQuery($sql);
	}
 
	/**
	 * Adds root node
	 *
	 * @param object_id Id of object in system (this is not db id)
	 * @return boolean
	 */
	public function addRoot($object_id) {
		$rs = $this->db->executeQuery('SELECT * FROM `tree` WHERE `parent_id` ="0"');
		if($rs->getRecordCount() == 0) {
			$this->db->executeQuery('INSERT INTO `tree` ( `id` , `object_id` , `left` , `right` ) VALUES ( '0', '' . $object_id . '', '1', '2')');
			return true;
		}
		return false;
	}
 
	/**
	 * Removes node
	 *
	 * @param $id Id of node
	 */
	public function deleteNode($id) {
		$rs = $this->db->executeQuery('SELECT `parent_id`, `left` FROM `tree` WHERE `id`="'. $id .'"');
		while($rs->next()) {
			$node = array();
			$node['parent'] = $rs->getInt('parent_id');
			$node['left'] = $rs->getInt('left');
		}
 
		$this->db->executeQuery('DELETE FROM `tree` WHERE `id`="' . $id . '" LIMIT 1');
		$this->rebuild($node['parent'], $node['left'] - 1);
	}
 
	/**
	 * Rebuilds tree recursively
	 * If something goes wrong, you'll use this
	 *
	 * @param $parent Id of parent node
	 * @param $left Left
	 */
	public function rebuild($parent, $left) {
		$right = $left+1;
 
		$rs = $this->db->executeQuery('SELECT `id` FROM `tree` WHERE `parent_id`="' . $parent . '";');
		while ($rs->next()) {
			$right = $this->rebuild($rs->getInt('id'), $right);
		}
		$this->db->executeQuery('UPDATE tree SET `left`=' . $left . ', `right`=' . $right . ' WHERE `id`="' . $parent . '";');
		return $right+1;
	}
 
	/**
	 * Test method
	 *
	 * @param $root Id of node which is root to display
	 */
	function display($root) {
		$rs = $this->db->executeQuery('SELECT `left`, `right` FROM `tree` WHERE `id`="'.$root.'";');
		while($rs->next()) {
			$l = $rs->getInt('left');
			$r = $rs->getInt('right');
		}
 
		$right = array();
 
		$rs = $this->db->executeQuery('SELECT `object_id`, `left`, `right` FROM tree WHERE `left` BETWEEN '. $l .' AND ' . $r . ' ORDER BY `left` ASC;');
		while ($rs->next()) {
			if (count($right)>0) {
			   while ($right[count($right)-1] < $rs->getInt('right')) {
				   array_pop($right);
			   }
		   }
		   echo str_repeat('&nbsp;&nbsp;&nbsp;',count($right)) . $rs->getString('object_id'). ' Left: ' . $rs->getInt('left') . ' Right: '. $rs->getInt('right') . "<br/>n";
 
		   $right[] = $rs->getInt('right');
	   }
	}
 
	/**
	 * Gets object id
	 *
	 * @param id of node
	 * @return object id
	 */
	public function getNode($id) {
		$rs = $this->db->executeQuery('SELECT `object_id` FROM `tree` WHERE `id`="'.$id.'";');
		while($rs->next()) {
			return $rs->getInt('object_id');
		}
	}
}
?>
[PHP] pobierz, plaintext 

[SQL] pobierz, plaintext 
CREATE TABLE `tree` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `parent_id` int(11) NOT NULL DEFAULT '0',
  `object_id` int(11) NOT NULL DEFAULT '0',
  `left` int(11) NOT NULL DEFAULT '0',
  `right` int(11) NOT NULL DEFAULT '0',
  PRIMARY KEY  (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 AUTO_INCREMENT=3 ;
[SQL] pobierz, plaintext 

Może komuś się przyda.
Object_id to nr obiektu w cmsie, równie dobrze możecie zastąpić to przez jakiś TEXT.

[mike]

Przyznam że nawet nie zagłębiałem się w kod.
Jedyne co na starcie mi się nasuwa, że to może cos o drzewach binarnych (IMG:http://forum.php.pl/style_emoticons/default/tongue.gif)

Dlatego cytat stąd:

Autor musi jasno okreslic do czego służy klasa, funkcja lub algorytm i jak go używać (nie wklejamy tylko kodu).

@bella_666 możesz troszkę obkomentować?

[bela]

Tyle o drzewkach piszą wokół, aż trudno nie słyszeć, ale co tam.
Proponuję lekturę http://www.sitepoint.com/article/hierarchical-data-database bo nie lubię się powtarzać.

[ebe]

Metoda display jest kompletnie bezużyteczna narzucasz sposób prezentacji drzewa, pozatym przydałaby się kolumna pozycjonująca elementy w gałęzi i metody do jej obsługi.

UPDATE zauważyłem że display to tylko metoda dotestowania (IMG:http://forum.php.pl/style_emoticons/default/biggrin.gif) , tak więc jak proponujesz rozwiązania do np. prezentacji drzewa w formie menu? Np. ktoś chciałby sobie wstawić takie menu w <ul><li> a ktoś np. w <table> i jak zbudować seryjnie i wydajnie obiekty powiązane z poszczególnymi gałęziami...

Ten post edytował ebe 29.08.2005, 13:32:24

[bela]

Fajnie, że zwróciłeś na to uwagę, jak wróce z treningu to się tym zajmę (IMG:http://forum.php.pl/style_emoticons/default/snitch.gif)

[Bakus]

Poprawiłem temat by był zgodny z nowymi zasadami na forum.

[wiechol]

Witam,

Bawił sie już ktoś przenoszeniem węzłów?

Pozdrawiam

[sf]

Tutaj jest lepsza klasa : http://www.phpriot.com/articles/nested-trees-appendix , która ma już zaimplementowaną odbudowę całego drzewa po przeniesieniu elementu.

[Crozin]

Mógłbyś chociaż dodać możliwość przenoszenia (góra/dół) elementów po drzewku:

[PHP] pobierz, plaintext 
<?php
public function moveNodes($row, $direction){
	$parentID = is_null($row->{$this->parentID}) ? ' IS NULL ' : ' = ' . $row->{$this->parentID} . ' ';
 
	$query = 'SELECT ' . $this->id .', ' . $this->left . ', ' . $this->right . 
				   ' FROM ' . $this->table . 
				   ' WHERE ' . $this->parentID . $parentID . 
					 ' AND ' . 
			 (($direction == 'up') ? $this->right . ' < ' . $row->{$this->right} . 
									 ' ORDER BY ' . $this->right . ' DESC' 
								   : $this->left . ' > ' . $row->{$this->left} .
									 ' ORDER BY ' . $this->left . ' ASC') .
			 ' LIMIT 1;';
 
	$target = $this->db->getRow($query);
	if(!$target)
	  return false;
 
	if($direction == 'up'){
			$leftID = $target->{$this->left};
			$rightID = $row->{$this->right};
 
			$diffUp = $row->{$this->left} - $target->{$this->left};
			$diffDown = $row->{$this->right} + 1 - $row->{$this->left};
 
			$moveUpLeft = $row->{$this->left};
			$moveUpRight = $row->{$this->right};
		}else{
			$leftID = $row->{$this->left};
			$rightID = $target->{$this->right};
 
			$diffUp = $row->{$this->right} + 1 - $row->{$this->left};
			$diffDown = $target->{$this->right} - $row->{$this->right};
 
			$moveUpLeft = $row->{$this->right} + 1;
			$moveUpRight = $target->{$this->right};
		}
 
		$query = 'UPDATE ' . $this->table . 
				   ' SET ' . $this->left . ' = ' . $this->left . ' + CASE' .
					  ' WHEN ' . $this->left . ' BETWEEN ' . $moveUpLeft . ' AND ' . $moveUpRight .' THEN -' . $diffUp .
					 ' ELSE ' . $diffDown . 
				   ' END, ' .
				   $this->right . ' = ' . $this->right . ' + CASE' .
					 ' WHEN ' . $this->right . ' BETWEEN ' . $moveUpLeft . ' AND ' . $moveUpRight .' THEN -' . $diffUp .
					 ' ELSE ' . $diffDown .
				   ' END' .
				   ' WHERE ' . $this->left . ' BETWEEN ' . $leftID . ' AND ' . $rightID . 
					  ' AND ' . $this->right . ' BETWEEN ' . $leftID . ' AND ' . $rightID . ';';
		$this->db->query($query);
 
		return true;
  }
?>
[PHP] pobierz, plaintext 

I tak jeszcze w ramach objaśnienia:

[PHP] pobierz, plaintext 
<?php
$this->table; //nazwa tabeli przechowywujacej drzewko
//nazwy pol w bazie (w konstruktorze klasy definujemy je sobie - nazwe tabeli tez)
$this->id //np: moduleID
$this->left 
$this->right //np. treeRight
$this->parentID
$this->indent
?>
[PHP] pobierz, plaintext 

Metoda ta przyjmuje dwa argumenty - pierwszy to wynik zapytania pobierającego wszystko n/t elementu (node) którego chcemy przenieś. Drugi to string (up/down) - kierunek przesunięcia


EDIT: To wycinek z klasy gdzieś z początku 2007 (gdy zaczynałem OOP) - więc proszę bez zbednych komentarzy (IMG:http://forum.php.pl/style_emoticons/default/biggrin.gif)

Ten post edytował Crozin 4.05.2008, 16:04:44

[wiechol]

@Crozin

Twoja metoda zdaje się umożl
144d
iwia porządkowanie kolejności liści w węźle.

Mi chodziło o możliwość przenoszenia całych węzłów np mamy:

[HTML] pobierz, plaintext 
Systemy operacyjne
     Rodzina windows
          Windows Vista
          Windows XP
                Windows XP Home
                Windows XP Professional
           Windows Server
           Rodzina UNIX
                Linux
                Ubunt
           Rodzina Apple
[HTML] pobierz, plaintext 

i chce sobie przenieść Windows XP do Rodziny Apple.

Rozwiązałem to już:

[PHP] pobierz, plaintext 
<?php
public function moveNode($currentNodeId, $destinationNodeId){
 
		$currentResult = $this->db->query('SELECT id, rgt, rgt-lft+1 AS width FROM '.$this->table.' WHERE id='.$this->db->realEscapeString($currentNodeId));
		$currentRow = $currentResult->fetchRow();
		$c
1383
urrentResult->free();
 
		$destinationResult = $this->db->query('SELECT id, rgt FROM '.$this->table.' WHERE id='.$this->db->realEscapeString($destinationNodeId));
		$destinationRow = $destinationResult->fetchRow();
		$destinationResult->free();
 
		$this->db->query('UPDATE '.$this->table.' SET rgt = rgt - '.$currentRow['width'].' WHERE rgt > '.$currentRow['rgt']);
		$this->db->query('UPDATE '.$this->table.' SET lft = lft - '.$currentRow['width'].' WHERE lft > '.$currentRow['rgt']);
 
		$this->db->query('UPDATE '.$this->table.' SET rgt = rgt + '.$currentRow['width'].' WHERE rgt > '.$destinationRow['rgt']);
		$this->db->query('UPDATE '.$this->table.' SET lft = lft + '.$currentRow['width'].' WHERE lft > '.$destinationRow['rgt']);
 
		$this->db->query('UPDATE '.$this->table.' SET parent_id = '.$destinationRow['id'].' WHERE id='.$currentRow['id']);
 
		$this->_rebuildTree();
	}
 
	protected function _rebuildTree($parent = 0, $left = 0, $level = 0) {
		$right = $left + 1;
 
		$wynik = $this->db->query('SELECT id FROM '.$this->table.' WHERE parent_id='.$parent);
 
		while ($row = $wynik->fetchRow()) {
			$right = $this->_rebuildTree($row['id'], $right, $level+1);
		}
 
		$this->db->query('UPDATE '.$this->table.' SET lft = '.$left.', rgt = '.$right.', level = '.$level.' WHERE id='.$parent);
		return $right + 1;
	}
?>
[PHP] pobierz, plaintext 

Z chęcią zobaczę propozycje innych bo nie jestem zwolennikiem rekurencji

pozdrawiam