SV: clueless newbie question

Max Møller Rasmussen maxm at normik.dk
Mon Sep 25 11:34:02 CEST 2000


From: MCM [mailto:absolutniks at hotmail.com]

>I'm trying to figure out how to do recursion in a threaded discussion list
>I'm writing in python, where every message has an id as follows "1_3_3_1".
>The first number is the absolute parent, then the subparent (sorry, lack of
>formal training prevents me from explaining it properly. hope this is clear
>enough).

Well you can always do it the wimpy way and skip recursion altogether.

I have made this small class, which does the same thing without recursion.
It uses a simple dict with a tuple as a key instead.

Take these items to put in the tree:

1: dad
2: mom
3: dad_son
4: mom_daugther
5: mom_daugther_2
6: dad_son_son
7: dad_son_2

That should give a tree like this:

dad
   dad_son
      dad_son_son
   dad_son_2
mom
   mom_daugther
   mom_daugther_2

It will have these keys:

(0,1) = 'dad'
(0,2) = 'mom'
(0,1,3) 'dad_son'
(0,2,4) 'mom_daugther'
(0,2,5) 'mom_daugther_2'
(0,1,3,6) 'dad_son_son'
(0,1,7) 'dad_son_2'

when you then sort the keys it will look like this:

(0,1) = 'dad'
(0,1,3) = 'dad_son'
(0,1,3,6) = 'dad_son_son'
(0,1,7) = 'dad_son_2'
(0,2) = 'mom'
(0,2,4) = 'mom_daugther'
(0,2,5) = 'mom_daugther_2'

The length of the key will then tell you the indention level of the message.

The "tree" can then be processed like a normal dict with tuples as keys. I
like this way of doing it for threaded diskussions.

---------------------------
class fakeTree:
    def __init__(self):
        #create tree and insert root element
        self.treeKeys = {}
        self.treeKeys[0] = (0,)
        self.tree = {}
        self.tree[(0,)] = ''
        
    def insert(self, id, parent, value):
        # create new key
        keyList = list(self.treeKeys[parent])
        keyList.append(id)
        keyTuple = tuple(keyList)
        self.treeKeys[id] = keyTuple
        # insert in tree with new tuple key
        self.tree[keyTuple] = value
 
    def print_(self):
        keyList = self.tree.keys()
        keyList.sort()
        spacesInIndent = 3
        for key in keyList[1:]:
            print spacesInIndent * (len(key)-2) * ' ' + self.tree[key]

tree = fakeTree()
tree.insert(1, 0, 'dad')
tree.insert(2, 0, 'mom')
tree.insert(3, 1, 'dad_son')
tree.insert(4, 2, 'mom_daugther')
tree.insert(5, 2, 'mom_daugther_2')
tree.insert(6, 3, 'dad_son_son')
tree.insert(7, 1, 'dad_son_2')
tree.print_()
---------------------------
Output:

dad
   dad_son
      dad_son_son
   dad_son_2
mom
   mom_daugther
   mom_daugther_2

----------------------------

a little trick in html is to use the singe char with the value #160 (press
ALT+0160 on the numeric keypad to get it in yout editor) instead of  .
It makes the source a lot prettier, and smaller to.

Regards
	Max M




More information about the Python-list mailing list