Go to the documentation of this file. 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)
57 template<
class Val,
class SV>
101 : csv_(csv), idx_(idx)
105 {
return bool(*
this) == bool(ref); }
106 bool is_null()
const {
return csv_.is_null(idx_); }
133 max_id_ = csv.max_id_;
134 in_sync_ = csv.in_sync_;
137 bv_blocks_ptr_->copy_from(*(csv.bv_blocks_ptr_));
154 max_id_ = csv.max_id_; in_sync_ = csv.in_sync_;
157 bv_blocks_ptr_->copy_from(*(csv.bv_blocks_ptr_));
177 bool empty()
const {
return sv_.empty(); }
261 bool zero_mem =
true)
const;
326 statistics* stat = 0);
355 void sync(
bool force);
393 static unsigned plains() {
return sparse_vector_type::plains(); }
396 static unsigned stored_plains() {
return sparse_vector_type::stored_plains(); }
444 void construct_bv_blocks();
445 void free_bv_blocks();
462 template<
class Val,
class SV>
467 : sv_(null_able, ap, bv_max_size, alloc),
468 max_id_(0), in_sync_(false)
473 construct_bv_blocks();
478 template<
class Val,
class SV>
486 template<
class Val,
class SV>
490 max_id_(csv.max_id_),
491 in_sync_(csv.in_sync_)
495 construct_bv_blocks();
498 bv_blocks_ptr_->copy_from(*(csv.bv_blocks_ptr_));
504 template<
class Val,
class SV>
507 max_id_(0), in_sync_(
false)
512 max_id_ = csv.max_id_; in_sync_ = csv.in_sync_;
514 bv_blocks_ptr_ = csv.bv_blocks_ptr_; csv.bv_blocks_ptr_ = 0;
520 template<
class Val,
class SV>
529 template<
class Val,
class SV>
537 sv_.throw_range_error(
"compressed sparse vector push_back() range error");
539 push_back_no_check(idx, v);
544 template<
class Val,
class SV>
550 bv_null->set_bit_no_check(idx);
551 sv_.push_back_no_null(v);
559 template<
class Val,
class SV>
565 bool found = bv_null->test(idx);
568 size_type sv_idx = bv_null->count_range(0, idx);
569 bv_null->clear_bit_no_check(idx);
576 template<
class Val,
class SV>
582 bool found = bv_null->test(idx);
583 size_type sv_idx = bv_null->count_range(0, idx);
587 sv_.set(--sv_idx, v);
591 sv_.insert_value_no_null(sv_idx, v);
592 bv_null->set_bit_no_check(idx);
602 template<
class Val,
class SV>
608 if (max_id_ != csv.max_id_)
610 bool same_sv = sv_.equal(csv.sv_);
616 template<
class Val,
class SV>
625 const bvector_type* bv_null_src = sv_src.get_null_bvector();
634 *bv_null = *bv_null_src;
638 unsigned src_plains = sv_src.plains();
639 for (
unsigned i = 0; i < src_plains; ++i)
645 rank_compr.
compress(*bv_plain, *bv_null, *bv_src_plain);
657 template<
class Val,
class SV>
662 const bvector_type* bv_null_src = this->get_null_bvector();
671 *bv_null = *bv_null_src;
675 unsigned src_plains = sv_.plains();
676 for (
unsigned i = 0; i < src_plains; ++i)
682 rank_compr.
decompress(*bv_plain, *bv_null, *bv_src_plain);
685 sv.resize(this->size());
690 template<
class Val,
class SV>
693 if (in_sync_ && force ==
false)
697 bv_null->build_rs_index(bv_blocks_ptr_);
700 bool found = bv_null->find_reverse(max_id_);
711 template<
class Val,
class SV>
719 *idx_to = bv_null->count_to_test(idx, *bv_blocks_ptr_);
723 bool found = bv_null->test(idx);
730 *idx_to = bv_null->count_range(0, idx);
733 return bool(*idx_to);
738 template<
class Val,
class SV>
743 bool found = resolve(idx, &sv_idx);
746 sv_.throw_range_error(
"compressed collection item not found");
748 return sv_.at(--sv_idx);
753 template<
class Val,
class SV>
758 bool found = resolve(idx, &sv_idx);
762 return sv_.get(--sv_idx);
767 template<
class Val,
class SV>
772 return !(bv_null->test(idx));
777 template<
class Val,
class SV>
782 sv_.optimize(temp_block, opt_mode, (
typename sparse_vector_type::statistics*)st);
786 st->memory_used += bv_blocks_ptr_->get_total() *
787 (
sizeof(
typename rs_index_type::size_type)
788 +
sizeof(
typename rs_index_type::sb_pair_type));
794 template<
class Val,
class SV>
798 in_sync_ =
false; max_id_ = 0;
803 template<
class Val,
class SV>
808 sv_.calc_stat((
typename sparse_vector_type::statistics*)st);
812 st->memory_used += bv_blocks_ptr_->get_total() *
813 (
sizeof(
typename rs_index_type::size_type)
814 +
sizeof(
typename rs_index_type::sb_pair_type));
820 template<
class Val,
class SV>
824 return sv_.get_null_bvector();
829 template<
class Val,
class SV>
837 b = bv_null->select(rank, idx, *bv_blocks_ptr_);
839 b = bv_null->find_rank(rank, 0, idx);
846 template<
class Val,
class SV>
859 if (idx_from >= this->size())
867 size_type rank = bv_null->count_to(idx_from, *bv_blocks_ptr_);
868 bool b = bv_null->test(idx_from);
872 if (idx_from + size <= i)
885 while (idx_from < en_idx)
907 template<
class Val,
class SV>
914 bv_blocks_ptr_ =
new(bv_blocks_ptr_) rs_index_type();
919 template<
class Val,
class SV>
920 void rsc_sparse_vector<Val, SV>::free_bv_blocks()
924 bv_blocks_ptr_->~rs_index_type();
bvector_type::allocator_type allocator_type
bool empty() const
return true if vector is empty
void decompress(BV &bv_target, const BV &bv_idx, const BV &bv_src)
Rank decompression.
Reference class to access elements via common [] operator.
const sparse_vector_type & get_sv() const
access dense vector
rs_index< allocator_type > rs_index_type
size_type decode(value_type *arr, size_type idx_from, size_type size, bool zero_mem=true) const
sparse vector de-serializer
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
bool valid() const
Checks if iterator is still valid. Analog of != 0 comparison for pointers.
void load_to(sparse_vector_type &sv) const
Exort compressed vector to a sparse vector (with NULLs)
optmode
Optimization mode Every next level means additional checks (better compression vs time)
const unsigned char * get_remap_buffer() const
bool find_rank(size_type rank, size_type &idx) const
find position of compressed element by its rank
bvector_type::rs_index_type rs_index_type
void * aligned_new_malloc(size_t size)
Aligned malloc (unlike classic malloc it throws bad_alloc exception)
bool is_null(size_type idx) const
test if specified element is NULL
void advance()
advance iterator forward by one
void resize_internal(size_type sz)
bool operator==(const reference &ref) const
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...
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
Constant iterator designed to enumerate "ON" bits.
algorithms for sparse_vector scan/seach
value_type operator[](size_type idx) const
get specified element without bounds checking
value_type get(size_type idx) const
get specified element without bounds checking
size_t remap_size() const
void unsync()
Unsync the prefix sum table.
const bvector_type * get_null_bvector() const
Get bit-vector of assigned values (or NULL)
const typedef bvector_type * bvector_type_const_ptr
Bitvector Bit-vector container with runtime compression of bits.
pre-processor un-defines to avoid global space pollution (internal)
@ use_null
support "non-assigned" or "NULL" logic
void clear() BMNOEXEPT
resize to zero, free memory
bvector_type_const_ptr get_plain(unsigned i) const
get access to bit-plain, function checks and creates a plain
size_type effective_vector_max() const
Always 1 (non-matrix type)
rsc_sparse_vector< Val, SV > & operator=(const rsc_sparse_vector< Val, SV > &csv)
@ opt_compress
compress blocks when possible (GAP/prefix sum)
void calc_stat(struct rsc_sparse_vector< Val, SV >::statistics *st) const
Calculates memory statistics.
bool resolve(size_type idx, size_type *idx_to) const
Resolve logical address to access via rank compressed address.
reference(rsc_sparse_vector< Val, SV > &csv, size_type idx) BMNOEXEPT
bvector_type_ptr get_plain(unsigned i)
bvector_type * bvector_type_ptr
bool equal(const rsc_sparse_vector< Val, SV > &csv) const
check if another vector has the same content
void load_from(const sparse_vector_type &sv_src)
Load compressed vector from a sparse vector (with NULLs)
void sync()
Re-calculate prefix sum table used for rank search (if necessary)
static unsigned plains()
get total number of bit-plains in the vector
const typedef value_type & const_reference
void aligned_free(void *ptr)
Aligned free.
SV::bvector_type bvector_type
size_type size() const
return size of the vector
Rank-Select compressed sparse vector.
static bool is_compressed()
trait if sparse vector is "compressed" (true)
bool is_nullable() const
if container supports NULL(unassigned) values (true)
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 plains
size_type size_internal() const
void push_back(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
unsigned char * init_remap_buffer()
null_support
NULL-able value support.
void push_back_no_check(size_type idx, value_type v)
rsc_sparse_vector< Val, SV > & operator=(rsc_sparse_vector< Val, SV > &&csv) BMNOEXEPT
bool in_sync() const
returns true if prefix sum table is in sync with the vector
bvector_type::allocation_policy allocation_policy_type
bvector_type::enumerator bvector_enumerator_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())
unsigned effective_plains() const
static unsigned stored_plains()
Number of stored bit-plains (value plains + extra.
void set_null(size_type idx)
set specified element to NULL RSC vector actually erases element when it is set to NULL (expensive).
value_type at(size_type idx) const
access specified element with bounds checking
size_type effective_size() const
size of internal dense vector
Structure with statistical information about memory allocation footprint, serialization projection,...
SV::const_iterator sparse_vector_const_iterator