interval_set works not correct with custom compare function

[denis@…]

Just catch a bug: interval_set works not correct with custom compare function. Here is the test case, it fails with boost 1.46.1 and truck version (23 May 2011, svn revision 72124). It works ok with default std::less comparator.

Of course, it is weird to use std::greater with int as it is in this listing. Here is a simplified test case, I got the bug using a custom datatype (int64_t inside) with a custom comparator. I did not investigated it yet. It looks like icl::succ and icl::pred should be customized together with comparator.

#include <iostream>
#include <assert.h>
#include <boost/cstdint.hpp>
#include <boost/icl/interval_set.hpp>


int main() {
  typedef boost::icl::interval_set<boost::uint32_t, ICL_COMPARE_INSTANCE(std::greater, boost::uint32_t)> Set;

  Set q1( Set::interval_type::closed(UINT32_MAX, 0) );
  Set q2( Set::interval_type::closed(1000, 100) );
  Set q3( Set::interval_type::closed(1, 1) );
  Set q4( Set::interval_type::closed(1, 0) );
  Set q5( Set::interval_type::closed(0, 0) );

  std::cout << q1 << " + " << q2 << " = " << (q1+q2) << std::endl; // ok
  std::cout << q1 << " + " << q3 << " = " << (q1+q3) << std::endl; // incorrect result
  std::cout << q1 << " + " << q4 << " = " << (q1+q4) << std::endl; // incorrect result
  std::cout << q1 << " + " << q5 << " = " << (q1+q5) << std::endl; // assertion inside icl

  assert(q1 == q1+q2);
  assert(q1 == q1+q3);
  assert(q1 == q1+q4);
  assert(q1 == q1+q5);
}

[denis@…]

This can be worked around this way

#include <iostream>
#include <assert.h>
#include <boost/cstdint.hpp>
#include <boost/icl/interval_set.hpp>

class rint {
  boost::uint32_t i_;
public:
  rint(int i=0) : i_(i) {}
  operator boost::uint32_t() const { return i_; }
  const rint& operator++() { ++i_; return *this; }
  const rint& operator--() { --i_; return *this; }
  bool operator <(rint r) const { return i_ < r.i_; }
  bool operator >(rint r) const { return i_ > r.i_; }
};
namespace boost{ namespace icl {
  template <> inline rint succ(rint x) { return --x; }
  template <> inline rint pred(rint x) { return ++x; }
}}


int main() {
  typedef boost::icl::interval_set<rint, ICL_COMPARE_INSTANCE(std::greater, rint)> Set;

  Set q1( Set::interval_type::closed(UINT32_MAX, 0) );
  Set q2( Set::interval_type::closed(1000, 100) );
  Set q3( Set::interval_type::closed(1, 1) );
  Set q4( Set::interval_type::closed(1, 0) );
  Set q5( Set::interval_type::closed(0, 0) );

  std::cout << q1 << " + " << q2 << " = " << (q1+q2) << std::endl; // ok
  std::cout << q1 << " + " << q3 << " = " << (q1+q3) << std::endl; // ok
  std::cout << q1 << " + " << q4 << " = " << (q1+q4) << std::endl; // ok
  std::cout << q1 << " + " << q5 << " = " << (q1+q5) << std::endl; // ok

  assert(q1 == q1+q2);
  assert(q1 == q1+q3);
  assert(q1 == q1+q4);
  assert(q1 == q1+q5);
}

It is a bit strange, that Compare is settable per-container while succ() and pred() is settable per-type. discrete_interval needs all 3 function be performable on its domain and all of them to be consistent. Thus, per-type defined succ() and pred() give no chance for Compare to be chosen freely per-container. If succ() does increment then Compare has to be std::less, if succ() does decrement then Compare has to be std::greater, etc

[Joachim Faulhaber]

Hi Denis,

thank you for your input. Your code example does not compile with the include-files given. UINT32_MAX is not defined. When using (std::numeric_limits<uint32_t>::max)() instead, I found that the claimed bugs for q3 and q4 do not occur.

Which leaves us with the assertion violation from case q5. I have fixed the code for that and created a test.

BOOST_AUTO_TEST_CASE(ticket_5559_Denis)
{
    //Submitted by Denis
    typedef boost::icl::interval_set<boost::uint32_t, std::greater> Set;
    const uint32_t ui32_max = (std::numeric_limits<uint32_t>::max)();

    Set q1( Set::interval_type::closed(ui32_max, 0) );
    Set q5( Set::interval_type::closed(0, 0) );

    BOOST_CHECK_EQUAL(q1, q1+q5);
}

Cheers, Joachim

[denis@…]

q3 and q4 bugs seem to #5482

[denis@…]

q3 and q4 bugs seem to be #5482