Hi,
I started a nested sets implementation
Just sharing the code. I welcome any thoughts you have
2 files - nstree_controller (just quick and dirty tests of the model),
and nstree_model
[nstree_controller :]
t1 = nstree(db, db.tree1)
def index():
return dict(message="Version " + nstree.version)
def test_path():
_id = 33
return dict(message = " > ".join([node.name for node in t1.path
(_id)]))
def test_removetree():
_id = request.vars.id if request.vars.id else 3
t1.remove_tree(_id)
return dict(message="Success")
def test_delete():
_id = request.vars.id if request.vars.id else 19
node = t1.delete(_id)
return dict(message= node.name + " deleted ")
def test_get():
_id = request.vars.id if request.vars.id else 15
#nodes = t1.ancestors(_id)
#nodes = t1.descendants(_id)
nodes = t1.children(_id)
return dict(message= ", ".join([node.name for node in nodes]))
def test_gettree():
root_id = request.vars.root_id if request.vars.root_id else 1
nodes = t1.tree(root_id)
return dict(message="Count "+str(len(nodes)))
def test_add():
root_id = request.vars.root_id if request.vars.root_id else
t1.roots()[0].id
r1 = t1.add(root_id, name='1')
r2 = t1.add(root_id, name='2')
r3 = t1.add(root_id, name='3')
t1.add(r1, name='11')
t1.add(r1, name='12')
return dict(message="Success")
def test_create_roots():
'''
t1.create_root(name='root1')
t1.create_root(name='root2')
t1.create_root(name='root3')
t1.create_root(name='root4')
'''
roots = t1.roots()
return dict(message="Roots count : " + str(len(roots)))
[nstree_model:]
db.define_table('tree1',
SQLField('name', "string", 128),
SQLField('lft','integer'),
SQLField('rgt','integer'),
SQLField('level','integer'),
SQLField('root_id','integer'),
SQLField('parent_id','reference tree1'),
)
#
# A Nested Sets implementation
# need to pass a table with following fields:
# lft, rgt, level, parent_id, root_id - all fields of type int
# -------
# Notes:
# - table can contain multiple roots
#
class nstree:
version = "1.0.0.04"
def __init__(self, db, dbtable):
self.db = db
self.dbtable = dbtable
#self.lft = dbtable.lft
#self.rgt = dbtable.rgt
#self.level = dbtable.level
#self.parent_id = dbtable.parent_id
#self.root_id = dbtable.root_id
#
# Methods for building tree (create, delete nodes)
#
def create_root(self, **fields):
_id = self.dbtable.insert(lft=1, rgt=2, level=0, **fields)
_root = self.dbtable[_id]
_root.update_record(root_id = _id)
return _root
def add(self, parent_id, **fields): return self.add_last_child
(parent_id, **fields)
def add_last_child(self, parent_id, **fields):
_parent = self.dbtable[parent_id]
q1 = self.dbtable.rgt >= _parent.rgt
q2 = self.dbtable.lft >= _parent.rgt
q3 = self.dbtable.root_id == _parent.root_id
self.db(q1)(q3).update(rgt=self.dbtable.rgt+2)
self.db(q2)(q3).update(lft=self.dbtable.lft+2)
return self.dbtable.insert(
parent_id = parent_id,
lft = _parent.rgt,
rgt = _parent.rgt+1,
level = _parent.level+1,
root_id = _parent.root_id,
**fields
)
def delete(self, id): return self.remove(id)
def remove(self, id):
node = self.dbtable[id]
delta = node.rgt - node.lft + 1
q1 = self.dbtable.lft >= node.lft
q2 = self.dbtable.rgt <= node.rgt
self.db(q1)(q2).delete()
self.db(self.dbtable.lft > node.rgt).update(lft =
self.dbtable.lft - delta)
self.db(self.dbtable.rgt > node.rgt).update(rgt =
self.dbtable.rgt - delta)
return node
def remove_descendants(self, id):
node = self.dbtable[id]
delta = node.rgt - node.lft + 1
q1 = self.dbtable.lft > node.lft
q2 = self.dbtable.rgt < node.rgt
self.db(q1)(q2).delete()
self.db(self.dbtable.lft > node.rgt).update(lft =
self.dbtable.lft - delta)
self.db(self.dbtable.rgt > node.rgt).update(rgt =
self.dbtable.rgt - delta)
def remove_tree(self, id):
self.db(self.dbtable.root_id == id).delete()
#
# Methods for retrieving nodes
#
def roots(self): return self.db(self.dbtable.lft == 1).select()
def tree(self, root_id): return self.db(self.dbtable.root_id ==
root_id).select(orderby = self.dbtable.lft)
def ancestors(self, id):
node = self.dbtable[id]
q1 = self.dbtable.lft < node.lft
q2 = self.dbtable.rgt > node.rgt
q3 = self.dbtable.root_id == node.root_id
return self.db(q1)(q2)(q3).select(orderby = self.dbtable.lft)
def path(self, id):
node = self.dbtable[id]
q1 = self.dbtable.lft <= node.lft
q2 = self.dbtable.rgt >= node.rgt
q3 = self.dbtable.root_id == node.root_id
return self.db(q1)(q2)(q3).select(orderby = self.dbtable.lft)
def descendants(self, id):
node = self.dbtable[id]
q1 = self.dbtable.lft > node.lft
q2 = self.dbtable.rgt < node.rgt
q3 = self.dbtable.root_id == node.root_id
return self.db(q1)(q2)(q3).select(orderby = self.dbtable.lft)
def children(self, id): return self.db(self.dbtable.parent_id ==
id).select(orderby = self.dbtable.lft)
#
# Methods for checking or getting state of node(s)
#
def num_children(self, node): return int((node.rgt-node.lft-1)/2)
def is_root(self, node): return node.id == node.root_id
def is_leaf(self, node): return node.lft == node.rgt-1
def is_child(self, node1, node2): return node1.lft > node2.lft
and node1.rgt < node2.rgt
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"web2py-users" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/web2py?hl=en
-~----------~----~----~----~------~----~------~--~---
