bmintervals.h
Go to the documentation of this file.
#ifndef BMINTERVALS__H__INCLUDED__
#define BMINTERVALS__H__INCLUDED__
/*
Copyright(c) 2002-2020 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
For more information please visit: http://bitmagic.io
*/
/*! \file bmintervals.h
\brief Algorithms for bit ranges and intervals
*/
#ifndef BM__H__INCLUDED__
// BitMagic utility headers do not include main "bm.h" declaration
// #include "bm.h" or "bm64.h" explicitly
# error missing include (bm.h or bm64.h)
#endif
#include "bmdef.h"
/** \defgroup bvintervals Algorithms for bit intervals
Algorithms and iterators for bit ranges and intervals
@ingroup bvector
*/
namespace bm
{
/*!
\brief forward iterator class to traverse bit-vector as ranges
Traverse enumerator for forward walking bit-vector as intervals:
series of consequtive 1111s flanked with zeroes.
Enumerator can traverse the whole bit-vector or jump(go_to) to position.
\ingroup bvintervals
*/
template<typename BV>
class interval_enumerator
{
public:
#ifndef BM_NO_STL
typedef std::input_iterator_tag iterator_category;
#endif
typedef BV bvector_type;
typedef typename bvector_type::size_type size_type;
typedef typename bvector_type::allocator_type allocator_type;
typedef bm::byte_buffer<allocator_type> buffer_type;
typedef bm::pair<size_type, size_type> pair_type;
public:
/*! @name Construction and assignment */
//@{
interval_enumerator()
: bv_(0), interval_(bm::id_max, bm::id_max), gap_ptr_(0)
{}
/**
Construct enumerator for the bit-vector
*/
interval_enumerator(const BV& bv)
: bv_(&bv), interval_(bm::id_max, bm::id_max), gap_ptr_(0)
{
go_to_impl(0, false);
}
/**
Construct enumerator for the specified position
@param bv - source bit-vector
@param start_pos - position on bit-vector to search for interval
@param extend_start - flag to extend interval start to the start if
true start happenes to be less than start_pos
@sa go_to
*/
interval_enumerator(const BV& bv, size_type start_pos, bool extend_start)
: bv_(&bv), interval_(bm::id_max, bm::id_max), gap_ptr_(0)
{
go_to_impl(start_pos, extend_start);
}
/**
Copy constructor
*/
interval_enumerator(const interval_enumerator<BV>& ien)
: bv_(ien.bv_), interval_(bm::id_max, bm::id_max), gap_ptr_(0)
{
go_to_impl(ien.start(), false);
}
/**
Assignment operator
*/
interval_enumerator& operator=(const interval_enumerator<BV>& ien)
{
bv_ = ien.bv_; gap_ptr_ = 0;
go_to_impl(ien.start(), false);
}
#ifndef BM_NO_CXX11
/** move-ctor */
interval_enumerator(interval_enumerator<BV>&& ien) BMNOEXCEPT
: bv_(0), interval_(bm::id_max, bm::id_max), gap_ptr_(0)
{
this->swap(ien);
}
/** move assignmment operator */
interval_enumerator<BV>& operator=(interval_enumerator<BV>&& ien) BMNOEXCEPT
{
if (this != &ien)
this->swap(ien);
return *this;
}
#endif
//@}
// -----------------------------------------------------------------
/*! @name Comparison methods all use start position to compare */
//@{
bool operator==(const interval_enumerator<BV>& ien) const BMNOEXCEPT
{ return (start() == ien.start()); }
bool operator!=(const interval_enumerator<BV>& ien) const BMNOEXCEPT
{ return (start() != ien.start()); }
bool operator < (const interval_enumerator<BV>& ien) const BMNOEXCEPT
{ return (start() < ien.start()); }
bool operator <= (const interval_enumerator<BV>& ien) const BMNOEXCEPT
{ return (start() <= ien.start()); }
bool operator > (const interval_enumerator<BV>& ien) const BMNOEXCEPT
{ return (start() > ien.start()); }
bool operator >= (const interval_enumerator<BV>& ien) const BMNOEXCEPT
{ return (start() >= ien.start()); }
//@}
/// Return interval start/left as bit-vector coordinate 011110 [left..right]
size_type start() const BMNOEXCEPT;
/// Return interval end/right as bit-vector coordinate 011110 [left..right]
size_type end() const BMNOEXCEPT;
const pair_type& operator*() const BMNOEXCEPT { return interval_; }
/// Get interval pair
const pair_type& get() const BMNOEXCEPT { return interval_; }
/// Returns true if enumerator is valid (false if traversal is done)
bool valid() const BMNOEXCEPT;
// -----------------------------------------------------------------
/*! @name enumerator positioning */
//@{
/*!
@brief Go to inetrval at specified position
Jump to position with interval. If interval is not available at
the specified position (o bit) enumerator will find the next interval.
If interval is present we have an option to find interval start [left..]
and set enumerator from the effective start coodrinate
@param pos - position on bit-vector
@param extend_start - find effective start if it is less than the
go to position
@return true if enumerator remains valid after the jump
*/
bool go_to(size_type pos, bool extend_start = true);
/*! Advance to the next interval
@return true if interval is available
@sa valid
*/
bool advance();
/*! \brief Advance enumerator forward to the next available bit */
interval_enumerator<BV>& operator++() BMNOEXCEPT
{ advance(); return *this; }
/*! \brief Advance enumerator forward to the next available bit */
interval_enumerator<BV> operator++(int) BMNOEXCEPT
{
interval_enumerator<BV> tmp = *this;
advance();
return tmp;
}
//@}
/**
swap enumerator with another one
*/
void swap(interval_enumerator<BV>& ien) BMNOEXCEPT;
protected:
typedef typename bvector_type::block_idx_type block_idx_type;
typedef typename bvector_type::allocator_type bv_allocator_type;
typedef bm::heap_vector<unsigned short, bv_allocator_type, true>
gap_vector_type;
bool go_to_impl(size_type pos, bool extend_start);
/// Turn FSM into invalid state (out of range)
void invalidate() BMNOEXCEPT;
private:
const BV* bv_; ///!< bit-vector for traversal
gap_vector_type gap_buf_; ///!< GAP buf.vector for bit-block
pair_type interval_; ///! current inetrval
const bm::gap_word_t* gap_ptr_; ///!< current pointer in GAP block
};
//----------------------------------------------------------------------------
/*!
\brief Returns true if range is all 1s flanked with 0s
Function performs the test on a closed range [left, right]
true interval is all 1s AND test(left-1)==false AND test(right+1)==false
Examples:
01110 [1,3] - true
11110 [0,3] - true
11110 [1,3] - false
\param bv - bit-vector for check
\param left - index of first bit start checking
\param right - index of last bit
\return true/false
\ingroup bvintervals
@sa is_all_one_range
*/
template<class BV>
bool is_interval(const BV& bv,
typename BV::size_type left,
typename BV::size_type right) BMNOEXCEPT
{
typedef typename BV::block_idx_type block_idx_type;
const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
if (!bman.is_init())
return false; // nothing to do
if (right < left)
bm::xor_swap(left, right);
if (left == bm::id_max) // out of range
return false;
if (right == bm::id_max)
--right;
block_idx_type nblock_left = (left >> bm::set_block_shift);
block_idx_type nblock_right = (right >> bm::set_block_shift);
if (nblock_left == nblock_right) // same block (fast case)
{
unsigned nbit_left = unsigned(left & bm::set_block_mask);
unsigned nbit_right = unsigned(right & bm::set_block_mask);
if ((nbit_left > 0) && (nbit_right < bm::gap_max_bits-1))
{
unsigned i0, j0;
bm::get_block_coord(nblock_left, i0, j0);
const bm::word_t* block = bman.get_block_ptr(i0, j0);
bool b = bm::block_is_interval(block, nbit_left, nbit_right);
return b;
}
}
bool is_left, is_right, is_all_one;
is_left = left > 0 ? bv.test(left-1) : false;
if (is_left == false)
{
is_right = (right < (bm::id_max - 1)) ? bv.test(right + 1) : false;
if (is_left == false && is_right == false)
{
is_all_one = bv.is_all_one_range(left, right);
return is_all_one;
}
}
return false;
}
//----------------------------------------------------------------------------
/*!
\brief Reverse find index of first 1 bit gap (01110) starting from position
Reverse scan for the first 1 in a block of continious 1s.
Method employs closed interval semantics: 0[pos..from]
\param bv - bit-vector for search
\param from - position to start reverse search from
\param pos - [out] index of the found first 1 bit in a gap of bits
\return true if search returned result, false if not found
(start point is zero)
\sa is_interval, find_interval_end
\ingroup bvintervals
*/
template<class BV>
bool find_interval_start(const BV& bv,
typename BV::size_type from,
typename BV::size_type& pos) BMNOEXCEPT
{
typedef typename BV::size_type size_type;
typedef typename BV::block_idx_type block_idx_type;
const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
if (!bman.is_init())
return false; // nothing to do
if (!from)
{
pos = from;
return bv.test(from);
}
block_idx_type nb = (from >> bm::set_block_shift);
unsigned i0, j0;
bm::get_block_coord(nb, i0, j0);
size_type base_idx;
unsigned found_nbit;
const bm::word_t* block = bman.get_block_ptr(i0, j0);
if (!block)
return false;
unsigned nbit = unsigned(from & bm::set_block_mask);
unsigned res = bm::block_find_interval_start(block, nbit, &found_nbit);
switch (res)
{
case 0: // not interval
return false;
case 1: // interval found
pos = found_nbit + (nb * bm::gap_max_bits);
return true;
case 2: // keep scanning
base_idx = bm::get_block_start<size_type>(i0, j0);
pos = base_idx + found_nbit;
if (!nb)
return true;
break;
default:
BM_ASSERT(0);
} // switch
--nb;
bm::get_block_coord(nb, i0, j0);
bm::word_t*** blk_root = bman.top_blocks_root();
for (unsigned i = i0; true; --i)
{
bm::word_t** blk_blk = blk_root[i];
if (!blk_blk)
return true;
if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
{
pos = bm::get_super_block_start<size_type>(i);
if (!i)
break;
continue;
}
unsigned j = (i == i0) ? j0 : 255;
for (; true; --j)
{
if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
{
pos = bm::get_block_start<size_type>(i, j);
goto loop_j_end; // continue
}
block = blk_blk[j];
if (!block)
return true;
res = bm::block_find_interval_start(block,
bm::gap_max_bits-1, &found_nbit);
switch (res)
{
case 0: // not interval (but it was the interval, so last result
return true;
case 1: // interval found
base_idx = bm::get_block_start<size_type>(i, j);
pos = base_idx + found_nbit;
return true;
case 2: // keep scanning
pos = bm::get_block_start<size_type>(i, j);
break;
default:
BM_ASSERT(0);
} // switch
loop_j_end: // continue point
if (!j)
break;
} // for j
if (!i)
break;
} // for i
return true;
}
//----------------------------------------------------------------------------
/*!
\brief Reverse find index of first 1 bit gap (01110) starting from position
Reverse scan for the first 1 in a block of continious 1s.
Method employs closed interval semantics: 0[pos..from]
\param bv - bit-vector for search
\param from - position to start reverse search from
\param pos - [out] index of the found first 1 bit in a gap of bits
\return true if search returned result, false if not found
(start point is zero)
\sa is_interval, find_interval_end
\ingroup bvintervals
*/
template <typename BV>
bool find_interval_end(const BV& bv,
typename BV::size_type from,
typename BV::size_type & pos) BMNOEXCEPT
{
typedef typename BV::block_idx_type block_idx_type;
if (from == bm::id_max)
return false;
const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
if (!bman.is_init())
return false; // nothing to do
if (from == bm::id_max-1)
{
pos = from;
return bv.test(from);
}
block_idx_type nb = (from >> bm::set_block_shift);
unsigned i0, j0;
bm::get_block_coord(nb, i0, j0);
unsigned found_nbit;
const bm::word_t* block = bman.get_block_ptr(i0, j0);
if (!block)
return false;
unsigned nbit = unsigned(from & bm::set_block_mask);
unsigned res = bm::block_find_interval_end(block, nbit, &found_nbit);
switch (res)
{
case 0: // not interval
return false;
case 1: // interval found
pos = found_nbit + (nb * bm::gap_max_bits);
return true;
case 2: // keep scanning
pos = found_nbit + (nb * bm::gap_max_bits);
break;
default:
BM_ASSERT(0);
} // switch
block_idx_type nblock_right = (bm::id_max >> bm::set_block_shift);
unsigned i_from, j_from, i_to, j_to;
bm::get_block_coord(nblock_right, i_to, j_to);
block_idx_type top_size = bman.top_block_size();
if (i_to >= top_size)
i_to = unsigned(top_size-1);
++nb;
bm::word_t*** blk_root = bman.top_blocks_root();
bm::get_block_coord(nb, i_from, j_from);
for (unsigned i = i_from; i <= i_to; ++i)
{
bm::word_t** blk_blk = blk_root[i];
if (!blk_blk)
return true;
if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
{
if (i > i_from)
{
pos += bm::gap_max_bits * bm::set_sub_array_size;
continue;
}
else
{
// TODO: optimization to avoid scanning rest of the super block
}
}
unsigned j = (i == i_from) ? j_from : 0;
do
{
if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
{
pos += bm::gap_max_bits;
continue;
}
block = blk_blk[j];
if (!block)
return true;
res = bm::block_find_interval_end(block, 0, &found_nbit);
switch (res)
{
case 0: // not interval (but it was the interval, so last result
return true;
case 1: // interval found
pos += found_nbit+1;
return true;
case 2: // keep scanning
pos += bm::gap_max_bits;
break;
default:
BM_ASSERT(0);
} // switch
} while (++j < bm::set_sub_array_size);
} // for i
return true;
}
//----------------------------------------------------------------------------
//
//----------------------------------------------------------------------------
template<typename BV>
typename interval_enumerator<BV>::size_type
interval_enumerator<BV>::start() const BMNOEXCEPT
{
return interval_.first;
}
//----------------------------------------------------------------------------
template<typename BV>
typename interval_enumerator<BV>::size_type
interval_enumerator<BV>::end() const BMNOEXCEPT
{
return interval_.second;
}
//----------------------------------------------------------------------------
template<typename BV>
bool interval_enumerator<BV>::valid() const BMNOEXCEPT
{
return (interval_.first != bm::id_max);
}
//----------------------------------------------------------------------------
template<typename BV>
void interval_enumerator<BV>::invalidate() BMNOEXCEPT
{
interval_.first = interval_.second = bm::id_max;
}
//----------------------------------------------------------------------------
template<typename BV>
bool interval_enumerator<BV>::go_to(size_type pos, bool extend_start)
{
return go_to_impl(pos, extend_start);
}
//----------------------------------------------------------------------------
template<typename BV>
bool interval_enumerator<BV>::go_to_impl(size_type pos, bool extend_start)
{
if (!bv_ || !bv_->is_init() || (pos >= bm::id_max))
{
invalidate();
return false;
}
bool found;
size_type start_pos;
// go to prolog: identify the true interval start position
//
if (extend_start)
{
found = bm::find_interval_start(*bv_, pos, start_pos);
if (!found)
{
found = bv_->find(pos, start_pos);
if (!found)
{
invalidate();
return false;
}
}
}
else
{
found = bv_->find(pos, start_pos);
if (!found)
{
invalidate();
return false;
}
}
// start position established, start decoding from it
interval_.first = pos = start_pos;
block_idx_type nb = (pos >> bm::set_block_shift);
const typename BV::blocks_manager_type& bman = bv_->get_blocks_manager();
unsigned i0, j0;
bm::get_block_coord(nb, i0, j0);
const bm::word_t* block = bman.get_block_ptr(i0, j0);
BM_ASSERT(block);
if (block == FULL_BLOCK_FAKE_ADDR)
{
// super-long interval, find the end of it
found = bm::find_interval_end(*bv_, pos, interval_.second);
BM_ASSERT(found);
gap_ptr_ = 0;
return true;
}
if (BM_IS_GAP(block))
{
const bm::gap_word_t* BMRESTRICT gap_block = BMGAP_PTR(block);
unsigned nbit = unsigned(pos & bm::set_block_mask);
unsigned is_set;
unsigned gap_pos = bm::gap_bfind(gap_block, nbit, &is_set);
BM_ASSERT(is_set);
interval_.second = (nb * bm::gap_max_bits) + gap_block[gap_pos];
if (gap_block[gap_pos] == bm::gap_max_bits-1)
{
// it is the end of the GAP block - run search
//
if (interval_.second == bm::id_max-1)
{
gap_ptr_ = 0;
return true;
}
found = bm::find_interval_end(*bv_, interval_.second + 1, start_pos);
if (found)
interval_.second = start_pos;
gap_ptr_ = 0;
return true;
}
gap_ptr_ = gap_block + gap_pos;
return true;
}
// bit-block: turn to GAP and position there
//
if (gap_buf_.size() == 0)
{
gap_buf_.resize(bm::gap_max_bits+64);
}
bm::gap_word_t* gap_tmp = gap_buf_.data();
unsigned len = bm::bit_to_gap(gap_tmp, block, bm::gap_max_bits+64);
BM_ASSERT(len);
size_type base_idx = (nb * bm::gap_max_bits);
for (unsigned i = 1; i <= len; ++i)
{
size_type gap_pos = base_idx + gap_tmp[i];
if (gap_pos >= pos)
{
if (gap_tmp[i] == bm::gap_max_bits - 1)
{
found = bm::find_interval_end(*bv_, gap_pos, interval_.second);
BM_ASSERT(found);
gap_ptr_ = 0;
return true;
}
gap_ptr_ = &gap_tmp[i];
interval_.second = gap_pos;
return true;
}
if (gap_tmp[i] == bm::gap_max_bits - 1)
break;
} // for
BM_ASSERT(0);
return false;
}
//----------------------------------------------------------------------------
template<typename BV>
bool interval_enumerator<BV>::advance()
{
BM_ASSERT(valid());
if (interval_.second == bm::id_max-1)
{
invalidate();
return false;
}
block_idx_type nb = (interval_.first >> bm::set_block_shift);
bool found;
if (gap_ptr_) // in GAP block
{
++gap_ptr_; // 0 - GAP
if (*gap_ptr_ == bm::gap_max_bits-1) // GAP block end
{
return go_to_impl(((nb+1) * bm::gap_max_bits), false);
}
unsigned prev = *gap_ptr_;
++gap_ptr_; // 1 - GAP
BM_ASSERT(*gap_ptr_ > prev);
interval_.first = (nb * bm::gap_max_bits) + prev + 1;
if (*gap_ptr_ == bm::gap_max_bits-1) // GAP block end
{
found = bm::find_interval_end(*bv_, interval_.first, interval_.second);
BM_ASSERT(found); (void)found;
gap_ptr_ = 0;
return true;
}
interval_.second = (nb * bm::gap_max_bits) + *gap_ptr_;
return true;
}
return go_to_impl(interval_.second + 1, false);
}
//----------------------------------------------------------------------------
template<typename BV>
void interval_enumerator<BV>::swap(interval_enumerator<BV>& ien) BMNOEXCEPT
{
const BV* bv_tmp = bv_;
bv_ = ien.bv_;
ien.bv_ = bv_tmp;
gap_buf_.swap(ien.gap_buf_);
bm::xor_swap(interval_.first, ien.interval_.first);
bm::xor_swap(interval_.second, ien.interval_.second);
const bm::gap_word_t* gap_tmp = gap_ptr_;
gap_ptr_ = ien.gap_ptr_;
ien.gap_ptr_ = gap_tmp;
}
//----------------------------------------------------------------------------
//
//----------------------------------------------------------------------------
} // namespace bm
#endif
bmdef.h
Definitions(internal).
BMRESTRICT
#define BMRESTRICT
Definition bmdef.h:203
BMNOEXCEPT
#define BMNOEXCEPT
Definition bmdef.h:82
BMGAP_PTR
#define BMGAP_PTR(ptr)
Definition bmdef.h:189
BM_IS_GAP
#define BM_IS_GAP(ptr)
Definition bmdef.h:191
BM_ASSERT
#define BM_ASSERT
Definition bmdef.h:139
FULL_BLOCK_FAKE_ADDR
#define FULL_BLOCK_FAKE_ADDR
Definition bmdef.h:158
bm::size_type
bm::bvector::get_blocks_manager
const blocks_manager_type & get_blocks_manager() const BMNOEXCEPT
get access to memory manager (internal) Use only if you are BitMagic library
Definition bm.h:2058
bm::bvector::size_type
bvector_size_type size_type
Definition bm.h:121
bm::bvector::block_idx_type
blocks_manager_type::block_idx_type block_idx_type
Definition bm.h:120
bm::bvector::allocator_type
Alloc allocator_type
Definition bm.h:117
bm::interval_enumerator::operator>=
bool operator>=(const interval_enumerator< BV > &ien) const BMNOEXCEPT
Definition bmintervals.h:148
bm::interval_enumerator::iterator_category
std::input_iterator_tag iterator_category
Definition bmintervals.h:56
bm::interval_enumerator::get
const pair_type & get() const BMNOEXCEPT
Get interval pair.
Definition bmintervals.h:161
bm::interval_enumerator::block_idx_type
bvector_type::block_idx_type block_idx_type
Definition bmintervals.h:210
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< bm::bvector<> >::end
size_type end() const BMNOEXCEPT
bm::interval_enumerator::go_to_impl
bool go_to_impl(size_type pos, bool extend_start)
Definition bmintervals.h:592
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::pair_type
bm::pair< size_type, size_type > pair_type
Definition bmintervals.h:62
bm::interval_enumerator::buffer_type
bm::byte_buffer< allocator_type > buffer_type
Definition bmintervals.h:61
bm::interval_enumerator::interval_enumerator
interval_enumerator(const BV &bv)
Construct enumerator for the bit-vector.
Definition bmintervals.h:75
bm::interval_enumerator::interval_enumerator
interval_enumerator(interval_enumerator< BV > &&ien) BMNOEXCEPT
move-ctor
Definition bmintervals.h:115
bm::interval_enumerator::operator=
interval_enumerator< BV > & operator=(interval_enumerator< BV > &&ien) BMNOEXCEPT
move assignmment operator
Definition bmintervals.h:122
bm::interval_enumerator< bm::bvector<> >::advance
bool advance()
bm::interval_enumerator::operator<
bool operator<(const interval_enumerator< BV > &ien) const BMNOEXCEPT
Definition bmintervals.h:142
bm::interval_enumerator::operator=
interval_enumerator & operator=(const interval_enumerator< BV > &ien)
Assignment operator.
Definition bmintervals.h:107
bm::interval_enumerator::operator>
bool operator>(const interval_enumerator< BV > &ien) const BMNOEXCEPT
Definition bmintervals.h:146
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::bvector_type
BV bvector_type
Definition bmintervals.h:58
bm::interval_enumerator::interval_enumerator
interval_enumerator()
Definition bmintervals.h:68
bm::interval_enumerator::interval_enumerator
interval_enumerator(const interval_enumerator< BV > &ien)
Copy constructor.
Definition bmintervals.h:98
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::swap
void swap(interval_enumerator< BV > &ien) BMNOEXCEPT
swap enumerator with another one
Definition bmintervals.h:757
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::bv_allocator_type
bvector_type::allocator_type bv_allocator_type
Definition bmintervals.h:211
bm::interval_enumerator::size_type
bvector_type::size_type size_type
Definition bmintervals.h:59
bm::interval_enumerator::allocator_type
bvector_type::allocator_type allocator_type
Definition bmintervals.h:60
bm::interval_enumerator::operator==
bool operator==(const interval_enumerator< BV > &ien) const BMNOEXCEPT
Definition bmintervals.h:138
bm::interval_enumerator::operator<=
bool operator<=(const interval_enumerator< BV > &ien) const BMNOEXCEPT
Definition bmintervals.h:144
bm::interval_enumerator::invalidate
void invalidate() BMNOEXCEPT
Turn FSM into invalid state (out of range).
Definition bmintervals.h:576
bm::interval_enumerator< bm::bvector<> >::go_to
bool go_to(size_type pos, bool extend_start=true)
bm::interval_enumerator::operator!=
bool operator!=(const interval_enumerator< BV > &ien) const BMNOEXCEPT
Definition bmintervals.h:140
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::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::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
bm
Definition bm.h:78
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:6128
bm::id_max
const unsigned id_max
Definition bmconst.h:109
bm::word_t
unsigned int word_t
Definition bmconst.h:39
bm::set_block_mask
const unsigned set_block_mask
Definition bmconst.h:57
bm::gap_bfind
unsigned gap_bfind(const T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set) BMNOEXCEPT
Definition bmfunc.h:1725
bm::get_block_start
BMFORCEINLINE RTYPE get_block_start(unsigned i, unsigned j) BMNOEXCEPT
Compute bit address of the first bit in a block.
Definition bmfunc.h:201
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:4870
bm::set_sub_array_size
const unsigned set_sub_array_size
Definition bmconst.h:95
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:180
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:6396
bm::xor_swap
BMFORCEINLINE void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two variables.
Definition bmutil.h:534
bm::get_super_block_start
BMFORCEINLINE RTYPE get_super_block_start(unsigned i) BMNOEXCEPT
Compute bit address of the first bit in a superblock.
Definition bmfunc.h:191
bm::gap_word_t
unsigned short gap_word_t
Definition bmconst.h:78
bm::gap_max_bits
const unsigned gap_max_bits
Definition bmconst.h:81
bm::set_block_shift
const unsigned set_block_shift
Definition bmconst.h:56
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:6232
bm::pair
Pair type.
Definition bmfunc.h:154