On Sat, 07 Aug 2004 20:26:05 +0000, Arcane Jill wrote:
> But we /can/ have our cake and eat it. [SUGGESTION:] Associative arrays don't
> need opCmp(). Honestly, they don't. Why not? - because the only thing AAs
> require is a sort criterion. That sort criterion does not have to be based on <.
> The current implementation of AAs is to sort based on (x < y), but then to have
> Object define < such that (x < y) is implemented as (&x < &y). So why not just
> have the sort criterion for AAs be (&x < &y) instead of (x < y)? If this were

I don't know how the AA algorithm works, but since &x != &y doesn't mean x
!= y, wouldn't using &x < &y not be kosher?  In other words,
import AJ's bigint;
Int a = new Int(5);
Int b = new Int(5);
bit[Int] aa;
aa[a] = true;
if (aa[b])
	printf("true\n\0");
else
	printf("false\n\0");

That should print true, but if the AA is sorted using &a and &b, it could easily print false.  Again, I don't know how the algorithm works, so this small example might work using the references, but with larger AAs, what's the point of sorting by a (basically) arbitrary and irrelevant number?

Or am I WAY off base? (If so, please explain)

Instead of using (x < y) I think the hash should be used, this way it can
be overridden by classes, since &x can't be overridden (and I really hope
I'm not wrong about that.)

John

In article <pan.2004.08.08.08.43.07.193849@teqdruid.com>, teqDruid says...

>That should print true, but if the AA is sorted using &a and &b, it could easily print false.  Again, I don't know how the algorithm works, so this small example might work using the references, but with larger AAs, what's the point of sorting by a (basically) arbitrary and irrelevant number?
>
>Or am I WAY off base? (If so, please explain)

No, you're right. Damn!

>Instead of using (x < y) I think the hash should be used, this way it can
>be overridden by classes, since &x can't be overridden (and I really hope
>I'm not wrong about that.)

I don't think that would work either, since hash(x) == hash(y) does not imply x
== y. (Although obviously using hash() would work for a hashmap). What you need
for AAs is a sort function for which precisely one of the following conditions
is always true: either (a) x preceeds y; or (b) x == y; or (c) x succeeds y.
Using (hash(x)<hash(y)) as the sort criterion would allow a fourth possibility:
that (a), (b) and (c) are all simulataneously false. An AA would fall over if
that possibility were encountered.

So I don't have an answer any more. The way that C++ does it (in std::map) is that the sort criterion is <, but < is not defined for everything, so if < isn't defined, you simply can't store your object in a std::map. C++ also provides std::hash_map, which requires storable objects to implement the function hash().

I wonder if AAs couldn't simply be re-implemented /as/ a hashmap? That way you don't need a sort criterion at all. It would require hash() to implemented for all storable objects though.

Jill

Arcane Jill wrote:

> In article <pan.2004.08.08.08.43.07.193849@teqdruid.com>, teqDruid says...
> 
>>That should print true, but if the AA is sorted using &a and &b, it could easily print false.  Again, I don't know how the algorithm works, so this small example might work using the references, but with larger AAs, what's the point of sorting by a (basically) arbitrary and irrelevant number?
>>
>>Or am I WAY off base? (If so, please explain)
> 
> No, you're right. Damn!
> 
>>Instead of using (x < y) I think the hash should be used, this way it can
>>be overridden by classes, since &x can't be overridden (and I really hope
>>I'm not wrong about that.)
> 
> I don't think that would work either, since hash(x) == hash(y) does not
> imply x == y. (Although obviously using hash() would work for a hashmap).
> What you need for AAs is a sort function for which precisely one of the
> following conditions is always true: either (a) x preceeds y; or (b) x ==
> y; or (c) x succeeds y. Using (hash(x)<hash(y)) as the sort criterion
> would allow a fourth possibility: that (a), (b) and (c) are all
> simulataneously false. An AA would fall over if that possibility were
> encountered.
> 
> So I don't have an answer any more. The way that C++ does it (in std::map) is that the sort criterion is <, but < is not defined for everything, so if < isn't defined, you simply can't store your object in a std::map. C++ also provides std::hash_map, which requires storable objects to implement the function hash().
> 
> I wonder if AAs couldn't simply be re-implemented /as/ a hashmap? That way you don't need a sort criterion at all. It would require hash() to implemented for all storable objects though.
> 
> Jill


One can see how AAs are implemented by looking at src/phobos/internal/aaA.d It is a hash table with a nifty collision data structure (none of this slow linked-list collision stuff). I bet Walter has been tweaking it for years.

In article <cf5gq2$2uq4$1@digitaldaemon.com>, Arcane Jill says...
>
> So I don't have an answer any more. The way that C++ does it (in std::map) is that the sort criterion is <, but < is not defined for everything, so if < isn't defined, you simply can't store your object in a std::map.

Basing AAs on the user implemented opCmp is not a good idea, since it's behavior is not defined. I might for example have a group of objects which are all "equal" in the way I want to compare them (opCmp() always 0, opEquals() always true) but which contain entirely different data. The AAs should use the algorithm it already uses, but it should be implemented as part of the AA, not in Object.

It's different for std::map, since it's defined and "advertised" as a _sorted_ container, placing certain restrictions on the input type (in the docs.) Also, STL always allows you to specify a custom ordering functor as an optional template parameter, so < and > might not be used at all if you don't want them to. This is a good practice for DTL to follow, btw :)

> C++ also provides
> std::hash_map, which requires storable objects to implement the function
> hash().

The hash containers are not really part of C++, just in the SGI implementation
(which gcc uses.)

Nick

In article <cf31k5$223l$2@digitaldaemon.com>, Walter says...
>
>
>"Jarrett Billingsley" <kb3ctd2@yahoo.com> wrote in message news:cf2qfj$1toe$1@digitaldaemon.com...
>> personally i don't see what's wrong with
>> operator+() , but oh well.
>
>operator+ doesn't work when you need both the forward and the 'r' versions of an operator overload. Also, opCmp handles <, <=, >, >=. And lastly, opCmp is eminently greppable.
>
>

i'd still prefer operator cmp() and similar. opAnything looks ugly. operator
Anything() not (imho). but thats me.. and doesn't really mather

"Nick" <Nick_member@pathlink.com> wrote in message news:cf5rd5$75$1@digitaldaemon.com...
> In article <cf5gq2$2uq4$1@digitaldaemon.com>, Arcane Jill says...
> >
> > So I don't have an answer any more. The way that C++ does it (in
std::map) is
> > that the sort criterion is <, but < is not defined for everything, so if
< isn't
> > defined, you simply can't store your object in a std::map.
>
> Basing AAs on the user implemented opCmp is not a good idea, since it's
behavior
> is not defined.

What do you mean by undefined behaviour?

> I might for example have a group of objects which are all
> "equal" in the way I want to compare them (opCmp() always 0, opEquals()
always
> true) but which contain entirely different data. The AAs should use the algorithm it already uses, but it should be implemented as part of the AA,
not
> in Object.

Maybe your objects are strange? In most cases my for my classes the two
objects are either a<b or a==b (or !(a<b))

> It's different for std::map, since it's defined and "advertised" as a
_sorted_
> container, placing certain restrictions on the input type (in the docs.)

I like it the way std::map dos things!

> Also,
> STL always allows you to specify a custom ordering functor as an optional
> template parameter, so < and > might not be used at all if you don't want
them
> to. This is a good practice for DTL to follow, btw :)

Yes it is!
But what do you think about the subject of removing opCmp and opEquals
from Object! They prevent us from writing templates that require these
operators
because there are default  versions of these, and they probbably don't do
what
the author of the class wants!

>
> > C++ also provides
> > std::hash_map, which requires storable objects to implement the function
> > hash().
>
> The hash containers are not really part of C++, just in the SGI
implementation
> (which gcc uses.)
>
> Nick
>
>

"Lars Ivar Igesund" <larsivar@igesund.net> wrote in message news:cf3ik6$2abe$1@digitaldaemon.com...
> Ivan Senji wrote:
>
> > opCmp shouldn't be discriminated this way! :)
>
> Ivan's correct. You got my vote.

Hooray! Thanks.
But: Walter is the one to say if i am correct or not
and it seems to me he thinks i am wrong on this subject. :(

>
> Lars Ivar Igesund

Me too. I dislike the root class having things that derived classes (or their designers) cannot make informed choices on.

And a runtime assert is a revolting way to denote that a type should not take part in comparison operations.

"Lars Ivar Igesund" <larsivar@igesund.net> wrote in message news:cf3ik6$2abe$1@digitaldaemon.com...
> Ivan Senji wrote:
>
> > opCmp shouldn't be discriminated this way! :)
>
> Ivan's correct. You got my vote.
>
> Lars Ivar Igesund

"Nick" <Nick_member@pathlink.com> wrote in message news:cf5rd5$75$1@digitaldaemon.com...
> In article <cf5gq2$2uq4$1@digitaldaemon.com>, Arcane Jill says...
> >
> > So I don't have an answer any more. The way that C++ does it (in std::map) is that the sort criterion is <, but < is not defined for everything, so if < isn't defined, you simply can't store your object in a std::map.
>
> Basing AAs on the user implemented opCmp is not a good idea, since it's behavior is not defined. I might for example have a group of objects which are all "equal" in the way I want to compare them (opCmp() always 0, opEquals() always true) but which contain entirely different data. The AAs should use the algorithm it already uses, but it should be implemented as part of the AA, not in Object.
>
> It's different for std::map, since it's defined and "advertised" as a _sorted_ container, placing certain restrictions on the input type (in the docs.) Also, STL always allows you to specify a custom ordering functor as an optional template parameter, so < and > might not be used at all if you don't want them to. This is a good practice for DTL to follow, btw :)

Those prototypes are already in. (Just not implemented in most cases.)

> > C++ also provides
> > std::hash_map, which requires storable objects to implement the function
> > hash().
>
> The hash containers are not really part of C++, just in the SGI implementation
> (which gcc uses.)

"Ivan Senji" <ivan.senji@public.srce.hr> wrote in message news:cf3i3d$2a7r$3@digitaldaemon.com...
> What is so special about opCmp, (ok it is used in AAs but couldn't compiler report: "this type cann't be used in AA because of the missing opCmp!")

Putting it in Object reserves a predictable vtbl[] slot for it.