1#ifndef BMINTERVALS__H__INCLUDED__
2#define BMINTERVALS__H__INCLUDED__
25#ifndef BM__H__INCLUDED__
28# error missing include (bm.h or bm64.h)
109 bv_ = ien.bv_; gap_ptr_ = 0;
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()); }
212 typedef bm::heap_vector<unsigned short, bv_allocator_type, true>
254 const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
269 if (nblock_left == nblock_right)
277 const bm::word_t* block = bman.get_block_ptr(i0, j0);
282 bool is_left, is_right, is_all_one;
283 is_left = left > 0 ? bv.test(left-1) :
false;
284 if (is_left ==
false)
286 is_right = (right < (
bm::id_max - 1)) ? bv.test(right + 1) :
false;
287 if (is_left ==
false && is_right ==
false)
289 is_all_one = bv.is_all_one_range(left, right);
316 typename BV::size_type from,
319 typedef typename BV::size_type
size_type;
322 const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
329 return bv.test(from);
339 const bm::word_t* block = bman.get_block_ptr(i0, j0);
353 base_idx = bm::get_block_start<size_type>(i0, j0);
354 pos = base_idx + found_nbit;
364 bm::word_t*** blk_root = bman.top_blocks_root();
366 for (
unsigned i = i0;
true; --i)
373 pos = bm::get_super_block_start<size_type>(i);
378 unsigned j = (i == i0) ? j0 : 255;
383 pos = bm::get_block_start<size_type>(i, j);
398 base_idx = bm::get_block_start<size_type>(i, j);
399 pos = base_idx + found_nbit;
402 pos = bm::get_block_start<size_type>(i, j);
437template <
typename BV>
439 typename BV::size_type from,
446 const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
453 return bv.test(from);
462 const bm::word_t* block = bman.get_block_ptr(i0, j0);
482 unsigned i_from, j_from, i_to, j_to;
485 if (i_to >= top_size)
486 i_to = unsigned(top_size-1);
489 bm::word_t*** blk_root = bman.top_blocks_root();
492 for (
unsigned i = i_from; i <= i_to; ++i)
510 unsigned j = (i == i_from) ? j_from : 0;
553 return interval_.
first;
594 if (!bv_ || !bv_->is_init() || (pos >=
bm::id_max))
610 found = bv_->find(pos, start_pos);
620 found = bv_->find(pos, start_pos);
629 interval_.
first = pos = start_pos;
632 const typename BV::blocks_manager_type& bman = bv_->get_blocks_manager();
635 const bm::word_t* block = bman.get_block_ptr(i0, j0);
668 interval_.
second = start_pos;
672 gap_ptr_ = gap_block + gap_pos;
678 if (gap_buf_.size() == 0)
688 for (
unsigned i = 1; i <= len; ++i)
690 size_type gap_pos = base_idx + gap_tmp[i];
701 gap_ptr_ = &gap_tmp[i];
702 interval_.
second = gap_pos;
736 unsigned prev = *gap_ptr_;
759 const BV* bv_tmp = bv_;
763 gap_buf_.swap(ien.gap_buf_);
768 gap_ptr_ = ien.gap_ptr_;
769 ien.gap_ptr_ = gap_tmp;
#define FULL_BLOCK_FAKE_ADDR
bvector_size_type size_type
blocks_manager_type::block_idx_type block_idx_type
forward iterator class to traverse bit-vector as ranges
bool operator>=(const interval_enumerator< BV > &ien) const BMNOEXCEPT
std::input_iterator_tag iterator_category
bvector_type::block_idx_type block_idx_type
interval_enumerator(const BV &bv, size_type start_pos, bool extend_start)
Construct enumerator for the specified position.
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)
bm::pair< size_type, size_type > pair_type
bm::byte_buffer< allocator_type > buffer_type
interval_enumerator(const BV &bv)
Construct enumerator for the bit-vector.
const pair_type & get() const BMNOEXCEPT
Get interval pair.
interval_enumerator(interval_enumerator< BV > &&ien) BMNOEXCEPT
move-ctor
interval_enumerator & operator=(const interval_enumerator< BV > &ien)
Assignment operator.
bool operator<(const interval_enumerator< BV > &ien) const BMNOEXCEPT
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].
interval_enumerator(const interval_enumerator< BV > &ien)
Copy constructor.
bm::heap_vector< unsigned short, bv_allocator_type, true > gap_vector_type
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 bv_allocator_type
bvector_type::size_type size_type
interval_enumerator< BV > & operator=(interval_enumerator< BV > &&ien) BMNOEXCEPT
move assignmment operator
bvector_type::allocator_type 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,...
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.
const unsigned set_block_mask
unsigned gap_bfind(const T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set) BMNOEXCEPT
unsigned bit_to_gap(gap_word_t *BMRESTRICT dest, const unsigned *BMRESTRICT block, unsigned dest_len) BMNOEXCEPT
Convert bit block to GAP representation.
const unsigned set_sub_array_size
BMFORCEINLINE void get_block_coord(BI_TYPE nb, unsigned &i, unsigned &j) BMNOEXCEPT
Recalc linear bvector block index into 2D matrix coordinates.
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.
BMFORCEINLINE void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two variables.
unsigned short gap_word_t
const unsigned gap_max_bits
const unsigned set_block_shift
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.