Walter Bright wrote:
> Sean Kelly wrote:
>> Walter Bright wrote:
>>> How do you do a hash for it if there's no constant data?
>>
>> Using address, currently :-p  But that obviously has to change.  What might make the most sense from a hash perspective would be something like this:
>>
>> class C {
>>     hash_t hash;
>>     hash_t toHash() {
>>         if (hash != hash.init)
>>             return hash;
>>         hash = cast(hash_t) this;
>>         return hash;
>>     }
>> }
> 
> That will fail if the object gets moved.

Not at all.  The hash value is stored the first time it's computed, and it will remain constant for the life of the object.  If the object is later moved and a new object created in its old position then the two objects would simply have the same hash value.  Collisions would still be resolved with opCmp or opEquals depending on AA implementation.  In the worst case however, I'll admit that this could result in long hash chains.

>> But that leaves opCmp to wrestle with.  An "object id" would be a reasonable universal solution, but I don't want to pay for the synchronized op on construction.  I suppose I'm simply having a hard time getting over the idea that an object's address is is not a unique identifier in GCed languages.
> 
> An opCmp has the same problem that toHash does; fix it for either and it is fixed for both. I think you'll have to do a unique id for each in order to store them in an AA, or else wait until the thread id is assigned before storing it.

opCmp doesn't have quite the same problem as toHash because it's completely valid (if ill-advised) for toHash to always return zero while opCmp may only evaluate two objects as equivalent if they actually are equivalent.  Essentially, I see toHash as a weak identity operation, opEquals as a strong identity operation, and opCmp as an ordering operation.

I'll admit that the template idea is appealing, but not if it would require adding a ton of stuff to object.d.  I think this could probably be avoided by passing the comparator as a delegate parameter however, and would allow the compiler to switch between two AA implementations (one for objects with opCmp, and one for objects with only opEquals) to handle each class of objects in a reasonable manner.  This should also eliminate the need for a default opCmp and opEquals implementation:


// implicit or in object.d:

extern (C)
{
    void* aaGetByCmp(void* key, int function(void*,void*) cmp);
    void* aaGetByEquals(void* key, bool function(void*,void*) equals);
}

bool doCmp(T)(void* a, void* b)
{
    return a == b ? 0 :
           a ? (cast(T)a).opCmp(cast(T)b) :
               (cast(T)b).opCmp(cast(T)a);
}

bool doEquals(T)(void* a, void* b)
{
    return cast(T)a == cast(T)b;
}

// user code:

class C
{
    hash_t toHash();
    bool opEquals( C val );
}

C[C] myAA;
C key = new C;
myAA[key] = key;

// this call:

C val = myAA[key];

// translates to:

C val = cast(C) aaGetByEquals(key, &doEquals!(C));

Sean Kelly wrote:
> Walter Bright wrote:
>> Sean Kelly wrote:
>>> Walter Bright wrote:
>>>> How do you do a hash for it if there's no constant data?
>>>
>>> Using address, currently :-p  But that obviously has to change.  What might make the most sense from a hash perspective would be something like this:
>>>
>>> class C {
>>>     hash_t hash;
>>>     hash_t toHash() {
>>>         if (hash != hash.init)
>>>             return hash;
>>>         hash = cast(hash_t) this;
>>>         return hash;
>>>     }
>>> }
>>
>> That will fail if the object gets moved.
> 
> Not at all.  The hash value is stored the first time it's computed, and it will remain constant for the life of the object.  If the object is later moved and a new object created in its old position then the two objects would simply have the same hash value.  Collisions would still be resolved with opCmp or opEquals depending on AA implementation.  In the worst case however, I'll admit that this could result in long hash chains.

Storing a sequence number, instead of the address, will produce the same result and will also work with opEquals and opCmp. The only downside is you'll need to sync the counter accesses upon construction, but thread stuff is sync'd anyway so I don't think that is a big problem.

On Fri, 08 Sep 2006 13:06:43 -0700, Kirk McDonald <kirklin.mcdonald@gmail.com> wrote:
>I think that Object's opEquals should simply call opCmp.
>
>class Object {
>     // ...
>     int opEquals(Object o) {
>         return this.opCmp(o);
>     }
>     // ...
>}

I think you mean...

  return (this.opCmp(o) == 0);

>This way, a class can simply overload opCmp to overload all comparison operations. If it can more efficiently overload opEquals, then it is free to do so.

The problem is, every class already has an opEquals which it inherits from Object.

Also, it's often good to make it explicit that you really intend something, rather than to have it just magically happen.

-- 
Remove 'wants' and 'nospam' from e-mail.

Ivan Senji wrote:
> Walter Bright wrote:
>> Ivan Senji wrote:
>>> Yes: here is a suggestion: remove opCmp from Object. I think the only reason it is there is that when AAs where first implemented templates weren't where they are now so there was no way to check if an object has opCmp. These days a template version of AAs would be much better, and it would (if I'm not mistaken) remove the need for opCmp to be in Object.
>>
>> While it'd be fun to offer a templated version of AAs, I feel the core capabilities should be available to the user without needing templates. This is because many programmers are not comfortable with them.
> 
> I didn't mean change int[char[]] to AA!(int, char[]),
> I meant it would be nice to change the implementation to a template, without changing the syntax.
> 
> I guess this is one thing in D I still can't get over the C++ way.
> (a couple of years back I thought iostream and <<, >> where the best :)
> But these AAs and their requirements are bugging me: Why do I have to (in my class ABC) declare opCmp to be int opCmp(Object o)?
> IMO that sucks because when used in an AA it's not like there is going to be objects of different types as keys.
> 
> And that is a textbook example of when a template should be used.
> 
> 
>>
>> Can you give an example of a class that could not have a meaningful opCmp implementation that one would want to put into an AA?
> 
> Sean Kelly gave a good example.
> 
> But I have nothing against AAs requiring opCmp, opEquals, toHash or what ever it needs, but would prefer for them not to be in Object.

This is not an issue I know a lot about, but that seems a good idea.
For the record, both Java and C# have an Equals and a Hash method in the Object class, but the Compare method is not. Classes that are comparable implement the IComparable interface, which is a generic interface since the introduction of generics, meaning that the Compare method parameter does not have to be of type Object, like in D.
(Note: of course, in D an interface wouldn't be needed, an under-the-hoods templated AA implementation can simply check if the opCmp method exists or not, in what is effectively a compile-time version of duck-typing)


-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D

http://d.puremagic.com/issues/show_bug.cgi?id=323





------- Comment #8 from bugzilla@digitalmars.com  2008-06-25 02:57 -------
Covariant function parameters make it very difficult to do overloading - should it be an overload, or an override?


-- 

http://d.puremagic.com/issues/show_bug.cgi?id=323


bugzilla@digitalmars.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |WONTFIX




------- Comment #9 from bugzilla@digitalmars.com  2008-06-25 03:18 -------
I don't think Sean's default opCmp should be used, because it will hide errors where one has not declared an overriding opCmp correctly. I think it is best to leave the throwing one as the default.


--