[boost] [interval containers (itl)] Update on Review Version. Element iterators added.

Subject: [boost] [interval containers (itl)] Update on Review Version. Element iterators added.
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2009-12-08 11:57:03

Dear all,

while hanging around in "The Queue" my library was getting
pretty bored :-/ So I decided to implement some depreciated
featured to arrange for some entertainment =)

Well, jokes aside, for a long time I resisted to implement
iteration on *elements* for interval containers. Element
iterators would be an invitation to inefficient usage of
interval containers just by normal habitual use of iterators.
For instantiations with continuous domain types like
interval_set<double>, interval_set<rational<int>>,
interval_set<string>, etc. element iteration would not be
possible at all.

Yet the questions about such iteration and the related question
of interval containers being a model of SortedAssociativeContainer
reoccurred in many feed backs on presentations of my library.
There even was a proposal for a DenseSet library by
Vicente Botet in the wiki's Library Wish List:
https://svn.boost.org/trac/boost/wiki/LibrariesUnderConstruction
that follows the idea of interval containers but provides element
iteration in order to fully implement SortedAssociativeContainer.

So finally I decided to provide element iteration and put the
responsibility to avoid inefficient deployment on the user.
Moreover, while element iteration on interval containers can be
substituted easily by simple loops, the element iteration over an
interval_bitset that Zachary Turner asked for
http://archives.free.net.ph/message/20091103.064651.263bf6bb.en.html
is not so trivial, so it can not be substituted easily by a
few lines of user code. That gave me some new motivation.

So I have uploaded an update of my library's review version
http://www.boostpro.com/vault/index.php?action=downloadfile&filename=itl_3_2_0.zip&directory=Containers
to the vault that is extended by these features:

* element iterators on all interval containers
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/function_reference/element_iteration.html

* itl::insert_iterator and itl::inserter that allows interval containers
  to be copied or transformed from std::containers using
  insert semantics
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/examples/std_copy.html

* itl::add_iterator and itl::adder that allows interval containers
  to be copied or transformed from std::containers using
  addition semantics so that aggregate on overlap can be done.
http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/examples/std_transform.html

In the extended library itl_xt that is part of
http://www.boostpro.com/vault/index.php?action=downloadfile&filename=itl_plus_3_2_0.zip&directory=Containers

* there is an implementation of a large interval_bitset, that
  combines interval compression and bit compression.
  Element iteration is now available for interval_bitset.
https://svn.boost.org/svn/boost/sandbox/itl/boost/itl_xt/interval_bitset.hpp

Element iteration now enables interval_containers to be
used with std::algorithms like the corresponding containers
of elements. The major requirement for usability of element
iteration is that the interval container's domain_type is
a discrete type that has a smallest steppable unit and
exposes an increment and decrement operator for it's
in- and decrementation.

I have successfully tested copy (and variants), equal,
lexicogrphic_compare, find, lower_bound, upper_bound,
includes and set_<algorithms>. All tested algorithms
that were applicable to a SortedAssociativeContainer of
elements were also working with interval_containers using
element_iterators.

The test have been done using a law "AtomicEquivalence"
https://svn.boost.org/svn/boost/sandbox/itl/boost/validate/laws/atomic_equivalence.hpp
on the law based test automaton (LaBatea)
https://svn.boost.org/svn/boost/sandbox/itl/libs/validate/example/labat_sorted_associative_set_
https://svn.boost.org/svn/boost/sandbox/itl/libs/validate/example/labat_sorted_associative_set_back_
https://svn.boost.org/svn/boost/sandbox/itl/libs/validate/example/labat_sorted_associative_map_
https://svn.boost.org/svn/boost/sandbox/itl/libs/validate/example/labat_sorted_associative_map_back_
https://svn.boost.org/svn/boost/sandbox/itl/libs/validate/example/labat_sorted_associative_bitset_
https://svn.boost.org/svn/boost/sandbox/itl/libs/validate/example/labat_sorted_associative_bitset_back_

So I think this is a valuable addition to interval containers
in the end and I hope it'll make std::algorithm aficionados
among you happy ;-)

Cheers
Joachim

-----------------------------------------------------------
Some repeated information on the library:

Please note that the original ITL as presented in May 2008
has been split into 3 parts and only the *first* part was
submitted for review (2009-09-18):

itl     : Core library, interval containers, SUBMITTED FOR REVIEW

Additional parts are:
itl_xt  : Extensions like interval_bitset, histories and generalized
           crosstables
validate: The law based test automaton (LaBatea). A validation
        tool using laws aka axioms.

*itl* is a complete library containing all required ingredients
particularly a separate test suite (NOT using LaBatea) and the
quickbook documentation. The code is successfully compiled
and tested with gcc-3.4.4, 4.1.0, 4.3.2 and msvc-8.0, 9.0, 10.0.
I have uploaded the first update of the review version as
itl_3_2_0.zip to the vault in section containers.

http://www.boostpro.com/vault/index.php?action=downloadfile&filename=itl_3_2_0.zip&directory=Containers

Another file itl_plus_3_2_0.zip contains all three parts
(itl, itl_xt and validate).

http://www.boostpro.com/vault/index.php?action=downloadfile&filename=itl_plus_3_2_0.zip&directory=Containers

Reviewers interested in the law based testing
part may have to refer to this file to examine
those tests. The law base testing examples
compile and run with gcc-4.3.2, msvc-8.0, 9.0 and 10.0.
LaBatea does not compile with gcc-4.1.0 or older.

The quickbook generated documentation is included in the
zip files and is also available 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/