Modified Preorder Tree Traversal in Web2Py?

351 views
Skip to first unread message

sociotech

unread,
Feb 13, 2009, 3:31:51 AM2/13/09
to web2py Web Framework
Just wondering if anyone has implemented modified preorder tree
traversal (MPTT) functions for Web2Py yet. MPTT is an efficient
approach to organizing hierarchically-related records (e.g., nested
menus, parent/child relationships, etc.) in a database.

I was hoping someone here might've already implemented it (there is an
implementation for Django and more general information here:
http://code.google.com/p/django-mptt/), but I haven't found anything
yet.

Thanks very much,

Chris

mdipierro

unread,
Feb 13, 2009, 11:24:47 AM2/13/09
to web2py Web Framework
Hi Chris,

no. But it is trivial with web2py.

Here I implemented the example in http://www.sitepoint.com/print/hierarchical-data-database/

db=SQLDB('sqlite://tree.db')
db.define_table('tree',db.Field('title'),db.Field
('left','integer'),db.Field('right','integer'))
db.tree.insert(title='Food',left=1,right=2)

def add_node(title,parent_title):

"""
add_node
('Fruit','Food')
add_node
('Meat','Food')
add_node
('Red','Fruit')
"""
parent=db(db.tree.title==parent_title).select()[0]
db(db.tree.right>=parent.right).update(right=db.tree.right+2)
db(db.tree.left>=parent.right).update(left=db.tree.left+2)
db.tree.insert(title=title,left=parent.right,right=parent.right+1)

def ancestors(title,*fields):
""" print ancestors('Red',db.tree.title)"""
node=db(db.tree.title==title).select()[0]
return db(db.tree.left<node.left)(db.tree.right>node.right).select
(orderby=db.tree.left,*fields)

def descendants(title,*fields):
""" print ancestors('Fruit',db.tree.title)"""
node=db(db.tree.title==title).select()[0]
return db(db.tree.left>node.left)(db.tree.right<node.right).select
(orderby=db.tree.left,*fields)

def test():
print db().select(db.tree.ALL)
add_node('Fruit','Food')
print db().select(db.tree.ALL)
add_node('Meat','Food')
print db().select(db.tree.ALL)
add_node('Red','Fruit')
print db().select(db.tree.ALL)
print ancestors('Red',db.tree.title)
print descendants('Fruit',db.tree.title)

test()

OUTPUT:
tree.id,tree.title,tree.left,tree.right
1,Food,1,2

tree.id,tree.title,tree.left,tree.right
1,Food,1,4
2,Fruit,2,3

tree.id,tree.title,tree.left,tree.right
1,Food,1,6
2,Fruit,2,3
3,Meat,4,5

tree.id,tree.title,tree.left,tree.right
1,Food,1,8
2,Fruit,2,5
3,Meat,6,7
4,Red,3,4

tree.title
Food
Fruit

tree.title
Red

mdipierro

unread,
Feb 13, 2009, 11:27:46 AM2/13/09
to web2py Web Framework
Chris, you manage to package this a little better please let me know.
You could write an alterego entry about it or just post the code
somewhere.

Massimo

On Feb 13, 10:24 am, mdipierro <mdipie...@cs.depaul.edu> wrote:
> Hi Chris,
>
> no. But it is trivial with web2py.
>
> Here I implemented the example inhttp://www.sitepoint.com/print/hierarchical-data-database/

sociotech

unread,
Feb 13, 2009, 5:30:56 PM2/13/09
to web2py Web Framework
Massimo,

Thanks very much for your quick response and helpful code.

I'm new to Web2Py, but I'm really enjoying it so far. In a way, it
reminds me of the rapid development positive feedback loop I felt
when I first encountered Borland's Delphi environment. Addictively
fun!

I'm not sure what's involved in packaging the code better, but I'll
give it
a shot as soon as i figure it out :)

Thanks again!

Chris

mdipierro

unread,
Feb 14, 2009, 10:30:50 AM2/14/09
to web2py Web Framework
All I mean by packaging is add any other function that may be useful
and try document the example. You way also
want to post it somewhere for other people to use it. Thanks for
bringing this up. It is interesting.

Massimo
Reply all
Reply to author
Forward
0 new messages