BitMagic-C++
bmsparsevec_compr.h
Go to the documentation of this file.
1 #ifndef BMSPARSEVEC_COMPR_H__INCLUDED__
2 #define BMSPARSEVEC_COMPR_H__INCLUDED__
3 /*
4 Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5 
6 Licensed under the Apache License, Version 2.0 (the "License");
7 you may not use this file except in compliance with the License.
8 You may obtain a copy of the License at
9 
10  http://www.apache.org/licenses/LICENSE-2.0
11 
12 Unless required by applicable law or agreed to in writing, software
13 distributed under the License is distributed on an "AS IS" BASIS,
14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 See the License for the specific language governing permissions and
16 limitations under the License.
17 
18 For more information please visit: http://bitmagic.io
19 */
20 
21 /*! \file bmsparsevec_compr.h
22  \brief Compressed sparse container rsc_sparse_vector<> for integer types
23 */
24 
25 #include <memory.h>
26 
27 #ifndef BM_NO_STL
28 #include <stdexcept>
29 #endif
30 
31 #include "bmsparsevec.h"
32 #include "bmdef.h"
33 
34 namespace bm
35 {
36 
37 
38 /*!
39  \brief Rank-Select compressed sparse vector
40 
41  Container uses Rank-Select method of compression, where
42  all NULL columns gets dropped, effective address of columns is computed
43  using address bit-vector.
44 
45  Use for cases, where memory efficiency is preferable over
46  single element access latency.
47 
48  \ingroup sv
49 */
50 template<class Val, class SV>
52 {
53 public:
54 
56  {
57  sv_plains = (sizeof(Val) * 8 + 1),
58  sv_value_plains = (sizeof(Val) * 8)
59  };
60 
61  typedef Val value_type;
62  typedef const value_type& const_reference;
64  typedef SV sparse_vector_type;
65  typedef typename SV::const_iterator sparse_vector_const_iterator;
66  typedef typename SV::bvector_type bvector_type;
67  typedef bvector_type* bvector_type_ptr;
68  typedef const bvector_type* bvector_type_const_ptr;
69  typedef typename bvector_type::allocator_type allocator_type;
70  typedef typename bvector_type::allocation_policy allocation_policy_type;
71  typedef typename bvector_type::rs_index_type rs_index_type;
72  typedef typename bvector_type::enumerator bvector_enumerator_type;
73 
74 public:
75  /*! Statistical information about memory allocation details. */
76  struct statistics : public bv_statistics
77  {};
78 
79 public:
80  /**
81  Reference class to access elements via common [] operator
82  */
83  class reference
84  {
85  public:
87  : csv_(csv), idx_(idx)
88  {}
89  operator value_type() const { return csv_.get(idx_); }
90  bool operator==(const reference& ref) const
91  { return bool(*this) == bool(ref); }
92  bool is_null() const { return csv_.is_null(idx_); }
93  private:
95  size_type idx_;
96  };
97 
98 public:
99  // ------------------------------------------------------------
100  /*! @name Construction and assignment */
101  //@{
102 
104  allocation_policy_type ap = allocation_policy_type(),
105  size_type bv_max_size = bm::id_max,
106  const allocator_type& alloc = allocator_type());
108 
109  /*! copy-ctor */
111 
112 
113  /*! copy assignmment operator */
115  {
116  if (this != &csv)
117  {
118  sv_ = csv.sv_;
119  max_id_ = csv.max_id_;
120  in_sync_ = csv.in_sync_;
121  if (in_sync_)
122  {
123  bv_blocks_ptr_->copy_from(*(csv.bv_blocks_ptr_));
124  }
125  }
126  return *this;
127  }
128 
129 #ifndef BM_NO_CXX11
130  /*! move-ctor */
132 
133  /*! move assignmment operator */
135  {
136  if (this != &csv)
137  {
138  clear();
139  sv_.swap(csv.sv_);
140  max_id_ = csv.max_id_; in_sync_ = csv.in_sync_;
141  if (in_sync_)
142  {
143  bv_blocks_ptr_->copy_from(*(csv.bv_blocks_ptr_));
144  }
145  }
146  return *this;
147  }
148 #endif
149 
150  //@}
151  // ------------------------------------------------------------
152  /*! @name Size, etc */
153  ///@{
154 
155  /*! \brief return size of the vector
156  \return size of sparse vector
157  */
158  size_type size() const;
159 
160  /*! \brief return true if vector is empty
161  \return true if empty
162  */
163  bool empty() const { return sv_.empty(); }
164 
165  ///@}
166 
167  // ------------------------------------------------------------
168  /*! @name Element access */
169  //@{
170 
171  /*!
172  \brief get specified element without bounds checking
173  \param idx - element index
174  \return value of the element
175  */
176  value_type operator[](size_type idx) const { return this->get(idx); }
177 
178  /*!
179  \brief access specified element with bounds checking
180  \param idx - element index
181  \return value of the element
182  */
183  value_type at(bm::id_t idx) const;
184 
185  /*!
186  \brief get specified element without bounds checking
187  \param idx - element index
188  \return value of the element
189  */
190  value_type get(bm::id_t idx) const;
191 
192 
193  /** \brief test if specified element is NULL
194  \param idx - element index
195  \return true if it is NULL false if it was assigned or container
196  is not configured to support assignment flags
197  */
198  bool is_null(size_type idx) const;
199 
200  /**
201  \brief Get bit-vector of assigned values (or NULL)
202  */
203  const bvector_type* get_null_bvector() const;
204 
205  /**
206  \brief find position of compressed element by its rank
207  \param rank - rank (virtual index in sparse vector)
208  \param idx - index (true position)
209  */
210  bool find_rank(bm::id_t rank, bm::id_t& idx) const;
211 
212  //@}
213 
214  // ------------------------------------------------------------
215  /*! @name Export content to C-stype array */
216  ///@{
217 
218  size_type decode(value_type* arr,
219  size_type idx_from,
220  size_type size,
221  bool zero_mem = true) const;
222 
223  ///@}
224 
225 
226  // ------------------------------------------------------------
227  /*! @name Various traits */
228  //@{
229  /**
230  \brief if container supports NULL(unassigned) values (true)
231  */
232  bool is_nullable() const { return true; }
233 
234  /** \brief trait if sparse vector is "compressed" (true)
235  */
236  static
237  bool is_compressed() { return true; }
238 
239  ///@}
240 
241 
242  // ------------------------------------------------------------
243  /*! @name Comparison */
244  //@{
245 
246  /*!
247  \brief check if another vector has the same content
248  \return true, if it is the same
249  */
250  bool equal(const rsc_sparse_vector<Val, SV>& csv) const;
251  //@}
252 
253  // ------------------------------------------------------------
254  /*! @name Load-Export compressed vector with data */
255 
256  //@{
257 
258  /*!
259  \brief set specified element with bounds checking and automatic resize
260 
261  Method cannot insert elements, so every new idx has to be greater or equal
262  than what it used before. Elements must be loaded in a sorted order.
263 
264  \param idx - element index
265  \param v - element value
266  */
267  void push_back(size_type idx, value_type v);
268 
269  /*!
270  \brief Load compressed vector from a sparse vector (with NULLs)
271  \param sv_src - source sparse vector
272  */
273  void load_from(const sparse_vector_type& sv_src);
274 
275  /*!
276  \brief Exort compressed vector to a sparse vector (with NULLs)
277  \param sv - target sparse vector
278  */
279  void load_to(sparse_vector_type& sv) const;
280 
281  //@}
282 
283  // ------------------------------------------------------------
284  /*! @name Memory optimization */
285  ///@{
286 
287  /*!
288  \brief run memory optimization for all vector plains
289  \param temp_block - pre-allocated memory block to avoid unnecessary re-allocs
290  \param opt_mode - requested compression depth
291  \param stat - memory allocation statistics after optimization
292  */
293  void optimize(bm::word_t* temp_block = 0,
294  typename bvector_type::optmode opt_mode = bvector_type::opt_compress,
295  statistics* stat = 0);
296 
297  /*! \brief resize to zero, free memory
298  */
299  void clear() BMNOEXEPT;
300 
301  /*!
302  @brief Calculates memory statistics.
303 
304  Function fills statistics structure containing information about how
305  this vector uses memory and estimation of max. amount of memory
306  bvector needs to serialize itself.
307 
308  @param st - pointer on statistics structure to be filled in.
309 
310  @sa statistics
311  */
312  void calc_stat(struct rsc_sparse_vector<Val, SV>::statistics* st) const;
313 
314  ///@}
315 
316 
317  // ------------------------------------------------------------
318  /*! @name Fast access structues sync */
319  //@{
320  /*!
321  \brief Re-calculate prefix sum table used for rank search
322  \param force - force recalculation even if it is already recalculated
323  */
324  void sync(bool force);
325 
326  /*!
327  \brief Re-calculate prefix sum table used for rank search (if necessary)
328  */
329  void sync() { sync(false); }
330 
331  /*!
332  \brief returns true if prefix sum table is in sync with the vector
333  */
334  bool in_sync() const { return in_sync_; }
335 
336  /*!
337  \brief Unsync the prefix sum table
338  */
339  void unsync() { in_sync_ = false; }
340  ///@}
341 
342  // ------------------------------------------------------------
343  /*! @name Access to internals */
344  ///@{
345 
346  /*!
347  \brief get access to bit-plain, function checks and creates a plain
348  \return bit-vector for the bit plain
349  */
350  bvector_type_const_ptr get_plain(unsigned i) const { return sv_.get_plain(i); }
351 
352  bvector_type_ptr get_plain(unsigned i) { return sv_.get_plain(i); }
353 
354  /*!
355  Number of effective bit-plains in the value type
356  */
357  unsigned effective_plains() const { return sv_.effective_plains(); }
358 
359  /*!
360  \brief get total number of bit-plains in the vector
361  */
362  static unsigned plains() { return sparse_vector_type::plains(); }
363 
364  /** Number of stored bit-plains (value plains + extra */
365  static unsigned stored_plains() { return sparse_vector_type::stored_plains(); }
366 
367  /*!
368  \brief access dense vector
369  */
370  const sparse_vector_type& get_sv() const { return sv_; }
371 
372  /*!
373  \brief size of internal dense vector
374  */
375  size_type effective_size() const { return sv_.size(); }
376 
377  ///@}
378 
379 protected:
380  /*!
381  \brief Resolve logical address to access via rank compressed address
382 
383  \param idx - input id to resolve
384  \param idx_to - output id
385 
386  \return true if id is known and resolved successfully
387  */
388  bool resolve(bm::id_t idx, bm::id_t* idx_to) const;
389 
390  void resize_internal(size_type sz) { sv_.resize_internal(sz); }
391  size_type size_internal() const { return sv_.size(); }
392 
393 private:
394  void construct_bv_blocks();
395  void free_bv_blocks();
396 
397 protected:
398  template<class SVect> friend class sparse_vector_scanner;
399  template<class SVect> friend class sparse_vector_serializer;
400  template<class SVect> friend class sparse_vector_deserializer;
401 
402 private:
403  sparse_vector_type sv_; ///< transpose-sparse vector for "dense" packing
404  bm::id_t max_id_; ///< control variable for sorted load
405  bool in_sync_; ///< flag if prefix sum is in-sync with vector
406  rs_index_type* bv_blocks_ptr_ = 0; ///< prefix sum for rank translation
407 };
408 
409 //---------------------------------------------------------------------
410 //---------------------------------------------------------------------
411 
412 template<class Val, class SV>
415  size_type bv_max_size,
416  const allocator_type& alloc)
417  : sv_(null_able, ap, bv_max_size, alloc),
418  max_id_(0), in_sync_(false)
419 {
420  BM_ASSERT(null_able == bm::use_null);
421  BM_ASSERT(int(sv_value_plains) == int(SV::sv_value_plains));
422 
423  construct_bv_blocks();
424 }
425 
426 //---------------------------------------------------------------------
427 
428 template<class Val, class SV>
430 {
431  free_bv_blocks();
432 }
433 
434 //---------------------------------------------------------------------
435 
436 template<class Val, class SV>
438  const rsc_sparse_vector<Val, SV>& csv)
439 : sv_(csv.sv_),
440  max_id_(csv.max_id_),
441  in_sync_(csv.in_sync_)
442 {
443  BM_ASSERT(int(sv_value_plains) == int(SV::sv_value_plains));
444 
445  construct_bv_blocks();
446  if (in_sync_)
447  {
448  bv_blocks_ptr_->copy_from(*(csv.bv_blocks_ptr_));
449  }
450 }
451 
452 //---------------------------------------------------------------------
453 
454 template<class Val, class SV>
456 : sv_(bm::use_null),
457  max_id_(0), in_sync_(false)
458 {
459  if (this != &csv)
460  {
461  sv_.swap(csv.sv_);
462  max_id_ = csv.max_id_; in_sync_ = csv.in_sync_;
463 
464  bv_blocks_ptr_ = csv.bv_blocks_ptr_; csv.bv_blocks_ptr_ = 0;
465  }
466 }
467 
468 //---------------------------------------------------------------------
469 
470 template<class Val, class SV>
473 {
474  return max_id_+1;
475 }
476 
477 //---------------------------------------------------------------------
478 
479 template<class Val, class SV>
481 {
482  if (sv_.empty())
483  {
484  }
485  else
486  if (idx <= max_id_)
487  {
488  sv_.throw_range_error("compressed sparse vector push_back() range error");
489  }
490 
491  bvector_type* bv_null = sv_.get_null_bvect();
492  BM_ASSERT(bv_null);
493 
494  bv_null->set(idx);
495  sv_.push_back_no_null(v);
496 
497  max_id_ = idx;
498  in_sync_ = false;
499 }
500 
501 //---------------------------------------------------------------------
502 
503 template<class Val, class SV>
505  const rsc_sparse_vector<Val, SV>& csv) const
506 {
507  if (this == &csv)
508  return true;
509  if (max_id_ != csv.max_id_)
510  return false;
511  bool same_sv = sv_.equal(csv.sv_);
512  return same_sv;
513 }
514 
515 //---------------------------------------------------------------------
516 
517 template<class Val, class SV>
519  const sparse_vector_type& sv_src)
520 {
521  max_id_ = 0;
522 
523  bvector_type* bv_null = sv_.get_null_bvect();
524  BM_ASSERT(bv_null);
525 
526  const bvector_type* bv_null_src = sv_src.get_null_bvector();
527  if (!bv_null_src) // dense vector (no NULL columns)
528  {
529  sv_ = sv_src;
530  BM_ASSERT(sv_.get_null_bvect());
531  }
532  else
533  {
534  sv_.clear();
535  *bv_null = *bv_null_src;
536 
537  bm::rank_compressor<bvector_type> rank_compr; // re-used for plains
538 
539  unsigned src_plains = sv_src.plains();
540  for (unsigned i = 0; i < src_plains; ++i)
541  {
542  const bvector_type* bv_src_plain = sv_src.get_plain(i);
543  if (bv_src_plain)
544  {
545  bvector_type* bv_plain = sv_.get_plain(i);
546  rank_compr.compress(*bv_plain, *bv_null, *bv_src_plain);
547  }
548  } // for
549  unsigned count = bv_null->count(); // set correct sizes
550  sv_.resize(count);
551  }
552 
553  sync(true);
554 }
555 
556 //---------------------------------------------------------------------
557 
558 template<class Val, class SV>
560 {
561  sv.clear();
562 
563  const bvector_type* bv_null_src = this->get_null_bvector();
564  if (!bv_null_src)
565  {
566  BM_ASSERT(bv_null_src);
567  return;
568  }
569 
570  bvector_type* bv_null = sv.get_null_bvect();
571  BM_ASSERT(bv_null);
572  *bv_null = *bv_null_src;
573 
574  bm::rank_compressor<bvector_type> rank_compr; // re-used for plains
575 
576  unsigned src_plains = sv_.plains();
577  for (unsigned i = 0; i < src_plains; ++i)
578  {
579  const bvector_type* bv_src_plain = sv_.get_plain(i);
580  if (bv_src_plain)
581  {
582  bvector_type* bv_plain = sv.get_plain(i);
583  rank_compr.decompress(*bv_plain, *bv_null, *bv_src_plain);
584  }
585  } // for
586  sv.resize(this->size());
587 }
588 
589 //---------------------------------------------------------------------
590 
591 template<class Val, class SV>
593 {
594  if (in_sync_ && force == false)
595  return; // nothing to do
596  const bvector_type* bv_null = sv_.get_null_bvector();
597  BM_ASSERT(bv_null);
598  bv_null->running_count_blocks(bv_blocks_ptr_); // compute popcount prefix list
599 
600  // sync the max-id
601  bool found = bv_null->find_reverse(max_id_);
602  if (!found)
603  {
604  BM_ASSERT(!bv_null->any());
605  max_id_ = 0;
606  }
607  in_sync_ = true;
608 }
609 
610 //---------------------------------------------------------------------
611 
612 template<class Val, class SV>
614 {
615  BM_ASSERT(idx_to);
616 
617  const bvector_type* bv_null = sv_.get_null_bvector();
618  if (in_sync_)
619  {
620  *idx_to = bv_null->count_to_test(idx, *bv_blocks_ptr_);
621  }
622  else // slow access
623  {
624  bool found = bv_null->test(idx);
625  if (!found)
626  {
627  *idx_to = 0;
628  }
629  else
630  {
631  *idx_to = bv_null->count_range(0, idx);
632  }
633  }
634  return bool(*idx_to);
635 }
636 
637 //---------------------------------------------------------------------
638 
639 template<class Val, class SV>
642 {
643  bm::id_t sv_idx;
644  bool found = resolve(idx, &sv_idx);
645  if (!found)
646  {
647  sv_.throw_range_error("compressed collection item not found");
648  }
649  return sv_.at(--sv_idx);
650 }
651 
652 //---------------------------------------------------------------------
653 
654 template<class Val, class SV>
657 {
658  bm::id_t sv_idx;
659  bool found = resolve(idx, &sv_idx);
660  if (!found)
661  return value_type();
662 
663  return sv_.get(--sv_idx);
664 }
665 
666 //---------------------------------------------------------------------
667 
668 template<class Val, class SV>
670 {
671  const bvector_type* bv_null = sv_.get_null_bvector();
672  BM_ASSERT(bv_null);
673  return !(bv_null->test(idx));
674 }
675 
676 //---------------------------------------------------------------------
677 
678 template<class Val, class SV>
680  typename bvector_type::optmode opt_mode,
681  statistics* stat)
682 {
683  sv_.optimize(temp_block, opt_mode, (typename sparse_vector_type::statistics*)stat);
684  if (stat)
685  {
686  stat->memory_used += sizeof(rs_index_type);
687  }
688 }
689 
690 //---------------------------------------------------------------------
691 
692 template<class Val, class SV>
694 {
695  sv_.clear();
696  in_sync_ = false; max_id_ = 0;
697 }
698 
699 //---------------------------------------------------------------------
700 
701 template<class Val, class SV>
704 {
705  BM_ASSERT(st);
706  sv_.calc_stat((typename sparse_vector_type::statistics*)st);
707  if (st)
708  {
709  st->memory_used += sizeof(rs_index_type);
710  }
711 }
712 
713 //---------------------------------------------------------------------
714 
715 template<class Val, class SV>
718 {
719  return sv_.get_null_bvector();
720 }
721 
722 //---------------------------------------------------------------------
723 
724 template<class Val, class SV>
725 bool
727 {
728  BM_ASSERT(rank);
729 
730  bool b;
731  const bvector_type* bv_null = get_null_bvector();
732  if (in_sync())
733  b = bv_null->select(rank, idx, *bv_blocks_ptr_);
734  else
735  b = bv_null->find_rank(rank, 0, idx);
736  return b;
737 }
738 
739 //---------------------------------------------------------------------
740 
741 
742 template<class Val, class SV>
745  size_type idx_from,
746  size_type size,
747  bool /*zero_mem*/) const
748 {
749  BM_ASSERT(arr);
750  BM_ASSERT(in_sync_); // call sync() before decoding
751  BM_ASSERT(bv_blocks_ptr_);
752 
753 
754  if (size == 0)
755  return 0;
756  if (idx_from >= this->size())
757  return 0;
758 
759  if (bm::id_max - size <= idx_from)
760  {
761  size = bm::id_max - idx_from;
762  }
763 
764  const bvector_type* bv_null = sv_.get_null_bvector();
765 
766  bm::id_t rank = bv_null->count_to(idx_from, *bv_blocks_ptr_);
767  bool b = bv_null->test(idx_from);
768 
769  bvector_enumerator_type en_i = bv_null->get_enumerator(idx_from);
770  size_type i = *en_i;
771  if (idx_from + size <= i) // empty space (all zeros)
772  {
773  ::memset(arr, 0, sizeof(value_type)*size);
774  return size;
775  }
776  rank -= b;
777  sparse_vector_const_iterator it = sv_.get_const_iterator(rank);
778  i = 0;
779  while (it.valid())
780  {
781  if (!en_i.valid())
782  break;
783  size_type en_idx = *en_i;
784  while (idx_from < en_idx) // zero the empty prefix
785  {
786  arr[i] ^= arr[i];
787  ++i; ++idx_from;
788  if (i == size)
789  return i;
790  }
791  BM_ASSERT(idx_from == en_idx);
792  arr[i] = *it;
793  ++i; ++idx_from;
794  if (i == size)
795  return i;
796 
797  en_i.advance();
798  it.advance();
799  } // while
800 
801  return i;
802 }
803 
804 //---------------------------------------------------------------------
805 
806 template<class Val, class SV>
808 {
809  if (bv_blocks_ptr_)
810  return;
811  bv_blocks_ptr_ =
813  bv_blocks_ptr_ = new(bv_blocks_ptr_) rs_index_type(); // placement new
814 }
815 
816 //---------------------------------------------------------------------
817 
818 template<class Val, class SV>
820 {
821  bm::aligned_free(bv_blocks_ptr_);
822 }
823 
824 //---------------------------------------------------------------------
825 
826 
827 } // namespace bm
828 
829 #include "bmundef.h"
830 
831 
832 #endif
size_type size() const
return size of the vector
bool find_rank(bm::id_t rank, bm::id_t &idx) const
find position of compressed element by its rank
void clear() BMNOEXEPT
resize to zero, free memory
bool operator==(const reference &ref) const
size_type size_internal() const
size_type effective_size() const
size of internal dense vector
value_type at(bm::id_t idx) const
access specified element with bounds checking
rsc_sparse_vector< Val, SV > & operator=(const rsc_sparse_vector< Val, SV > &csv)
bvector_type::allocation_policy allocation_policy_type
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
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
void * aligned_new_malloc(size_t size)
Aligned malloc (unlike classic malloc it throws bad_alloc exception)
Definition: bmalloc.h:400
Rank-Select compressed sparse vector.
Definition: bm.h:69
void load_to(sparse_vector_type &sv) const
Exort compressed vector to a sparse vector (with NULLs)
pre-processor un-defines to avoid global space pollution (internal)
value_type operator[](size_type idx) const
get specified element without bounds checking
size_type decode(value_type *arr, size_type idx_from, size_type size, bool zero_mem=true) const
static unsigned stored_plains()
Number of stored bit-plains (value plains + extra.
#define BMNOEXEPT
Definition: bmdef.h:78
algorithms for sparse_vector scan/seach
bool resolve(bm::id_t idx, bm::id_t *idx_to) const
Resolve logical address to access via rank compressed address.
const value_type & const_reference
const unsigned id_max
Definition: bmconst.h:43
SV::bvector_type bvector_type
void aligned_free(void *ptr)
Aligned free.
Definition: bmalloc.h:428
void unsync()
Unsync the prefix sum table.
null_support
NULL-able value support.
Definition: bmconst.h:169
const sparse_vector_type & get_sv() const
access dense vector
SV::const_iterator sparse_vector_const_iterator
bool is_nullable() const
if container supports NULL(unassigned) values (true)
void load_from(const sparse_vector_type &sv_src)
Load compressed vector from a sparse vector (with NULLs)
unsigned int word_t
Definition: bmconst.h:35
value_type get(bm::id_t idx) const
get specified element without bounds checking
void decompress(BV &bv_target, const BV &bv_idx, const BV &bv_src)
Rank decompression.
Definition: bmalgo.h:285
bvector_type * bvector_type_ptr
support "non-assigned" or "NULL" logic
Definition: bmconst.h:171
bool in_sync() const
returns true if prefix sum table is in sync with the vector
void resize_internal(size_type sz)
unsigned effective_plains() const
const bvector_type * get_null_bvector() const
Get bit-vector of assigned values (or NULL)
bvector_type::enumerator bvector_enumerator_type
bool equal(const rsc_sparse_vector< Val, SV > &csv) const
check if another vector has the same content
Definitions(internal)
void calc_stat(struct rsc_sparse_vector< Val, SV >::statistics *st) const
Calculates memory statistics.
rsc_sparse_vector< Val, SV > & operator=(rsc_sparse_vector< Val, SV > &&csv) BMNOEXEPT
static bool is_compressed()
trait if sparse vector is "compressed" (true)
bvector_type::rs_index_type rs_index_type
Serialize sparse vector into a memory buffer(s) structure.
bool is_null(size_type idx) const
test if specified element is NULL
const bvector_type * bvector_type_const_ptr
rsc_sparse_vector(bm::null_support null_able=bm::use_null, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type())
void sync()
Re-calculate prefix sum table used for rank search (if necessary)
sparse vector de-serializer
bvector_type_const_ptr get_plain(unsigned i) const
get access to bit-plain, function checks and creates a plain
unsigned int id_t
Definition: bmconst.h:34
reference(rsc_sparse_vector< Val, SV > &csv, size_type idx) BMNOEXEPT
bvector_type::allocator_type allocator_type
bool empty() const
return true if vector is empty
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:211
#define BM_ASSERT
Definition: bmdef.h:116
bvector_type_ptr get_plain(unsigned i)
Reference class to access elements via common [] operator.
Structure with statistical information about bitset&#39;s memory allocation details.
Definition: bmfunc.h:54
void push_back(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
static unsigned plains()
get total number of bit-plains in the vector