[itl] Preview 4 of the Interval Template Library
Dear list, I am happy to announce that the Interval Template Library (Boost.Itl) converges to a state, that conforms the standards of the boost libraries. It now contains substantial test suites and almost complete quickbook documentation. I hope it will soon be mature for a formal review after a last round of feedback and subsequent improvements. Since the last progress report in November last year the following work has been done. + Interoperability of interval_containers: Addition, subtraction, intersection and symmetric difference are now interoperable for all combinations of interval containers that make sense: You may for instance intersect a split_interval_map with an interval_map, an interval_set an interval or an element. + Added symmetric difference and renamed operators in accordance to other set class templates like e.g. boost::dynamic_bitset. + Introduced infix operators as itl::namespace global functions that are interoperable between interval_maps, sets, intervals and elements, so far as the combinations make sense. + Operators are now +=, +, |=, | : Set union / Map union with aggregation -=, - : Set difference / Map union with aggregation &=, & : Set intersection / Map intersection with aggregation ^=, ^ : Set symmetric difference / Map symmetric difference with aggregation. + Extended the test suite, specifically for the new operators and their overloadings. + Wrote quickbook documentation for the library. Please note that the original ITL as presented in May 2008 has been split into 3 parts and only the *first* part is prepared for boost now: itl : Core library, interval containers, PREPARED FOR BOOST itl_xt : Extensions like histories and generalized crosstables validate: The law based test automaton (LaBatea). A validation tool using laws aka axioms. So please focus on the core part (itl). Download the current version 'preview 4' from the boost vault's containers section: itl.zip http://www.boostpro.com/vault/index.php?action=downloadfile&filename=itl.zip&directory=Containers If you are interested in extended parts or LaBatea you may download all parts as itl_plus.zip http://www.boostpro.com/vault/index.php?action=downloadfile&filename=itl_plus.zip&directory=Containers The quickbook generated documentation is included in the zip files and is also availabe online at http://herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/index.html Sources are also available form the sandbox: https://svn.boost.org/svn/boost/sandbox/itl/ The documentation has a focus on tree aspects (1) A short introduction, that wants to be easy to understand and to provide good and use case related examples: http://herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/index.html#boost_... http://herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/example... (2) Synoptical representations that allows to see the complete 'picture' of the library. For instance the function matrix http://herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/interfa... is supposed to give a complete overview over the most important functions across all itl containers. (3) A description of the semantics which is characterized by sets of laws that apply for the different interval containers. The semantical analysis, based on sets of laws, was a quite interesting work, where software development sometimes transformed into software discovery guided by the validation tool LaBatea ;) My main finding out of that process was, that the semantics of the aggregating itl::Maps is determined by the semantics of their data or codomain parameter U, so that if U is model of concept C then itl::Map<T,U> is model of C which is stated in section concept induction: http://herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/semanti... All your feedback is welcome. Cheers Joachim
I talk a quick look at the documentation. I'd like to suggest that the introduction needs to be more introductory. It seems to jump right in to technical details. What is ITL? What is the motivation to use it? What might it be used for?
Hi Joachim, Joachim Faulhaber wrote:
I have an application for which I have been considering implementing an interval tree (i.e. http://en.wikipedia.org/wiki/Interval_tree). A quick look at your docs does not reveal the implementation that you are using, but I have the impression that it's something different. Can you comment on the complexity / efficiency of whatever you're doing compared to a traditional interval tree? I.e. complexity for insert and lookup, storage required, number of bytes of overhead per element etc. To make that concrete, say I have N items and for each I store one pointer indexed by an interval of floats. How much space is needed, and how much time is needed to find the M items that (partially) overlap some interval? Sorry if this is in the docs somewhere but I couldn't find it. Cheers, Phil.
2009/3/5 Phil Endecott <spam_from_boost_dev@chezphil.org>:
Yes, different. Itl containers use std::set and and std::map as implementing containers. Sorry, I should have mentioned that in my post: A section about the implementation and it's complexity is one of the important things that is still missing from the documentation. I will do that next. Itl's interval containers are different from interval trees. The most important difference is, that interval trees store all intervals that are inserted into them while itl interval containers only stores the resulting collection of non overlapping intervals. see http://herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/index.html#boost_... So intervals in itl interval containers do never overlap. But you can compute the overlap count of a set of intervals as aggregation result using an interval_map.
Roughly ... Time complexity of insert depends on the size of the inserted interval. Worst case is O(n lg(n)), if the inserted interval overlaps with all intervals in the container. For small intervals complexity approaches that of inserting singleton intervals: O(lg(n)) Lookup of an element is O(lg(n)). Lookup for intervals is not implemented, but an interval container can be intersected with an interval to obtain the result as intersection which has a worst case time complexity of O(n lg(n)). Again efficiency is much better here, and for other operations on interval containers, if the interval size is relatively small compared to the enclosing interval of the container and approaches O(lg(n)) then.
you could implement that via an interval_map<float, itl::set<ItemPtr> > item_map; But I admit this would work far less efficient than an interval tree, specifically if the inserted intervals are all of similar size. Joachim
participants (3)
-
Joachim Faulhaber -
Neal Becker -
Phil Endecott