dictionary interface

[Antoon Pardon]

Op 2005-10-05, Tom Anderson schreef <twic at urchin.earth.li>:
> On Tue, 4 Oct 2005, Robert Kern wrote:
>
>> Antoon Pardon wrote:
>>
>>>   class Tree:
>>>
>>>     def __lt__(self, term):
>>>       return set(self.iteritems()) < set(term.iteritems())
>>>
>>>     def __eq__(self, term):
>>>       return set(self.iteritems()) == set(term.iteritems())
>>>
>>> Would this be a correct definition of the desired behaviour?
>>
>> No.
>>
>> In [1]: {1:2} < {3:4}
>> Out[1]: True
>>
>> In [2]: set({1:2}.iteritems()) < set({3:4}.iteritems())
>> Out[2]: False
>>
>>> Anyone a reference?
>>
>> The function dict_compare in dictobject.c .
>
> Well there's a really helpful answer. I'm intrigued, Robert - since you 
> know the real answer to this question, why did you choose to tell the 
> Antoon that he was wrong, not tell him in what way he was wrong, certainly 
> not tell him how to be right, but just tell him to read the source, rather 
> than simply telling him what you knew? Still, at least you told him which 
> file to look in. And if he knows python but not C, or gets lost in the 
> byzantine workings of the interpreter, well, that's his own fault, i 
> guess.
>
> So, Antoon, firstly, your implementation of __eq__ is, i believe, correct.
>
> Your implementation of __lt__ is, sadly, not. While sets take "<" to mean 
> "is a proper subset of", for dicts, it's a more conventional comparison 
> operation, which constitutes a total ordering over all dicts (so you can 
> sort with it, for example). However, since dicts don't really have a 
> natural total ordering, it is ever so slightly arbitrary.
>
> The rules for ordering on dicts are, AFAICT:
>
> - If one dict has fewer elements than the other, it's the lesser
> - If not, find the smallest key for which the two dicts have different 
> values (counting 'not present' as a value)
> -- If there is no such key, the dicts are equal
> -- If the key is present in one dict but not the other, the dict in which 
> it is present is the lesser
> -- Otherwise, the dict in which the value is lesser is itself the lesser
>
> In code:
>
> def dict_cmp(a, b):
>  	diff = cmp(len(a), len(b))
>  	if (diff != 0):
>  		return diff
>  	for key in sorted(set(a.keys() + b.keys())):
>  		if (key not in a):
>  			return 1
>  		if (key not in b):
>  			return -1
>  		diff = cmp(a[key], b[key])
>  		if (diff != 0):
>  			return diff
>  	return 0
>

Thanks for the explanation, but you somehow give me too much.

I have been searching some more and finally stumbled on this:

http://docs.python.org/ref/comparisons.html

  Mappings (dictionaries) compare equal if and only if their sorted
  (key, value) lists compare equal. Outcomes other than equality are
  resolved consistently, but are not otherwise defined.

This seems to imply that the specific method to sort the dictionaries
is unimported (as long as it is a total ordering). So I can use whatever
method I want as long as it is achieves this.

But that is contradicted by the unittest. If you have a unittest for
comparing dictionaries, that means comparing dictionaries has a
testable characteristic and thus is further defined.

So I don't need a full implementation of dictionary comparison,
I need to know in how far such a comparison is defined and
what I can choose.

-- 
Antoon Pardon