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