AA with complex keytype?
Frits van Bommel
fvbommel at REMwOVExCAPSs.nl
Sat Feb 10 02:41:23 PST 2007
Manfred Nowak wrote:
> Frits van Bommel wrote
>
>> you must always do compare(a, b), never compare(b, a)
>
> No. Because if you are at a node in the tree where a==b, you are done.
> And if you are at a node in the tree where a!=b, you will go into the
> direction dictated by opCmp, which is by construction of opCmp the same
> for all permutations.
> This holds for all operations on the tree.
Let's say a!=b. If compare(a,b) returns a!=b, as you proposed, that
evaluates to true, which converts to integer 1, representing "greater".
So it returns that a>b holds. So if b is the node in the tree, you would
then continue searching in the *right* branch.
If on the other hand compare(b,a) is called, by the same process it
returns 1 indicating b>a holds. If b is still the tree node, you would
then continue your search in the *left* branch
So the implementation needs to be careful about parameter order, and I
don't want to go dig into the source to find out if it is. Nor do I want
to check every Phobos/Tango release I use to find out if it _still_ is.
Since the API doesn't specify this, I think it would be a mistake to
rely on it even if it _currently_ holds.
More information about the Digitalmars-d
mailing list