For complex numbers comparisons other than == and != are not defined.

AA's require classes to have comparisons defined.

Why are AA's of complex numbers allowed?

-manfred

Manfred Nowak wrote:
> For complex numbers comparisons other than == and != are not defined.
> 
> AA's require classes to have comparisons defined.
> 
> Why are AA's of complex numbers allowed?

Asociative arrays are unordered. All they need is a hash function, which can be defined over any data type.


Andrei

Andrei Alexandrescu (See Website For Email) wrote:
> Manfred Nowak wrote:
>> For complex numbers comparisons other than == and != are not defined.
>>
>> AA's require classes to have comparisons defined.
>>
>> Why are AA's of complex numbers allowed?
> 
> Asociative arrays are unordered. All they need is a hash function, which can be defined over any data type.

Not the DMD associative arrays. They require full ordering.

/Oskar

Oskar Linde wrote:
> Andrei Alexandrescu (See Website For Email) wrote:
>> Manfred Nowak wrote:
>>> For complex numbers comparisons other than == and != are not defined.
>>>
>>> AA's require classes to have comparisons defined.
>>>
>>> Why are AA's of complex numbers allowed?
>>
>> Asociative arrays are unordered. All they need is a hash function, which can be defined over any data type.
> 
> Not the DMD associative arrays. They require full ordering.


Yes, ordering (opCmp) is used in case of hash collisions.

L.

Manfred Nowak wrote:
> For complex numbers comparisons other than == and != are not defined.

Indeed.

> AA's require classes to have comparisons defined.

Also correct.

> Why are AA's of complex numbers allowed?

For one thing, complex numbers aren't classes :P.


Seriously: AA's use the TypeInfo.compare() method to compare. For complex types, this is implemented as lexicographical ordering (compare the real parts, and return the result unless it's equal; in that case, return the result of comparing the imaginary parts).

The reason "<" and friends aren't defined for complex types is that there's no definition that makes any mathematical sense (at least, not more than other definitions).
Fortunately, AA's don't require the ordering to make any mathematical sense at all, they just need some way to decide in what order to put them in a binary three if a hash collision should occur. As long as the order is consistent[1] (a < b && b < c => a < c, that sort of thing) they're happy.


[1]: I'm sure there's a mathematical term for this that I can't currently remember.

Frits van Bommel Wrote:

> [1] (a < b && b < c => a < c, that sort of thing)
> 
> ...
> 
> [1]: I'm sure there's a mathematical term for this that I can't currently remember.

Transitivity! :)

Brian Byrne

Frits van Bommel wrote
> As long as the order is consistent[1] (a < b && b <
> c => a < c, that sort of thing) they're happy.

Thank you. This answers my question.

But immediately another arises:
Why are classes required to implement opCmp( Object) for AA's to
function properly?

Currently AA's misbehave if opCmp(Object) is not overwritten for a class, but no error is thrown.

For the transitivity of an ordering it suffices for opCmp(Object) to always give "==" if the objects are equal, and give "<" if they are not.

It should be easy to implement this as the default opCmp(Object).

Manfred Nowak wrote:
> Frits van Bommel wrote
>> As long as the order is consistent[1] (a < b && b <
>> c => a < c, that sort of thing) they're happy.
> 
> Thank you. This answers my question.
> 
> But immediately another arises:
> Why are classes required to implement opCmp( Object) for AA's to function properly?

Because the TypeInfo for objects uses Object.opCmp (if neither is null)

> Currently AA's misbehave if opCmp(Object) is not overwritten for a class, but no error is thrown.
> 
> For the transitivity of an ordering it suffices for opCmp(Object) to always give "==" if the objects are equal, and give "<" if they are not.

By "that sort of thing", I meant "and similar properties". For instance, the order also needs to be non-symmetric: a < b => !(b < a)[1]. Your proposed default implementation doesn't satisfy that.

IIRC Object used to compare addresses by default, but that was problematic because that behavior disallows moving garbage collectors.

> It should be easy to implement this as the default opCmp(Object).

But as explained above it wouldn't work correctly...



[1]: Actually, since the compare return value can have three meanings (less than, equal to, greater than), that would be: a < b => b > a

Brian Byrne wrote:
> Frits van Bommel Wrote:
> 
>> [1] (a < b && b < c => a < c, that sort of thing) 
>>
>> ...
>>
>> [1]: I'm sure there's a mathematical term for this that I can't currently remember.
> 
> Transitivity! :)

"that sort of thing" == "and stuff like that", i.e. not *just* that.
If I'd meant transitivity, I'd have said that (that term I know).

Frits van Bommel wrote
> Your proposed default implementation doesn't satisfy that.
In fact those requirements are necessary only for binary tress built in
the collision buckets.
If one can live with linear lists in the collsions baskets, then
opCmp(Object) is allowed to degenerate to !opEquals(Object).

-manfred