Subject: [Boost-commit] svn:boost r57073 - in sandbox/itl: boost/itl boost/validate/type libs/itl/build/win32 libs/itl/doc libs/itl/example/large_bitset_ libs/itl/example/std_copy_ libs/itl/example/std_transform_
From: afojgo_at_[hidden]
Date: 2009-10-22 12:17:24
Author: jofaber
Date: 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
New Revision: 57073
URL: http://svn.boost.org/trac/boost/changeset/57073
Log:
Added examples: std_copy, std_transform and large_bitset. Added documentation, section projects.qbk. Stable {msvc-9.0}
Added:
sandbox/itl/libs/itl/doc/projects.qbk (contents, props changed)
sandbox/itl/libs/itl/example/large_bitset_/
sandbox/itl/libs/itl/example/large_bitset_/bits.hpp (contents, props changed)
sandbox/itl/libs/itl/example/large_bitset_/large_bitset.cpp (contents, props changed)
sandbox/itl/libs/itl/example/large_bitset_/large_bitset.hpp (contents, props changed)
sandbox/itl/libs/itl/example/large_bitset_/meta_log.hpp (contents, props changed)
sandbox/itl/libs/itl/example/large_bitset_/vc9_large_bitset.vcproj (contents, props changed)
sandbox/itl/libs/itl/example/std_copy_/
sandbox/itl/libs/itl/example/std_copy_/std_copy.cpp (contents, props changed)
sandbox/itl/libs/itl/example/std_copy_/vc9_std_copy.vcproj (contents, props changed)
sandbox/itl/libs/itl/example/std_transform_/
sandbox/itl/libs/itl/example/std_transform_/std_transform.cpp (contents, props changed)
sandbox/itl/libs/itl/example/std_transform_/vc9_std_transform.vcproj (contents, props changed)
Text files modified:
sandbox/itl/boost/itl/interval_base_map.hpp | 4
sandbox/itl/boost/itl/interval_base_set.hpp | 4
sandbox/itl/boost/itl/split_interval_set.hpp | 4
sandbox/itl/boost/validate/type/bits.hpp | 8 +-
sandbox/itl/libs/itl/build/win32/vc9_all.sln | 6 ++
sandbox/itl/libs/itl/doc/acknowledgments.qbk | 5 +
sandbox/itl/libs/itl/doc/examples.qbk | 81 ++++++++++++++++++++++++++++++++++++++++
sandbox/itl/libs/itl/doc/itl.qbk | 2
8 files changed, 102 insertions(+), 12 deletions(-)
Modified: sandbox/itl/boost/itl/interval_base_map.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_base_map.hpp (original)
+++ sandbox/itl/boost/itl/interval_base_map.hpp 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -1389,10 +1389,10 @@
inline bool operator == (const interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>& lhs,
const interval_base_map<SubType,DomainT,CodomainT,Traits,Compare,Combine,Section,Interval,Alloc>& rhs)
{
- //MEMO PORT: This implemetation worked with stlport, sgi and gnu
+ //MEMO PORT: This implementation worked with stlport, sgi and gnu
// implementations of the stl. But using MSVC-implementation
// results in runtime error! So I had to provide an independent
- // safe implemetation.
+ // safe implementation.
//return std::equal(lhs.begin(), lhs.end(), rhs.begin());
return Set::lexicographical_equal(lhs, rhs);
}
Modified: sandbox/itl/boost/itl/interval_base_set.hpp
==============================================================================
--- sandbox/itl/boost/itl/interval_base_set.hpp (original)
+++ sandbox/itl/boost/itl/interval_base_set.hpp 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -691,10 +691,10 @@
inline bool operator == (const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& lhs,
const interval_base_set<SubType,DomainT,Compare,Interval,Alloc>& rhs)
{
- //MEMO PORT: This implemetation worked with stlport, sgi and gnu
+ //MEMO PORT: This implementation worked with stlport, sgi and gnu
// implementations of the stl. But using MSVC-implementation
// results in runtime error! So I had to provide an independent
- // safe implemetation.
+ // safe implementation.
//return std::equal(lhs.begin(), lhs.end(), rhs.begin());
return Set::lexicographical_equal(lhs, rhs);
}
Modified: sandbox/itl/boost/itl/split_interval_set.hpp
==============================================================================
--- sandbox/itl/boost/itl/split_interval_set.hpp (original)
+++ sandbox/itl/boost/itl/split_interval_set.hpp 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -325,10 +325,10 @@
inline bool operator == (const split_interval_set<DomainT,Compare,Interval,Alloc>& lhs,
const split_interval_set<DomainT,Compare,Interval,Alloc>& rhs)
{
- //MEMO PORT: This implemetation worked with stlport, sgi and gnu
+ //MEMO PORT: This implementation worked with stlport, sgi and gnu
// implementations of the stl. But using MSVC-implementation
// results in runtime error! So I had to provide an independent
- // safe implemetation.
+ // safe implementation.
//return std::equal(lhs.begin(), lhs.end(), rhs.begin());
return Set::lexicographical_equal(lhs, rhs);
}
Modified: sandbox/itl/boost/validate/type/bits.hpp
==============================================================================
--- sandbox/itl/boost/validate/type/bits.hpp (original)
+++ sandbox/itl/boost/validate/type/bits.hpp 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -66,11 +66,11 @@
BOOST_STATIC_CONSTANT(bool, value = true);
};
-template <>struct type_to_string<itl::bits<unsigned char> > {static std::string apply(){ return "bit8"; }};
+template <>struct type_to_string<itl::bits<unsigned char > >{static std::string apply(){ return "bit8"; }};
template <>struct type_to_string<itl::bits<unsigned short> >{static std::string apply(){ return "bit16"; }};
-template <>struct type_to_string<itl::bits<unsigned int> > {static std::string apply(){ return "bit32"; }};
-template <>struct type_to_string<itl::bits<unsigned long> > {static std::string apply(){ return "bitl32"; }};
-template <>struct type_to_string<itl::bits<unsigned long long> > {static std::string apply(){ return "bit64"; }};
+template <>struct type_to_string<itl::bits<unsigned int > >{static std::string apply(){ return "bit32"; }};
+template <>struct type_to_string<itl::bits<unsigned long > >{static std::string apply(){ return "bitl32"; }};
+template <>struct type_to_string<itl::bits<unsigned long long> >{static std::string apply(){ return "bit64"; }};
}} // namespace itl boost
Modified: sandbox/itl/libs/itl/build/win32/vc9_all.sln
==============================================================================
--- sandbox/itl/libs/itl/build/win32/vc9_all.sln (original)
+++ sandbox/itl/libs/itl/build/win32/vc9_all.sln 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -143,6 +143,8 @@
EndProject
Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "vc9_std_copy", "..\..\example\std_copy_\vc9_std_copy.vcproj", "{8DC9BDE4-E5A4-4294-A12F-D75FD6990B84}"
EndProject
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "vc9_std_transform", "..\..\example\std_transform_\vc9_std_transform.vcproj", "{8DC9BDE4-E5A4-4294-A12F-D75FD6990B85}"
+EndProject
Global
GlobalSection(SolutionConfigurationPlatforms) = preSolution
Debug|Win32 = Debug|Win32
@@ -433,6 +435,10 @@
{8DC9BDE4-E5A4-4294-A12F-D75FD6990B84}.Debug|Win32.Build.0 = Debug|Win32
{8DC9BDE4-E5A4-4294-A12F-D75FD6990B84}.Release|Win32.ActiveCfg = Release|Win32
{8DC9BDE4-E5A4-4294-A12F-D75FD6990B84}.Release|Win32.Build.0 = Release|Win32
+ {8DC9BDE4-E5A4-4294-A12F-D75FD6990B85}.Debug|Win32.ActiveCfg = Debug|Win32
+ {8DC9BDE4-E5A4-4294-A12F-D75FD6990B85}.Debug|Win32.Build.0 = Debug|Win32
+ {8DC9BDE4-E5A4-4294-A12F-D75FD6990B85}.Release|Win32.ActiveCfg = Release|Win32
+ {8DC9BDE4-E5A4-4294-A12F-D75FD6990B85}.Release|Win32.Build.0 = Release|Win32
EndGlobalSection
GlobalSection(SolutionProperties) = preSolution
HideSolutionNode = FALSE
Modified: sandbox/itl/libs/itl/doc/acknowledgments.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/acknowledgments.qbk (original)
+++ sandbox/itl/libs/itl/doc/acknowledgments.qbk 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -17,6 +17,7 @@
Many thanks to Paul A. Bristow, Vicente Botet, Luke Simonson,
Alp Mestan, David Abrahams, Steven Watanabe, Neal Becker,
+Robert Stewart, Jeff Flinn
and other developers
form the Boost community who supported the development of the
Interval Template Library by numerous hints and feedbacks on
@@ -26,8 +27,8 @@
Barend Gehrels, Luke Simonson and Hartmut Kaiser.
Special thanks for reading and improving this documentation to
Neal Becker and Ilya Bobir.
-Jeff Flinn did a great job fixing portability problems with
-CodeWarrior 9.4.
+Jeff Flinn provided valuable feedback and a codepatch to fix
+portability problems with CodeWarrior 9.4. Many thanks for that.
[endsect]
Modified: sandbox/itl/libs/itl/doc/examples.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/examples.qbk (original)
+++ sandbox/itl/libs/itl/doc/examples.qbk 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -26,6 +26,10 @@
[[basic] [[link boost_itl.examples.overlap_counter Overlap counter]]
[__itv_map__][The most simple application of an interval map:
Counting the overlaps of added intervals.]]
+ [[basic] [[link boost_itl.examples.std_copy Std copy]]
+ [__itv_map__][Fill interval containers using `std::copy`.]]
+ [[basic] [[link boost_itl.examples.std_transform Std transform]]
+ [__itv_map__,\n__sep_itv_set__][Fill interval containers from user defined objects using `std::transform`.]]
[[advanced][[link boost_itl.examples.partys_height_average Party's height average]]
[__itv_map__][Using /aggregate on overlap/ the average of party guests is computed.
Associated values are user defined class objects, that implement
@@ -153,6 +157,83 @@
[example_overlap_counter]
[endsect]
+
+[section Std copy]
+
+The standard algorithm
+[@http://www.cplusplus.com/reference/algorithm/copy/ `std::copy`]
+can be used to fill interval containers
+from standard containers of intervals or
+interval value pairs (segments). Because intervals
+do not represent ['*elements*] but ['*sets*], that
+can be empty or contain more than one element,
+the usage of `std::copy` differs from what we
+are familiar with using ['containers of elements].
+
+* Use `itl::inserter` from `#include <boost/itl/iterator.hpp>`
+ instead of `std::inserter` to call insertions on the target
+ interval container.
+
+* As shown in the examples above and below this point, most of
+ the time we will not be interested to `insert` segments
+ into __itv_maps__ but to __biLadd__
+ them, in order to generate the desired aggregation results.
+ You can use `std::copy` with an `itl::adder` instead of an
+ `itl::inserter` to achieve this.
+
+[import ../example/std_copy_/std_copy.cpp]
+[example_std_copy]
+
+[endsect][/ Std copy]
+
+
+[section Std transform]
+
+Instead of writing loops, the standard algorithm
+[@http://www.cplusplus.com/reference/algorithm/transform/ `std::transform`]
+can be used to fill interval containers
+from std containers of user defined objects.
+We need a function, that
+maps the ['user defined object] into the
+['segement type] of an interval map or the
+['interval type] of an interval set.
+Based on that we can use `std::transform`
+with an `itl::inserter` or `itl::adder`
+to transform the user objects into interval
+containers.
+
+[import ../example/std_transform_/std_transform.cpp]
+[example_std_transform]
+
+To get clear about the different behaviors of interval containers
+in the example, you may want to refer to the section about
+[link boost_itl.introduction.interval_combining_styles interval combining styles]
+that uses the same data.
+
+[/
+Instead of `itl::inserter` we could also use an `std::inserter`
+with algorithms `std::copy` and `std::transform`.
+This is ['*depreciated*], because `std::inserter` is designed for
+containers of elements, where ['*exacty one*] element is inserted
+via `std::inserter` if it is not already in the container.
+In contrast to that, an interval or segemnt can represent zero, one,
+or many elements of an interval container.
+
+You can use `std::inserter` *only*, if you actively take care of
+two preconditions:
+
+# None of the intervals or segements of the source containers
+ must be empty.
+
+# A segment never carries a neutral value when your target
+ interval map absorbs neutrons.
+
+Violating those preconditions leads to ['*undefined behavior*].
+]
+
+[endsect][/ std::transform]
+
+
[section:partys_height_average Party's height average]
In the example `partys_height_average.cpp` we compute yet another aggregation:
Modified: sandbox/itl/libs/itl/doc/itl.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/itl.qbk (original)
+++ sandbox/itl/libs/itl/doc/itl.qbk 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -135,6 +135,7 @@
[def __biLRange__ [link boost_itl.function_reference.range ['*Range*]]]
[def __biLSelection__ [link boost_itl.function_reference.selection ['*Selection*]]]
[def __biLAddition__ [link boost_itl.function_reference.addition ['*Addition*]]]
+[def __biLadd__ [link boost_itl.function_reference.addition ['*add*]]]
[def __biLSubtraction__ [link boost_itl.function_reference.subtraction ['*Subtraction*]]]
[def __biLsubtraction__ [link boost_itl.function_reference.subtraction ['*subtraction*]]]
[def __biLInsertion__ [link boost_itl.function_reference.insertion ['*Insertion*]]]
@@ -192,6 +193,7 @@
[include introduction.qbk]
[include examples.qbk]
+[include projects.qbk]
[include concepts.qbk]
[include semantics.qbk]
[include interface.qbk]
Added: sandbox/itl/libs/itl/doc/projects.qbk
==============================================================================
--- (empty file)
+++ sandbox/itl/libs/itl/doc/projects.qbk 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -0,0 +1,501 @@
+[/
+ Copyright (c) 2009-2009 Joachim Faulhaber
+
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENSE_1_0.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
+]
+
+[section Projects]
+
+['*Projects*] are examples on the usage of interval containers
+that go beyond small toy snippets of code. The code presented
+here addresses more serious applications that approach the
+quality of real world programming. At the same time it aims to
+guide the reader more deeply into various aspects of
+the library. In order not to overburden the reader with implementation
+details, the code in ['*projects*] tries to be ['*minimal*]. It has a focus on
+the main aspects of the projects and is not intended to be complete
+and mature like the library code itself. Cause it's minimal,
+project code lives in `namespace mini`.
+
+[/
+[section Overview]
+
+[table Overview over Itl Examples
+ [[level] [example] [classes] [features]]
+ [[basic] [[link boost_itl.examples.large_bitset Large Bitset]]
+ [__itv_map__][The most simple application of an interval map:
+ Counting the overlaps of added intervals.]]
+]
+
+[endsect][/ Overview IN Projects]
+]
+
+[section Large Bitset][/ IN Projects]
+
+Bitsets are just sets. Sets of unsigned integrals,
+to be more precise.
+The prefix ['*bit*] usually only indicates,
+that the representation of those sets is organized in a compressed
+form that exploits the fact, that we can switch on an off single
+bits in machine word. Bitsets are therefore known to be very small
+and thus efficient.
+The efficiency of bitsets is usually coupled to the
+precondition that the range of values of elements
+is relatively small, like [0..32) or [0..64), values that can
+be typically represented in single or a small number of
+machine words. If we wanted to represent a set containing
+two values {1, 1000000}, we would be much better off using
+other sets like e.g. an `std::set`.
+
+Bitsets compress well, if elements spread over narrow ranges
+only. Interval sets compress well, if many elements are clustered
+over intervals. They can span large sets very efficiently then.
+In project ['*Large Bitset*] we want to ['*combine the bit compression
+and the interval compression*] to achieve a set implementation,
+that is capable of spanning large chunks of contiguous elements
+using intervals and also to represent more narrow ['nests] of varying
+bit sequences using bitset compression.
+As we will see, this can be achieved using only a small
+amount of code because most of the properties we need
+are provided by an __itv_map__ of `bitsets`:
+
+``
+typedef interval_map<NaturalT, SomeBitSet<N>, partial_absorber,
+ std::less, inplace_bit_add, inplace_bit_and> IntervalBitmap;
+``
+
+Such an `IntervalBitmap` represents `k*N` bits for every segment.
+``
+[a, a+k)->'1111....1111' //(N bits)
+``
+
+For the interval `[a, a+k)` above all bits are set.
+But we can also have individual ['nests] or ['clusters]
+of bitsequences.
+
+``
+[b, b+1)->'01001011...1'
+[b+1,b+2)->'11010001...0'
+. . .
+``
+
+and we can span intervals of equal bit sequences that represent
+periodic patterns.
+
+``
+[c,d)->'010101....01' // Every second bit is set in range [c,d)
+[d,e)->'001100..0011' // Every two bits alterate in range [d,e)
+[e,f)->'bit-sequence' // 'bit-sequence' reoccurs every N bits in range [e,f)
+``
+
+An `IntervalBitmap` can represent
+`N*(2^M-1)` elements, if `M` is the number of bits of the
+unsigned integral type `NaturalT`.
+There are fields where such large
+bitsets implementations are needed. E.g. for the compact
+representation of large file allocation tables.
+What remains to be done for project *Large Bitset* is
+to code a wrapper `class large_bitset` around `IntervalBitmap`
+so that `large_bitset` looks and feels like a usual
+set class.
+
+[section Usage of a large_bitset]
+
+To quicken your appetite for a look at the implementation
+here are a few use cases first. Let's start large.
+In the first example . . .
+
+[import ../example/large_bitset_/large_bitset.cpp]
+[large_bitset_test_large_set_all]
+
+. . . we are testing the limits. First we set all bits and
+the we switch off the very last bit.
+
+[large_bitset_test_large_erase_last]
+
+Program output (/a little beautified/):
+``
+----- Test function test_large() -----------------------------------------------
+We have just turned on the awesome amount of 18,446,744,073,709,551,615 bits ;-)
+[ 0, 288230376151711744) -> 1111111111111111111111111111111111111111111111111111111111111111
+---- Let's swich off the very last bit -----------------------------------------
+[ 0, 288230376151711743) -> 1111111111111111111111111111111111111111111111111111111111111111
+[288230376151711743, 288230376151711744) -> 1111111111111111111111111111111111111111111111111111111111111110
+---- Venti is plenty ... let's do something small: A tall ----------------------
+``
+
+More readable is a smaller version of `large_bitset`.
+In function `test_small()` we apply a few more operations . . .
+
+[large_bitset_test_small]
+
+. . . producing this output:
+``
+----- Test function test_small() -----------
+-- Switch on all bits in range [0,64] ------
+[0,9)->11111111
+--------------------------------------------
+-- Turn off bits: 25,27,28 -----------------
+[0,3)->11111111
+[3,4)->10100111
+[4,9)->11111111
+--------------------------------------------
+-- Flip bits in range [24,30) --------------
+[0,3)->11111111
+[3,4)->01011011
+[4,9)->11111111
+--------------------------------------------
+-- Remove the first 10 bits ----------------
+[1,2)->00111111
+[2,3)->11111111
+[3,4)->01011011
+[4,9)->11111111
+--------------------------------------------
+``
+
+Finally, we present a little /picturesque/ example,
+that demonstrates that `large_bitset` can also serve
+as a self compressing bitmap, that we can 'paint' with.
+
+[large_bitset_test_picturesque]
+
+Note that we have two `large_bitsets` for the /outline/
+and the /interior/. Both parts are compressed but we can
+compose both by `operator +`, because the right /positions/
+are provided. This is the program output:
+
+``
+----- Test function test_picturesque() -----
+-------- empty face: 3 intervals -----
+********
+* *
+* *
+* *
+* *
+ ******
+-------- compressed smile: 2 intervals -----
+ * *
+ ****
+-------- staring bitset: 6 intervals -----
+********
+* *
+* * * *
+* *
+* **** *
+ ******
+--------------------------------------------
+``
+
+So, may be you are curious how this class template
+is coded on top of __itv_map__ using only about 250 lines
+of code. This is shown in the sections that follow.
+
+[endsect][/ Usage of a large_bitset]
+
+[section The interval_bitmap]
+
+To begin, let's look at the basic data type again, that
+will be providing the major functionality:
+
+``
+typedef interval_map<DomainT, BitSetT, partial_absorber,
+ std::less, inplace_bit_add, inplace_bit_and> IntervalBitmap;
+``
+
+`DomainT` is supposed to be an unsigned integral
+type, the bitset type `BitSetT` will be a wrapper class around an
+unsigned integral type. `BitSetT` has to implement bitwise operators
+that will be called by the functors `inplace_bit_add` and `inplace_bit_and`.
+The type trait of interval_map is `partial_absorber`, which means
+that it is /partial/ and that empty `BitSetTs` are not stored in
+the map. This is desired and keeps the `interval_map` minimal, storing
+only bitsets, that contain at least one bit switched on.
+Functor `inplace_bit_add` for parameter `Combine` indicates that we
+do not expect `operator +=` as addition but the bitwise operator
+`|=`. For parameter `Section` we expect the bitwise `&=` operator.
+
+[endsect][/ section The interval_bitmap]
+
+[section A class implementation for the bitset type]
+
+The code of the project is enclosed in a `namespace mini`.
+The name indicates, that the implementation is a /minimal/
+example implementation. The name of the bitset class will
+be `bits` or qualified `mini::bits`.
+
+To be used as a codomain parameter of class template __itv_map__
+`mini::bits` has implement all the functions that are required
+for a codomain_type in general, which are the default ctor `bits()`
+and `operator==`. Moreover `mini::bits` has to implement operators
+required by the instantiations for parameter `Combine` and `Section`
+which are `inplace_bit_add` and `inplace_bit_and`. From functors
+`inplace_bit_add` and `inplace_bit_and` there are inverse functors
+`inplace_bit_subtract` and `inplace_bit_xor`. Those functors
+use operators `|= &= ^=` and `~`. Finally if we want to apply
+lexicographical and subset comparison on large_bitset, we also
+need an `operator <`. All the operators that we need can be implemented
+for `mini::bits` on a few lines:
+
+[import ../example/large_bitset_/bits.hpp]
+[mini_bits_class_bits]
+
+Finally there is one important piece of meta information, we have
+to provide: `mini::bits` has to be recognized as a `Set` by the
+itl code. Otherwise we can not exploit the fact that a map of
+sets is model of `Set` and the resulting large_bitset would not
+behave like a set. So we have to say that `mini::bits` shall be sets:
+
+[mini_bits_is_set]
+
+This is done by adding a partial template specialization to
+the type trait template `itl::is_set`.
+For the extension of this type trait template and the result
+values of inclusion_compare we need these `#includes` for the
+implementation of `mini::bits`:
+
+[mini_bits_includes]
+
+[endsect][/ A class implementation for the bitset type]
+
+[section Implementation of a large bitset]
+
+Having finished our `mini::bits` implementation, we can start to
+code the wrapper class that hides the efficient interval map of mini::bits
+and exposes a simple and convenient set behavior to the world of users.
+
+Let's start with the required `#include`s this time:
+
+[import ../example/large_bitset_/large_bitset.hpp]
+[large_bitset_includes]
+
+Besides `boost/itl/interval_map.hpp` and `bits.hpp` the most important
+include here is `boost/operators.hpp`. We use this library in order
+to further minimize the code and to provide pretty extensive operator
+functionality using very little code.
+
+For a short and concise naming of the most important unsigned integer
+types and the corresponding `mini::bits` we define this:
+
+[large_bitset_natural_typedefs]
+
+[section large_bitset: Public interface][/ ------------------------------------]
+
+An now let's code `large_bitset`.
+
+[large_bitset_class_template_header]
+
+The first template parameter `DomainT` will be instantiated with
+an unsigned integral type that defines the set of numbers that can
+be included in the set. Since we want to go for a large set we
+use `nat3` as default which is a 64 bit unsigned integer ranging
+from `0` to `2^64-1`. As bitset parameter we also choose a 64-bit
+default. Parameters `Combine` and `Interval` are necessary to
+be passed to dependent type expressions. An allocator can be
+chosen, if desired.
+
+The nested list of private inheritance contains groups of template
+instantiations from
+[@http://www.boost.org/doc/libs/1_39_0/libs/utility/operators.htm Boost.Operator],
+that provides derivable operators from more fundamental once.
+Implementing the fundamental operators, we get the derivable ones
+/for free/. Below is a short overview of what we get using Boost.Operator,
+where __S stands for `large_bitset`, __i for it's `interval_type`
+and __e for it's `domain_type` or `element_type`.
+
+[table
+[[Group ][fundamental] [derivable ]]
+[[Equality, ordering ][`==`] [`!=` ]]
+[[ ][`<` ] [`> <= >=` ]]
+[[Set operators (__S x __S)][`+= |= -= &= ^=` ][`+ | - & ^` ]]
+[[Set operators (__S x __e)][`+= |= -= &= ^=` ][`+ | - & ^` ]]
+[[Set operators (__S x __i)][`+= |= -= &= ^=` ][`+ | - & ^` ]]
+]
+
+There is a number of associated types
+
+[large_bitset_associated_types]
+
+most importantly the implementing `interval_bitmap_type` that is used
+for the implementing container.
+
+[large_bitmap_impl_map]
+
+In order to use
+[@http://www.boost.org/doc/libs/1_39_0/libs/utility/operators.htm Boost.Operator]
+we have to implement the fundamental operators as class members. This can be
+done quite schematically.
+
+[large_bitset_operators]
+
+As we can see, the seven most important operators that work on the
+class type `large_bitset` can be directly implemented propagation
+the operation to the implementing `_map`
+of type `interval_bitmap_type`. For the operators that work on segment and
+element types, we use member functions `add`, `subtract`, `intersect` and
+`flip`. As we will see only a small amount of adaper code in needed
+to couple those functions with the functionality of the implementing
+container.
+
+Member functions `add`, `subtract`, `intersect` and `flip`,
+that allow to combine ['*intervals*] to `large_bitsets` can
+be uniformly implemented using a private function
+`segment_apply` that applies /addition/, /subtraction/,
+/intersection/ or /symmetric difference/, after having
+translated the intervals borders into the right bitset
+positions.
+
+[large_bitset_fundamental_functions]
+
+In the sample programs, that we will present to demonstrate
+the capabilities of `large_bitset` we will need a few additional
+functions specifically output functions in two different
+flavors.
+
+[large_bitset_demo_functions]
+
+* The first one, `show_segments()` shows the container
+content as it is implemented, in the compressed form.
+
+* The second function `show_matrix` shows the complete
+matrix of bits that is represented by the container.
+
+[endsect][/ large_bitset: Public interface]
+[section large_bitset: Private implementation] [/ -------------------------------------]
+
+In order to implement operations like the addition of
+an element say `42` to
+the large bitset, we need to translate the /value/ to the
+/position/ of the associated *bit* representing `42` in the
+interval container of bitsets. As an example, suppose we
+use a
+``
+large_bitset<nat, mini::bits8> lbs;
+``
+that carries small bitsets of 8 bits only.
+The first four singleton interval of `lbs` are assumed to
+be associated with some bitsets. Now we want to add the interval
+`[a,b]==[5,27]`. This will result in the following situation:
+``
+ [0,1)-> [1,2)-> [2,3)-> [3,4)->
+ [00101100][11001011][11101001][11100000]
++ [111 11111111 11111111 1111] [5,27] as bitset
+ a b
+
+=> [0,1)-> [1,3)-> [3,4)->
+ [00101111][11111111][11110000]
+``
+So we have to convert values 5 and 35 into a part that
+points to the interval and a part that refers to the
+position within the interval, which is done by a
+/division/ and a /modulo/ computation. (In order to have a
+consistent representation of the bitsequences across the containers,
+within this project, bitsets are denoted with the
+['*least significant bit on the left!*])
+
+``
+A = a/8 = 5/8 = 0 // refers to interval
+B = b/8 = 27/8 = 3
+R = a%8 = 5%8 = 5 // refers to the position in the associated bitset.
+S = b%8 = 27%8 = 3
+``
+
+All /division/ and /modulo operations/ needed here are always done
+using a divisor `d` that is a power of `2`: `d = 2^x`. Therefore
+division and modulo can be expressed by bitset operations.
+The constants needed for those bitset computations are defined
+using the BOOST_STATIC_CONSTANT macro, which guarantees portability:
+
+[large_bitset_impl_constants]
+
+Applied to the example type `large_bitset<nat, mini::bits8>` we have
+
+[table
+[/ [] [] [] [] [] ]
+[[Type] [Constant] [Expression] [Example] [Comment] ]
+[[`chunk_type`][`bit_count`][`(sizeof chunk_type)*CHAR_BIT )`][`8`] [Size of the associated bitsets]]
+[[`chunk_type`][`divisor`] [`bit_count`] [`8`] [Divisor to find intervals for values]]
+[[`chunk_type`][`shift`] [`log2_<divisor>::value`] [`3`] [To express the division as bit shift]]
+[[`chunk_type`][`c1`] [`static_cast<chunk_type>(1)`] [ ] [Helps to avoid static_casts for `long long`. ]]
+[[`chunk_type`][`mask`] [`divisor - c1`] [`7 = '11100000'`] [Helps to express the modulo operation as bit_and.\n
+ *Note*: least significant bit on the left!]]
+[[`chunk_type`][`all`] [`~static_cast<chunk_type>(0)`] [`255 = '11111111'`][Helps to express a complete associated bitset.]]
+[[`chunk_type`][`top`] [`c1 << (bit_count-c1)`] [`128 = '00000001'`][Value of the most significant bit of associated bitsets.]]
+]
+
+Looking at the example again, we can see that we have to identify the
+positions of the beginning and ending of the interval [5,7] that is
+to insert, and then ['*subdivide*] that range of bitsets into three partitions.
+
+# The bitset where the interval starts.
+# the bitset where the interval ends
+# The bitsets that are completely overlapped by the interval
+
+``
+combine interval [5,27] to large_bitset lbs w.r.t. some operation o
+
+ [0,1)-> [1,2)-> [2,3)-> [3,4)->
+ [00101100][11001011][11101001][11100000]
+o [111 11111111 11111111 1111]
+ a b
+subdivide:
+ [first! ][mid_1] . . .[mid_n][ !last]
+ [00000111][1...1] . . .[1...1][11110000]
+``
+
+After subdividing, we perform the operation `o` as follows:
+
+# For the first bitset: Set all bits from ther starting bit (`!`)
+ to the end of the bitset to `1`. All other bits are `0`. Then
+ perform operation `o`: `_map o= ([0,1)->00000111)`
+
+# For the last bitset: Set all bits from the beginning of the bitset
+ to the ending bit (`!`) to `1`. All other bits are `0`. Then
+ perform operation `o`: `_map o= ([3,4)->11110000)`
+
+# For the range of bitsets in between the staring and ending one,
+ perform operation `o`: `_map o= ([1,3)->11111111)`
+
+The algorithm, that has been outlined and illustrated by the
+example is implemented by the private member function
+`segment_apply`. To make the combiner operation a variable
+in this algorithm, we use a /pointer to member function type/
+
+[large_bitset_segment_modifier]
+
+as first function argument. We will pass member functions `combine_` here,
+``
+combine_(first_of_interval, end_of_interval, some_bitset);
+``
+that take the beginning and ending of an interval and a bitset and combine
+them to the implementing `interval_bitmap_type _map`. Here are these functions:
+
+[large_bitmap_combiners]
+
+Finally we can code function `segment_apply`, that does the partitioning
+and subsequent combining:
+
+[large_bitset_segment_apply]
+
+The functions that help filling bitsets to and from a given bit are
+implemented here:
+[large_bitset_bitset_filler]
+
+This completes the implementation of class template `large_bitset`.
+Using only a small amount of mostly schematic code,
+we have been able to provide a pretty powerful, self compressing
+and generally usable set type for all
+unsigned integral domain types.
+
+[endsect][/ large_bitset: Private implementation]
+
+[endsect][/ Implementation of a large bitset]
+
+[endsect][/ Large Bitsets IN Projects]
+
+
+[endsect][/ Projects]
+
+
+
Added: sandbox/itl/libs/itl/example/large_bitset_/bits.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/libs/itl/example/large_bitset_/bits.hpp 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -0,0 +1,65 @@
+/*-----------------------------------------------------------------------------+
+Author: Joachim Faulhaber
+Copyright (c) 2009-2009: Joachim Faulhaber
++------------------------------------------------------------------------------+
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENCE.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
++-----------------------------------------------------------------------------*/
+#ifndef BOOST_LIBS_ITL_EXAMPLE_LARGE_BITSET_BITS_HPP_JOFA_091019
+#define BOOST_LIBS_ITL_EXAMPLE_LARGE_BITSET_BITS_HPP_JOFA_091019
+//[mini_bits_includes
+ // These includes are needed ...
+#include <string> // for conversion to output
+#include <boost/itl/type_traits/is_set.hpp> // to define that bits is a set
+//]
+
+namespace mini
+{
+//[mini_bits_class_bits
+template<class NaturalT> class bits
+{
+public:
+ typedef NaturalT chunk_type;
+ BOOST_STATIC_CONSTANT( int, bit_count = CHAR_BIT*sizeof(NaturalT) );
+ BOOST_STATIC_CONSTANT( NaturalT, n1 = static_cast<NaturalT>(1) );
+
+ bits():_bits(){}
+ explicit bits(NaturalT value):_bits(value){}
+
+ NaturalT number()const{ return _bits; }
+ bits& operator |= (const bits& value){_bits |= value._bits; return *this;}
+ bits& operator &= (const bits& value){_bits &= value._bits; return *this;}
+ bits& operator ^= (const bits& value){_bits ^= value._bits; return *this;}
+ bits operator ~ ()const { return bits(~_bits); }
+ bool operator < (const bits& value)const{return _bits < value._bits;}
+ bool operator == (const bits& value)const{return _bits == value._bits;}
+
+ bool contains(NaturalT element)const{ return ((n1 << element) & _bits) != 0; }
+ std::string as_string(const char off_on[2] = " 1")const;
+
+private:
+ NaturalT _bits;
+};
+//]
+
+template<class NaturalT>
+std::string bits<NaturalT>::as_string(const char off_on[2])const
+{
+ std::string sequence;
+ for(int bit=0; bit < bit_count; bit++)
+ sequence += contains(bit) ? off_on[1] : off_on[0];
+ return sequence;
+}
+
+//[mini_bits_is_set
+template<class NaturalT>
+struct boost::itl::is_set<mini::bits<NaturalT> >
+{
+ typedef boost::itl::is_set<mini::bits<NaturalT> > type;
+ BOOST_STATIC_CONSTANT(bool, value = true);
+};
+//]
+
+} // mini
+#endif
Added: sandbox/itl/libs/itl/example/large_bitset_/large_bitset.cpp
==============================================================================
--- (empty file)
+++ sandbox/itl/libs/itl/example/large_bitset_/large_bitset.cpp 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -0,0 +1,140 @@
+/*-----------------------------------------------------------------------------+
+Author: Joachim Faulhaber
+Copyright (c) 2009-2009: Joachim Faulhaber
++------------------------------------------------------------------------------+
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENCE.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
++-----------------------------------------------------------------------------*/
+/** Example large_bitset.cpp \file large_bitset.cpp
+
+ \include large_bitset_/large_bitset.cpp
+*/
+
+//[large_bitset_cpp_includes
+#include <limits>
+#include "large_bitset.hpp"
+
+using namespace std;
+using namespace boost;
+using namespace boost::itl;
+using namespace mini;
+//]
+
+
+//[large_bitset_test_large_set_all
+void test_large()
+{
+ const nat3 much = 0xffffffffffffffffull; // BTW nat3 is defined as boost::uint64_t
+ // in large_bitset.hpp
+ large_bitset<> venti; // ... the largest, I can think of ;)
+ venti += interval<nat3>(0, much);
+
+ cout << "----- Test function test_large() -----------------------------------------------\n";
+ cout << "We have just turned on the awesome amount of 18,446,744,073,709,551,615 bits ;-)\n";
+ venti.show_segments();
+ //]
+
+ //[large_bitset_test_large_erase_last
+ cout << "---- Let's swich off the very last bit -----------------------------------------\n";
+ venti -= much;
+ venti.show_segments();
+
+ cout << "---- Venti is plenty ... let's do something small: A tall ----------------------\n\n";
+}
+//]
+
+//[large_bitset_test_small
+void test_small()
+{
+ large_bitset<nat, bits8> tall; // small is tall ...
+ // ... it really is, because even this 'small' large_bitset
+ // can represent up to 2^32-1 == 4,294,967,295 bits.
+
+ cout << "----- Test function test_small() -----------\n";
+ cout << "-- Switch on all bits in range [0,64] ------\n";
+ tall += interval<nat>(0, 64);
+ tall.show_segments();
+ cout << "--------------------------------------------\n";
+
+ cout << "-- Turn off bits: 25,27,28 -----------------\n";
+ (((tall -= 25) -= 27) -= 28) ;
+ tall.show_segments();
+ cout << "--------------------------------------------\n";
+
+ cout << "-- Flip bits in range [24,30) --------------\n";
+ tall ^= interval<nat>::rightopen(24,30);
+ tall.show_segments();
+ cout << "--------------------------------------------\n";
+
+ cout << "-- Remove the first 10 bits ----------------\n";
+ tall -= interval<nat>::rightopen(0,10);
+ tall.show_segments();
+ cout << "--------------------------------------------\n\n";
+}
+//]
+
+//[large_bitset_test_picturesque
+void test_picturesque()
+{
+ typedef large_bitset<nat, bits8> Bit8Set;
+
+ Bit8Set square, stare;
+ square += interval<nat>(0,7);
+ for(int i=1; i<5; i++)
+ {
+ square += 8*i;
+ square += 8*i+7;
+ }
+
+ square += interval<nat>(41,46);
+
+ cout << "----- Test function test_picturesque() -----\n";
+ cout << "-------- empty face: "
+ << square.interval_count() << " intervals -----\n";
+ square.show_matrix(" *");
+
+ stare += 18; stare += 21;
+ stare += interval<nat>(34,37);
+
+ cout << "-------- compressed smile: "
+ << stare.interval_count() << " intervals -----\n";
+ stare.show_matrix(" *");
+
+ cout << "-------- staring bitset: "
+ << (square + stare).interval_count() << " intervals -----\n";
+ (square + stare).show_matrix(" *");
+
+ cout << "--------------------------------------------\n";
+}
+//]
+
+template<class NatT, class BitsT>
+void test_set()
+{
+ const NatT much = (numeric_limits<NatT>::max)();
+
+ large_bitset<NatT, BitsT> venti; //the largest, I can think of
+ venti += interval<NatT>(0, much);
+
+ cout << "--------------------------------------------------------------------------------\n";
+ venti.show_segments();
+
+ venti -= much;
+ cout << "--------------------------------------------------------------------------------\n";
+ venti.show_segments();
+}
+
+
+
+int main()
+{
+ cout << ">> Interval Template Library: Sample large_bitset.cpp <<\n";
+ cout << "--------------------------------------------------------\n";
+ test_large();
+ test_small();
+ test_picturesque();
+ //test_set<nat3,bits64>();
+ return 0;
+}
+
Added: sandbox/itl/libs/itl/example/large_bitset_/large_bitset.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/libs/itl/example/large_bitset_/large_bitset.hpp 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -0,0 +1,225 @@
+/*-----------------------------------------------------------------------------+
+Author: Joachim Faulhaber
+Copyright (c) 2009-2009: Joachim Faulhaber
++------------------------------------------------------------------------------+
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENCE.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
++-----------------------------------------------------------------------------*/
+#ifndef BOOST_LIBS_ITL_EXAMPLE_LARGE_BITSET__LARGE_BITSET_HPP_JOFA_091019
+#define BOOST_LIBS_ITL_EXAMPLE_LARGE_BITSET__LARGE_BITSET_HPP_JOFA_091019
+//[large_bitset_includes
+#include <iostream> // to organize output
+#include <boost/cstdint.hpp> // portable long integers
+#include <boost/operators.hpp> // to define operators with minimal effort
+#include "bits.hpp" // a minimal bitset implementation
+#include "meta_log.hpp" // a meta logarithm
+#include <boost/itl/interval_map.hpp> // base of large bitsets
+
+namespace mini // minimal implementations for example projects
+{
+//]
+
+//[large_bitset_natural_typedefs
+typedef unsigned int nat;
+typedef unsigned char nat0; // nati i: number of duplications of a byte
+typedef unsigned short nat1;
+typedef unsigned long nat2;
+typedef boost::uint64_t nat3;
+
+typedef bits<nat0> bits8;
+typedef bits<nat1> bits16;
+typedef bits<nat2> bits32;
+typedef bits<nat3> bits64;
+//]
+
+//[large_bitset_class_template_header
+template
+<
+ typename DomainT = nat3,
+ typename BitSetT = mini::bits<nat3>,
+ ITL_COMPARE Compare = ITL_COMPARE_INSTANCE(std::less, DomainT),
+ template<class, ITL_COMPARE>class Interval = boost::itl::interval,
+ ITL_ALLOC Alloc = std::allocator
+>
+class large_bitset
+ : boost::equality_comparable < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>
+ , boost::less_than_comparable< large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>
+
+ , boost::addable < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>
+ , boost::orable < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>
+ , boost::subtractable < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>
+ , boost::andable < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>
+ , boost::xorable < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>
+
+ , boost::addable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, DomainT
+ , boost::orable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, DomainT
+ , boost::subtractable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, DomainT
+ , boost::andable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, DomainT
+ , boost::xorable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, DomainT
+
+ , boost::addable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, Interval<DomainT,Compare>
+ , boost::orable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, Interval<DomainT,Compare>
+ , boost::subtractable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, Interval<DomainT,Compare>
+ , boost::andable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, Interval<DomainT,Compare>
+ , boost::xorable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, Interval<DomainT,Compare>
+ > > > > > > > > > > > > > > > > >
+ //^ & - | + ^ & - | + ^ & - | + < ==
+ //segment element container
+//]
+{
+public:
+ //[large_bitset_associated_types
+ typedef boost::itl::interval_map
+ <DomainT, BitSetT, boost::itl::partial_absorber,
+ std::less, boost::itl::inplace_bit_add, boost::itl::inplace_bit_and> interval_bitmap_type;
+
+ typedef DomainT domain_type;
+ typedef DomainT element_type;
+ typedef BitSetT bitset_type;
+ typedef typename BitSetT::chunk_type chunk_type;
+ typedef typename interval_bitmap_type::interval_type interval_type;
+ typedef typename interval_bitmap_type::value_type value_type;
+ //]
+//[large_bitset_operators
+public:
+ bool operator ==(const large_bitset& rhs) { return _map == rhs._map; }
+ bool operator < (const large_bitset& rhs) { return _map < rhs._map; }
+
+ large_bitset& operator +=(const large_bitset& rhs) {_map += rhs._map; return *this;}
+ large_bitset& operator |=(const large_bitset& rhs) {_map |= rhs._map; return *this;}
+ large_bitset& operator -=(const large_bitset& rhs) {_map -= rhs._map; return *this;}
+ large_bitset& operator &=(const large_bitset& rhs) {_map &= rhs._map; return *this;}
+ large_bitset& operator ^=(const large_bitset& rhs) {_map ^= rhs._map; return *this;}
+
+ large_bitset& operator +=(const element_type& rhs) {return add(interval_type(rhs, rhs)); }
+ large_bitset& operator |=(const element_type& rhs) {return add(interval_type(rhs, rhs)); }
+ large_bitset& operator -=(const element_type& rhs) {return subtract(interval_type(rhs, rhs)); }
+ large_bitset& operator &=(const element_type& rhs) {return intersect(interval_type(rhs, rhs));}
+ large_bitset& operator ^=(const element_type& rhs) {return flip(interval_type(rhs, rhs)); }
+
+ large_bitset& operator +=(const interval_type& rhs){return add(rhs); }
+ large_bitset& operator |=(const interval_type& rhs){return add(rhs); }
+ large_bitset& operator -=(const interval_type& rhs){return subtract(rhs); }
+ large_bitset& operator &=(const interval_type& rhs){return intersect(rhs);}
+ large_bitset& operator ^=(const interval_type& rhs){return flip(rhs); }
+ //]
+ //[large_bitset_fundamental_functions
+ large_bitset& add (const interval_type& rhs){return segment_apply(&large_bitset::add_, rhs);}
+ large_bitset& subtract (const interval_type& rhs){return segment_apply(&large_bitset::subtract_, rhs);}
+ large_bitset& intersect(const interval_type& rhs){return segment_apply(&large_bitset::intersect_,rhs);}
+ large_bitset& flip (const interval_type& rhs){return segment_apply(&large_bitset::flip_, rhs);}
+ //]
+
+ //[large_bitset_demo_functions
+ size_t interval_count()const { return _map.interval_count(); }
+
+ void show_segments()const
+ {
+ ITL_const_FORALL(interval_bitmap_type, it_, _map)
+ {
+ interval_type itv = it_->first;
+ bitset_type bits = it_->second;
+ cout << itv << "->" << bits.as_string("01") << endl;
+ }
+ }
+
+ void show_matrix(const char off_on[2] = " 1")const
+ {
+ interval_bitmap_type::const_iterator iter = _map.begin();
+ while(iter != _map.end())
+ {
+ element_type fst = iter->first.first(), lst = iter->first.last();
+ for(element_type chunk = fst; chunk <= lst; chunk++)
+ std::cout << iter->second.as_string(off_on) << endl;
+ ++iter;
+ }
+ }
+ //]
+
+//[large_bitset_impl_constants
+private:
+ BOOST_STATIC_CONSTANT( chunk_type, bit_count = (sizeof chunk_type)*CHAR_BIT );
+ BOOST_STATIC_CONSTANT( chunk_type, divisor = bit_count );
+ BOOST_STATIC_CONSTANT( chunk_type, shift = log2_<divisor>::value );
+ BOOST_STATIC_CONSTANT( chunk_type, c1 = static_cast<chunk_type>(1) );
+ BOOST_STATIC_CONSTANT( chunk_type, mask = divisor - c1 );
+ BOOST_STATIC_CONSTANT( chunk_type, all = ~static_cast<chunk_type>(0) );
+ BOOST_STATIC_CONSTANT( chunk_type, top = c1 << (bit_count-c1) );
+ //]
+ //[large_bitset_segment_modifier
+ typedef void (large_bitset::*segment_modifier)(element_type, element_type, bitset_type);
+ //]
+
+ //[large_bitset_bitset_filler
+ chunk_type from_lower_to(chunk_type bit){return bit==bit_count-c1 ? all : (1<<(bit+1))-1;}
+ chunk_type to_upper_from(chunk_type bit){return bit==bit_count-c1 ? top : ~((1<<bit)-1); }
+ //]
+
+ //[large_bitset_segment_apply
+ large_bitset& segment_apply(segment_modifier modify, const interval_type& operand)
+ {
+ // Binary division: [base, ceil] == [first/divisor, last/divisor]
+ element_type base = operand.first() >> shift;
+ element_type ceil = operand.last() >> shift;
+ // Binary modulo: [base_rest, ceil_rest] == [first%divisor, last%divisor]
+ element_type base_rest = operand.first() & mask;
+ element_type ceil_rest = operand.last() & mask;
+
+ if(base == ceil) // [first, last] are within one bitset (chunk)
+ {
+ //CL dbg_shift(base_rest, ceil_rest);
+ (this->*modify)(base, base+1, bitset_type( to_upper_from(base_rest)
+ & from_lower_to(ceil_rest)));
+ }
+ else // [first, last] spread over more than one bitset (chunk)
+ {
+ element_type lower, upper;
+
+ if(base_rest == 0)
+ lower = base;
+ else
+ {
+ (this->*modify)(base, base+1, bitset_type(to_upper_from(base_rest)));
+ lower = base+1;
+ }
+
+ if(ceil_rest == 0)
+ upper = ceil+1;
+ else
+ {
+ (this->*modify)(ceil, ceil+1, bitset_type(from_lower_to(ceil_rest)));
+ upper = ceil;
+ }
+
+ if(lower < upper)
+ (this->*modify)(lower, upper, bitset_type(all));
+ }
+ return *this;
+ }
+ //]
+
+ //[large_bitmap_combiners
+ void add_(element_type lower, element_type upper, bitset_type bits)
+ { _map += value_type(interval_type::rightopen(lower, upper), bits); }
+
+ void subtract_(element_type lower, element_type upper, bitset_type bits)
+ { _map -= value_type(interval_type::rightopen(lower, upper), bits); }
+
+ void intersect_(element_type lower, element_type upper, bitset_type bits)
+ { _map &= value_type(interval_type::rightopen(lower, upper), bits); }
+
+ void flip_(element_type lower, element_type upper, bitset_type bits)
+ { _map ^= value_type(interval_type::rightopen(lower, upper), bits); }
+ //]
+
+//[large_bitmap_impl_map
+private:
+ interval_bitmap_type _map;
+//]
+};
+
+} // mini
+#endif
+
+
Added: sandbox/itl/libs/itl/example/large_bitset_/meta_log.hpp
==============================================================================
--- (empty file)
+++ sandbox/itl/libs/itl/example/large_bitset_/meta_log.hpp 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -0,0 +1,26 @@
+/*-----------------------------------------------------------------------------+
+Author: Joachim Faulhaber
+Copyright (c) 2009-2009: Joachim Faulhaber
++------------------------------------------------------------------------------+
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENCE.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
++-----------------------------------------------------------------------------*/
+
+namespace mini // minimal implementations for example projects
+{
+// A meta implementation of an the logarithm function on integrals
+template <size_t Argument, size_t Base=2>
+struct log_{ enum { value = 1 + log_<Argument/Base, Base>::value }; };
+
+template <size_t Base>struct log_<1, Base>{ enum { value = 0 }; };
+template <size_t Base>struct log_<0, Base>{ enum { value = 0 }; };
+
+template <size_t Argument>
+struct log2_{ enum { value = log_<Argument, 2>::value }; };
+
+template <size_t Argument>
+struct power2_{ enum { value = 1 << Argument }; };
+
+} // namespace mini
+
Added: sandbox/itl/libs/itl/example/large_bitset_/vc9_large_bitset.vcproj
==============================================================================
--- (empty file)
+++ sandbox/itl/libs/itl/example/large_bitset_/vc9_large_bitset.vcproj 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -0,0 +1,212 @@
+<?xml version="1.0" encoding="Windows-1252"?>
+<VisualStudioProject
+ ProjectType="Visual C++"
+ Version="9,00"
+ Name="vc9_large_bitset"
+ ProjectGUID="{6BE62DDE-21B9-4333-BF11-AA054DD53759}"
+ RootNamespace="Large_bitset"
+ Keyword="Win32Proj"
+ TargetFrameworkVersion="131072"
+ >
+ <Platforms>
+ <Platform
+ Name="Win32"
+ />
+ </Platforms>
+ <ToolFiles>
+ </ToolFiles>
+ <Configurations>
+ <Configuration
+ Name="Debug|Win32"
+ OutputDirectory="../../../../bin/debug/"
+ IntermediateDirectory="../../../../bin/obj/$(ProjectName)/debug/"
+ ConfigurationType="1"
+ CharacterSet="1"
+ >
+ <Tool
+ Name="VCPreBuildEventTool"
+ />
+ <Tool
+ Name="VCCustomBuildTool"
+ />
+ <Tool
+ Name="VCXMLDataGeneratorTool"
+ />
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"
+ />
+ <Tool
+ Name="VCMIDLTool"
+ />
+ <Tool
+ Name="VCCLCompilerTool"
+ Optimization="0"
+ AdditionalIncludeDirectories="../../../../; ../../../../boost_1_35_0"
+ PreprocessorDefinitions="WIN32;_DEBUG;_CONSOLE"
+ MinimalRebuild="true"
+ BasicRuntimeChecks="3"
+ RuntimeLibrary="3"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="false"
+ DebugInformationFormat="4"
+ />
+ <Tool
+ Name="VCManagedResourceCompilerTool"
+ />
+ <Tool
+ Name="VCResourceCompilerTool"
+ />
+ <Tool
+ Name="VCPreLinkEventTool"
+ />
+ <Tool
+ Name="VCLinkerTool"
+ UseUnicodeResponseFiles="true"
+ OutputFile="../../../../bin/debug/$(ProjectName).exe"
+ LinkIncremental="2"
+ AdditionalLibraryDirectories="../../../../lib;../../boost_1_35_0/lib"
+ IgnoreAllDefaultLibraries="false"
+ GenerateDebugInformation="true"
+ AssemblyDebug="1"
+ SubSystem="1"
+ RandomizedBaseAddress="1"
+ DataExecutionPrevention="0"
+ TargetMachine="1"
+ />
+ <Tool
+ Name="VCALinkTool"
+ />
+ <Tool
+ Name="VCManifestTool"
+ UseUnicodeResponseFiles="true"
+ />
+ <Tool
+ Name="VCXDCMakeTool"
+ />
+ <Tool
+ Name="VCBscMakeTool"
+ />
+ <Tool
+ Name="VCFxCopTool"
+ />
+ <Tool
+ Name="VCAppVerifierTool"
+ />
+ <Tool
+ Name="VCPostBuildEventTool"
+ />
+ </Configuration>
+ <Configuration
+ Name="Release|Win32"
+ OutputDirectory="../../../../bin/release/"
+ IntermediateDirectory="../../../../bin/obj/$(ProjectName)/release/"
+ ConfigurationType="1"
+ CharacterSet="1"
+ WholeProgramOptimization="1"
+ >
+ <Tool
+ Name="VCPreBuildEventTool"
+ />
+ <Tool
+ Name="VCCustomBuildTool"
+ />
+ <Tool
+ Name="VCXMLDataGeneratorTool"
+ />
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"
+ />
+ <Tool
+ Name="VCMIDLTool"
+ />
+ <Tool
+ Name="VCCLCompilerTool"
+ AdditionalIncludeDirectories="../../../../; ../../../../boost_1_35_0"
+ PreprocessorDefinitions="WIN32;NDEBUG;_CONSOLE"
+ RuntimeLibrary="2"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="false"
+ DebugInformationFormat="3"
+ />
+ <Tool
+ Name="VCManagedResourceCompilerTool"
+ />
+ <Tool
+ Name="VCResourceCompilerTool"
+ />
+ <Tool
+ Name="VCPreLinkEventTool"
+ />
+ <Tool
+ Name="VCLinkerTool"
+ UseUnicodeResponseFiles="false"
+ OutputFile="../../../../bin/release/$(ProjectName).exe"
+ LinkIncremental="1"
+ AdditionalLibraryDirectories="../../../../lib;../../boost_1_35_0/lib"
+ IgnoreAllDefaultLibraries="false"
+ GenerateDebugInformation="true"
+ SubSystem="1"
+ OptimizeReferences="2"
+ EnableCOMDATFolding="2"
+ RandomizedBaseAddress="1"
+ DataExecutionPrevention="0"
+ TargetMachine="1"
+ />
+ <Tool
+ Name="VCALinkTool"
+ />
+ <Tool
+ Name="VCManifestTool"
+ />
+ <Tool
+ Name="VCXDCMakeTool"
+ />
+ <Tool
+ Name="VCBscMakeTool"
+ />
+ <Tool
+ Name="VCFxCopTool"
+ />
+ <Tool
+ Name="VCAppVerifierTool"
+ />
+ <Tool
+ Name="VCPostBuildEventTool"
+ />
+ </Configuration>
+ </Configurations>
+ <References>
+ </References>
+ <Files>
+ <Filter
+ Name="Quelldateien"
+ Filter="cpp;c;cc;cxx;def;odl;idl;hpj;bat;asm;asmx"
+ UniqueIdentifier="{4FC737F1-C7A5-4376-A066-2A32D752A2FF}"
+ >
+ <File
+ RelativePath=".\large_bitset.cpp"
+ >
+ </File>
+ </Filter>
+ <Filter
+ Name="Headerdateien"
+ Filter="h;hpp;hxx;hm;inl;inc;xsd"
+ UniqueIdentifier="{93995380-89BD-4b04-88EB-625FBE52EBFB}"
+ >
+ <File
+ RelativePath="..\..\..\..\boost\itl\interval_map.hpp"
+ >
+ </File>
+ </Filter>
+ <Filter
+ Name="Ressourcendateien"
+ Filter="rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx;tiff;tif;png;wav"
+ UniqueIdentifier="{67DA6AB6-F800-4c08-8B7A-83BB121AAD01}"
+ >
+ </Filter>
+ </Files>
+ <Globals>
+ </Globals>
+</VisualStudioProject>
Added: sandbox/itl/libs/itl/example/std_copy_/std_copy.cpp
==============================================================================
--- (empty file)
+++ sandbox/itl/libs/itl/example/std_copy_/std_copy.cpp 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -0,0 +1,106 @@
+/*-----------------------------------------------------------------------------+
+Interval Template Library
+Author: Joachim Faulhaber
+Copyright (c) 2007-2009: Joachim Faulhaber
+Copyright (c) 1999-2006: Cortex Software GmbH, Kantstrasse 57, Berlin
++------------------------------------------------------------------------------+
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENCE.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
++-----------------------------------------------------------------------------*/
+/** Example std_copy.cpp \file std_copy.cpp
+
+ Example std_copy shows how algorithm std::copy can be used to
+ fill interval containers from other std::containers and how copying
+ to interval containers differs from other uses of std::copy.
+
+ \include std_copy_/std_copy.cpp
+*/
+//[example_std_copy
+#include <iostream>
+#include <vector>
+#include <algorithm>
+#include <boost/itl/interval_map.hpp>
+#include <boost/itl/iterator.hpp> // needed for itl::inserter and
+ // itl::adder.
+
+using namespace std;
+using namespace boost;
+using namespace boost::itl;
+
+// 'make_segments' returns a vector of interval value pairs, which
+// are not sorted. The values are taken from the minimal example
+// in section 'interval combining styles'.
+vector<pair<interval<int>, int> > make_segments()
+{
+ vector<pair<interval<int>, int> > segment_vec;
+ segment_vec.push_back(make_pair(interval<int>::rightopen(2,4), 1));
+ segment_vec.push_back(make_pair(interval<int>::rightopen(4,5), 1));
+ segment_vec.push_back(make_pair(interval<int>::rightopen(1,3), 1));
+ return segment_vec;
+}
+
+// 'show_segments' displays the source segements.
+void show_segments(const vector<pair<interval<int>, int> >& segments)
+{
+ vector<pair<interval<int>, int> >::const_iterator iter = segments.begin();
+ while(iter != segments.end())
+ {
+ cout << "(" << iter->first << "," << iter->second << ")";
+ ++iter;
+ }
+}
+
+void std_copy()
+{
+ // So we have some segments stored in an std container.
+ vector<pair<interval<int>, int> > segments = make_segments();
+ // Display the input
+ cout << "input sequence: "; show_segments(segments); cout << "\n\n";
+
+ // We are going to 'std::copy' those segments into an interval_map:
+ interval_map<int,int> segmap;
+
+ // Use an 'itl::inserter' from <boost/itl/interator.hpp> to call
+ // insertion on the interval container.
+ std::copy(segments.begin(), segments.end(),
+ itl::inserter(segmap, segmap.end()));
+ cout << "itl::inserting: " << segmap << endl;
+ segmap.clear();
+
+ // When we are feeding data into interval_maps, most of the time we are
+ // intending to compute an aggregation result. So we are not interested
+ // the std::insert semantincs but the aggregating itl::addition semantics.
+ // To achieve this there is an itl::add_iterator and an itl::adder function
+ // provided in <boost/itl/interator.hpp>.
+ std::copy(segments.begin(), segments.end(),
+ itl::adder(segmap, segmap.end())); //Aggregating associated values
+ cout << "itl::adding : " << segmap << endl;
+
+ // In this last case, the semantics of 'std::copy' transforms to the
+ // generalized addition operation, that is implemented by operator
+ // += or + on itl maps and sets.
+}
+
+int main()
+{
+ cout << ">> Interval Template Library: Example std_copy.cpp <<\n";
+ cout << "-----------------------------------------------------------\n";
+ cout << "Using std::copy to fill an interval_map:\n\n";
+
+ std_copy();
+ return 0;
+}
+
+// Program output:
+/*---------------------------------------------------------
+>> Interval Template Library: Example std_copy.cpp <<
+-----------------------------------------------------------
+Using std::copy to fill an interval_map:
+
+input sequence: ([2,4),1)([4,5),1)([1,3),1)
+
+itl::inserting: {([1,5)->1)}
+itl::adding : {([1,2)->1)([2,3)->2)([3,5)->1)}
+---------------------------------------------------------*/
+//]
Added: sandbox/itl/libs/itl/example/std_copy_/vc9_std_copy.vcproj
==============================================================================
--- (empty file)
+++ sandbox/itl/libs/itl/example/std_copy_/vc9_std_copy.vcproj 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -0,0 +1,210 @@
+<?xml version="1.0" encoding="Windows-1252"?>
+<VisualStudioProject
+ ProjectType="Visual C++"
+ Version="9,00"
+ Name="vc9_std_copy"
+ ProjectGUID="{8DC9BDE4-E5A4-4294-A12F-D75FD6990B84}"
+ RootNamespace="std_copy"
+ Keyword="Win32Proj"
+ TargetFrameworkVersion="131072"
+ >
+ <Platforms>
+ <Platform
+ Name="Win32"
+ />
+ </Platforms>
+ <ToolFiles>
+ </ToolFiles>
+ <Configurations>
+ <Configuration
+ Name="Debug|Win32"
+ OutputDirectory="../../../../bin/debug/"
+ IntermediateDirectory="../../../../bin/obj/$(ProjectName)/debug/"
+ ConfigurationType="1"
+ CharacterSet="1"
+ >
+ <Tool
+ Name="VCPreBuildEventTool"
+ />
+ <Tool
+ Name="VCCustomBuildTool"
+ />
+ <Tool
+ Name="VCXMLDataGeneratorTool"
+ />
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"
+ />
+ <Tool
+ Name="VCMIDLTool"
+ />
+ <Tool
+ Name="VCCLCompilerTool"
+ Optimization="0"
+ AdditionalIncludeDirectories="../../../../; ../../../../boost_1_35_0"
+ PreprocessorDefinitions="WIN32;_DEBUG;_CONSOLE"
+ MinimalRebuild="true"
+ BasicRuntimeChecks="3"
+ RuntimeLibrary="3"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="false"
+ DebugInformationFormat="4"
+ />
+ <Tool
+ Name="VCManagedResourceCompilerTool"
+ />
+ <Tool
+ Name="VCResourceCompilerTool"
+ />
+ <Tool
+ Name="VCPreLinkEventTool"
+ />
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="../../../../bin/debug/$(ProjectName).exe"
+ LinkIncremental="2"
+ AdditionalLibraryDirectories="../../../../lib"
+ GenerateDebugInformation="true"
+ SubSystem="1"
+ RandomizedBaseAddress="1"
+ DataExecutionPrevention="0"
+ TargetMachine="1"
+ />
+ <Tool
+ Name="VCALinkTool"
+ />
+ <Tool
+ Name="VCManifestTool"
+ />
+ <Tool
+ Name="VCXDCMakeTool"
+ />
+ <Tool
+ Name="VCBscMakeTool"
+ />
+ <Tool
+ Name="VCFxCopTool"
+ />
+ <Tool
+ Name="VCAppVerifierTool"
+ />
+ <Tool
+ Name="VCPostBuildEventTool"
+ />
+ </Configuration>
+ <Configuration
+ Name="Release|Win32"
+ OutputDirectory="../../../../bin/release/"
+ IntermediateDirectory="../../../../bin/obj/$(ProjectName)/release/"
+ ConfigurationType="1"
+ CharacterSet="1"
+ WholeProgramOptimization="1"
+ >
+ <Tool
+ Name="VCPreBuildEventTool"
+ />
+ <Tool
+ Name="VCCustomBuildTool"
+ />
+ <Tool
+ Name="VCXMLDataGeneratorTool"
+ />
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"
+ />
+ <Tool
+ Name="VCMIDLTool"
+ />
+ <Tool
+ Name="VCCLCompilerTool"
+ AdditionalIncludeDirectories="../../../../; ../../../../boost_1_35_0"
+ PreprocessorDefinitions="WIN32;NDEBUG;_CONSOLE"
+ RuntimeLibrary="2"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="false"
+ DebugInformationFormat="3"
+ />
+ <Tool
+ Name="VCManagedResourceCompilerTool"
+ />
+ <Tool
+ Name="VCResourceCompilerTool"
+ />
+ <Tool
+ Name="VCPreLinkEventTool"
+ />
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="../../../../bin/release/$(ProjectName).exe"
+ LinkIncremental="1"
+ AdditionalLibraryDirectories="../../../../lib"
+ GenerateDebugInformation="true"
+ SubSystem="1"
+ OptimizeReferences="2"
+ EnableCOMDATFolding="2"
+ RandomizedBaseAddress="1"
+ DataExecutionPrevention="0"
+ TargetMachine="1"
+ />
+ <Tool
+ Name="VCALinkTool"
+ />
+ <Tool
+ Name="VCManifestTool"
+ />
+ <Tool
+ Name="VCXDCMakeTool"
+ />
+ <Tool
+ Name="VCBscMakeTool"
+ />
+ <Tool
+ Name="VCFxCopTool"
+ />
+ <Tool
+ Name="VCAppVerifierTool"
+ />
+ <Tool
+ Name="VCPostBuildEventTool"
+ />
+ </Configuration>
+ </Configurations>
+ <References>
+ </References>
+ <Files>
+ <Filter
+ Name="Quelldateien"
+ Filter="cpp;c;cc;cxx;def;odl;idl;hpj;bat;asm;asmx"
+ UniqueIdentifier="{4FC737F1-C7A5-4376-A066-2A32D752A2FF}"
+ >
+ <File
+ RelativePath=".\std_copy.cpp"
+ >
+ </File>
+ </Filter>
+ <Filter
+ Name="Headerdateien"
+ Filter="h;hpp;hxx;hm;inl;inc;xsd"
+ UniqueIdentifier="{93995380-89BD-4b04-88EB-625FBE52EBFB}"
+ >
+ <File
+ RelativePath="..\..\..\..\boost\itl\interval.hpp"
+ >
+ </File>
+ <File
+ RelativePath="..\..\..\..\boost\itl\interval_map.hpp"
+ >
+ </File>
+ </Filter>
+ <Filter
+ Name="Ressourcendateien"
+ Filter="rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx;tiff;tif;png;wav"
+ UniqueIdentifier="{67DA6AB6-F800-4c08-8B7A-83BB121AAD01}"
+ >
+ </Filter>
+ </Files>
+ <Globals>
+ </Globals>
+</VisualStudioProject>
Added: sandbox/itl/libs/itl/example/std_transform_/std_transform.cpp
==============================================================================
--- (empty file)
+++ sandbox/itl/libs/itl/example/std_transform_/std_transform.cpp 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -0,0 +1,150 @@
+/*-----------------------------------------------------------------------------+
+Interval Template Library
+Author: Joachim Faulhaber
+Copyright (c) 2007-2009: Joachim Faulhaber
+Copyright (c) 1999-2006: Cortex Software GmbH, Kantstrasse 57, Berlin
++------------------------------------------------------------------------------+
+ Distributed under the Boost Software License, Version 1.0.
+ (See accompanying file LICENCE.txt or copy at
+ http://www.boost.org/LICENSE_1_0.txt)
++-----------------------------------------------------------------------------*/
+/** Example std_transform.cpp \file std_transform.cpp
+
+ Example std_transform shows how algorithm std::transform can be used to
+ fill interval containers from std::containers of objects of a user
+ defined class.
+
+ \include std_transform_/std_transform.cpp
+*/
+//[example_std_transform
+#include <iostream>
+#include <vector>
+#include <algorithm>
+#include <boost/itl/split_interval_map.hpp>
+#include <boost/itl/separate_interval_set.hpp>
+#include <boost/itl/iterator.hpp> // needed for itl::inserter and
+ // itl::adder.
+
+using namespace std;
+using namespace boost;
+using namespace boost::itl;
+
+// Suppose we are working with a class called MyObject, containing some
+// information about interval bounds e.g. _from, _to and some data members
+// that carry associated information like e.g. _value.
+class MyObject
+{
+public:
+ MyObject(){}
+ MyObject(int from, int to, int value): _from(from), _to(to), _value(value){}
+ int from()const {return _from;}
+ int to()const {return _to;}
+ int value()const{return _value;}
+private:
+ int _from;
+ int _to;
+ int _value;
+};
+
+// ... in order to use the std::transform algorithm to fill
+// interval maps with MyObject data we need a function
+// 'to_segment' that maps an object of type MyObject into
+// the value type to the interval map we want to tranform to ...
+pair<interval<int>, int> to_segment(const MyObject& myObj)
+{
+ return std::pair< interval<int>, int >
+ (interval<int>::closed(myObj.from(), myObj.to()), myObj.value());
+}
+
+// ... there may be another function that returns the interval
+// of an object only
+interval<int> to_interval(const MyObject& myObj)
+{
+ return interval<int>::closed(myObj.from(), myObj.to());
+}
+
+
+// ... make_object computes a sequence of objects to test.
+vector<MyObject> make_objects()
+{
+ vector<MyObject> object_vec;
+ object_vec.push_back(MyObject(2,3,1));
+ object_vec.push_back(MyObject(4,4,1));
+ object_vec.push_back(MyObject(1,2,1));
+ return object_vec;
+}
+
+// ... show_objects displays the sequence of input objects.
+void show_objects(const vector<MyObject>& objects)
+{
+ vector<MyObject>::const_iterator iter = objects.begin();
+ while(iter != objects.end())
+ {
+ cout << "([" << iter->from() << "," << iter->to() << "],"
+ << iter->value() << ")";
+ ++iter;
+ }
+}
+
+
+void std_transform()
+{
+ // This time we want to transform objects into a splitting interval map:
+ split_interval_map<int,int> segmap;
+ vector<MyObject> myObjects = make_objects();
+
+ // Display the input
+ cout << "input sequence: "; show_objects(myObjects); cout << "\n\n";
+
+ // Use an itl::inserter to fill the interval map via inserts
+ std::transform(myObjects.begin(), myObjects.end(),
+ itl::inserter(segmap, segmap.end()),
+ to_segment);
+ cout << "itl::inserting: " << segmap << endl;
+ segmap.clear();
+
+ // In order to compute aggregation results on associated values, we
+ // usually want to use an itl::adder instead of an std or itl::inserter
+ std::transform(myObjects.begin(), myObjects.end(),
+ itl::adder(segmap, segmap.end()),
+ to_segment);
+ cout << "itl::adding : " << segmap << "\n\n";
+
+ separate_interval_set<int> segset;
+ std::transform(myObjects.begin(), myObjects.end(),
+ itl::adder (segset, segset.end()),
+ // could be a itl::inserter(segset, segset.end()), here: same effect
+ to_interval);
+
+ cout << "Using std::transform to fill a separate_interval_set:\n\n";
+ cout << "itl::adding : " << segset << "\n\n";
+}
+
+
+int main()
+{
+ cout << ">> Interval Template Library: Example std_transform.cpp <<\n";
+ cout << "------------------------------------------------------------\n";
+ cout << "Using std::transform to fill a split_interval_map:\n\n";
+
+ std_transform();
+ return 0;
+}
+
+// Program output:
+/*----------------------------------------------------------
+>> Interval Template Library: Example std_transform.cpp <<
+------------------------------------------------------------
+Using std::transform to fill a split_interval_map:
+
+input sequence: ([2,3],1)([4,4],1)([1,2],1)
+
+itl::inserting: {([1,2)->1)([2,3]->1)([4,4]->1)}
+itl::adding : {([1,2)->1)([2,2]->2)((2,3]->1)([4,4]->1)}
+
+Using std::transform to fill a separate_interval_set:
+
+itl::adding : {[1,3][4,4]}
+----------------------------------------------------------*/
+//]
+
Added: sandbox/itl/libs/itl/example/std_transform_/vc9_std_transform.vcproj
==============================================================================
--- (empty file)
+++ sandbox/itl/libs/itl/example/std_transform_/vc9_std_transform.vcproj 2009-10-22 12:17:21 EDT (Thu, 22 Oct 2009)
@@ -0,0 +1,210 @@
+<?xml version="1.0" encoding="Windows-1252"?>
+<VisualStudioProject
+ ProjectType="Visual C++"
+ Version="9,00"
+ Name="vc9_std_transform"
+ ProjectGUID="{8DC9BDE4-E5A4-4294-A12F-D75FD6990B85}"
+ RootNamespace="std_transform"
+ Keyword="Win32Proj"
+ TargetFrameworkVersion="131072"
+ >
+ <Platforms>
+ <Platform
+ Name="Win32"
+ />
+ </Platforms>
+ <ToolFiles>
+ </ToolFiles>
+ <Configurations>
+ <Configuration
+ Name="Debug|Win32"
+ OutputDirectory="../../../../bin/debug/"
+ IntermediateDirectory="../../../../bin/obj/$(ProjectName)/debug/"
+ ConfigurationType="1"
+ CharacterSet="1"
+ >
+ <Tool
+ Name="VCPreBuildEventTool"
+ />
+ <Tool
+ Name="VCCustomBuildTool"
+ />
+ <Tool
+ Name="VCXMLDataGeneratorTool"
+ />
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"
+ />
+ <Tool
+ Name="VCMIDLTool"
+ />
+ <Tool
+ Name="VCCLCompilerTool"
+ Optimization="0"
+ AdditionalIncludeDirectories="../../../../; ../../../../boost_1_35_0"
+ PreprocessorDefinitions="WIN32;_DEBUG;_CONSOLE"
+ MinimalRebuild="true"
+ BasicRuntimeChecks="3"
+ RuntimeLibrary="3"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="false"
+ DebugInformationFormat="4"
+ />
+ <Tool
+ Name="VCManagedResourceCompilerTool"
+ />
+ <Tool
+ Name="VCResourceCompilerTool"
+ />
+ <Tool
+ Name="VCPreLinkEventTool"
+ />
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="../../../../bin/debug/$(ProjectName).exe"
+ LinkIncremental="2"
+ AdditionalLibraryDirectories="../../../../lib"
+ GenerateDebugInformation="true"
+ SubSystem="1"
+ RandomizedBaseAddress="1"
+ DataExecutionPrevention="0"
+ TargetMachine="1"
+ />
+ <Tool
+ Name="VCALinkTool"
+ />
+ <Tool
+ Name="VCManifestTool"
+ />
+ <Tool
+ Name="VCXDCMakeTool"
+ />
+ <Tool
+ Name="VCBscMakeTool"
+ />
+ <Tool
+ Name="VCFxCopTool"
+ />
+ <Tool
+ Name="VCAppVerifierTool"
+ />
+ <Tool
+ Name="VCPostBuildEventTool"
+ />
+ </Configuration>
+ <Configuration
+ Name="Release|Win32"
+ OutputDirectory="../../../../bin/release/"
+ IntermediateDirectory="../../../../bin/obj/$(ProjectName)/release/"
+ ConfigurationType="1"
+ CharacterSet="1"
+ WholeProgramOptimization="1"
+ >
+ <Tool
+ Name="VCPreBuildEventTool"
+ />
+ <Tool
+ Name="VCCustomBuildTool"
+ />
+ <Tool
+ Name="VCXMLDataGeneratorTool"
+ />
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"
+ />
+ <Tool
+ Name="VCMIDLTool"
+ />
+ <Tool
+ Name="VCCLCompilerTool"
+ AdditionalIncludeDirectories="../../../../; ../../../../boost_1_35_0"
+ PreprocessorDefinitions="WIN32;NDEBUG;_CONSOLE"
+ RuntimeLibrary="2"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="false"
+ DebugInformationFormat="3"
+ />
+ <Tool
+ Name="VCManagedResourceCompilerTool"
+ />
+ <Tool
+ Name="VCResourceCompilerTool"
+ />
+ <Tool
+ Name="VCPreLinkEventTool"
+ />
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="../../../../bin/release/$(ProjectName).exe"
+ LinkIncremental="1"
+ AdditionalLibraryDirectories="../../../../lib"
+ GenerateDebugInformation="true"
+ SubSystem="1"
+ OptimizeReferences="2"
+ EnableCOMDATFolding="2"
+ RandomizedBaseAddress="1"
+ DataExecutionPrevention="0"
+ TargetMachine="1"
+ />
+ <Tool
+ Name="VCALinkTool"
+ />
+ <Tool
+ Name="VCManifestTool"
+ />
+ <Tool
+ Name="VCXDCMakeTool"
+ />
+ <Tool
+ Name="VCBscMakeTool"
+ />
+ <Tool
+ Name="VCFxCopTool"
+ />
+ <Tool
+ Name="VCAppVerifierTool"
+ />
+ <Tool
+ Name="VCPostBuildEventTool"
+ />
+ </Configuration>
+ </Configurations>
+ <References>
+ </References>
+ <Files>
+ <Filter
+ Name="Quelldateien"
+ Filter="cpp;c;cc;cxx;def;odl;idl;hpj;bat;asm;asmx"
+ UniqueIdentifier="{4FC737F1-C7A5-4376-A066-2A32D752A2FF}"
+ >
+ <File
+ RelativePath=".\std_transform.cpp"
+ >
+ </File>
+ </Filter>
+ <Filter
+ Name="Headerdateien"
+ Filter="h;hpp;hxx;hm;inl;inc;xsd"
+ UniqueIdentifier="{93995380-89BD-4b04-88EB-625FBE52EBFB}"
+ >
+ <File
+ RelativePath="..\..\..\..\boost\itl\interval.hpp"
+ >
+ </File>
+ <File
+ RelativePath="..\..\..\..\boost\itl\interval_map.hpp"
+ >
+ </File>
+ </Filter>
+ <Filter
+ Name="Ressourcendateien"
+ Filter="rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx;tiff;tif;png;wav"
+ UniqueIdentifier="{67DA6AB6-F800-4c08-8B7A-83BB121AAD01}"
+ >
+ </Filter>
+ </Files>
+ <Globals>
+ </Globals>
+</VisualStudioProject>