//
// Boost.Geometry rtree failure?
//
// Scenario: 
// * Add some values to a rtree
// * Remove (some or all of) them in different order
// * Add another element -> BOOM 
//
// Compile:
// clang++ rtree-crash.cpp -std=c++11 -Wall -I /opt/local/include/ -o rtree-crash
//
// FAILS:
// rtree-crash 14 5
// rtree-crash 30 15
//
// PASS:
// rtree-crash <n> 1
//
// SEGFAULT:
// rtree-crash 1000 123 (with -DNDEBUG)
//
// * Also fails in two dimensions e.g. with value_type{i, i + 1}
// 

#include <boost/geometry.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <boost/lexical_cast.hpp>

#include <iostream>

#include <cassert>

typedef boost::geometry::model::point<
      int, 1, boost::geometry::cs::cartesian> value_type;
typedef boost::geometry::index::quadratic<4> strategy;
typedef boost::geometry::index::rtree<value_type, strategy> tree;

// Add n values
void add_values(tree& tr, const long n) {
  for (long i = 0; i < n; ++i) {
    std::cout << "insert " << i << std::endl;
    tr.insert(value_type{i});
  }
}

// Remove n values, order determined by m.
// If gcd(m, n) == 1, all elements are removed.
void remove_values(tree& tr, const long n, const long m) {
  for (long j = 0; j < n; ++j) {
    long const i = (j * m) % n;
    std::cout << "remove " << i << std::endl;
    tr.remove(value_type{i});
  }
}

int main(int const argc, char const** const argv) { 
  assert(3 == argc);

  long const n = boost::lexical_cast<long>(argv[1]);
  long const m = boost::lexical_cast<long>(argv[2]);

  tree tr;
     add_values(tr, n   );
  remove_values(tr, n, m);
     add_values(tr, 1   );
}