Boost C++ Libraries: Ticket #5561: error on calculating interval_map intersection

Joachim Faulhaber — Wed, 25 May 2011 12:56:27 GMT

Hi Denis,

as already mentioned in private mail, the behavior that you consider erroneous is correct and follows the specification (see docs). Since interval_maps perform aggregation on overlap, they pass a type's combine-operation to combine associated values for + and they pass a type's intersecting operation to intersect associated values on overlap, if an intersection is called on the interval_map.

This is only possible if the type of the associated values (codomain_type) implements an intersection operation for operator &.

`Q = interval_map<T, Numeric>`	is a Quantifier not having set semantics
`interval_map<T, Q>`	is a Quantifier not having set semantics
`C = interval_map<T, Set>`	is a Collector that has set semantics
`interval_map<T, C>`	is a Collector that has set semantics

For Quantifiers, the intersection operations & degenerates to +.

http://www.joachim-faulhaber.de/boost_icl/doc/libs/icl/doc/html/boost_icl/semantics/quantifiers__maps_of_numbers.html

What you always can do is this

//Define a user defined type ...
class MySettic
{
    // Has some kind of intersection
    MySettic& operator &= (const MySettic& rhs){...};
    . . .
};
//... make it have set semantics by partial specialization 
//of template icl::is_set
namespace boost{ namespace icl
{
    struct is_set<MySettic>
    {
        typedef is_set<bits<NaturalT> > type;
        BOOST_STATIC_CONSTANT(bool, value = true);
    };
} }
//... and then use it in your interval maps.
interval_map<int, MySettic> myIMap;

HTH, Best regards,

Joachim

status changed; resolution set

Joachim Faulhaber — Wed, 25 May 2011 12:57:10 GMT

status new → closed
resolution → invalid

denis@… — Tue, 31 May 2011 13:19:23 GMT

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. 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:
  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
}

Joachim Faulhaber — Mon, 06 Jun 2011 12:29:33 GMT

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 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