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

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.

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