Re: [boost] proposal: interval containers; boost examples and more

From: Alp Mestan (alpmestan_at_[hidden])
Date: 2008-07-29 07:44:03

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_at_[hidden]>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