00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027 #ifndef BMVMIN__H__INCLUDED__
00028 #define BMVMIN__H__INCLUDED__
00029
00030 namespace bm
00031 {
00032
00033
00034 #define BM_MINISET_GAPLEN (bm::gap_len_table<true>::_len[0])
00035 #define BM_MINISET_ARRSIZE(x) ((x / 32) + ( (x % 32) && 1 ))
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054 template <class A, size_t N> class miniset
00055 {
00056 public:
00057
00058 miniset()
00059 : m_buf(0),
00060 m_type(1)
00061 {}
00062
00063 miniset(const miniset& mset)
00064 {
00065 if (mset.m_buf)
00066 {
00067 if (mset.m_type)
00068 init_gapbuf(mset.m_buf);
00069 else
00070 init_bitbuf(mset.m_buf);
00071 }
00072 else
00073 {
00074 m_type = mset.m_type;
00075 m_buf = 0;
00076 }
00077 }
00078
00079 ~miniset()
00080 {
00081 if (m_buf)
00082 {
00083 A::deallocate(m_buf, m_type ?
00084 (BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t)))
00085 :
00086 (BM_MINISET_ARRSIZE(N)));
00087 }
00088 }
00089
00090
00091 unsigned test(bm::id_t n) const
00092 {
00093 return
00094 !m_buf ? 0
00095 :
00096 m_type ?
00097 gap_test((gap_word_t*)m_buf, n)
00098 :
00099 m_buf[n>>bm::set_word_shift] & (1<<(n & bm::set_word_mask));
00100 }
00101
00102 void set(bm::id_t n, bool val=true)
00103 {
00104 if (m_type == 0)
00105 {
00106 if (!m_buf)
00107 {
00108 if (!val) return;
00109 init_bitbuf(0);
00110 }
00111
00112 unsigned nword = n >> bm::set_word_shift;
00113 unsigned mask = unsigned(1) << (n & bm::set_word_mask);
00114
00115 val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
00116 }
00117 else
00118 {
00119 if (!m_buf)
00120 {
00121 if (!val) return;
00122 init_gapbuf(0);
00123 }
00124
00125 unsigned is_set;
00126 unsigned new_block_len =
00127 gap_set_value(val, (gap_word_t*)m_buf, n, &is_set);
00128
00129 if (new_block_len > unsigned(BM_MINISET_GAPLEN-4))
00130 {
00131 convert_buf();
00132 }
00133 }
00134 }
00135
00136 unsigned mem_used() const
00137 {
00138 return sizeof(*this) +
00139 m_buf ?
00140 (m_type ? (BM_MINISET_GAPLEN * sizeof(gap_word_t))
00141 : (BM_MINISET_ARRSIZE(N) * sizeof(bm::word_t)))
00142 : 0;
00143 }
00144
00145 void swap(miniset& mset)
00146 {
00147 bm::word_t* buftmp = m_buf;
00148 m_buf = mset.m_buf;
00149 mset.m_buf = buftmp;
00150 unsigned typetmp = m_type;
00151 m_type = mset.m_type;
00152 mset.m_type = typetmp;
00153 }
00154
00155
00156 private:
00157
00158 void init_bitbuf(bm::word_t* buf)
00159 {
00160 unsigned arr_size = BM_MINISET_ARRSIZE(N);
00161 m_buf = A::allocate(arr_size, 0);
00162 if (buf)
00163 {
00164 ::memcpy(m_buf, buf, arr_size * sizeof(bm::word_t));
00165 }
00166 else
00167 {
00168 ::memset(m_buf, 0, arr_size * sizeof(bm::word_t));
00169 }
00170 m_type = 0;
00171 }
00172
00173 void init_gapbuf(bm::word_t* buf)
00174 {
00175 unsigned arr_size =
00176 BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t));
00177 m_buf = A::allocate(arr_size, 0);
00178 if (buf)
00179 {
00180 ::memcpy(m_buf, buf, arr_size * sizeof(bm::word_t));
00181 }
00182 else
00183 {
00184 *m_buf = 0;
00185 gap_set_all((gap_word_t*)m_buf, bm::gap_max_bits, 0);
00186 }
00187 m_type = 1;
00188 }
00189
00190 void convert_buf()
00191 {
00192 unsigned arr_size = BM_MINISET_ARRSIZE(N);
00193 bm::word_t* buf = A::allocate(arr_size, 0);
00194
00195 gap_convert_to_bitset(buf, (gap_word_t*) m_buf, arr_size);
00196 arr_size =
00197 BM_MINISET_GAPLEN / (sizeof(bm::word_t) / sizeof(bm::gap_word_t));
00198 A::deallocate(m_buf, arr_size);
00199 m_buf = buf;
00200 m_type = 0;
00201 }
00202
00203 private:
00204 bm::word_t* m_buf;
00205 unsigned m_type;
00206 };
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217 template<size_t N> class bvmini
00218 {
00219 public:
00220
00221 bvmini(int start_strategy = 0)
00222 {
00223 ::memset(m_buf, 0, sizeof(m_buf));
00224 }
00225
00226 bvmini(const bvmini& mset)
00227 {
00228 ::memcpy(m_buf, mset.m_buf, sizeof(m_buf));
00229 }
00230
00231
00232
00233 unsigned test(bm::id_t n) const
00234 {
00235 return m_buf[n>>bm::set_word_shift] & (1<<(n & bm::set_word_mask));
00236 }
00237
00238 void set(bm::id_t n, bool val=true)
00239 {
00240 unsigned nword = n >> bm::set_word_shift;
00241 unsigned mask = unsigned(1) << (n & bm::set_word_mask);
00242
00243 val ? (m_buf[nword] |= mask) : (m_buf[nword] &= ~mask);
00244 }
00245
00246 unsigned mem_used() const
00247 {
00248 return sizeof(*this);
00249 }
00250
00251 void swap(bvmini& mset)
00252 {
00253 for (unsigned i = 0; i < BM_MINISET_ARRSIZE(N); ++i)
00254 {
00255 bm::word_t tmp = m_buf[i];
00256 m_buf[i] = mset.m_buf[i];
00257 mset.m_buf[i] = tmp;
00258 }
00259 }
00260
00261 private:
00262 bm::word_t m_buf[BM_MINISET_ARRSIZE(N)];
00263 };
00264
00265
00266
00267
00268
00269
00270
00271
00272
00273
00274 template<class A> class bvector_mini
00275 {
00276 public:
00277 bvector_mini(unsigned size)
00278 : m_buf(0),
00279 m_size(size)
00280 {
00281 unsigned arr_size = (size / 32) + 1;
00282 m_buf = A::allocate(arr_size, 0);
00283 ::memset(m_buf, 0, arr_size * sizeof(unsigned));
00284 }
00285 bvector_mini(const bvector_mini& bvect)
00286 : m_size(bvect.m_size)
00287 {
00288 unsigned arr_size = (m_size / 32) + 1;
00289 m_buf = A::allocate(arr_size, 0);
00290 ::memcpy(m_buf, bvect.m_buf, arr_size * sizeof(unsigned));
00291 }
00292
00293 ~bvector_mini()
00294 {
00295 A::deallocate(m_buf, (m_size / 32) + 1);
00296 }
00297
00298
00299 int is_bit_true(unsigned pos) const
00300 {
00301 unsigned char mask = (unsigned char)((char)0x1 << (pos & 7));
00302 unsigned char* offs = (unsigned char*)m_buf + (pos >> 3);
00303
00304 return (*offs) & mask;
00305 }
00306
00307
00308 void set_bit(unsigned pos)
00309 {
00310 unsigned char mask = (unsigned char)(0x1 << (pos & 7));
00311 unsigned char* offs = (unsigned char*)m_buf + (pos >> 3);
00312 *offs |= mask;
00313 }
00314
00315
00316
00317 void clear_bit(unsigned pos)
00318 {
00319 unsigned char mask = (unsigned char)(0x1 << (pos & 7));
00320 unsigned char* offs = (unsigned char*)m_buf + (pos >> 3);
00321
00322 *offs &= ~mask;
00323 }
00324
00325
00326 unsigned bit_count() const
00327 {
00328 register unsigned count = 0;
00329 const unsigned* end = m_buf + (m_size / 32)+1;
00330
00331 for (unsigned* start = m_buf; start < end; ++start)
00332 {
00333 register unsigned value = *start;
00334 for (count += (value!=0); value &= value - 1; ++count);
00335 }
00336 return count;
00337 }
00338
00339
00340 int compare(const bvector_mini& bvect)
00341 {
00342 unsigned cnt1 = bit_count();
00343 unsigned cnt2 = bvect.bit_count();
00344
00345 if (!cnt1 && !cnt2) return 0;
00346
00347 unsigned cnt_min = cnt1 < cnt2 ? cnt1 : cnt2;
00348
00349 if (!cnt_min) return cnt1 ? 1 : -1;
00350
00351 unsigned idx1 = get_first();
00352 unsigned idx2 = bvect.get_first();
00353
00354 for (unsigned i = 0; i < cnt_min; ++i)
00355 {
00356 if (idx1 != idx2)
00357 {
00358 return idx1 < idx2 ? 1 : -1;
00359 }
00360 idx1 = get_next(idx1);
00361 idx2 = bvect.get_next(idx2);
00362 }
00363
00364 BM_ASSERT(idx1==0 || idx2==0);
00365
00366 if (idx1 != idx2)
00367 {
00368 if (!idx1) return -1;
00369 if (!idx2) return 1;
00370 return idx1 < idx2 ? 1 : -1;
00371 }
00372
00373 return 0;
00374 }
00375
00376
00377
00378 unsigned get_first() const
00379 {
00380 unsigned pos = 0;
00381 const unsigned char* ptr = (unsigned char*) m_buf;
00382
00383 for (unsigned i = 0; i < (m_size/8)+1; ++i)
00384 {
00385 register unsigned char w = ptr[i];
00386
00387
00388 if (w != 0)
00389 {
00390 while ((w & 1) == 0)
00391 {
00392 w >>= 1;
00393 ++pos;
00394 }
00395 return pos;
00396 }
00397 pos += sizeof(unsigned char) * 8;
00398 }
00399 return 0;
00400 }
00401
00402
00403
00404 unsigned get_next(unsigned idx) const
00405 {
00406 register unsigned i;
00407
00408 for (i = idx+1; i < m_size; ++i)
00409 {
00410 unsigned char* offs = (unsigned char*)m_buf + (i >> 3);
00411 if (*offs)
00412 {
00413 unsigned char mask = (unsigned char)((char)0x1 << (i & 7));
00414
00415 if (*offs & mask)
00416 {
00417 return i;
00418 }
00419 }
00420 else
00421 {
00422 i += 7;
00423 }
00424 }
00425 return 0;
00426 }
00427
00428
00429 void combine_and(const bvector_mini& bvect)
00430 {
00431 const unsigned* end = m_buf + (m_size / 32)+1;
00432
00433 const unsigned* src = bvect.get_buf();
00434
00435 for (unsigned* start = m_buf; start < end; ++start)
00436 {
00437 *start &= *src++;
00438 }
00439 }
00440
00441 void combine_xor(const bvector_mini& bvect)
00442 {
00443 const unsigned* end = m_buf + (m_size / 32)+1;
00444
00445 const unsigned* src = bvect.get_buf();
00446
00447 for (unsigned* start = m_buf; start < end; ++start)
00448 {
00449 *start ^= *src++;
00450 }
00451 }
00452
00453
00454 void combine_or(const bvector_mini& bvect)
00455 {
00456 const unsigned* end = m_buf + (m_size / 32)+1;
00457
00458 const unsigned* src = bvect.get_buf();
00459
00460 for (unsigned* start = m_buf; start < end; ++start)
00461 {
00462 *start |= *src++;
00463 }
00464 }
00465
00466 void combine_sub(const bvector_mini& bvect)
00467 {
00468 const unsigned* end = m_buf + (m_size / 32)+1;
00469
00470 const unsigned* src = bvect.get_buf();
00471
00472 for (unsigned* start = m_buf; start < end; ++start)
00473 {
00474 *start &= ~(*src++);
00475 }
00476 }
00477
00478 const unsigned* get_buf() const { return m_buf; }
00479 unsigned mem_used() const
00480 {
00481 return sizeof(bvector_mini) + (m_size / 32) + 1;
00482 }
00483
00484 void swap(bvector_mini& bvm)
00485 {
00486 BM_ASSERT(m_size == bvm.m_size);
00487 bm::word_t* buftmp = m_buf;
00488 m_buf = bvm.m_buf;
00489 bvm.m_buf = buftmp;
00490 }
00491
00492 private:
00493 bm::word_t* m_buf;
00494 unsigned m_size;
00495 };
00496
00497
00498
00499 }
00500
00501 #endif