Fix for find_nearest() with maximum distance in argument

[Sylvain Bougerel]

Paul Harris wrote:
> Hi Sylvain,
>
> On 08/12/2007, Sylvain Bougerel <sylvain.bougerel.devel at gmail.com> wrote:
>   
>> Hi,
>>
>> In the last commit there is 2 things:
>> - A fix for find_nearest() when used with a maximum distance in
>> argument. In certain condition it does not work properly.
>> (if the max distance given is greater than the distance from the root
>> node to the target value, and the nearest children node is not the
>> node under which the best node can be found).
>>     
>
> So it wasn't checking all the potential branches?
>   
Yes, particularly the entire left side from the root node (if the target 
value is on the right side), or the entire right side of the root node 
(if the target value is on the left side). Only happen when the given 
distance is bigger than the distance from the root to the node.
>   
>> - The behavior for find_nearest() is very slightly modified. In the
>> case where there is many closest node a same distance, the algorithm
>> now always return the node with the smaller address in memory. This is
>> to preempt the iterative implementation of find_exact().
>>
>>     
>
> note, the reason i implemented find_exact() was because you couldn't
> call tree.erase(item) and expect it to work.  it would often erase a
> different item that existed at the same location.  so find_exact()
> would look for the tree via location, and confirm that the item
> equaled the item (via the == operator, IIRC).
>
> thinking about it now, it might be possible to implement find_exact()
> via find_nearest_if().  i'll check it out on monday, it might simplify
> the code.  i have to double-check my memory of the method (not sure if
> the previous paragraph is accurate).
>   
Yes it should be possible, using 0 as a max distance:
find_nearest_if(val, 0, predicate(my_value_to_erase) ).
>> Finally, I wanted to send an apology because I forgot to mention that
>> find_nearest() was now returning the squared version of the distance.
>> So, at the moment, you will have to call sqrt() on the best distance
>> (i.e. iterator->second)  returned by find_nearest(). After a heated
>> discussion on that matter, Paul will implement a fix that restores the
>> previous behavior by default.
>>
>>     
>
> i'll try and make it so the library user can control this behaviour.
>   
Thanks for that.
>> Second, I also removed the template on the search value of
>> find_nearest(). I wanted to stick to the standard (the STL
>> implementation for the trees), but I admit that it makes sense to have
>> a template on the searched value. I will therefore restore the
>> template in find_nearest() soon.
>>
>>     
>
> i'll do this on monday too, i already made the patch, i just need to
> merge it with your changes
>
> thanks
Cheers,

- Sylvain