www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 323] New: Error: need opCmp for class Bar

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=323

           Summary: Error: need opCmp for class Bar
           Product: D
           Version: unspecified
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: bugzilla digitalmars.com
        ReportedBy: someanon yahoo.com


I think this use to work; now on Linux dmd.166, it reports:

Error: need opCmp for class Bar

============================================
template Valuable(T) {
protected:
  float m_value = 0.0;

public:
  float value()  {return m_value;}
  void  value(float v)  {m_value=v;}
  int opCmp(T other) {
    int r;

    if      (value < other.value)  {r = -1;}
    else if (value > other.value)  {r =  1;}

    return r;
  }
}

class Foo {
}

class Bar : Foo {
  mixin  Valuable!(Bar);  // defined opCmp to compare Bar

public:
  this(float v) {
    m_value = v;
  }
}

int main(char[][] args) {
  Bar[3] bars;

  for (int i = 0; i < 3; i++) {
    bars[i] = new Bar(i);
  }
  bars.sort;

  return 0;
}

============================================


--
Sep 03 2006
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=323






Same problem on WindowsXP:

Error: need opCmp for class Bar


--
Sep 03 2006
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=323






Two more questions:

1) this is reported at compile time, but errors out at run-time. Maybe the
compiler does see the opCmp, but other things goes wrong.

2) Before I isolate the problem, in my real program: on Linux, it builds and
errors out at run-time.  But on WinXP, I have a link time error: "Unexpected
OPTLINK Termination at EIP=0044C37B".  Not sure if it's related to this opCmp
issue.


--
Sep 03 2006
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=323






Sorry, typo:

1) this is reported at compile time ...

should be:

1) this is NOT reported at compile time ...


--
Sep 03 2006
prev sibling next sibling parent Thomas Kuehne <thomas-dloop kuehne.cn> writes:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

d-bugmail puremagic.com schrieb am 2006-09-03:

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



 I think this use to work; now on Linux dmd.166, it reports:


http://www.digitalmars.com/d/changelog.html#new0163






 Error: need opCmp for class Bar


<snip>

   int opCmp(T other) {
     int r;

     if      (value < other.value)  {r = -1;}
     else if (value > other.value)  {r =  1;}

     return r;
   }


The cause is a nasty result of D's function inheritance and overriding.

http://www.digitalmars.com/d/function.html





Thus "int T.opCmp(T other)" dosen't override "int Object.opCmp(Object o)" ...

Should do the trick:




















Thomas


-----BEGIN PGP SIGNATURE-----

iD8DBQFE/+hrLK5blCcjpWoRAn19AJ4xroQQhMNn1DkxLCAafdrzXw2UswCeNZfA
2eWscmpgVCkItONOreZGRmo=
=UXBJ
-----END PGP SIGNATURE-----
Sep 07 2006
prev sibling next sibling parent reply Sean Kelly <sean f4.ca> writes:
Since D's associative arrays use opCmp to resolve collisions, any class 
that has opEquals defined should probably have opCmp defined also.  The 
old default implementation of Object.opCmp in Phobos was not compatible 
with compacting GCs so it was replaced with a version that throws an 
exception on use.  However, there is a default implementation that 
actually works and is compatible with compacting GCs:

     int opCmp(Object o)
     {
	return this !is o;
     }

Compare to opEquals:

     int opEquals(Object o)
     {
         return this is o;
     }

The opCmp function above forces the binary tree chaining mechanism into 
a linked-list, and equivalence is resolved by pointer equality rather 
than some ordering mechanism.  It won't be as fast as an ordering 
implementation of opCall for the degenerate case but it has the benefit 
of being immune to object movement.  If a default implementation of 
opEquals is to remain in Phobos then I suggest adopting the default 
opCmp implementation above as well.
Sep 07 2006
parent reply xs0 <xs0 xs0.com> writes:
Sean Kelly wrote:

 Since D's associative arrays use opCmp to resolve collisions, any class 
 that has opEquals defined should probably have opCmp defined also.  The 
 old default implementation of Object.opCmp in Phobos was not compatible 
 with compacting GCs so it was replaced with a version that throws an 
 exception on use.  However, there is a default implementation that 
 actually works and is compatible with compacting GCs:
 
     int opCmp(Object o)
     {
     return this !is o;
     }


That's not a really good solution, as no usable ordering is defined (a>b 
and b>a will always be true whenever a !is b). While it may work for 
(degenerate) insertion into a binary tree, it's (imho) worse than 
throwing an exception in practically all other cases. For example, a 
quick sort will not only run really slow in O(n^2) time but also produce 
an unsorted result without any indication of error.


xs0
Sep 07 2006
parent reply Sean Kelly <sean f4.ca> writes:
xs0 wrote:

 Sean Kelly wrote:

 Since D's associative arrays use opCmp to resolve collisions, any 
 class that has opEquals defined should probably have opCmp defined 
 also.  The old default implementation of Object.opCmp in Phobos was 
 not compatible with compacting GCs so it was replaced with a version 
 that throws an exception on use.  However, there is a default 
 implementation that actually works and is compatible with compacting GCs:

     int opCmp(Object o)
     {
     return this !is o;
     }


 
 That's not a really good solution, as no usable ordering is defined (a>b 
 and b>a will always be true whenever a !is b). While it may work for 
 (degenerate) insertion into a binary tree, it's (imho) worse than 
 throwing an exception in practically all other cases. For example, a 
 quick sort will not only run really slow in O(n^2) time but also produce 
 an unsorted result without any indication of error.


Ah good point.  So any ideas?  Personally, I'd be happy if the default 
AA used a linked-list for chaining and opEquals for comparison so this 
wasn't an issue, but that seems a foregone conclusion.  I'm mostly 
concerned about providing default behavior that makes sense for the 
common case.  The problem I've run into is that I have objects which 
need to be used as keys in an AA but are not inherently sortable.
Sep 07 2006
parent reply xs0 <xs0 xs0.com> writes:
Sean Kelly wrote:

 xs0 wrote:
 Ah good point.  So any ideas?  Personally, I'd be happy if the default 
 AA used a linked-list for chaining and opEquals for comparison so this 
 wasn't an issue, but that seems a foregone conclusion.  I'm mostly 
 concerned about providing default behavior that makes sense for the 
 common case.  The problem I've run into is that I have objects which 
 need to be used as keys in an AA but are not inherently sortable.


Well, one possibly good solution would be to templatize AAs and remove 
opCmp from Object. That way, you'd get an error when using comparison on 
objects without opCmp (most other operators work that way) and the 
template could test for its presence and use different implementations 
for each.

Another nice consequence would be the possibility of having optimized 
implementations for specific types; most probably even a single 
implementation could be considerably faster, because the compiler would 
know the exact type at compile-time, producing an optimized version of 
code for each.


xs0
Sep 07 2006
parent reply Sean Kelly <sean f4.ca> writes:
xs0 wrote:

 Sean Kelly wrote:

 xs0 wrote:
 Ah good point.  So any ideas?  Personally, I'd be happy if the default 
 AA used a linked-list for chaining and opEquals for comparison so this 
 wasn't an issue, but that seems a foregone conclusion.  I'm mostly 
 concerned about providing default behavior that makes sense for the 
 common case.  The problem I've run into is that I have objects which 
 need to be used as keys in an AA but are not inherently sortable.


 
 Well, one possibly good solution would be to templatize AAs and remove 
 opCmp from Object. That way, you'd get an error when using comparison on 
 objects without opCmp (most other operators work that way) and the 
 template could test for its presence and use different implementations 
 for each.


Some fancier AA support would be nice, but I'm not sure how to add 
templates to the built-in syntax.  I just noticed something confusing in 
the spec however.  Why are classes intended to be used as keys in an AA 
required to implement both opCmp *and* opEquals?  Since the AA is backed 
by a binary tree I would expect it determine 'equality' as equivalence 
using opCmp.  It's quite common for me to define classes that are 
equivalent but not equal, and also classes that can be compared for 
equality but not sorted.  But it sounds like both would not be 
compatible with D's built-in AA implementation.  I'm beginning to feel 
that any possible performance advantage that can be offered from binary 
tree chaining over linked list chaining is overshadowed by the 
limitations it imposes on the use of AAs in general.  Can someone 
suggest an alternate default implementation for opCmp that solves these 
problems?


Sean
Sep 07 2006
next sibling parent reply Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
Sean Kelly wrote:

 xs0 wrote:

 Sean Kelly wrote:

 xs0 wrote:
 Ah good point.  So any ideas?  Personally, I'd be happy if the 
 default AA used a linked-list for chaining and opEquals for 
 comparison so this wasn't an issue, but that seems a foregone 
 conclusion.  I'm mostly concerned about providing default behavior 
 that makes sense for the common case.  The problem I've run into is 
 that I have objects which need to be used as keys in an AA but are 
 not inherently sortable.


 Well, one possibly good solution would be to templatize AAs and remove 
 opCmp from Object. That way, you'd get an error when using comparison 
 on objects without opCmp (most other operators work that way) and the 
 template could test for its presence and use different implementations 
 for each.


 
 Some fancier AA support would be nice, but I'm not sure how to add 
 templates to the built-in syntax.  


I think xs0 was thinking of making AAs templates, and then the compiler 
would add syntactic sugar to that template to achieve current syntax.
So something like
char[float[]] a; would become something like AA!(char, float[]) a;


 I just noticed something confusing in 
 the spec however.  Why are classes intended to be used as keys in an AA 
 required to implement both opCmp *and* opEquals?  Since the AA is backed 
 by a binary tree I would expect it determine 'equality' as equivalence 
 using opCmp.


I would too.


 It's quite common for me to define classes that are 
 equivalent but not equal, and also classes that can be compared for 
 equality but not sorted.  But it sounds like both would not be 
 compatible with D's built-in AA implementation.  


It is a rather big limitation.


 I'm beginning to feel 
 that any possible performance advantage that can be offered from binary 
 tree chaining over linked list chaining is overshadowed by the 
 limitations it imposes on the use of AAs in general.  Can someone 
 suggest an alternate default implementation for opCmp that solves these 
 problems?


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.
Sep 07 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
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.

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?
Sep 07 2006
next sibling parent reply Sean Kelly <sean f4.ca> writes:
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.
 
 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?


The one I've been wrestling with is a Thread class, as it has no data 
that is static and unique for the life of the object.  The thread id is 
only guaranteed to be unique while the thread is active, and the id 
isn't even assigned until Thread.start is called.  Threads simply have 
no features which inherently support ordering, but it makes sense to 
compare two Thread objects for equality simply by comparing object 
addresses.


Sean
Sep 07 2006
next sibling parent Walter Bright <newshound digitalmars.com> writes:
Sean Kelly wrote:

 Walter Bright wrote:

 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?


 
 The one I've been wrestling with is a Thread class, as it has no data 
 that is static and unique for the life of the object.  The thread id is 
 only guaranteed to be unique while the thread is active, and the id 
 isn't even assigned until Thread.start is called.  Threads simply have 
 no features which inherently support ordering, but it makes sense to 
 compare two Thread objects for equality simply by comparing object 
 addresses.


One way to solve this is to have the Thread constructor add a unique 
sequence number.
Sep 08 2006
prev sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Sean Kelly wrote:

 Walter Bright wrote:

 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?


 
 The one I've been wrestling with is a Thread class, as it has no data 
 that is static and unique for the life of the object.  The thread id is 
 only guaranteed to be unique while the thread is active, and the id 
 isn't even assigned until Thread.start is called.  Threads simply have 
 no features which inherently support ordering, but it makes sense to 
 compare two Thread objects for equality simply by comparing object 
 addresses.


How do you do a hash for it if there's no constant data?
Sep 08 2006
parent reply Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:

 Sean Kelly wrote:

 Walter Bright wrote:

 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?


 The one I've been wrestling with is a Thread class, as it has no data 
 that is static and unique for the life of the object.  The thread id 
 is only guaranteed to be unique while the thread is active, and the id 
 isn't even assigned until Thread.start is called.  Threads simply have 
 no features which inherently support ordering, but it makes sense to 
 compare two Thread objects for equality simply by comparing object 
 addresses.


 
 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;
     }
}

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.


Sean
Sep 08 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
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.


 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.
Sep 08 2006
parent reply Sean Kelly <sean f4.ca> writes:
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));
Sep 08 2006
parent Walter Bright <newshound digitalmars.com> writes:
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.
Sep 08 2006
prev sibling next sibling parent Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
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.
Sep 08 2006
prev sibling parent reply xs0 <xs0 xs0.com> writes:
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.


But if you hide the implementation via AA syntax sugar, those many 
programmers won't have to deal with templates at all?


 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?


Object :)

OK, that may be a bit Java-ish, but the simplest way to obtain a unique 
key/identifier is simply "new Object()". It works in HashMaps, is equal 
only to itself, and that's about everything you need in some cases.

----

I think opCmp should be removed from Object, it causes nothing but grief:
- it errors at runtime if not implemented, instead of at compile time
- it requires you to cast the parameter
- can never be inlined

Further, I think toHash should also be removed from Object, because the 
current implementation is buggy wrt compacting GCs, and as Object has no 
inherent data except its possibly changing address, a correct default 
toHash can only return 0 (or another constant), making it useless 
(alternatively, we could acknowledge that a compacting GC for a systems 
language is practically impossible to do and stop calling the current 
implementation buggy).

Then, a templated version of AAs can check for existence of those two 
functions and implements itself accordingly. Worst case is obviously 
just a list/array of key/value pairs with linear scanning on lookup, but

- at least it works
- can be still useful/fast enough for maps with only a few keys

----

BTW, is there any particular reason for hash_t? I think it would be 
better to use uint and make it non-platform-dependent (the latter is 
bad, and the extra 32 bits don't help at all in any realistic case)


xs0
Sep 08 2006
parent Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
xs0 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.


 
 But if you hide the implementation via AA syntax sugar, those many 
 programmers won't have to deal with templates at all?


Yes, everything would remain as it is now, except better.


 

 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?


 
 Object :)


LOL


 
 OK, that may be a bit Java-ish, but the simplest way to obtain a unique 
 key/identifier is simply "new Object()". It works in HashMaps, is equal 
 only to itself, and that's about everything you need in some cases.
 
 ----
 
 I think opCmp should be removed from Object, it causes nothing but grief:
 - it errors at runtime if not implemented, instead of at compile time
 - it requires you to cast the parameter
 - can never be inlined


Thanks xs0, you have put my exact thoughts into words :)
Sep 08 2006
prev sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Sean Kelly wrote:

 Some fancier AA support would be nice, but I'm not sure how to add 
 templates to the built-in syntax.  I just noticed something confusing in 
 the spec however.  Why are classes intended to be used as keys in an AA 
 required to implement both opCmp *and* opEquals?  Since the AA is backed 
 by a binary tree I would expect it determine 'equality' as equivalence 
 using opCmp.  It's quite common for me to define classes that are 
 equivalent but not equal, and also classes that can be compared for 
 equality but not sorted.  But it sounds like both would not be 
 compatible with D's built-in AA implementation.  I'm beginning to feel 
 that any possible performance advantage that can be offered from binary 
 tree chaining over linked list chaining is overshadowed by the 
 limitations it imposes on the use of AAs in general.  Can someone 
 suggest an alternate default implementation for opCmp that solves these 
 problems?


Although the current AA implementation only uses opCmp, having both 
available means that an implementation could use both or either. 
Sometimes opEquals can be computed a lot more efficiently than opCmp.
The current implementation uses hashing with binary trees, but an 
implementation isn't required to do it that way.

Hashing with binary trees has proven in practice to be very efficient. 
It beats even C++ templated hash tables. I'm sure with some careful 
coding one can create a faster one customized to a particular data type, 
but the current general purpose one is pretty darned fast and compact. 
It's the central algorithm in DMDScript, for example, and DMDScript 
still beats the other javascript implementations around the block.
Sep 07 2006
parent reply Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:

 
 Although the current AA implementation only uses opCmp, having both 
 available means that an implementation could use both or either. 
 Sometimes opEquals can be computed a lot more efficiently than opCmp.
 The current implementation uses hashing with binary trees, but an 
 implementation isn't required to do it that way.


This is good to know.  I'd considered playing with the current 
implementation, but was concerned about altering spec-defined behavior.


 Hashing with binary trees has proven in practice to be very efficient. 
 It beats even C++ templated hash tables. I'm sure with some careful 
 coding one can create a faster one customized to a particular data type, 
 but the current general purpose one is pretty darned fast and compact. 
 It's the central algorithm in DMDScript, for example, and DMDScript 
 still beats the other javascript implementations around the block.


I agree that it's got fantastic performance--my concerns here are really 
more practical, as I have objects I want to use as keys that don't 
contain any data which could be used for sorting purposes.  But it 
sounds like there's enough wiggle room in the spec to find some 
reasonable middle ground.  Thanks!


Sean
Sep 07 2006
parent Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Sean Kelly wrote:

 Walter Bright wrote:
 

 Although the current AA implementation only uses opCmp, having both 
 available means that an implementation could use both or either. 
 Sometimes opEquals can be computed a lot more efficiently than opCmp.
 The current implementation uses hashing with binary trees, but an 
 implementation isn't required to do it that way.


 
 
 This is good to know.  I'd considered playing with the current 
 implementation, but was concerned about altering spec-defined behavior.
 

 Hashing with binary trees has proven in practice to be very efficient. 
 It beats even C++ templated hash tables. I'm sure with some careful 
 coding one can create a faster one customized to a particular data 
 type, but the current general purpose one is pretty darned fast and 
 compact. It's the central algorithm in DMDScript, for example, and 
 DMDScript still beats the other javascript implementations around the 
 block.


 
 
 I agree that it's got fantastic performance--my concerns here are really 
 more practical, as I have objects I want to use as keys that don't 
 contain any data which could be used for sorting purposes.  But it 
 sounds like there's enough wiggle room in the spec to find some 
 reasonable middle ground.  Thanks!
 
 
 Sean


If I recall correctly, the old "standard" Object.opCmp simply compared
addresses.  Maybe 
that could be written into a mixin somewhere to be used by classes with no
inherent 
logical order of their own.

-- Chris Nicholson-Sauls
Sep 08 2006
prev sibling next sibling parent %u <z gg.com> writes:
==========================================================================

The cause is a nasty result of D's function inheritance and overriding.

http://www.digitalmars.com/d/function.html





Thus "int T.opCmp(T other)" dosen't override "int Object.opCmp(Object o)" ...

Should do the trick:




















==========================================================================

This is realy ugly.

For these special method (.dup, .opCmp, .equals), Why can't we have coveriant
parameters, or even anchored types as in eiffel?

http://www.pi.informatik.tu-darmstadt.de/inf1/eiff-ref/chap12.htm

So we can write more clean code:

class Dog : Animal {

Dog dup()           {...}
int opCmp(Dog d)    {...}
int opEquals(Dog d) {...}

}

Instead of casting Object around?
Sep 11 2006
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=323






Covariant function parameters make it very difficult to do overloading - should
it be an overload, or an override?


--
Jun 25 2008
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=323


bugzilla digitalmars.com changed:

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





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.


--
Jun 25 2008