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