Subject: [Boost-commit] svn:boost r57109 - in sandbox/itl/libs/itl: doc example/large_bitset_ example/std_copy_ example/std_transform_
From: afojgo_at_[hidden]
Date: 2009-10-23 13:29:41
Author: jofaber
Date: 2009-10-23 13:29:41 EDT (Fri, 23 Oct 2009)
New Revision: 57109
URL: http://svn.boost.org/trac/boost/changeset/57109
Log:
Refactoring: Some further simplifications for example large_bitset. Stable {msvc-8.0, 9.0; gcc-3.4.4}
Text files modified:
sandbox/itl/libs/itl/doc/projects.qbk | 28 ++----------
sandbox/itl/libs/itl/example/large_bitset_/large_bitset.hpp | 85 +++++++++++++++------------------------
sandbox/itl/libs/itl/example/std_copy_/std_copy.cpp | 2
sandbox/itl/libs/itl/example/std_transform_/std_transform.cpp | 2
4 files changed, 40 insertions(+), 77 deletions(-)
Modified: sandbox/itl/libs/itl/doc/projects.qbk
==============================================================================
--- sandbox/itl/libs/itl/doc/projects.qbk (original)
+++ sandbox/itl/libs/itl/doc/projects.qbk 2009-10-23 13:29:41 EDT (Fri, 23 Oct 2009)
@@ -293,13 +293,13 @@
[section large_bitset: Public interface][/ ------------------------------------]
-An now let's code `large_bitset`.
+And 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
+an unsigned integral type that defines the kind of numbers that can
+be elements of 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
@@ -415,26 +415,10 @@
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:
+The constants needed for those bitset computations are defined here:
[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.
@@ -469,11 +453,11 @@
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
+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]
+[large_bitset_segment_combiner]
as first function argument. We will pass member functions `combine_` here,
``
Modified: sandbox/itl/libs/itl/example/large_bitset_/large_bitset.hpp
==============================================================================
--- sandbox/itl/libs/itl/example/large_bitset_/large_bitset.hpp (original)
+++ sandbox/itl/libs/itl/example/large_bitset_/large_bitset.hpp 2009-10-23 13:29:41 EDT (Fri, 23 Oct 2009)
@@ -12,8 +12,8 @@
#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 "bits.hpp" // a minimal bitset implementation
#include <boost/itl/interval_map.hpp> // base of large bitsets
namespace mini // minimal implementations for example projects
@@ -139,17 +139,19 @@
//]
//[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) );
+private: // Example value
+ static const chunk_type // 8-bit case
+ bit_count = sizeof(chunk_type)*CHAR_BIT, // 8 Size of the associated bitsets
+ divisor = bit_count , // 8 Divisor to find intervals for values
+ shift = log2_<divisor>::value , // 3 To express the division as bit shift
+ c1 = static_cast<chunk_type>(1) , // Helps to avoid static_casts for long long
+ mask = divisor - c1 , // 7=11100000 Helps to express the modulo operation as bit_and
+ all = ~static_cast<chunk_type>(0), // 255=11111111 Helps to express a complete associated bitset
+ top = c1 << (bit_count-c1) ; // 128=00000001 Value of the most significant bit of associated bitsets
+ // !> Note: Most signigicant bit on the right.
//]
- //[large_bitset_segment_modifier
- typedef void (large_bitset::*segment_modifier)(element_type, element_type, bitset_type);
+ //[large_bitset_segment_combiner
+ typedef void (large_bitset::*segment_combiner)(element_type, element_type, bitset_type);
//]
//[large_bitset_bitset_filler
@@ -158,60 +160,37 @@
//]
//[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;
+ large_bitset& segment_apply(segment_combiner combine, const interval_type& operand)
+ { // same as
+ element_type base = operand.first() >> shift, // operand.first()/ divisor
+ ceil = operand.last() >> shift, // operand.last() / divisor
+ base_rest = operand.first() & mask , // operand.first()% divisor
+ ceil_rest = operand.last() & mask ; // operand.last() % divisor
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)
+ (this->*combine)(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 == all)
- upper = ceil+1;
- else
- {
- (this->*modify)(ceil, ceil+1, bitset_type(from_lower_to(ceil_rest)));
- upper = ceil;
- }
+ element_type mid_low = base_rest == 0 ? base : base+1, // first element of mid part
+ mid_up = ceil_rest == all ? ceil+1 : ceil ; // last element of mid part
- if(lower < upper)
- (this->*modify)(lower, upper, bitset_type(all));
+ if(base_rest > 0) // Bitset of base interval has to be filled from base_rest to last
+ (this->*combine)(base, base+1, bitset_type(to_upper_from(base_rest)));
+ if(ceil_rest < all) // Bitset of ceil interval has to be filled from first to ceil_rest
+ (this->*combine)(ceil, ceil+1, bitset_type(from_lower_to(ceil_rest)));
+ if(mid_low < mid_up) // For the middle part all bits have to set.
+ (this->*combine)(mid_low, mid_up, 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); }
+ void add_(DomainT lo, DomainT up, BitSetT bits){_map += value_type(interval_type::rightopen(lo,up), bits);}
+ void subtract_(DomainT lo, DomainT up, BitSetT bits){_map -= value_type(interval_type::rightopen(lo,up), bits);}
+ void intersect_(DomainT lo, DomainT up, BitSetT bits){_map &= value_type(interval_type::rightopen(lo,up), bits);}
+ void flip_(DomainT lo, DomainT up, BitSetT bits){_map ^= value_type(interval_type::rightopen(lo,up), bits);}
//]
//[large_bitmap_impl_map
Modified: sandbox/itl/libs/itl/example/std_copy_/std_copy.cpp
==============================================================================
--- sandbox/itl/libs/itl/example/std_copy_/std_copy.cpp (original)
+++ sandbox/itl/libs/itl/example/std_copy_/std_copy.cpp 2009-10-23 13:29:41 EDT (Fri, 23 Oct 2009)
@@ -61,7 +61,7 @@
// 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
+ // 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()));
Modified: sandbox/itl/libs/itl/example/std_transform_/std_transform.cpp
==============================================================================
--- sandbox/itl/libs/itl/example/std_transform_/std_transform.cpp (original)
+++ sandbox/itl/libs/itl/example/std_transform_/std_transform.cpp 2009-10-23 13:29:41 EDT (Fri, 23 Oct 2009)
@@ -116,7 +116,7 @@
// 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 << "Using std::transform to fill a separate_interval_set:\n\n";
cout << "itl::adding : " << segset << "\n\n";
}