1 /*-----------------------------------------------------------------------------+ 2 Author: Joachim Faulhaber 3 Copyright (c) 2009-2009: Joachim Faulhaber 4 +------------------------------------------------------------------------------+ 5 Distributed under the Boost Software License, Version 1.0. 6 (See accompanying file LICENCE.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt) 8 +-----------------------------------------------------------------------------*/ 9 #ifndef BOOST_LIBS_ICL_EXAMPLE_LARGE_BITSET__LARGE_BITSET_HPP_JOFA_091019 10 #define BOOST_LIBS_ICL_EXAMPLE_LARGE_BITSET__LARGE_BITSET_HPP_JOFA_091019 11 12 //[large_bitset_includes 13 #include <iostream> // to organize output 14 #include <limits> // limits and associated constants 15 #include <boost/operators.hpp> // to define operators with minimal effort 16 #include "meta_log.hpp" // a meta logarithm 17 #include "bits.hpp" // a minimal bitset implementation 18 #include <boost/icl/interval_map.hpp> // base of large bitsets 19 20 namespace mini // minimal implementations for example projects 21 { 22 //] 23 24 //[large_bitset_natural_typedefs 25 typedef unsigned char nat8; // nati i: number bits 26 typedef unsigned short nat16; 27 typedef unsigned long nat32; 28 typedef unsigned long long nat64; 29 typedef unsigned long nat; 30 31 typedef bits<nat8> bits8; 32 typedef bits<nat16> bits16; 33 typedef bits<nat32> bits32; 34 typedef bits<nat64> bits64; 35 //] 36 37 //[large_bitset_class_template_header 38 template 39 < 40 typename DomainT = nat64, 41 typename BitSetT = bits64, 42 ICL_COMPARE Compare = ICL_COMPARE_INSTANCE(std::less, DomainT), 43 ICL_INTERVAL(ICL_COMPARE) Interval = ICL_INTERVAL_INSTANCE(ICL_INTERVAL_DEFAULT, DomainT, Compare), 44 ICL_ALLOC Alloc = std::allocator 45 > 46 class large_bitset 47 : boost::equality_comparable < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc> 48 , boost::less_than_comparable< large_bitset<DomainT,BitSetT,Compare,Interval,Alloc> 49 50 , boost::addable < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc> 51 , boost::orable < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc> 52 , boost::subtractable < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc> 53 , boost::andable < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc> 54 , boost::xorable < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc> 55 56 , boost::addable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, DomainT 57 , boost::orable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, DomainT 58 , boost::subtractable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, DomainT 59 , boost::andable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, DomainT 60 , boost::xorable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, DomainT 61 62 , boost::addable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, ICL_INTERVAL_TYPE(Interval,DomainT,Compare) 63 , boost::orable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, ICL_INTERVAL_TYPE(Interval,DomainT,Compare) 64 , boost::subtractable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, ICL_INTERVAL_TYPE(Interval,DomainT,Compare) 65 , boost::andable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, ICL_INTERVAL_TYPE(Interval,DomainT,Compare) 66 , boost::xorable2 < large_bitset<DomainT,BitSetT,Compare,Interval,Alloc>, ICL_INTERVAL_TYPE(Interval,DomainT,Compare) 67 > > > > > > > > > > > > > > > > > 68 //^ & - | + ^ & - | + ^ & - | + < == 69 //segment element container 70 //] 71 { 72 public: 73 //[large_bitset_associated_types 74 typedef boost::icl::interval_map 75 <DomainT, BitSetT, boost::icl::partial_absorber, 76 std::less, boost::icl::inplace_bit_add, boost::icl::inplace_bit_and> interval_bitmap_type; 77 78 typedef DomainT domain_type; 79 typedef DomainT element_type; 80 typedef BitSetT bitset_type; 81 typedef typename BitSetT::word_type word_type; 82 typedef typename interval_bitmap_type::interval_type interval_type; 83 typedef typename interval_bitmap_type::value_type value_type; 84 //] 85 //[large_bitset_operators 86 public: operator ==(const large_bitset & rhs) const87 bool operator ==(const large_bitset& rhs)const { return _map == rhs._map; } operator <(const large_bitset & rhs) const88 bool operator < (const large_bitset& rhs)const { return _map < rhs._map; } 89 operator +=(const large_bitset & rhs)90 large_bitset& operator +=(const large_bitset& rhs) {_map += rhs._map; return *this;} operator |=(const large_bitset & rhs)91 large_bitset& operator |=(const large_bitset& rhs) {_map |= rhs._map; return *this;} operator -=(const large_bitset & rhs)92 large_bitset& operator -=(const large_bitset& rhs) {_map -= rhs._map; return *this;} operator &=(const large_bitset & rhs)93 large_bitset& operator &=(const large_bitset& rhs) {_map &= rhs._map; return *this;} operator ^=(const large_bitset & rhs)94 large_bitset& operator ^=(const large_bitset& rhs) {_map ^= rhs._map; return *this;} 95 operator +=(const element_type & rhs)96 large_bitset& operator +=(const element_type& rhs) {return add(interval_type(rhs)); } operator |=(const element_type & rhs)97 large_bitset& operator |=(const element_type& rhs) {return add(interval_type(rhs)); } operator -=(const element_type & rhs)98 large_bitset& operator -=(const element_type& rhs) {return subtract(interval_type(rhs)); } operator &=(const element_type & rhs)99 large_bitset& operator &=(const element_type& rhs) {return intersect(interval_type(rhs));} operator ^=(const element_type & rhs)100 large_bitset& operator ^=(const element_type& rhs) {return flip(interval_type(rhs)); } 101 operator +=(const interval_type & rhs)102 large_bitset& operator +=(const interval_type& rhs){return add(rhs); } operator |=(const interval_type & rhs)103 large_bitset& operator |=(const interval_type& rhs){return add(rhs); } operator -=(const interval_type & rhs)104 large_bitset& operator -=(const interval_type& rhs){return subtract(rhs); } operator &=(const interval_type & rhs)105 large_bitset& operator &=(const interval_type& rhs){return intersect(rhs);} operator ^=(const interval_type & rhs)106 large_bitset& operator ^=(const interval_type& rhs){return flip(rhs); } 107 //] 108 //[large_bitset_fundamental_functions add(const interval_type & rhs)109 large_bitset& add (const interval_type& rhs){return segment_apply(&large_bitset::add_, rhs);} subtract(const interval_type & rhs)110 large_bitset& subtract (const interval_type& rhs){return segment_apply(&large_bitset::subtract_, rhs);} intersect(const interval_type & rhs)111 large_bitset& intersect(const interval_type& rhs){return segment_apply(&large_bitset::intersect_,rhs);} flip(const interval_type & rhs)112 large_bitset& flip (const interval_type& rhs){return segment_apply(&large_bitset::flip_, rhs);} 113 //] 114 115 //[large_bitset_demo_functions interval_count() const116 size_t interval_count()const { return boost::icl::interval_count(_map); } 117 show_segments() const118 void show_segments()const 119 { 120 for(typename interval_bitmap_type::const_iterator it_ = _map.begin(); 121 it_ != _map.end(); ++it_) 122 { 123 interval_type itv = it_->first; 124 bitset_type bits = it_->second; 125 std::cout << itv << "->" << bits.as_string("01") << std::endl; 126 } 127 } 128 show_matrix(const char off_on[2]=" 1") const129 void show_matrix(const char off_on[2] = " 1")const 130 { 131 using namespace boost; 132 typename interval_bitmap_type::const_iterator iter = _map.begin(); 133 while(iter != _map.end()) 134 { 135 element_type fst = icl::first(iter->first), lst = icl::last(iter->first); 136 for(element_type chunk = fst; chunk <= lst; chunk++) 137 std::cout << iter->second.as_string(off_on) << std::endl; 138 ++iter; 139 } 140 } 141 //] 142 143 //[large_bitset_impl_constants 144 private: // Example value 145 static const word_type // 8-bit case 146 digits = std::numeric_limits // -------------------------------------------------------------- 147 <word_type>::digits , // 8 Size of the associated bitsets 148 divisor = digits , // 8 Divisor to find intervals for values 149 last = digits-1 , // 7 Last bit (0 based) 150 shift = log2_<divisor>::value , // 3 To express the division as bit shift 151 w1 = static_cast<word_type>(1) , // Helps to avoid static_casts for long long 152 mask = divisor - w1 , // 7=11100000 Helps to express the modulo operation as bit_and 153 all = ~static_cast<word_type>(0), // 255=11111111 Helps to express a complete associated bitset 154 top = w1 << (digits-w1) ; // 128=00000001 Value of the most significant bit of associated bitsets 155 // !> Note: Most signigicant bit on the right. 156 //] 157 //[large_bitset_segment_combiner 158 typedef void (large_bitset::*segment_combiner)(element_type, element_type, bitset_type); 159 //] 160 161 //[large_bitset_bitset_filler from_lower_to(word_type bit)162 static word_type from_lower_to(word_type bit){return bit==last ? all : (w1<<(bit+w1))-w1;} to_upper_from(word_type bit)163 static word_type to_upper_from(word_type bit){return bit==last ? top : ~((w1<<bit)-w1); } 164 //] 165 166 //[large_bitset_segment_apply segment_apply(segment_combiner combine,const interval_type & operand)167 large_bitset& segment_apply(segment_combiner combine, const interval_type& operand) 168 { 169 using namespace boost; 170 if(icl::is_empty(operand)) 171 return *this; 172 // same as 173 element_type base = icl::first(operand) >> shift, // icl::first(operand) / divisor 174 ceil = icl::last (operand) >> shift; // icl::last (operand) / divisor 175 word_type base_rest = icl::first(operand) & mask , // icl::first(operand) % divisor 176 ceil_rest = icl::last (operand) & mask ; // icl::last (operand) % divisor 177 178 if(base == ceil) // [first, last] are within one bitset (chunk) 179 (this->*combine)(base, base+1, bitset_type( to_upper_from(base_rest) 180 & from_lower_to(ceil_rest))); 181 else // [first, last] spread over more than one bitset (chunk) 182 { 183 element_type mid_low = base_rest == 0 ? base : base+1, // first element of mid part 184 mid_up = ceil_rest == all ? ceil+1 : ceil ; // last element of mid part 185 186 if(base_rest > 0) // Bitset of base interval has to be filled from base_rest to last 187 (this->*combine)(base, base+1, bitset_type(to_upper_from(base_rest))); 188 if(ceil_rest < all) // Bitset of ceil interval has to be filled from first to ceil_rest 189 (this->*combine)(ceil, ceil+1, bitset_type(from_lower_to(ceil_rest))); 190 if(mid_low < mid_up) // For the middle part all bits have to set. 191 (this->*combine)(mid_low, mid_up, bitset_type(all)); 192 } 193 return *this; 194 } 195 //] 196 197 //[large_bitmap_combiners add_(DomainT lo,DomainT up,BitSetT bits)198 void add_(DomainT lo, DomainT up, BitSetT bits){_map += value_type(interval_type::right_open(lo,up), bits);} subtract_(DomainT lo,DomainT up,BitSetT bits)199 void subtract_(DomainT lo, DomainT up, BitSetT bits){_map -= value_type(interval_type::right_open(lo,up), bits);} intersect_(DomainT lo,DomainT up,BitSetT bits)200 void intersect_(DomainT lo, DomainT up, BitSetT bits){_map &= value_type(interval_type::right_open(lo,up), bits);} flip_(DomainT lo,DomainT up,BitSetT bits)201 void flip_(DomainT lo, DomainT up, BitSetT bits){_map ^= value_type(interval_type::right_open(lo,up), bits);} 202 //] 203 204 //[large_bitmap_impl_map 205 private: 206 interval_bitmap_type _map; 207 //] 208 }; 209 210 } // mini 211 #endif 212 213 214