Boost C++ Libraries: Ticket #5482: iterative_size() not the same for interval_maps using std::less and std::greater

Joachim Faulhaber — Sat, 16 Apr 2011 10:02:15 GMT

Hi,

thank you for this interesting bug report. In generic programming we may forget to vary template paramteres in tests, specifically if we have many of them ;) The problem you have found has to do with interval initialization of singleton intervals [x, ++x), because x < ++x is only valid with std::less and not with std::greater.

Replying to boicotinho@…:

The assertion at the bottom fails.

typedef interval_map<int,int,partial_absorber,std::less>	m1_t;
typedef interval_map<int,int,partial_absorber,std::greater> m2_t;
m1_t m1;
m2_t m2;
m1.insert(make_pair(m1_t::interval_type(1), 20));
m1.insert(make_pair(m1_t::interval_type(2), 20));
m1.insert(make_pair(m1_t::interval_type(3), 20));
m2.insert(make_pair(m2_t::interval_type(1), 20));
m2.insert(make_pair(m2_t::interval_type(2), 20));
m2.insert(make_pair(m2_t::interval_type(3), 20));
Assert::IsTrue(m1.iterative_size() == m2.iterative_size());

I will fix that bug for the general case ASAP. For the time being, you could use a work around that seems to work. Construct intervals explicitly with two values:

typedef interval_map<int,int,partial_absorber,std::less>    m1_t;
typedef interval_map<int,int,partial_absorber,std::greater> m2_t;
m1_t m1;
m2_t m2;
m1.insert(make_pair(m1_t::interval_type(1), 20));
m1.insert(make_pair(m1_t::interval_type(2), 20));
m1.insert(make_pair(m1_t::interval_type(3), 20));
m2.insert(make_pair(m2_t::interval_type(3,2), 20)); //Singleton intervals
m2.insert(make_pair(m2_t::interval_type(2,1), 20)); //constructed explicitly
m2.insert(make_pair(m2_t::interval_type(1,0), 20)); //with std::greater ordering
BOOST_CHECK_EQUAL(m1.iterative_size(), m2.iterative_size());

Alas I can't guarantee that there aren't more problems lurking with std::greater, since as you detected, I haven't tested these cases carefully enough yet.

Best regards, Joachim

keywords, status, milestone changed

Joachim Faulhaber — Sat, 16 Apr 2011 10:04:59 GMT

keywords ordering added
status new → assigned
milestone To Be Determined → Boost 1.47.0

anonymous — Sun, 17 Apr 2011 09:53:37 GMT

Replying to jofaber:

Thank you for looking into this - I really like this ICL of yours and use it a lot :)

FYI It seems that your workaround works - but if I insert the intervals in another order for m2, then m2.find() fails while m1.find() still works.

In the meanwhile I am using std::less but representing the data with negative numbers instead.

The reason I wanted to use std::greater is because I would like find() to start from the highest interval given a range.

Joachim Faulhaber — Sun, 17 Apr 2011 16:50:32 GMT

Replying to anonymous:

Replying to jofaber:

Thank you for looking into this - I really like this ICL of yours and use it a lot :)

That's nice to hear. For me it is good to have users who are challenging the library or use it creative ways, so we can detect flaws and improve the code.

FYI It seems that your workaround works - but if I insert the intervals in another order for m2, then m2.find() fails while m1.find() still works.

True, I suspected you'd find some more problems using std::greater. I have found and fixed more inconsistencies between compare-order and incrementation/decrementation that caused these program failures and committed the improved code to the boost/trunk. You might want to get a copy of that code if you like. I am still doing some testing though before closing the ticket.

In the meanwhile I am using std::less but representing the data with negative numbers instead.

The reason I wanted to use std::greater is because I would like find() to start from the highest interval given a range.

To find the last interval that overlaps a given interval I you could use it = m.upper_bound(I), which yields an iterator to the first interval that is greater than I and then decrement the iterator it once.

Cheers, Joachim

status changed; resolution set

Joachim Faulhaber — Mon, 18 Apr 2011 13:42:37 GMT

status assigned → closed
resolution → fixed

denis@… — Tue, 24 May 2011 13:31:10 GMT

related ticket #5559