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