Re: [boost] [Review] ITL review starts today, February 18th

Subject: Re: [boost] [Review] ITL review starts today, February 18th
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2010-03-05 13:38:19

Hi Barend,

sorry for the delay, I intended to reply on the various comments of
your thorough review earlier, but since I know that you are pretty
busy yourself, a little delay might be ok for you.

2010/2/28 Barend Gehrels <barend_at_[hidden]>:
> 2) DOCUMENTATION
> The documentation is extensive and good. I've some small remarks about the
> introduction.
>
> When I started I was confused by the definitions of interval_set and
> interval_map, and when to use them. It might be explained a little better
> for people not having worked with intervals before, probably with some
> sample code and images. The documentation contains, at the start:
>
> "It means that we can use an interval_set or interval_map like a set or map
> of elements. It exposes the same functions."
>
> and then gives the example " mySet.contains(42)". But contains is NOT an
> method of std::set, but YES from interval_set. This was confusing.

my view on sets here is not governed by std::sets but rather by the
mathematical notion of a set or the itl::Set concept that is part of
my documentation. In this view the "is element of" function is pretty
fundamental and it is available for itl::interval_set and for itl::set
as bool T::contains(const domain_type&);

Let me put it this way:
std::set  : could be model of itl::Set, if operators were implemented
itl::set : is model of itl::Set
itl::interval_set : is model of itl::Set but implemented via intervals
boost::dynamic_bitset : is almost model of itl::Set but implemented
via arrays of machine words.

There is a common semantic core of all of those. For interval_set and
bitset, their implementation is not completely hidden. You can access
some aspects of it because this may be useful.

Which is the common interface, the fundamental aspect, that
constitutes this semantic kernel? Would that signature contain
find(x)? Would it contain contains(x)? Would it provide iterators?

boost::dynamic_bitset does not implement find, it does not implement
iterators. Would we therefore say it is not a set? Its signature does
not provide contains(x) but it contains test(x), which IMO should be
called contains(x).

I think std::set is one implementation of Set but not THE set.

> I then expected a sample for the map below but not there... Furthermore,
> that threelined set-sample means that the *interval* 42-42 is inserted,

since interval_set is basically a set (of elements) it should be irrelevant how
mySet.insert(42);
works internally.

> which was also not clear to me at first sight...

which is intentional, because I did *not* want to emphasize on
implementation but on abstraction here.

> I would change that
> section. I would suggest something like this:
>
> void intro_sets_for_dummies()
> {
>   namespace itl = boost::itl;
>
>   // STANDARD std::set works with values
>   std::set<int> std_set;
>   std_set.insert(3);
>   std_set.insert(7);
>   BOOST_FOREACH(int const& value, std_set)
>   {
>       std::cout << " " << value;
>   }
>   //std::cout << " " << (std_set.contains(3) ? "YES" : "NO"); //not
> implemented in std::set
>   std::cout << std::endl;
>
>   // BOOST.ITL itl::interval_set works with intervals instead of values
>   itl::interval_set<int> itl_set; // Interval's of integer, e.g. seconds or
> years
>   itl_set.insert(itl::interval<int>(3,5));
>   itl_set.insert(itl::interval<int>(4,8)); // Overlap with previous is
> detected automatically
>   itl_set.insert(1); // Interval of (1,1)
>   BOOST_FOREACH(itl::interval<int> const& interval, itl_set)
>   {
>       std::cout << " " << interval.first() << ".." << interval.last();
>   }
>   std::cout << " " << (itl_set.contains(3) ? "YES" : "NO") << std::endl;
>   //  1..1 3..8 YES
> }
>
>
> The same for map. The itl::interval_map is REALLY very useful. My
> suggestion:
> void intro_maps_for_dummies()
> {
>   namespace itl = boost::itl;
>
>   // STANDARD std::map
>   std::map<int, int> std_map;
>   std_map[3] = 4;
>   std_map[7] = 8;
>   for(std::map<int,int>::const_iterator it = std_map.begin(); it !=
> std_map.end(); ++it)
>   {
>       std::cout << " " << it->first << ": " << it->second;
>   }
>   std::cout << std::endl;
>
>   // BOOST.ITL itl::interval_map
>   itl::interval_map<int, int> itl_map;
>   itl_map += std::make_pair(itl::interval<int>(3,5), 4); // add 4 to [3,5]
>   itl_map += std::make_pair(itl::interval<int>(4,8), 8); // add 8 to [4,8]
> -> will generate 3 intervals
>   itl_map -= std::make_pair(itl::interval<int>(5,5), 2); // subtract 2 ->
> will split another interval
>   for(itl::interval_map<int, int>::const_iterator it = itl_map.begin(); it
> != itl_map.end(); ++it)
>   {
>       itl::interval<int> const& interval = it->first;
>       std::cout << " " << interval.first() << ".." << interval.last() << ":
> " << it->second;
>   }
>   std::cout << std::endl;
>   // OUTPUT:  3..3: 4   4..4: 12   5..5: 10   6..8: 8
> }
>
> This would give me a clearer picture how it works.

Thank you again for sharing your experiences with the introduction.
Developers want to *see how it works* :-D Yet I wanted to focus on
concept and abstraction.

> At the same time I now
> realize that during our discussion on +=, -=, |= , I didn't realize enough
> that += really does mathematics behind the screens. So it adds values where
> to the map on the specified interval, it subtracts values from the map on
> the specified interval. This goes beyond "set theoretic operations", "set
> union" and especially "set difference". See below for more on this.
>
> I realize that a similar sample is there in the documentation, and that this
> principle, "aggregate on overlap" is well explained there. However, a sample
> with the numeric values is (for me) somewhat more clear than the given
> sample with names which are added to a set; the sample of interval_map with
> itl::set probably does too much at a time...
>
> But let me repeat that the overall documentation is impressive and complete!

I think I'll change the intro a little according to the suggested. But
to address the issues that you are raising here in a broader way, I
think it'll be better to put that into a tutorial. Anyway your
suggestions will not be forgotten.

So much on this part. More next time.

Cheers,
Joachim