Fix for find_nearest() with maximum distance in argument

[Paul Harris]

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?

> - 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).

> 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.

> 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!
Paul