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

## Source for file memory.php

Documentation is available at memory.php

1. <?php
2. /**
3. * File containing the ezcTreeMemory 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. * ezcTreeMemory is an implementation of a tree backend that operates on
30. * an in-memory tree structure. Meta-information is kept in objects of the
31. * ezcTreeMemoryNode class.
32. *
33. * Example:
34. * <code>
35. * <?php
36. * // Create a new tree
37. * $tree = ezcTreeMemory::create( new ezcTreeMemoryDataStore() );
38. * // or
39. * $tree = new ezcTreeMemory( new ezcTreeMemoryDataStore() );
40. * ?>
41. * </code>
42. *
43. * See {@link ezcTree} for examples on how to operate on the tree.
44. *
45. * @property-read ezcTreeXmlDataStore $store
46. * The data store that is used for retrieving/storing data.
47. * @property string $nodeClassName
48. * Which class is used as tree node - this class *must* inherit
49. * the ezcTreeNode class.
50. *
51. * @package Tree
52. * @version //autogentag//
53. * @mainclass
54. */
55. class ezcTreeMemory extends ezcTree
56. {
57. /**
58. * Contains a list of all nodes, indexed by node ID that link directly to the create node so that they can be looked up quickly.
59. *
60. * @var array(string=>ezcTreeMemoryNode)
61. */
62. private $nodeList = array();
64. /**
65. * Contains the root node.
66. *
67. * @var ezcTreeMemoryNode
68. */
69. private $rootNode;
71. /**
72. * Stores the last auto generated ID that was used.
73. *
74. * @var integer $autoNodeId
75. */
76. private $autoNodeId = 0;
78. /**
79. * Constructs a new ezcTreeMemory object.
80. *
81. * The store that is used for data storage should be passed as the
82. * $store argument.
83. *
84. * @param ezcTreeMemoryDataStore $store
85. */
86. protected function __construct ( ezcTreeMemoryDataStore $store )
87. {
88. $this-> properties ['store'] = $store;
89. $this-> properties ['autoId'] = false;
90. }
92. /**
93. * This method generates the next node ID.
94. *
95. * @return integer
96. */
97. protected function generateNodeID ()
98. {
99. $this->autoNodeId++;
100. return $this->autoNodeId;
101. }
103. /**
104. * A factory method that creates a new empty tree using the data store $store.
105. *
106. * @param ezcTreeMemoryDataStore $store
107. * @return ezcTreeMemory
108. */
109. public static function create ( ezcTreeMemoryDataStore $store )
110. {
111. $newTree = new ezcTreeMemory ( $store );
112. $newTree->nodeList = null;
113. $newTree->rootNode = null;
114. return $newTree;
115. }
117. /**
118. * Returns whether the node with ID $nodeId exists.
119. *
120. * @param string $nodeId
121. * @return bool
122. */
123. public function nodeExists ( $nodeId )
124. {
125. return isset( $this->nodeList[$nodeId] );
126. }
128. /**
129. * Returns the node identified by the ID $nodeId.
130. *
131. * @param string $nodeId
132. * @throws ezcTreeInvalidIdException if there is no node with ID $nodeId
133. * @return ezcTreeNode
134. */
135. public function fetchNodeById ( $nodeId )
136. {
137. return $this->getNodeById( $nodeId )->node;
138. }
140. /**
141. * Returns the node container for node $nodeId.
142. *
143. * @param string $nodeId
144. * @throws ezcTreeInvalidIdException if there is no node with ID $nodeId
145. * @return ezcTreeMemoryNode
146. */
147. private function getNodeById( $nodeId )
148. {
149. if ( !$this-> nodeExists ( $nodeId ) )
150. {
151. throw new ezcTreeUnknownIdException ( $nodeId );
152. }
153. return $this->nodeList[$nodeId];
154. }
156. /**
157. * Returns all the children of the node with ID $nodeId.
158. *
159. * @param string $nodeId
160. * @return ezcTreeNodeList
161. */
162. public function fetchChildren ( $nodeId )
163. {
164. $treeNode = $this->getNodeById( $nodeId );
165. $list = new ezcTreeNodeList ;
166. foreach ( $treeNode->children as $nodeId => $child )
167. {
168. $list->addNode( $child->node );
169. }
170. return $list;
171. }
173. /**
174. * Returns the parent node of the node with ID $nodeId.
175. *
176. * This method returns null if there is no parent node.
177. *
178. * @param string $nodeId
179. * @return ezcTreeNode
180. */
181. public function fetchParent ( $nodeId )
182. {
183. $treeNode = $this->getNodeById( $nodeId );
184. $parentNode = $treeNode->parent;
185. return $parentNode !== null ? $parentNode->node : null;
186. }
188. /**
189. * Returns all the nodes in the path from the root node to the node with ID
190. * $nodeId, including those two nodes.
191. *
192. * @param string $nodeId
193. * @return ezcTreeNodeList
194. */
195. public function fetchPath ( $nodeId )
196. {
197. $list = new ezcTreeNodeList ;
198. $memoryNode = $this->getNodeById( $nodeId );
200. $nodes = array();
201. $nodes[] = $memoryNode->node;
203. $memoryNode = $memoryNode->parent;
205. while ( $memoryNode !== null )
206. {
207. $nodes[] = $memoryNode->node;
208. $memoryNode = $memoryNode->parent;
209. }
211. $list = new ezcTreeNodeList ;
212. foreach ( array_reverse ( $nodes ) as $node )
213. {
214. $list->addNode( $node );
215. }
216. return $list;
217. }
219. /**
220. * Adds the children nodes of the node $memoryNode to the
221. * ezcTreeNodeList $list.
222. *
223. * @param ezcTreeNodeList $list
224. * @param ezcTreeMemoryNode $memoryNode
225. */
226. private function addChildNodesDepthFirst( ezcTreeNodeList $list, ezcTreeMemoryNode $memoryNode )
227. {
228. foreach ( $memoryNode->children as $nodeId => $childMemoryNode )
229. {
230. $list->addNode( $childMemoryNode->node );
231. $this->addChildNodesDepthFirst( $list, $childMemoryNode );
232. }
233. }
235. /**
236. * Returns the node with ID $nodeId and all its children, sorted accoring to
237. * the {@link http://en.wikipedia.org/wiki/Depth-first_search Depthth-first sorting}
238. * algorithm.
239. *
240. * @param string $nodeId
241. * @return ezcTreeNodeList
242. */
243. public function fetchSubtreeDepthFirst ( $nodeId )
244. {
245. $list = new ezcTreeNodeList ;
246. $memoryNode = $this->getNodeById( $nodeId );
247. $list->addNode( $memoryNode->node );
248. $this->addChildNodesDepthFirst( $list, $memoryNode );
249. return $list;
250. }
252. /**
253. * Alias for fetchSubtreeDepthFirst().
254. *
255. * @param string $nodeId
256. * @return ezcTreeNodeList
257. */
258. public function fetchSubtree ( $nodeId )
259. {
260. return $this-> fetchSubtreeDepthFirst ( $nodeId );
261. }
263. /**
264. * Adds the children nodes of the node $memoryNode to the
265. * ezcTreeNodeList $list.
266. *
267. * @param ezcTreeNodeList $list
268. * @param ezcTreeMemoryNode $memoryNode
269. */
270. private function addChildNodesBreadthFirst( ezcTreeNodeList $list, ezcTreeMemoryNode $memoryNode )
271. {
272. foreach ( $memoryNode->children as $nodeId => $childMemoryNode )
273. {
274. $list->addNode( $childMemoryNode->node );
275. }
276. foreach ( $memoryNode->children as $nodeId => $childMemoryNode )
277. {
278. $this->addChildNodesBreadthFirst( $list, $childMemoryNode );
279. }
280. }
282. /**
283. * Returns the node with ID $nodeId and all its children, sorted according to
284. * the {@link http://en.wikipedia.org/wiki/Breadth-first_search Breadth-first sorting}
285. * algorithm.
286. *
287. * @param string $nodeId
288. * @return ezcTreeNodeList
289. */
290. public function fetchSubtreeBreadthFirst ( $nodeId )
291. {
292. $list = new ezcTreeNodeList ;
293. $memoryNode = $this->getNodeById( $nodeId );
294. $list->addNode( $memoryNode->node );
295. $this->addChildNodesBreadthFirst( $list, $memoryNode );
296. return $list;
297. }
299. /**
300. * Returns the number of direct children of the node with ID $nodeId.
301. *
302. * @param string $nodeId
303. * @return int
304. */
305. public function getChildCount ( $nodeId )
306. {
307. return count ( $this->getNodeById( $nodeId )->children );
308. }
310. /**
311. * Helper method that iterates recursively over the children of $node to
312. * count the number of children.
313. *
314. * @param integer $count
315. * @param ezcTreeMemoryNode $node
316. */
317. private function countChildNodes( &$count, ezcTreeMemoryNode $node )
318. {
319. foreach ( $node->children as $nodeId => $node )
320. {
321. $count++;
322. $this->countChildNodes( $count, $node );
323. }
324. }
326. /**
327. * Returns the number of children of the node with ID $nodeId, recursively
328. *
329. * @param string $nodeId
330. * @return int
331. */
332. public function getChildCountRecursive ( $nodeId )
333. {
334. $count = 0;
335. $node = $this->getNodeById( $nodeId );
336. $this->countChildNodes( $count, $node );
337. return $count;
338. }
340. /**
341. * Returns the distance from the root node to the node with ID $nodeId
342. *
343. * @param string $nodeId
344. * @return int
345. */
346. public function getPathLength ( $nodeId )
347. {
348. $childNode = $this->getNodeById( $nodeId );
349. $length = -1;
351. while ( $childNode !== null )
352. {
353. $childNode = $childNode->parent;
354. $length++;
355. }
356. return $length;
357. }
359. /**
360. * Returns whether the node with ID $nodeId has children
361. *
362. * @param string $nodeId
363. * @return bool
364. */
365. public function hasChildNodes ( $nodeId )
366. {
367. return count ( $this->getNodeById( $nodeId )->children ) > 0;
368. }
370. /**
371. * Returns whether the node with ID $childId is a direct child of the node
372. * with ID $parentId
373. *
374. * @param string $childId
375. * @param string $parentId
376. * @return bool
377. */
378. public function isChildOf ( $childId, $parentId )
379. {
380. $childNode = $this->getNodeById( $childId );
381. $parentNode = $this->getNodeById( $parentId );
383. if ( $childNode->parent->node === $parentNode->node )
384. {
385. return true;
386. }
387. return false;
388. }
390. /**
391. * Returns whether the node with ID $childId is a direct or indirect child
392. * of the node with ID $parentId
393. *
394. * @param string $childId
395. * @param string $parentId
396. * @return bool
397. */
398. public function isDescendantOf ( $childId, $parentId )
399. {
400. $childNode = $this->getNodeById( $childId );
401. $parentNode = $this->getNodeById( $parentId );
403. if ( $childNode === $parentNode )
404. {
405. return false;
406. }
408. while ( $childNode !== null )
409. {
410. if ( $childNode->node === $parentNode->node )
411. {
412. return true;
413. }
414. $childNode = $childNode->parent;
415. }
416. return false;
417. }
419. /**
420. * Returns whether the nodes with IDs $child1Id and $child2Id are siblings
421. * (ie, the share the same parent)
422. *
423. * @param string $child1Id
424. * @param string $child2Id
425. * @return bool
426. */
427. public function isSiblingOf ( $child1Id, $child2Id )
428. {
429. $elem1 = $this->getNodeById( $child1Id );
430. $elem2 = $this->getNodeById( $child2Id );
431. return (
432. ( $child1Id !== $child2Id ) &&
433. ( $elem1->parent === $elem2->parent )
434. );
435. }
437. /**
438. * Sets a new node as root node, this wipes also out the whole tree
439. *
440. * @param ezcTreeNode $node
441. */
442. public function setRootNode ( ezcTreeNode $node )
443. {
444. // wipe nodelist and data
445. $this->nodeList = array();
446. $this->store->deleteDataForAllNodes();
448. // replace root node
449. $newObj = new ezcTreeMemoryNode( $node, array() );
450. $this->rootNode = $newObj;
452. // Add to node list
453. $this->nodeList[$node->id] = $newObj;
454. }
456. /**
457. * Returns the root node
458. *
459. * This methods returns null if there is no root node.
460. *
461. * @return ezcTreeNode
462. */
463. public function getRootNode ()
464. {
465. if ( $this->rootNode )
466. {
467. return $this->rootNode->node;
468. }
469. return null;
470. }
472. /**
473. * Adds the node $childNode as child of the node with ID $parentId
474. *
475. * @param string $parentId
476. * @param ezcTreeNode $childNode
477. */
478. public function addChild ( $parentId, ezcTreeNode $childNode )
479. {
480. if ( $this-> inTransaction )
481. {
482. $this-> addTransactionItem ( new ezcTreeTransactionItem( ezcTreeTransactionItem::ADD, $childNode, null, $parentId ) );
483. return;
484. }
486. // Locate parent node
487. $parentMemoryNode = $this->getNodeById( $parentId );
489. // Create new node
490. $newObj = new ezcTreeMemoryNode( $childNode, array(), $parentMemoryNode );
492. // Append to parent node
493. $parentMemoryNode->children[$childNode->id] = $newObj;
495. // Add to node list
496. $this->nodeList[$childNode->id] = $newObj;
497. }
499. /**
500. * Deletes the node with ID $nodeId from the tree, including all its children
501. *
502. * @param string $nodeId
503. */
504. public function delete ( $nodeId )
505. {
506. if ( $this-> inTransaction )
507. {
508. $this-> addTransactionItem ( new ezcTreeTransactionItem( ezcTreeTransactionItem::DELETE, null, $nodeId ) );
509. return;
510. }
512. // locate node to move
513. $nodeToDelete = $this->getNodeById( $nodeId );
515. // fetch the whole subtree and delete all the associated data
516. $children = $nodeToDelete->node->fetchSubtree();
517. $this->store->deleteDataForNodes( $children );
519. // Use the parent to remove the child
520. unset( $nodeToDelete->parent->children[$nodeId] );
522. // Remove the node and all its children
523. foreach ( new ezcTreeNodeListIterator ( $this, $children ) as $nodeId => $data )
524. {
525. unset( $this->nodeList[$nodeId] );
526. }
527. }
529. /**
530. * Moves the node with ID $nodeId as child to the node with ID $targetParentId
531. *
532. * @param string $nodeId
533. * @param string $targetParentId
534. */
535. public function move ( $nodeId, $targetParentId )
536. {
537. if ( $this-> inTransaction )
538. {
539. $this-> addTransactionItem ( new ezcTreeTransactionItem( ezcTreeTransactionItem::MOVE, null, $nodeId, $targetParentId ) );
540. return;
541. }
543. // locate node to move
544. $nodeToMove = $this->getNodeById( $nodeId );
546. // locate new parent
547. $newParent = $this->getNodeById( $targetParentId );
549. // new placement for node
550. $newParent->children[$nodeId] = $nodeToMove;
552. // remove old location from previous parent
553. unset( $nodeToMove->parent->children[$nodeId] );
555. // update parent attribute of the node
556. $nodeToMove->parent = $newParent;
557. }
559. /**
560. * Fixates the transaction.
561. */
562. public function fixateTransaction ()
563. {
564. }
565. }
566. ?>

Documentation generated by phpDocumentor 1.4.3