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