1#ifndef BMSPARSEVEC_H__INCLUDED__
2#define BMSPARSEVEC_H__INCLUDED__
33#ifndef BM__H__INCLUDED__
36# error missing include (bm.h or bm64.h)
85template<
class Val,
class BV>
138 {
return bool(*
this) == bool(ref); }
186 {
return (pos_ == it.pos_) && (sv_ == it.sv_); }
190 {
return pos_ < it.pos_; }
192 {
return pos_ <= it.pos_; }
194 {
return pos_ > it.pos_; }
196 {
return pos_ >= it.pos_; }
286 this->flush(); sv_ = bi.sv_; bv_null_ = bi.bv_null_;
289 this->set_not_null_ = bi.set_not_null_;
297 this->flush(); sv_ = bi.sv_; bv_null_ = bi.bv_null_;
298 this->buffer_.swap(bi.buffer_);
299 this->buf_ptr_ = bi.buf_ptr_;
300 this->set_not_null_ = bi.set_not_null_;
304 ~~back_insert_iterator();
365 bool set_not_null_ =
true;
444 {
return this->
get(idx); }
606 bool set_not_null =
true);
616 bool set_not_null =
true);
644 bool zero_mem =
true)
const;
916 bool zero_mem = true) const;
925 bool zero_mem = true) const;
1013 bm::heap_matrix<
unsigned char,
1025 *idx_from = from; *idx_to = to;
return true;
1042 bool set_not_null =
true);
1081template<
class Val,
class BV>
1092template<
class Val,
class BV>
1100template<
class Val,
class BV>
1103 parent_type::swap(sv);
1111template<
class Val,
class BV>
1117template<
class Val,
class BV>
1120 parent_type::swap(sv);
1125template<
class Val,
class BV>
1129 throw std::range_error(err_msg);
1137template<
class Val,
class BV>
1140 BV::throw_bad_alloc();
1145template<
class Val,
class BV>
1153template<
class Val,
class BV>
1159 if constexpr (std::is_signed<value_type>::value)
1161 const unsigned tmp_size = 1024;
1164 while (i < arr_size)
1166 arr_tmp[k++] = this->s2u(arr[i++]);
1169 import_u(arr_tmp, k, offset, set_not_null);
1170 k = 0; offset += tmp_size;
1175 import_u(arr_tmp, k, offset, set_not_null);
1186template<
class Val,
class BV>
1193 throw_range_error(
"sparse_vector range error (import size 0)");
1196 if (offset < this->size_)
1197 this->clear_range(offset, offset + arr_size - 1);
1199 this->import_u_nocheck(arr, arr_size, offset, set_not_null);
1203template<
class Val,
class BV>
1211 const unsigned bit_capacity =
sizeof(Val)*8;
1212 unsigned char b_list[bit_capacity];
1213 unsigned row_len[bit_capacity] = {0, };
1216 const unsigned transpose_window = 256;
1226 for (i = 0; i < arr_size; ++i)
1231 for (
unsigned j = 0; j < bcnt; ++j)
1233 unsigned p = b_list[j];
1234 unsigned rl = row_len[p];
1235 tm.
row(p)[rl] = bit_idx;
1238 if (rl == transpose_window)
1242 bv = bv_slices[p] = this->get_create_slice(p);
1246 bv->import_sorted(r, rl,
false);
1254 unsigned rows = tm.
rows();
1255 for (
unsigned k = 0; k < rows; ++k)
1257 if (
unsigned rl = row_len[k])
1261 bv = this->get_create_slice(k);
1263 bv->import_sorted(row, rl,
false);
1268 if (i + offset > this->size_)
1269 this->size_ = i + offset;
1274 bv_null->set_range(offset, offset + arr_size - 1);
1281template<
class Val,
class BV>
1284 const bvector_type* bv_null = this->get_null_bvector();
1287 bool found = bv_null->find_reverse(this->size_);
1288 this->size_ += found;
1293template<
class Val,
class BV>
1298 if constexpr (std::is_signed<value_type>::value)
1300 const unsigned tmp_size = 1024;
1303 while (i < arr_size)
1305 arr_tmp[k++] = this->s2u(arr[i++]);
1308 import_back_u(arr_tmp, k, set_not_null);
1314 import_back_u(arr_tmp, k, set_not_null);
1326template<
class Val,
class BV>
1331 this->import_u_nocheck(arr, arr_size, this->size(), set_not_null);
1336template<
class Val,
class BV>
1341 bool zero_mem)
const
1343 return extract(arr, dec_size, idx_from, zero_mem);
1348template<
class Val,
class BV>
1361 arr[0] = this->get(idx[0]);
1368 bool sorted_block =
true;
1380 sorted_block =
true;
1386 if (idx[r] < idx_prev)
1387 sorted_block =
false;
1394 sorted_block =
false;
1395 for (; r < size; ++r)
1437 unsigned eff_planes = this->effective_slices();
1440 for (
unsigned j = 0; j < eff_planes; ++j)
1442 const bm::word_t* blk = this->bmatr_.get_block(j, i0, j0);
1467 unsigned gap_value = gap_blk[gidx];
1471 for (++k; k < r; ++k)
1506 if constexpr (parent_type::is_signed())
1507 u2s_translate(arr, size);
1514template<
class Val,
class BV>
1519 bool zero_mem)
const
1528 if (end > this->size_)
1542 auto planes = this->effective_slices();
1545 for (
unsigned j = 0; j < planes; ++j)
1547 blk = this->bmatr_.get_block(j, i0, j0);
1558 blk = this->bmatr_.get_block(j, i0, j0);
1579 is_set = (blk[nword] & mask0);
1591 if constexpr (parent_type::is_signed())
1592 u2s_translate(arr, size);
1599template<
class Val,
class BV>
1604 bool zero_mem)
const
1614 if (end > this->size_)
1617 for (
size_type i = 0; i < parent_type::value_bits(); ++i)
1624 typename BV::enumerator en(bv, offset);
1625 for (;en.valid(); ++en)
1641template<
class Val,
class BV>
1650 struct sv_decode_visitor_func
1655 : arr_(varr), mask_(mask), sv_off_(off)
1665 for (
unsigned i = 0; i < bits_size; ++i)
1666 arr_[bits[i] + base] |= m;
1671 auto base = bv_offset - sv_off_;
1674 arr_[i + base] |= m;
1690 if (end > this->size_)
1693 sv_decode_visitor_func func(arr, 0, offset);
1695 auto planes = this->effective_slices();
1706 const size_type exported_size = end - offset;
1707 if constexpr (parent_type::is_signed())
1708 u2s_translate(arr, exported_size);
1709 return exported_size;
1714template<
class Val,
class BV>
1720 ::memcpy(&uv, &arr[i],
sizeof(uv));
1721 arr[i] = parent_type::u2s(uv);
1728template<
class Val,
class BV>
1732 if (idx >= this->size_)
1733 throw_range_error(
"sparse vector range error");
1734 return this->get(idx);
1739template<
class Val,
class BV>
1745 return get_no_check(i);
1750template<
class Val,
class BV>
1756 if constexpr (parent_type::is_signed())
1757 return this->u2s(uv);
1764template<
class Val,
class BV>
1772 unsigned eff_planes = this->effective_slices();
1776 for (
unsigned j = 0; smask && j < eff_planes; j+=4, smask >>= 4)
1790template<
class Val,
class BV>
1794 if (this->is_null(idx))
1803template<
class Val,
class BV>
1809 this->size_ = idx+1;
1814 set_value(idx, v, need_clear);
1819template<
class Val,
class BV>
1823 this->size_ = idx+1;
1830 bv_null->clear_bit_no_check(idx);
1837template<
class Val,
class BV>
1840 set_value(this->size_, v,
false);
1846template<
class Val,
class BV>
1853 this->size_ += count;
1859template<
class Val,
class BV>
1864 this->size_ = idx+1;
1865 set_value(idx, v,
false);
1868 insert_value(idx, v);
1873template<
class Val,
class BV>
1876 insert_value_no_null(idx, v);
1877 this->insert_null(idx,
true);
1882template<
class Val,
class BV>
1890 for (; i <= bsr; ++i)
1895 bv->insert(idx,
true);
1900 bv->insert(idx,
false);
1906 unsigned eff_planes = this->effective_slices();
1908 for (; i < eff_planes; ++i)
1911 bv->insert(idx,
false);
1918template<
class Val,
class BV>
1922 if (idx >= this->size_)
1924 this->erase_column(idx, erase_null);
1925 this->size_ -= erase_null;
1931template<
class Val,
class BV>
1934 set_value_no_null(this->size_, v,
false);
1940template<
class Val,
class BV>
1944 set_value_no_null(idx, v, need_clear);
1946 bv_null->set_bit_no_check(idx);
1951template<
class Val,
class BV>
1967 unsigned eff_planes = this->effective_slices();
1969 this->bmatr_.clear_slices_range(bsr, eff_planes, idx);
1974 for (
unsigned j = 0; j <= bsr; ++j)
1979 bv->set_bit_no_check(idx);
1981 else if (need_clear)
1983 if (
const bm::word_t* blk = this->bmatr_.get_block(j, i0, j0))
1987 bv->clear_bit_no_check(idx);
1997template<
class Val,
class BV>
2000 if (idx >= this->size_)
2002 this->size_ = idx+1;
2003 set_value_no_null(idx, 1,
false);
2009 bv_null->set_bit_no_check(idx);
2014template<
class Val,
class BV>
2017 if constexpr (parent_type::is_signed())
2020 if (std::numeric_limits<value_type>::max() == v)
2024 set_value_no_null(idx, v,
true);
2027 for (
unsigned i = 0; i < parent_type::sv_value_slices; ++i)
2030 if (
bool carry_over = bv->inc(idx); !carry_over)
2037template<
class Val,
class BV>
2041 set_value_no_null(idx, v + v_prev,
true);
2046template<
class Val,
class BV>
2049 parent_type::clear_all(free_mem);
2054template<
class Val,
class BV>
2064template<
class Val,
class BV>
2071 parent_type::clear_range(left, right, set_null);
2077template<
class Val,
class BV>
2083 parent_type::calc_stat(&stbv);
2093template<
class Val,
class BV>
2101 parent_type::optimize(temp_block, opt_mode, st ? &stbv : 0);
2112template<
class Val,
class BV>
2115 unsigned stored_slices = this->stored_slices();
2116 for (
unsigned j = 0; j < stored_slices; ++j)
2119 bv->optimize_gap_size();
2125template<
class Val,
class BV>
2130 if (this->size_ < arg_size)
2133 unsigned planes = (unsigned)this->bmatr_.rows();
2137 for (
unsigned j = 0; j < planes; ++j)
2146 join_null_slice(sv);
2152template<
class Val,
class BV>
2157 if (this->size_ < arg_size)
2160 this->merge_matr(sv.
bmatr_);
2162 join_null_slice(sv);
2169template<
class Val,
class BV>
2179 bv_null->set_range(0, arg_size-1);
2193template<
class Val,
class BV>
2202 this->copy_range_slices(sv, left, right, slice_null);
2203 this->resize(sv.
size());
2208template<
class Val,
class BV>
2214 this->keep_range_no_check(left, right, slice_null);
2220template<
class Val,
class BV>
2224 unsigned slices = (unsigned)this->get_bmatrix().rows();
2225 for (
unsigned j = 0; j < slices; ++j)
2228 bv->bit_and(bv_mask);
2234template<
class Val,
class BV>
2240 return (sv_value > val) - (sv_value < val);
2245template<
class Val,
class BV>
2249 return parent_type::equal(sv, null_able);
2254template<
class Val,
class BV>
2259 return it_type(
this);
2264template<
class Val,
class BV>
2268 this->bmatr_.set_allocator_pool(pool_ptr);
2277template<
class Val,
class BV>
2279: sv_(0), pos_(
bm::
id_max), buf_ptr_(0)
2284template<
class Val,
class BV>
2287: sv_(it.sv_), pos_(it.pos_), buf_ptr_(0)
2292template<
class Val,
class BV>
2296: sv_(sv), buf_ptr_(0)
2304template<
class Val,
class BV>
2308: sv_(sv), buf_ptr_(0)
2316template<
class Val,
class BV>
2319 pos_ = (!sv_ || pos >= sv_->size()) ?
bm::id_max : pos;
2325template<
class Val,
class BV>
2331 if (pos_ >= sv_->size())
2347template<
class Val,
class BV>
2358 sv_->extract(buf_ptr_,
n_buf_size, pos_,
true);
2366template<
class Val,
class BV>
2377 if (++buf_ptr_ < buf_end)
2382 if (pos_ >= sv_->size())
2387 if (buf_ptr_ >= buf_end)
2394template<
class Val,
class BV>
2397 return sv_->is_null(pos_);
2406template<
class Val,
class BV>
2412template<
class Val,
class BV>
2420 bv_null_ = sv_->get_null_bvect();
2426 buf_ptr_ = 0; bv_null_ = 0;
2432template<
class Val,
class BV>
2435: sv_(bi.sv_), bv_null_(bi.bv_null_), buf_ptr_(0),
2436 set_not_null_(bi.set_not_null_),
2437 prev_nb_(bi.prev_nb_), opt_mode_(bi.opt_mode_)
2449template<
class Val,
class BV>
2452: sv_(bi.sv_), bv_null_(bi.bv_null_), buf_ptr_(bi.buf_ptr_),
2453 set_not_null_(bi.set_not_null_),
2454 prev_nb_(bi.prev_nb_), opt_mode_(bi.opt_mode_)
2456 buffer_.swap(bi.buffer_);
2457 buf_ptr_ = bi.buf_ptr_;
2462template<
class Val,
class BV>
2470template<
class Val,
class BV>
2481 this->add_value_no_null(v);
2485 bv_null_->set_bit_no_check(sz + buf_idx);
2491template<
class Val,
class BV>
2512template<
class Val,
class BV>
2521template<
class Val,
class BV>
2533 sv_->push_back_null(count);
2539template<
class Val,
class BV>
2547template<
class Val,
class BV>
2556 sv_->import_back_u(arr, arr_size,
false);
2561 sv_->optimize_block(prev_nb_, opt_mode_);
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!)
Base class for bit-transposed(bit-sliced) sparse vector construction.
void freeze_matr()
Turn on RO mode.
void resize(size_type new_size, bool set_null)
void copy_from(const base_sparse_vector< Val, BV, MAX_SIZE > &bsv)
static unsigned_value_type s2u(value_type v) BMNOEXCEPT
Convert signed value type to unsigned representation.
const bmatrix_type & get_bmatrix() const BMNOEXCEPT
bmatrix_type bmatr_
bit-transposed matrix
allocator_type::allocator_pool_type allocator_pool_type
size_type size_
array size
std::make_unsigned< value_type >::type unsigned_value_type
void bit_sub_rows(const bvector_type &bv, bool use_null)
Set SUB (MINUS) operation on all existing bit-slices.
bvector_type bvector_type
unsigned short value_type
BV::allocator_type allocator_type
bool is_nullable() const BMNOEXCEPT
check if container supports NULL(unassigned) values
Basic dense bit-matrix class.
size_type get_null_idx() const BMNOEXCEPT
return index of the NULL vector
const bvector_type * row(size_type i) const BMNOEXCEPT
size_type rows() const BMNOEXCEPT
Constant iterator designed to enumerate "ON" 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
bvector_size_type size_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*()
noop
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
void operator=(value_type v)
push value to the vector
bvector_type::block_idx_type block_idx_type
void operator=(const back_insert_iterator &bi)
back_insert_iterator & operator++()
noop
back_insert_iterator & operator++(int)
noop
sparse_vector_type::unsigned_value_type unsigned_value_type
void add_null()
add NULL (no-value) to the container
bvector_type * get_null_bvect() const BMNOEXCEPT
Get access to not-null vector.
sparse_vector_type::size_type size_type
bool flush()
flush the accumulated buffer
back_insert_iterator(back_insert_iterator &&bi) BMNOEXCEPT
move constructor
back_insert_iterator(const back_insert_iterator &bi)
void add_value_no_null(value_type v)
add value to the buffer without changing the NULL vector
void add(value_type v)
add value to the container
void disable_set_null() BMNOEXCEPT
Reconfigure 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
sparse_vector< Val, BV > sparse_vector_type
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.
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
const_iterator operator++(int)
Advance to the next available value.
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
const_iterator & operator++() BMNOEXCEPT
Advance to the next available value.
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
bool operator>=(const const_iterator &it) const BMNOEXCEPT
Reference class to access elements via common [] operator.
reference & operator=(const reference &ref)
reference & operator=(value_type val)
bool operator==(const reference &ref) const BMNOEXCEPT
bool is_null() const BMNOEXCEPT
reference(sparse_vector< Val, BV > &sv, size_type idx) BMNOEXCEPT
sparse vector de-serializer
algorithms for sparse_vector scan/search
succinct sparse vector with runtime compression using bit-slicing / transposition method
unsigned char * init_remap_buffer() BMNOEXCEPT
void inc(size_type idx)
increment specified element by one
bvector_type::size_type size_type
void set_value(size_type idx, value_type v, bool need_clear)
set value without checking boundaries
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 set_value_no_null(size_type idx, value_type v, bool need_clear)
set value without checking boundaries or support of NULL
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
static constexpr bool is_str() BMNOEXCEPT
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, build fast access index
const value_type & const_reference
void push_back(value_type v)
push value back into vector
remap_matrix_type * get_remap_matrix()
void sync_size() BMNOEXCEPT
recalculate size to exclude tail NULL elements After this call size() will return the true size of th...
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
unsigned_value_type get_unsigned(size_type idx) const BMNOEXCEPT
void clear_all(bool free_mem) BMNOEXCEPT
resize to zero, free memory
bvector_type * bvector_type_ptr
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< Val, BV > & operator=(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
bool try_get(size_type idx, value_type &v) const BMNOEXCEPT
get specified element with NOT NULL check
size_t remap_size() const BMNOEXCEPT
void clear(size_type idx, bool set_null)
clear specified element with bounds checking and automatic resize
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,...
void resize_internal(size_type sz, bool set_null=true)
static constexpr bool is_compressed() BMNOEXCEPT
various type traits
constexpr bool is_remap() const BMNOEXCEPT
void inc_no_null(size_type idx, value_type v)
increment by v without chnaging NULL vector or size
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
void import_u_nocheck(const unsigned_value_type *arr, size_type arr_size, size_type offset, bool set_not_null)
void inc_no_null(size_type idx)
Increment element by 1 without chnaging NULL vector or size.
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(),...
void freeze()
Turn sparse vector into immutable mode Read-only (immutable) vector uses less memory and allows faste...
int compare(size_type idx, const value_type val) const BMNOEXCEPT
Compare vector element with argument.
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
void swap(sparse_vector< Val, BV > &sv) BMNOEXCEPT
content exchange
void set_null(const bvector_type &bv_idx)
Set NULL all elements set as 1 in the argument vector.
bm::heap_matrix< unsigned char, sizeof(value_type), 256, typename bvector_type::allocator_type > remap_matrix_type
unused remap matrix type for compatibility with the sparse serializer
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.
size_type extract_planes(value_type *arr, size_type size, size_type offset, bool zero_mem=true) const
extract medium window without use of masking vector
static void throw_bad_alloc()
throw bad alloc
void keep_range(size_type left, size_type right, bm::null_support slice_null=bm::use_null)
Keep only specified interval in the sparse vector, clear all other elements.
void import_u(const unsigned_value_type *arr, size_type arr_size, size_type offset, bool set_not_null)
Import list of elements from a C-style array.
void join_null_slice(const sparse_vector< Val, BV > &sv)
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.
void push_back_null()
push back NULL value
sparse_vector< Val, BV > & clear_range(size_type left, size_type right, bool set_null=false)
clear range (assign bit 0 for all planes)
void erase(size_type idx, bool erase_null=true)
erase specified element from container
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.
value_type get_no_check(size_type idx) const BMNOEXCEPT
get specified element without checking boundary conditions
const remap_matrix_type * get_remap_matrix() const
bm::basic_bmatrix< BV > bmatrix_type
void clear(const bvector_type &bv_idx)
Set vector elements spcified by argument bit-vector to zero Note that set to 0 elements are NOT going...
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)
void copy_range(const sparse_vector< Val, BV > &sv, size_type left, size_type right, bm::null_support slice_null=bm::use_null)
copy range of values from another sparse vector
const unsigned char * get_remap_buffer() const BMNOEXCEPT
const_iterator get_const_iterator(size_type idx) const BMNOEXCEPT
Get const_itertor re-positioned to specific element.
parent_type::unsigned_value_type unsigned_value_type
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 import_back_u(const unsigned_value_type *arr, size_type arr_size, bool set_not_null=true)
Import list of elements from a C-style array (pushed back)
static void u2s_translate(value_type *arr, size_type sz) BMNOEXCEPT
void filter(const bvector_type &bv_mask)
Apply value filter, defined by mask vector.
const bvector_type * bvector_type_const_ptr
bool is_ro() const BMNOEXCEPT
Returns true if vector is read-only.
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 planes
unsigned short bitscan(V w, B *bits) BMNOEXCEPT
Templated Bitscan with dynamic dispatch for best type.
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
int 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.
const unsigned set_block_mask
unsigned gap_bfind(const T *BMRESTRICT buf, unsigned pos, unsigned *BMRESTRICT is_set) BMNOEXCEPT
const unsigned set_word_shift
BMFORCEINLINE void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two variables.
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
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.
static unsigned rows() BMNOEXCEPT
const T * row(unsigned row_idx) const BMNOEXCEPT