www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - AA with complex keytype?

reply Manfred Nowak <svv1999 hotmail.com> writes:
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
Feb 09 2007
next sibling parent reply "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail erdani.org> writes:
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
Feb 09 2007
parent reply Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
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
Feb 09 2007
parent Lionello Lunesu <lio lunesu.remove.com> writes:
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.
Feb 09 2007
prev sibling parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
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.
Feb 09 2007
next sibling parent reply Brian Byrne <bdbyrne wisc.edu> writes:
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
Feb 09 2007
parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
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).
Feb 09 2007
parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Frits van Bommel" <fvbommel REMwOVExCAPSs.nl> wrote in message 
news:eqi7ph$io7$2 digitaldaemon.com...
 "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).

Woah, woah, woah! Calm down there, killer!
Feb 09 2007
parent Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Jarrett Billingsley wrote:
 "Frits van Bommel" <fvbommel REMwOVExCAPSs.nl> wrote in message 
 news:eqi7ph$io7$2 digitaldaemon.com...
 "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).

Woah, woah, woah! Calm down there, killer!

I think that came over wrong. Maybe I should have put in a smiley or something. I just wanted to clarify that point. So hard to convey tone and stuff over a text-only medium...
Feb 09 2007
prev sibling parent reply Manfred Nowak <svv1999 hotmail.com> writes:
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).
Feb 09 2007
parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
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
Feb 09 2007
parent reply Manfred Nowak <svv1999 hotmail.com> writes:
Frits van Bommel wrote
 Your proposed default implementation doesn't satisfy that.

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
Feb 09 2007
parent Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Manfred Nowak wrote:
 Frits van Bommel wrote
 Your proposed default implementation doesn't satisfy that.

the collision buckets.

Yes, but the current implementation *does* use binary trees, IIRC.
 If one can live with linear lists in the collsions baskets, then
 opCmp(Object) is allowed to degenerate to !opEquals(Object).

That might not be a great solution, especially when you need to consider that user-defined hash functions may not be very good...
Feb 09 2007