sort(cmp=func)

[Tobiah]

On Wed, 09 Jul 2008 20:58:32 -0700, Daniel Fetchinson wrote:

>> I have a list of objects that generate code.  Some
>> of them depend on others being listed first, to
>> satisfy dependencies of others.
>>
>> I wrote a cmp function something like this:
>>
>> def dep_cmp(ob1, ob2):
>> 	
>> 	if ob1.name in ob2.deps:
>> 		return -1
>> 	else:
>> 		return 1
>>
>> I also tried returning 0 when there were no dependency
>> relationships between the objects.
>>
>> This failed, because every object was not compared with
>> ever other.  I imagine that this is because sort assumes
>> that if a > b and b > c, then a > c.  In my case, this
>> isn't really true.  If a is not dependent on b, and
>> b is not dependent on c, that doesn't mean that a is not
>> dependent on c.
>>
>> Is there a better way?
> 
> It's only meaningful to talk about sorting if your particular
> definition of "<" is transitive. I.e. a < b and b < c should imply a <
> c. If this is not satisfied, it doesn't make sense to sort according
> to your "<" definition. It's just not a well-defined operation and no
> trick will make it work.

There is a meaningful relationship here however.  Basically, some
items must precede some other items.  There are more than one
correct orders however.  Here was my eventual solution. I had to 
compare each item with each other item, swapping on failed 
dependencies.  Recursion simplified this greatly:

def dep_sort(tables):

        for this_index in range(len(tables)):
                this_table = tables[this_index]
                for prev_index in range(this_index):
                        prev_table = tables[prev_index]
                        if this_table.name in prev_table.deps:
                                tables[prev_index] = this_table
                                tables[this_index] = prev_table
                                dep_sort(tables)
                                return

** Posted from http://www.teranews.com **