Re: [Boost-users] [Review] ITL review starts today, February 18th

Subject: Re: [Boost-users] [Review] ITL review starts today, February 18th
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2010-02-23 16:13:34

2010/2/23 Mathias Gaunard <mathias.gaunard_at_[hidden]>:
> Hartmut Kaiser wrote:
>
>> Interval containers allow to access and manipulate collections of
>> intervals
>> on an abstract level as sets and maps (of elements), but also to exploit
>> segmental information that is given by the interval borders. Interval
>> containers are fairly generic. They can be instantiated with discrete
>> domain
>> (or key) types like integral numeric types or boost::date or time types.
>> But
>> they also work with continuous domain types like double, rational or
>> string.
>> Using the latter allows to represent infinite sets and maps.
>>
>> The interface of the interval containers strives to be very intuitive and
>> in
>> line with the stl and other boost libraries.
>>
>> * The set theoretic operations union, difference, intersection
>>  and symmetric difference are available as operators for all
>>  interval containers and for many useful overloads between them.
>
> I have no knowledge of the problem domain (nor did I actually look at the
> library yet, sorry about that), but I simply have a question: how does this
> compare to geometry libraries or spatial indexes that provide that kind of
> facilities for arbitrary dimensions?
>
> I certainly wouldn't want to force over-generalization to the authors, but I
> am wondering how much is gained by limiting things to one dimension.

So can this library survive in a field of power called boost of an ever
abstracting ever generalizing and ever optimizing bunch of thinkers?

A few points:

* Geometry usually is based on a numeric coordinate type
  that comes with a distance measure. Many algorithms in
  geometry libraries rely on that. Intervals and interval containers
  of the ITL, similar to SortedAssociativeContainers, only require a
  strict weak ordering on their key type. So interval containers
  are less restricted and allow for a larger class of instantiations.
  You may for example want to work with interval sets of strings.

* Interval containers implement interval combining styles that
  can be useful in providing and manipulating certain time grids. E.g.
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/examples/time_grids_for_months_and_weeks.html
  I'm not aware of something like that in geometry.

* There are not only interval sets but also interval maps.
  itl::interval_map is the real workhorse in those real world
  applications that already exist. interval_maps provide a
  general idiom of aggregation of associated values. This
  idiom is very useful for computing statistical data through
  aggregation that occur in time.

* Sometimes a more simple and basic class of data structures
  is advantageous. It may be simpler to implement
  optimizations. Like Lukes Manhattan integral polygons
  compared to more general GGL polygons.

* Transfer of geometry knowledge to the more simple models
  of interval sets and maps may be a step users may not
  come up with.

* The basic set and map concepts of the ITL allow for a
  variety of applications that may go beyond the scope of
  geometry. One such example is the self compressing
  large bitset, which not really has the look and feel of
  geometry ...
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/projects.html
  ... or the example of a system of authorisations. See
  the example user_groups
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/examples/user_groups.html

* Well known data structures from geometry like interval_tree or
  spatial indices do have different focuses and different applications.
  An interval_tree is more space efficient than an interval_map that
  can computes all overlaps at once. This may be desired if you
  need all of them. If you don't and you have reoccurring arbitrary
  stabbing queries interval_trees are the better choice.

* itl::Maps are defining a generalized addition, which I think
  is a quite powerful feature that accounts for most of the
  goodies in the applications that we have done. This addition
  function is a generalisation of the common insert function on
  SortedAssociativeContainers and it introduces the aggregating
  properties of itl::Maps. The aggregate on overlap idiom is
  independent of the question, if the domain_type of the
  map or interval_map is a scalar or a tuple (has dimensions)
  or something else. There are already interesting applications
  of aggregations using itl::maps of tuples, but this exceeds the
  scope of the core library.

Cheers,
Joachim