1#ifndef BMSPARSEVEC_H__INCLUDED__
2#define BMSPARSEVEC_H__INCLUDED__
32#ifndef BM__H__INCLUDED__
35# error missing include (bm.h or bm64.h)
80template<
class Val,
class BV>
131 {
return bool(*
this) == bool(ref); }
178 {
return (pos_ == it.pos_) && (sv_ == it.sv_); }
182 {
return pos_ < it.pos_; }
184 {
return pos_ <= it.pos_; }
186 {
return pos_ > it.pos_; }
188 {
return pos_ >= it.pos_; }
228 n_buf_size = 1024 * 8
278 this->
flush(); sv_ = bi.sv_; bv_null_ = bi. bv_null_;
336 n_buf_size = 1024 * 8
423 {
return this->
get(idx); }
542 bool set_not_null =
true);
552 bool set_not_null =
true);
580 bool zero_mem =
true)
const;
817 bool zero_mem = true) const;
826 bool zero_mem = true) const;
905 *idx_from = from; *idx_to = to;
return true;
921template<
class Val,
class BV>
932template<
class Val,
class BV>
940template<
class Val,
class BV>
943 parent_type::swap(sv);
951template<
class Val,
class BV>
957template<
class Val,
class BV>
960 parent_type::swap(sv);
965template<
class Val,
class BV>
969 throw std::range_error(err_msg);
977template<
class Val,
class BV>
980 BV::throw_bad_alloc();
985template<
class Val,
class BV>
993template<
class Val,
class BV>
999 unsigned char b_list[
sizeof(Val)*8];
1000 unsigned row_len[
sizeof(Val)*8] = {0, };
1002 const unsigned transpose_window = 256;
1006 throw_range_error(
"sparse_vector range error (import size 0)");
1008 if (offset < this->size_)
1011 this->clear_range(offset, offset + arr_size - 1);
1021 for (i = 0; i < arr_size; ++i)
1026 for (
unsigned j = 0; j < bcnt; ++j)
1028 unsigned p = b_list[j];
1029 unsigned rl = row_len[p];
1030 tm.row(p)[rl] = bit_idx;
1033 if (rl == transpose_window)
1046 for (
unsigned k = 0; k < tm.rows(); ++k)
1048 unsigned rl = row_len[k];
1058 if (i + offset > this->size_)
1059 this->size_ = i + offset;
1065 bv_null->set_range(offset, offset + arr_size - 1);
1071template<
class Val,
class BV>
1076 this->
import(arr, arr_size, this->size(), set_not_null);
1081template<
class Val,
class BV>
1086 bool zero_mem)
const
1088 return extract(arr, dec_size, idx_from, zero_mem);
1093template<
class Val,
class BV>
1106 arr[0] = this->get(idx[0]);
1113 bool sorted_block =
true;
1128 sorted_block = !(idx[r] < idx_prev);
1134 sorted_block =
false;
1135 for (; r < size; ++r)
1160 arr[i] = this->get(idx[i]);
1170 unsigned eff_plains = this->effective_plains();
1171 for (
unsigned j = 0; j < eff_plains; ++j)
1173 const bm::word_t* blk = this->bmatr_.get_block(j, i0, j0);
1198 unsigned gap_value = gap_blk[gidx];
1201 arr[k] |= vm = (mask1 << j);
1202 for (++k; k < r; ++k)
1242template<
class Val,
class BV>
1247 bool zero_mem)
const
1256 if (end > this->size_)
1272 for (
unsigned j = 0; j <
sizeof(Val)*8; ++j)
1274 blk = this->bmatr_.get_block(j, i0, j0);
1285 blk = this->bmatr_.get_block(j, i0, j0);
1306 is_set = (blk[nword] & mask0);
1322template<
class Val,
class BV>
1327 bool zero_mem)
const
1337 if (end > this->size_)
1342 for (
size_type i = 0; i < parent_type::value_bits(); ++i)
1350 typename BV::enumerator en(bv, offset);
1351 for (;en.valid(); ++en)
1367template<
class Val,
class BV>
1377 struct sv_decode_visitor_func
1382 : arr_(varr), mask_(mask), sv_off_(off)
1386 const unsigned char* bits,
unsigned bits_size)
BMNOEXCEPT
1391 for (
unsigned i = 0; i < bits_size; ++i)
1392 arr_[bits[i] + base] |= m;
1396 auto base = bv_offset - sv_off_;
1399 arr_[i + base] |= m;
1414 if (end > this->size_)
1417 sv_decode_visitor_func func(arr, 0, offset);
1419 for (
size_type i = 0; i < parent_type::value_bits(); ++i)
1427 return end - offset;
1432template<
class Val,
class BV>
1436 if (idx >= this->size_)
1437 throw_range_error(
"sparse vector range error");
1438 return this->get(idx);
1443template<
class Val,
class BV>
1452 unsigned eff_plains = this->effective_plains();
1453 for (
unsigned j = 0; j < eff_plains; j+=4)
1455 bool b = this->bmatr_.test_4rows(j);
1468template<
class Val,
class BV>
1473 this->size_ = idx+1;
1480template<
class Val,
class BV>
1484 this->size_ = idx+1;
1491 bv_null->set(idx,
false);
1497template<
class Val,
class BV>
1500 set_value(this->size_, v);
1506template<
class Val,
class BV>
1513 this->size_ += count;
1519template<
class Val,
class BV>
1524 this->size_ = idx+1;
1528 insert_value(idx, v);
1533template<
class Val,
class BV>
1536 insert_value_no_null(idx, v);
1537 this->insert_null(idx,
true);
1542template<
class Val,
class BV>
1548 for (; i <= bsr; ++i)
1553 bv->insert(idx,
true);
1559 bv->insert(idx,
false);
1564 unsigned eff_plains = this->effective_plains();
1565 for (; i < eff_plains; ++i)
1569 bv->insert(idx,
false);
1577template<
class Val,
class BV>
1581 if (idx >= this->size_)
1583 this->erase_column(idx);
1590template<
class Val,
class BV>
1593 set_value_no_null(this->size_, v);
1599template<
class Val,
class BV>
1602 set_value_no_null(idx, v);
1605 bv_null->set_bit_no_check(idx);
1610template<
class Val,
class BV>
1620 unsigned eff_plains = this->effective_plains();
1623 for (
unsigned i = bsr; i < eff_plains; ++i)
1625 const bm::word_t* blk = this->bmatr_.get_block(i, i0, j0);
1630 bv->clear_bit_no_check(idx);
1637 for (
unsigned j = 0; j <= bsr; ++j)
1642 bv->set_bit_no_check(idx);
1646 const bm::word_t* blk = this->bmatr_.get_block(j, i0, j0);
1650 bv->clear_bit_no_check(idx);
1660template<
class Val,
class BV>
1663 if (idx >= this->size_)
1664 this->size_ = idx+1;
1666 for (
unsigned i = 0; i < parent_type::sv_value_plains; ++i)
1669 bool carry_over = bv->inc(idx);
1675 bv_null->set_bit_no_check(idx);
1680template<
class Val,
class BV>
1683 parent_type::clear();
1688template<
class Val,
class BV>
1698template<
class Val,
class BV>
1705 parent_type::clear_range(left, right, set_null);
1711template<
class Val,
class BV>
1717 parent_type::calc_stat(&stbv);
1727template<
class Val,
class BV>
1735 parent_type::optimize(temp_block, opt_mode, st ? &stbv : 0);
1746template<
class Val,
class BV>
1749 unsigned stored_plains = this->stored_plains();
1750 for (
unsigned j = 0; j < stored_plains; ++j)
1755 bv->optimize_gap_size();
1762template<
class Val,
class BV>
1767 if (this->size_ < arg_size)
1774 plains = this->stored_plains();
1776 plains = this->plains();
1778 for (
unsigned j = 0; j < plains; ++j)
1785 bv = this->get_plain(j);
1793 bv_null->set_range(0, arg_size-1);
1801template<
class Val,
class BV>
1806 if (this->size_ < arg_size)
1813 plains = this->stored_plains();
1815 plains = this->plains();
1817 for (
unsigned j = 0; j < plains; ++j)
1824 bv = this->get_plain(j);
1832 bv_null->set_range(0, arg_size-1);
1840template<
class Val,
class BV>
1849 this->copy_range_plains(sv, left, right, splice_null);
1850 this->resize(sv.
size());
1854template<
class Val,
class BV>
1862 plains = this->stored_plains();
1863 bv_null->bit_and(bv_mask);
1866 plains = this->plains();
1868 for (
unsigned j = 0; j < plains; ++j)
1872 bv->bit_and(bv_mask);
1878template<
class Val,
class BV>
1884 return (sv_value > val) - (sv_value < val);
1889template<
class Val,
class BV>
1893 return parent_type::equal(sv, null_able);
1898template<
class Val,
class BV>
1903 return it_type(
this);
1908template<
class Val,
class BV>
1912 this->bmatr_.set_allocator_pool(pool_ptr);
1921template<
class Val,
class BV>
1923: sv_(0), pos_(
bm::
id_max), buf_ptr_(0)
1928template<
class Val,
class BV>
1931: sv_(it.sv_), pos_(it.pos_), buf_ptr_(0)
1936template<
class Val,
class BV>
1940: sv_(sv), buf_ptr_(0)
1948template<
class Val,
class BV>
1952: sv_(sv), buf_ptr_(0)
1960template<
class Val,
class BV>
1963 pos_ = (!sv_ || pos >= sv_->size()) ?
bm::id_max : pos;
1969template<
class Val,
class BV>
1975 if (pos_ >= sv_->size())
1983 if (buf_ptr_ - ((
value_type*)buffer_.data()) >= n_buf_size)
1991template<
class Val,
class BV>
2000 buffer_.reserve(n_buf_size *
sizeof(
value_type));
2002 sv_->extract(buf_ptr_, n_buf_size, pos_,
true);
2010template<
class Val,
class BV>
2021 if (++buf_ptr_ < buf_end)
2026 if (pos_ >= sv_->size())
2031 if (buf_ptr_ >= buf_end)
2038template<
class Val,
class BV>
2041 return sv_->is_null(pos_);
2050template<
class Val,
class BV>
2052: sv_(0), bv_null_(0), buf_ptr_(0), prev_nb_(0), set_not_null_(true)
2057template<
class Val,
class BV>
2060: sv_(sv), buf_ptr_(0), set_not_null_(true)
2065 bv_null_ = sv_->get_null_bvect();
2069 bv_null_ = 0; prev_nb_ = 0;
2075template<
class Val,
class BV>
2077 const typename sparse_vector<Val, BV>::back_insert_iterator& bi)
2078: sv_(bi.sv_), bv_null_(bi.bv_null_), buf_ptr_(0), prev_nb_(bi.prev_nb_),
2079 set_not_null_(bi.set_not_null_)
2086template<
class Val,
class BV>
2094template<
class Val,
class BV>
2098 size_type buf_idx = this->add_value_no_null(v);
2102 bv_null_->set_bit_no_check(sz + buf_idx);
2108template<
class Val,
class BV>
2116 buffer_.reserve(n_buf_size *
sizeof(
value_type));
2122 if (buf_ptr_ - ((
value_type*)buffer_.data()) >= n_buf_size)
2136template<
class Val,
class BV>
2145template<
class Val,
class BV>
2157 sv_->push_back_null(count);
2163template<
class Val,
class BV>
2166 return (!buf_ptr_ || !sv_);
2171template<
class Val,
class BV>
2177 sv_->import_back(d,
size_type(buf_ptr_ - d),
false);
2183 sv_->optimize_block(prev_nb_);
basic bit-matrix class and utilities
#define IS_FULL_BLOCK(addr)
#define BM_ASSERT_THROW(x, xerrcode)
#define FULL_BLOCK_FAKE_ADDR
Utilities for bit transposition (internal) (experimental!)
pre-processor un-defines to avoid global space pollution (internal)
Base class for bit-transposed sparse vector construction.
void copy_from(const base_sparse_vector< Val, BV, MAX_SIZE > &bsv)
bmatrix_type bmatr_
bit-transposed matrix
void resize(size_type new_size)
size_type size_
array size
bool is_nullable() const BMNOEXCEPT
check if container supports NULL(unassigned) values
Basic dense bit-matrix class.
const bvector_type * row(size_type i) const BMNOEXCEPT
bvector_type_const_ptr get_row(size_type i) const BMNOEXCEPT
Constant iterator designed to enumerate "ON" bits.
Bitvector Bit-vector container with runtime compression of bits.
optmode
Optimization mode Every next level means additional checks (better compression vs time)
@ opt_compress
compress blocks when possible (GAP/prefix sum)
allocator_type::allocator_pool_type allocator_pool_type
blocks_manager_type::block_idx_type block_idx_type
Rank-Select compressed sparse vector.
Back insert iterator implements buffered insert, faster than generic access assignment.
back_insert_iterator & operator=(value_type v)
push value to the vector
void add_null(size_type count)
add a series of consequitve NULLs (no-value) to the container
bm::byte_buffer< allocator_type > buffer_type
bvector_type::allocator_type::allocator_pool_type allocator_pool_type
bvector_type::block_idx_type block_idx_type
size_type add_value_no_null(value_type v)
add value to the buffer without changing the NULL vector
void add_null()
add NULL (no-value) to the container
back_insert_iterator & operator++()
noop
sparse_vector_type::size_type size_type
bvector_type * get_null_bvect() const BMNOEXCEPT
Get access to not-null vector.
back_insert_iterator & operator++(int)
noop
back_insert_iterator(const back_insert_iterator &bi)
void add(value_type v)
add value to the container
void flush()
flush the accumulated buffer
void disable_set_null() BMNOEXCEPT
Reconfшпгку back inserter not to touch the NULL vector.
bool empty() const
return true if insertion buffer is empty
sparse_vector_type * sparse_vector_type_ptr
back_insert_iterator(sparse_vector_type *sv)
bvector_type::allocator_type allocator_type
back_insert_iterator & operator*()
noop
sparse_vector< Val, BV > sparse_vector_type
back_insert_iterator & operator=(const back_insert_iterator &bi)
std::output_iterator_tag iterator_category
sparse_vector_type::value_type value_type
sparse_vector_type::bvector_type bvector_type
Const iterator to traverse the sparse vector.
const_iterator & operator++() BMNOEXCEPT
Advance to the next available value.
void go_to(size_type pos) BMNOEXCEPT
re-position to a specified position
std::input_iterator_tag iterator_category
bool operator==(const const_iterator &it) const BMNOEXCEPT
bool operator>(const const_iterator &it) const BMNOEXCEPT
bvector_type::allocator_type allocator_type
sparse_vector< Val, BV > sparse_vector_type
bool is_null() const BMNOEXCEPT
Get NULL status.
bool advance() BMNOEXCEPT
advance iterator forward by one
value_type operator*() const
Get current position (value)
sparse_vector_type::bvector_type bvector_type
bool operator!=(const const_iterator &it) const BMNOEXCEPT
bool operator<(const const_iterator &it) const BMNOEXCEPT
bool operator<=(const const_iterator &it) const BMNOEXCEPT
bool valid() const BMNOEXCEPT
Returns true if iterator is at a valid position.
const_iterator() BMNOEXCEPT
bm::byte_buffer< allocator_type > buffer_type
void invalidate() BMNOEXCEPT
Invalidate current iterator.
value_type value() const
Get current position (value)
void skip_zero_values() BMNOEXCEPT
sparse_vector_type::size_type size_type
size_type pos() const BMNOEXCEPT
Current position (index) in the vector.
sparse_vector_type * sparse_vector_type_ptr
sparse_vector_type::value_type value_type
bvector_type::allocator_type::allocator_pool_type allocator_pool_type
const_iterator & operator++(int)
Advance to the next available value.
bool operator>=(const const_iterator &it) const BMNOEXCEPT
Reference class to access elements via common [] operator.
bool operator==(const reference &ref) const BMNOEXCEPT
bool is_null() const BMNOEXCEPT
reference & operator=(const reference &ref)
reference & operator=(value_type val)
reference(sparse_vector< Val, BV > &sv, size_type idx) BMNOEXCEPT
sparse vector de-serializer
algorithms for sparse_vector scan/search
sparse vector with runtime compression using bit transposition method
void inc(size_type idx)
increment specified element by one
bool is_remap() const BMNOEXCEPT
bvector_type::size_type size_type
static bool is_compressed() BMNOEXCEPT
trait if sparse vector is "compressed" (false)
value_type at(size_type idx) const
access specified element with bounds checking
void set_null(size_type idx)
set specified element to unassigned value (NULL)
void copy_range(const sparse_vector< Val, BV > &sv, size_type left, size_type right, bm::null_support splice_null=bm::use_null)
copy range of values from another sparse vector
void erase(size_type idx)
erase specified element from container
void set_value(size_type idx, value_type v)
set value without checking boundaries
value_type get(size_type idx) const BMNOEXCEPT
get specified element without bounds checking
allocator_type::allocator_pool_type allocator_pool_type
void insert_value_no_null(size_type idx, value_type v)
insert value without checking boundaries or support of NULL
bool equal(const sparse_vector< Val, BV > &sv, bm::null_support null_able=bm::use_null) const BMNOEXCEPT
check if another sparse vector has the same content and size
void sync(bool)
syncronize internal structures
const value_type & const_reference
void push_back(value_type v)
push value back into vector
size_type size_internal() const BMNOEXCEPT
void push_back_no_null(value_type v)
push value back into vector without NULL semantics
void insert_value(size_type idx, value_type v)
insert value without checking boundaries
bvector_type * bvector_type_ptr
void resize_internal(size_type sz)
unsigned char * init_remap_buffer() BMNOEXCEPT
void set_remap() BMNOEXCEPT
size_type size() const BMNOEXCEPT
return size of the vector
void optimize_gap_size()
Optimize sizes of GAP blocks.
sparse_vector(const sparse_vector< Val, BV > &sv)
sparse_vector(sparse_vector< Val, BV > &&sv) BMNOEXCEPT
bvector_type::enumerator bvector_enumerator_type
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
void resize(size_type sz)
resize vector
size_t remap_size() const BMNOEXCEPT
void set_value_no_null(size_type idx, value_type v)
set value without checking boundaries or support of NULL
static void throw_range_error(const char *err_msg)
throw range error
const_iterator end() const BMNOEXCEPT
Provide const iterator access to the end
back_insert_iterator get_back_inserter()
Provide back insert iterator Back insert iterator implements buffered insertion, which is faster,...
bool resolve_range(size_type from, size_type to, size_type *idx_from, size_type *idx_to) const BMNOEXCEPT
friend back_insert_iterator
bvector_type::block_idx_type block_idx_type
size_type gather(value_type *arr, const size_type *idx, size_type size, bm::sort_order sorted_idx) const
Gather elements to a C-style array.
void push_back_null(size_type count)
push back specified amount of NULL values
sparse_vector< Val, BV > & merge(sparse_vector< Val, BV > &sv)
merge with another sparse vector using OR operation Merge is different from join(),...
const unsigned char * get_remap_buffer() const BMNOEXCEPT
int compare(size_type idx, const value_type val) const BMNOEXCEPT
Compare vector element with argument.
size_type extract_plains(value_type *arr, size_type size, size_type offset, bool zero_mem=true) const
extract medium window without use of masking vector
bool empty() const BMNOEXCEPT
return true if vector is empty
~sparse_vector() BMNOEXCEPT
static bool find_rank(size_type rank, size_type &pos) BMNOEXCEPT
find position of compressed element by its rank
sparse_vector< Val, BV > & operator=(const sparse_vector< Val, BV > &sv)
void swap(sparse_vector< Val, BV > &sv) BMNOEXCEPT
content exchange
sparse_vector< Val, BV > & join(const sparse_vector< Val, BV > &sv)
join all with another sparse vector using OR operation
static size_type translate_address(size_type i) BMNOEXCEPT
address translation for this type of container
void insert(size_type idx, value_type v)
insert specified element into container
void import_back(const value_type *arr, size_type arr_size, bool set_not_null=true)
Import list of elements from a C-style array (pushed back)
base_sparse_vector< Val, BV, 1 > parent_type
size_type extract_range(value_type *arr, size_type size, size_type offset, bool zero_mem=true) const
extract small window without use of masking vector
void calc_stat(struct sparse_vector< Val, BV >::statistics *st) const BMNOEXCEPT
Calculates memory statistics.
static void throw_bad_alloc()
throw bad alloc
BV::allocator_type allocator_type
sparse_vector(bm::null_support null_able=bm::no_null, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type())
Sparse vector constructor.
sparse_vector< Val, BV > & clear_range(size_type left, size_type right, bool set_null=false)
clear range (assign bit 0 for all plains)
size_type effective_size() const BMNOEXCEPT
size of sparse vector (may be different for RSC)
void clear() BMNOEXCEPT
resize to zero, free memory
size_type decode(value_type *arr, size_type idx_from, size_type dec_size, bool zero_mem=true) const
Bulk export list of elements to a C-style array.
bm::basic_bmatrix< BV > bmatrix_type
size_type extract(value_type *arr, size_type size, size_type offset=0, bool zero_mem=true) const BMNOEXCEPT2
Bulk export list of elements to a C-style array.
size_type effective_vector_max() const BMNOEXCEPT
Always 1 (non-matrix type)
const_iterator get_const_iterator(size_type idx) const BMNOEXCEPT
Get const_itertor re-positioned to specific element.
const_iterator begin() const BMNOEXCEPT
Provide const iterator access to container content
bvector_type::allocation_policy allocation_policy_type
void import(const value_type *arr, size_type arr_size, size_type offset=0, bool set_not_null=true)
Import list of elements from a C-style array.
void filter(const bvector_type &bv_mask)
Apply value filter, defined by mask vector.
const bvector_type * bvector_type_const_ptr
void clear(size_type idx, bool set_null=false)
clear specified element with bounds checking and automatic resize
void set_allocator_pool(allocator_pool_type *pool_ptr) BMNOEXCEPT
Set allocator pool for local (non-threaded) memory cyclic(lots of alloc-free ops) opertations.
value_type operator[](size_type idx) const BMNOEXCEPT
get specified element without bounds checking
void optimize(bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename sparse_vector< Val, BV >::statistics *stat=0)
run memory optimization for all vector plains
void bit_block_gather_scatter(unsigned *BMRESTRICT arr, const bm::word_t *BMRESTRICT blk, const unsigned *BMRESTRICT idx, unsigned size, unsigned start, unsigned bit_idx) BMNOEXCEPT
bit index to word gather-scatter algorithm (SIMD)
unsigned bit_scan_reverse(T value) BMNOEXCEPT
sort_order
Sort order declaration.
null_support
NULL-able value support.
@ BM_UNSORTED
input set is NOT sorted
@ BM_SORTED
input set is sorted (ascending order)
@ BM_UNKNOWN
sort order unknown
@ BM_SORTED_UNIFORM
sorted and in one block (internal!)
@ use_null
support "non-assigned" or "NULL" logic
@ no_null
do not support NULL values
unsigned gap_test_unr(const T *BMRESTRICT buf, const unsigned pos) BMNOEXCEPT
Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.
const unsigned set_array_mask
void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two scalar variables.
const unsigned set_block_mask
unsigned short bitscan(V w, B *bits) BMNOEXCEPT
unsigned gap_bfind(const T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set) BMNOEXCEPT
const unsigned set_word_shift
bm::id64_t idx_arr_block_lookup_u64(const bm::id64_t *idx, bm::id64_t size, bm::id64_t nb, bm::id64_t start) BMNOEXCEPT
block boundaries look ahead U32
unsigned idx_arr_block_lookup_u32(const unsigned *idx, unsigned size, unsigned nb, unsigned start) BMNOEXCEPT
block boundaries look ahead U32
const unsigned set_array_shift
unsigned short gap_word_t
const unsigned set_block_shift
const unsigned set_word_mask
void for_each_bit_range_no_check(const BV &bv, typename BV::size_type left, typename BV::size_type right, Func &bit_functor)
Implementation of for_each_bit_range without boilerplave checks.
Structure with statistical information about memory allocation footprint, serialization projection,...
void reset() BMNOEXCEPT
Reset statisctics.
void add(const bv_statistics &st) BMNOEXCEPT
Sum data from another sttructure.
Statistical information about bitset's memory allocation details.
Mini-matrix for bit transposition purposes.