Re: [boost] Review Request: Boost.Itl; The Interval Template Library

Subject: Re: [boost] Review Request: Boost.Itl; The Interval Template Library
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2009-09-24 08:31:22

2009/9/24 Gottlob Frege <gottlobfrege_at_[hidden]>:
> On Wed, Sep 23, 2009 at 8:42 AM, Stewart, Robert <Robert.Stewart_at_[hidden]> wrote:
>> Joachim Faulhaber wrote:
>>> 2009/9/21 Simonson, Lucanus J <lucanus.j.simonson_at_[hidden]>:
>>> > Joachim Faulhaber wrote:
>>> >>>> the Interval Template Library is now in a state
>>> >>>> where I think it does conform the requirements
>>> >>>> and guidelines for boost libraries fairly well.
>>> >>>
>>> >>>(Markus Werle)
>>> >>> Actually I am very unlucky with the name "itl".
>>> >
>>> > I'd suggest naming it either Interval
>>> > Set--boost::interval_set or Interval Set Library--boost::isl.
>>>
>>> after pondering for a while I tend to prefer this name
>>>
>>> Compact Associative Containers
>>> boost::compass
>>
>> That's a highly creative name which I don't foresee its conflicting with other libraries.
>
> Except a compass library for handling built in compasses of various
> smart phones. :-)
>
>>
>> How about Minimal (or Minimized) Associative Containers (MAC)?  Packed Associative Containers (PAC)?
>>
>> None of those names, however, reveals the interval behaviors of your containers which are their raison d'être.
>>
>> Interval-Based Associative Containers (IBAC)?  Is "associative" necessary in the name: Interval-Based Containers (IBC)?  Compact Interval-based Associative Containers (CIAC or CIBAC)?  (Associative) Containers of Intervals ((A)CI or (A)COI)?  Compact Associative Containers of/for Intervals (CACI)?  Packed Associative Interval Containers (PAIC)?
>>
>> Of all these ideas, I rather like CACI.  The acronym is pronounceable (like khaki), and the full name is highly descriptive.
>>
These are highly creative acronyms too ;-) Obviously, like Luke above and
Tony below, you would vote to preserve 'Interval' as a part of the libs name.
I like the pronounceable CACI but also the more simple COI for it's
reminiscence to the ornamental fish 'Koi'.

>
> I would leave 'compact' out of it, and 'interval' in.  I'm sure there
> are other ways to compact a container; this library chose intervals.
> And NOT just as an implementation detail.  Intervals are very much
> forefront in the design and API.

Most people that looked at my lib seem to share this view. Yet my
efforts were very much directed towards a design that makes the
core API independent from Intervals
(http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/concepts/sets_and_maps.html)
I have called those core parts the *abstract aspect*
(http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/concepts/aspects.html)
The library implements the abstract aspect for
interval containers *and* containers of elements.
I define all formal laws that forms the major
semantics of the library on that core signatures
for both interval and element containers.
(http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/semantics.html)
And all of the automated law validation is done
for interval containers *and* containers of elements
for identical laws that all abstract from intervals.

But yes, on the other hand there is the more implementation
oriented part called *iterative aspect* on interval containers,
one could also say *sequence of intervals revealing* part,
that is accessible through the API. I did this, because of
the usefulness of those functions. The iterative aspect
could be removed (used only privately) without damaging
the core functions of the *abstract aspect*.

> Furthermore, there may be other ways
> to compact interval sets even more. (ie with generating functions - ie
> how would this interval library handle the Cantor Set!?).

Good point.

>
> The word 'interval' may conflict with other uses of the word, but they
> both derive from the same mathematical concept - a range of numbers.

in the itl a range of StrictWeakComparable objects, which may be
not in line with the mathematical notion of an interval but makes
the library's scope more general.

> Hey, we could use the word 'range'.  Oh wait, also already taken.  (Or
> are these concepts actually the same and using boost::range as an
> interval makes sense at times.  I think so...).

Interesting point.

>
> Could the library be expanded to 2D or more? If so, then 'region'
> might be a more applicable word.

In the extended part of my lib currently called itl_xt, I have
pursued ideas similar to those from interval_maps, for tuple maps,
in order to model generalized crosstables or cubes. I used
the same philosophy: Defining a generalized addition
operation and using that for computing aggregates.
In this part of my lib there are no intervals at all but the
same strategy of generalizing addition on maps.

Because this is may be more fundamental to the design
of my generic stuff than other aspects, I tried to find a name
for that, but so far nothing really convincing came to my mind.

> Might the library be expanded to other containers (ie besides
> associative ones)?  interval_vector?  Or is that less interesting?

You already are able to use an
interval_map<unsigned int, double, total_absorber> infi_vec;
as an infinite or at least very large vector, which is
defined for the complete range of unsigned ints.

> should
> 'associative' be part of the name?
>
might be an obstacle for future extensions,
but I have no plans or ideas to go beyond that scope now.
>
> So, to me, that leaves 'interval' and 'container'.  icl.  Although I
> like the sound of 'isl' (Set) better.
>
> But really, we should avoid TLAs.
>
> Did that help?  Probably not.
>
Yes it did :)
You discussed a lot of interesting and important aspects.
Considering all that I agree that ICL is a good and kind of
an essential acronym.

> ------
> So anyhow, I should also say that after years of working on video
> editing applications (ie Adobe Premiere Pro), I was considering
> writing a similar library.  (To handle the range of time for each
> video clip on a timeline, etc).  Thanks for beating me to it!
>
sorry, I had all the fun ;-)

> As an example usage, with your library, how would you write a 'for a
> given interval_set, is this time-range [a, b) empty' function?
>
I am not sure if I understand exactly what you mean here ... but

// This code checks if an interval_set is empty within a range.
interval_set<time> some_times;
some_times += ...; time a = ..., b = ...;
if(intersects(some_times, interval<int>::rightopen(a,b)))
    ; // Within the range [a,b) some_times is not empty

Cheers
Joachim