Re: [boost] proposal: interval containers

From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2008-05-17 06:08:28

2008/5/17, vicente.botet <vicente.botet_at_[hidden]>:

Hi Vicente,

thank you again for your vivid interest in my stuff. Your questions
are great, yet there are a lot explanations to give. I am going to
answer only one/few question at a time so the postings won't get
indigestibly fat.
>
> >> * Why not follow the STL set and map interfaces as far as possible?
> >
> > I intended to follow the STL and there is a large set of functions and
> > operators common to std::set/map and itl::interval_sets/maps. But
> > there are differences
> > also.
>
> Could you be exhaustive with the functions not implemented?
> In addition there are the template parameters for comparator and allocator
> that don't mach.
>
I resorted to template template parameters for comparator and
allocator when performed code validation with the law based test
automaton LaBatea (which might be worth an extra look ;-)

One law that I wanted to validate was this:
itl::interval_set<T> is homomorphic to itl::set<T>, which is to say
both implementations show identical behavior. I implemented such
homomorphism laws via a law 'BinaryPushout' see
itl\src\validate\laws\pushouts.h in my source code that implements a
commuting diagram:

(a,b) ---o---> c
   |               |
   |f              |f
  V              V
(a',b')---o---> c'

One instance of this BinaryPushout is
a, b, c:   objects of type itl::interval_set<T>
a', b', c': objects of type itl::set<T>
f: a functor Atomize:   itl::interval_set<T> -> itl::set<T>
that transforms an interval_set into a set.
o: A binary operation (in it's inplace incarnation +=, -=, *=).

What all the fuzz is about is simply to say that performing first an
operaton += on interval sets and then atomize the result to set,
yields the same results as atomizing the the arguments first and then
performing += on the atomized sets:

Atomize(a o b) == Atomize(a) o Atomize(b)

The instance of that BinaryPushout Law looks like that:

BinaryPushout
<
    Type,
    typename Type::atomized_type,
    Interval::Atomize,
    inplace_plus
>
see \itl\src\validate\typevalidater.h line 505

Now, for the instance type Type, which requires to be an
interval_container (or at least something that is Atomizable), we do
need a derived or associated type
typename Type::atomized_type !!

interval_set provides that derived type:
typedef typename itl::set<DomainT,Compare,Alloc> atomized_type;

It passes the Compare and Alloc template tempate right thru to the
itl::set and finally to the implementing std::set where it is finally
instantiated.

I at least had severe difficulties to manage those derived types as
long as I worked with instantiated Compare<T> and Alloc<T>. Sorry I
can't remember the details. But from the moment I consequently used
template template parameters the problems ceased. IMO this is also
much more elegant and appropriate. I suspect template template
parameters were not available at the time of STL's original design,
otherwise they would have been used then ;-)

cheers
Joachim