ModifiedPreorderTreeTraversalInAdmin: models.2.py

File models.2.py, 10.0 KB (added by [530], 19 years ago)

updated version

Line 
1from django.db import models, connection
2from django.db.models.query import Q
3# -*- coding: utf-8 -*-
4
5# Implementation of a Modified Preorder Tree Traversal algorithm
6# Theory taken from http://www.sitepoint.com/print/hierarchical-data-database
7# More examples at: http://code.djangoproject.com/wiki/ModifiedPreorderTreeTraversal
8# http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
9
10CHOICES = (
11 ('before','Before'),
12 ('after','After'),
13 ('below','Below')
14 )
15
16#set table name here fixme, detect table automatically
17TABLE = 'pages_page'
18
19class TreeManager(models.Manager):
20
21 def get_query_set(self):
22
23 sql = "SELECT node.id, count(parent.lft) AS level " \
24 "FROM %s AS node, " \
25 "%s AS parent " \
26 "WHERE node.lft BETWEEN parent.lft AND parent.rgt " \
27 "GROUP BY node.lft, node.id " \
28 "ORDER BY node.lft" % (TABLE, TABLE)
29
30 cursor = connection.cursor()
31 cursor.execute(sql)
32 rows = cursor.fetchall()
33
34 qc = Q()
35 self.leveldict = {}
36 for i in rows:
37 id,level = i
38 self.leveldict[id] = level
39 qc = qc|Q(id__exact=id)
40
41 self.model.add_to_class('levels', self.leveldict)
42
43 return super(TreeManager, self).get_query_set().filter(qc)
44
45 def all(self): # gets children
46
47 sql = "SELECT node.id " \
48 "FROM %s AS node, " \
49 "%s AS parent " \
50 "WHERE node.lft BETWEEN 1 AND 5000 " \
51 "AND node.lft BETWEEN parent.lft AND parent.rgt " \
52 "GROUP BY node.lft, node.id " \
53 "HAVING (count(parent.lft)-1) = 0 " \
54 "ORDER BY node.lft" % (TABLE, TABLE)
55
56 cursor = connection.cursor()
57 cursor.execute(sql)
58 rows = cursor.fetchall()
59
60 top = []
61 for i in rows:
62 top.append(super(TreeManager, self).get_query_set().get(pk=i[0]))
63
64 return top
65
66class Page(models.Model):
67
68 label = models.CharField(maxlength=255)
69
70 # To create categories for a website menu, we won't probably need to record
71 # what user created the node. But if nodes are used for threaded comments
72 # or forums posts, it's a good idea to have.
73 where = models.CharField(maxlength=6,choices=CHOICES,blank=True,null=True)
74 wich = models.ForeignKey("self",blank=True,null=True)
75
76 lft = models.PositiveIntegerField(blank=True,null=True,db_index = True)
77 rgt = models.PositiveIntegerField(blank=True,null=True)
78
79 manager = TreeManager()
80
81 def __repr__(self):
82 # Page.objects.all() should get whole list as tree with level , repeat --- per level
83 # rertun'---' times level + self.label
84 try:
85 level = self.levels[self.id]
86 except:
87 level=1
88
89 return ('----' * level) + ' ' + self.label
90
91 def before(self,related_node):
92
93 # adds node before picked node self.wich
94 cursor = connection.cursor()
95
96 target_rgt = related_node.rgt - 1
97 target_lft = related_node.lft - 1
98
99 cursor.execute("UPDATE %s " \
100 "SET rgt = rgt + 2 " \
101 "WHERE rgt > %i " % (self.tbl(), int(target_rgt)))
102
103 cursor.execute("UPDATE %s " \
104 "SET lft = lft + 2 " \
105 "WHERE lft > %i " % (self.tbl(), int(target_lft)))
106
107 self.rgt = related_node.rgt
108 self.lft = related_node.lft
109
110 def after(self,related_node):
111
112 # adds node after picked node self.wich
113
114 cursor = connection.cursor()
115
116 target_rgt = related_node.rgt
117
118 cursor.execute("UPDATE %s " \
119 "SET rgt = rgt + 2 " \
120 "WHERE rgt > %i " % (self.tbl(), int(target_rgt)))
121
122 cursor.execute("UPDATE %s " \
123 "SET lft = lft + 2 " \
124 "WHERE lft > %i " % (self.tbl(), int(target_rgt)))
125
126 self.lft = related_node.lft + 2
127 self.rgt = related_node.rgt + 2
128
129 def below(self,related_node):
130
131 # *fixme* should make sure below does not work on nodes already having child nodes
132 # because that does not have a happy ending
133 if related_node.rgt == related_node.lft + 1:
134
135 cursor = connection.cursor()
136
137 target_rgt = related_node.rgt - 1
138
139 cursor.execute("UPDATE %s " \
140 "SET rgt = rgt + 2 " \
141 "WHERE rgt > %i " % (self.tbl(), int(target_rgt)))
142
143 cursor.execute("UPDATE %s " \
144 "SET lft = lft + 2 " \
145 "WHERE lft > %i " % (self.tbl(), int(target_rgt)))
146
147 self.rgt = related_node.rgt + 1
148 self.lft = related_node.lft + 1
149
150 else:
151
152 sql = "SELECT node.lft, node.rgt " \
153 "FROM %s AS node, " \
154 "%s AS parent " \
155 "WHERE node.lft BETWEEN %s AND %s " \
156 "AND node.lft BETWEEN parent.lft AND parent.rgt " \
157 "GROUP BY node.lft, node.rgt " \
158 "HAVING (count(parent.lft)-1) = 1 " \
159 "ORDER BY node.lft" % (self.tbl(), self.tbl(), related_node.lft, related_node.rgt)
160
161 cursor = connection.cursor()
162 cursor.execute(sql)
163 rows = cursor.fetchall()
164
165 related_node.lft, related_node.rgt = rows[0]
166
167 self.before(related_node)
168
169 def top(self):
170
171 # adds node to bottom of top level
172 # If there are zero nodes for this tree so far, we will just
173 # insert with lft = 1 and rgt = 2
174
175 cursor = connection.cursor()
176 cursor.execute("SELECT MAX(rgt) FROM %s LIMIT 1" % self.tbl() )
177
178 row = cursor.fetchone()
179
180 current_max_rgt = row[0]
181
182 if current_max_rgt is None:
183 self.lft = 1
184 self.rgt = 2
185 # But if there are already pages attached to the tree we will put
186 # this new one at the top level (to the right of the 'tree')
187 else:
188 self.lft = current_max_rgt + 1
189 self.rgt = current_max_rgt + 2
190
191 def skip(self):
192 u=False
193 # *fixme* reset parentnode to avoid future errors
194
195 def save(self):
196
197 where = self.where # where to place node ralative to related_node
198
199
200 if self.id:
201 dont_trust_the_form = Page.manager.get(pk=self.id)
202 self.lft = dont_trust_the_form.lft
203 self.rgt = dont_trust_the_form.rgt
204
205 try: # test for related node
206 related_node = self.wich
207 except:
208 related_node = False
209
210 if where:
211 where = "skip" # don't do anything if no node is selected
212 else: # add to toplevel if no node is selected
213 where = "top"
214
215 if self.rgt: # node exists just change content, fix this to allow moving og nodes and child nodes
216 where = "skip"
217
218 # done testing for now, execute!
219
220 if where=="before":
221 self.before(related_node)
222
223 if where=="after":
224 self.after(related_node)
225
226 if where=="below":
227 self.below(related_node)
228
229 if where=="skip":
230 self.skip()
231
232 if where=="top":
233 self.top()
234
235 self.where = ''
236 self.wich = ''
237
238 super(Page, self).save()
239
240 def delete(self):
241 # delete nodes and child nodes
242 if self.rgt and self.lft:
243 width = self.rgt - self.lft + 1
244
245 del_sql = "DELETE FROM %s WHERE lft BETWEEN %s AND %s" % (self.tbl(), self.lft, self.rgt)
246 upd_sql_1 = "UPDATE %s SET rgt = rgt - %s WHERE rgt > %s" % (self.tbl(), width, self.rgt)
247 upd_sql_2 = "UPDATE %s SET lft = lft - %s WHERE rgt > %s" % (self.tbl(), width, self.rgt)
248
249 cursor = connection.cursor()
250 cursor.execute(del_sql)
251 cursor.execute(upd_sql_1)
252 cursor.execute(upd_sql_2)
253
254 super(Page, self).delete()
255
256 def get_parent(self):
257
258 parentid = 5000
259 if self.where == 'below':
260 parentid = self.wich.id
261 else:
262 sql = "SELECT parent.id " \
263 "FROM %s AS node, " \
264 "%s AS parent " \
265 "WHERE node.lft BETWEEN parent.lft AND parent.rgt" \
266 "AND node.id = %s " \
267 "ORDER BY node.lft" % (self.tbl(), self.tbl(), self.wich.id)
268
269 cursor = connection.cursor()
270 cursor.execute(sql)
271
272 row = cursor.fetchall()
273
274 parentid=row[0][0]
275
276 return Page.manager.get(pk=parentid)
277
278 def get_children(self): # gets children
279
280 sql = "SELECT node.id " \
281 "FROM %s AS node, " \
282 "%s AS parent " \
283 "WHERE node.lft BETWEEN %s AND %s " \
284 "AND node.lft BETWEEN parent.lft AND parent.rgt " \
285 "GROUP BY node.lft, node.id " \
286 "HAVING (count(parent.lft)-1) = 1 " \
287 "ORDER BY node.lft" % (self.tbl(), self.tbl(), self.lft, self.rgt)
288
289 cursor = connection.cursor()
290 cursor.execute(sql)
291 rows = cursor.fetchall()
292
293 children = []
294 for i in rows:
295 children.append(Page.manager.get(pk=i[0]))
296
297 return children
298
299
300
301 def tbl(self): # finds table name how do i do this in the TreeManager
302
303 name = self.__class__.__name__.lower()
304 app = __name__.split('.')[1]
305
306 return app + '_' + name
307
308 class Meta:
309 ordering = ['lft',]
310
311 class Admin:
312 list_display = ('__repr__','lft','rgt')
313 fields = (
314 (None, { 'fields' : ('label',) }),
315 ('Position', { 'fields': ('where','wich') }),
316 ('Advanced', { 'fields': ('lft','rgt') , 'classes': 'collapse' }),
317 )
318 manager = TreeManager()
Back to Top