BitMagic-C++
bmintervals.h
Go to the documentation of this file.
1 #ifndef BMINTERVALS__H__INCLUDED__
2 #define BMINTERVALS__H__INCLUDED__
3 
4 /*
5 Copyright(c) 2002-2020 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
6 
7 Licensed under the Apache License, Version 2.0 (the "License");
8 you may not use this file except in compliance with the License.
9 You may obtain a copy of the License at
10 
11  http://www.apache.org/licenses/LICENSE-2.0
12 
13 Unless required by applicable law or agreed to in writing, software
14 distributed under the License is distributed on an "AS IS" BASIS,
15 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 See the License for the specific language governing permissions and
17 limitations under the License.
18 
19 For 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 
39 namespace 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 */
51 template<typename BV>
53 {
54 public:
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 
64 public:
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 */
192  interval_enumerator<BV>& operator++() BMNOEXCEPT
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 
209 protected:
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 
221 private:
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 */
247 template<class BV>
248 bool 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 */
314 template<class BV>
315 bool 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  {
373  pos = bm::get_super_block_start<size_type>(i);
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  {
383  pos = bm::get_block_start<size_type>(i, j);
384  goto loop_j_end; // continue
385  }
386 
387  block = blk_blk[j];
388  if (!block)
389  return true;
390 
391  res = bm::block_find_interval_start(block,
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
402  pos = bm::get_block_start<size_type>(i, j);
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 */
437 template <typename BV>
438 bool 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 
481  block_idx_type nblock_right = (bm::id_max >> bm::set_block_shift);
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 
549 template<typename BV>
552 {
553  return interval_.first;
554 }
555 
556 //----------------------------------------------------------------------------
557 
558 template<typename BV>
561 {
562  return interval_.second;
563 }
564 
565 //----------------------------------------------------------------------------
566 
567 template<typename BV>
569 {
570  return (interval_.first != bm::id_max);
571 }
572 
573 //----------------------------------------------------------------------------
574 
575 template<typename BV>
577 {
578  interval_.first = interval_.second = bm::id_max;
579 }
580 
581 //----------------------------------------------------------------------------
582 
583 template<typename BV>
584 bool interval_enumerator<BV>::go_to(size_type pos, bool extend_start)
585 {
586  return go_to_impl(pos, extend_start);
587 }
588 
589 //----------------------------------------------------------------------------
590 
591 template<typename BV>
592 bool interval_enumerator<BV>::go_to_impl(size_type pos, bool extend_start)
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 
631  block_idx_type nb = (pos >> bm::set_block_shift);
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 
716 template<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 
756 template<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
bm::interval_enumerator::gap_vector_type
bm::heap_vector< unsigned short, bv_allocator_type, true > gap_vector_type
Definition: bmintervals.h:213
bm::interval_enumerator::size_type
bvector_type::size_type size_type
Definition: bmintervals.h:59
bm::block_find_interval_start
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:5613
bm::interval_enumerator::go_to
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 ...
Definition: bmintervals.h:584
BM_IS_GAP
#define BM_IS_GAP(ptr)
Definition: bmdef.h:181
bm::pair::first
First first
Definition: bmfunc.h:123
bm::interval_enumerator::swap
void swap(interval_enumerator< BV > &ien) BMNOEXCEPT
swap enumerator with another one
Definition: bmintervals.h:757
BMGAP_PTR
#define BMGAP_PTR(ptr)
Definition: bmdef.h:179
bm::interval_enumerator::interval_enumerator
interval_enumerator()
Definition: bmintervals.h:68
bm::block_is_interval
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:5348
bm::find_interval_start
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 ...
Definition: bmintervals.h:315
bm::bvector::allocator_type
Alloc allocator_type
Definition: bm.h:110
bm::set_sub_array_size
const unsigned set_sub_array_size
Definition: bmconst.h:94
bm::interval_enumerator::end
size_type end() const BMNOEXCEPT
Return interval end/right as bit-vector coordinate 011110 [left..right].
Definition: bmintervals.h:560
bm::interval_enumerator::iterator_category
std::input_iterator_tag iterator_category
Definition: bmintervals.h:56
bm::interval_enumerator::operator==
bool operator==(const interval_enumerator< BV > &ien) const BMNOEXCEPT
Definition: bmintervals.h:138
bmundef.h
pre-processor un-defines to avoid global space pollution (internal)
bm::get_block_coord
BMFORCEINLINE void get_block_coord(BI_TYPE nb, unsigned &i, unsigned &j) BMNOEXCEPT
Recalc linear bvector block index into 2D matrix coordinates.
Definition: bmfunc.h:148
bm::interval_enumerator::interval_enumerator
interval_enumerator(interval_enumerator< BV > &&ien) BMNOEXCEPT
move-ctor
Definition: bmintervals.h:115
bm::pair< size_type, size_type >
bm::id_max
const unsigned id_max
Definition: bmconst.h:108
bm::set_block_mask
const unsigned set_block_mask
Definition: bmconst.h:56
bm::xor_swap
void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two scalar variables.
Definition: bmfunc.h:911
bm::interval_enumerator::start
size_type start() const BMNOEXCEPT
Return interval start/left as bit-vector coordinate 011110 [left..right].
Definition: bmintervals.h:551
bm::interval_enumerator::interval_enumerator
interval_enumerator(const BV &bv, size_type start_pos, bool extend_start)
Construct enumerator for the specified position.
Definition: bmintervals.h:89
bm::interval_enumerator::advance
bool advance()
Definition: bmintervals.h:717
BMNOEXCEPT
#define BMNOEXCEPT
Definition: bmdef.h:79
FULL_BLOCK_FAKE_ADDR
#define FULL_BLOCK_FAKE_ADDR
Definition: bmdef.h:149
bm::interval_enumerator::get
const pair_type & get() const BMNOEXCEPT
Get interval pair.
Definition: bmintervals.h:161
bm::gap_word_t
unsigned short gap_word_t
Definition: bmconst.h:77
bm::interval_enumerator::bv_allocator_type
bvector_type::allocator_type bv_allocator_type
Definition: bmintervals.h:211
bm::interval_enumerator::pair_type
bm::pair< size_type, size_type > pair_type
Definition: bmintervals.h:62
BM_ASSERT
#define BM_ASSERT
Definition: bmdef.h:130
bm::interval_enumerator::operator>=
bool operator>=(const interval_enumerator< BV > &ien) const BMNOEXCEPT
Definition: bmintervals.h:148
bm::interval_enumerator::block_idx_type
bvector_type::block_idx_type block_idx_type
Definition: bmintervals.h:210
bmdef.h
Definitions(internal)
bm::interval_enumerator::interval_enumerator
interval_enumerator(const interval_enumerator< BV > &ien)
Copy constructor.
Definition: bmintervals.h:98
bm::block_find_interval_end
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:5452
bm::bit_to_gap
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:4268
bm::interval_enumerator::operator<
bool operator<(const interval_enumerator< BV > &ien) const BMNOEXCEPT
Definition: bmintervals.h:142
bm::interval_enumerator::interval_enumerator
interval_enumerator(const BV &bv)
Construct enumerator for the bit-vector.
Definition: bmintervals.h:75
bm::gap_max_bits
const unsigned gap_max_bits
Definition: bmconst.h:80
bm::interval_enumerator::operator>
bool operator>(const interval_enumerator< BV > &ien) const BMNOEXCEPT
Definition: bmintervals.h:146
bm::interval_enumerator::operator=
interval_enumerator< BV > & operator=(interval_enumerator< BV > &&ien) BMNOEXCEPT
move assignmment operator
Definition: bmintervals.h:122
bm::gap_bfind
unsigned gap_bfind(const T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set) BMNOEXCEPT
Definition: bmfunc.h:1222
bm::interval_enumerator::operator<=
bool operator<=(const interval_enumerator< BV > &ien) const BMNOEXCEPT
Definition: bmintervals.h:144
bm::pair::second
Second second
Definition: bmfunc.h:124
bm::set_block_shift
const unsigned set_block_shift
Definition: bmconst.h:55
bm
Definition: bm.h:76
bm::bvector::block_idx_type
blocks_manager_type::block_idx_type block_idx_type
Definition: bm.h:113
bm::interval_enumerator::valid
bool valid() const BMNOEXCEPT
Returns true if enumerator is valid (false if traversal is done)
Definition: bmintervals.h:568
bm::interval_enumerator::operator=
interval_enumerator & operator=(const interval_enumerator< BV > &ien)
Assignment operator.
Definition: bmintervals.h:107
bm::interval_enumerator::buffer_type
bm::byte_buffer< allocator_type > buffer_type
Definition: bmintervals.h:61
bm::interval_enumerator::operator!=
bool operator!=(const interval_enumerator< BV > &ien) const BMNOEXCEPT
Definition: bmintervals.h:140
bm::interval_enumerator::operator++
interval_enumerator< BV > operator++(int) BMNOEXCEPT
Advance enumerator forward to the next available bit.
Definition: bmintervals.h:196
bm::interval_enumerator
forward iterator class to traverse bit-vector as ranges
Definition: bmintervals.h:52
bm::interval_enumerator::bvector_type
BV bvector_type
Definition: bmintervals.h:58
bm::word_t
unsigned int word_t
Definition: bmconst.h:38
BMRESTRICT
#define BMRESTRICT
Definition: bmdef.h:193
bm::interval_enumerator::allocator_type
bvector_type::allocator_type allocator_type
Definition: bmintervals.h:60
bm::bvector::size_type
bm::id_t size_type
Definition: bm.h:117
bm::interval_enumerator::invalidate
void invalidate() BMNOEXCEPT
Turn FSM into invalid state (out of range)
Definition: bmintervals.h:576
bm::interval_enumerator::go_to_impl
bool go_to_impl(size_type pos, bool extend_start)
Definition: bmintervals.h:592
bm::find_interval_end
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 ...
Definition: bmintervals.h:438
bm::is_interval
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: bmintervals.h:248