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

## Source for file tree.php

Documentation is available at tree.php

1. <?php
2. /**
3. * File containing the ezcTree 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 Tree
26. */
28. /**
29. * ezcTree is an abstract class from which all the tree implementations
30. * inherit.
31. *
32. * Example:
33. * <code>
34. * <?php
35. * // Instantiating an existing tree, and creating a new tree is done through
36. * // the inherited classes
37. *
38. * // Creating a new in-memory tree
39. * $tree = ezcTreeMemory::create( new ezcTreeMemoryDataStore() );
40. *
41. * // Opening an existing tree in an XML file
42. * $tree = new ezcTreeXml( 'test.xml', new ezcTreeXmlInternalDataStore() );
43. *
44. * // Opening an existing tree from a database, using a nested set backend
45. * // - This retrieves data from the ezcTreeDbExternalTableDataStore store
46. * // using $this->dbh as database handle, $dataTable as table where to fetch
47. * // data from using 'id' as ID field.
48. * $store = new ezcTreeDbExternalTableDataStore( $this->dbh, $dataTable, 'id' );
49. * // - It uses the 'nested_set' table for keeping the tree structure
50. * $tree = new ezcTreeDbNestedSet( $this->dbh, 'nested_set', $store );
51. *
52. * // Fetching nodes and subtrees
53. * $node = $tree->fetchNodeById( 'He' );
54. * $nodeList = $tree->fetchSubtree( 'Pantherinae' );
55. *
56. * // Checking for relations between nodes
57. * $tree->isDescendantOf( 'Tiger', 'Panthera' );
58. * $tree->isSiblingOf( 'Lion', 'Leopard' );
59. * ?>
60. * </code>
61. *
62. * @property-read ezcTreeXmlDataStore $store
63. * The data store that is used for retrieving/storing data.
64. * @property string $nodeClassName
65. * Which class is used as tree node - this class *must* inherit
66. * the ezcTreeNode class.
67. * @property boolean $autoId
68. * When set to true, you can add nodes to the database without
69. * setting the ID. This only works with numeric keys however.
70. *
71. * @package Tree
72. * @version //autogentag//
73. */
74. abstract class ezcTree implements ezcTreeVisitable
75. {
76. /**
77. * Holds the properties of this class.
78. *
79. * @var array(string=>mixed)
80. */
81. protected $properties = array( 'nodeClassName' => 'ezcTreeNode' );
83. /**
84. * Contains whether a transaction has been started.
85. *
86. * @var bool
87. */
88. protected $inTransaction = false;
90. /**
91. * Contains whether we are in a transaction commit stage.
92. *
93. * @var bool
94. */
95. protected $inTransactionCommit = false;
97. /**
98. * Contains a list of transaction items.
99. *
100. * @var array(ezcTreeTransactionItem)
101. */
102. private $transactionList = array();
104. /**
105. * Returns the value of the property $name.
106. *
107. * @throws ezcBasePropertyNotFoundException if the property does not exist.
108. * @param string $name
109. * @ignore
110. */
111. public function __get( $name )
112. {
113. switch ( $name )
114. {
115. case 'autoId':
116. case 'store':
117. case 'nodeClassName':
118. return $this-> properties [$name];
119. }
120. throw new ezcBasePropertyNotFoundException ( $name );
121. }
123. /**
124. * Sets the property $name to $value.
125. *
126. * @throws ezcBasePropertyNotFoundException if the property does not exist.
127. * @throws ezcBasePropertyPermissionException if a read-only property is
128. * tried to be modified.
129. * @throws ezcBaseValueException if trying to assign a wrong value to the
130. * property
131. * @throws ezcBaseInvalidParentClassException
132. * if the class name passed as replacement for the ezcTreeNode
133. * classs does not inherit from the ezcTreeNode class.
134. * @param string $name
135. * @param mixed $value
136. * @ignore
137. */
138. public function __set( $name, $value )
139. {
140. switch ( $name )
141. {
142. case 'store':
143. throw new ezcBasePropertyPermissionException ( $name, ezcBasePropertyPermissionException ::READ );
145. case 'autoId':
146. if ( ! is_bool ( $value ) )
147. {
148. throw new ezcBaseValueException ( $name, $value, 'boolean' );
149. }
150. $this-> properties [$name] = $value;
151. break;
153. case 'nodeClassName':
154. if ( ! is_string ( $value ) )
155. {
156. throw new ezcBaseValueException ( $name, $value, 'string that contains a class name' );
157. }
159. // Check if the passed classname actually implements the
160. // correct parent class.
161. if ( 'ezcTreeNode' !== $value &&
162. ! in_array ( 'ezcTreeNode', class_parents ( $value ) ) )
163. {
164. throw new ezcBaseInvalidParentClassException ( 'ezcTreeNode', $value );
165. }
166. $this-> properties [$name] = $value;
167. break;
169. default:
170. throw new ezcBasePropertyNotFoundException ( $name );
171. }
172. }
174. /**
175. * Returns true if the property $name is set, otherwise false.
176. *
177. * @param string $name
178. * @return bool
179. * @ignore
180. */
181. public function __isset( $name )
182. {
183. switch ( $name )
184. {
185. case 'autoId':
186. case 'store':
187. case 'nodeClassName':
188. return isset( $this-> properties [$name] );
190. default:
191. return false;
192. }
193. }
195. /**
196. * This method checks whether a node ID is valid to be used in a backend.
197. *
198. * @throws ezcTreeInvalidNodeIDException if the node is not valid.
199. *
200. * @param string $nodeId
201. */
202. protected function checkNodeId ( $nodeId )
203. {
204. /* The default implementation does not check anything */
205. }
207. /**
208. * This method generates the next node ID.
209. *
210. * @return integer
211. */
212. abstract protected function generateNodeID ();
214. /**
215. * Creates a new tree node with node ID $nodeId and $data.
216. *
217. * This method returns by default an object of the ezcTreeNode class,
218. * however if a replacement is configured through the nodeClassName property
219. * an object of that class is returned instead. This object is guaranteed
220. * to inherit from ezcTreeNode.
221. *
222. * @param string $nodeId
223. * @param mixed $data
224. * @return ezcTreeNode
225. */
226. public function createNode ( $nodeId, $data )
227. {
228. if ( $nodeId === null )
229. {
230. if ( $this-> properties ['autoId'] )
231. {
232. $nodeId = $this-> generateNodeID ();
233. }
234. else
235. {
236. throw new ezcTreeInvalidIdException ( null, '' );
237. }
238. }
239. $this->checkNodeID( $nodeId );
240. $className = $this-> properties ['nodeClassName'];
241. return new $className( $this, $nodeId, $data );
242. }
244. /**
245. * Implements the accept method for visiting.
246. *
247. * @param ezcTreeVisitor $visitor
248. */
249. public function accept ( ezcTreeVisitor $visitor )
250. {
251. $visitor->visit( $this );
252. $root = $this-> getRootNode ();
253. if ( $root instanceof ezcTreeNode )
254. {
255. $root->accept( $visitor );
256. }
257. }
259. /**
260. * Returns whether the node with ID $nodeId exists.
261. *
262. * @param string $nodeId
263. * @return bool
264. */
265. abstract public function nodeExists ( $nodeId );
267. /**
268. * Returns the node identified by the ID $nodeId.
269. *
270. * @param string $nodeId
271. * @throws ezcTreeUnknownIdException if there is no node with ID $nodeId
272. * @return ezcTreeNode
273. */
274. public function fetchNodeById ( $nodeId )
275. {
276. if ( !$this-> nodeExists ( $nodeId ) )
277. {
278. throw new ezcTreeUnknownIdException ( $nodeId );
279. }
280. $className = $this-> properties ['nodeClassName'];
281. $node = new $className( $this, $nodeId );
283. return $node;
284. }
286. /**
287. * Returns all the children of the node with ID $nodeId.
288. *
289. * @param string $nodeId
290. * @return ezcTreeNodeList
291. */
292. abstract public function fetchChildren ( $nodeId );
294. /**
295. * Returns the parent node of the node with ID $nodeId.
296. *
297. * @param string $nodeId
298. * @return ezcTreeNode
299. */
300. abstract public function fetchParent ( $nodeId );
302. /**
303. * Returns all the nodes in the path from the root node to the node with ID
304. * $nodeId, including those two nodes.
305. *
306. * @param string $nodeId
307. * @return ezcTreeNodeList
308. */
309. abstract public function fetchPath ( $nodeId );
311. /**
312. * Alias for fetchSubtreeDepthFirst().
313. *
314. * @param string $nodeId
315. * @return ezcTreeNodeList
316. */
317. abstract public function fetchSubtree ( $nodeId );
319. /**
320. * Returns the node with ID $nodeId and all its children, sorted according to
321. * the {@link http://en.wikipedia.org/wiki/Breadth-first_search Breadth-first sorting}
322. * algorithm.
323. *
324. * @param string $nodeId
325. * @return ezcTreeNodeList
326. */
327. abstract public function fetchSubtreeBreadthFirst ( $nodeId );
329. /**
330. * Returns the node with ID $nodeId and all its children, sorted according to
331. * the {@link http://en.wikipedia.org/wiki/Depth-first_search Depth-first sorting}
332. * algorithm.
333. *
334. * @param string $nodeId
335. * @return ezcTreeNodeList
336. */
337. abstract public function fetchSubtreeDepthFirst ( $nodeId );
339. /**
340. * Returns the number of direct children of the node with ID $nodeId.
341. *
342. * @param string $nodeId
343. * @return int
344. */
345. abstract public function getChildCount ( $nodeId );
347. /**
348. * Returns the number of children of the node with ID $nodeId, recursively.
349. *
350. * @param string $nodeId
351. * @return int
352. */
353. abstract public function getChildCountRecursive ( $nodeId );
355. /**
356. * Returns the distance from the root node to the node with ID $nodeId.
357. *
358. * @param string $nodeId
359. * @return int
360. */
361. abstract public function getPathLength ( $nodeId );
363. /**
364. * Returns whether the node with ID $nodeId has children.
365. *
366. * @param string $nodeId
367. * @return bool
368. */
369. abstract public function hasChildNodes ( $nodeId );
371. /**
372. * Returns whether the node with ID $childId is a direct child of the node
373. * with ID $parentId.
374. *
375. * @param string $childId
376. * @param string $parentId
377. * @return bool
378. */
379. abstract public function isChildOf ( $childId, $parentId );
381. /**
382. * Returns whether the node with ID $childId is a direct or indirect child
383. * of the node with ID $parentId.
384. *
385. * @param string $childId
386. * @param string $parentId
387. * @return bool
388. */
389. abstract public function isDescendantOf ( $childId, $parentId );
391. /**
392. * Returns whether the nodes with IDs $child1Id and $child2Id are siblings
393. * (ie, they share the same parent).
394. *
395. * @param string $child1Id
396. * @param string $child2Id
397. * @return bool
398. */
399. abstract public function isSiblingOf ( $child1Id, $child2Id );
401. /**
402. * Sets a new node as root node, this also wipes out the whole tree.
403. *
404. * @param ezcTreeNode $node
405. */
406. abstract public function setRootNode ( ezcTreeNode $node );
408. /**
409. * Returns the root node.
410. *
411. * @return ezcTreeNode
412. */
413. abstract public function getRootNode ();
415. /**
416. * Adds the node $childNode as child of the node with ID $parentId.
417. *
418. * @param string $parentId
419. * @param ezcTreeNode $childNode
420. */
421. abstract public function addChild ( $parentId, ezcTreeNode $childNode );
423. /**
424. * Deletes the node with ID $nodeId from the tree, including all its children.
425. *
426. * @param string $nodeId
427. */
428. abstract public function delete ( $nodeId );
430. /**
431. * Moves the node with ID $nodeId as child to the node with ID $targetParentId.
432. *
433. * @param string $nodeId
434. * @param string $targetParentId
435. */
436. abstract public function move ( $nodeId, $targetParentId );
438. /**
439. * Copies all the children of node $fromNode to node $toNode recursively.
440. *
441. * This method copies all children recursively from $fromNode to $toNode.
442. * The $fromNode belongs to the $from tree and the $toNode to the $to tree.
443. * Data associated with the nodes is copied as well from the store
444. * associated with the $from tree to the $to tree.
445. *
446. * @param ezcTree $from
447. * @param ezcTree $to
448. * @param ezcTreeNode $fromNode
449. * @param ezcTreeNode $toNode
450. */
451. private static function copyChildren( ezcTree $from, ezcTree $to, ezcTreeNode $fromNode, ezcTreeNode $toNode )
452. {
453. $children = $fromNode->fetchChildren();
454. foreach ( new ezcTreeNodeListIterator ( $from, $children, true ) as $childNodeKey => $childNodeData )
455. {
456. $fromChildNode = $from->fetchNodeById( $childNodeKey );
457. $toChildNode = new ezcTreeNode ( $to, $childNodeKey, $childNodeData );
458. $toNode->addChild( $toChildNode );
459. self::copyChildren( $from, $to, $fromChildNode, $toChildNode );
460. }
461. }
463. /**
464. * Copies the tree in $from to the empty tree in $to.
465. *
466. * This method copies all the nodes, including associated data from the
467. * used data store, from the tree $from to the tree $to. Because this
468. * function uses internally setRootNode() the target tree will be cleared
469. * out automatically. The method will not check whether the $from and $to
470. * trees share the same database table or data store, so make sure they are
471. * different to prevent unexpected behavior.
472. *
473. * @param ezcTree $from
474. * @param ezcTree $to
475. */
476. public static function copy ( ezcTree $from, ezcTree $to )
477. {
478. $fromRootNode = $from->getRootNode();
479. $to->setRootNode( new ezcTreeNode ( $to, $fromRootNode->id, $fromRootNode->data ) );
480. $toRootNode = $to->getRootNode();
481. self::copyChildren( $from, $to, $fromRootNode, $toRootNode );
482. }
484. /**
485. * Returns whether we are currently in a transaction or not
486. *
487. * @return bool
488. */
489. public function inTransaction ()
490. {
491. return $this-> inTransaction ;
492. }
494. /**
495. * Returns whether we are currently in a transaction commit state or not
496. *
497. * @return bool
498. */
499. public function inTransactionCommit ()
500. {
501. return $this-> inTransactionCommit ;
502. }
504. /**
505. * Starts an transaction in which all tree modifications are queued until
506. * the transaction is committed with the commit() method.
507. */
508. public function beginTransaction ()
509. {
510. if ( $this-> inTransaction )
511. {
512. throw new ezcTreeTransactionAlreadyStartedException ;
513. }
514. $this-> inTransaction = true;
515. $this->transactionList = array();
516. }
518. /**
519. * Commits the transaction by running the stored instructions to modify
520. * the tree structure.
521. */
522. public function commit ()
523. {
524. if ( !$this-> inTransaction )
525. {
526. throw new ezcTreeTransactionNotStartedException ;
527. }
528. $this-> inTransaction = false;
529. $this-> inTransactionCommit = true;
530. foreach ( $this->transactionList as $transactionItem )
531. {
532. switch ( $transactionItem->type )
533. {
534. case ezcTreeTransactionItem::ADD:
535. $this-> addChild ( $transactionItem->parentId, $transactionItem->node );
536. break;
538. case ezcTreeTransactionItem::DELETE:
539. $this-> delete ( $transactionItem->nodeId );
540. break;
542. case ezcTreeTransactionItem::MOVE:
543. $this-> move ( $transactionItem->nodeId, $transactionItem->parentId );
544. break;
545. }
546. }
547. $this-> inTransactionCommit = false;
548. $this->fixateTransaction();
549. }
551. /**
552. * Adds a new transaction item to the list.
553. *
554. * @param ezcTreeTransactionItem $item
555. */
556. protected function addTransactionItem ( ezcTreeTransactionItem $item )
557. {
558. $this->transactionList[] = $item;
559. }
561. /**
562. * Rolls back the transaction by clearing all stored instructions.
563. */
564. public function rollback ()
565. {
566. if ( !$this-> inTransaction )
567. {
568. throw new ezcTreeTransactionNotStartedException ;
569. }
570. $this-> inTransaction = false;
571. $this->transactionList = array();
572. }
573. }
574. ?>

Documentation generated by phpDocumentor 1.4.3