Hello,
This may be bit OT now and should belong under "Tree Traversal Methods", however I just wanted to maintain a coherent thread so that I can easily find it later on. I have been looking back at the top of this thread to see if I missed anything at the same time I kept looking back as to why I used a recursive approach to building the tree traversal data for my MPTT implementation. As I said earlier, it's been about three months since I last touched the implementation found here: http://abing.gotdns.com/wobject.php.html Setting all other fields aside, here are the important fields for a node in the object tree: id = object's ID parent_id = object's parent ID lft, rgt = fields for MPTT data link_order = indicates position of a node relative to its siblings Looking at these fields, one can say that parent_id and link_order are not needed. Ordinarily the recursive approach to rebuilding the MPTT data every time the nodes are updated is also not needed. MPTT was developed to remove the need for recursion in tree traversal. Looking back at the notes I have on paper, I remembered why I made the decision to include these redundant fields. Here are the use cases for my system that warrant such fields: * Inserting a new node in an arbitrary position within a subtree. There are three cases for this. Each case requires finding a specific node in the subtree and making sure (for validation purposes) that node is the one we want. 1. Insert a new node at the beginning of the subtree. We need to find the first child node of the parent node. This can easily be found with WHERE Node.lft=(ParentNode.lft + 1). This needs two queries, one to obtain the node data of the parent node and another one to find the node itself. With adjacency list, only one query is needed. 2. Insert a new node at the end of the subtree. We need to find the last child node of the parent node. This can easily be found with WHERE Node.rgt=(ParentNode.rgt -1). This is similar to case #1. 3. Insert a new node right after a specified sibling node in the subtree. This was where things got a bit sticky. How do you find out if a node is an immediate child of its parent? The best, MPTTish way I could come up with was to issue a query to find *all* the nodes under our parent and then traverse it to find the all the immediate children of our parent. This does not scale very well with very large subtrees. The solution I finally decided on is to combine the MPTT approach with the adjacency list approach and maintain a parent_id and a link_order field for each node. Then it was only a simple matter of having WHERE Node.parent_id=(ParentNode.id) AND Node.link_order=Position. There are probably better ways of doing this and I would gladly explore the alternatives when I find the time. However, there is another use case that warrants this decision. Which leads us to... * Obtain a list of immediate child nodes and be able to paginate them. This is where I needed adjacency list approach. As I mentioned above, I could not think of an easier (read: obvious + generic) way to obtain the immediate child nodes of a chosen parent using only the MPTT technique. Once I was able to solve those problems, the other operations/use cases (arbitrary node reparenting, node removal, node deletion) are easily solved by using a combination of adjacency list and MPTT. Finally, as for the recursive _rebuildTreeTraversalData() method, it's a bit of a misnomer as it not only rebuilds the tree traversal data, it also rebuilds and fixes any discrepancies in the adjacency list data when nodes are moved around in the whole tree. I also wrote it so that _rebuildTreeTraversalData() tries to avoid calling itself as much as possible. As for handling ACL, I was looking at this particular implementation at the time: http://phpgacl.sourceforge.net/ There is a demo here: http://phpgacl.sourceforge.net/demo/phpgacl/admin/acl_list.php However, I must admit that I have no idea if this implementation scales better than the CakePHP implementation. But judging from the database schema here: http://phpgacl.cvs.sourceforge.net/phpgacl/phpgacl/schema.xml?view=annotate the project also uses MPTT and it would be interesting to see if and how their implementation handles the case presented by Dr. Tarique. -- _nimrod_a_abing_ [?] http://abing.gotdns.com --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Cake PHP" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/cake-php?hl=en -~----------~----~----~----~------~----~------~--~---
