2010/2/23 Mathias Gaunard
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/exa... 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/pro... ... 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/exa... * 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