Subject: Re: [Boost-bugs] [Boost C++ Libraries] #5561: error on calculating interval_map intersection
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2011-06-06 12:29:33
#5561: error on calculating interval_map intersection
------------------------------+---------------------------------------------
Reporter: denis@… | Owner: jofaber
Type: Bugs | Status: closed
Milestone: Boost 1.47.0 | Component: ICL
Version: Boost 1.46.1 | Severity: Problem
Resolution: invalid | Keywords:
------------------------------+---------------------------------------------
Comment (by jofaber):
Hi Denis,
this is advanced usage of the ICL and as stated before, it is interesting
for me **and others** to see how my library can be used in creative ways.
So **please** lead this kind of communication on the boost developers list
from the beginning. Sometimes we are entering use cases here, that are a
kind of complex and we are running the risk of making errors.
Replying to [comment:3 denis@…]:
> You solution is nice, but it not only enables set semantic but allows
Icl to assume that codomain is an iterable container. And Icl uses
iteration to perform some operations (for example {{{ operator^() }}} ).
> What I want is to have a codomain with set semantic without exposing its
internals. It might have a container inside but also might not have. One
example of such codomain is bool (or fixed-length array of bool). Another
is AST tree.
I think my solution works and you were running into some problems by doing
something wrong. One of those errors is to use a codomain type that leaves
its value undefined on default construction. (See below). Another problem
is that you did not instantiate template `icl::is_set` for the custom
codomain type `MySettic`, as suggested.
> Below is code of exampled MySettic which exposes its
intersection/union/difference interface but not the iteration interface.
What is the recommended way to use it as a interval_map's codomain?
>
> {{{
> class MySettic {
> uint32_t set_;
> friend std::ostream& operator <<(std::ostream&, const MySettic&);
> public:
> }}}
//Problem: Undefined default-ctor
> {{{
> MySettic() {}
>
> MySettic(int a, int b) {
> set_ = (1<<a) | (1<<b);
> }
>
> bool operator == (const MySettic& rhs) const { return set_ ==
rhs.set_; }
>
> MySettic& operator &= (const MySettic& rhs){
> set_ &= rhs.set_;
> return *this ;
> };
> MySettic& operator -= (const MySettic& rhs){
> set_ &= ~rhs.set_;
> return *this ;
> };
> MySettic& operator ^= (const MySettic& rhs){
> set_ ^= rhs.set_;
> return *this ;
> };
> MySettic& operator += (const MySettic& rhs){
> set_ |= rhs.set_;
> return *this ;
> };
> };
> std::ostream& operator <<(std::ostream& o, const MySettic& ms) {
> bool needspace=false;
> for(int i=0; i<32; i++)
> if(ms.set_ & (1<<i)) {
> if(needspace++) o << " ";
> o << i;
> }
> return o;
> }
>
> class fmt {
> std::ostringstream ss;
> public:
> operator std::ostringstream&() {return ss;}
> operator std::string() const {return ss.str();}
> template<typename T> fmt& operator<<(T const& v) {ss<<v; return
*this;}
> };
>
> TEST(IntervalMap, MyCodomainSetSemantic) {
> MySettic s1(1,6), s2(1,12), s3;
>
> #ifdef TMP_FIX // it solves the issue partially, '|' '&' '-' work, but
'^' fails
> icl::interval_map<int, MySettic,
> icl::partial_absorber, // default
> ICL_COMPARE_INSTANCE(std::less, DomainT), // default
> ICL_COMBINE_INSTANCE(icl::inplace_plus, MySettic), // default
> ICL_SECTION_INSTANCE(icl::inplace_et, MySettic)
> > m1, m2;
> #else
> icl::interval_map<int, MySettic> m1, m2;
> #endif
> m1.add(make_pair(icl::interval<int>::closed(1,10), s1));
> m2.add(make_pair(icl::interval<int>::closed(5,15), s2));
>
> EXPECT_EQ("1 6 12", std::string(fmt() << ((s3=s1)+=s2)));
> EXPECT_EQ("1", std::string(fmt() << ((s3=s1)&=s2)));
> EXPECT_EQ("6", std::string(fmt() << ((s3=s1)-=s2)));
> EXPECT_EQ("6 12", std::string(fmt() << ((s3=s1)^=s2)));
>
> EXPECT_EQ("{([1,5)->1 6)([5,10]->1 6 12)((10,15]->1 12)}",
std::string(fmt() << (m1|m2)));
> EXPECT_EQ("{([5,10]->1)}",
std::string(fmt() << (m1&m2)));
> EXPECT_EQ("{([1,5)->1 6)([5,10]->6)}",
std::string(fmt() << (m1-m2)));
> EXPECT_EQ("{([1,5)->1 6)([5,10]->6 12)((10,15]->1 12)}",
std::string(fmt() << (m1^m2))); // wrong with TMP_FIX
> }
>
> }}}
I am giving the modified source code for `MySettic` in which all
operations work as expected:
{{{
//==============================================================================
class MySettic {
uint32_t set_;
friend std::ostream& operator <<(std::ostream&, const MySettic&);
public:
// ADDED
// When working with ICL the default ctor *must not* be undefined.
// Always implememetn it so it represents the identity element w.r.t.
// your major combining operation (which is += or |= implementing
// set union in this case.
MySettic(): set_(0u){}
// ADDED
MySettic(uint32_t bits): set_(bits){}
MySettic(int a, int b) {
set_ = (1<<a) | (1<<b);
}
bool operator == (const MySettic& rhs) const { return set_ == rhs.set_;
}
MySettic& operator &= (const MySettic& rhs){
set_ &= rhs.set_;
return *this ;
};
MySettic& operator -= (const MySettic& rhs){
set_ &= ~rhs.set_;
return *this ;
};
MySettic& operator ^= (const MySettic& rhs){
set_ ^= rhs.set_;
return *this ;
};
MySettic& operator += (const MySettic& rhs){
set_ |= rhs.set_;
return *this ;
};
//ADDED
MySettic& operator |= (const MySettic& rhs){
set_ |= rhs.set_;
return *this ;
};
//ADDED
MySettic operator ~ ()const {
return MySettic(~set_);
}
};
std::ostream& operator <<(std::ostream& o, const MySettic& ms) {
bool needspace=false;
for(int i=0; i<32; i++)
if(ms.set_ & (1<<i)) {
if(needspace++) o << " ";
o << i;
}
return o;
}
class fmt {
std::ostringstream ss;
public:
operator std::ostringstream&() {return ss;}
operator std::string() const {return ss.str();}
template<typename T> fmt& operator<<(T const& v) {ss<<v; return *this;}
};
// ADDED
// You *have to* instantiate template icl::is_set for you custom type,
// to achive set semantic behavior of interval_maps.
template<>
struct is_set<MySettic>
{
typedef is_set<MySettic> type;
BOOST_STATIC_CONSTANT(bool, value = true);
};
BOOST_AUTO_TEST_CASE(settic_codomain_4_denis)
{
MySettic s1(1,6), s2(1,12);
cout << "symptomic_difference ---------" << endl;
cout << "s1=" << s1 << endl;
cout << "s2=" << s2 << endl;
cout << "s1^s2=" << (s1^s2) << endl;
// Working with a type like this is not a FIX as your posting impies
// but proper advanced usage of interval containers.
typedef interval_map<int, MySettic, partial_absorber, std::less,
inplace_bit_add, inplace_bit_and> BitCollectorT;
// This type works properly as well but you have to implement += via
|=
// which is done for MySettic.
typedef interval_map<int, MySettic, partial_absorber, std::less,
inplace_plus, inplace_et> BitCollector2T;
BitCollectorT m1, m2;
m1.add(make_pair(icl::interval<int>::closed(1,10), s1));
m2.add(make_pair(icl::interval<int>::closed(5,15), s2));
cout << "m1:" << m1 << endl;
cout << "m2:" << m2 << endl;
cout << "m1^m2:" << (m1^m2) << endl;
}
//==============================================================================
}}}
As you can see, there is still no bug on the library's side, so the ticket
stays closed.
Thank you again for you valuable use cases and comments.
Joachim
-- Ticket URL: <https://svn.boost.org/trac/boost/ticket/5561#comment:4> Boost C++ Libraries <http://www.boost.org/> Boost provides free peer-reviewed portable C++ source libraries.
This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:06 UTC