ModifiedPreorderTreeTraversalInAdmin: models.py

File models.py, 10.0 KB (added by [530], 17 years ago)
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