А теперь давайте код 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

Первый параметр шаблона DomainT будет мгновенным с интегральным типом, который определяет тип чисел, которые могут быть элементами набора. Поскольку мы хотим пойти на большой набор, мы используем nat64 как по умолчанию, который является 64-битным неподписанным целым числом, начиная от 0 до 2^64-1. Как параметр битсета мы также выбираем 64-битный по умолчанию. Параметры Combine и Interval необходимо передавать на зависимые выражения типа. При желании может быть выбран аллокат.

Вложенный список частного наследования содержит группы шаблонных мгновенных сообщений от Boost.Operator, которые предоставляют производных операторов от более фундаментальных раз. Реализуя основные операторы, мы получаем производные бесплатно. Ниже приведен краткий обзор того, что мы получаем с помощью Boost.Operator, где S означает large_bitset, i для него interval_type и e для него domain_type или .

Существует ряд связанных типов

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;

самое главное - реализация interval_bitmap_type, которая используется для реализации контейнера.

private:
    interval_bitmap_type _map;

Для того, чтобы использовать Boost.Operator, мы должны реализовать основные операторы в качестве членов класса. Это можно сделать довольно схематично.

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

Как мы видим, семь наиболее важных операторов, которые работают на типе класса large_bitset, могут быть непосредственно реализованы путем распространения операции на реализацию _map типа interval_bitmap_type. Для операторов, которые работают на сегментах и типах элементов, мы используем функции add, subtract, intersect и flip. Поскольку мы увидим, что для объединения этих функций с функциональностью реализующего контейнера требуется лишь небольшое количество адапера.

addition, subtraction, intersection или симметричное различие, после перевода границ интервала в правый битсет позиции. .

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, нам понадобится несколько дополнительных функций, специально выводимых в двух разных вкусах.

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

Для реализации таких операций, как добавление элемента, скажем 42 к большому биту, нам нужно перевести value на позицион бит, представляющий 42 в интервале контейнера битетов. В качестве примера предположим, что мы используем

large_bitset<nat, mini::bits8> lbs;

который несет только небольшие биты 8 бит. Предполагается, что первые четыре интервала lbs связаны с некоторыми битами. Теперь мы хотим добавить интервал [a,b]==[5,27]. Это приведет к следующему:

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

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

d Это мощность 2: d = 2^x. Поэтому разделение и модуло могут быть выражены битетными операциями. Константы, необходимые для этих вычислений, определены здесь:

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.

Глядя на пример снова, мы видим, что мы должны определить позиции начала и окончания интервала [5,27], то есть вставить, а затем subdivide этот диапазон битов на три раздела.

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]

После разделения мы выполняем операцию o следующим образом:

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

как первый аргумент функции. Мы проведем функции членов combine_ здесь,

combine_(first_of_interval, end_of_interval, some_bitset);

interval_bitmap_type _map. Вот эти функции:

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

Наконец, мы можем кодировать функцию segment_apply, что делает разделение и последующее объединение:

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

Функции, которые помогают заполнять биты в определенный момент и из него, реализованы здесь:

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

Это завершает реализацию шаблона класса large_bitset. Используя только небольшое количество в основном схематического кода, мы смогли предоставить довольно мощный, сжимающий и обычно используемый тип набора для всех типов интегральных доменов.