error on calculating interval_map intersection

[denis@…]

here is the test case, reproducible with boost 1.46.1 and the today trunk.

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


int main() {
  typedef boost::icl::interval_map<int, boost::icl::interval_set<int>> I1;
  I1 i(std::make_pair(0, 100)),
     j(std::make_pair(0, 200));
  std::cout << i     << std::endl; //  {([0,0]->{[100,100]})}
  std::cout << j     << std::endl; //  {([0,0]->{[200,200]})}
  std::cout << (i+j) << std::endl; //  {([0,0]->{[100,100][200,200]})}
  std::cout << (i-j) << std::endl; //  {([0,0]->{[100,100]})}
  std::cout << (i&j) << std::endl; //  {}
  assert((i&j).empty());

  // suppose to work same way as the test above
  typedef boost::icl::interval_map<int, boost::icl::interval_map<int, int>> I2;
  I2 k(std::make_pair(0, std::make_pair(100, 1))),
     l(std::make_pair(0, std::make_pair(200, 1)));
  std::cout << k     << std::endl; //  {([0,0]->{([100,100]->1)})}
  std::cout << l     << std::endl; //  {([0,0]->{([200,200]->1)})}
  std::cout << (k+l) << std::endl; //  {([0,0]->{([100,100]->1)([200,200]->1)})}
  std::cout << (k-l) << std::endl; //  {([0,0]->{([100,100]->1)})}
  std::cout << (k&l) << std::endl; //  {([0,0]->{([100,100]->1)([200,200]->1)})} while expecting {}
  assert((k&l).empty());
}

[Joachim Faulhaber]

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

so

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

See also ​http://www.joachim-faulhaber.de/boost_icl/doc/libs/icl/doc/html/boost_icl/semantics/collectors__maps_of_sets.html

​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

[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. 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]

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