Re: [boost] proposal: interval containers

From: Vicente Botet (vicente.botet_at_[hidden])
Date: 2008-05-17 08:40:04

----- Original Message ----- 
From: "Joachim Faulhaber" <afojgo_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Saturday, May 17, 2008 12:08 PM
Subject: Re: [boost] proposal: interval containers

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

I will do

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

This is a good thing. Given an interval set we have an associaated set<T> 
via its atomized_type.
Is the atomized_type a model of UniqueAssociativeContainer?

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

Maybe you are right and it should be like that. In addition I'm not sure 
allocator are part of the Container concept. Can some one help on this? 
Which are the allocator related constraints for the Container concept?

I suspect that I will need to revise my Locally Unique Identifiers library 
which has a parameter UniqueAssociativeContainer and use the allocator 
constructor.

Cheers
Vicente