Changes between Version 1 and Version 2 of ModifiedPreorderTreeTraversal
- Timestamp:
- Feb 1, 2006, 6:09:55 AM (19 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
ModifiedPreorderTreeTraversal
v1 v2 1 There's a good article explaining [http://www.sitepoint.com/print/hierarchical-data-database what's Modified Preorder Tree Traversal on SitePoint]. Basically, it allows you to discover every children, or parent, or the whole tree, with a single query. Very efficient! And good for threaded discussions...1 There's a good article explaining [http://www.sitepoint.com/print/hierarchical-data-database what's Modified Preorder Tree Traversal on SitePoint]. I am not going to explain the whole theory here, just offer some code so you can implement it quickly. 2 2 3 I modified these snippets from an app I coded in portuguese, with more features than what's pasted here. If there's anything wrong, send me an email, because I do have it working here :) 3 Basically, it allows you to discover every children, or parent, or the whole tree, with a single query. Very efficient! And good for threaded discussions... 4 5 I modified these snippets from an app I coded in the portuguese language, with more features than what's pasted here. If there's anything wrong, send me an email, because I do have it working :) 4 6 5 7 Here's a model, a view and a couple functions to help you implement it. … … 36 38 cursor.execute("UPDATE `app_comments` " \ 37 39 "SET `lft` = `lft` + 2 " \ 38 "WHERE `lft` > %i" % int(target_rght) 40 "WHERE `lft` > %i" % int(target_rght)) 39 41 40 42 db.commit() … … 60 62 for j in stack_copy: 61 63 if j < comment.rght: 62 stack.pop() 64 stack.pop() 63 65 64 66 stack_size = len(stack) 65 67 66 comment.stack = stack_size 68 comment.stack = stack_size 67 69 68 70 stack.append(comentario.rght) 69 71 }}} 70 72 71 So, what have we done? There's a "stack" attribute on each comment now that tells you "how far" each comment is from another. For example, every "root" comment has a stack of 1. Every comment that's an answer to the root comments has a stack of 2. The stack respect the order that the comments were inserted at the database. Somethinglike this:73 So, what have we done? There's a "stack" attribute on each comment now that tells you "how far" each comment is from another. For example, every "root" comment (the direct reply to a "post", for example) has a stack of 1. Every comment that's an answer to the root comments has a stack of 2. The stack respects the order (because of order_by=['lft']) that the comments were inserted at the database. So we end up with comments having stacks numbered like this: 72 74 73 75 {{{ … … 76 78 3 77 79 3 80 4 81 2 78 82 2 79 83 80 84 1 81 85 2 86 3 82 87 3 83 88 }}} … … 89 94 {{ comment.body }} 90 95 </div> 91 92 96 }}} 93 97