Changes between Version 2 and Version 3 of ModifiedPreorderTreeTraversal
- Timestamp:
- Feb 4, 2006, 9:46:53 AM (18 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
ModifiedPreorderTreeTraversal
v2 v3 1 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 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...3 Basically, it allows you to discover every children, or parents, or the whole tree, with a single query. Very efficient! And good for threaded discussions... 4 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 :) 5 [http://www.inerciasensorial.com.br/hacks/mptt-0.9.zip Download the necessary files] from my website. For now, it's just a model and a view (with a single function). I thought about adding a template tag but stick with the do-it-yourself flexibility. 6 6 7 Here's a model, a view and a couple functions to help you implement it. 7 If you hack it to add some functionality, drop me an email (inerte is my gmail.com username). Current version is 0.9, and if it doesn't break anything, as soon as I finish editing the forms that I use to serve as an example, it will be 1.0. And if we depend on any new features, it will probably stay at this version forever :p 8 8 9 '''Model''' 9 If you need more documentation, check old versions from this wiki page (specially the first and second), for a longer explanation of the whole thing, when mptt wasn't in a file for you to download, but just code that I pasted here. 10 10 11 What you really need are the ''lft'' and ''rght'' "columns". Yes, they mean ''left'' and ''right'', but these are reserved SQL words. Everything else is optional. You will probably want an "article" or "post" fields, using ForeignKey, to say where the comment belongs to. If you do add something like this, don't forget to change the SQL queries to add the column. 11 '''How to install''' 12 13 Drop the mptt folder inside your Django project folder. 14 15 Change to the directory of your project (where manage.py is) and type: 12 16 13 17 {{{ 14 class Comment(meta.Model): 15 body = meta.TextField() 16 lft = meta.PositiveIntegerField(db_index = True) 17 rght = meta.PositiveIntegerField(db_index = True) 18 python manage.py install mptt 19 python manage.py sqlindexes mptt 18 20 }}} 19 21 20 == New record == 22 If you have to, copy the output of sqlindexes and apply to your database. This is very important for performance! The object_id and lft columns should be indexed! 21 23 22 I have this on my request (form) processing view, but you can put it anywhere (_pre_save() it's a good idea). The ''comment_id'' pk is the comment we're replying to, the one that will become the parent: 24 '''Using it''' 25 26 Edit the views.py file from your app to call mptt's views.py and pass its function to a template: 23 27 24 28 {{{ 25 comment = get_object_or_404(comments, pk = comment_id) 29 from your_project_name.mptt.views import * 26 30 27 target_rght = comment.rght - 1 28 29 new_comment_lft = target_rght + 1 30 new_comment_rght = target_rght + 2 31 32 cursor = db.cursor() 33 34 cursor.execute("UPDATE `app_comments` " \ 35 "SET `rght` = `rght` + 2 " \ 36 "WHERE `rght` > %i" % int(target_rght)) 37 38 cursor.execute("UPDATE `app_comments` " \ 39 "SET `lft` = `lft` + 2 " \ 40 "WHERE `lft` > %i" % int(target_rght)) 41 42 db.commit() 43 44 new_comment = comments.Comment(body = some_var 45 lft = new_comment_lft, 46 rght = new_comment_rght, 47 ) 48 49 new_comment.save() 31 # Example view 32 def your_view(request, id): 33 your_object = get_object_or_404(models, id__exact = id) 34 35 context = {'your_object': your_object, 36 'node_tree': node_tree(id), 37 } 38 39 return render_to_response('dir/file', context) 50 40 }}} 51 41 52 53 == Getting the tree == 54 55 {{{ 56 comment_list = comments.get_list(order_by=['lft']) 57 58 stack = [] 59 for comment in comment_list: 60 # [:] creates a copy of the list, needed because .pop() modifies it on each iteration and mess with the loop 61 stack_copy = stack[:] 62 for j in stack_copy: 63 if j < comment.rght: 64 stack.pop() 65 66 stack_size = len(stack) 67 68 comment.stack = stack_size 69 70 stack.append(comentario.rght) 71 }}} 72 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: 42 Now we have a list called "node_tree" to use on your template. What's is it? There's a "stack" attribute on each node now that tells you "how far" each node is from the object. For example, every "root" node (the direct reply to a "post", for example) has a stack of 1. Every node that's an answer to the root nodes has a stack of 2. The stack respects the order (because of order_by=['lft']) that the nodes were inserted at the database. So we end up with nodes having stacks numbered like this: 74 43 75 44 {{{ … … 88 57 }}} 89 58 90 If you want to show the comments a little far from the left viewport border, based on their stack numbers, use this on your template: 59 '''Template''' 60 61 If you want to show the nodes a little far from the left viewport border, based on their stack numbers, use this on your template: 91 62 92 63 {{{ 93 <div style="margin-left:{% widthratio comentario.stack 20 100 %}%"> 94 {{ comment.body }} 95 </div> 64 {% for node in node_tree %} 65 <div style="margin-left:{% widthratio node.stack 20 100 %}%"> 66 {{ node.body }} 67 </div> 68 {% endfor %} 96 69 }}} 97 70 98 The same can be done but shrinking a table. It gets smaller, aligned to the right, the further the commentis stacked:71 The same can be done but shrinking a table. It gets smaller, aligned to the right, the further the node is stacked: 99 72 100 73 {{{ 101 <table style="width:{% widthratio comentario.stack 500 100 %}%" align="right"> 102 <tr><td> 103 {{ comment.body }} 104 </td></tr> 105 </div> 74 {% for node in node_tree %} 75 <table style="width:{% widthratio comentario.stack 500 100 %}%" align="right"> 76 <tr><td> 77 {{ node.body }} 78 </td></tr> 79 </div> 80 {% endfor %} 106 81 }}} 82 83 I will leave to you to code the necessary forms to insert the new node on your public view. Just remember to give a new Node the object_id which we're replying to. If it's a Node itself, the new node/comment will act as a "reply". If it's for any other Django content, it's like a new "root" node/comment. 84 85 Other than that, the whole mptt model and view aren't very smart. Editing them using the admin interface is hard and doesn't make sense (because nodes represent threaded content, and not single objects). 86 87 But, good luck!