Re: [boost] proposal: interval containers

From: vicente.botet (vicente.botet_at_[hidden])
Date: 2008-05-17 03:06:32

Hello Joachim,

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

> 2008/5/16, vicente.botet <vicente.botet_at_[hidden]>:
>
>> Hello,
>>
>> I'm mainly interested in an implementation of set<T> using 
>> set<interval<T>
>> and on how it comapres to the stl::set in space and time, when the set 
>> are
>> dense or scattered.
>>
>> I have just take a look to the documentation and the implementation, and 
>> I
>> have some questions?
>
> Thank you for looking at my code. I am quite thrilled to get so many
> good responses.

You are welcome and thanks for all your explanations.
I would like to use a set implemented with interval_set. This was on my todo 
list for a locally unique identifier library.

> Let me note, before answering your questions, that I followed the
> boost advice from the web page to post suggestions *before* investing
> work on adjusting or producing library code to conform the boost
> standards and requirements, in order to avoid unnecessary work.

No problem.

> I know the library might not conform some boost requirements yet, but
> I am of course happy to adjust the code and design if there is
> significant interest in my work.
>
> To keep the text simple I will talk mostly of sets and interval_sets,
> when I want to say things about sets/maps and
> interval_sets/interval_maps because most statements apply to both.
>
>> * 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.

> (1) One very interesting point is that interval_sets in the design 
> presented
> do have a twofold character. An interval_set is intended to implement
> set. Yet at the same time it is a set of intervals. So the question
> how a function like e.g.
> find should be implemented has no obvious answer.

As the base classes are not public you have the choice between not 
implementing them, use policies, or even better use mixins, which will give 
you the impresion of virtual functions.

> (2) In my design I am exploiting concepts (Inplace)Addable and
> (Inplace)Subtractable in many ways. That is I do rely on the existence
> of a += operator for almost all and -= for many datatypes in my
> library. So I have added +=, -= and also *= (intersection) to
> interval_set/map. A propagation of += and -= through container
> operations is a core element of my design and a base of the useful
> 'aggregate on overlap' (aggrovering;) mechanics of interval_maps.
> (see examples party and history from http://sourceforge.net/projects/itl.)

OK, I understand.

> I have defined o= operators as memberfunctions because this seemed
> natural to me. But I think the whole library can be easily refactored,
> making them global function templates.

Yes, this should be possible.

>> * Why do you use virtual functions? Are the classes sets, and
>> interval_base_set public?  I think this can and should be avoided.
>
> The original design was classical OO-design, defining an interface
> class that allows different implementations being used uniformly by a
> weak polymophic interfacepointer.

Do you need this polymorphism now?

> Furthermore there is a body of
> baseclass functions that are common to interval_set and
> split_interval_set. They only vary in the handling of interval
> borders. This has been expressed by basecalss interval_base_set,
> interitence and a virtual function 'handle_neighbours'.
>
> All those virtual functions can be devirtualized without problems. The
> interface class templates can be omitted and handle_neighbours might
> be expressed via a policy template parameter.

Please consider the possibility to use mixins.

>> * Does it works with boost::interval?
>>
> Unfortunately not. Interval containers rely on the notion of open
> interval bounds. This was necessary to express operations for
> flotingpoint numbers:
> interval_set<double> is;
> is.insert([1,pi)); is.insert([pi,4]); // is=={[1,4]} merging INTENDED
> is.insert([1,pi)); is.insert((pi,4]); // is=={[1,pi), (pi,4]} must not 
> merge

This is not a reason your library should not work for boost::intervals. If 
interval_set works for any kind of intervals, why should not work for closed 
intervals?

> As I've read in the archives an extension for open interval bounds
> have been suggested for boost::interval in the past.

It will be a good thing to see how to extend the interval library to manage 
with open boundaries and continuous semanstics. Why not make a separated 
proposal for intervals?

>> > The benefits of interval sets and maps are
>> > 1. The implementation of sets/maps via interval_set/map is very
>> > space and also time efficient.
>>
>> Have you done some messures, in space and time? In the worst case {1, 11,
>> 21...}?
>>
> Not yet. Space can be reckoned easily. Wost case is that every
> interval inserted has exactly one value element x per interval [x,x].
> In this case you have double data content and one byte extra for
> borderinformation so roughly 2 times the space of stl::set.
> The 'nice' case is that you can represent a set of uncountable values like
> {[0.0, pi)} quite compact ;)

You are right. This is the nice feature.

>> Do you plan to boostify your code?
>>
> I would very much like to boostify the code. I admit thou that I am
> not yet familiar with all of the boostification ;) I hope guidance
> will be provided.

If I can give you a first guide, follow the directory structure
    boost/itl for the public files
    boost/itl/detail for non public files
    libs/itl/src for the implementation
    libs/itl/example
    libs/itl/test

This will help a lot on how to read your code.

>> I'm no sure interval_set is a model of  Unique Associative Container.
>>
>> Given the following :
>>    interval_set<int> is;  //not quite: interval_set<interval<int>> is;
>>    is.insert([1,3));
>>    is.insert([3,5));
>>
>> What is the result of
>>    assert(find([1,3))!= end);
>> And of
>>    assert(find([1,5))== end);
>>
> I thought about find more than twice and decided not to provide it.
> You can say
> interval_set<int> found;
> is.intersect(found, rightopen_interval([1,5]); // Intersect to find 
> contents

This was a sage decision. I'm not sure which could be consequences to give 
to the find function a intersection semantic. I need to think more on that.

> As interval_set<T> implements set<T> if find is implemented it should
> deliver an iterator pointing to a value, but such iterators are not
> available.

First of all I think that interval_set<interval<T>> must not provide the 
interface of set<T>. I can be used to implement the interface of set<T>.

> The closest one can provide is an iterator that points to
> the interval containing the value or end(), if such interval does not
> exist.

You can use a use the same technique used by bitset. The iterator is a proxy 
that contains the iterator to the interval and the current value. Evidently 
this not work for continuous types.

>> I'm no sure interval_set is a model of  Unique Associative Container.
> No, I'm afraid it is not.
>
>
>> Which operator would you use for set_symmetric_difference? This is a 
>> detail
>> but it will be better to provided the function version of this operators 
>> as
>> well.
> don't know, probably function name. Are there boost suggestions for that?

Maybe ^= could b an option. As is the case for stl::bitset and 
boost::dynamic_bitset

a|b union
a&b intersection
a^b difference
a^b symetric difference
~a not

a|=b inplace union
a&=b inplace intersection
a-=b inplace difference
a^=b inplace symetric difference

Otherwise you can use /,and /= for symetric difference

>>> split_interval_set:
>>> split_interval_set works like interval_set but borders of the
>>> inserted intervals are preserved, so it can be used as time grid.
>>> Using itl::split_interval_set you can partition other interval
>>> containers using the *= operator to perform intersections.

Please could you clarify me. Which are the difference between 
split_interval_set <interval<T> > and
set<interval<T> >?

Best regards
Vicente Botet