zwang wrote:
<snip>
> What do you want to prove by this example?
> The compiler does not care how you implement the opCmp operator at all.

Oops.  That code example was a red herring, as there were no hash collisions.  I reported this bug a while back

http://www.digitalmars.com/drn-bin/wwwnews?digitalmars.D.bugs/2643

and was sure I had discovered that the bug doesn't apply to classes. However, it seems that either

(a) I was imagining it
(b) it's just GDC 0.11
(c) there's been a regression somewhere.

Stewart.

-- 
My e-mail is valid but not my primary mailbox.  Please keep replies on the 'group where everyone may benefit.

In article <d7j4u7$bjs$2@digitaldaemon.com>, Walter says...
>
>
>"zwang" <nehzgnaw@gmail.com> wrote in message news:d7gp4d$ml7$1@digitaldaemon.com...
>> Walter wrote:
>> > To work in an AA, it needs to be sortable and hashable. How would
>interfaces
>> > be sorted?
>>
>> Why is sortability required for a hashed AA?
>
>To deal with the inevitable hash collisions.

All this requires is an equality check.  Sorting just allows for more optimal
worst-case performance (O(log N) vs. O(N)).


Sean

In article <d7khl9$1rh5$1@digitaldaemon.com>, Sean Kelly says...
>>>
>>> Why is sortability required for a hashed AA?
>>
>>To deal with the inevitable hash collisions.
>
>All this requires is an equality check.  Sorting just allows for more optimal
>worst-case performance (O(log N) vs. O(N)).
>
>Sean

Here is a proposal: If objects are unequal according to opEquals, then why can't it just sort objects according to their memory location/pointer value, or some other low-level value guaranteed to be different for different objects? This should be much faster than calling opCmp, and it always works.

Nick

"Stewart Gordon" <smjg_1998@yahoo.com> wrote in message news:d7juh4$1387$1@digitaldaemon.com...
> Walter wrote:
> > "zwang" <nehzgnaw@gmail.com> wrote in message news:d7gp4d$ml7$1@digitaldaemon.com...
> >
> >> Walter wrote:
> >>
> >>> To work in an AA, it needs to be sortable and hashable. How would interfaces be sorted?
> >>
> >> Why is sortability required for a hashed AA?
> >
> > To deal with the inevitable hash collisions.
>
> Doesn't follow:
>
> (a) Last time I checked the AA implementation worked perfectly well on
> classes (but not structs) where unequal objects can rank equally in order.

It'll appear to work if the hashes don't collide.

> (b) Java's HashMap manages perfectly well without this "required"
"feature".

You can resolve collisions by using a linear list. D's AA implementation uses a binary tree to resolve collisions, which is much faster.

Walter wrote:
> "Stewart Gordon" <smjg_1998@yahoo.com> wrote in message
> news:d7juh4$1387$1@digitaldaemon.com...
<snip>
>> (a) Last time I checked the AA implementation worked perfectly well on
>> classes (but not structs) where unequal objects can rank equally in order.
> 
> It'll appear to work if the hashes don't collide.

At least I *thought* it worked - but see my reply to zwang.  But try this modification to the code example I posted that way:

----------
class UintBox {
    uint value;

    this(uint v) { value = v; }

    uint toHash() {
        writefln("toHash: %d", value);
        return 0;
    }

    int opEquals(Object o) {
        writefln("opEquals: %d", value);
        return value == (cast(UintBox) o).value;
    }

    int opCmp(Object o) {
        writefln("opCmp: %d", value);
        return 0;
    }
}
----------

(main function as before)

It calls opEquals during both assignment and lookup.  What does it use the result for?

How about using it to check that the match it's found really is a match, and if not then look further down the tree?

>> (b) Java's HashMap manages perfectly well without this "required" "feature".
> 
> You can resolve collisions by using a linear list. D's AA implementation
> uses a binary tree to resolve collisions, which is much faster.

You mean reimplement D's AAs to use a linear list instead?  Why not have this built in as well?  The answer seems to be because the presence of Object.opCmp makes it practically impossible to tell when you need to.

Stewart.

-- 
My e-mail is valid but not my primary mailbox.  Please keep replies on
the 'group where everyone may benefit.