Changes between Initial Version and Version 1 of ModifiedPreorderTreeTraversal

Timestamp:

Feb 1, 2006, 5:59:32 AM (19 years ago)

Author:

inerte@…

Comment:

Adding ModifiedPreorderTreeTraversal

ModifiedPreorderTreeTraversal

@@ +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...
+
+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 :)
+
+Here's a model, a view and a couple functions to help you implement it.
+
+'''Model'''
+
+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.
+
+{{{
+class Comment(meta.Model):
+    body = meta.TextField()
+    lft = meta.PositiveIntegerField(db_index = True)
+    rght = meta.PositiveIntegerField(db_index = True)
+}}}
+
+== New record ==
+
+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:
+
+{{{
+comment = get_object_or_404(comments, pk = comment_id)
+
+target_rght = comment.rght - 1
+
+new_comment_lft = target_rght + 1
+new_comment_rght = target_rght + 2
+   
+cursor = db.cursor()   
+
+cursor.execute("UPDATE `app_comments` " \
+               "SET `rght` = `rght` + 2 " \
+               "WHERE `rght` > %i" % int(target_rght))
+
+cursor.execute("UPDATE `app_comments` " \
+               "SET `lft` = `lft` + 2 " \
+               "WHERE `lft` > %i" % int(target_rght)
+
+db.commit()
+
+new_comment = comments.Comment(body = some_var
+                              lft = new_comment_lft,
+                              rght = new_comment_rght,
+                              )
+
+new_comment.save()
+}}}
+
+
+== Getting the tree ==
+
+{{{
+comment_list = comments.get_list(order_by=['lft'])
+
+stack = []
+for comment in comment_list:
+    # [:] creates a copy of the list, needed because .pop() modifies it on each iteration and mess with the loop
+    stack_copy = stack[:]
+    for j in stack_copy:
+        if j < comment.rght:
+            stack.pop()                    
+
+    stack_size = len(stack)
+
+    comment.stack = stack_size       
+
+    stack.append(comentario.rght)
+}}}
+
+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. Something like this:
+
+{{{
+1
+ 2
+  3
+  3
+ 2
+
+1
+ 2
+  3
+}}}
+
+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:
+
+{{{
+<div style="margin-left:{% widthratio comentario.stack 20 100 %}%">
+  {{ comment.body }}
+</div>
+
+}}}
+
+The same can be done but shrinking a table. It gets smaller, aligned to the right, the further the comment is stacked:
+
+{{{
+<table style="width:{% widthratio comentario.stack 500 100 %}%" align="right">
+  <tr><td>
+  {{ comment.body }}
+  </td></tr>
+</div>
+}}}