1 | from django.db import models, connection |
---|
2 | from 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 | |
---|
10 | CHOICES = ( |
---|
11 | ('before','Before'), |
---|
12 | ('after','After'), |
---|
13 | ('below','Below') |
---|
14 | ) |
---|
15 | |
---|
16 | #set table name here fixme, detect table automatically |
---|
17 | TABLE = 'pages_page' |
---|
18 | |
---|
19 | class 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 | |
---|
66 | class 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() |
---|