Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

PrevUpHomeNext

Projects

Large Bitset

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.

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 words. 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 interval_map of bitsets:

typedef interval_map<IntegralT, 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 associated: Represents a total of k*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) elements, if M is the number of bits of the integral type IntegralT. Unlike bitsets, that usually represent unsigned integral numbers, large_bitset may range over negative numbers as well. 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.

To quicken your appetite for a look at the implementation here are a few use cases first. Within the examples that follow, we will use natk for unsigned integrals and bitsk for bitsets containing k bits.

Let's start large. In the first example . . .

void test_large()
{ 
    const nat64 much = 0xffffffffffffffffull; 
    large_bitset<> venti; // ... the largest, I can think of ;)
    venti += discrete_interval<nat64>(0, much);

    cout << "----- Test function test_large() -----------------------------------------------\n";
    cout << "We have just turned on the awesome amount of 18,446,744,073,709,551,616 bits ;-)\n";
    venti.show_segments();
    

. . . we are testing the limits. First we set all bits and then we switch off the very last bit.

    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";
}

Program output (a little beautified):

----- Test function test_large() -----------------------------------------------
We have just turned on the awesome amount of 18,446,744,073,709,551,616 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 . . .

void test_small()
{
    large_bitset<nat32, bits8> tall; // small is tall ...
        // ... because even this 'small' large_bitset 
        // can represent up to 2^32 == 4,294,967,296 bits.

    cout << "----- Test function test_small() -----------\n";
    cout << "-- Switch on all bits in range [0,64] ------\n";
    tall += discrete_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 ^= discrete_interval<nat>::right_open(24,30);
    tall.show_segments();
    cout << "--------------------------------------------\n";

    cout << "-- Remove the first 10 bits ----------------\n";
    tall -= discrete_interval<nat>::right_open(0,10);
    tall.show_segments();

    cout << "-- Remove even bits in range [0,72) --------\n";
    int bit;
    for(bit=0; bit<72; bit++) if(!(bit%2)) tall -= bit;
    tall.show_segments();

    cout << "--    Set odd  bits in range [0,72) --------\n";
    for(bit=0; bit<72; bit++) if(bit%2) tall += bit;
    tall.show_segments();

    cout << "--------------------------------------------\n\n";

}

. . . producing this output:

----- Test function test_small() -----------
-- Switch on all bits in range [0,64] ------
[0,8)->11111111
[8,9)->10000000
--------------------------------------------
-- Turn off bits: 25,27,28 -----------------
[0,3)->11111111
[3,4)->10100111
[4,8)->11111111
[8,9)->10000000
--------------------------------------------
-- Flip bits in range [24,30) --------------
[0,3)->11111111
[3,4)->01011011
[4,8)->11111111
[8,9)->10000000
--------------------------------------------
-- Remove the first 10 bits ----------------
[1,2)->00111111
[2,3)->11111111
[3,4)->01011011
[4,8)->11111111
[8,9)->10000000
-- Remove even bits in range [0,72) --------
[1,2)->00010101
[2,3)->01010101
[3,4)->01010001
[4,8)->01010101
--    Set odd  bits in range [0,72) --------
[0,9)->01010101
--------------------------------------------

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.

void test_picturesque()
{
    typedef large_bitset<nat, bits8> Bit8Set;

    Bit8Set square, stare;
    square += discrete_interval<nat>(0,8);
    for(int i=1; i<5; i++)
    { 
        square += 8*i; 
        square += 8*i+7; 
    }

    square += discrete_interval<nat>(41,47);

    cout << "----- Test function test_picturesque() -----\n";
    cout << "-------- empty face:       " 
         << square.interval_count()           << " intervals -----\n";
    square.show_matrix(" *");

    stare += 18; stare += 21;
    stare += discrete_interval<nat>(34,38);

    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";
}

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 interval_map using only about 250 lines of code. This is shown in the sections that follow.

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 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<BitSetT> and inplace_bit_and<BitSetT>. 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 template inplace_bit_add for parameter Combine indicates that we do not expect operator += as addition but the bitwise operator |=. For template parameter Section which is instaniated by inplace_bit_and we expect the bitwise &= operator.

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 mini::bits if qualified.

To be used as a codomain parameter of class template interval_map, mini::bits has to implement all the functions that are required for a codomain_type in general, which are the default constructor bits() and an equality 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:

template<class NaturalT> class bits
{
public:
    typedef NaturalT word_type;
    static const int       digits = std::numeric_limits<NaturalT>::digits;
    static const word_type w1     = static_cast<NaturalT>(1) ;

    bits():_bits(){}
    explicit bits(word_type value):_bits(value){}

    word_type word()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(word_type element)const{ return ((w1 << element) & _bits) != 0; } 
    std::string as_string(const char off_on[2] = " 1")const;

private:
    word_type _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 icl 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:

namespace boost { namespace icl 
{
    template<class NaturalT>
    struct is_set<mini::bits<NaturalT> >
    { 
        typedef is_set<mini::bits<NaturalT> > type;
        BOOST_STATIC_CONSTANT(bool, value = true); 
    };

    template<class NaturalT>
    struct has_set_semantics<mini::bits<NaturalT> >
    { 
        typedef has_set_semantics<mini::bits<NaturalT> > type;
        BOOST_STATIC_CONSTANT(bool, value = true); 
    };
}}

This is done by adding a partial template specialization to the type trait template icl::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:

                                               // These includes are needed ...
#include <string>                              // for conversion to output and to
#include <boost/icl/type_traits/has_set_semantics.hpp>//declare that bits has the
                                               // behavior of a set.

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 #includes this time:

#include <iostream>                   // to organize output
#include <limits>                     // limits and associated constants
#include <boost/operators.hpp>        // to define operators with minimal effort
#include "meta_log.hpp"               // a meta logarithm
#include "bits.hpp"                   // a minimal bitset implementation
#include <boost/icl/interval_map.hpp> // base of large bitsets

namespace mini // minimal implementations for example projects
{

Besides boost/icl/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:

typedef unsigned char      nat8; // nati i: number bits
typedef unsigned short     nat16;
typedef unsigned long      nat32; 
typedef unsigned long long nat64; 
typedef unsigned long      nat; 

typedef bits<nat8>  bits8;
typedef bits<nat16> bits16;
typedef bits<nat32> bits32;
typedef bits<nat64> bits64;

And now let's code large_bitset.

template 
<
    typename    DomainT = nat64, 
    typename    BitSetT = bits64, 
    ICL_COMPARE Compare = ICL_COMPARE_INSTANCE(std::less, DomainT),
    ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare),
    ICL_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>, ICL_INTERVAL_TYPE(Interval,DomainT,Compare)
    , boost::orable2       < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, ICL_INTERVAL_TYPE(Interval,DomainT,Compare)
    , boost::subtractable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, ICL_INTERVAL_TYPE(Interval,DomainT,Compare)
    , boost::andable2      < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, ICL_INTERVAL_TYPE(Interval,DomainT,Compare)
    , boost::xorable2      < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, ICL_INTERVAL_TYPE(Interval,DomainT,Compare)
      > > > > > > > > > > > > > > > > >
    //^ & - | + ^ & - | + ^ & - | + < == 
    //segment   element   container

The first template parameter DomainT will be instantiated with an 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 nat64 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 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.

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

typedef boost::icl::interval_map
    <DomainT, BitSetT, boost::icl::partial_absorber, 
     std::less, boost::icl::inplace_bit_add, boost::icl::inplace_bit_and> interval_bitmap_type;

typedef DomainT                                      domain_type;
typedef DomainT                                      element_type;
typedef BitSetT                                      bitset_type;
typedef typename BitSetT::word_type                  word_type;
typedef typename interval_bitmap_type::interval_type interval_type;
typedef typename interval_bitmap_type::value_type    value_type;

most importantly the implementing interval_bitmap_type that is used for the implementing container.

private:
    interval_bitmap_type _map;

In order to use Boost.Operator we have to implement the fundamental operators as class members. This can be done quite schematically.

public:
    bool     operator ==(const large_bitset& rhs)const { return _map == rhs._map; }
    bool     operator < (const large_bitset& rhs)const { 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));      }
    large_bitset& operator |=(const element_type& rhs) {return add(interval_type(rhs));      }
    large_bitset& operator -=(const element_type& rhs) {return subtract(interval_type(rhs)); }
    large_bitset& operator &=(const element_type& rhs) {return intersect(interval_type(rhs));}
    large_bitset& operator ^=(const element_type& rhs) {return flip(interval_type(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);     }
    

As we can see, the seven most important operators that work on the class type large_bitset can be directly implemented by propagating 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 is 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 interval's borders into the right bitset positions.

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);}

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.

size_t interval_count()const { return boost::icl::interval_count(_map); }

void show_segments()const
{
    for(typename interval_bitmap_type::const_iterator it_ = _map.begin();
        it_ != _map.end(); ++it_)
    {
        interval_type   itv  = it_->first;
        bitset_type     bits = it_->second;
        std::cout << itv << "->" << bits.as_string("01") << std::endl;
    }
}

void show_matrix(const char off_on[2] = " 1")const
{
    using namespace boost;
    typename interval_bitmap_type::const_iterator iter = _map.begin();
    while(iter != _map.end())
    {
        element_type fst = icl::first(iter->first), lst = icl::last(iter->first);
        for(element_type chunk = fst; chunk <= lst; chunk++)
            std::cout << iter->second.as_string(off_on) << std::endl;
        ++iter;
    }
}

  • 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.

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 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 27 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 here:

private:                                      // Example value
    static const word_type                    //   8-bit case  
        digits  = std::numeric_limits         // --------------------------------------------------------------
                  <word_type>::digits       , //   8           Size of the associated bitsets 
        divisor = digits                    , //   8           Divisor to find intervals for values
        last    = digits-1                  , //   7           Last bit (0 based)
        shift   = log2_<divisor>::value     , //   3           To express the division as bit shift
        w1      = static_cast<word_type>(1) , //               Helps to avoid static_casts for long long
        mask    = divisor - w1              , //   7=11100000  Helps to express the modulo operation as bit_and
        all     = ~static_cast<word_type>(0), // 255=11111111  Helps to express a complete associated bitset
        top     = w1 << (digits-w1)      ;    // 128=00000001  Value of the most significant bit of associated bitsets
                                              //            !> Note: Most signigicant bit on the right.
    

Looking at the example again, we can see that we have to identify the positions of the beginning and ending of the interval [5,27] that is to insert, and then subdivide that range of bitsets into three partitions.

  1. The bitset where the interval starts.
  2. the bitset where the interval ends
  3. 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:

  1. 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)
  2. 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)
  3. 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

typedef void (large_bitset::*segment_combiner)(element_type, element_type, bitset_type);

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:

void       add_(DomainT lo, DomainT up, BitSetT bits){_map += value_type(interval_type::right_open(lo,up), bits);}
void  subtract_(DomainT lo, DomainT up, BitSetT bits){_map -= value_type(interval_type::right_open(lo,up), bits);}
void intersect_(DomainT lo, DomainT up, BitSetT bits){_map &= value_type(interval_type::right_open(lo,up), bits);}
void      flip_(DomainT lo, DomainT up, BitSetT bits){_map ^= value_type(interval_type::right_open(lo,up), bits);}

Finally we can code function segment_apply, that does the partitioning and subsequent combining:

large_bitset& segment_apply(segment_combiner combine, const interval_type& operand)
{
    using namespace boost;
    if(icl::is_empty(operand))
        return *this;
                                                        // same as
    element_type   base = icl::first(operand) >> shift, // icl::first(operand) / divisor
                   ceil = icl::last (operand) >> shift; // icl::last (operand) / divisor
    word_type base_rest = icl::first(operand) &  mask , // icl::first(operand) % divisor
              ceil_rest = icl::last (operand) &  mask ; // icl::last (operand) % divisor  

    if(base == ceil) // [first, last] are within one bitset (chunk)
        (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 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(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;
}

The functions that help filling bitsets to and from a given bit are implemented here:

static word_type from_lower_to(word_type bit){return bit==last ? all : (w1<<(bit+w1))-w1;}
static word_type to_upper_from(word_type bit){return bit==last ? top : ~((w1<<bit)-w1); }

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 integral domain types.


PrevUpHomeNext