Pomoc - Szukaj - Użytkownicy - Kalendarz
Pełna wersja: Drzewko left-right
Forum PHP.pl > Forum > Gotowe rozwiązania > Algorytmy, klasy, funkcje
bela
29.08.2005, 13:10:57 
[PHP] pobierz, plaintext 
  1. <?php
  2. class Tree {
  3. 	/**
  4. 	 * Instance of Creole
  5. 	 */
  6. 	private $db;
  7.  
  8. 	/**
  9. 	 * Constructor, initialize Creole
  10. 	 *
  11. 	 * @param $dsn
  12. 	 */
  13. 	public function __construct($dsn) {
  14. 		$this->db = Creole::getConnection($dsn);;
  15. 	}
  16.  
  17. 	/**
  18. 	 * Adds node to tree
  19. 	 *
  20. 	 * @param object_id Id of object in system (this is not db id)
  21. 	 * @param parent Id of parent - db id
  22. 	 */
  23. 	public function addNode($object_id, $parent) {
  24. 		$rs = $this->db->executeQuery('SELECT `id`, `left`, `right` FROM tree WHERE `id`="' . $parent . '"');
  25. 		if($rs->getRecordCount() == 0) {
  26. 			$left = 1;
  27. 			$right = 2;
  28. 		} else {
  29. 			while($rs->next()) {
  30. 				$left = $rs->getInt('left');
  31. 				$right = $rs->getInt('right');
  32. 				$parentId = $rs->getInt('id');
  33. 			}
  34. 		}
  35. 		$sql = 'UPDATE tree SET `right` = `right` +2 WHERE `right` >' . ($right - 1);
  36. 		$this->db->executeQuery($sql);
  37.  
  38. 		$sql = 'UPDATE tree SET `left` = `left` +2 WHERE `left` > '. ($right - 1);
  39. 		$this->db->executeQuery($sql);
  40.  
  41. 		$sql = 'INSERT INTO tree SET `left`=' . ($right - 1) .', `right`=' . $right . ', `object_id`="'. $object_id .'", `parent_id`="' . $parentId .'";';
  42. 		$this->db->executeQuery($sql);
  43. 	}
  44.  
  45. 	/**
  46. 	 * Adds root node
  47. 	 *
  48. 	 * @param object_id Id of object in system (this is not db id)
  49. 	 * @return boolean
  50. 	 */
  51. 	public function addRoot($object_id) {
  52. 		$rs = $this->db->executeQuery('SELECT * FROM `tree` WHERE `parent_id` ="0"');
  53. 		if($rs->getRecordCount() == 0) {
  54. 			$this->db->executeQuery('INSERT INTO `tree` ( `id` , `object_id` , `left` , `right` ) VALUES ( '0', '' . $object_id . '', '1', '2')');
  55. 			return true;
  56. 		}
  57. 		return false;
  58. 	}
  59.  
  60. 	/**
  61. 	 * Removes node
  62. 	 *
  63. 	 * @param $id Id of node
  64. 	 */
  65. 	public function deleteNode($id) {
  66. 		$rs = $this->db->executeQuery('SELECT `parent_id`, `left` FROM `tree` WHERE `id`="'. $id .'"');
  67. 		while($rs->next()) {
  68. 			$node = array();
  69. 			$node['parent'] = $rs->getInt('parent_id');
  70. 			$node['left'] = $rs->getInt('left');
  71. 		}
  72.  
  73. 		$this->db->executeQuery('DELETE FROM `tree` WHERE `id`="' . $id . '" LIMIT 1');
  74. 		$this->rebuild($node['parent'], $node['left'] - 1);
  75. 	}
  76.  
  77. 	/**
  78. 	 * Rebuilds tree recursively
  79. 	 * If something goes wrong, you'll use this
  80. 	 *
  81. 	 * @param $parent Id of parent node
  82. 	 * @param $left Left
  83. 	 */
  84. 	public function rebuild($parent, $left) {
  85. 		$right = $left+1;
  86.  
  87. 		$rs = $this->db->executeQuery('SELECT `id` FROM `tree` WHERE `parent_id`="' . $parent . '";');
  88. 		while ($rs->next()) {
  89. 			$right = $this->rebuild($rs->getInt('id'), $right);
  90. 		}
  91. 		$this->db->executeQuery('UPDATE tree SET `left`=' . $left . ', `right`=' . $right . ' WHERE `id`="' . $parent . '";');
  92. 		return $right+1;
  93. 	}
  94.  
  95. 	/**
  96. 	 * Test method
  97. 	 *
  98. 	 * @param $root Id of node which is root to display
  99. 	 */
  100. 	function display($root) {
  101. 		$rs = $this->db->executeQuery('SELECT `left`, `right` FROM `tree` WHERE `id`="'.$root.'";');
  102. 		while($rs->next()) {
  103. 			$l = $rs->getInt('left');
  104. 			$r = $rs->getInt('right');
  105. 		}
  106.  
  107. 		$right = array();
  108.  
  109. 		$rs = $this->db->executeQuery('SELECT `object_id`, `left`, `right` FROM tree WHERE `left` BETWEEN '. $l .' AND ' . $r . ' ORDER BY `left` ASC;');
  110. 		while ($rs->next()) {
  111. 			if (count($right)>0) {
  112. 			   while ($right[count($right)-1] < $rs->getInt('right')) {
  113. 				   array_pop($right);
  114. 			   }
  115. 		   }
  116. 		   echo str_repeat('&nbsp;&nbsp;&nbsp;',count($right)) . $rs->getString('object_id'). ' Left: ' . $rs->getInt('left') . ' Right: '. $rs->getInt('right') . "<br/>n";
  117.  
  118. 		   $right[] = $rs->getInt('right');
  119. 	   }
  120. 	}
  121.  
  122. 	/**
  123. 	 * Gets object id
  124. 	 *
  125. 	 * @param id of node
  126. 	 * @return object id
  127. 	 */
  128. 	public function getNode($id) {
  129. 		$rs = $this->db->executeQuery('SELECT `object_id` FROM `tree` WHERE `id`="'.$id.'";');
  130. 		while($rs->next()) {
  131. 			return $rs->getInt('object_id');
  132. 		}
  133. 	}
  134. }
  135. ?>
[PHP] pobierz, plaintext 


[SQL] pobierz, plaintext 
  1. CREATE TABLE `tree` (
  2.   `id` int(11) NOT NULL AUTO_INCREMENT,
  3.   `parent_id` int(11) NOT NULL DEFAULT '0',
  4.   `object_id` int(11) NOT NULL DEFAULT '0',
  5.   `left` int(11) NOT NULL DEFAULT '0',
  6.   `right` int(11) NOT NULL DEFAULT '0',
  7.   PRIMARY KEY  (`id`)
  8. ) 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
29.08.2005, 13:17:04
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 tongue.gif

Dlatego cytat stąd:
Cytat
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
29.08.2005, 13:27:14
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
29.08.2005, 13:29:55
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 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...
bela
29.08.2005, 13:46:19
Fajnie, że zwróciłeś na to uwagę, jak wróce z treningu to się tym zajmę snitch.gif
Bakus
31.08.2005, 21:18:38
Poprawiłem temat by był zgodny z nowymi zasadami na forum.
wiechol
4.05.2008, 14:33:22
Witam,

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

Pozdrawiam
sf
4.05.2008, 14:49:07
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
4.05.2008, 16:02:41
Mógłbyś chociaż dodać możliwość przenoszenia (góra/dół) elementów po drzewku:
[PHP] pobierz, plaintext 
  1. <?php
  2. public function moveNodes($row, $direction){
  3. 	$parentID = is_null($row->{$this->parentID}) ? ' IS NULL ' : ' = ' . $row->{$this->parentID} . ' ';
  4.  
  5. 	$query = 'SELECT ' . $this->id .', ' . $this->left . ', ' . $this->right . 
  6. 				   ' FROM ' . $this->table . 
  7. 				   ' WHERE ' . $this->parentID . $parentID . 
  8. 					 ' AND ' . 
  9. 			 (($direction == 'up') ? $this->right . ' < ' . $row->{$this->right} . 
  10. 									 ' ORDER BY ' . $this->right . ' DESC' 
  11. 								   : $this->left . ' > ' . $row->{$this->left} .
  12. 									 ' ORDER BY ' . $this->left . ' ASC') .
  13. 			 ' LIMIT 1;';
  14.  
  15. 	$target = $this->db->getRow($query);
  16. 	if(!$target)
  17. 	  return false;
  18.  
  19. 	if($direction == 'up'){
  20. 			$leftID = $target->{$this->left};
  21. 			$rightID = $row->{$this->right};
  22.  
  23. 			$diffUp = $row->{$this->left} - $target->{$this->left};
  24. 			$diffDown = $row->{$this->right} + 1 - $row->{$this->left};
  25.  
  26. 			$moveUpLeft = $row->{$this->left};
  27. 			$moveUpRight = $row->{$this->right};
  28. 		}else{
  29. 			$leftID = $row->{$this->left};
  30. 			$rightID = $target->{$this->right};
  31.  
  32. 			$diffUp = $row->{$this->right} + 1 - $row->{$this->left};
  33. 			$diffDown = $target->{$this->right} - $row->{$this->right};
  34.  
  35. 			$moveUpLeft = $row->{$this->right} + 1;
  36. 			$moveUpRight = $target->{$this->right};
  37. 		}
  38.  
  39. 		$query = 'UPDATE ' . $this->table . 
  40. 				   ' SET ' . $this->left . ' = ' . $this->left . ' + CASE' .
  41. 					  ' WHEN ' . $this->left . ' BETWEEN ' . $moveUpLeft . ' AND ' . $moveUpRight .' THEN -' . $diffUp .
  42. 					 ' ELSE ' . $diffDown . 
  43. 				   ' END, ' .
  44. 				   $this->right . ' = ' . $this->right . ' + CASE' .
  45. 					 ' WHEN ' . $this->right . ' BETWEEN ' . $moveUpLeft . ' AND ' . $moveUpRight .' THEN -' . $diffUp .
  46. 					 ' ELSE ' . $diffDown .
  47. 				   ' END' .
  48. 				   ' WHERE ' . $this->left . ' BETWEEN ' . $leftID . ' AND ' . $rightID . 
  49. 					  ' AND ' . $this->right . ' BETWEEN ' . $leftID . ' AND ' . $rightID . ';';
  50. 		$this->db->query($query);
  51.  
  52. 		return true;
  53.   }
  54. ?>
[PHP] pobierz, plaintext
I tak jeszcze w ramach objaśnienia:
[PHP] pobierz, plaintext 
  1. <?php
  2. $this->table; //nazwa tabeli przechowywujacej drzewko
  3. //nazwy pol w bazie (w konstruktorze klasy definujemy je sobie - nazwe tabeli tez)
  4. $this->id //np: moduleID
  5. $this->left 
  6. $this->right //np. treeRight
  7. $this->parentID
  8. $this->indent
  9. ?>
[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 biggrin.gif
wiechol
4.05.2008, 17:39:54
@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 
  1. Systemy operacyjne
  2.      Rodzina windows
  3.           Windows Vista
  4.           Windows XP
  5.                 Windows XP Home
  6.                 Windows XP Professional
  7.            Windows Server
  8.            Rodzina UNIX
  9.                 Linux
  10.                 Ubunt
  11.            Rodzina Apple
[HTML] pobierz, plaintext


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

Rozwiązałem to już:


[PHP] pobierz, plaintext 
  1. <?php
  2. public function moveNode($currentNodeId, $destinationNodeId){
  3.  
  4. 		$currentResult = $this->db->query('SELECT id, rgt, rgt-lft+1 AS width FROM '.$this->table.' WHERE id='.$this->db->realEscapeString($currentNodeId));
  5. 		$currentRow = $currentResult->fetchRow();
  6. 		$c
  7. 1383
  8. urrentResult->free();
  9.  
  10. 		$destinationResult = $this->db->query('SELECT id, rgt FROM '.$this->table.' WHERE id='.$this->db->realEscapeString($destinationNodeId));
  11. 		$destinationRow = $destinationResult->fetchRow();
  12. 		$destinationResult->free();
  13.  
  14. 		$this->db->query('UPDATE '.$this->table.' SET rgt = rgt - '.$currentRow['width'].' WHERE rgt > '.$currentRow['rgt']);
  15. 		$this->db->query('UPDATE '.$this->table.' SET lft = lft - '.$currentRow['width'].' WHERE lft > '.$currentRow['rgt']);
  16.  
  17. 		$this->db->query('UPDATE '.$this->table.' SET rgt = rgt + '.$currentRow['width'].' WHERE rgt > '.$destinationRow['rgt']);
  18. 		$this->db->query('UPDATE '.$this->table.' SET lft = lft + '.$currentRow['width'].' WHERE lft > '.$destinationRow['rgt']);
  19.  
  20. 		$this->db->query('UPDATE '.$this->table.' SET parent_id = '.$destinationRow['id'].' WHERE id='.$currentRow['id']);
  21.  
  22. 		$this->_rebuildTree();
  23. 	}
  24.  
  25. 	protected function _rebuildTree($parent = 0, $left = 0, $level = 0) {
  26. 		$right = $left + 1;
  27.  
  28. 		$wynik = $this->db->query('SELECT id FROM '.$this->table.' WHERE parent_id='.$parent);
  29.  
  30. 		while ($row = $wynik->fetchRow()) {
  31. 			$right = $this->_rebuildTree($row['id'], $right, $level+1);
  32. 		}
  33.  
  34. 		$this->db->query('UPDATE '.$this->table.' SET lft = '.$left.', rgt = '.$right.', level = '.$level.' WHERE id='.$parent);
  35. 		return $right + 1;
  36. 	}
  37. ?>
[PHP] pobierz, plaintext


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

pozdrawiam
To jest wersja lo-fi głównej zawartości. Aby zobaczyć pełną wersję z większą zawartością, obrazkami i formatowaniem proszę kliknij tutaj.
Invision Power Board © 2001-2025 Invision Power Services, Inc.