proposal: interval containers; boost examples and more
Dear boost developers, after encouraging feedback by Paul A Bristow, Vicente Botet and Luke Simonson to my proposal on interval containers from end of May (http://lists.boost.org/Archives/boost/2008/05/137301.php), I started to boostify my interval template library (ITL). Even though there is a lot left to be done for the ITL to become fully boost compliant I'd like to report on some aspects of my current work. (1) As suggested by Paul A Bristow I have prepared some new examples that are using boost::date_time as instance types for the interval containers. * Example boost_party.cpp is a boostified instance of the introductory example party.cpp that demonstrates the 'aggregate on overlap' mechanism of interval maps (see: http://www.herold-faulhaber.de/itl/boost__party_8cpp.html). * Example month_and_weeks_grid.cpp demonstrates how different time grids can be merged in split_interval_sets by intersection (see: http://www.herold-faulhaber.de/itl/month__and__week__grid_8cpp.html). * Example man_power.cpp shows how calculations on interval_sets and maps can be obtained using set type operations. In the example the available man power in a small company is calculated accounting for weekends, holidays vacations etc. (see: http://www.herold-faulhaber.de/itl/man__power_8cpp.html). * Example user_groups shows how interval maps can be unified or intersected (see: http://www.herold-faulhaber.de/itl/user__groups_8cpp.html). (2) In the course of boostification of my code I have reviewed the design and completed the interval container classes as follows: * interval_set * split_interval_set * separate_interval_set (added) * interval_map (added) * split_interval_map You can see an overview these interval containers and some basic characteristics in the ITL's documentation here: http://www.herold-faulhaber.de/itl/interval__container__conduct_8h.html The major addition here is the class template interval_map. In contrast to a split_interval_map that preserves all interval borders that may emerge due to insertion and intersection operations, an interval_map keeps itself always minimal: Whenever two neighbouring interval-value pairs ([a,b), v), ([b,c),v) emerge, they will be joined to ([a,c),v). (3) Reviewing the overall design of the interval containers I have separated the meaning of insert/add and erase/subtract, which had been confounded in the previous version of the ITL. This has consequences especially for interval maps: As a design decision I'd like to choose that interval maps are addable and subtractable objects having operators += and -= that implement these properties. Addition and subtraction is then defined via element addition (add(value_type&)) and element subtraction (subtract(value_type&)). At a general level I can define add<inplace_op>(value_type&) and subtract<inplace_op>(value_type&)as member function templates, that implement aggregation on overlap (aggovering) not only for inplace_plus (+=) but also for arbitrary aggregate operations (inplace_op). It turned out, that function insert (std::insert semantics) can be expressed by the general add template (as well as erase can expressed by the subtract member function template): add<inplace_identity>(value_type&) is equivalent to insert(value_type&) subtract<inplace_erasure>(value_type&) is equivalent to erase(value_type&) In addition we can also define 'plain' element add and subtract by means of these templates: add(value_type&) can be defined as: add<inplace_plus>(value_type&) subtract(value_type&) can be defined as: subtract<inplace_minus>(value_type&) So for the ITL container classes I do provide now insert and erase that covers the std::semantics and I provide add and subtract that is the basis for addability and subtractability of itl::maps and itl::interval_maps. You can find an overview over all insert/erase and add/subtact functions and their relationships to std::semantics in the ITL's documentation here: http://www.herold-faulhaber.de/itl/interval__container__design_8h.html I find these design and semantical questions quite rich, and sometimes surprising ;-) and I have found many more aspects and properties while reviewing the ITL's design. I am planning to prepare a more detailed article about these topics in the next months to come. (4) I have prepared a new release 2.0.1 of the ITL for the current state that can be downloaded from: http://www.sourceforge.net/projects/itl Documentation is availabe online also from here: http://www.herold-faulhaber.de/itl The code is well tested using the Law Based Test Automaton (LaBatea) and is protabel for gcc 3.4.4 and msvc 8.0 sp1. I am sorry the ITL is still not in the boost standard directory structure. This will be one of the next steps on my todo list. (5) Concerning boostification of ITL there is still a lot to be done. Besides reviewing of the overall design reported above, I have removed virtual functions from all interval container classes using the curiously recurring template pattern (CRTP). To prevent you repeating advices that already found their way into my todo list I am listing it roughly as appendix to this posting. Cheers Joachim Faulhaber --- Boostification todo list: - Extracting a subset of the ITL as boost proposal - Providing the code in boost directory structure - Replacing own metaprogramming code by boost::mpl,fusion etc. - Using boost::value_initialized for generic initialisations - Further minimizing of class template interfaces and... - Providing more operators and functions as itl::global algorithms - Providing as much std::semantics as possible for interval containers (viewed as set<interval<T>> or map<interval<T>,U>) - Adapting testcode to boost testing standards - Improving documentation especially for issues of design and complexity - Providing boost style documentation - Preparing a proposal on the addition of open interval bounds to boost::interval
That looks quite good. Internally, how do you manage errors ? Is there an exception based system ? Or did you write some static-verification-system ? On Tue, Jul 29, 2008 at 8:51 AM, Joachim Faulhaber <afojgo@googlemail.com>wrote:
Dear boost developers,
after encouraging feedback by Paul A Bristow, Vicente Botet and Luke Simonson to my proposal on interval containers from end of May (http://lists.boost.org/Archives/boost/2008/05/137301.php), I started to boostify my interval template library (ITL). Even though there is a lot left to be done for the ITL to become fully boost compliant I'd like to report on some aspects of my current work.
(1) As suggested by Paul A Bristow I have prepared some new examples that are using boost::date_time as instance types for the interval containers.
* Example boost_party.cpp is a boostified instance of the introductory example party.cpp that demonstrates the 'aggregate on overlap' mechanism of interval maps (see: http://www.herold-faulhaber.de/itl/boost__party_8cpp.html).
* Example month_and_weeks_grid.cpp demonstrates how different time grids can be merged in split_interval_sets by intersection (see: http://www.herold-faulhaber.de/itl/month__and__week__grid_8cpp.html ).
* Example man_power.cpp shows how calculations on interval_sets and maps can be obtained using set type operations. In the example the available man power in a small company is calculated accounting for weekends, holidays vacations etc. (see: http://www.herold-faulhaber.de/itl/man__power_8cpp.html).
* Example user_groups shows how interval maps can be unified or intersected (see: http://www.herold-faulhaber.de/itl/user__groups_8cpp.html).
(2) In the course of boostification of my code I have reviewed the design and completed the interval container classes as follows:
* interval_set * split_interval_set * separate_interval_set (added)
* interval_map (added) * split_interval_map
You can see an overview these interval containers and some basic characteristics in the ITL's documentation here: http://www.herold-faulhaber.de/itl/interval__container__conduct_8h.html
The major addition here is the class template interval_map. In contrast to a split_interval_map that preserves all interval borders that may emerge due to insertion and intersection operations, an interval_map keeps itself always minimal: Whenever two neighbouring interval-value pairs ([a,b), v), ([b,c),v) emerge, they will be joined to ([a,c),v).
(3) Reviewing the overall design of the interval containers I have separated the meaning of insert/add and erase/subtract, which had been confounded in the previous version of the ITL. This has consequences especially for interval maps:
As a design decision I'd like to choose that interval maps are addable and subtractable objects having operators += and -= that implement these properties. Addition and subtraction is then defined via element addition (add(value_type&)) and element subtraction (subtract(value_type&)).
At a general level I can define add<inplace_op>(value_type&) and subtract<inplace_op>(value_type&)as member function templates, that implement aggregation on overlap (aggovering) not only for inplace_plus (+=) but also for arbitrary aggregate operations (inplace_op).
It turned out, that function insert (std::insert semantics) can be expressed by the general add template (as well as erase can expressed by the subtract member function template):
add<inplace_identity>(value_type&) is equivalent to insert(value_type&) subtract<inplace_erasure>(value_type&) is equivalent to erase(value_type&)
In addition we can also define 'plain' element add and subtract by means of these templates: add(value_type&) can be defined as: add<inplace_plus>(value_type&) subtract(value_type&) can be defined as: subtract<inplace_minus>(value_type&)
So for the ITL container classes I do provide now insert and erase that covers the std::semantics and I provide add and subtract that is the basis for addability and subtractability of itl::maps and itl::interval_maps.
You can find an overview over all insert/erase and add/subtact functions and their relationships to std::semantics in the ITL's documentation here: http://www.herold-faulhaber.de/itl/interval__container__design_8h.html
I find these design and semantical questions quite rich, and sometimes surprising ;-) and I have found many more aspects and properties while reviewing the ITL's design. I am planning to prepare a more detailed article about these topics in the next months to come.
(4) I have prepared a new release 2.0.1 of the ITL for the current state that can be downloaded from: http://www.sourceforge.net/projects/itl Documentation is availabe online also from here: http://www.herold-faulhaber.de/itl The code is well tested using the Law Based Test Automaton (LaBatea) and is protabel for gcc 3.4.4 and msvc 8.0 sp1. I am sorry the ITL is still not in the boost standard directory structure. This will be one of the next steps on my todo list.
(5) Concerning boostification of ITL there is still a lot to be done. Besides reviewing of the overall design reported above, I have removed virtual functions from all interval container classes using the curiously recurring template pattern (CRTP).
To prevent you repeating advices that already found their way into my todo list I am listing it roughly as appendix to this posting.
Cheers Joachim Faulhaber
--- Boostification todo list: - Extracting a subset of the ITL as boost proposal - Providing the code in boost directory structure - Replacing own metaprogramming code by boost::mpl,fusion etc. - Using boost::value_initialized for generic initialisations - Further minimizing of class template interfaces and... - Providing more operators and functions as itl::global algorithms - Providing as much std::semantics as possible for interval containers (viewed as set<interval<T>> or map<interval<T>,U>) - Adapting testcode to boost testing standards - Improving documentation especially for issues of design and complexity - Providing boost style documentation - Preparing a proposal on the addition of open interval bounds to boost::interval _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-- Alp Mestan --- http://blog.mestan.fr/ --- http://alp.developpez.com/ --- In charge of the Qt, Algorithms and Artificial Intelligence sections on Developpez
on Tue Jul 29 2008, "Alp Mestan" <alpmestan-AT-gmail.com> wrote:
That looks quite good.
Internally, how do you manage errors ? Is there an exception based system ? Or did you write some static-verification-system ?
On Tue, Jul 29, 2008 at 8:51 AM, Joachim Faulhaber <afojgo@googlemail.com>wrote:
Dear boost developers,
after encouraging feedback by Paul A Bristow, Vicente Botet and Luke Simonson to my proposal on interval containers from end of May (http://lists.boost.org/Archives/boost/2008/05/137301.php), I started to boostify my interval template library (ITL). Even though there is a lot left to be done for the ITL to become fully boost compliant I'd like to report on <snip entire (long!) post>
1. Please don't overquote 2. I wrote an interval map about ten years ago now by modifying the rb-tree implementation from STLPort. This can be a really useful class of data structures. I support continued work on getting this into Boost. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
2008/7/29, David Abrahams <dave@boostpro.com>:
on Tue Jul 29 2008, "Alp Mestan" <alpmestan-AT-gmail.com> wrote:
That looks quite good.
Internally, how do you manage errors ? Is there an exception based system ? Or did you write some static-verification-system ?
On Tue, Jul 29, 2008 at 8:51 AM, Joachim Faulhaber <afojgo@googlemail.com>wrote:
Dear boost developers,
after encouraging feedback by Paul A Bristow, Vicente Botet and Luke Simonson to my proposal on interval containers from end of May (http://lists.boost.org/Archives/boost/2008/05/137301.php), I started to boostify my interval template library (ITL). Even though there is a lot left to be done for the ITL to become fully boost compliant I'd like to report on <snip entire (long!) post>
1. Please don't overquote
2. I wrote an interval map about ten years ago now by modifying the rb-tree implementation from STLPort. This can be a really useful class of data structures. I support continued work on getting this into Boost.
Thank you for looking at my work. I am really happy to have such an influential boost developer supporting my project. You mention your own implementation of an interval map using rb-trees. As you might have noticed my library implements interval sets finally via std::sets and interval_maps via std::maps. I am well aware that a specifically tailored interval tree has an optimization potential over a std::container implementation. So this is also on my todo list. Yet I wanted to focus on design, clarity and correctness first before improving performance using a more optimally tailored implementation. I have been thinking about such optimized implementation a few times and would also choose a balanced tree implementation (e.g. the newly simplified left leaned rb trees by Robert Sedgewick http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf) that additionally exploits properties of the intervals. Therefore I am interested to take a look at your implementation of an interval map using rb-trees. This might save me some unnecessary hours of work. Thanks Joachim
2008/7/29, Alp Mestan <alpmestan@gmail.com>:
That looks quite good.
Thank you for looking at my project
Internally, how do you manage errors ? Is there an exception based system ? Or did you write some static-verification-system ?
Until now I did not see any necessity to throw or catch any exceptions in my implementation of interval containers. I do not have an internal error management and I hope I won't need it. Errors may result from inadequate instantiations of interval container parameters. To prevent such instantiations to cause unreadable compile time errors, I should use boost::concept_check. I will add this to my todo list. Thanks Joachim
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Joachim Faulhaber Sent: 29 July 2008 07:52 To: boost@lists.boost.org Subject: [boost] proposal: interval containers; boost examples and more
I started to boostify my interval template library (ITL). Even though there is a lot left to be done for the ITL to become fully boost compliant I'd like to report on some aspects of my current work.
A glance at your work in progress shows that you have made a lot of progress and that the design is maturing. It is especially reassuring that you have real-life working systems using your ITL, and some neat and nicely documented examples. I feel sure I will prove widely useful. I wonder if it is time for you to move this code to the Boost Sandbox? Any of the Boost Moderators may be willing to help with this? Paul --- Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539561830 & SMS, Mobile +44 7714 330204 & SMS pbristow@hetp.u-net.com
2008/8/7 Paul A Bristow <pbristow@hetp.u-net.com>:
I started to boostify my interval template library (ITL). Even though there is a lot left to be done for the ITL to become fully boost compliant I'd like to report on some aspects of my current work.
A glance at your work in progress shows that you have made a lot of progress and that the design is maturing. It is especially reassuring that you have real-life working systems using your ITL, and some neat and nicely documented examples.
I feel sure I will prove widely useful.
Thank you for your positive comments on my library code again.
I wonder if it is time for you to move this code to the Boost Sandbox? Any of the Boost Moderators may be willing to help with this?
After extracting the interval container part form the current release of the ITL and rearranging the files into the standard boost directory structure, moving the code to the boost sandbox can be the next step. Cheers Joachim
participants (4)
-
Alp Mestan -
David Abrahams -
Joachim Faulhaber -
Paul A Bristow