sorting question

Devan L devlai at gmail.com
Wed Aug 10 10:30:44 CEST 2005


Ksenia Marasanova wrote:
> Hi,
>
> I have a list that contains nodes from a tree. Each node is a class
> instance, but I'll use dictionary here to simplify the example.
> So the list looks like this:
> [
> {'id': 1,
> 'name': 'Parent node',
> 'ord_number': 1,
> 'parent_id': 0,
> 'url': '/parentnode/'},
> {'id': 2,
> 'name': 'My node',
> 'ord_number': 1,
> 'parent_id': 1,
> 'url': '/parentnode/mynode/'}
> ]
>
> Where 'ord_number' is the "sibling index". It's not always properly
> filled in; sometimes it's the same for several siblings, or doesn't
> starts with 1.
>
> 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".
> The second rule is kind of tricky to do in the database. I probably
> would need to do something like "ORDER BY
> cut_off_lastpart_from_url(url), ord_number". But there seems to be no
> native string function in Postgres to do it easily, so I desided to
> sort it in Python.
>
> So I've come up with this:
>
>         def cmp_tree(x, y):
>             if x['parent_id'] == y['parent_id']:
>                 return cmp(x['ord_number'], y['ord_number'])
>             else:
>                 return cmp(x['url'], y['url'])
>
>         nodes.sort(cmp_tree)
>
> but it doesn't work as expected. Apparently I don't have a clue about
> how sorting function work :(
>
> Can anybody help?
>
> --
> Ksenia

class Node:
	def __init__(self, name, url, order, pid, id):
                self.name = name
		self.url = url
		self.order = order
		self.pid = pid
		self.id = id
	def __repr__(self):
		return self.url
def mycmp(x,y):
	if x.pid == y.pid:
		if x.order != y.order:
			return cmp(x.order,y.order)
		return cmp(x.url,y.url)
	return cmp(x.pid,y.pid)
a = Node('ham','/test/ham/',1,0,1)
b = Node('eggs','/test/ham/eggs/',1,1,2)
c = Node('bacon','/test/ham/bacon/',1,1,3)
d = Node('spam','/test/ham/bacon/spam/',1,3,4)

Does this work for you? I haven't tested it much.




More information about the Python-list mailing list