dictionary interface

[Bengt Richter]

On 5 Oct 2005 08:23:53 GMT, Antoon Pardon <apardon at forel.vub.ac.be> wrote:

>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.
>
"other outcomes" may not in general mean orderings are defined,
even when  ==  and != are well defined. E.g., below

>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.
>
A couple of data points that may be of interest:

 >>> {'a':0j} < {'a':1j}
 Traceback (most recent call last):
   File "<stdin>", line 1, in ?
 TypeError: cannot compare complex numbers using <, <=, >, >=

and
 >>> cmp(0j, 1j)
 Traceback (most recent call last):
   File "<stdin>", line 1, in ?
 TypeError: cannot compare complex numbers using <, <=, >, >=

but
 >>> {'a':0j} == {'a':1j}
 False
 >>> {'a':1j} == {'a':1j}
 True

Regards,
Bengt Richter