Announce: Interval Template Library (itl): Generic intervalcontainers.

[Joachim Faulhaber]

Hi,

I have developed a library of interval containers called Interval
Template Library (ITL). The library, initially developed in an
software
industrial context, was proposed at the boost developer's list in
May 2008, refined according to boost standards, presented at
boostcon09
and submitted for a formal review in September 2009. Hartmut Kaiser is
now supporting the ITL as review manager.

I have uploaded a new release of the core library of interval
containers
(itl), extensions (itl_xt) and a test tool (validate) for law based
automated testings as itl_plus_3_2_1 at the itl's project site at
sourceforge:
http://sourceforge.net/projects/itl/

Interval_sets and interval_maps of the ITL proved to be very useful in
many fields the most important of which is the date and time problem
domain.

* Interval_sets and interval_maps can be used like the sets or maps
of elements. Yet they are much more space and time efficient when
the elements occur in contiguous chunks.

* Interval containers allow for intersection with interval_sets to
work with segmentation. For instance you might want to intersect
an interval container with a grid of months and then iterate over
those months.

* The ITL comes with a universal mechanism of aggregation, that allows
to combine associated values in meaningful ways when intervals
overlap on insertion. Aggregation results that are difficult to
obtain by handwritten algorithms can be computed in an abstract and
simple way.

* itl::interval_bitset is a self compressing class to represent very
large bitsets. It combines interval and bitset compression.

* You can get an instant impression of the usefulness of interval
containers by looking at the collection of examples:
http://www.herold-faulhaber.de/boos...itl/examples.html#boost_itl.examples.overview

* To get an overview over the itl's api refer to
http://www.herold-faulhaber.de/boos...ml/boost_itl/interface/function_synopsis.html

I hope you will find this useful. In case you do, I'd like to
encourage
you to send in your feed back and suggestions and to participate in
the upcoming review on the boost developer's list.

Best regards
Joachim Faulhaber

---------------------------------------------------------------------
Interval Template Library (ITL) | Boost.IntervalContainers
---------------------------------------------------------------------
Availability:
Project page at sourceforge:
http://sourceforge.net/projects/itl/
Boost Vault:
http://www.boostpro.com/vault/index.php?&direction=0&order=&directory=Containers

Boost Quickbook documentation (core library itl)
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/index.html
Doxygen Documentation (extensions itl_xt, validate)
http://www.herold-faulhaber.de/itl/index.html

The name ITL is provisional and will probably be changed to
Boost.IntervalContainers after the review.

 

[Brian Wood]

Hi,

I have developed a library of interval containers called Interval
Template Library (ITL). The library, initially developed in an
software
industrial context, was proposed at the boost developer's list in
May 2008, refined according to boost standards, presented at
boostcon09
and submitted for a formal review in September 2009. Hartmut Kaiser is
now supporting the ITL as review manager.

I have uploaded a new release of the core library of interval
containers
(itl), extensions (itl_xt) and a test tool (validate) for law based
automated testings as itl_plus_3_2_1 at the itl's project site at
sourceforge:http://sourceforge.net/projects/itl/

Interval_sets and interval_maps of the ITL proved to be very useful in
many fields the most important of which is the date and time problem
domain.

* Interval_sets and interval_maps can be used like the sets or maps
  of elements. Yet they are much more space and time efficient when
  the elements occur in contiguous chunks.

* Interval containers allow for intersection with interval_sets to
  work with segmentation. For instance you might want to intersect
  an interval container with a grid of months and then iterate over
  those months.

* The ITL comes with a universal mechanism of aggregation, that allows
  to combine associated values in meaningful ways when intervals
  overlap on insertion. Aggregation results that are difficult to
  obtain by handwritten algorithms can be computed in an abstract and
  simple way.

* itl::interval_bitset is a self compressing class to represent very
  large bitsets. It combines interval and bitset compression.

* You can get an instant impression of the usefulness of interval
  containers by looking at the collection of examples:
 http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_....

* To get an overview over the itl's api refer to
 http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_....

I hope you will find this useful. In case you do, I'd like to
encourage
you to send in your feed back and suggestions and to participate in
the upcoming review on the boost developer's list.

Best regards
Joachim Faulhaber

---------------------------------------------------------------------
Interval Template Library (ITL) | Boost.IntervalContainers
---------------------------------------------------------------------
Availability:
Project page at sourceforge:http://sourceforge.net/projects/itl/
Boost Vault:http://www.boostpro.com/vault/index.php?&direction=0&order=&directory...

Boost Quickbook documentation (core library itl)http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/index....
Doxygen Documentation (extensions itl_xt, validate)http://www.herold-faulhaber.de/itl/index.html

The name ITL is provisional and will probably be changed to
Boost.IntervalContainers after the review.

I have taken some lines from the party example and will add a few
thoughts.


// Type itl::set<string> collects the names of party guests. Therefore
it needs to
// implement operator += that performs a set union on overlap of
intervals.
typedef boost::itl::set<string> GuestSetT;

I disagree with the Boost approach of reusing names like set.
During the review of the Boost Intrusive containers, I voted
against duplicating the names of the containers in the
standard library, but others voted for it and they "won."

Later I brought the matter up on this newsgroup and someone
else agreed with me saying, "I'm quite sure that if this boost
ilist which they call list is going to be added to the std
library, they would not call it list but something else,
perhaphs even ilist."

My view is that C++ namespaces are often abused and
that an on line dictionary is needed to control the
distribution of names.

In general I think the idea of the library is interesting
and has some utility. G-d willing we'll work on adding
marshalling support for this library to the C++ Middleware
Writer, but I don't have any idea when that might be.

Your documentation is better than mine, but here are a
few comments about that.


"We are introducing interval_maps using an interval map of
sets of strings, because of it's didactic advantages. The
party example is used to give an immediate and depictive
access to the basic ideas of interval maps and aggregate
on overlap. For real world applications, an interval_map
of sets is not necessarily recommended. It has the same
efficiency problems as a std::map of std::sets. There is
a big realm though of using interval_maps with numerical
and other efficient codomain types."

It looks like you have a tendency to make up words. Neither
"depictive" nor "codomain" are in my dictionary. You could
replace "immediate and depictive access to" with "quick and
dirty example of." As you mention it isn't a composition of
types that would normally be used so the dirty part kind of
fits. And if you mean co-domain in the second case, that
still doesn't really do anything for me as far as
understanding what your intention is.


Regards,
Brian Wood
http://webEbenezer.net
(651) 251-9384

 

[Joachim Faulhaber]

Brian,

thank you for looking at my library and for commenting on it.

I have taken some lines from the party example and will add a few
thoughts.

// Type itl::set<string> collects the names of party guests. Therefore
it needs to
// implement operator += that performs a set union on overlap of
intervals.
typedef boost::itl::set<string> GuestSetT;

I disagree with the Boost approach of reusing names like set.
During the review of the Boost Intrusive containers, I voted
against duplicating the names of the containers in the
standard library, but others voted for it and they "won."

Later I brought the matter up on this newsgroup and someone
else agreed with me saying, "I'm quite sure that if this boost
ilist which they call list is going to be added to the std
library, they would not call it list but something else,
perhaphs even ilist."

I can see the point that you are making. The reuse of a class
template name like 'set' within a new namespace will obstruct the
possibility to integrate this class template into a more important
namespace like std where the name already exists.

I don't share this concern very much. Even class names that do
not yet exist in std seem to be included under an additional
namespace like e.g. std::tr1::unordered_set.

My view is that C++ namespaces are often abused and
that an on line dictionary is needed to control the
distribution of names.

In my view those class name overloadings are an intended use rather
than a misuse of namespaces. I think at the heart of naming should
be the intended behavior of a class that can be formalized by it's
concepts. The concept consists of sytactical (interface) and, more
important, semantical properties (laws aka axioms). If a class
fulfills those properies, is a model of the concept, it should be
named according to the concept. Aspects like certain implementation
techniques (intrusiveness) are secondary in this respect. As long
as there are no 'concepts' and no 'aspects' integrated into c++, I
think that namespaces are the best way to separate such
implementation variants. std::set, intrusive::set.

There is an overall trend to support overloading and polymorphism
across programming languages to give library authors and developers
the means to use short non-technical names. And I like that.

In general I think the idea of the library is interesting
and has some utility. G-d willing we'll work on adding
marshalling support for this library to the C++ Middleware
Writer, but I don't have any idea when that might be.

that's good to hear

Your documentation is better than mine,

Boost quickbook contributes a lot to a good and consistent
graphical/typographical style.

but here are a
few comments about that.

"We are introducing interval_maps using an interval map of
sets of strings, because of it's didactic advantages. The
party example is used to give an immediate and depictive
access to the basic ideas of interval maps and aggregate
on overlap. For real world applications, an interval_map
of sets is not necessarily recommended. It has the same
efficiency problems as a std::map of std::sets. There is
a big realm though of using interval_maps with numerical
and other efficient codomain types."

It looks like you have a tendency to make up words.

.... well, yes
I made the observation that, generally, non native speakers
tend to use a foreign language, out of emergency, more
creatively.

Neither
"depictive" nor "codomain" are in my dictionary.

I remember the moment when looking for a translation for the
german word 'anschaulich'. I had problems to find good direct
translation. Maybe a bilingual person can help with that.

You could
replace "immediate and depictive access to" with "quick and
dirty example of." As you mention it isn't a composition of
types that would normally be used so the dirty part kind of
fits. And if you mean co-domain in the second case, that
still doesn't really do anything for me as far as
understanding what your intention is.

Thank you very much for your suggestions. This will
improve my docs.

Cheers
Joachim

 

[Brian]

Brian,

thank you for looking at my library and for commenting on it.

You're welcome.

I can see the point that you are making. The reuse of a class
template name like 'set' within a new namespace will obstruct the
possibility to integrate this class template into a more important
namespace like std where the name already exists.

That's related to it. I'm more concerned with being able
to correctly interpret what I'm reading and not have to
hunt for using directives etc. Clarity it seems to me
is what is lost here. It kind of has to do with key
words also. Should the language allow users to define
their own int and long classes rather than introducing
BigInt or something like that?

I don't share this concern very much. Even class names that do
not yet exist in std seem to be included under an additional
namespace like e.g. std::tr1::unordered_set.


In my view those class name overloadings are an intended use rather
than a misuse of namespaces. I think at the heart of naming should
be the intended behavior of a class that can be formalized by it's
concepts. The concept consists of sytactical (interface) and, more
important, semantical properties (laws aka axioms). If a class
fulfills those properies, is a model of the concept, it should be
named according to the concept.

Calling the Boost Intrusive list ilist or intrusive_list
seems like it is being named according to the concept as
well.

Aspects like certain implementation
techniques (intrusiveness) are secondary in this respect. As long
as there are no 'concepts' and no 'aspects' integrated into c++, I
think that namespaces are the best way to separate such
implementation variants. std::set, intrusive::set.

There is an overall trend to support overloading and polymorphism
across programming languages to give library authors and developers
the means to use short non-technical names. And I like that.



Boost quickbook contributes a lot to a good and consistent
graphical/typographical style.

Thanks, I may check into that.


Regards,
Brian Wood
http://webEbenezer.net
(651) 251-9384