Algorithms for bit intervals
BitMagic Library » bvector<> container

Algorithms and iterators for bit ranges and intervals. More...

Collaboration diagram for Algorithms for bit intervals:

## Data Structures

class | bm::interval_enumerator< BV >
| forward iterator class to traverse bit-vector as ranges More...

## Functions

template<class BV>
bool | bm::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, 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.
template<class BV>
bool | bm::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 a block of continious 1s. Method employs closed interval semantics: 0[pos..from].
template<typename BV>
bool | bm::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 a block of continious 1s. Method employs closed interval semantics: 0[pos..from].

## Detailed Description

Algorithms and iterators for bit ranges and intervals.

## Function Documentation

## find_interval_end()

template<typename BV>

bool bm::find_interval_end | ( | const BV & | bv,
|  | typename BV::size_type | from,
|  | typename BV::size_type & | pos )

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].

Parameters

  bv | - bit-vector for search
  from | - position to start reverse search from
  pos | - [out] index of the found first 1 bit in a gap of bits

Returns
  true if search returned result, false if not found (start point is zero)

See also
  is_interval, find_interval_end

Examples
  sample22.cpp, and xsample08.cpp.

Definition at line 438 of file bmintervals.h.

References block_find_interval_end(), BM_ASSERT, BMNOEXCEPT, FULL_BLOCK_FAKE_ADDR, gap_max_bits, get_block_coord(), id_max, set_block_mask, set_block_shift, and set_sub_array_size.

Referenced by bm::interval_enumerator< BV >::advance(), bm::interval_enumerator< BV >::go_to_impl(), main(), and splice_model().

## find_interval_start()

template<class BV>

bool bm::find_interval_start | ( | const BV & | bv,
|  | typename BV::size_type | from,
|  | typename BV::size_type & | pos )

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].

Parameters

  bv | - bit-vector for search
  from | - position to start reverse search from
  pos | - [out] index of the found first 1 bit in a gap of bits

Returns
  true if search returned result, false if not found (start point is zero)

See also
  is_interval, find_interval_end

Examples
  sample22.cpp, and xsample08.cpp.

Definition at line 315 of file bmintervals.h.

References block_find_interval_start(), BM_ASSERT, BMNOEXCEPT, FULL_BLOCK_FAKE_ADDR, gap_max_bits, get_block_coord(), get_block_start(), bm::bvector< Alloc >::get_blocks_manager(), get_super_block_start(), set_block_mask, and set_block_shift.

Referenced by bm::interval_enumerator< BV >::go_to_impl(), main(), and splice_model().

## is_interval()

template<class BV>

bool bm::is_interval | ( | const BV & | bv,
|  | typename BV::size_type | left,
|  | typename BV::size_type | right )

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.

Parameters

  bv | - bit-vector for check
  left | - index of first bit start checking
  right | - index of last bit

Returns
  true/false

See also
  is_all_one_range

Examples
  sample22.cpp.

Definition at line 248 of file bmintervals.h.

References block_is_interval(), BMNOEXCEPT, gap_max_bits, get_block_coord(), id_max, is_interval(), set_block_mask, set_block_shift, and xor_swap().

Referenced by is_interval(), and main().