sorting question

[Peter Otten]

Ksenia Marasanova wrote:

> I want to sort this list with the following rules:
> 1. The parent must always come before the children in the list
> 2. Nodes with the same parent must be sorted by 'ord_number'
> 
> The first rule is easy, cause I can use 'url' for it. List with nodes
> is coming from the database, so I just do "ORDER BY url".

I think you cannot get away with your first rule, but have to operate on the
full path instead. Otherwise the position of inner nodes would sometimes be
determined by their url and sometimes by their ord_number *during* *the*
*same* *sort*.

class Node(object):
    nodes = {} # defeats garbage collection
    def __init__(self, id, name, ord_number, parent_id, url):
        self.id = id
        self.name = name
        self.ord_number = ord_number
        self.parent_id = parent_id
        self.url = url
        assert id not in self.nodes
        self.nodes[id] = self
    def get_path(self):
        node = self
        path = []
        while node is not None:
            path.append(node)
            node = self.nodes.get(node.parent_id)
        path.reverse()
        return path
    def get_key(self):
        return [node.ord_number for node in self.get_path()]
    def __cmp__(self, other):
        return cmp(self.get_key(), other.get_key())
    def __str__(self):
        return "%s %s" % (self.name, self.get_key())

nodes = [Node(**row) for row in data]

# key argument not necessary, but should be faster
nodes.sort(key=Node.get_key)

I'm too lazy to do the test cases, so you have to check it yourself.

Peter