BitMagic-C++
bmintervals.h
Go to the documentation of this file.
1#ifndef BMINTERVALS__H__INCLUDED__
2#define BMINTERVALS__H__INCLUDED__
3
4/*
5Copyright(c) 2002-2020 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
6
7Licensed under the Apache License, Version 2.0 (the "License");
8you may not use this file except in compliance with the License.
9You may obtain a copy of the License at
10
11 http://www.apache.org/licenses/LICENSE-2.0
12
13Unless required by applicable law or agreed to in writing, software
14distributed under the License is distributed on an "AS IS" BASIS,
15WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16See the License for the specific language governing permissions and
17limitations under the License.
18
19For more information please visit: http://bitmagic.io
20*/
21/*! \file bmintervals.h
22 \brief Algorithms for bit ranges and intervals
23*/
24
25#ifndef BM__H__INCLUDED__
26// BitMagic utility headers do not include main "bm.h" declaration
27// #include "bm.h" or "bm64.h" explicitly
28# error missing include (bm.h or bm64.h)
29#endif
30
31#include "bmdef.h"
32
33/** \defgroup bvintervals Algorithms for bit intervals
34 Algorithms and iterators for bit ranges and intervals
35 @ingroup bvector
36 */
37
38
39namespace bm
40{
41
42/*!
43 \brief forward iterator class to traverse bit-vector as ranges
44
45 Traverse enumerator for forward walking bit-vector as intervals:
46 series of consequtive 1111s flanked with zeroes.
47 Enumerator can traverse the whole bit-vector or jump(go_to) to position.
48
49 \ingroup bvintervals
50*/
51template<typename BV>
53{
54public:
55#ifndef BM_NO_STL
56 typedef std::input_iterator_tag iterator_category;
57#endif
58 typedef BV bvector_type;
61 typedef bm::byte_buffer<allocator_type> buffer_type;
63
64public:
65 /*! @name Construction and assignment */
66 //@{
67
69 : bv_(0), interval_(bm::id_max, bm::id_max), gap_ptr_(0)
70 {}
71
72 /**
73 Construct enumerator for the bit-vector
74 */
75 interval_enumerator(const BV& bv)
76 : bv_(&bv), interval_(bm::id_max, bm::id_max), gap_ptr_(0)
77 {
78 go_to_impl(0, false);
79 }
80
81 /**
82 Construct enumerator for the specified position
83 @param bv - source bit-vector
84 @param start_pos - position on bit-vector to search for interval
85 @param extend_start - flag to extend interval start to the start if
86 true start happenes to be less than start_pos
87 @sa go_to
88 */
89 interval_enumerator(const BV& bv, size_type start_pos, bool extend_start)
90 : bv_(&bv), interval_(bm::id_max, bm::id_max), gap_ptr_(0)
91 {
92 go_to_impl(start_pos, extend_start);
93 }
94
95 /**
96 Copy constructor
97 */
99 : bv_(ien.bv_), interval_(bm::id_max, bm::id_max), gap_ptr_(0)
100 {
101 go_to_impl(ien.start(), false);
102 }
103
104 /**
105 Assignment operator
106 */
108 {
109 bv_ = ien.bv_; gap_ptr_ = 0;
110 go_to_impl(ien.start(), false);
111 }
112
113#ifndef BM_NO_CXX11
114 /** move-ctor */
116 : bv_(0), interval_(bm::id_max, bm::id_max), gap_ptr_(0)
117 {
118 this->swap(ien);
119 }
120
121 /** move assignmment operator */
123 {
124 if (this != &ien)
125 this->swap(ien);
126 return *this;
127 }
128#endif
129
130 //@}
131
132
133 // -----------------------------------------------------------------
134
135 /*! @name Comparison methods all use start position to compare */
136 //@{
137
139 { return (start() == ien.start()); }
141 { return (start() != ien.start()); }
143 { return (start() < ien.start()); }
145 { return (start() <= ien.start()); }
147 { return (start() > ien.start()); }
149 { return (start() >= ien.start()); }
150 //@}
151
152
153 /// Return interval start/left as bit-vector coordinate 011110 [left..right]
154 size_type start() const BMNOEXCEPT;
155 /// Return interval end/right as bit-vector coordinate 011110 [left..right]
156 size_type end() const BMNOEXCEPT;
157
158 const pair_type& operator*() const BMNOEXCEPT { return interval_; }
159
160 /// Get interval pair
161 const pair_type& get() const BMNOEXCEPT { return interval_; }
162
163 /// Returns true if enumerator is valid (false if traversal is done)
164 bool valid() const BMNOEXCEPT;
165
166 // -----------------------------------------------------------------
167
168 /*! @name enumerator positioning */
169 //@{
170
171 /*!
172 @brief Go to inetrval at specified position
173 Jump to position with interval. If interval is not available at
174 the specified position (o bit) enumerator will find the next interval.
175 If interval is present we have an option to find interval start [left..]
176 and set enumerator from the effective start coodrinate
177
178 @param pos - position on bit-vector
179 @param extend_start - find effective start if it is less than the
180 go to position
181 @return true if enumerator remains valid after the jump
182 */
183 bool go_to(size_type pos, bool extend_start = true);
184
185 /*! Advance to the next interval
186 @return true if interval is available
187 @sa valid
188 */
189 bool advance();
190
191 /*! \brief Advance enumerator forward to the next available bit */
193 { advance(); return *this; }
194
195 /*! \brief Advance enumerator forward to the next available bit */
197 {
198 interval_enumerator<BV> tmp = *this;
199 advance();
200 return tmp;
201 }
202 //@}
203
204 /**
205 swap enumerator with another one
206 */
208
209protected:
212 typedef bm::heap_vector<unsigned short, bv_allocator_type, true>
214
215
216 bool go_to_impl(size_type pos, bool extend_start);
217
218 /// Turn FSM into invalid state (out of range)
219 void invalidate() BMNOEXCEPT;
220
221private:
222 const BV* bv_; ///!< bit-vector for traversal
223 gap_vector_type gap_buf_; ///!< GAP buf.vector for bit-block
224 pair_type interval_; ///! current inetrval
225 const bm::gap_word_t* gap_ptr_; ///!< current pointer in GAP block
226};
227
228//----------------------------------------------------------------------------
229
230/*!
231 \brief Returns true if range is all 1s flanked with 0s
232 Function performs the test on a closed range [left, right]
233 true interval is all 1s AND test(left-1)==false AND test(right+1)==false
234 Examples:
235 01110 [1,3] - true
236 11110 [0,3] - true
237 11110 [1,3] - false
238 \param bv - bit-vector for check
239 \param left - index of first bit start checking
240 \param right - index of last bit
241 \return true/false
242
243 \ingroup bvintervals
244
245 @sa is_all_one_range
246*/
247template<class BV>
248bool is_interval(const BV& bv,
249 typename BV::size_type left,
250 typename BV::size_type right) BMNOEXCEPT
251{
252 typedef typename BV::block_idx_type block_idx_type;
253
254 const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
255
256 if (!bman.is_init())
257 return false; // nothing to do
258
259 if (right < left)
260 bm::xor_swap(left, right);
261 if (left == bm::id_max) // out of range
262 return false;
263 if (right == bm::id_max)
264 --right;
265
266 block_idx_type nblock_left = (left >> bm::set_block_shift);
267 block_idx_type nblock_right = (right >> bm::set_block_shift);
268
269 if (nblock_left == nblock_right) // same block (fast case)
270 {
271 unsigned nbit_left = unsigned(left & bm::set_block_mask);
272 unsigned nbit_right = unsigned(right & bm::set_block_mask);
273 if ((nbit_left > 0) && (nbit_right < bm::gap_max_bits-1))
274 {
275 unsigned i0, j0;
276 bm::get_block_coord(nblock_left, i0, j0);
277 const bm::word_t* block = bman.get_block_ptr(i0, j0);
278 bool b = bm::block_is_interval(block, nbit_left, nbit_right);
279 return b;
280 }
281 }
282 bool is_left, is_right, is_all_one;
283 is_left = left > 0 ? bv.test(left-1) : false;
284 if (is_left == false)
285 {
286 is_right = (right < (bm::id_max - 1)) ? bv.test(right + 1) : false;
287 if (is_left == false && is_right == false)
288 {
289 is_all_one = bv.is_all_one_range(left, right);
290 return is_all_one;
291 }
292 }
293 return false;
294}
295
296
297//----------------------------------------------------------------------------
298
299/*!
300
301 \brief Reverse find index of first 1 bit gap (01110) starting from position
302 Reverse scan for the first 1 in a block of continious 1s.
303 Method employs closed interval semantics: 0[pos..from]
304
305 \param bv - bit-vector for search
306 \param from - position to start reverse search from
307 \param pos - [out] index of the found first 1 bit in a gap of bits
308 \return true if search returned result, false if not found
309 (start point is zero)
310
311 \sa is_interval, find_interval_end
312 \ingroup bvintervals
313*/
314template<class BV>
315bool find_interval_start(const BV& bv,
316 typename BV::size_type from,
317 typename BV::size_type& pos) BMNOEXCEPT
318{
319 typedef typename BV::size_type size_type;
320 typedef typename BV::block_idx_type block_idx_type;
321
322 const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
323
324 if (!bman.is_init())
325 return false; // nothing to do
326 if (!from)
327 {
328 pos = from;
329 return bv.test(from);
330 }
331
332 block_idx_type nb = (from >> bm::set_block_shift);
333 unsigned i0, j0;
334 bm::get_block_coord(nb, i0, j0);
335
336 size_type base_idx;
337 unsigned found_nbit;
338
339 const bm::word_t* block = bman.get_block_ptr(i0, j0);
340 if (!block)
341 return false;
342 unsigned nbit = unsigned(from & bm::set_block_mask);
343 unsigned res = bm::block_find_interval_start(block, nbit, &found_nbit);
344
345 switch (res)
346 {
347 case 0: // not interval
348 return false;
349 case 1: // interval found
350 pos = found_nbit + (nb * bm::gap_max_bits);
351 return true;
352 case 2: // keep scanning
353 base_idx = bm::get_block_start<size_type>(i0, j0);
354 pos = base_idx + found_nbit;
355 if (!nb)
356 return true;
357 break;
358 default:
359 BM_ASSERT(0);
360 } // switch
361
362 --nb;
363 bm::get_block_coord(nb, i0, j0);
364 bm::word_t*** blk_root = bman.top_blocks_root();
365
366 for (unsigned i = i0; true; --i)
367 {
368 bm::word_t** blk_blk = blk_root[i];
369 if (!blk_blk)
370 return true;
371 if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
372 {
374 if (!i)
375 break;
376 continue;
377 }
378 unsigned j = (i == i0) ? j0 : 255;
379 for (; true; --j)
380 {
381 if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
382 {
384 goto loop_j_end; // continue
385 }
386
387 block = blk_blk[j];
388 if (!block)
389 return true;
390
392 bm::gap_max_bits-1, &found_nbit);
393 switch (res)
394 {
395 case 0: // not interval (but it was the interval, so last result
396 return true;
397 case 1: // interval found
398 base_idx = bm::get_block_start<size_type>(i, j);
399 pos = base_idx + found_nbit;
400 return true;
401 case 2: // keep scanning
403 break;
404 default:
405 BM_ASSERT(0);
406 } // switch
407
408 loop_j_end: // continue point
409 if (!j)
410 break;
411 } // for j
412
413 if (!i)
414 break;
415 } // for i
416
417 return true;
418}
419
420
421//----------------------------------------------------------------------------
422
423/*!
424 \brief Reverse find index of first 1 bit gap (01110) starting from position
425 Reverse scan for the first 1 in a block of continious 1s.
426 Method employs closed interval semantics: 0[pos..from]
427
428 \param bv - bit-vector for search
429 \param from - position to start reverse search from
430 \param pos - [out] index of the found first 1 bit in a gap of bits
431 \return true if search returned result, false if not found
432 (start point is zero)
433
434 \sa is_interval, find_interval_end
435 \ingroup bvintervals
436*/
437template <typename BV>
438bool find_interval_end(const BV& bv,
439 typename BV::size_type from,
440 typename BV::size_type & pos) BMNOEXCEPT
441{
442 typedef typename BV::block_idx_type block_idx_type;
443
444 if (from == bm::id_max)
445 return false;
446 const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
447
448 if (!bman.is_init())
449 return false; // nothing to do
450 if (from == bm::id_max-1)
451 {
452 pos = from;
453 return bv.test(from);
454 }
455
456 block_idx_type nb = (from >> bm::set_block_shift);
457 unsigned i0, j0;
458 bm::get_block_coord(nb, i0, j0);
459
460 unsigned found_nbit;
461
462 const bm::word_t* block = bman.get_block_ptr(i0, j0);
463 if (!block)
464 return false;
465 unsigned nbit = unsigned(from & bm::set_block_mask);
466 unsigned res = bm::block_find_interval_end(block, nbit, &found_nbit);
467 switch (res)
468 {
469 case 0: // not interval
470 return false;
471 case 1: // interval found
472 pos = found_nbit + (nb * bm::gap_max_bits);
473 return true;
474 case 2: // keep scanning
475 pos = found_nbit + (nb * bm::gap_max_bits);
476 break;
477 default:
478 BM_ASSERT(0);
479 } // switch
480
482 unsigned i_from, j_from, i_to, j_to;
483 bm::get_block_coord(nblock_right, i_to, j_to);
484 block_idx_type top_size = bman.top_block_size();
485 if (i_to >= top_size)
486 i_to = unsigned(top_size-1);
487
488 ++nb;
489 bm::word_t*** blk_root = bman.top_blocks_root();
490 bm::get_block_coord(nb, i_from, j_from);
491
492 for (unsigned i = i_from; i <= i_to; ++i)
493 {
494 bm::word_t** blk_blk = blk_root[i];
495 if (!blk_blk)
496 return true;
497 if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
498 {
499 if (i > i_from)
500 {
502 continue;
503 }
504 else
505 {
506 // TODO: optimization to avoid scanning rest of the super block
507 }
508 }
509
510 unsigned j = (i == i_from) ? j_from : 0;
511 do
512 {
513 if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
514 {
515 pos += bm::gap_max_bits;
516 continue;
517 }
518
519 block = blk_blk[j];
520 if (!block)
521 return true;
522
523 res = bm::block_find_interval_end(block, 0, &found_nbit);
524 switch (res)
525 {
526 case 0: // not interval (but it was the interval, so last result
527 return true;
528 case 1: // interval found
529 pos += found_nbit+1;
530 return true;
531 case 2: // keep scanning
532 pos += bm::gap_max_bits;
533 break;
534 default:
535 BM_ASSERT(0);
536 } // switch
537 } while (++j < bm::set_sub_array_size);
538 } // for i
539
540 return true;
541}
542
543
544
545//----------------------------------------------------------------------------
546//
547//----------------------------------------------------------------------------
548
549template<typename BV>
552{
553 return interval_.first;
554}
555
556//----------------------------------------------------------------------------
557
558template<typename BV>
561{
562 return interval_.second;
563}
564
565//----------------------------------------------------------------------------
566
567template<typename BV>
569{
570 return (interval_.first != bm::id_max);
571}
572
573//----------------------------------------------------------------------------
574
575template<typename BV>
577{
578 interval_.first = interval_.second = bm::id_max;
579}
580
581//----------------------------------------------------------------------------
582
583template<typename BV>
584bool interval_enumerator<BV>::go_to(size_type pos, bool extend_start)
585{
586 return go_to_impl(pos, extend_start);
587}
588
589//----------------------------------------------------------------------------
590
591template<typename BV>
593{
594 if (!bv_ || !bv_->is_init() || (pos >= bm::id_max))
595 {
596 invalidate();
597 return false;
598 }
599
600 bool found;
601 size_type start_pos;
602
603 // go to prolog: identify the true interval start position
604 //
605 if (extend_start)
606 {
607 found = bm::find_interval_start(*bv_, pos, start_pos);
608 if (!found)
609 {
610 found = bv_->find(pos, start_pos);
611 if (!found)
612 {
613 invalidate();
614 return false;
615 }
616 }
617 }
618 else
619 {
620 found = bv_->find(pos, start_pos);
621 if (!found)
622 {
623 invalidate();
624 return false;
625 }
626 }
627
628 // start position established, start decoding from it
629 interval_.first = pos = start_pos;
630
632 const typename BV::blocks_manager_type& bman = bv_->get_blocks_manager();
633 unsigned i0, j0;
634 bm::get_block_coord(nb, i0, j0);
635 const bm::word_t* block = bman.get_block_ptr(i0, j0);
636 BM_ASSERT(block);
637
638 if (block == FULL_BLOCK_FAKE_ADDR)
639 {
640 // super-long interval, find the end of it
641 found = bm::find_interval_end(*bv_, pos, interval_.second);
642 BM_ASSERT(found);
643 gap_ptr_ = 0;
644 return true;
645 }
646
647 if (BM_IS_GAP(block))
648 {
649 const bm::gap_word_t* BMRESTRICT gap_block = BMGAP_PTR(block);
650 unsigned nbit = unsigned(pos & bm::set_block_mask);
651
652 unsigned is_set;
653 unsigned gap_pos = bm::gap_bfind(gap_block, nbit, &is_set);
654 BM_ASSERT(is_set);
655
656 interval_.second = (nb * bm::gap_max_bits) + gap_block[gap_pos];
657 if (gap_block[gap_pos] == bm::gap_max_bits-1)
658 {
659 // it is the end of the GAP block - run search
660 //
661 if (interval_.second == bm::id_max-1)
662 {
663 gap_ptr_ = 0;
664 return true;
665 }
666 found = bm::find_interval_end(*bv_, interval_.second + 1, start_pos);
667 if (found)
668 interval_.second = start_pos;
669 gap_ptr_ = 0;
670 return true;
671 }
672 gap_ptr_ = gap_block + gap_pos;
673 return true;
674 }
675
676 // bit-block: turn to GAP and position there
677 //
678 if (gap_buf_.size() == 0)
679 {
680 gap_buf_.resize(bm::gap_max_bits+64);
681 }
682 bm::gap_word_t* gap_tmp = gap_buf_.data();
683 unsigned len = bm::bit_to_gap(gap_tmp, block, bm::gap_max_bits+64);
684 BM_ASSERT(len);
685
686
687 size_type base_idx = (nb * bm::gap_max_bits);
688 for (unsigned i = 1; i <= len; ++i)
689 {
690 size_type gap_pos = base_idx + gap_tmp[i];
691 if (gap_pos >= pos)
692 {
693 if (gap_tmp[i] == bm::gap_max_bits - 1)
694 {
695 found = bm::find_interval_end(*bv_, gap_pos, interval_.second);
696 BM_ASSERT(found);
697 gap_ptr_ = 0;
698 return true;
699 }
700
701 gap_ptr_ = &gap_tmp[i];
702 interval_.second = gap_pos;
703 return true;
704 }
705 if (gap_tmp[i] == bm::gap_max_bits - 1)
706 break;
707 } // for
708
709 BM_ASSERT(0);
710
711 return false;
712}
713
714//----------------------------------------------------------------------------
715
716template<typename BV>
718{
719 BM_ASSERT(valid());
720
721 if (interval_.second == bm::id_max-1)
722 {
723 invalidate();
724 return false;
725 }
726 block_idx_type nb = (interval_.first >> bm::set_block_shift);
727
728 bool found;
729 if (gap_ptr_) // in GAP block
730 {
731 ++gap_ptr_; // 0 - GAP
732 if (*gap_ptr_ == bm::gap_max_bits-1) // GAP block end
733 {
734 return go_to_impl(((nb+1) * bm::gap_max_bits), false);
735 }
736 unsigned prev = *gap_ptr_;
737
738 ++gap_ptr_; // 1 - GAP
739 BM_ASSERT(*gap_ptr_ > prev);
740 interval_.first = (nb * bm::gap_max_bits) + prev + 1;
741 if (*gap_ptr_ == bm::gap_max_bits-1) // GAP block end
742 {
743 found = bm::find_interval_end(*bv_, interval_.first, interval_.second);
744 BM_ASSERT(found); (void)found;
745 gap_ptr_ = 0;
746 return true;
747 }
748 interval_.second = (nb * bm::gap_max_bits) + *gap_ptr_;
749 return true;
750 }
751 return go_to_impl(interval_.second + 1, false);
752}
753
754//----------------------------------------------------------------------------
755
756template<typename BV>
758{
759 const BV* bv_tmp = bv_;
760 bv_ = ien.bv_;
761 ien.bv_ = bv_tmp;
762
763 gap_buf_.swap(ien.gap_buf_);
764 bm::xor_swap(interval_.first, ien.interval_.first);
765 bm::xor_swap(interval_.second, ien.interval_.second);
766
767 const bm::gap_word_t* gap_tmp = gap_ptr_;
768 gap_ptr_ = ien.gap_ptr_;
769 ien.gap_ptr_ = gap_tmp;
770}
771
772//----------------------------------------------------------------------------
773//
774//----------------------------------------------------------------------------
775
776
777} // namespace bm
778
779#include "bmundef.h"
780
781#endif
Definitions(internal)
#define BMRESTRICT
Definition bmdef.h:193
#define BMNOEXCEPT
Definition bmdef.h:79
#define BMGAP_PTR(ptr)
Definition bmdef.h:179
#define BM_IS_GAP(ptr)
Definition bmdef.h:181
#define BM_ASSERT
Definition bmdef.h:130
#define FULL_BLOCK_FAKE_ADDR
Definition bmdef.h:149
pre-processor un-defines to avoid global space pollution (internal)
Alloc allocator_type
Definition bm.h:110
blocks_manager_type::block_idx_type block_idx_type
Definition bm.h:113
bm::id_t size_type
Definition bm.h:117
forward iterator class to traverse bit-vector as ranges
Definition bmintervals.h:53
bool operator>=(const interval_enumerator< BV > &ien) const BMNOEXCEPT
const pair_type & get() const BMNOEXCEPT
Get interval pair.
interval_enumerator(const BV &bv, size_type start_pos, bool extend_start)
Construct enumerator for the specified position.
Definition bmintervals.h:89
size_type end() const BMNOEXCEPT
Return interval end/right as bit-vector coordinate 011110 [left..right].
bool go_to_impl(size_type pos, bool extend_start)
bool valid() const BMNOEXCEPT
Returns true if enumerator is valid (false if traversal is done)
interval_enumerator(const BV &bv)
Construct enumerator for the bit-vector.
Definition bmintervals.h:75
bvector_type::size_type size_type
Definition bmintervals.h:59
interval_enumerator(interval_enumerator< BV > &&ien) BMNOEXCEPT
move-ctor
interval_enumerator< BV > & operator=(interval_enumerator< BV > &&ien) BMNOEXCEPT
move assignmment operator
bool operator<(const interval_enumerator< BV > &ien) const BMNOEXCEPT
bvector_type::block_idx_type block_idx_type
interval_enumerator & operator=(const interval_enumerator< BV > &ien)
Assignment operator.
bm::byte_buffer< allocator_type > buffer_type
Definition bmintervals.h:61
bool operator>(const interval_enumerator< BV > &ien) const BMNOEXCEPT
size_type start() const BMNOEXCEPT
Return interval start/left as bit-vector coordinate 011110 [left..right].
std::input_iterator_tag iterator_category
Definition bmintervals.h:56
bm::heap_vector< unsigned short, bv_allocator_type, true > gap_vector_type
interval_enumerator(const interval_enumerator< BV > &ien)
Copy constructor.
Definition bmintervals.h:98
void swap(interval_enumerator< BV > &ien) BMNOEXCEPT
swap enumerator with another one
interval_enumerator< BV > operator++(int) BMNOEXCEPT
Advance enumerator forward to the next available bit.
bvector_type::allocator_type allocator_type
Definition bmintervals.h:60
bm::pair< size_type, size_type > pair_type
Definition bmintervals.h:62
bvector_type::allocator_type bv_allocator_type
bool operator==(const interval_enumerator< BV > &ien) const BMNOEXCEPT
bool operator<=(const interval_enumerator< BV > &ien) const BMNOEXCEPT
void invalidate() BMNOEXCEPT
Turn FSM into invalid state (out of range)
bool go_to(size_type pos, bool extend_start=true)
Go to inetrval at specified position Jump to position with interval. If interval is not available at ...
bool operator!=(const interval_enumerator< BV > &ien) const BMNOEXCEPT
bool find_interval_end(const BV &bv, typename BV::size_type from, typename BV::size_type &pos) BMNOEXCEPT
Reverse find index of first 1 bit gap (01110) starting from position Reverse scan for the first 1 in ...
bool find_interval_start(const BV &bv, typename BV::size_type from, typename BV::size_type &pos) BMNOEXCEPT
Reverse find index of first 1 bit gap (01110) starting from position Reverse scan for the first 1 in ...
bool is_interval(const BV &bv, typename BV::size_type left, typename BV::size_type right) BMNOEXCEPT
Returns true if range is all 1s flanked with 0s Function performs the test on a closed range [left,...
Definition bm.h:77
void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two scalar variables.
Definition bmfunc.h:909
bool block_is_interval(const bm::word_t *const BMRESTRICT block, unsigned left, unsigned right) BMNOEXCEPT
Returns "true" if all bits are 1 in the block [left, right] and border bits are 0.
Definition bmfunc.h:5324
const unsigned id_max
Definition bmconst.h:108
unsigned int word_t
Definition bmconst.h:38
const unsigned set_block_mask
Definition bmconst.h:56
unsigned gap_bfind(const T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set) BMNOEXCEPT
Definition bmfunc.h:1220
BMFORCEINLINE RTYPE get_block_start(unsigned i, unsigned j) BMNOEXCEPT
Compute bit address of the first bit in a block.
Definition bmfunc.h:168
unsigned bit_to_gap(gap_word_t *BMRESTRICT dest, const unsigned *BMRESTRICT block, unsigned dest_len) BMNOEXCEPT
Convert bit block to GAP representation.
Definition bmfunc.h:4248
const unsigned set_sub_array_size
Definition bmconst.h:94
unsigned block_find_interval_start(const bm::word_t *BMRESTRICT block, unsigned nbit_from, unsigned *BMRESTRICT found_nbit) BMNOEXCEPT
Find start of the current 111 interval.
Definition bmfunc.h:5528
BMFORCEINLINE RTYPE get_super_block_start(unsigned i) BMNOEXCEPT
Compute bit address of the first bit in a superblock.
Definition bmfunc.h:158
unsigned short gap_word_t
Definition bmconst.h:77
const unsigned gap_max_bits
Definition bmconst.h:80
void get_block_coord(BI_TYPE nb, unsigned &i, unsigned &j) BMNOEXCEPT
Recalc linear bvector block index into 2D matrix coordinates.
Definition bmfunc.h:147
const unsigned set_block_shift
Definition bmconst.h:55
unsigned block_find_interval_end(const bm::word_t *BMRESTRICT block, unsigned nbit_from, unsigned *BMRESTRICT found_nbit) BMNOEXCEPT
Find end of the current 111 interval.
Definition bmfunc.h:5428
Pair type.
Definition bmfunc.h:122
Second second
Definition bmfunc.h:124
First first
Definition bmfunc.h:123