Can't replicate C++ behavior

[eadf]

In voronoi_builder.hpp line 400 the key of a map is altered in-place. Naturally I can't do this in Rust, so the obvious solution is to remove and then re-insert the object with the new key. Problem is that does not always work. Somehow the beach-line calculations sometimes requires that the object remains in the old position, while the key is altered.

The root of the problem is that the beachline keys in boost are not transitive (as I understand it). A<B, B<C and yet this could also be true: C<A.

    // Change the (A, B) bisector node to the (A, C) bisector node.
    const_cast<key_type&>(it_first->first).right_site(site3);

Same section in rust is builder.rs line 663

Issue can be tested with this input:

0
6
0 10000000 700000 1
700000 1 700000 9000000
700000 9000000 9100000 9000000
9100000 9000000 9100000 0
9100000 0 10000000 10000000
10000000 10000000 0 10000000

Update: I made a test in boost voronoi 1.76 and added this to voronoi_builder.hpp

284    // Find the node in the binary search tree with left arc
285    // lying above the new site point.
286    key_type new_key(*site_event_iterator_);
287    {
            beach_line_iterator i;
            node_comparer_type cmp;
            std::cout << std::endl << "lower_bound:" << std::endl;
            for(i=beach_line_.begin();i!=beach_line_.end();i++){
               std::cout << (cmp(i->first, new_key)?"true":"false") << " " << (cmp(new_key, i->first)?"true":"false") << std::endl;
            }
        }
        beach_line_iterator right_it = beach_line_.lower_bound(new_key);

It shows how each item in the beach-line map (in order) compares to the key and it generates this output:

...
false true
false true
false true

lower_bound:
true false
true false
true false
true false
false true  <----  ???????
true false
true false
false true
false true
false true

lower_bound:
true false
true false
...

I don't understand how C++ map() can find the correct value under such conditions. Doesn't C++ map require Strict weak orderings?

[eadf]

It's impossible to search for the correct beach-line key in a BTree when the keys are corrupted.

So instead I fixed(?) the problem by implementing a Vec based linked-list that emulates a C++ map and it's pointer based iterators. It can only do linear search - but it works! It's also faster than the old (buggy) BTree code.

[eadf]

Turns out the fix is not adequate, i'll need to find a better solution than this