Boost C++ Libraries: Ticket #5559: interval_set works not correct with custom compare function

denis@… — Tue, 24 May 2011 13:27:58 GMT

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 — Wed, 25 May 2011 10:59:47 GMT

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@… — Wed, 25 May 2011 11:40:12 GMT

q3 and q4 bugs seem to #5482

denis@… — Wed, 25 May 2011 11:40:58 GMT

q3 and q4 bugs seem to be #5482

status changed

Joachim Faulhaber — Wed, 25 May 2011 11:46:44 GMT

status new → assigned

status changed; resolution set

Joachim Faulhaber — Sun, 05 Jun 2011 13:45:13 GMT

status assigned → closed
resolution → fixed