[Tutor] depth first with a twist

[Magnus Lycka]

At Sun, 2 Mar 2003 11:41:44 -0500, Poor Yorick wrote:
>Hi, I majored in a social science, so I'm hoping this group can help me
>fill in the gaps;)

Sure.

>I have a dictionary where each key contains a list of
>values. Values 1 and 2 are parent, and older_sibling, respectively. I
>would like to append an order number onto each list, using parent and
>older_sibling to determine the order, and am looking for an iterative
>solution. I have written a function which works, but boy, is it ugly!

Ok. Maybe this indicates that you need a different abstraction.

>     def OrderDepth(self):

I see that this is a method (due to indentation, and "self"), but the fact
that you don't use "self" a single time in the code suggests that the code
is in fact in the wrong class! Methods should work with the attributes of
the instance of the class! May I suggest having a look at Arthur Riel's
book "Object-Oriented Design Heuristics".

In this case I think the logic should be in a Tree Item class. Below,
I instanciate it from your dict, but it might be unwarranted to use
both represetations in practice. As I see it, each parent object should
be able to sort out his children, and then it's fairly trivial. I don't
know if this is fewer lines of code than your version, but it makes
more sense to me. Each method is fairly trivial.

I didn't include the number before the printed item, but that's a
trivial addition. E.g. instead of a print statement in "printTree"
there could be an append to a list (either known by name or passed
as argument), and then it's trivial to iterate the list and print
with a number before each line. It's also possible to pass an
object that returns an incremented number on each access, to printTree.

# A registry of items in the tree, might not be global in "real" code.
reg = {}

class TreeItem:
     def __init__(self, name, parent, older_sibling, note):
         self.name = name
         self.parent = parent
         self.older_sibling = older_sibling
         self.note = note
         self.children = []
         # Register myself by name, so my children will find me.
         reg[name] = self

     def tellParent(self):
         # Hi daddy, I'm your kid
         if self.parent:
             try:
                 reg[self.parent].addChild(self)
             except KeyError:
                 print self.name, "is missing his parent", self.parent
                 raise

     def addChild(self, child):
         # Oops, this one claims to be my kid. ;)
         self.children.append(child)

     def printTree(self):
         # First me, then my kids (and their kids) in order
         print self
         self.sortChildren()
         for child in self.children:
             child.printTree()

     def sortChildren(self):
         lastChild = None
         sorted = []
         while self.children:
             for child in self.children:
                 if child.older_sibling == lastChild:
                     self.children.remove(child)
                     sorted.append(child)
                     lastChild = child.name
                     break
             else:
                 # Error handling, we don't expect to get here
                 print "Bad child list"
                 print "Sorted", map(str, sorted)
                 print "Leftovers", map(str, self.children)
                 raise SystemExit
         self.children = sorted

     def __str__(self):
         return self.name

d = {'monty': [None, None, "Monty Python's Flying Circus"],
      'actors': ['monty', None, 'Actor Data'],
      'sketches': ['monty', 'actors', 'Sketch Data'],
      'basic': ['actors', None, 'Basic Bio'],
      'filmography': ['actors', 'basic', 'Filmography']}

for name, (parent, older, note) in d.items():
     TreeItem(name, parent, older, note) # Self-registering...

# Once all items are registered we can inform parents of their
# chldren.
for item in reg.values():
     item.tellParent()

# Find root item(s) and print tree(s)
for item in reg.values():
     if item.parent is None:
         # Root item!
         item.printTree()

This should print:

monty
actors
basic
filmography
sketches

If you want the number before, write an incrementor class
like this:

class Incr:
     def __init__(self):
         self.x = 0
     def get(self):
         self.x += 1
         return self.x

and modify one method:

     def printTree(self, incr = Incr()):
         print incr.get(), self
         self.sortChildren()
         for child in self.children:
             child.printTree(incr)

Then it should come out like:

1 monty
2 actors
3 basic
4 filmography
5 sketches


-- 
Magnus Lycka, Thinkware AB
Alvans vag 99, SE-907 50 UMEA, SWEDEN
phone: int+46 70 582 80 65, fax: int+46 70 612 80 65
http://www.thinkware.se/  mailto:magnus@thinkware.se