1#ifndef BMSPARSEVEC_COMPR_H__INCLUDED__
2#define BMSPARSEVEC_COMPR_H__INCLUDED__
31#ifndef BM__H__INCLUDED__
34# error missing include (bm.h or bm64.h)
57template<
class Val,
class SV>
104 : csv_(csv), idx_(idx)
108 {
return bool(*
this) == bool(ref); }
155 {
return (pos_ == it.pos_) && (csv_ == it.csv_); }
159 {
return pos_ < it.pos_; }
161 {
return pos_ <= it.pos_; }
163 {
return pos_ > it.pos_; }
165 {
return pos_ >= it.pos_; }
205 n_buf_size = 1024 * 8
259 this->
flush(); sv_bi_ = bi.sv_bi_;
267 { this->
add(v);
return *
this; }
337 size_ = csv.size_; max_id_ = csv.max_id_;
338 in_sync_ = csv.in_sync_;
341 rs_idx_->copy_from(*(csv.rs_idx_));
358 size_ = csv.size_; max_id_ = csv.max_id_; in_sync_ = csv.in_sync_;
360 rs_idx_->copy_from(*(csv.rs_idx_));
575 bool zero_mem = true) const;
691 throw_no_rsc_index();
721 statistics* stat = 0);
827 {
return sv_.get_slice(i); }
830 {
return sv_.get_create_slice(i); }
836 {
return sv_.effective_slices(); }
842 {
return sparse_vector_type::slices(); }
846 {
return sparse_vector_type::stored_slices(); }
867 {
return sv_.get_bmatrix(); }
873 {
return sv_.get_bmatrix(); }
881 {
return in_sync_ ? rs_idx_ : 0; }
884 { sv_.mark_null_idx(null_idx); }
913 sv_.resize_internal(sz);
925 bm::heap_matrix<
unsigned char, 1, 1,
938 {
return sparse_vector_type::s2u(v); }
941 {
return sparse_vector_type::u2s(v); }
946 void construct_rs_index();
948 void free_rs_index();
956 void throw_no_rsc_index();
971 bool is_dense_ =
false;
978template<
class Val,
class SV>
983: sv_(
bm::
use_null, ap, bv_max_size, alloc), in_sync_(false)
989 construct_rs_index();
994template<
class Val,
class SV>
998 construct_rs_index();
1003 bool found = bv->find_reverse(max_id_);
1006 size_ = max_id_ + 1;
1013 size_ = max_id_ = 0;
1019template<
class Val,
class SV>
1027template<
class Val,
class SV>
1030: sv_(csv.sv_), size_(csv.size_), max_id_(csv.max_id_), in_sync_(csv.in_sync_)
1034 construct_rs_index();
1036 rs_idx_->copy_from(*(csv.rs_idx_));
1041template<
class Val,
class SV>
1046 max_id_(0), in_sync_(
false)
1051 size_ = csv.size_; max_id_ = csv.max_id_; in_sync_ = csv.in_sync_;
1052 rs_idx_ = csv.rs_idx_; csv.rs_idx_ = 0;
1058template<
class Val,
class SV>
1067template<
class Val,
class SV>
1074 BM_ASSERT(sv_.get_null_bvect()->none());
1076 size_ = max_id_ = 0;
1079 if (new_size >= size_)
1082 max_id_ = new_size - 1;
1094 max_id_ = new_size - 1;
1100 size_type new_sv_size = sv_.size() - clear_size;
1101 sv_.resize_internal(new_sv_size,
false);
1102 bv_null->clear_range(new_size,
bm::id_max-1);
1105 max_id_ = new_size - 1;
1114template<
class Val,
class SV>
1120 if (idx <= max_id_ && size_)
1122 sv_.throw_range_error(
"compressed sparse vector push_back() range error");
1124 push_back_no_check(idx, v);
1129template<
class Val,
class SV>
1139template<
class Val,
class SV>
1145 bv_null->set_bit_no_check(idx);
1146 sv_.push_back_no_null(v);
1155template<
class Val,
class SV>
1161 bool found = bv_null->test(idx);
1165 size_type sv_idx = bv_null->count_range(0, idx);
1166 bv_null->clear_bit_no_check(idx);
1167 sv_.erase(--sv_idx,
false);
1175 size_ = max_id_ + 1;
1182template<
class Val,
class SV>
1187 bv_sub.bit_and(bv_idx, *bv_null);
1192 rank_compr.
compress(bv_sub_rsc, *bv_null, bv_sub);
1193 sv_.clear(bv_sub_rsc);
1202 size_type sv_idx = bv_null->count_range(0, idx);
1204 sv_.erase(--sv_idx,
false);
1206 bv_null->bit_sub(bv_sub);
1211template<
class Val,
class SV>
1217 bv_sub.bit_and(bv_idx, *bv_null);
1221 rank_compr.
compress(bv_sub_rsc, *bv_null, bv_sub);
1223 sv_.clear(bv_sub_rsc);
1228template<
class Val,
class SV>
1235 bool found = bv_null->test(idx);
1237 sv_idx = in_sync_ ? bv_null->count_to(idx, *rs_idx_)
1238 : bv_null->count_range(0, idx);
1242 sv_.inc_no_null(--sv_idx);
1246 sv_.insert_value_no_null(sv_idx, 1);
1247 bv_null->set_bit_no_check(idx);
1252 size_ = max_id_ + 1;
1260template<
class Val,
class SV>
1267 bool found = bv_null->test(idx);
1269 sv_idx = in_sync_ ? bv_null->count_to(idx, *rs_idx_)
1270 : bv_null->count_range(0, idx);
1274 sv_.inc_no_null(--sv_idx, v);
1278 sv_.insert_value_no_null(sv_idx, v);
1279 bv_null->set_bit_no_check(idx);
1284 size_ = max_id_ + 1;
1292template<
class Val,
class SV>
1299 sv_idx = in_sync_ ? bv_null->count_to(idx, *rs_idx_)
1300 : bv_null->count_range(0, idx);
1303 sv_.inc_no_null(sv_idx);
1305 sv_.inc_no_null(sv_idx, v);
1311template<
class Val,
class SV>
1318 bool found = bv_null->test(idx);
1320 sv_idx = in_sync_ ? bv_null->count_to(idx, *rs_idx_)
1321 : bv_null->count_range(0, idx);
1325 sv_.set_value_no_null(--sv_idx, v,
true);
1329 sv_.insert_value_no_null(sv_idx, v);
1330 bv_null->set_bit_no_check(idx);
1335 size_ = max_id_ + 1;
1343template<
class Val,
class SV>
1349 if (max_id_ != csv.max_id_ || size_ != csv.size_)
1351 bool same_sv = sv_.equal(csv.sv_);
1357template<
class Val,
class SV>
1361 max_id_ = size_ = 0;
1366 const bvector_type* bv_null_src = sv_src.get_null_bvector();
1374 sv_.clear_all(
true);
1375 *bv_null = *bv_null_src;
1379 unsigned src_planes = sv_src.slices();
1380 for (
unsigned i = 0; i < src_planes; ++i)
1382 const bvector_type* bv_src_plane = sv_src.get_slice(i);
1386 rank_compr.
compress(*bv_plane, *bv_null, *bv_src_plane);
1398template<
class Val,
class SV>
1403 const bvector_type* bv_null_src = this->get_null_bvector();
1412 *bv_null = *bv_null_src;
1416 unsigned src_planes = sv_.slices();
1417 for (
unsigned i = 0; i < src_planes; ++i)
1419 if (
const bvector_type* bv_src_plane = sv_.get_slice(i))
1422 rank_compr.
decompress(*bv_plane, *bv_null, *bv_src_plane);
1425 sv.resize(this->size());
1430template<
class Val,
class SV>
1433 if (in_sync_ && force ==
false)
1437 bv_null->build_rs_index(rs_idx_);
1442 size_type cnt = size_ ? bv_null->count_range(0, size_-1, *rs_idx_)
1444 is_dense_ = (cnt == size_);
1452template<
class Val,
class SV>
1458 bool found = bv_null->find_reverse(max_id_);
1460 max_id_ = size_ = 0;
1462 size_ = max_id_ + 1;
1468template<
class Val,
class SV>
1476 BM_ASSERT(bv_null->get_bit(idx) ==
false);
1480 return resolve_sync(idx, idx_to);
1483 bool found = bv_null->test(idx);
1486 *idx_to = bv_null->count_range_no_check(0, idx);
1492template<
class Val,
class SV>
1507 BM_ASSERT(bv_null->get_bit(idx) ==
false);
1510 *idx_to = bv_null->count_to_test(idx, *rs_idx_);
1511 return bool(*idx_to);
1516template<
class Val,
class SV>
1525 copy_sz = bv_null->count_range(from, to, *rs_idx_);
1527 copy_sz = bv_null->count_range(from, to);
1532 sv_left = bv_null->rank_corrected(from, *rs_idx_);
1535 sv_left = bv_null->count_range(0, from);
1536 bool tl = bv_null->test(from);
1540 *idx_from = sv_left; *idx_to = sv_left + copy_sz - 1;
1547template<
class Val,
class SV>
1553 sv_.throw_range_error(
"compressed collection access error");
1555 bool found = resolve(idx, &sv_idx);
1558 sv_.throw_range_error(
"compressed collection item not found");
1560 return sv_.at(--sv_idx);
1565template<
class Val,
class SV>
1570 bool found = resolve(idx, &sv_idx);
1574 return sv_.get(--sv_idx);
1579template<
class Val,
class SV>
1584 if (!resolve(idx, &sv_idx))
1586 v = sv_.get(--sv_idx);
1592template<
class Val,
class SV>
1597 bool found = resolve_sync(idx, &sv_idx);
1600 v = sv_.get(--sv_idx);
1606template<
class Val,
class SV>
1611 return !(bv_null->test(idx));
1616template<
class Val,
class SV>
1621 sv_.optimize(temp_block, opt_mode, (
typename sparse_vector_type::statistics*)st);
1626 (
sizeof(
typename rs_index_type::size_type)
1627 +
sizeof(
typename rs_index_type::sb_pair_type));
1635template<
class Val,
class SV>
1638 sv_.clear_all(free_mem);
1639 in_sync_ =
false; max_id_ = size_ = 0;
1644template<
class Val,
class SV>
1649 sv_.calc_stat((
typename sparse_vector_type::statistics*)st);
1653 st->memory_used += rs_idx_->get_total() *
1654 (
sizeof(
typename rs_index_type::size_type)
1655 +
sizeof(
typename rs_index_type::sb_pair_type));
1661template<
class Val,
class SV>
1665 return sv_.get_null_bvector();
1670template<
class Val,
class SV>
1679 b = bv_null->select(rank, idx, *rs_idx_);
1681 b = bv_null->find_rank(rank, 0, idx);
1687template<
class Val,
class SV>
1691 throw std::domain_error(
"Rank-Select index not constructed, call sync() first");
1700template<
class Val,
class SV>
1705 bool zero_mem)
const
1710 throw_no_rsc_index();
1715 if (idx_from >= this->size())
1720 if ((idx_from + size) > this->size())
1721 size = this->size() - idx_from;
1724 size_type rank = bv_null->rank_corrected(idx_from, *rs_idx_);
1726 BM_ASSERT(rank == bv_null->count_range(0, idx_from) - bv_null->test(idx_from));
1748 arr[i++] = it.
value();
1760template<
class Val,
class SV>
1768 if (!size || (idx_from >= this->size()))
1778 if ((idx_from + size) > this->size())
1779 size = this->size() - idx_from;
1785 size_type rank = bv_null->rank_corrected(idx_from, *rs_idx_);
1787 BM_ASSERT(rank == bv_null->count_range(0, idx_from) - bv_null->test(idx_from));
1794 if (idx_from + size <= i)
1798 bv_null->count_range_no_check(idx_from, idx_from + size - 1, *rs_idx_);
1801 auto ex_sz = sv_.decode(arr_buf_tmp, rank, extract_cnt,
true);
1802 BM_ASSERT(ex_sz == extract_cnt); (void) ex_sz;
1804 for (i = 0; i < extract_cnt; ++i)
1808 arr[en_idx-idx_from] = arr_buf_tmp[i];
1818template<
class Val,
class SV>
1833 arr[0] = this->get(idx[0]);
1843 idx_tmp_buf[i] = idx[i];
1859 if (resolve(idx[i], &sv_idx))
1861 idx_tmp_buf[i] = sv_idx-1;
1874 size = sv_.gather(arr, idx_tmp_buf, size, sorted_idx);
1881template<
class Val,
class SV>
1887 rs_idx_ =
new(rs_idx_) rs_index_type();
1892template<
class Val,
class SV>
1893void rsc_sparse_vector<Val, SV>::free_rs_index()
1897 rs_idx_->~rs_index_type();
1904template<
class Val,
class SV>
1912 if (left >= csv.
size())
1915 size_ = csv.size_; max_id_ = csv.max_id_;
1918 const bvector_type* arg_bv_null = csv.sv_.get_null_bvector();
1920 bool range_valid = csv.
resolve_range(left, right, &sv_left, &sv_right);
1923 sv_.clear_all(
true); sv_.resize(size_);
1925 bv_null->copy_range(*arg_bv_null, 0, right);
1929 bv_null->copy_range(*arg_bv_null, 0, right);
1930 sv_.copy_range(csv.sv_, sv_left, sv_right,
bm::no_null);
1936template<
class Val,
class SV>
1940 BM_ASSERT(sv_.get_null_bvector()->equal(*csv.sv_.get_null_bvector()));
1947template<
class Val,
class SV>
1960 return bv_null->count_range_no_check(left, right);
1962 return bv_null->count_range_no_check(left, right, *rs_idx_);
1970template<
class Val,
class SV>
1978template<
class Val,
class SV>
1984 sv_bi_.disable_set_null();
1989template<
class Val,
class SV>
2000template<
class Val,
class SV>
2008template<
class Val,
class SV>
2015 sv_bi_.add_value_no_null(v);
2018 bv_null->set_bit_no_check(csv_->size_);
2026template<
class Val,
class SV>
2032 csv_->max_id_++; csv_->size_++;
2037template<
class Val,
class SV>
2044 csv_->max_id_+=count;
2050template<
class Val,
class SV>
2054 csv_->in_sync_ =
false;
2061template<
class Val,
class BV>
2063: csv_(0), pos_(
bm::
id_max), buf_ptr_(0)
2068template<
class Val,
class SV>
2071: csv_(it.csv_), pos_(it.pos_), buf_ptr_(0)
2076template<
class Val,
class SV>
2080: csv_(csv), buf_ptr_(0)
2088template<
class Val,
class SV>
2092: csv_(csv), buf_ptr_(0)
2100template<
class Val,
class SV>
2103 pos_ = (!csv_ || pos >= csv_->size()) ?
bm::id_max : pos;
2109template<
class Val,
class SV>
2115 if (pos_ >= csv_->size())
2123 if (buf_ptr_ - ((
value_type*)vbuffer_.data()) >= n_buf_size)
2131template<
class Val,
class SV>
2140 vbuffer_.reserve(n_buf_size *
sizeof(
value_type));
2141 tbuffer_.reserve(n_buf_size *
sizeof(
value_type));
2145 csv_->decode_buf(buf_ptr_, tmp_buf_ptr, pos_, n_buf_size,
true);
2153template<
class Val,
class SV>
2164 if (++buf_ptr_ < buf_end)
2169 if (pos_ >= csv_->size())
2174 if (buf_ptr_ >= buf_end)
2181template<
class Val,
class SV>
2184 return csv_->is_null(pos_);
#define BM_ASSERT_THROW(x, xerrcode)
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
Constant iterator designed to enumerate "ON" bits.
size_type value() const BMNOEXCEPT
Get current position (value)
bool advance() BMNOEXCEPT
bool valid() const BMNOEXCEPT
Checks if iterator is still valid.
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
rs_index< allocator_type > rs_index_type
Algorithms for rank compression of bit-vector.
void decompress(BV &bv_target, const BV &bv_idx, const BV &bv_src)
Rank decompression.
void compress(BV &bv_target, const BV &bv_idx, const BV &bv_src)
Rank compression algorithm based on two palallel iterators/enumerators set of source vector gets re-m...
Back insert iterator implements buffered insert, faster than generic access assignment.
back_insert_iterator & operator++()
noop
void flush()
flush the accumulated buffer
rsc_sparse_vector_type * rsc_sparse_vector_type_ptr
rsc_sparse_vector_type::sparse_vector_type sparse_vector_type
add value to the buffer without changing the NULL vector
back_insert_iterator & operator++(int)
noop
void add(value_type v)
add value to the container
std::output_iterator_tag iterator_category
rsc_sparse_vector_type::bvector_type bvector_type
rsc_sparse_vector< Val, SV > rsc_sparse_vector_type
rsc_sparse_vector_type::size_type size_type
back_insert_iterator & operator*()
noop
rsc_sparse_vector_type::value_type value_type
back_insert_iterator & operator=(value_type v)
push value to the vector
back_insert_iterator() BMNOEXCEPT
void add_null() BMNOEXCEPT
add NULL (no-value) to the container
sparse_vector_type::back_insert_iterator sparse_vector_bi
Const iterator to traverse the rsc sparse vector.
bool advance() BMNOEXCEPT
advance iterator forward by one
rsc_sparse_vector< Val, SV > rsc_sparse_vector_type
void skip_zero_values() BMNOEXCEPT
size_type pos() const BMNOEXCEPT
Current position (index) in the vector.
rsc_sparse_vector_type::value_type value_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
bm::byte_buffer< allocator_type > buffer_type
void go_to(size_type pos) BMNOEXCEPT
re-position to a specified position
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 is_null() const BMNOEXCEPT
Get NULL status.
rsc_sparse_vector_type::bvector_type bvector_type
std::input_iterator_tag iterator_category
rsc_sparse_vector_type * rsc_sparse_vector_type_ptr
bool valid() const BMNOEXCEPT
Returns true if iterator is at a valid position.
void invalidate() BMNOEXCEPT
Invalidate current iterator.
bool operator>=(const const_iterator &it) const BMNOEXCEPT
const_iterator & operator++() BMNOEXCEPT
Advance to the next available value.
rsc_sparse_vector_type::size_type size_type
const_iterator() BMNOEXCEPT
bvector_type::allocator_type::allocator_pool_type allocator_pool_type
value_type operator*() const
Get current position (value)
value_type value() const
Get current position (value)
bvector_type::allocator_type allocator_type
Reference class to access elements via common [] operator.
bool operator==(const reference &ref) const BMNOEXCEPT
bool is_null() const BMNOEXCEPT
reference(rsc_sparse_vector< Val, SV > &csv, size_type idx) BMNOEXCEPT
Rank-Select compressed sparse vector.
static constexpr bool is_str() BMNOEXCEPT
void clear_all(bool free_mem) BMNOEXCEPT
resize to zero, free memory
static constexpr bool is_compressed() BMNOEXCEPT
various type traits
static unsigned stored_slices()
Number of stored bit-slices (value slices + extra.
bvector_type * bvector_type_ptr
const bmatrix_type & get_bmatrix() const BMNOEXCEPT
bool try_get(size_type idx, value_type &v) const BMNOEXCEPT
get specified element with NOT NULL check
bool resolve(size_type idx, size_type *idx_to) const BMNOEXCEPT
Resolve logical address to access via rank compressed address.
void load_from(const sparse_vector_type &sv_src)
Load compressed vector from a sparse vector (with NULLs)
remap_matrix_type * get_remap_matrix()
bool is_nullable() const
if container supports NULL(unassigned) values (true)
bool resolve_sync(size_type idx, size_type *idx_to) const BMNOEXCEPT
void merge_not_null(rsc_sparse_vector< Val, SV > &csv)
merge two vectors (argument gets destroyed) It is important that both vectors have the same NULL vect...
size_type decode(value_type *arr, size_type idx_from, size_type size, bool zero_mem=true) const
C-style decode.
void freeze()
Turn sparse vector into immutable mode Read-only (immutable) vector uses less memory and allows faste...
void push_back(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
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...
back_insert_iterator get_back_inserter()
void load_to(sparse_vector_type &sv) const
Exort compressed vector to a sparse vector (with NULLs)
SV::bmatrix_type bmatrix_type
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
bm::heap_matrix< unsigned char, 1, 1, typename bvector_type::allocator_type > remap_matrix_type
unused remap matrix type for compatibility with the sparse serializer
const_iterator end() const BMNOEXCEPT
Provide const iterator access to the end
value_type at(size_type idx) const
access specified element with bounds checking
void optimize(bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, statistics *stat=0)
run memory optimization for all vector slices
void sync(bool force)
Re-calculate rank-select index for faster access to vector.
size_type count_range_notnull(size_type left, size_type right) const BMNOEXCEPT
size_type effective_vector_max() const BMNOEXCEPT
Always 1 (non-matrix type)
const rs_index_type * get_RS() const BMNOEXCEPT
SV::unsigned_value_type unsigned_value_type
rsc_sparse_vector(bm::null_support null_able=bm::use_null, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type())
void push_back_null()
push back NULL value
void unsync() BMNOEXCEPT
Unsync the prefix sum table.
bool resolve_range(size_type from, size_type to, size_type *idx_from, size_type *idx_to) const BMNOEXCEPT
size_type effective_size() const BMNOEXCEPT
size of internal dense vector
static unsigned_value_type s2u(value_type v) BMNOEXCEPT
Convert signed value type to unsigned representation.
void set_remap() BMNOEXCEPT
void set_null(size_type idx)
set specified element to NULL RSC vector actually erases element when it is set to NULL (expensive).
void inc_not_null(size_type idx, value_type v)
increment specified element by one, element MUST be NOT NULL Faster than just inc() if element is NUL...
bvector_type_const_ptr get_slice(unsigned i) const BMNOEXCEPT
get access to bit-plane, function checks and creates a plane
void resize(size_type new_size)
change vector size
void resize_internal(size_type sz)
size_type decode_buf(value_type *arr, value_type *arr_buf_tmp, size_type idx_from, size_type size, bool zero_mem=true) const BMNOEXCEPT
C-style decode (variant with external memory) Analog of decode, but requires two arrays.
size_type size_internal() const BMNOEXCEPT
SV::const_iterator sparse_vector_const_iterator
bvector_type_ptr get_create_slice(unsigned i)
constexpr bool is_remap() const BMNOEXCEPT
bool equal(const rsc_sparse_vector< Val, SV > &csv) const BMNOEXCEPT
check if another vector has the same content
value_type get(size_type idx) const BMNOEXCEPT
get specified element without bounds checking
bool empty() const BMNOEXCEPT
return true if vector is empty
const value_type & const_reference
const_iterator get_const_iterator(size_type idx) const BMNOEXCEPT
Get const_itertor re-positioned to specific element.
const bvector_type * bvector_type_const_ptr
size_t remap_size() const BMNOEXCEPT
void sync()
Re-calculate prefix sum table used for rank search (if necessary)
const remap_matrix_type * get_remap_matrix() const
const unsigned char * get_remap_buffer() const BMNOEXCEPT
void set_null(const bvector_type &bv_idx)
Set NULL all elements set as 1 in the argument vector.
bool is_null(size_type idx) const BMNOEXCEPT
test if specified element is NULL
static value_type u2s(unsigned_value_type v) BMNOEXCEPT
bmatrix_type & get_bmatrix() BMNOEXCEPT
unsigned char * init_remap_buffer() BMNOEXCEPT
void mark_null_idx(unsigned null_idx) BMNOEXCEPT
void calc_stat(struct rsc_sparse_vector< Val, SV >::statistics *st) const BMNOEXCEPT
Calculates memory statistics.
bvector_type::allocator_type allocator_type
rsc_sparse_vector(rsc_sparse_vector< Val, SV > &&csv) BMNOEXCEPT
const bvector_type * get_null_bvector() const BMNOEXCEPT
Get bit-vector of assigned values (or NULL)
const sparse_vector_type & get_sv() const BMNOEXCEPT
access dense vector
rsc_sparse_vector< Val, SV > & operator=(rsc_sparse_vector< Val, SV > &&csv) BMNOEXCEPT
void clear() BMNOEXCEPT
resize to zero, free memory
void push_back(value_type v)
add element with automatic resize
unsigned effective_slices() const BMNOEXCEPT
bool try_get_sync(size_type idx, value_type &v) const BMNOEXCEPT
get specified element with NOT NULL check Caller guarantees that the vector is in sync mode (RS-index...
bvector_type::rs_index_type rs_index_type
bool is_sync() const BMNOEXCEPT
returns true if prefix sum table is in sync with the vector
bool find_rank(size_type rank, size_type &idx) const BMNOEXCEPT
find position of compressed element by its rank
size_type size() const BMNOEXCEPT
return size of the vector
bvector_type::enumerator bvector_enumerator_type
static unsigned slices() BMNOEXCEPT
get total number of bit-slices in the vector
void push_back_null(size_type count)
push back specified amount of NULL values
bool in_sync() const BMNOEXCEPT
returns true if prefix sum table is in sync with the vector
void copy_range(const rsc_sparse_vector< Val, SV > &csv, size_type left, size_type right)
copy range of values from another sparse vector
void inc(size_type idx)
increment specified element by one
size_type gather(value_type *arr, const size_type *idx, size_type *idx_tmp_buf, size_type size, bm::sort_order sorted_idx) const
Gather elements to a C-style array.
void push_back_no_check(size_type idx, value_type v)
bool is_ro() const BMNOEXCEPT
Returns true if vector is read-only.
bvector_type::allocation_policy allocation_policy_type
SV::bvector_type bvector_type
void inc(size_type idx, value_type v)
increment specified element by one
void sync_size() BMNOEXCEPT
recalculate size to exclude tail NULL elements After this call size() will return the true size of th...
const_iterator begin() const
Provide const iterator access to container content
sparse vector de-serializer
algorithms for sparse_vector scan/search
sort_order
Sort order declaration.
null_support
NULL-able value support.
@ BM_SORTED
input set is sorted (ascending order)
@ BM_UNKNOWN
sort order unknown
@ use_null
support "non-assigned" or "NULL" logic
@ no_null
do not support NULL values
void aligned_free(void *ptr) BMNOEXCEPT
Aligned free.
void * aligned_new_malloc(size_t size)
Aligned malloc (unlike classic malloc it throws bad_alloc exception)
BMFORCEINLINE void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two variables.
unsigned long long int id64_t
const unsigned rs3_border0
Structure with statistical information about memory allocation footprint, serialization projection,...
size_t memory_used
memory usage for all blocks and service tables