• Manfred Nowak (19/19) Apr 21 2005 Currently AA is implemented by hashing with conflict resolution by
• zwang (4/31) Apr 21 2005 I would prefer a red-black tree implementation of AA using opCmp only.
• Sean Kelly (7/12) Apr 21 2005 No. But forcing us into one mandated method for comparison is intolerab...

Manfred Nowak <svv1999 hotmail.com> writes:

Currently AA is implemented by hashing with conflict resolution by 
unbalanced binary trees.

There are three items that currently bind D as a language to this 
implementation: `toHash', `opCmp' and `rehash'.

Is such a restriction tolerable?

If it is tolerable then have a look whether the right items are used:

Hashing needs at least one hash function, an _equal_ operator and one 
of these: an upper bound on the number of elements or a rehash-
operation.

Balanced binary trees need a _compare_ operator.

So currently there is more required than needed for both: an 
implementation with hashing as well as an implementation with binary 
trees. And at the same time the simpler solution for hashing in the 
case of a known upper bound on the number of elements is not 
supported.

Furthermore: both currently possible implementations do not support 
the notion of an array, which implies lookup and insertion times 
independent from the number of elements stored.

-manfred

zwang <nehzgnaw gmail.com> writes:

Manfred Nowak wrote:
 Currently AA is implemented by hashing with conflict resolution by 
 unbalanced binary trees.
 
 There are three items that currently bind D as a language to this 
 implementation: `toHash', `opCmp' and `rehash'.
 
 Is such a restriction tolerable?
 
 If it is tolerable then have a look whether the right items are used:
 
 Hashing needs at least one hash function, an _equal_ operator and one 
 of these: an upper bound on the number of elements or a rehash-
 operation.
 
 Balanced binary trees need a _compare_ operator.
 
 So currently there is more required than needed for both: an 
 implementation with hashing as well as an implementation with binary 
 trees. And at the same time the simpler solution for hashing in the 
 case of a known upper bound on the number of elements is not 
 supported.
 
 Furthermore: both currently possible implementations do not support 
 the notion of an array, which implies lookup and insertion times 
 independent from the number of elements stored.
 
 -manfred

I would prefer a red-black tree implementation of AA using opCmp only.
This will also guarantee an ascending order of enumerated keys in a foreach
loop.

Sean Kelly <sean f4.ca> writes:

In article <d48hng$91v$1 digitaldaemon.com>, Manfred Nowak says...
Currently AA is implemented by hashing with conflict resolution by 
unbalanced binary trees.

There are three items that currently bind D as a language to this 
implementation: `toHash', `opCmp' and `rehash'.

Is such a restriction tolerable?

No.  But forcing us into one mandated method for comparison is intolerable, no
matter what that method is.  Sometimes it's approriate to use equality and
sometimes it's appropriate to use equivalence, and using the other may very wel
yield an incorrect result.  I know that I personally tend to define equality and
equivalence differently for objects I want to store.


Sean