bmsparsevec_compr.h
Go to the documentation of this file.
#ifndef BMSPARSEVEC_COMPR_H__INCLUDED__
#define BMSPARSEVEC_COMPR_H__INCLUDED__
/*
Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
For more information please visit: http://bitmagic.io
*/
/*! \file bmsparsevec_compr.h
\brief Compressed sparse container rsc_sparse_vector<> for integer types
*/
#include <memory.h>
#ifndef BM_NO_STL
#include <stdexcept>
#endif
#ifndef BM__H__INCLUDED__
// BitMagic utility headers do not include main "bm.h" declaration
// #include "bm.h" or "bm64.h" explicitly
# error missing include (bm.h or bm64.h)
#endif
#include "bmsparsevec.h"
#include "bmdef.h"
namespace bm
{
/*!
\brief Rank-Select compressed sparse vector
Container uses Rank-Select method of compression, where
all NULL columns gets dropped, effective address of columns is computed
using address bit-vector.
Use for cases, where memory efficiency is preferable over
single element access latency.
\ingroup sv
*/
template<class Val, class SV>
class rsc_sparse_vector
{
public:
enum bit_slices
{
sv_slices = (sizeof(Val) * 8 + 1),
sv_value_slices = (sizeof(Val) * 8)
};
typedef Val value_type;
typedef const value_type& const_reference;
typedef typename SV::size_type size_type;
typedef SV sparse_vector_type;
typedef typename SV::const_iterator sparse_vector_const_iterator;
typedef typename SV::bvector_type bvector_type;
typedef bvector_type* bvector_type_ptr;
typedef const bvector_type* bvector_type_const_ptr;
typedef typename bvector_type::allocator_type allocator_type;
typedef typename bvector_type::allocation_policy allocation_policy_type;
typedef typename bvector_type::rs_index_type rs_index_type;
typedef typename bvector_type::enumerator bvector_enumerator_type;
typedef typename SV::bmatrix_type bmatrix_type;
typedef typename SV::unsigned_value_type unsigned_value_type;
enum vector_capacity
{
max_vector_size = 1
};
struct is_remap_support { enum trait { value = false }; };
struct is_rsc_support { enum trait { value = true }; };
struct is_dynamic_splices { enum trait { value = false }; };
public:
/*! Statistical information about memory allocation details. */
struct statistics : public bv_statistics
{};
public:
/**
Reference class to access elements via common [] operator
*/
class reference
{
public:
reference(rsc_sparse_vector<Val, SV>& csv, size_type idx) BMNOEXCEPT
: csv_(csv), idx_(idx)
{}
operator value_type() const BMNOEXCEPT { return csv_.get(idx_); }
bool operator==(const reference& ref) const BMNOEXCEPT
{ return bool(*this) == bool(ref); }
bool is_null() const BMNOEXCEPT { return csv_.is_null(idx_); }
private:
rsc_sparse_vector<Val, SV>& csv_;
size_type idx_;
};
/**
Const iterator to traverse the rsc sparse vector.
Implementation uses buffer for decoding so, competing changes
to the original vector may not match the iterator returned values.
This iterator keeps an operational buffer, memory footprint is not
negligable
@ingroup sv
*/
class const_iterator
{
public:
friend class rsc_sparse_vector;
#ifndef BM_NO_STL
typedef std::input_iterator_tag iterator_category;
#endif
typedef rsc_sparse_vector<Val, SV> rsc_sparse_vector_type;
typedef rsc_sparse_vector_type* rsc_sparse_vector_type_ptr;
typedef typename rsc_sparse_vector_type::value_type value_type;
typedef typename rsc_sparse_vector_type::size_type size_type;
typedef typename rsc_sparse_vector_type::bvector_type bvector_type;
typedef typename bvector_type::allocator_type allocator_type;
typedef typename
bvector_type::allocator_type::allocator_pool_type allocator_pool_type;
typedef bm::byte_buffer<allocator_type> buffer_type;
typedef unsigned difference_type;
typedef unsigned* pointer;
typedef value_type& reference;
public:
const_iterator() BMNOEXCEPT;
const_iterator(const rsc_sparse_vector_type* csv) BMNOEXCEPT;
const_iterator(const rsc_sparse_vector_type* csv, size_type pos) BMNOEXCEPT;
const_iterator(const const_iterator& it) BMNOEXCEPT;
bool operator==(const const_iterator& it) const BMNOEXCEPT
{ return (pos_ == it.pos_) && (csv_ == it.csv_); }
bool operator!=(const const_iterator& it) const BMNOEXCEPT
{ return ! operator==(it); }
bool operator < (const const_iterator& it) const BMNOEXCEPT
{ return pos_ < it.pos_; }
bool operator <= (const const_iterator& it) const BMNOEXCEPT
{ return pos_ <= it.pos_; }
bool operator > (const const_iterator& it) const BMNOEXCEPT
{ return pos_ > it.pos_; }
bool operator >= (const const_iterator& it) const BMNOEXCEPT
{ return pos_ >= it.pos_; }
/// \brief Get current position (value)
value_type operator*() const { return this->value(); }
/// \brief Advance to the next available value
const_iterator& operator++() BMNOEXCEPT { this->advance(); return *this; }
/// \brief Advance to the next available value
const_iterator& operator++(int)
{ const_iterator tmp(*this);this->advance(); return tmp; }
/// \brief Get current position (value)
value_type value() const;
/// \brief Get NULL status
bool is_null() const BMNOEXCEPT;
/// Returns true if iterator is at a valid position
bool valid() const BMNOEXCEPT { return pos_ != bm::id_max; }
/// Invalidate current iterator
void invalidate() BMNOEXCEPT { pos_ = bm::id_max; }
/// Current position (index) in the vector
size_type pos() const BMNOEXCEPT{ return pos_; }
/// re-position to a specified position
void go_to(size_type pos) BMNOEXCEPT;
/// advance iterator forward by one
/// @return true if it is still valid
bool advance() BMNOEXCEPT;
void skip_zero_values() BMNOEXCEPT;
private:
enum buf_size_e
{
n_buf_size = 1024 * 8
};
private:
const rsc_sparse_vector_type* csv_; ///!< ptr to parent
size_type pos_; ///!< Position
mutable buffer_type vbuffer_; ///!< value buffer
mutable buffer_type tbuffer_; ///!< temp buffer
mutable value_type* buf_ptr_; ///!< position in the buffer
};
/**
Back insert iterator implements buffered insert, faster than generic
access assignment.
Limitations for buffered inserter:
1. Do not use more than one inserter per vector at a time
2. Use method flush() at the end to send the rest of accumulated buffer
flush is happening automatically on destruction, but if flush produces an
exception (for whatever reason) it will be an exception in destructor.
As such, explicit flush() is safer way to finilize the sparse vector load.
@ingroup sv
*/
class back_insert_iterator
{
public:
#ifndef BM_NO_STL
typedef std::output_iterator_tag iterator_category;
#endif
typedef rsc_sparse_vector<Val, SV> rsc_sparse_vector_type;
typedef rsc_sparse_vector_type* rsc_sparse_vector_type_ptr;
typedef typename rsc_sparse_vector_type::value_type value_type;
typedef typename rsc_sparse_vector_type::size_type size_type;
typedef typename rsc_sparse_vector_type::bvector_type bvector_type;
typedef void difference_type;
typedef void pointer;
typedef void reference;
public:
/*! @name Construction and assignment */
///@{
back_insert_iterator() BMNOEXCEPT;
back_insert_iterator(rsc_sparse_vector_type* csv) ;
back_insert_iterator(const back_insert_iterator& bi);
void operator=(const back_insert_iterator& bi)
{
BM_ASSERT(bi.empty());
this->flush(); sv_bi_ = bi.sv_bi_;
}
~back_insert_iterator();
///@}
/** push value to the vector */
back_insert_iterator& operator=(value_type v)
{ this->add(v); return *this; }
/** noop */
back_insert_iterator& operator*() { return *this; }
/** noop */
back_insert_iterator& operator++() { return *this; }
/** noop */
back_insert_iterator& operator++( int ) { return *this; }
/** add value to the container*/
void add(value_type v);
/** add NULL (no-value) to the container */
void add_null() BMNOEXCEPT;
/** add a series of consequitve NULLs (no-value) to the container */
void add_null(size_type count) BMNOEXCEPT;
/** flush the accumulated buffer */
void flush();
protected:
/** add value to the buffer without changing the NULL vector
@param v - value to push back
@return index of added value in the internal buffer
@internal
*/
///size_type add_value(value_type v);
typedef rsc_sparse_vector_type::sparse_vector_type sparse_vector_type;
typedef
typename sparse_vector_type::back_insert_iterator sparse_vector_bi;
private:
rsc_sparse_vector_type* csv_; ///!< pointer on the parent vector
sparse_vector_bi sv_bi_;
};
public:
// ------------------------------------------------------------
/*! @name Construction and assignment */
//@{
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());
/**
Contructor to pre-initialize the list of assigned (not NULL) elements.
If the list of not NULL elements is known upfront it can help to
pre-declare it, enable rank-select index and then use set function.
This scenario gives significant speed boost, comparing random assignment
@param bv_null - not NULL vector for the container
*/
rsc_sparse_vector(const bvector_type& bv_null);
~rsc_sparse_vector();
/*! copy-ctor */
rsc_sparse_vector(const rsc_sparse_vector<Val, SV>& csv);
/*! copy assignmment operator */
rsc_sparse_vector<Val,SV>& operator=(const rsc_sparse_vector<Val, SV>& csv)
{
if (this != &csv)
{
sv_ = csv.sv_;
size_ = csv.size_; max_id_ = csv.max_id_;
in_sync_ = csv.in_sync_;
if (in_sync_)
{
rs_idx_->copy_from(*(csv.rs_idx_));
}
}
return *this;
}
#ifndef BM_NO_CXX11
/*! move-ctor */
rsc_sparse_vector(rsc_sparse_vector<Val,SV>&& csv) BMNOEXCEPT;
/*! move assignmment operator */
rsc_sparse_vector<Val,SV>& operator=(rsc_sparse_vector<Val,SV>&& csv) BMNOEXCEPT
{
if (this != &csv)
{
clear_all(true, 0);
sv_.swap(csv.sv_);
size_ = csv.size_; max_id_ = csv.max_id_; in_sync_ = csv.in_sync_;
if (in_sync_)
rs_idx_->copy_from(*(csv.rs_idx_));
}
return *this;
}
#endif
//@}
// ------------------------------------------------------------
/*! @name Size, etc */
///@{
/*! \brief return size of the vector
\return size of sparse vector
*/
size_type size() const BMNOEXCEPT;
/*! \brief return true if vector is empty
\return true if empty
*/
bool empty() const BMNOEXCEPT { return sv_.empty(); }
/**
\brief recalculate size to exclude tail NULL elements
After this call size() will return the true size of the vector
*/
void sync_size() BMNOEXCEPT;
/*! \brief change vector size
\param new_size - new vector size
*/
void resize(size_type new_size);
/*
\brief Returns count of not NULL elements (population)
in the given range [left..right]
Uses rank-select index to accelerate the search (after sync())
\param left - index of first bit start counting from
\param right - index of last bit
@sa sync
*/
size_type
count_range_notnull(size_type left, size_type right) const BMNOEXCEPT;
///@}
// ------------------------------------------------------------
/*! @name Element access */
//@{
/*!
\brief get specified element without bounds checking
\param idx - element index
\return value of the element
*/
value_type operator[](size_type idx) const { return this->get(idx); }
/*!
\brief access specified element with bounds checking
\param idx - element index
\return value of the element
*/
value_type at(size_type idx) const;
/*!
\brief get specified element without bounds checking
\param idx - element index
\return value of the element
*/
value_type get(size_type idx) const BMNOEXCEPT;
/** Get raw unsigned value first N bits
\param idx - element index in the vector
\param N_bits - number of bits to be extracted (should be > 0)
@return unsigned value for
*/
unsigned_value_type get_unsigned_bits(size_type idx,
size_type N_bits) const BMNOEXCEPT;
/**
\brief get specified element with NOT NULL check
\param idx - element index
\param v - [out] value to get
\return true if value was aquired (NOT NULL), false otherwise
@sa is_null, get
*/
bool try_get(size_type idx, value_type& v) const BMNOEXCEPT;
/**
\brief get specified element with NOT NULL check
Caller guarantees that the vector is in sync mode (RS-index access).
\param idx - element index
\param v - [out] value to get
\return true if value was aquired (NOT NULL), false otherwise
@sa is_null, get, sync
*/
bool try_get_sync(size_type idx, value_type& v) const BMNOEXCEPT;
/*!
\brief set specified element with bounds checking and automatic resize
Method cannot insert elements, so every new idx has to be greater or equal
than what it used before. Elements must be loaded in a sorted order.
\param idx - element index
\param v - element value
*/
void push_back(size_type idx, value_type v);
/*!
\brief add element with automatic resize
\param v - element value
*/
void push_back(value_type v)
{ this->push_back(size_, v); }
/*!
\brief push back specified amount of NULL values
\param count - number of NULLs to push back
*/
void push_back_null(size_type count);
/*!
\brief push back NULL value
*/
void push_back_null() { push_back_null(1); }
/*!
\brief set specified element with bounds checking and automatic resize
\param idx - element index
\param v - element value
*/
void set(size_type idx, value_type v);
/*!
\brief increment specified element by one
\param idx - element index
*/
void inc(size_type idx);
/*!
\brief increment specified element by one
\param idx - element index
\param v - increment value
*/
void inc(size_type idx, value_type v);
/*!
\brief increment specified element by one, element MUST be NOT NULL
Faster than just inc() if element is NULL - behavior is undefined
\param idx - element index
\param v - increment value
@sa inc
*/
void inc_not_null(size_type idx, value_type v);
/*!
\brief set specified element to NULL
RSC vector actually erases element when it is set to NULL (expensive).
\param idx - element index
*/
void set_null(size_type idx);
/**
Set NULL all elements set as 1 in the argument vector.
Function also clears all the values to 0.
Note: this can be a very expensive function for an RS container.
\param bv_idx - index bit-vector for elements which to be set to NULL
*/
void set_null(const bvector_type& bv_idx);
/**
Set vector elements spcified by argument bit-vector to zero
Note that set to 0 elements are NOT going to tuned to NULL (NULL qualifier is preserved)
\param bv_idx - index bit-vector for elements which to be set to 0
*/
void clear(const bvector_type& bv_idx);
/** \brief test if specified element is NULL
\param idx - element index
\return true if it is NULL false if it was assigned or container
is not configured to support assignment flags
*/
bool is_null(size_type idx) const BMNOEXCEPT;
/**
\brief Get bit-vector of assigned values (or NULL)
*/
const bvector_type* get_null_bvector() const BMNOEXCEPT;
/**
\brief find position of compressed element by its rank
\param rank - rank (virtual index in sparse vector)
\param idx - index (true position)
*/
bool find_rank(size_type rank, size_type& idx) const BMNOEXCEPT;
//@}
// ------------------------------------------------------------
/*! @name Export content to C-stype array */
///@{
/**
\brief C-style decode
\param arr - decode target array (must be properly sized)
\param idx_from - start address to decode
\param size - number of elements to decode
\param zero_mem - flag if array needs to beset to zeros first
@return actual decoded size
@sa decode_buf
*/
size_type decode(value_type* arr,
size_type idx_from,
size_type size,
bool zero_mem = true) const;
/**
\brief C-style decode (variant with external memory)
Analog of decode, but requires two arrays.
Faster than decode in many cases.
\param arr - decode target array (must be properly sized)
\param arr_buf_tmp - decode temp bufer (must be same size of arr)
\param idx_from - start address to decode
\param size - number of elements to decode
\param zero_mem - flag if array needs to beset to zeros first
@return actual decoded size
@sa decode
*/
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;
/*!
\brief Gather elements to a C-style array
Gather collects values from different locations, for best
performance feed it with sorted list of indexes.
Faster than one-by-one random access.
For efficiency, this is left as a low level function,
it does not do any bounds checking on the target array, it will
override memory and crash if you are not careful with allocation
and request size.
\param arr - destination array
\param idx - index list to gather elements (read only)
\param idx_tmp_buf - temp scratch buffer for index rank-select index translation
must be correctly allocated to match size. No value initialization requirement.
\param size - decoding index list size (array allocation should match)
\param sorted_idx - sort order directive for the idx array
(BM_UNSORTED, BM_SORTED, BM_UNKNOWN)
Sort order affects both performance and correctness(!), use BM_UNKNOWN
if not sure.
\return number of actually exported elements (can be less than requested)
\sa decode
*/
size_type gather(value_type* arr,
const size_type* idx,
size_type* idx_tmp_buf,
size_type size,
bm::sort_order sorted_idx) const;
///@}
// ------------------------------------------------------------
/*! @name Various traits */
///@{
/**
\brief if container supports NULL(unassigned) values (true)
*/
bool is_nullable() const { return true; }
/** \brief various type traits
*/
static constexpr
bool is_compressed() BMNOEXCEPT { return true; }
static constexpr
bool is_str() BMNOEXCEPT { return false; }
///@}
// ------------------------------------------------------------
/*! @name Comparison */
///@{
/*!
\brief check if another vector has the same content
\return true, if it is the same
*/
bool equal(const rsc_sparse_vector<Val, SV>& csv) const BMNOEXCEPT;
//@}
// ------------------------------------------------------------
/*! @name Load-Export compressed vector with data */
///@{
/*!
\brief Load compressed vector from a sparse vector (with NULLs)
\param sv_src - source sparse vector
*/
void load_from(const sparse_vector_type& sv_src);
/*!
\brief Exort compressed vector to a sparse vector (with NULLs)
\param sv - target sparse vector
*/
void load_to(sparse_vector_type& sv) const;
///@}
// ------------------------------------------------------------
/*! @name Iterator access */
///@{
/** Provide const iterator access to container content */
const_iterator begin() const
{
if (!in_sync_)
throw_no_rsc_index(); // call sync() to build RSC fast access index
return const_iterator(this);
}
/** Provide const iterator access to the end */
const_iterator end() const BMNOEXCEPT
{ return const_iterator(this, bm::id_max); }
/** Get const_itertor re-positioned to specific element
@param idx - position in the sparse vector
*/
const_iterator get_const_iterator(size_type idx) const BMNOEXCEPT
{ return const_iterator(this, idx); }
back_insert_iterator get_back_inserter() { return back_insert_iterator(this); }
///@}
// ------------------------------------------------------------
/*! @name Memory optimization */
///@{
/*!
\brief run memory optimization for all vector slices
\param temp_block - pre-allocated memory block to avoid unnecessary re-allocs
\param opt_mode - requested compression depth
\param stat - memory allocation statistics after optimization
*/
void optimize(
bm::word_t* temp_block = 0,
typename bvector_type::optmode opt_mode = bvector_type::opt_compress,
statistics* stat = 0);
/*! \brief resize to zero, free memory
@param free_mem - free bit vector slices if true
*/
void clear_all(bool free_mem, unsigned) BMNOEXCEPT;
/*! \brief resize to zero, free memory
@param free_mem - free bit vector slices if true
*/
void clear() BMNOEXCEPT { clear_all(true, 0); }
/*!
@brief Calculates memory statistics.
Function fills statistics structure containing information about how
this vector uses memory and estimation of max. amount of memory
bvector needs to serialize itself.
@param st - pointer on statistics structure to be filled in.
@sa statistics
*/
void calc_stat(
struct rsc_sparse_vector<Val, SV>::statistics* st) const BMNOEXCEPT;
/**
@brief Turn sparse vector into immutable mode
Read-only (immutable) vector uses less memory and allows faster searches.
Before freezing it is recommenede to call optimize() to get full memory saving effect
@sa optimize
*/
void freeze() { sv_.freeze(); }
/** Returns true if vector is read-only */
bool is_ro() const BMNOEXCEPT { return sv_.is_ro_; }
///@}
// ------------------------------------------------------------
/*! @name Merge, split, partition data */
///@{
/**
@brief copy range of values from another sparse vector
Copy [left..right] values from the source vector,
clear everything outside the range.
\param csv - source vector
\param left - index from in losed diapason of [left..right]
\param right - index to in losed diapason of [left..right]
*/
void copy_range(const rsc_sparse_vector<Val, SV>& csv,
size_type left, size_type right);
/**
@brief merge two vectors (argument gets destroyed)
It is important that both vectors have the same NULL vectors
@param csv - [in,out] argumnet vector to merge
(works like move so arg should not be used after the merge)
*/
void merge_not_null(rsc_sparse_vector<Val, SV>& csv);
///@}
// ------------------------------------------------------------
/*! @name Fast access structues sync */
///@{
/*!
\brief Re-calculate rank-select index for faster access to vector
\param force - force recalculation even if it is already recalculated
*/
void sync(bool force);
/*!
\brief Re-calculate prefix sum table used for rank search (if necessary)
*/
void sync() { sync(false); }
/*!
\brief returns true if prefix sum table is in sync with the vector
*/
bool in_sync() const BMNOEXCEPT { return in_sync_; }
/*!
\brief returns true if prefix sum table is in sync with the vector
*/
bool is_sync() const BMNOEXCEPT { return in_sync_; }
/*!
\brief Unsync the prefix sum table
*/
void unsync() BMNOEXCEPT { in_sync_ = is_dense_ = false; }
///@}
// ------------------------------------------------------------
/*! @name Access to internals */
///@{
/*!
\brief get access to bit-plane, function checks and creates a plane
\return bit-vector for the bit slice
*/
bvector_type_const_ptr get_slice(unsigned i) const BMNOEXCEPT
{ return sv_.get_slice(i); }
bvector_type_ptr get_create_slice(unsigned i)
{ return sv_.get_create_slice(i); }
bvector_type_ptr slice(unsigned i)
{ return sv_.slice(i); }
/*!
Number of effective bit-slices in the value type
*/
unsigned effective_slices() const BMNOEXCEPT
{ return sv_.effective_slices(); }
/*!
\brief get total number of bit-slices in the vector
*/
static unsigned slices() BMNOEXCEPT
{ return sparse_vector_type::slices(); }
/** Number of stored bit-slices (value slices + extra */
static unsigned stored_slices()
{ return sparse_vector_type::stored_slices(); }
/*!
\brief access dense vector
*/
const sparse_vector_type& get_sv() const BMNOEXCEPT { return sv_; }
/*!
\brief size of internal dense vector
*/
size_type effective_size() const BMNOEXCEPT { return sv_.size(); }
/**
\brief Always 1 (non-matrix type)
*/
size_type effective_vector_max() const BMNOEXCEPT { return 1; }
/*!
get read-only access to inetrnal bit-matrix
*/
const bmatrix_type& get_bmatrix() const BMNOEXCEPT
{ return sv_.get_bmatrix(); }
/*!
get read-only access to inetrnal bit-matrix
*/
bmatrix_type& get_bmatrix() BMNOEXCEPT
{ return sv_.get_bmatrix(); }
/*! Get Rank-Select index pointer
@return NULL if sync() was not called to construct the index
@sa sync()
*/
const rs_index_type* get_RS() const BMNOEXCEPT
{ return in_sync_ ? rs_idx_ : 0; }
void mark_null_idx(unsigned null_idx) BMNOEXCEPT
{ sv_.mark_null_idx(null_idx); }
/*!
\brief Resolve logical address to access via rank compressed address
\param idx - input id to resolve
\param idx_to - output id
\return true if id is known and resolved successfully
@internal
*/
bool resolve(size_type idx, size_type* idx_to) const BMNOEXCEPT;
///@}
protected:
enum octet_slices
{
sv_octet_slices = sizeof(value_type)
};
bool resolve_sync(size_type idx, size_type* idx_to) const BMNOEXCEPT;
bool resolve_range(size_type from, size_type to,
size_type* idx_from, size_type* idx_to) const BMNOEXCEPT;
void resize_internal(size_type sz)
{
sv_.resize_internal(sz);
}
size_type size_internal() const BMNOEXCEPT { return sv_.size(); }
constexpr bool is_remap() const BMNOEXCEPT { return false; }
size_t remap_size() const BMNOEXCEPT { return 0; }
const unsigned char* get_remap_buffer() const BMNOEXCEPT { return 0; }
unsigned char* init_remap_buffer() BMNOEXCEPT { return 0; }
void set_remap() BMNOEXCEPT { }
/// unused remap matrix type for compatibility with the sparse serializer
typedef
bm::heap_matrix<unsigned char, 1, 1,
typename bvector_type::allocator_type> remap_matrix_type;
const remap_matrix_type* get_remap_matrix() const { return 0; }
remap_matrix_type* get_remap_matrix() { return 0; }
void push_back_no_check(size_type idx, value_type v);
/**
Convert signed value type to unsigned representation
*/
static
unsigned_value_type s2u(value_type v) BMNOEXCEPT
{ return sparse_vector_type::s2u(v); }
static
value_type u2s(unsigned_value_type v) BMNOEXCEPT
{ return sparse_vector_type::u2s(v); }
private:
/// Allocate memory for RS index
void construct_rs_index();
/// Free rs-index
void free_rs_index();
/**
\brief throw error that RSC index not constructed (call sync())
\internal
@sa sync
*/
static
void throw_no_rsc_index();
protected:
template<class SVect, unsigned S_FACTOR> friend class sparse_vector_scanner;
template<class SVect> friend class sparse_vector_serializer;
template<class SVect> friend class sparse_vector_deserializer;
private:
sparse_vector_type sv_; ///< transpose-sparse vector for "dense" packing
size_type size_; ///< vector size (logical)
size_type max_id_; ///< control variable for sorted load
bool in_sync_; ///< flag if prefix sum is in-sync with vector
rs_index_type* rs_idx_ = 0; ///< prefix sum for rank-select translation
bool is_dense_ = false; ///< flag if vector is dense
};
//---------------------------------------------------------------------
//
//---------------------------------------------------------------------
template<class Val, class SV>
rsc_sparse_vector<Val, SV>::rsc_sparse_vector(bm::null_support null_able,
allocation_policy_type ap,
size_type bv_max_size,
const allocator_type& alloc)
: sv_(bm::use_null, ap, bv_max_size, alloc), in_sync_(false)
{
(void) null_able;
BM_ASSERT(null_able == bm::use_null);
BM_ASSERT(int(sv_value_slices) == int(SV::sv_value_slices));
size_ = max_id_ = 0;
construct_rs_index();
}
//---------------------------------------------------------------------
template<class Val, class SV>
rsc_sparse_vector<Val, SV>::rsc_sparse_vector(const bvector_type& bv_null)
: sv_(bm::use_null), in_sync_(false)
{
construct_rs_index();
bvector_type* bv = sv_.get_null_bvect();
BM_ASSERT(bv);
*bv = bv_null;
bool found = bv->find_reverse(max_id_);
if (found)
{
size_ = max_id_ + 1;
size_type sz = bv->count();
sv_.resize(sz);
}
else
{
BM_ASSERT(!bv->any());
size_ = max_id_ = 0;
}
}
//---------------------------------------------------------------------
template<class Val, class SV>
rsc_sparse_vector<Val, SV>::~rsc_sparse_vector()
{
free_rs_index();
}
//---------------------------------------------------------------------
template<class Val, class SV>
rsc_sparse_vector<Val, SV>::rsc_sparse_vector(
const rsc_sparse_vector<Val, SV>& csv)
: sv_(csv.sv_), size_(csv.size_), max_id_(csv.max_id_), in_sync_(csv.in_sync_)
{
BM_ASSERT(int(sv_value_slices) == int(SV::sv_value_slices));
construct_rs_index();
if (in_sync_)
rs_idx_->copy_from(*(csv.rs_idx_));
}
//---------------------------------------------------------------------
template<class Val, class SV>
rsc_sparse_vector<Val, SV>::rsc_sparse_vector(
rsc_sparse_vector<Val,SV>&& csv) BMNOEXCEPT
: sv_(bm::use_null),
size_(0),
max_id_(0), in_sync_(false)
{
if (this != &csv)
{
sv_.swap(csv.sv_);
size_ = csv.size_; max_id_ = csv.max_id_; in_sync_ = csv.in_sync_;
rs_idx_ = csv.rs_idx_; csv.rs_idx_ = 0;
}
}
//---------------------------------------------------------------------
template<class Val, class SV>
typename rsc_sparse_vector<Val, SV>::size_type
rsc_sparse_vector<Val, SV>::size() const BMNOEXCEPT
{
return size_;
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::resize(size_type new_size)
{
BM_ASSERT(new_size < bm::id_max);
if (!new_size) // clear memory
{
sv_.resize(0);
BM_ASSERT(sv_.get_null_bvect()->none());
in_sync_ = false;
size_ = max_id_ = 0;
return;
}
if (new_size >= size_) // vector grows
{
size_ = new_size;
max_id_ = new_size - 1;
return;
}
// vector shrinks
// compute tail rank
bvector_type* bv_null = sv_.get_null_bvect();
size_type clear_size = bv_null->count_range(new_size, bm::id_max-1);
if (!clear_size) // tail set/rank is empty
{
size_ = new_size;
max_id_ = new_size - 1;
BM_ASSERT(!bv_null->any_range(size_, bm::id_max-1));
return;
}
BM_ASSERT(sv_.size() >= clear_size);
size_type new_sv_size = sv_.size() - clear_size;
sv_.resize_internal(new_sv_size, false); // without touching NULL plane
bv_null->clear_range(new_size, bm::id_max-1);
size_ = new_size;
max_id_ = new_size - 1;
BM_ASSERT(!bv_null->any_range(size_, bm::id_max-1));
in_sync_ = false;
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::push_back(size_type idx, value_type v)
{
if (sv_.empty())
{}
else
if (idx <= max_id_ && size_)
{
sv_.throw_range_error("compressed sparse vector push_back() range error");
}
push_back_no_check(idx, v);
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::push_back_null(size_type count)
{
BM_ASSERT(size_ < bm::id_max - count); // overflow assert
size_ += count;
max_id_ = size_-1;
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::push_back_no_check(size_type idx, value_type v)
{
bvector_type* bv_null = sv_.get_null_bvect();
BM_ASSERT(bv_null);
bv_null->set_bit_no_check(idx);
sv_.push_back_no_null(v);
max_id_ = idx;
size_ = idx + 1;
in_sync_ = false;
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::set_null(size_type idx)
{
bvector_type* bv_null = sv_.get_null_bvect();
BM_ASSERT(bv_null);
bool found = bv_null->test(idx); // TODO: use extract bit
if (found)
{
// TODO: maybe RS-index is available
size_type sv_idx = bv_null->count_range(0, idx);
bv_null->clear_bit_no_check(idx);
sv_.erase(--sv_idx, false/*not delete NULL vector*/);
in_sync_ = false;
}
else
{
if (idx > max_id_)
{
max_id_ = idx;
size_ = max_id_ + 1;
}
}
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::set_null(const bvector_type& bv_idx)
{
bvector_type* bv_null = sv_.get_null_bvect();
bvector_type bv_sub; // subtraction vector cleared from NOT NULLs
bv_sub.bit_and(bv_idx, *bv_null);
// clear the main matrix to accelerate the erase in all bit-slices
{
bm::rank_compressor<bvector_type> rank_compr;
bvector_type bv_sub_rsc;
rank_compr.compress(bv_sub_rsc, *bv_null, bv_sub);
sv_.clear(bv_sub_rsc);
}
in_sync_ = false;
typename bvector_type::enumerator en(&bv_sub, 0);
for (size_type cnt = 0; en.valid(); ++en, ++cnt)
{
auto idx = *en;
size_type sv_idx = bv_null->count_range(0, idx);
sv_idx -= cnt; // correct rank for what we deleted previously
sv_.erase(--sv_idx, false/*not delete the NULL vector*/);
}
bv_null->bit_sub(bv_sub);
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::clear(const bvector_type& bv_idx)
{
const bvector_type* bv_null = sv_.get_null_bvector();
bvector_type bv_sub; // subtraction vector cleared from NOT NULLs
bv_sub.bit_and(bv_idx, *bv_null);
bm::rank_compressor<bvector_type> rank_compr;
bvector_type bv_sub_rsc;
rank_compr.compress(bv_sub_rsc, *bv_null, bv_sub);
sv_.clear(bv_sub_rsc);
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::inc(size_type idx)
{
bvector_type* bv_null = sv_.get_null_bvect();
BM_ASSERT(bv_null);
size_type sv_idx;
bool found = bv_null->test(idx);
sv_idx = in_sync_ ? bv_null->count_to(idx, *rs_idx_)
: bv_null->count_range(0, idx); // TODO: make test'n'count
if (found)
{
sv_.inc_no_null(--sv_idx);
}
else
{
sv_.insert_value_no_null(sv_idx, 1);
bv_null->set_bit_no_check(idx);
if (idx > max_id_)
{
max_id_ = idx;
size_ = max_id_ + 1;
}
in_sync_ = false;
}
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::inc(size_type idx, value_type v)
{
bvector_type* bv_null = sv_.get_null_bvect();
BM_ASSERT(bv_null);
size_type sv_idx;
bool found = bv_null->test(idx);
sv_idx = in_sync_ ? bv_null->count_to(idx, *rs_idx_)
: bv_null->count_range(0, idx); // TODO: make test'n'count
if (found)
{
sv_.inc_no_null(--sv_idx, v);
}
else
{
sv_.insert_value_no_null(sv_idx, v);
bv_null->set_bit_no_check(idx);
if (idx > max_id_)
{
max_id_ = idx;
size_ = max_id_ + 1;
}
in_sync_ = false;
}
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::inc_not_null(size_type idx, value_type v)
{
bvector_type* bv_null = sv_.get_null_bvect();
BM_ASSERT(bv_null->test(idx)); // idx must be NOT NULL
size_type sv_idx;
sv_idx = in_sync_ ? bv_null->count_to(idx, *rs_idx_)
: bv_null->count_range(0, idx); // TODO: make test'n'count
--sv_idx;
if (v == 1)
sv_.inc_no_null(sv_idx);
else
sv_.inc_no_null(sv_idx, v);
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::set(size_type idx, value_type v)
{
bvector_type* bv_null = sv_.get_null_bvect();
BM_ASSERT(bv_null);
size_type sv_idx;
bool found = bv_null->test(idx);
sv_idx = in_sync_ ? bv_null->count_to(idx, *rs_idx_)
: bv_null->count_range(0, idx); // TODO: make test'n'count
if (found)
{
sv_.set_value_no_null(--sv_idx, v, true);
}
else
{
sv_.insert_value_no_null(sv_idx, v);
bv_null->set_bit_no_check(idx);
if (idx > max_id_)
{
max_id_ = idx;
size_ = max_id_ + 1;
}
in_sync_ = false;
}
}
//---------------------------------------------------------------------
template<class Val, class SV>
bool rsc_sparse_vector<Val, SV>::equal(
const rsc_sparse_vector<Val, SV>& csv) const BMNOEXCEPT
{
if (this == &csv)
return true;
if (max_id_ != csv.max_id_ || size_ != csv.size_)
return false;
bool same_sv = sv_.equal(csv.sv_);
return same_sv;
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::load_from(
const sparse_vector_type& sv_src)
{
max_id_ = size_ = 0;
bvector_type* bv_null = sv_.get_null_bvect();
BM_ASSERT(bv_null);
const bvector_type* bv_null_src = sv_src.get_null_bvector();
if (!bv_null_src) // dense vector (no NULL columns)
{
sv_ = sv_src;
BM_ASSERT(sv_.get_null_bvect());
}
else
{
sv_.clear_all(true, 0);
*bv_null = *bv_null_src;
bm::rank_compressor<bvector_type> rank_compr; // re-used for planes
unsigned src_planes = sv_src.slices();
for (unsigned i = 0; i < src_planes; ++i)
{
const bvector_type* bv_src_plane = sv_src.get_slice(i);
if (bv_src_plane)
{
bvector_type* bv_plane = sv_.get_create_slice(i);
rank_compr.compress(*bv_plane, *bv_null, *bv_src_plane);
}
} // for
size_type count = bv_null->count(); // set correct sizes
sv_.resize(count);
}
sync(true);
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::load_to(sparse_vector_type& sv) const
{
sv.clear_all(true, 0);
const bvector_type* bv_null_src = this->get_null_bvector();
if (!bv_null_src)
{
BM_ASSERT(bv_null_src);
return;
}
bvector_type* bv_null = sv.get_null_bvect();
BM_ASSERT(bv_null);
*bv_null = *bv_null_src;
bm::rank_compressor<bvector_type> rank_compr; // re-used for planes
unsigned src_planes = sv_.slices();
for (unsigned i = 0; i < src_planes; ++i)
{
if (const bvector_type* bv_src_plane = sv_.get_slice(i))
{
bvector_type* bv_plane = sv.get_create_slice(i);
rank_compr.decompress(*bv_plane, *bv_null, *bv_src_plane);
}
} // for i
sv.resize(this->size());
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::sync(bool force)
{
if (in_sync_ && force == false)
return; // nothing to do
const bvector_type* bv_null = sv_.get_null_bvector();
BM_ASSERT(bv_null);
bv_null->build_rs_index(rs_idx_); // compute popcount prefix list
sv_.is_ro_ = bv_null->is_ro();
if (force)
sync_size();
size_type cnt = size_ ? bv_null->count_range(0, size_-1, *rs_idx_)
: 0;
is_dense_ = (cnt == size_); // dense vector?
BM_ASSERT(size_ >= bv_null->count());
in_sync_ = true;
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::sync_size() BMNOEXCEPT
{
const bvector_type* bv_null = sv_.get_null_bvector();
BM_ASSERT(bv_null);
// sync the max-id
bool found = bv_null->find_reverse(max_id_);
if (!found)
max_id_ = size_ = 0;
else
size_ = max_id_ + 1;
sync(false);
}
//---------------------------------------------------------------------
template<class Val, class SV>
bool rsc_sparse_vector<Val, SV>::resolve(size_type idx,
size_type* idx_to) const BMNOEXCEPT
{
BM_ASSERT(idx_to);
const bvector_type* bv_null = sv_.get_null_bvector();
if (idx >= size_)
{
BM_ASSERT(bv_null->get_bit(idx) == false);
return false;
}
if (in_sync_)
return resolve_sync(idx, idx_to);
// not in-sync: slow access
bool found = bv_null->test(idx);
if (!found)
return found;
*idx_to = bv_null->count_range_no_check(0, idx);
return found;
}
//---------------------------------------------------------------------
template<class Val, class SV>
bool rsc_sparse_vector<Val, SV>::resolve_sync(
size_type idx,
size_type* idx_to) const BMNOEXCEPT
{
BM_ASSERT(idx_to);
BM_ASSERT(in_sync_);
const bvector_type* bv_null = sv_.get_null_bvector();
if (is_dense_)
{
*idx_to = idx+1;
if (idx <= size_)
return true;
*idx_to = bm::id_max;
BM_ASSERT(bv_null->get_bit(idx) == false);
return false;
}
*idx_to = bv_null->count_to_test(idx, *rs_idx_);
return bool(*idx_to);
}
//---------------------------------------------------------------------
template<class Val, class SV>
bool rsc_sparse_vector<Val, SV>::resolve_range(
size_type from, size_type to,
size_type* idx_from, size_type* idx_to) const BMNOEXCEPT
{
BM_ASSERT(idx_to && idx_from);
const bvector_type* bv_null = sv_.get_null_bvector();
size_type copy_sz, sv_left;
if (in_sync_)
copy_sz = bv_null->count_range(from, to, *rs_idx_);
else // slow access
copy_sz = bv_null->count_range(from, to);
if (!copy_sz)
return false;
if (in_sync_)
sv_left = bv_null->rank_corrected(from, *rs_idx_);
else
{
sv_left = bv_null->count_range(0, from);
bool tl = bv_null->test(from); // TODO: add count and test
sv_left -= tl; // rank correction
}
*idx_from = sv_left; *idx_to = sv_left + copy_sz - 1;
return true;
}
//---------------------------------------------------------------------
template<class Val, class SV>
typename rsc_sparse_vector<Val, SV>::value_type
rsc_sparse_vector<Val, SV>::at(size_type idx) const
{
size_type sv_idx;
if (idx >= size())
sv_.throw_range_error("compressed collection access error");
bool found = resolve(idx, &sv_idx);
if (!found)
{
sv_.throw_range_error("compressed collection item not found");
}
return sv_.at(--sv_idx);
}
//---------------------------------------------------------------------
template<class Val, class SV>
typename rsc_sparse_vector<Val, SV>::value_type
rsc_sparse_vector<Val, SV>::get(size_type idx) const BMNOEXCEPT
{
size_type sv_idx;
bool found = resolve(idx, &sv_idx);
if (!found)
return value_type(0);
BM_ASSERT(!is_null(idx));
return sv_.get(--sv_idx);
}
//---------------------------------------------------------------------
template<class Val, class SV>
typename rsc_sparse_vector<Val, SV>::unsigned_value_type
rsc_sparse_vector<Val, SV>::get_unsigned_bits(size_type idx,
size_type N_bits) const BMNOEXCEPT
{
size_type sv_idx;
bool found = resolve(idx, &sv_idx);
if (!found)
return unsigned_value_type(0);
BM_ASSERT(!is_null(idx));
return sv_.get_unsigned_bits(--sv_idx, N_bits);
}
//---------------------------------------------------------------------
template<class Val, class SV>
bool rsc_sparse_vector<Val, SV>::try_get(
size_type idx, value_type& v) const BMNOEXCEPT
{
size_type sv_idx;
if (!resolve(idx, &sv_idx))
return false;
v = sv_.get(--sv_idx);
return true;
}
//---------------------------------------------------------------------
template<class Val, class SV>
bool rsc_sparse_vector<Val, SV>::try_get_sync(
size_type idx, value_type& v) const BMNOEXCEPT
{
size_type sv_idx;
bool found = resolve_sync(idx, &sv_idx);
if (!found)
return found;
v = sv_.get(--sv_idx);
return true;
}
//---------------------------------------------------------------------
template<class Val, class SV>
bool rsc_sparse_vector<Val, SV>::is_null(size_type idx) const BMNOEXCEPT
{
const bvector_type* bv_null = sv_.get_null_bvector();
BM_ASSERT(bv_null);
return !(bv_null->test(idx));
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::optimize(bm::word_t* temp_block,
typename bvector_type::optmode opt_mode,
statistics* st)
{
sv_.optimize(temp_block, opt_mode, (typename sparse_vector_type::statistics*)st);
if (st)
{
st->memory_used += sizeof(rs_index_type);
st->memory_used += rs_idx_->get_total() *
(sizeof(typename rs_index_type::size_type)
+ sizeof(typename rs_index_type::sb_pair_type));
}
if (is_sync()) // must rebuild the sync index after optimization
this->sync(true);
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::clear_all(bool free_mem, unsigned) BMNOEXCEPT
{
sv_.clear_all(free_mem, 0);
in_sync_ = false; max_id_ = size_ = 0;
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::calc_stat(
struct rsc_sparse_vector<Val, SV>::statistics* st) const BMNOEXCEPT
{
BM_ASSERT(st);
sv_.calc_stat((typename sparse_vector_type::statistics*)st);
if (st)
{
st->memory_used += sizeof(rs_index_type);
st->memory_used += rs_idx_->get_total() *
(sizeof(typename rs_index_type::size_type)
+ sizeof(typename rs_index_type::sb_pair_type));
}
}
//---------------------------------------------------------------------
template<class Val, class SV>
const typename rsc_sparse_vector<Val, SV>::bvector_type*
rsc_sparse_vector<Val, SV>::get_null_bvector() const BMNOEXCEPT
{
return sv_.get_null_bvector();
}
//---------------------------------------------------------------------
template<class Val, class SV>
bool
rsc_sparse_vector<Val, SV>::find_rank(size_type rank,
size_type& idx) const BMNOEXCEPT
{
BM_ASSERT(rank);
bool b;
const bvector_type* bv_null = get_null_bvector();
if (in_sync())
b = bv_null->select(rank, idx, *rs_idx_);
else
b = bv_null->find_rank(rank, 0, idx);
return b;
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::throw_no_rsc_index()
{
#ifndef BM_NO_STL
throw std::domain_error("Rank-Select index not constructed, call sync() first");
#else
BM_ASSERT_THROW(false, BM_ERR_RANGE);
#endif
}
//---------------------------------------------------------------------
template<class Val, class SV>
typename rsc_sparse_vector<Val, SV>::size_type
rsc_sparse_vector<Val, SV>::decode(value_type* arr,
size_type idx_from,
size_type size,
bool zero_mem) const
{
if (size == 0)
return 0;
if (!in_sync_)
throw_no_rsc_index(); // call sync() to build RSC fast access index
BM_ASSERT(arr);
BM_ASSERT(rs_idx_);
if (idx_from >= this->size())
return 0;
if ((bm::id_max - size) <= idx_from)
size = bm::id_max - idx_from;
if ((idx_from + size) > this->size())
size = this->size() - idx_from;
const bvector_type* bv_null = sv_.get_null_bvector();
size_type rank = bv_null->rank_corrected(idx_from, *rs_idx_);
BM_ASSERT(rank == bv_null->count_range(0, idx_from) - bv_null->test(idx_from));
size_type i = 0;
bvector_enumerator_type en_i = bv_null->get_enumerator(idx_from);
if (!en_i.valid())
return i;
if (zero_mem)
::memset(arr, 0, sizeof(value_type)*size);
sparse_vector_const_iterator it = sv_.get_const_iterator(rank);
if (it.valid())
{
do
{
size_type en_idx = *en_i;
size_type delta = en_idx - idx_from;
idx_from += delta;
i += delta;
if (i >= size)
return size;
arr[i++] = it.value();
if (!en_i.advance())
break;
if (!it.advance())
break;
++idx_from;
} while (i < size);
}
return i;
}
template<class Val, class SV>
typename rsc_sparse_vector<Val, SV>::size_type
rsc_sparse_vector<Val, SV>::decode_buf(value_type* arr,
value_type* arr_buf_tmp,
size_type idx_from,
size_type size,
bool zero_mem) const BMNOEXCEPT
{
if (!size || (idx_from >= this->size()))
return 0;
BM_ASSERT(arr && arr_buf_tmp);
BM_ASSERT(arr != arr_buf_tmp);
BM_ASSERT(in_sync_); // call sync() to build RSC fast access index
BM_ASSERT(rs_idx_);
if ((bm::id_max - size) <= idx_from)
size = bm::id_max - idx_from;
if ((idx_from + size) > this->size())
size = this->size() - idx_from;
if (zero_mem)
::memset(arr, 0, sizeof(value_type)*size);
const bvector_type* bv_null = sv_.get_null_bvector();
size_type rank = bv_null->rank_corrected(idx_from, *rs_idx_);
BM_ASSERT(rank == bv_null->count_range(0, idx_from) - bv_null->test(idx_from));
bvector_enumerator_type en_i = bv_null->get_enumerator(idx_from);
if (!en_i.valid())
return size;
size_type i = en_i.value();
if (idx_from + size <= i) // empty space (all zeros)
return size;
size_type extract_cnt =
bv_null->count_range_no_check(idx_from, idx_from + size - 1, *rs_idx_);
BM_ASSERT(extract_cnt <= this->size());
auto ex_sz = sv_.decode(arr_buf_tmp, rank, extract_cnt, true);
BM_ASSERT(ex_sz == extract_cnt); (void) ex_sz;
for (i = 0; i < extract_cnt; ++i)
{
BM_ASSERT(en_i.valid());
size_type en_idx = *en_i;
arr[en_idx-idx_from] = arr_buf_tmp[i];
en_i.advance();
} // for i
return size;
}
//---------------------------------------------------------------------
template<class Val, class SV>
typename rsc_sparse_vector<Val, SV>::size_type
rsc_sparse_vector<Val, SV>::gather(value_type* arr,
const size_type* idx,
size_type* idx_tmp_buf,
size_type size,
bm::sort_order sorted_idx) const
{
BM_ASSERT(arr);
BM_ASSERT(idx);
BM_ASSERT(idx_tmp_buf);
BM_ASSERT(size);
if (size == 1) // corner case: get 1 value
{
arr[0] = this->get(idx[0]);
return size;
}
if (is_dense_) // rank-select idx recalc is not needed (with bounds check)
{
BM_ASSERT(in_sync_);
for (size_type i = 0; i < size; ++i)
{
if (idx[i] < size_)
idx_tmp_buf[i] = idx[i];
else
{
idx_tmp_buf[i] = bm::id_max;
if (sorted_idx == bm::BM_SORTED)
sorted_idx = bm::BM_UNKNOWN; // UNK will evaluate the sort-order
}
} // for i
}
else
{
// validate index, resolve rank addresses
//
for (size_type i = 0; i < size; ++i)
{
size_type sv_idx;
if (resolve(idx[i], &sv_idx))
{
idx_tmp_buf[i] = sv_idx-1;
}
else
{
if (sorted_idx == bm::BM_SORTED)
sorted_idx = bm::BM_UNKNOWN; // UNK will evaluate the sort-order
idx_tmp_buf[i] = bm::id_max;
}
} // for i
}
// gather the data using resolved indexes
//
size = sv_.gather(arr, idx_tmp_buf, size, sorted_idx);
return size;
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::construct_rs_index()
{
if (rs_idx_)
return;
rs_idx_ = (rs_index_type*) bm::aligned_new_malloc(sizeof(rs_index_type));
rs_idx_ = new(rs_idx_) rs_index_type(); // placement new
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::free_rs_index()
{
if (rs_idx_)
{
rs_idx_->~rs_index_type();
bm::aligned_free(rs_idx_);
}
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::copy_range(
const rsc_sparse_vector<Val, SV>& csv,
size_type left, size_type right)
{
if (left > right)
bm::xor_swap(left, right);
if (left >= csv.size())
return;
size_ = csv.size_; max_id_ = csv.max_id_;
in_sync_ = false;
const bvector_type* arg_bv_null = csv.sv_.get_null_bvector();
size_type sv_left, sv_right;
bool range_valid = csv.resolve_range(left, right, &sv_left, &sv_right);
if (!range_valid)
{
sv_.clear_all(true, 0); sv_.resize(size_);
bvector_type* bv_null = sv_.get_null_bvect();
bv_null->copy_range(*arg_bv_null, 0, right);
return;
}
bvector_type* bv_null = sv_.get_null_bvect();
bv_null->copy_range(*arg_bv_null, 0, right); // not NULL vector gets a full copy
sv_.copy_range(csv.sv_, sv_left, sv_right, bm::no_null); // don't copy NULL
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::merge_not_null(rsc_sparse_vector<Val, SV>& csv)
{
// MUST have the same NULL to work
BM_ASSERT(sv_.get_null_bvector()->equal(*csv.sv_.get_null_bvector()));
sv_.merge(csv.sv_);
}
//---------------------------------------------------------------------
template<class Val, class SV>
typename rsc_sparse_vector<Val, SV>::size_type
rsc_sparse_vector<Val, SV>::count_range_notnull(
size_type left,
size_type right) const BMNOEXCEPT
{
if (left > right)
bm::xor_swap(left, right);
const bvector_type* bv_null = sv_.get_null_bvector();
size_type range = right - left;
if ((range < rs3_border0) || !in_sync_)
{
return bv_null->count_range_no_check(left, right);
}
return bv_null->count_range_no_check(left, right, *rs_idx_);
}
//---------------------------------------------------------------------
//
//---------------------------------------------------------------------
template<class Val, class SV>
rsc_sparse_vector<Val, SV>::back_insert_iterator::back_insert_iterator() BMNOEXCEPT
: csv_(0)
{}
//---------------------------------------------------------------------
template<class Val, class SV>
rsc_sparse_vector<Val, SV>::back_insert_iterator::back_insert_iterator
(rsc_sparse_vector_type* csv)
: csv_(csv),
sv_bi_(csv->sv_.get_back_inserter())
{
sv_bi_.disable_set_null(); // NULL will be handled outside
}
//---------------------------------------------------------------------
template<class Val, class SV>
rsc_sparse_vector<Val, SV>::back_insert_iterator::back_insert_iterator(
const back_insert_iterator& bi)
: csv_(bi.csv_),
sv_bi_(bi.sv_bi_)
{
}
//---------------------------------------------------------------------
template<class Val, class SV>
rsc_sparse_vector<Val, SV>::back_insert_iterator::~back_insert_iterator()
{
this->flush();
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::back_insert_iterator::add(
typename rsc_sparse_vector<Val, SV>::back_insert_iterator::value_type v)
{
BM_ASSERT(csv_);
BM_ASSERT(bm::id64_t(csv_->size_) + 1 < bm::id64_t(bm::id_max));
sv_bi_.add_value_no_null(v);
bvector_type* bv_null = sv_bi_.get_null_bvect();
BM_ASSERT(bv_null);
bv_null->set_bit_no_check(csv_->size_);
csv_->max_id_++;
csv_->size_++;
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::back_insert_iterator::add_null() BMNOEXCEPT
{
BM_ASSERT(csv_);
BM_ASSERT(bm::id64_t(csv_->size_) + 1 < bm::id64_t(bm::id_max));
csv_->max_id_++; csv_->size_++;
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::back_insert_iterator::add_null(
rsc_sparse_vector<Val, SV>::back_insert_iterator::size_type count) BMNOEXCEPT
{
BM_ASSERT(csv_);
BM_ASSERT(bm::id64_t(csv_->size_) + count < bm::id64_t(bm::id_max));
csv_->max_id_+=count;
csv_->size_+=count;
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::back_insert_iterator::flush()
{
if (sv_bi_.flush())
csv_->in_sync_ = false;
}
//---------------------------------------------------------------------
//
//---------------------------------------------------------------------
template<class Val, class BV>
rsc_sparse_vector<Val, BV>::const_iterator::const_iterator() BMNOEXCEPT
: csv_(0), pos_(bm::id_max), buf_ptr_(0)
{}
//---------------------------------------------------------------------
template<class Val, class SV>
rsc_sparse_vector<Val, SV>::const_iterator::const_iterator(
const typename rsc_sparse_vector<Val, SV>::const_iterator& it) BMNOEXCEPT
: csv_(it.csv_), pos_(it.pos_), buf_ptr_(0)
{}
//---------------------------------------------------------------------
template<class Val, class SV>
rsc_sparse_vector<Val, SV>::const_iterator::const_iterator(
const typename rsc_sparse_vector<Val, SV>::const_iterator::rsc_sparse_vector_type* csv
) BMNOEXCEPT
: csv_(csv), buf_ptr_(0)
{
BM_ASSERT(csv_);
pos_ = csv_->empty() ? bm::id_max : 0u;
}
//---------------------------------------------------------------------
template<class Val, class SV>
rsc_sparse_vector<Val, SV>::const_iterator::const_iterator(
const typename rsc_sparse_vector<Val, SV>::const_iterator::rsc_sparse_vector_type* csv,
typename rsc_sparse_vector<Val, SV>::size_type pos) BMNOEXCEPT
: csv_(csv), buf_ptr_(0)
{
BM_ASSERT(csv_);
this->go_to(pos);
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::const_iterator::go_to(size_type pos) BMNOEXCEPT
{
pos_ = (!csv_ || pos >= csv_->size()) ? bm::id_max : pos;
buf_ptr_ = 0;
}
//---------------------------------------------------------------------
template<class Val, class SV>
bool rsc_sparse_vector<Val, SV>::const_iterator::advance() BMNOEXCEPT
{
if (pos_ == bm::id_max) // nothing to do, we are at the end
return false;
++pos_;
if (pos_ >= csv_->size())
{
this->invalidate();
return false;
}
if (buf_ptr_)
{
++buf_ptr_;
if (buf_ptr_ - ((value_type*)vbuffer_.data()) >= n_buf_size)
buf_ptr_ = 0;
}
return true;
}
//---------------------------------------------------------------------
template<class Val, class SV>
typename rsc_sparse_vector<Val, SV>::const_iterator::value_type
rsc_sparse_vector<Val, SV>::const_iterator::value() const
{
BM_ASSERT(this->valid());
value_type v;
if (!buf_ptr_)
{
vbuffer_.reserve(n_buf_size * sizeof(value_type));
tbuffer_.reserve(n_buf_size * sizeof(value_type));
buf_ptr_ = (value_type*)(vbuffer_.data());
value_type* tmp_buf_ptr = (value_type*) (tbuffer_.data());
csv_->decode_buf(buf_ptr_, tmp_buf_ptr, pos_, n_buf_size, true);
}
v = *buf_ptr_;
return v;
}
//---------------------------------------------------------------------
template<class Val, class SV>
void rsc_sparse_vector<Val, SV>::const_iterator::skip_zero_values() BMNOEXCEPT
{
value_type v = value();
if (buf_ptr_)
{
v = *buf_ptr_;
value_type* buf_end = ((value_type*)vbuffer_.data()) + n_buf_size;
while(!v)
{
++pos_;
if (++buf_ptr_ < buf_end)
v = *buf_ptr_;
else
break;
}
if (pos_ >= csv_->size())
{
pos_ = bm::id_max;
return;
}
if (buf_ptr_ >= buf_end)
buf_ptr_ = 0;
}
}
//---------------------------------------------------------------------
template<class Val, class SV>
bool rsc_sparse_vector<Val, SV>::const_iterator::is_null() const BMNOEXCEPT
{
return csv_->is_null(pos_);
}
//---------------------------------------------------------------------
} // namespace bm
#endif
bmdef.h
Definitions(internal).
BMNOEXCEPT
#define BMNOEXCEPT
Definition bmdef.h:82
BM_ASSERT
#define BM_ASSERT
Definition bmdef.h:139
BM_ASSERT_THROW
#define BM_ASSERT_THROW(x, xerrcode)
Definition bmdef.h:338
bmsparsevec.h
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
bm::base_sparse_vector::slices
static unsigned slices() BMNOEXCEPT
get total number of bit-planes in the vector
Definition bmbmatrix.h:503
bm::base_sparse_vector::u2s
static value_type u2s(unsigned_value_type v) BMNOEXCEPT
Convert unsigned value type to signed representation.
Definition bmbmatrix.h:2108
bm::base_sparse_vector::s2u
static unsigned_value_type s2u(value_type v) BMNOEXCEPT
Convert signed value type to unsigned representation.
Definition bmbmatrix.h:2087
bm::base_sparse_vector::stored_slices
static unsigned stored_slices() BMNOEXCEPT
Number of stored bit-planes (value planes + extra.
Definition bmbmatrix.h:508
bm::bvector::enumerator
Constant iterator designed to enumerate "ON" bits.
Definition bm.h:603
bm::bvector::enumerator::value
size_type value() const BMNOEXCEPT
Get current position (value).
Definition bm.h:659
bm::bvector::enumerator::advance
bool advance() BMNOEXCEPT
Definition bm.h:680
bm::bvector::iterator_base::valid
bool valid() const BMNOEXCEPT
Checks if iterator is still valid.
Definition bm.h:283
bm::bvector::optmode
optmode
Optimization mode Every next level means additional checks (better compression vs time).
Definition bm.h:133
bm::bvector::opt_compress
@ opt_compress
compress blocks when possible (GAP/prefix sum)
Definition bm.h:137
bm::bvector::allocator_pool_type
allocator_type::allocator_pool_type allocator_pool_type
Definition bm.h:118
bm::bvector::rs_index_type
rs_index< allocator_type > rs_index_type
Definition bm.h:816
bm::bvector::allocator_type
Alloc allocator_type
Definition bm.h:117
bm::rank_compressor
Algorithms for rank compression of bit-vector.
Definition bmalgo.h:453
bm::rank_compressor::decompress
void decompress(BV &bv_target, const BV &bv_idx, const BV &bv_src)
Rank decompression.
Definition bmalgo.h:570
bm::rank_compressor::compress
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...
Definition bmalgo.h:497
bm::rsc_sparse_vector::back_insert_iterator::flush
void flush()
flush the accumulated buffer
Definition bmsparsevec_compr.h:2078
bm::rsc_sparse_vector::back_insert_iterator::rsc_sparse_vector_type_ptr
rsc_sparse_vector_type * rsc_sparse_vector_type_ptr
Definition bmsparsevec_compr.h:238
bm::rsc_sparse_vector::back_insert_iterator::sparse_vector_type
rsc_sparse_vector_type::sparse_vector_type sparse_vector_type
add value to the buffer without changing the NULL vector
Definition bmsparsevec_compr.h:295
bm::rsc_sparse_vector::back_insert_iterator::add
void add(value_type v)
add value to the container
Definition bmsparsevec_compr.h:2036
bm::rsc_sparse_vector::back_insert_iterator::iterator_category
std::output_iterator_tag iterator_category
Definition bmsparsevec_compr.h:235
bm::rsc_sparse_vector::back_insert_iterator::bvector_type
rsc_sparse_vector_type::bvector_type bvector_type
Definition bmsparsevec_compr.h:241
bm::rsc_sparse_vector::back_insert_iterator::pointer
void pointer
Definition bmsparsevec_compr.h:244
bm::rsc_sparse_vector::back_insert_iterator::operator=
back_insert_iterator & operator=(value_type v)
push value to the vector
Definition bmsparsevec_compr.h:266
bm::rsc_sparse_vector::back_insert_iterator::rsc_sparse_vector_type
rsc_sparse_vector< Val, SV > rsc_sparse_vector_type
Definition bmsparsevec_compr.h:237
bm::rsc_sparse_vector::back_insert_iterator::size_type
rsc_sparse_vector_type::size_type size_type
Definition bmsparsevec_compr.h:240
bm::rsc_sparse_vector::back_insert_iterator::reference
void reference
Definition bmsparsevec_compr.h:245
bm::rsc_sparse_vector::back_insert_iterator::value_type
rsc_sparse_vector_type::value_type value_type
Definition bmsparsevec_compr.h:239
bm::rsc_sparse_vector::back_insert_iterator::back_insert_iterator
back_insert_iterator() BMNOEXCEPT
Definition bmsparsevec_compr.h:1998
bm::rsc_sparse_vector::back_insert_iterator::operator*
back_insert_iterator & operator*()
noop
Definition bmsparsevec_compr.h:269
bm::rsc_sparse_vector::back_insert_iterator::difference_type
void difference_type
Definition bmsparsevec_compr.h:243
bm::rsc_sparse_vector::back_insert_iterator::operator++
back_insert_iterator & operator++(int)
noop
Definition bmsparsevec_compr.h:273
bm::rsc_sparse_vector::back_insert_iterator::add_null
void add_null() BMNOEXCEPT
add NULL (no-value) to the container
Definition bmsparsevec_compr.h:2054
bm::rsc_sparse_vector::back_insert_iterator::~back_insert_iterator
~back_insert_iterator()
Definition bmsparsevec_compr.h:2028
bm::rsc_sparse_vector::back_insert_iterator::operator++
back_insert_iterator & operator++()
noop
Definition bmsparsevec_compr.h:271
bm::rsc_sparse_vector::back_insert_iterator::sparse_vector_bi
sparse_vector_type::back_insert_iterator sparse_vector_bi
Definition bmsparsevec_compr.h:297
bm::rsc_sparse_vector::const_iterator
Const iterator to traverse the rsc sparse vector.
Definition bmsparsevec_compr.h:127
bm::rsc_sparse_vector::const_iterator::operator++
const_iterator & operator++() BMNOEXCEPT
Advance to the next available value.
Definition bmsparsevec_compr.h:172
bm::rsc_sparse_vector::const_iterator::advance
bool advance() BMNOEXCEPT
advance iterator forward by one
Definition bmsparsevec_compr.h:2137
bm::rsc_sparse_vector::const_iterator::rsc_sparse_vector_type
rsc_sparse_vector< Val, SV > rsc_sparse_vector_type
Definition bmsparsevec_compr.h:134
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::const_iterator::skip_zero_values
void skip_zero_values() BMNOEXCEPT
Definition bmsparsevec_compr.h:2181
bm::rsc_sparse_vector::const_iterator::pos
size_type pos() const BMNOEXCEPT
Current position (index) in the vector.
Definition bmsparsevec_compr.h:192
bm::rsc_sparse_vector::const_iterator::value_type
rsc_sparse_vector_type::value_type value_type
Definition bmsparsevec_compr.h:136
bm::rsc_sparse_vector::const_iterator::operator!=
bool operator!=(const const_iterator &it) const BMNOEXCEPT
Definition bmsparsevec_compr.h:156
bm::rsc_sparse_vector::const_iterator::operator<=
bool operator<=(const const_iterator &it) const BMNOEXCEPT
Definition bmsparsevec_compr.h:160
bm::rsc_sparse_vector::const_iterator::operator>
bool operator>(const const_iterator &it) const BMNOEXCEPT
Definition bmsparsevec_compr.h:162
bm::rsc_sparse_vector::const_iterator::buffer_type
bm::byte_buffer< allocator_type > buffer_type
Definition bmsparsevec_compr.h:142
bm::rsc_sparse_vector::const_iterator::go_to
void go_to(size_type pos) BMNOEXCEPT
re-position to a specified position
Definition bmsparsevec_compr.h:2128
bm::rsc_sparse_vector::const_iterator::operator<
bool operator<(const const_iterator &it) const BMNOEXCEPT
Definition bmsparsevec_compr.h:158
bm::rsc_sparse_vector::const_iterator::operator==
bool operator==(const const_iterator &it) const BMNOEXCEPT
Definition bmsparsevec_compr.h:154
bm::rsc_sparse_vector::const_iterator::is_null
bool is_null() const BMNOEXCEPT
Get NULL status.
Definition bmsparsevec_compr.h:2209
bm::rsc_sparse_vector::const_iterator::bvector_type
rsc_sparse_vector_type::bvector_type bvector_type
Definition bmsparsevec_compr.h:138
bm::rsc_sparse_vector::const_iterator::iterator_category
std::input_iterator_tag iterator_category
Definition bmsparsevec_compr.h:132
bm::rsc_sparse_vector::const_iterator::rsc_sparse_vector_type_ptr
rsc_sparse_vector_type * rsc_sparse_vector_type_ptr
Definition bmsparsevec_compr.h:135
bm::rsc_sparse_vector::const_iterator::operator++
const_iterator & operator++(int)
Advance to the next available value.
Definition bmsparsevec_compr.h:175
bm::rsc_sparse_vector::const_iterator::difference_type
unsigned difference_type
Definition bmsparsevec_compr.h:144
bm::rsc_sparse_vector::const_iterator::valid
bool valid() const BMNOEXCEPT
Returns true if iterator is at a valid position.
Definition bmsparsevec_compr.h:186
bm::rsc_sparse_vector::const_iterator::invalidate
void invalidate() BMNOEXCEPT
Invalidate current iterator.
Definition bmsparsevec_compr.h:189
bm::rsc_sparse_vector::const_iterator::operator>=
bool operator>=(const const_iterator &it) const BMNOEXCEPT
Definition bmsparsevec_compr.h:164
bm::rsc_sparse_vector::const_iterator::rsc_sparse_vector
friend class rsc_sparse_vector
Definition bmsparsevec_compr.h:129
bm::rsc_sparse_vector::const_iterator::size_type
rsc_sparse_vector_type::size_type size_type
Definition bmsparsevec_compr.h:137
bm::rsc_sparse_vector::const_iterator::const_iterator
const_iterator() BMNOEXCEPT
Definition bmsparsevec_compr.h:2089
bm::rsc_sparse_vector::const_iterator::reference
value_type & reference
Definition bmsparsevec_compr.h:146
bm::rsc_sparse_vector::const_iterator::allocator_pool_type
bvector_type::allocator_type::allocator_pool_type allocator_pool_type
Definition bmsparsevec_compr.h:141
bm::rsc_sparse_vector::const_iterator::operator*
value_type operator*() const
Get current position (value).
Definition bmsparsevec_compr.h:168
bm::rsc_sparse_vector::const_iterator::pointer
unsigned * pointer
Definition bmsparsevec_compr.h:145
bm::rsc_sparse_vector::const_iterator::value
value_type value() const
Get current position (value).
Definition bmsparsevec_compr.h:2160
bm::rsc_sparse_vector::const_iterator::allocator_type
bvector_type::allocator_type allocator_type
Definition bmsparsevec_compr.h:139
bm::rsc_sparse_vector::reference::operator==
bool operator==(const reference &ref) const BMNOEXCEPT
Definition bmsparsevec_compr.h:107
bm::rsc_sparse_vector::reference::is_null
bool is_null() const BMNOEXCEPT
Definition bmsparsevec_compr.h:109
bm::rsc_sparse_vector::reference::reference
reference(rsc_sparse_vector< Val, SV > &csv, size_type idx) BMNOEXCEPT
Definition bmsparsevec_compr.h:103
bm::rsc_sparse_vector::is_str
static constexpr bool is_str() BMNOEXCEPT
Definition bmsparsevec_compr.h:658
bm::rsc_sparse_vector::is_compressed
static constexpr bool is_compressed() BMNOEXCEPT
various type traits
Definition bmsparsevec_compr.h:655
bm::rsc_sparse_vector::stored_slices
static unsigned stored_slices()
Number of stored bit-slices (value slices + extra.
Definition bmsparsevec_compr.h:857
bm::rsc_sparse_vector::octet_slices
octet_slices
Definition bmsparsevec_compr.h:913
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::sv_octet_slices
@ sv_octet_slices
Definition bmsparsevec_compr.h:914
bm::rsc_sparse_vector::bvector_type_ptr
bvector_type * bvector_type_ptr
Definition bmsparsevec_compr.h:73
bm::rsc_sparse_vector::try_get
bool try_get(size_type idx, value_type &v) const BMNOEXCEPT
get specified element with NOT NULL check
Definition bmsparsevec_compr.h:1607
bm::rsc_sparse_vector::clear_all
void clear_all(bool free_mem, unsigned) BMNOEXCEPT
resize to zero, free memory
Definition bmsparsevec_compr.h:1663
bm::rsc_sparse_vector::bit_slices
bit_slices
Definition bmsparsevec_compr.h:62
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::sv_value_slices
@ sv_value_slices
Definition bmsparsevec_compr.h:64
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::sv_slices
@ sv_slices
Definition bmsparsevec_compr.h:63
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::sparse_vector_scanner
friend class sparse_vector_scanner
Definition bmsparsevec_compr.h:971
bm::rsc_sparse_vector::resolve
bool resolve(size_type idx, size_type *idx_to) const BMNOEXCEPT
Resolve logical address to access via rank compressed address.
Definition bmsparsevec_compr.h:1481
bm::rsc_sparse_vector::load_from
void load_from(const sparse_vector_type &sv_src)
Load compressed vector from a sparse vector (with NULLs).
Definition bmsparsevec_compr.h:1369
bm::rsc_sparse_vector::operator=
rsc_sparse_vector< Val, SV > & operator=(rsc_sparse_vector< Val, SV > &&csv) BMNOEXCEPT
Definition bmsparsevec_compr.h:352
bm::rsc_sparse_vector::size_type
SV::size_type size_type
Definition bmsparsevec_compr.h:69
bm::rsc_sparse_vector::get_sv
const sparse_vector_type & get_sv() const BMNOEXCEPT
access dense vector
Definition bmsparsevec_compr.h:863
bm::rsc_sparse_vector::value_type
Val value_type
Definition bmsparsevec_compr.h:67
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::is_nullable
bool is_nullable() const
Definition bmsparsevec_compr.h:650
bm::rsc_sparse_vector::resolve_sync
bool resolve_sync(size_type idx, size_type *idx_to) const BMNOEXCEPT
Definition bmsparsevec_compr.h:1505
bm::rsc_sparse_vector::get_bmatrix
const bmatrix_type & get_bmatrix() const BMNOEXCEPT
Definition bmsparsevec_compr.h:878
bm::rsc_sparse_vector::~rsc_sparse_vector
~rsc_sparse_vector()
Definition bmsparsevec_compr.h:1031
bm::rsc_sparse_vector::merge_not_null
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...
Definition bmsparsevec_compr.h:1964
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::decode
size_type decode(value_type *arr, size_type idx_from, size_type size, bool zero_mem=true) const
bm::rsc_sparse_vector::freeze
void freeze()
Turn sparse vector into immutable mode Read-only (immutable) vector uses less memory and allows faste...
Definition bmsparsevec_compr.h:762
bm::rsc_sparse_vector::push_back
void push_back(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
Definition bmsparsevec_compr.h:1126
bm::rsc_sparse_vector::clear
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...
Definition bmsparsevec_compr.h:1223
bm::rsc_sparse_vector::get_back_inserter
back_insert_iterator get_back_inserter()
Definition bmsparsevec_compr.h:714
bm::rsc_sparse_vector::load_to
void load_to(sparse_vector_type &sv) const
Exort compressed vector to a sparse vector (with NULLs).
Definition bmsparsevec_compr.h:1410
bm::rsc_sparse_vector::bmatrix_type
SV::bmatrix_type bmatrix_type
Definition bmsparsevec_compr.h:79
bm::rsc_sparse_vector::set
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
Definition bmsparsevec_compr.h:1323
bm::rsc_sparse_vector::remap_matrix_type
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
Definition bmsparsevec_compr.h:938
bm::rsc_sparse_vector::end
const_iterator end() const BMNOEXCEPT
Provide const iterator access to the end.
Definition bmsparsevec_compr.h:705
bm::rsc_sparse_vector::at
value_type at(size_type idx) const
access specified element with bounds checking
Definition bmsparsevec_compr.h:1561
bm::rsc_sparse_vector::optimize
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
Definition bmsparsevec_compr.h:1644
bm::rsc_sparse_vector::sync
void sync(bool force)
Re-calculate rank-select index for faster access to vector.
Definition bmsparsevec_compr.h:1442
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::count_range_notnull
size_type count_range_notnull(size_type left, size_type right) const BMNOEXCEPT
bm::rsc_sparse_vector::effective_vector_max
size_type effective_vector_max() const BMNOEXCEPT
Always 1 (non-matrix type).
Definition bmsparsevec_compr.h:873
bm::rsc_sparse_vector::unsigned_value_type
SV::unsigned_value_type unsigned_value_type
Definition bmsparsevec_compr.h:80
bm::rsc_sparse_vector::slice
bvector_type_ptr slice(unsigned i)
Definition bmsparsevec_compr.h:841
bm::rsc_sparse_vector::rsc_sparse_vector
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())
Definition bmsparsevec_compr.h:990
bm::rsc_sparse_vector::push_back_null
void push_back_null()
push back NULL value
Definition bmsparsevec_compr.h:489
bm::rsc_sparse_vector::unsync
void unsync() BMNOEXCEPT
Unsync the prefix sum table.
Definition bmsparsevec_compr.h:824
bm::rsc_sparse_vector::resolve_range
bool resolve_range(size_type from, size_type to, size_type *idx_from, size_type *idx_to) const BMNOEXCEPT
Definition bmsparsevec_compr.h:1529
bm::rsc_sparse_vector::effective_size
size_type effective_size() const BMNOEXCEPT
size of internal dense vector
Definition bmsparsevec_compr.h:868
bm::rsc_sparse_vector::s2u
static unsigned_value_type s2u(value_type v) BMNOEXCEPT
Convert signed value type to unsigned representation.
Definition bmsparsevec_compr.h:949
bm::rsc_sparse_vector::set_remap
void set_remap() BMNOEXCEPT
Definition bmsparsevec_compr.h:933
bm::rsc_sparse_vector::set_null
void set_null(size_type idx)
set specified element to NULL RSC vector actually erases element when it is set to NULL (expensive).
Definition bmsparsevec_compr.h:1167
bm::rsc_sparse_vector::inc_not_null
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...
Definition bmsparsevec_compr.h:1304
bm::rsc_sparse_vector::vector_capacity
vector_capacity
Definition bmsparsevec_compr.h:83
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::max_vector_size
@ max_vector_size
Definition bmsparsevec_compr.h:84
bm::rsc_sparse_vector::get_remap_matrix
const remap_matrix_type * get_remap_matrix() const
Definition bmsparsevec_compr.h:940
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::sparse_vector_serializer
friend class sparse_vector_serializer
Definition bmsparsevec_compr.h:972
bm::rsc_sparse_vector::get_slice
bvector_type_const_ptr get_slice(unsigned i) const BMNOEXCEPT
get access to bit-plane, function checks and creates a plane
Definition bmsparsevec_compr.h:835
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::resize
void resize(size_type new_size)
bm::rsc_sparse_vector::resize_internal
void resize_internal(size_type sz)
Definition bmsparsevec_compr.h:923
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::decode_buf
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
bm::rsc_sparse_vector::size_internal
size_type size_internal() const BMNOEXCEPT
Definition bmsparsevec_compr.h:927
bm::rsc_sparse_vector::sparse_vector_const_iterator
SV::const_iterator sparse_vector_const_iterator
Definition bmsparsevec_compr.h:71
bm::rsc_sparse_vector::get_create_slice
bvector_type_ptr get_create_slice(unsigned i)
Definition bmsparsevec_compr.h:838
bm::rsc_sparse_vector::is_remap
constexpr bool is_remap() const BMNOEXCEPT
Definition bmsparsevec_compr.h:929
bm::rsc_sparse_vector::equal
bool equal(const rsc_sparse_vector< Val, SV > &csv) const BMNOEXCEPT
check if another vector has the same content
Definition bmsparsevec_compr.h:1355
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::sparse_vector_deserializer
friend class sparse_vector_deserializer
Definition bmsparsevec_compr.h:973
bm::rsc_sparse_vector::get
value_type get(size_type idx) const BMNOEXCEPT
get specified element without bounds checking
Definition bmsparsevec_compr.h:1579
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::empty
bool empty() const BMNOEXCEPT
Definition bmsparsevec_compr.h:379
bm::rsc_sparse_vector::const_reference
const value_type & const_reference
Definition bmsparsevec_compr.h:68
bm::rsc_sparse_vector::get_bmatrix
bmatrix_type & get_bmatrix() BMNOEXCEPT
Definition bmsparsevec_compr.h:884
bm::rsc_sparse_vector::get_const_iterator
const_iterator get_const_iterator(size_type idx) const BMNOEXCEPT
Get const_itertor re-positioned to specific element.
Definition bmsparsevec_compr.h:711
bm::rsc_sparse_vector::bvector_type_const_ptr
const bvector_type * bvector_type_const_ptr
Definition bmsparsevec_compr.h:74
bm::rsc_sparse_vector::remap_size
size_t remap_size() const BMNOEXCEPT
Definition bmsparsevec_compr.h:930
bm::rsc_sparse_vector::sync
void sync()
Re-calculate prefix sum table used for rank search (if necessary).
Definition bmsparsevec_compr.h:810
bm::rsc_sparse_vector::get_remap_buffer
const unsigned char * get_remap_buffer() const BMNOEXCEPT
Definition bmsparsevec_compr.h:931
bm::rsc_sparse_vector::init_remap_buffer
unsigned char * init_remap_buffer() BMNOEXCEPT
Definition bmsparsevec_compr.h:932
bm::rsc_sparse_vector::set_null
void set_null(const bvector_type &bv_idx)
Set NULL all elements set as 1 in the argument vector.
Definition bmsparsevec_compr.h:1194
bm::rsc_sparse_vector::is_null
bool is_null(size_type idx) const BMNOEXCEPT
test if specified element is NULL
Definition bmsparsevec_compr.h:1634
bm::rsc_sparse_vector::u2s
static value_type u2s(unsigned_value_type v) BMNOEXCEPT
Definition bmsparsevec_compr.h:952
bm::rsc_sparse_vector::mark_null_idx
void mark_null_idx(unsigned null_idx) BMNOEXCEPT
Definition bmsparsevec_compr.h:895
bm::rsc_sparse_vector::calc_stat
void calc_stat(struct rsc_sparse_vector< Val, SV >::statistics *st) const BMNOEXCEPT
Calculates memory statistics.
Definition bmsparsevec_compr.h:1672
bm::rsc_sparse_vector::allocator_type
bvector_type::allocator_type allocator_type
Definition bmsparsevec_compr.h:75
bm::rsc_sparse_vector::rsc_sparse_vector
rsc_sparse_vector(rsc_sparse_vector< Val, SV > &&csv) BMNOEXCEPT
Definition bmsparsevec_compr.h:1053
bm::rsc_sparse_vector::sparse_vector_type
SV sparse_vector_type
Definition bmsparsevec_compr.h:70
bm::rsc_sparse_vector::get_null_bvector
const bvector_type * get_null_bvector() const BMNOEXCEPT
Get bit-vector of assigned values (or NULL).
Definition bmsparsevec_compr.h:1690
bm::rsc_sparse_vector::clear
void clear() BMNOEXCEPT
resize to zero, free memory
Definition bmsparsevec_compr.h:740
bm::rsc_sparse_vector::push_back
void push_back(value_type v)
add element with automatic resize
Definition bmsparsevec_compr.h:477
bm::rsc_sparse_vector::effective_slices
unsigned effective_slices() const BMNOEXCEPT
Definition bmsparsevec_compr.h:847
bm::rsc_sparse_vector::try_get_sync
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...
Definition bmsparsevec_compr.h:1620
bm::rsc_sparse_vector::rs_index_type
bvector_type::rs_index_type rs_index_type
Definition bmsparsevec_compr.h:77
bm::rsc_sparse_vector::is_sync
bool is_sync() const BMNOEXCEPT
returns true if prefix sum table is in sync with the vector
Definition bmsparsevec_compr.h:819
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::find_rank
bool find_rank(size_type rank, size_type &idx) const BMNOEXCEPT
bm::rsc_sparse_vector::get_remap_matrix
remap_matrix_type * get_remap_matrix()
Definition bmsparsevec_compr.h:941
bm::rsc_sparse_vector::size
size_type size() const BMNOEXCEPT
return size of the vector
Definition bmsparsevec_compr.h:1071
bm::rsc_sparse_vector::bvector_enumerator_type
bvector_type::enumerator bvector_enumerator_type
Definition bmsparsevec_compr.h:78
bm::rsc_sparse_vector::get_RS
const rs_index_type * get_RS() const BMNOEXCEPT
Definition bmsparsevec_compr.h:892
bm::rsc_sparse_vector::slices
static unsigned slices() BMNOEXCEPT
get total number of bit-slices in the vector
Definition bmsparsevec_compr.h:853
bm::rsc_sparse_vector::get_unsigned_bits
unsigned_value_type get_unsigned_bits(size_type idx, size_type N_bits) const BMNOEXCEPT
Get raw unsigned value first N bits.
Definition bmsparsevec_compr.h:1593
bm::rsc_sparse_vector::push_back_null
void push_back_null(size_type count)
push back specified amount of NULL values
Definition bmsparsevec_compr.h:1141
bm::rsc_sparse_vector::in_sync
bool in_sync() const BMNOEXCEPT
returns true if prefix sum table is in sync with the vector
Definition bmsparsevec_compr.h:815
bm::rsc_sparse_vector::copy_range
void copy_range(const rsc_sparse_vector< Val, SV > &csv, size_type left, size_type right)
copy range of values from another sparse vector
Definition bmsparsevec_compr.h:1932
bm::rsc_sparse_vector::inc
void inc(size_type idx)
increment specified element by one
Definition bmsparsevec_compr.h:1240
bm::rsc_sparse_vector< unsigned, sparse_vector_u32 >::gather
size_type gather(value_type *arr, const size_type *idx, size_type *idx_tmp_buf, size_type size, bm::sort_order sorted_idx) const
bm::rsc_sparse_vector::push_back_no_check
void push_back_no_check(size_type idx, value_type v)
Definition bmsparsevec_compr.h:1151
bm::rsc_sparse_vector::is_ro
bool is_ro() const BMNOEXCEPT
Returns true if vector is read-only.
Definition bmsparsevec_compr.h:765
bm::rsc_sparse_vector::allocation_policy_type
bvector_type::allocation_policy allocation_policy_type
Definition bmsparsevec_compr.h:76
bm::rsc_sparse_vector::bvector_type
SV::bvector_type bvector_type
Definition bmsparsevec_compr.h:72
bm::rsc_sparse_vector::inc
void inc(size_type idx, value_type v)
increment specified element by one
Definition bmsparsevec_compr.h:1272
bm::rsc_sparse_vector::sync_size
void sync_size() BMNOEXCEPT
recalculate size to exclude tail NULL elements After this call size() will return the true size of th...
Definition bmsparsevec_compr.h:1465
bm::rsc_sparse_vector::begin
const_iterator begin() const
Provide const iterator access to container content.
Definition bmsparsevec_compr.h:697
bm::sort_order
sort_order
Sort order declaration.
Definition bmconst.h:204
bm::null_support
null_support
NULL-able value support.
Definition bmconst.h:229
bm::BM_SORTED
@ BM_SORTED
input set is sorted (ascending order)
Definition bmconst.h:206
bm::BM_UNKNOWN
@ BM_UNKNOWN
sort order unknown
Definition bmconst.h:208
bm::use_null
@ use_null
support "non-assigned" or "NULL" logic
Definition bmconst.h:230
bm::no_null
@ no_null
do not support NULL values
Definition bmconst.h:231
bm
Definition bm.h:78
bm::id_max
const unsigned id_max
Definition bmconst.h:109
bm::word_t
unsigned int word_t
Definition bmconst.h:39
bm::aligned_free
void aligned_free(void *ptr) BMNOEXCEPT
Aligned free.
Definition bmalloc.h:464
bm::aligned_new_malloc
void * aligned_new_malloc(size_t size)
Aligned malloc (unlike classic malloc it throws bad_alloc exception).
Definition bmalloc.h:436
bm::xor_swap
BMFORCEINLINE void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two variables.
Definition bmutil.h:534
bm::id64_t
unsigned long long int id64_t
Definition bmconst.h:35
bm::rs3_border0
const unsigned rs3_border0
Definition bmconst.h:119
bm::bv_statistics::bv_statistics
bv_statistics() BMNOEXCEPT
Definition bmfunc.h:67
bm::bv_statistics::memory_used
size_t memory_used
memory usage for all blocks and service tables
Definition bmfunc.h:62
bm::bvector::allocation_policy
memory allocation policy
Definition bm.h:805
bm::rsc_sparse_vector::is_dynamic_splices
Definition bmsparsevec_compr.h:89
bm::rsc_sparse_vector::is_dynamic_splices::trait
trait
Definition bmsparsevec_compr.h:89
bm::rsc_sparse_vector::is_dynamic_splices::value
@ value
Definition bmsparsevec_compr.h:89
bm::rsc_sparse_vector::is_remap_support
Definition bmsparsevec_compr.h:87
bm::rsc_sparse_vector::is_remap_support::trait
trait
Definition bmsparsevec_compr.h:87
bm::rsc_sparse_vector::is_remap_support::value
@ value
Definition bmsparsevec_compr.h:87
bm::rsc_sparse_vector::is_rsc_support
Definition bmsparsevec_compr.h:88
bm::rsc_sparse_vector::is_rsc_support::trait
trait
Definition bmsparsevec_compr.h:88
bm::rsc_sparse_vector::is_rsc_support::value
@ value
Definition bmsparsevec_compr.h:88
bm::rsc_sparse_vector::statistics
Definition bmsparsevec_compr.h:94