Changes between Version 2 and Version 3 of ModifiedPreorderTreeTraversal


Ignore:
Timestamp:
02/04/2006 09:46:53 AM (9 years ago)
Author:
inerte@…
Comment:

MPTT as an app

Legend:

Unmodified
Added
Removed
Modified
  • ModifiedPreorderTreeTraversal

    v2 v3  
    11There'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.
    22
    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...
     3Basically, it allows you to discover every children, or parents, or the whole tree, with a single query. Very efficient! And good for threaded discussions...
    44
    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.
    66
    7 Here's a model, a view and a couple functions to help you implement it.
     7If 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
    88
    9 '''Model'''
     9If 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.
    1010
    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
     13Drop the mptt folder inside your Django project folder.
     14
     15Change to the directory of your project (where manage.py is) and type:
    1216
    1317{{{
    14 class Comment(meta.Model):
    15     body = meta.TextField()
    16     lft = meta.PositiveIntegerField(db_index = True)
    17     rght = meta.PositiveIntegerField(db_index = True)
     18python manage.py install mptt
     19python manage.py sqlindexes mptt
    1820}}}
    1921
    20 == New record ==
     22If 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!
    2123
    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
     26Edit the views.py file from your app to call mptt's views.py and pass its function to a template:
    2327
    2428{{{
    25 comment = get_object_or_404(comments, pk = comment_id)
     29from your_project_name.mptt.views import *
    2630
    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
     32def 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)
    5040}}}
    5141
    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:
     42Now 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:
    7443
    7544{{{
     
    8857}}}
    8958
    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
     61If you want to show the nodes a little far from the left viewport border, based on their stack numbers, use this on your template:
    9162
    9263{{{
    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 %}
    9669}}}
    9770
    98 The same can be done but shrinking a table. It gets smaller, aligned to the right, the further the comment is stacked:
     71The same can be done but shrinking a table. It gets smaller, aligned to the right, the further the node is stacked:
    9972
    10073{{{
    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 %}
    10681}}}
     82
     83I 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
     85Other 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
     87But, good luck!
Back to Top