## Apache Zeta Components Manual :: File Source for db_nested_set.php

## Source for file db_nested_set.php

Documentation is available at db_nested_set.php

1. <?php
2. /**
3. * File containing the ezcTreeDbNestedSet class.
4. *
5. * Licensed to the Apache Software Foundation (ASF) under one
6. * or more contributor license agreements. See the NOTICE file
7. * distributed with this work for additional information
8. * regarding copyright ownership. The ASF licenses this file
9. * to you under the Apache License, Version 2.0 (the
10. * "License"); you may not use this file except in compliance
11. * with the License. You may obtain a copy of the License at
12. *
13. * http://www.apache.org/licenses/LICENSE-2.0
14. *
15. * Unless required by applicable law or agreed to in writing,
16. * software distributed under the License is distributed on an
17. * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
18. * KIND, either express or implied. See the License for the
19. * specific language governing permissions and limitations
20. * under the License.
21. *
22. * @license http://www.apache.org/licenses/LICENSE-2.0 Apache License, Version 2.0
23. * @version //autogentag//
24. * @filesource
25. * @package TreeDatabaseTiein
26. */
28. /**
29. * ezcTreeDbNestedSet implements a tree backend which stores parent/child
30. * information with left and right values.
31. *
32. * The table that stores the index (configured using the $indexTableName argument
33. * of the {@link __construct} method) should contain at least four fields. The
34. * first one 'id' will contain the node's ID, the second one 'parent_id' the ID
35. * of the node's parent. Both fields should be of the same database field type.
36. * Supported field types are either integer or a string type. The other two
37. * fields "lft" and "rgt" will store the left and right values that the
38. * algorithm requires. These two fields should be of an integer type.
39. * In order to use auto-generated IDs, the 'id' field needs to be an
40. * auto-incrementing integer field, by using either an auto-increment field, or
41. * a sequence.
42. *
43. * @property-read ezcTreeDbDataStore $store
44. * The data store that is used for retrieving/storing data.
45. * @property string $nodeClassName
46. * Which class is used as tree node - this class *must* inherit
47. * the ezcTreeNode class.
48. *
49. * @package TreeDatabaseTiein
50. * @version //autogentag//
51. * @mainclass
52. */
53. class ezcTreeDbNestedSet extends ezcTreeDbParentChild
54. {
55. /**
56. * Creates a new ezcTreeDbNestedSet object.
57. *
58. * The different arguments to the method configure which database
59. * connection ($dbh) is used to access the database and the $indexTableName
60. * argument which table is used to retrieve the relation data from. The
61. * $store argument configure which data store is used with this tree.
62. *
63. * It is up to the user to create the database table and make sure it is
64. * empty.
65. *
66. * @param ezcDbHandler $dbh
67. * @param string $indexTableName
68. * @param ezcTreeDbDataStore $store
69. */
70. public static function create ( ezcDbHandler $dbh, $indexTableName, ezcTreeDbDataStore $store )
71. {
72. return new ezcTreeDbNestedSet ( $dbh, $indexTableName, $store );
73. }
75. /**
76. * Returns all the nodes in the path from the root node to the node with ID
77. * $nodeId, including those two nodes.
78. *
79. * @param string $nodeId
80. * @return ezcTreeNodeList
81. */
82. public function fetchPath ( $nodeId )
83. {
84. $className = $this-> properties ['nodeClassName'];
85. $list = new ezcTreeNodeList ;
87. $db = $this-> dbh ;
88. $q = $db->createSelectQuery();
90. // SELECT parent.id
91. // FROM indexTable as node,
92. // indexTable as parent
93. // WHERE
94. // node.lft BETWEEN parent.lft AND parent.rgt
95. // AND
96. // node.id = $nodeId
97. // ORDER BY parent.lft
98. $q->select( 'parent.id' )
99. ->from( $db->quoteIdentifier( $this-> indexTableName ) . " as node" )
100. ->from( $db->quoteIdentifier( $this-> indexTableName ) . " as parent" )
101. ->where( $q->expr->lAnd(
102. $q->expr->between( 'node.lft', 'parent.lft', 'parent.rgt' ),
103. $q->expr->eq( 'node.id', $q->bindValue( $nodeId ) )
104. ))
105. ->orderBy( 'parent.lft' );
107. $s = $q->prepare();
108. $s->execute();
110. foreach ( $s as $result )
111. {
112. $list->addNode( new $className( $this, $result['id'] ) );
113. }
114. return $list;
115. }
117. /**
118. * Returns the node with ID $nodeId and all its children, sorted according to
119. * the {@link http://en.wikipedia.org/wiki/Depth-first_search Depth-first sorting}
120. * algorithm.
121. *
122. * @param string $nodeId
123. * @return ezcTreeNodeList
124. */
125. public function fetchSubtreeDepthFirst ( $nodeId )
126. {
127. $className = $this-> properties ['nodeClassName'];
128. $list = new ezcTreeNodeList ;
129. $db = $this-> dbh ;
131. // Fetch parent information
132. list( $left, $right, $width ) = $this-> fetchNodeInformation ( $nodeId );
134. // Fetch subtree
135. // SELECT id
136. // FROM indexTable
137. // WHERE lft BETWEEN $left AND $right
138. // ORDER BY lft
139. $q = $db->createSelectQuery();
140. $q->select( 'id' )
141. ->from( $db->quoteIdentifier( $this-> indexTableName ) )
142. ->where( $q->expr->between( 'lft', $q->bindValue( $left ), $q->bindValue( $right ) ) )
143. ->orderBy( 'lft' );
144. $s = $q->prepare();
145. $s->execute();
147. foreach ( $s as $result )
148. {
149. $list->addNode( new $className( $this, $result['id'] ) );
150. }
151. return $list;
152. }
154. /**
155. * Returns the distance from the root node to the node with ID $nodeId.
156. *
157. * @param string $nodeId
158. * @return int
159. */
160. public function getPathLength ( $nodeId )
161. {
162. $path = $this-> fetchPath ( $nodeId );
163. return count ( $path->nodes ) - 1;
164. }
166. /**
167. * Returns whether the node with ID $childId is a direct or indirect child
168. * of the node with ID $parentId.
169. *
170. * @param string $childId
171. * @param string $parentId
172. * @return bool
173. */
174. public function isDescendantOf ( $childId, $parentId )
175. {
176. $path = $this-> fetchPath ( $childId );
178. if ( isset( $path[$parentId] ) && ( $childId !== $parentId ) )
179. {
180. return true;
181. }
182. return false;
183. }
185. /**
186. * Sets a new node as root node, this also wipes out the whole tree.
187. *
188. * @param ezcTreeNode $node
189. */
190. public function setRootNode ( ezcTreeNode $node )
191. {
192. $db = $this-> dbh ;
194. // Remove nodes from tree
195. // DELETE FROM indexTable
196. $q = $db->createDeleteQuery();
197. $q->deleteFrom( $db->quoteIdentifier( $this-> indexTableName ) );
198. $s = $q->prepare();
199. $s->execute();
201. // Remove all data belonging to those nodes
202. $this->store->deleteDataForAllNodes();
204. // Create new root node
205. // INSERT INTO indexTable
206. // SET parent_id = null,
207. // id = $node->id,
208. // lft = 1, rgt = 2
209. $q = $db->createInsertQuery();
210. $q->insertInto( $db->quoteIdentifier( $this-> indexTableName ) )
211. ->set( 'parent_id', "null" )
212. ->set( 'id', $q->bindValue( $node->id ) )
213. ->set( 'lft', 1 )
214. ->set( 'rgt', 2 );
215. $s = $q->prepare();
216. $s->execute();
218. // Store data for new root node
219. $this->store->storeDataForNode( $node, $node->data );
220. }
222. /**
223. * Creates the query to insert an empty node into the database, so that the last-inserted ID can be obtained.
224. *
225. * @return ezcQueryInsert
226. */
227. protected function createAddEmptyNodeQuery ()
228. {
229. $db = $this-> dbh ;
231. $q = $db->createInsertQuery();
232. $q->insertInto( $db->quoteIdentifier( $this-> indexTableName ) )
233. ->set( 'lft', 0 )
234. ->set( 'rgt', 0 );
236. return $q;
237. }
239. /**
240. * Updates the left and right values of the nodes that are added while
241. * adding a whole subtree as child of a node.
242. *
243. * The method does not update nodes where the IDs are in the $excludedIds
244. * list.
245. *
246. * @param int $right
247. * @param int $width
248. * @param array(string) $excludedIds
249. */
250. protected function updateNestedValuesForSubtreeAddition ( $right, $width, $excludedIds = array() )
251. {
252. $db = $this-> dbh ;
254. // Move all the right values + $width for nodes where the the right value >=
255. // the parent right value:
256. // UPDATE indexTable
257. // SET rgt = rgt + $width
258. // WHERE rgt >= $right
259. $q = $db->createUpdateQuery();
260. $q->update( $db->quoteIdentifier( $this-> indexTableName ) )
261. ->set( 'rgt', $q->expr->add( 'rgt', $width ) )
262. ->where( $q->expr->gte( 'rgt', $right ) );
263. if ( count ( $excludedIds ) )
264. {
265. $q->where( $q->expr->not( $q->expr->in( 'id', $excludedIds ) ) );
266. }
267. $q->prepare()->execute();
269. // Move all the left values + $width for nodes where the the right value >=
270. // the parent left value
271. // UPDATE indexTable
272. // SET lft = lft + $width
273. // WHERE lft >= $right
274. $q = $db->createUpdateQuery();
275. $q->update( $db->quoteIdentifier( $this-> indexTableName ) )
276. ->set( 'lft', $q->expr->add( 'lft', $width ) )
277. ->where( $q->expr->gte( 'lft', $right ) );
278. if ( count ( $excludedIds ) )
279. {
280. $q->where( $q->expr->not( $q->expr->in( 'id', $excludedIds ) ) );
281. }
282. $q->prepare()->execute();
283. }
285. /**
286. * Adds the node $childNode as child of the node with ID $parentId.
287. *
288. * @param string $parentId
289. * @param ezcTreeNode $childNode
290. */
291. public function addChild ( $parentId, ezcTreeNode $childNode )
292. {
293. if ( $this-> inTransaction )
294. {
295. $this-> addTransactionItem ( new ezcTreeTransactionItem( ezcTreeTransactionItem::ADD, $childNode, null, $parentId ) );
296. return;
297. }
299. $db = $this-> dbh ;
301. // Fetch parent's information
302. list( $left, $right, $width ) = $this-> fetchNodeInformation ( $parentId );
304. // Update left and right values to account for new subtree
305. $this-> updateNestedValuesForSubtreeAddition ( $right, 2 );
307. // Add new node
308. if ( $width == 2 )
309. {
310. $newLeft = $left + 1;
311. $newRight = $left + 2;
312. }
313. else
314. {
315. $newLeft = $right;
316. $newRight = $right + 1;
317. }
319. // INSERT INTO indexTable
320. // SET parent_id = $parentId,
321. // id = $childNode->id,
322. // lft = $newLeft,
323. // rgt = $newRight
324. $q = $this-> createAddNodeQuery ( $childNode->id );
325. $q->set( 'parent_id', $q->bindValue( $parentId ) )
326. ->set( 'id', $q->bindValue( $childNode->id ) )
327. ->set( 'lft', $q->bindValue( $newLeft ) )
328. ->set( 'rgt', $q->bindValue( $newRight ) );
329. $s = $q->prepare();
330. $s->execute();
332. // Add the data for the new node
333. $this->store->storeDataForNode( $childNode, $childNode->data );
334. }
336. /**
337. * Returns the left, right and width values for the node with ID $nodeId as an
338. * array.
339. *
340. * The format of the array is:
341. * - 0: left value
342. * - 1: right value
343. * - 2: width value (right - left + 1)
344. *
345. * @param string $nodeId
346. * @return array(int)
347. */
348. protected function fetchNodeInformation ( $nodeId )
349. {
350. $db = $this-> dbh ;
352. // SELECT lft, rgt, rft-lft+1 as width
353. // FROM indexTable
354. // WHERE id = $nodeId
355. $q = $db->createSelectQuery();
356. $q->select( 'lft, rgt, rgt - lft + 1 as width' )
357. ->from( $db->quoteIdentifier( $this-> indexTableName ) )
358. ->where( $q->expr->eq( 'id', $q->bindValue( $nodeId ) ) );
359. $s = $q->prepare();
360. $s->execute();
361. $r = $s->fetchAll( PDO::FETCH_NUM );
362. return $r[0];
363. }
365. /**
366. * Updates the left and right values in case a subtree is deleted.
367. *
368. * @param int $right
369. * @param int $width
370. */
371. protected function updateNestedValuesForSubtreeDeletion ( $right, $width )
372. {
373. $db = $this-> dbh ;
375. // Move all the right values + $width for nodes where the the right
376. // value > the parent right value
377. // UPDATE indexTable
378. // SET rgt = rgt - $width
379. // WHERE rgt > $right
380. $q = $db->createUpdateQuery();
381. $q->update( $db->quoteIdentifier( $this-> indexTableName ) )
382. ->set( 'rgt', $q->expr->sub( 'rgt', $width ) )
383. ->where( $q->expr->gt( 'rgt', $right ) );
384. $q->prepare()->execute();
386. // Move all the right values + $width for nodes where the the left
387. // value > the parent right value
388. // UPDATE indexTable
389. // SET lft = lft - $width
390. // WHERE lft > $right
391. $q = $db->createUpdateQuery();
392. $q->update( $db->quoteIdentifier( $this-> indexTableName ) )
393. ->set( 'lft', $q->expr->sub( 'lft', $width ) )
394. ->where( $q->expr->gt( 'lft', $right ) );
395. $q->prepare()->execute();
396. }
398. /**
399. * Deletes the node with ID $nodeId from the tree, including all its children.
400. *
401. * @param string $nodeId
402. */
403. public function delete ( $nodeId )
404. {
405. if ( $this-> inTransaction )
406. {
407. $this-> addTransactionItem ( new ezcTreeTransactionItem( ezcTreeTransactionItem::DELETE, null, $nodeId ) );
408. return;
409. }
411. // Delete all data for the deleted nodes
412. $nodeList = $this-> fetchSubtreeDepthFirst ( $nodeId );
413. $this->store->deleteDataForNodes( $nodeList );
415. // Fetch node information
416. list( $left, $right, $width ) = $this-> fetchNodeInformation ( $nodeId );
418. // DELETE FROM indexTable
419. // WHERE lft BETWEEN $left and $right
420. $db = $this-> dbh ;
421. $q = $db->createDeleteQuery();
422. $q->deleteFrom( $db->quoteIdentifier( $this-> indexTableName ) )
423. ->where( $q->expr->between( 'lft', $left, $right ) );
424. $s = $q->prepare();
425. $s->execute();
427. // Update the left and right values to account for the removed subtree
428. $this-> updateNestedValuesForSubtreeDeletion ( $right, $width );
429. }
431. /**
432. * Moves the node with ID $nodeId as child to the node with ID $targetParentId.
433. *
434. * @param string $nodeId
435. * @param string $targetParentId
436. */
437. public function move ( $nodeId, $targetParentId )
438. {
439. if ( $this-> inTransaction )
440. {
441. $this-> addTransactionItem ( new ezcTreeTransactionItem( ezcTreeTransactionItem::MOVE, null, $nodeId, $targetParentId ) );
442. return;
443. }
445. $db = $this-> dbh ;
447. // Get the nodes that are gonne be moved in the subtree
448. $nodeIds = array();
449. foreach ( $this-> fetchSubtreeDepthFirst ( $nodeId )->nodes as $node )
450. {
451. $nodeIds[] = $node->id;
452. }
454. // Update parent ID for the node
455. // UPDATE indexTable
456. // SET parent_id = $targetParentId
457. // WHERE id = $nodeId
458. $q = $db->createUpdateQuery();
459. $q->update( $db->quoteIdentifier( $this-> indexTableName ) )
460. ->set( 'parent_id', $q->bindValue( $targetParentId ) )
461. ->where( $q->expr->eq( 'id', $q->bindValue( $nodeId ) ) );
463. $s = $q->prepare();
464. $s->execute();
466. // Fetch node information
467. list( $origLeft, $origRight, $origWidth ) = $this-> fetchNodeInformation ( $nodeId );
469. // Update the nested values to account for the moved subtree (delete part)
470. $this-> updateNestedValuesForSubtreeDeletion ( $origRight, $origWidth );
472. // Fetch node information
473. list( $targetParentLeft, $targetParentRight, $targerParentWidth ) = $this-> fetchNodeInformation ( $targetParentId );
475. // Update the nested values to account for the moved subtree (addition part)
476. $this-> updateNestedValuesForSubtreeAddition ( $targetParentRight, $origWidth, $nodeIds );
478. // Update nodes in moved subtree
479. $adjust = $targetParentRight - $origLeft;
481. // UPDATE indexTable
482. // SET rgt = rgt + $adjust
483. // WHERE id in $nodeIds
484. $q = $db->createUpdateQuery();
485. $q->update( $db->quoteIdentifier( $this-> indexTableName ) )
486. ->set( 'rgt', $q->expr->add( 'rgt', $adjust ) )
487. ->where( $q->expr->in( 'id', $nodeIds ) );
488. $q->prepare()->execute();
490. // UPDATE indexTable
491. // SET lft = lft + $adjust
492. // WHERE id in $nodeIds
493. $q = $db->createUpdateQuery();
494. $q->update( $db->quoteIdentifier( $this-> indexTableName ) )
495. ->set( 'lft', $q->expr->add( 'lft', $adjust ) )
496. ->where( $q->expr->in( 'id', $nodeIds ) );
497. $q->prepare()->execute();
498. }
499. }
500. ?>

Documentation generated by phpDocumentor 1.4.3