Sparse vector algorithms
BitMagic Library » Sparse and compressed vectors

Sparse vector algorithms. More...

Collaboration diagram for Sparse vector algorithms:

## Data Structures

class | bm::sparse_vector_scanner< SV, S_FACTOR >
| algorithms for sparse_vector scan/search More...
class | bm::set2set_11_transform< SV >
| Integer set to set transformation (functional image in groups theory) https://en.wikipedia.org/wiki/Image_(mathematics). More...

## Functions

template<typename SV>
void | bm::dynamic_range_clip_high (SV &svect, unsigned high_bit)
| Clip dynamic range for signal higher than specified.
template<typename SV>
void | bm::dynamic_range_clip_low (SV &svect, unsigned low_bit)
| Clip dynamic range for signal lower than specified (boost).
template<typename SV>
bool | bm::sparse_vector_find_first_mismatch (const SV &sv1, const SV &sv2, typename SV::size_type &midx, bm::null_support null_proc=bm::use_null)
| Find first mismatch (element which is different) between two sparse vectors (uses linear scan in bit-vector planes).
template<typename SV1, typename SV2>
void | bm::sparse_vector_find_mismatch (typename SV1::bvector_type &bv, const SV1 &sv1, const SV2 &sv2, bm::null_support null_proc)
| Find mismatch vector, indicating positions of mismatch between two sparse vectors (uses linear scan in bit-vector planes).

## Detailed Description

Sparse vector algorithms.

## Function Documentation

## dynamic_range_clip_high()

template<typename SV>

void bm::dynamic_range_clip_high | ( | SV & | svect,
|  | unsigned | high_bit )

Clip dynamic range for signal higher than specified.

Parameters

  svect | - sparse vector to do clipping
  high_bit | - max bit (inclusive) allowed for this signal vector

See also
  dynamic_range_clip_low

Definition at line 67 of file bmsparsevec_algo.h.

References BM_ASSERT.

## dynamic_range_clip_low()

template<typename SV>

void bm::dynamic_range_clip_low | ( | SV & | svect,
|  | unsigned | low_bit )

Clip dynamic range for signal lower than specified (boost).

Parameters

  svect | - sparse vector to do clipping
  low_bit | - low bit (inclusive) allowed for this signal vector

See also
  dynamic_range_clip_high

Definition at line 107 of file bmsparsevec_algo.h.

References BM_ASSERT.

## sparse_vector_find_first_mismatch()

template<typename SV>

bool bm::sparse_vector_find_first_mismatch | ( | const SV & | sv1,
|  | const SV & | sv2,
|  | typename SV::size_type & | midx,
|  | bm::null_support | null_proc = bm::use_null )

Find first mismatch (element which is different) between two sparse vectors (uses linear scan in bit-vector planes).

Function works with both NULL and NOT NULL vectors NULL means unassigned (uncertainty), so first mismatch NULL is a mismatch even if values in vectors can be formally the same (i.e. 0)

Parameters

  sv1 | - vector 1
  sv2 | - vector 2
  midx | - mismatch index
  null_proc | - defines if we want to include (not) NULL vector into comparison (bm::use_null) or not. By default search takes NULL vector into account

Returns
  true if mismatch found

See also
  sparse_vector_find_mismatch

Examples
  strsvsample06.cpp, svsample09.cpp, xsample06.cpp, and xsample07.cpp.

Definition at line 170 of file bmsparsevec_algo.h.

References BM_ASSERT, id_max, bm::conditional< b >::test(), and use_null.

Referenced by compare_sv(), main(), main(), and test_mismatch_search().

## sparse_vector_find_mismatch()

template<typename SV1, typename SV2>

void bm::sparse_vector_find_mismatch | ( | typename SV1::bvector_type & | bv,
|  | const SV1 & | sv1,
|  | const SV2 & | sv2,
|  | bm::null_support | null_proc )

Find mismatch vector, indicating positions of mismatch between two sparse vectors (uses linear scan in bit-vector planes).

Function works with both NULL and NOT NULL vectors

Parameters

  bv | - [out] - bit-ector with mismatch positions indicated as 1s
  sv1 | - vector 1
  sv2 | - vector 2
  null_proc | - rules of processing for (not) NULL plane bm::no_null - NULLs from both vectors are treated as uncertainty and NOT included into final result bm::use_null - difference in NULLs accounted into the result

See also
  sparse_vector_find_first_mismatch

Definition at line 348 of file bmsparsevec_algo.h.

References bm::bvector< Alloc >::bit_or(), bm::bvector< Alloc >::bit_xor(), BM_ASSERT, bm::bvector< Alloc >::invert(), no_null, bm::bvector< Alloc >::opt_none, bm::bvector< Alloc >::resize(), bm::conditional< b >::test(), use_null, and xor_swap().