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 #ifndef BM__H__INCLUDED__
32 // BitMagic utility headers do not include main "bm.h" declaration
33 // #include "bm.h" or "bm64.h" explicitly
34 # error missing include (bm.h or bm64.h)
35 #endif
36 
37 
38 #include "bmsparsevec.h"
39 #include "bmdef.h"
40 
41 namespace bm
42 {
43 
44 
45 /*!
46  \brief Rank-Select compressed sparse vector
47 
48  Container uses Rank-Select method of compression, where
49  all NULL columns gets dropped, effective address of columns is computed
50  using address bit-vector.
51 
52  Use for cases, where memory efficiency is preferable over
53  single element access latency.
54 
55  \ingroup sv
56 */
57 template<class Val, class SV>
59 {
60 public:
62  {
63  sv_plains = (sizeof(Val) * 8 + 1),
64  sv_value_plains = (sizeof(Val) * 8)
65  };
66 
67  typedef Val value_type;
68  typedef const value_type& const_reference;
69  typedef typename SV::size_type size_type;
70  typedef SV sparse_vector_type;
71  typedef typename SV::const_iterator sparse_vector_const_iterator;
72  typedef typename SV::bvector_type bvector_type;
79  typedef typename SV::bmatrix_type bmatrix_type;
80 
82  {
84  };
85 
86  struct is_remap_support { enum trait { value = false }; };
87  struct is_rsc_support { enum trait { value = true }; };
88 
89 public:
90  /*! Statistical information about memory allocation details. */
91  struct statistics : public bv_statistics
92  {};
93 
94 public:
95  /**
96  Reference class to access elements via common [] operator
97  */
98  class reference
99  {
100  public:
102  : csv_(csv), idx_(idx)
103  {}
104  operator value_type() const BMNOEXCEPT { return csv_.get(idx_); }
105  bool operator==(const reference& ref) const BMNOEXCEPT
106  { return bool(*this) == bool(ref); }
107  bool is_null() const BMNOEXCEPT { return csv_.is_null(idx_); }
108  private:
110  size_type idx_;
111  };
112 
113  /**
114  Const iterator to traverse the rsc sparse vector.
115 
116  Implementation uses buffer for decoding so, competing changes
117  to the original vector may not match the iterator returned values.
118 
119  This iterator keeps an operational buffer, memory footprint is not
120  negligable
121 
122  @ingroup sv
123  */
125  {
126  public:
127  friend class rsc_sparse_vector;
128 
129 #ifndef BM_NO_STL
130  typedef std::input_iterator_tag iterator_category;
131 #endif
138  typedef typename
140  typedef bm::byte_buffer<allocator_type> buffer_type;
141 
142  typedef unsigned difference_type;
143  typedef unsigned* pointer;
145 
146  public:
151 
152  bool operator==(const const_iterator& it) const BMNOEXCEPT
153  { return (pos_ == it.pos_) && (csv_ == it.csv_); }
154  bool operator!=(const const_iterator& it) const BMNOEXCEPT
155  { return ! operator==(it); }
156  bool operator < (const const_iterator& it) const BMNOEXCEPT
157  { return pos_ < it.pos_; }
158  bool operator <= (const const_iterator& it) const BMNOEXCEPT
159  { return pos_ <= it.pos_; }
160  bool operator > (const const_iterator& it) const BMNOEXCEPT
161  { return pos_ > it.pos_; }
162  bool operator >= (const const_iterator& it) const BMNOEXCEPT
163  { return pos_ >= it.pos_; }
164 
165  /// \brief Get current position (value)
166  value_type operator*() const { return this->value(); }
167 
168 
169  /// \brief Advance to the next available value
170  const_iterator& operator++() BMNOEXCEPT { this->advance(); return *this; }
171 
172  /// \brief Advance to the next available value
174  { const_iterator tmp(*this);this->advance(); return tmp; }
175 
176 
177  /// \brief Get current position (value)
178  value_type value() const;
179 
180  /// \brief Get NULL status
181  bool is_null() const BMNOEXCEPT;
182 
183  /// Returns true if iterator is at a valid position
184  bool valid() const BMNOEXCEPT { return pos_ != bm::id_max; }
185 
186  /// Invalidate current iterator
187  void invalidate() BMNOEXCEPT { pos_ = bm::id_max; }
188 
189  /// Current position (index) in the vector
190  size_type pos() const BMNOEXCEPT{ return pos_; }
191 
192  /// re-position to a specified position
194 
195  /// advance iterator forward by one
196  /// @return true if it is still valid
197  bool advance() BMNOEXCEPT;
198 
200  private:
201  enum buf_size_e
202  {
203  n_buf_size = 1024 * 8
204  };
205 
206  private:
207  const rsc_sparse_vector_type* csv_; ///!< ptr to parent
208  size_type pos_; ///!< Position
209  mutable buffer_type vbuffer_; ///!< value buffer
210  mutable buffer_type tbuffer_; ///!< temp buffer
211  mutable value_type* buf_ptr_; ///!< position in the buffer
212  };
213 
214 
215 
216  /**
217  Back insert iterator implements buffered insert, faster than generic
218  access assignment.
219 
220  Limitations for buffered inserter:
221  1. Do not use more than one inserter per vector at a time
222  2. Use method flush() at the end to send the rest of accumulated buffer
223  flush is happening automatically on destruction, but if flush produces an
224  exception (for whatever reason) it will be an exception in destructor.
225  As such, explicit flush() is safer way to finilize the sparse vector load.
226 
227  @ingroup sv
228  */
230  {
231  public:
232 #ifndef BM_NO_STL
233  typedef std::output_iterator_tag iterator_category;
234 #endif
240 
241  typedef void difference_type;
242  typedef void pointer;
243  typedef void reference;
244 
245  public:
248 
250  {
251  BM_ASSERT(bi.empty());
252  this->flush(); sv_bi_ = bi.sv_bi_;
253  return *this;
254  }
255 
257 
258  /** push value to the vector */
260  { this->add(v); return *this; }
261  /** noop */
262  back_insert_iterator& operator*() { return *this; }
263  /** noop */
264  back_insert_iterator& operator++() { return *this; }
265  /** noop */
266  back_insert_iterator& operator++( int ) { return *this; }
267 
268  /** add value to the container*/
269  void add(value_type v);
270 
271  /** add NULL (no-value) to the container */
272  void add_null() BMNOEXCEPT;
273 
274  /** add a series of consequitve NULLs (no-value) to the container */
275  void add_null(size_type count) BMNOEXCEPT;
276 
277  /** flush the accumulated buffer */
278  void flush();
279  protected:
280 
281  /** add value to the buffer without changing the NULL vector
282  @param v - value to push back
283  @return index of added value in the internal buffer
284  @internal
285  */
286  ///size_type add_value(value_type v);
287 
289  typedef
291  private:
292  rsc_sparse_vector_type* csv_; ///!< pointer on the parent vector
293  sparse_vector_bi sv_bi_;
294  };
295 
296 public:
297  // ------------------------------------------------------------
298  /*! @name Construction and assignment */
299  //@{
300 
303  size_type bv_max_size = bm::id_max,
304  const allocator_type& alloc = allocator_type());
306 
307  /*! copy-ctor */
308  rsc_sparse_vector(const rsc_sparse_vector<Val, SV>& csv);
309 
310 
311  /*! copy assignmment operator */
312  rsc_sparse_vector<Val,SV>& operator=(const rsc_sparse_vector<Val, SV>& csv)
313  {
314  if (this != &csv)
315  {
316  sv_ = csv.sv_;
317  size_ = csv.size_; max_id_ = csv.max_id_;
318  in_sync_ = csv.in_sync_;
319  if (in_sync_)
320  {
321  bv_blocks_ptr_->copy_from(*(csv.bv_blocks_ptr_));
322  }
323  }
324  return *this;
325  }
326 
327 #ifndef BM_NO_CXX11
328  /*! move-ctor */
330 
331  /*! move assignmment operator */
333  {
334  if (this != &csv)
335  {
336  clear();
337  sv_.swap(csv.sv_);
338  size_ = csv.size_; max_id_ = csv.max_id_; in_sync_ = csv.in_sync_;
339  if (in_sync_)
340  {
341  bv_blocks_ptr_->copy_from(*(csv.bv_blocks_ptr_));
342  }
343  }
344  return *this;
345  }
346 #endif
347 
348  //@}
349  // ------------------------------------------------------------
350  /*! @name Size, etc */
351  ///@{
352 
353  /*! \brief return size of the vector
354  \return size of sparse vector
355  */
356  size_type size() const BMNOEXCEPT;
357 
358  /*! \brief return true if vector is empty
359  \return true if empty
360  */
361  bool empty() const { return sv_.empty(); }
362 
363  ///@}
364 
365  // ------------------------------------------------------------
366  /*! @name Element access */
367  //@{
368 
369  /*!
370  \brief get specified element without bounds checking
371  \param idx - element index
372  \return value of the element
373  */
374  value_type operator[](size_type idx) const { return this->get(idx); }
375 
376  /*!
377  \brief access specified element with bounds checking
378  \param idx - element index
379  \return value of the element
380  */
381  value_type at(size_type idx) const;
382 
383  /*!
384  \brief get specified element without bounds checking
385  \param idx - element index
386  \return value of the element
387  */
388  value_type get(size_type idx) const BMNOEXCEPT;
389 
390  /*!
391  \brief set specified element with bounds checking and automatic resize
392 
393  Method cannot insert elements, so every new idx has to be greater or equal
394  than what it used before. Elements must be loaded in a sorted order.
395 
396  \param idx - element index
397  \param v - element value
398  */
399  void push_back(size_type idx, value_type v);
400 
401  /*!
402  \brief set specified element with bounds checking and automatic resize
403  \param idx - element index
404  \param v - element value
405  */
406  void set(size_type idx, value_type v);
407 
408  /*!
409  \brief set specified element to NULL
410  RSC vector actually erases element when it is set to NULL (expensive).
411  \param idx - element index
412  */
413  void set_null(size_type idx);
414 
415 
416 
417  /** \brief test if specified element is NULL
418  \param idx - element index
419  \return true if it is NULL false if it was assigned or container
420  is not configured to support assignment flags
421  */
422  bool is_null(size_type idx) const BMNOEXCEPT;
423 
424  /**
425  \brief Get bit-vector of assigned values (or NULL)
426  */
428 
429  /**
430  \brief find position of compressed element by its rank
431  \param rank - rank (virtual index in sparse vector)
432  \param idx - index (true position)
433  */
434  bool find_rank(size_type rank, size_type& idx) const BMNOEXCEPT;
435 
436  //@}
437 
438  // ------------------------------------------------------------
439  /*! @name Export content to C-stype array */
440  ///@{
441 
442  /**
443  \brief C-style decode
444  \param arr - decode target array (must be properly sized)
445  \param idx_from - start address to decode
446  \param size - number of elements to decode
447  \param zero_mem - flag if array needs to beset to zeros first
448 
449  @return actual decoded size
450  @sa decode_buf
451  */
453  size_type idx_from,
454  size_type size,
455  bool zero_mem = true) const;
456 
457 
458  /**
459  \brief C-style decode (variant with external memory)
460  Analog of decode, but requires two arrays.
461  Faster than decode in many cases.
462 
463  \param arr - decode target array (must be properly sized)
464  \param arr_buf_tmp - decode temp bufer (must be same size of arr)
465  \param idx_from - start address to decode
466  \param size - number of elements to decode
467  \param zero_mem - flag if array needs to beset to zeros first
468 
469  @return actual decoded size
470  @sa decode
471  */
473  value_type* arr_buf_tmp,
474  size_type idx_from,
475  size_type size,
476  bool zero_mem = true) const BMNOEXCEPT;
477 
478  ///@}
479 
480 
481  // ------------------------------------------------------------
482  /*! @name Various traits */
483  //@{
484  /**
485  \brief if container supports NULL(unassigned) values (true)
486  */
487  bool is_nullable() const { return true; }
488 
489  /** \brief trait if sparse vector is "compressed" (true)
490  */
491  static
492  bool is_compressed() { return true; }
493 
494  ///@}
495 
496 
497  // ------------------------------------------------------------
498  /*! @name Comparison */
499  //@{
500 
501  /*!
502  \brief check if another vector has the same content
503  \return true, if it is the same
504  */
505  bool equal(const rsc_sparse_vector<Val, SV>& csv) const BMNOEXCEPT;
506  //@}
507 
508 
509  // ------------------------------------------------------------
510  /*! @name Load-Export compressed vector with data */
511 
512  //@{
513 
514 
515  /*!
516  \brief Load compressed vector from a sparse vector (with NULLs)
517  \param sv_src - source sparse vector
518  */
519  void load_from(const sparse_vector_type& sv_src);
520 
521  /*!
522  \brief Exort compressed vector to a sparse vector (with NULLs)
523  \param sv - target sparse vector
524  */
525  void load_to(sparse_vector_type& sv) const;
526 
527  //@}
528 
529  // ------------------------------------------------------------
530  /*! @name Iterator access */
531  //@{
532 
533  /** Provide const iterator access to container content */
535  { return const_iterator(this); }
536 
537  /** Provide const iterator access to the end */
539  { return const_iterator(this, bm::id_max); }
540 
541  /** Get const_itertor re-positioned to specific element
542  @param idx - position in the sparse vector
543  */
545  { return const_iterator(this, idx); }
546 
548  ///@}
549 
550  // ------------------------------------------------------------
551  /*! @name Memory optimization */
552  ///@{
553 
554  /*!
555  \brief run memory optimization for all vector plains
556  \param temp_block - pre-allocated memory block to avoid unnecessary re-allocs
557  \param opt_mode - requested compression depth
558  \param stat - memory allocation statistics after optimization
559  */
560  void optimize(
561  bm::word_t* temp_block = 0,
563  statistics* stat = 0);
564 
565  /*! \brief resize to zero, free memory
566  */
567  void clear() BMNOEXCEPT;
568 
569  /*!
570  @brief Calculates memory statistics.
571 
572  Function fills statistics structure containing information about how
573  this vector uses memory and estimation of max. amount of memory
574  bvector needs to serialize itself.
575 
576  @param st - pointer on statistics structure to be filled in.
577 
578  @sa statistics
579  */
580  void calc_stat(
581  struct rsc_sparse_vector<Val, SV>::statistics* st) const BMNOEXCEPT;
582 
583  ///@}
584 
585  // ------------------------------------------------------------
586  /*! @name Merge, split, partition data */
587  ///@{
588 
589  /**
590  @brief copy range of values from another sparse vector
591 
592  Copy [left..right] values from the source vector,
593  clear everything outside the range.
594 
595  \param csv - source vector
596  \param left - index from in losed diapason of [left..right]
597  \param right - index to in losed diapason of [left..right]
598  */
599  void copy_range(const rsc_sparse_vector<Val, SV>& csv,
600  size_type left, size_type right);
601 
602  ///@}
603 
604  // ------------------------------------------------------------
605  /*! @name Fast access structues sync */
606  //@{
607  /*!
608  \brief Re-calculate prefix sum table used for rank search
609  \param force - force recalculation even if it is already recalculated
610  */
611  void sync(bool force);
612 
613  /*!
614  \brief Re-calculate prefix sum table used for rank search (if necessary)
615  */
616  void sync() { sync(false); }
617 
618  /*!
619  \brief returns true if prefix sum table is in sync with the vector
620  */
621  bool in_sync() const BMNOEXCEPT { return in_sync_; }
622 
623  /*!
624  \brief Unsync the prefix sum table
625  */
626  void unsync() BMNOEXCEPT { in_sync_ = false; }
627  ///@}
628 
629  // ------------------------------------------------------------
630  /*! @name Access to internals */
631  ///@{
632 
633  /*!
634  \brief get access to bit-plain, function checks and creates a plain
635  \return bit-vector for the bit plain
636  */
638  { return sv_.get_plain(i); }
639 
641  { return sv_.get_plain(i); }
642 
643  /*!
644  Number of effective bit-plains in the value type
645  */
646  unsigned effective_plains() const BMNOEXCEPT
647  { return sv_.effective_plains(); }
648 
649  /*!
650  \brief get total number of bit-plains in the vector
651  */
652  static unsigned plains() BMNOEXCEPT
653  { return sparse_vector_type::plains(); }
654 
655  /** Number of stored bit-plains (value plains + extra */
656  static unsigned stored_plains()
657  { return sparse_vector_type::stored_plains(); }
658 
659  /*!
660  \brief access dense vector
661  */
662  const sparse_vector_type& get_sv() const BMNOEXCEPT { return sv_; }
663 
664  /*!
665  \brief size of internal dense vector
666  */
667  size_type effective_size() const BMNOEXCEPT { return sv_.size(); }
668 
669  /**
670  \brief Always 1 (non-matrix type)
671  */
673 
674  /*!
675  get read-only access to inetrnal bit-matrix
676  */
678  { return sv_.get_bmatrix(); }
679 
680  ///@}
681 
682 protected:
684  {
686  };
687 
688  /*!
689  \brief Resolve logical address to access via rank compressed address
690 
691  \param idx - input id to resolve
692  \param idx_to - output id
693 
694  \return true if id is known and resolved successfully
695  */
696  bool resolve(size_type idx, size_type* idx_to) const BMNOEXCEPT;
697 
698  bool resolve_range(size_type from, size_type to,
699  size_type* idx_from, size_type* idx_to) const BMNOEXCEPT;
700 
701  void resize_internal(size_type sz) { sv_.resize_internal(sz); }
702  size_type size_internal() const BMNOEXCEPT { return sv_.size(); }
703 
704  bool is_remap() const BMNOEXCEPT { return false; }
705  size_t remap_size() const BMNOEXCEPT { return 0; }
706  const unsigned char* get_remap_buffer() const BMNOEXCEPT { return 0; }
707  unsigned char* init_remap_buffer() BMNOEXCEPT { return 0; }
709 
711 
712 
713 private:
714  void construct_bv_blocks();
715  void free_bv_blocks();
716 
717 protected:
718  template<class SVect> friend class sparse_vector_scanner;
719  template<class SVect> friend class sparse_vector_serializer;
720  template<class SVect> friend class sparse_vector_deserializer;
721 
722 private:
723  sparse_vector_type sv_; ///< transpose-sparse vector for "dense" packing
724  size_type size_; ///< vector size (logical)
725  size_type max_id_; ///< control variable for sorted load
726  bool in_sync_; ///< flag if prefix sum is in-sync with vector
727  rs_index_type* bv_blocks_ptr_ = 0; ///< prefix sum for rank translation
728 };
729 
730 //---------------------------------------------------------------------
731 //
732 //---------------------------------------------------------------------
733 
734 template<class Val, class SV>
737  size_type bv_max_size,
738  const allocator_type& alloc)
739 : sv_(null_able, ap, bv_max_size, alloc), in_sync_(false)
740 {
741  BM_ASSERT(null_able == bm::use_null);
742  BM_ASSERT(int(sv_value_plains) == int(SV::sv_value_plains));
743  size_ = max_id_ = 0;
744  construct_bv_blocks();
745 }
746 
747 //---------------------------------------------------------------------
748 
749 template<class Val, class SV>
751 {
752  free_bv_blocks();
753 }
754 
755 //---------------------------------------------------------------------
756 
757 template<class Val, class SV>
759  const rsc_sparse_vector<Val, SV>& csv)
760 : sv_(csv.sv_), size_(csv.size_), max_id_(csv.max_id_), in_sync_(csv.in_sync_)
761 {
762  BM_ASSERT(int(sv_value_plains) == int(SV::sv_value_plains));
763 
764  construct_bv_blocks();
765  if (in_sync_)
766  bv_blocks_ptr_->copy_from(*(csv.bv_blocks_ptr_));
767 }
768 
769 //---------------------------------------------------------------------
770 
771 template<class Val, class SV>
774 : sv_(bm::use_null),
775  size_(0),
776  max_id_(0), in_sync_(false)
777 {
778  if (this != &csv)
779  {
780  sv_.swap(csv.sv_);
781  size_ = csv.size_; max_id_ = csv.max_id_; in_sync_ = csv.in_sync_;
782  bv_blocks_ptr_ = csv.bv_blocks_ptr_; csv.bv_blocks_ptr_ = 0;
783  }
784 }
785 
786 //---------------------------------------------------------------------
787 
788 template<class Val, class SV>
791 {
792  return size_;
793 }
794 
795 //---------------------------------------------------------------------
796 
797 template<class Val, class SV>
799 {
800  if (sv_.empty())
801  {}
802  else
803  if (idx <= max_id_ && size_)
804  {
805  sv_.throw_range_error("compressed sparse vector push_back() range error");
806  }
807  push_back_no_check(idx, v);
808 }
809 
810 //---------------------------------------------------------------------
811 
812 template<class Val, class SV>
814 {
815  bvector_type* bv_null = sv_.get_null_bvect();
816  BM_ASSERT(bv_null);
817 
818  bv_null->set_bit_no_check(idx);
819  sv_.push_back_no_null(v);
820 
821  max_id_ = idx;
822  size_ = idx + 1;
823  in_sync_ = false;
824 }
825 
826 //---------------------------------------------------------------------
827 
828 template<class Val, class SV>
830 {
831  bvector_type* bv_null = sv_.get_null_bvect();
832  BM_ASSERT(bv_null);
833 
834  bool found = bv_null->test(idx);
835  if (found)
836  {
837  size_type sv_idx = bv_null->count_range(0, idx);
838  bv_null->clear_bit_no_check(idx);
839  sv_.erase(--sv_idx);
840  in_sync_ = false;
841  }
842 }
843 
844 //---------------------------------------------------------------------
845 
846 template<class Val, class SV>
848 {
849  bvector_type* bv_null = sv_.get_null_bvect();
850  BM_ASSERT(bv_null);
851 
852  bool found = bv_null->test(idx);
853  size_type sv_idx = bv_null->count_range(0, idx); // TODO: make test'n'count
854  if (found)
855  {
856  sv_.set_value_no_null(--sv_idx, v);
857  }
858  else
859  {
860  sv_.insert_value_no_null(sv_idx, v);
861  bv_null->set_bit_no_check(idx);
862 
863  if (idx > max_id_)
864  {
865  max_id_ = idx;
866  size_ = max_id_ + 1;
867  }
868  in_sync_ = false;
869  }
870 }
871 
872 //---------------------------------------------------------------------
873 
874 template<class Val, class SV>
876  const rsc_sparse_vector<Val, SV>& csv) const BMNOEXCEPT
877 {
878  if (this == &csv)
879  return true;
880  if (max_id_ != csv.max_id_ || size_ != csv.size_)
881  return false;
882  bool same_sv = sv_.equal(csv.sv_);
883  return same_sv;
884 }
885 
886 //---------------------------------------------------------------------
887 
888 template<class Val, class SV>
890  const sparse_vector_type& sv_src)
891 {
892  max_id_ = size_ = 0;
893 
894  bvector_type* bv_null = sv_.get_null_bvect();
895  BM_ASSERT(bv_null);
896 
897  const bvector_type* bv_null_src = sv_src.get_null_bvector();
898  if (!bv_null_src) // dense vector (no NULL columns)
899  {
900  sv_ = sv_src;
901  BM_ASSERT(sv_.get_null_bvect());
902  }
903  else
904  {
905  sv_.clear();
906  *bv_null = *bv_null_src;
907 
908  bm::rank_compressor<bvector_type> rank_compr; // re-used for plains
909 
910  unsigned src_plains = sv_src.plains();
911  for (unsigned i = 0; i < src_plains; ++i)
912  {
913  const bvector_type* bv_src_plain = sv_src.get_plain(i);
914  if (bv_src_plain)
915  {
916  bvector_type* bv_plain = sv_.get_plain(i);
917  rank_compr.compress(*bv_plain, *bv_null, *bv_src_plain);
918  }
919  } // for
920  size_type count = bv_null->count(); // set correct sizes
921  sv_.resize(count);
922  }
923 
924  sync(true);
925 }
926 
927 //---------------------------------------------------------------------
928 
929 template<class Val, class SV>
931 {
932  sv.clear();
933 
934  const bvector_type* bv_null_src = this->get_null_bvector();
935  if (!bv_null_src)
936  {
937  BM_ASSERT(bv_null_src);
938  return;
939  }
940 
941  bvector_type* bv_null = sv.get_null_bvect();
942  BM_ASSERT(bv_null);
943  *bv_null = *bv_null_src;
944 
945  bm::rank_compressor<bvector_type> rank_compr; // re-used for plains
946 
947  unsigned src_plains = sv_.plains();
948  for (unsigned i = 0; i < src_plains; ++i)
949  {
950  const bvector_type* bv_src_plain = sv_.get_plain(i);
951  if (bv_src_plain)
952  {
953  bvector_type* bv_plain = sv.get_plain(i);
954  rank_compr.decompress(*bv_plain, *bv_null, *bv_src_plain);
955  }
956  } // for
957  sv.resize(this->size());
958 }
959 
960 //---------------------------------------------------------------------
961 
962 template<class Val, class SV>
964 {
965  if (in_sync_ && force == false)
966  return; // nothing to do
967  const bvector_type* bv_null = sv_.get_null_bvector();
968  BM_ASSERT(bv_null);
969  bv_null->build_rs_index(bv_blocks_ptr_); // compute popcount prefix list
970 
971  // sync the max-id
972  bool found = bv_null->find_reverse(max_id_);
973  if (!found)
974  {
975  BM_ASSERT(!bv_null->any());
976  max_id_ = size_ = 0;
977  }
978  else
979  {
980  size_ = max_id_ + 1;
981  }
982  in_sync_ = true;
983 }
984 
985 //---------------------------------------------------------------------
986 
987 template<class Val, class SV>
989  size_type* idx_to) const BMNOEXCEPT
990 {
991  BM_ASSERT(idx_to);
992  const bvector_type* bv_null = sv_.get_null_bvector();
993  if (in_sync_)
994  {
995  *idx_to = bv_null->count_to_test(idx, *bv_blocks_ptr_);
996  }
997  else // slow access
998  {
999  bool found = bv_null->test(idx);
1000  *idx_to = found ? bv_null->count_range(0, idx) : 0;
1001  }
1002  return bool(*idx_to);
1003 }
1004 
1005 //---------------------------------------------------------------------
1006 
1007 template<class Val, class SV>
1009  size_type from, size_type to,
1010  size_type* idx_from, size_type* idx_to) const BMNOEXCEPT
1011 {
1012  BM_ASSERT(idx_to && idx_from);
1013  const bvector_type* bv_null = sv_.get_null_bvector();
1014  size_type copy_sz, sv_left;
1015  if (in_sync_)
1016  copy_sz = bv_null->count_range(from, to, *bv_blocks_ptr_);
1017  else // slow access
1018  copy_sz = bv_null->count_range(from, to);
1019  if (!copy_sz)
1020  return false;
1021 
1022  if (in_sync_)
1023  sv_left = bv_null->rank_corrected(from, *bv_blocks_ptr_);
1024  else
1025  {
1026  sv_left = bv_null->count_range(0, from);
1027  bool tl = bv_null->test(from); // TODO: add count and test
1028  sv_left -= tl; // rank correction
1029  }
1030 
1031  *idx_from = sv_left; *idx_to = sv_left + copy_sz - 1;
1032  return true;
1033 }
1034 
1035 
1036 //---------------------------------------------------------------------
1037 
1038 template<class Val, class SV>
1041 {
1042  size_type sv_idx;
1043  if (idx >= size())
1044  sv_.throw_range_error("compressed collection access error");
1045 
1046  bool found = resolve(idx, &sv_idx);
1047  if (!found)
1048  {
1049  sv_.throw_range_error("compressed collection item not found");
1050  }
1051  return sv_.at(--sv_idx);
1052 }
1053 
1054 //---------------------------------------------------------------------
1055 
1056 template<class Val, class SV>
1059 {
1060  size_type sv_idx;
1061  bool found = resolve(idx, &sv_idx);
1062  if (!found)
1063  return value_type(0);
1064 
1065  return sv_.get(--sv_idx);
1066 }
1067 
1068 //---------------------------------------------------------------------
1069 
1070 template<class Val, class SV>
1072 {
1073  const bvector_type* bv_null = sv_.get_null_bvector();
1074  BM_ASSERT(bv_null);
1075  return !(bv_null->test(idx));
1076 }
1077 
1078 //---------------------------------------------------------------------
1079 
1080 template<class Val, class SV>
1082  typename bvector_type::optmode opt_mode,
1083  statistics* st)
1084 {
1085  sv_.optimize(temp_block, opt_mode, (typename sparse_vector_type::statistics*)st);
1086  if (st)
1087  {
1088  st->memory_used += sizeof(rs_index_type);
1089  st->memory_used += bv_blocks_ptr_->get_total() *
1090  (sizeof(typename rs_index_type::size_type)
1091  + sizeof(typename rs_index_type::sb_pair_type));
1092  }
1093 }
1094 
1095 //---------------------------------------------------------------------
1096 
1097 template<class Val, class SV>
1099 {
1100  sv_.clear();
1101  in_sync_ = false; max_id_ = size_ = 0;
1102 }
1103 
1104 //---------------------------------------------------------------------
1105 
1106 template<class Val, class SV>
1109 {
1110  BM_ASSERT(st);
1111  sv_.calc_stat((typename sparse_vector_type::statistics*)st);
1112  if (st)
1113  {
1114  st->memory_used += sizeof(rs_index_type);
1115  st->memory_used += bv_blocks_ptr_->get_total() *
1116  (sizeof(typename rs_index_type::size_type)
1117  + sizeof(typename rs_index_type::sb_pair_type));
1118  }
1119 }
1120 
1121 //---------------------------------------------------------------------
1122 
1123 template<class Val, class SV>
1126 {
1127  return sv_.get_null_bvector();
1128 }
1129 
1130 //---------------------------------------------------------------------
1131 
1132 template<class Val, class SV>
1133 bool
1135  size_type& idx) const BMNOEXCEPT
1136 {
1137  BM_ASSERT(rank);
1138  bool b;
1139  const bvector_type* bv_null = get_null_bvector();
1140  if (in_sync())
1141  b = bv_null->select(rank, idx, *bv_blocks_ptr_);
1142  else
1143  b = bv_null->find_rank(rank, 0, idx);
1144  return b;
1145 }
1146 
1147 //---------------------------------------------------------------------
1148 
1149 
1150 template<class Val, class SV>
1153  size_type idx_from,
1154  size_type size,
1155  bool zero_mem) const
1156 {
1157  if (size == 0)
1158  return 0;
1159 
1160  BM_ASSERT(arr);
1161  BM_ASSERT(in_sync_); // call sync() before decoding
1162  BM_ASSERT(bv_blocks_ptr_);
1163 
1164  if (idx_from >= this->size())
1165  return 0;
1166 
1167  if ((bm::id_max - size) <= idx_from)
1168  size = bm::id_max - idx_from;
1169  if ((idx_from + size) > this->size())
1170  size = this->size() - idx_from;
1171 
1172  const bvector_type* bv_null = sv_.get_null_bvector();
1173  size_type rank = bv_null->rank_corrected(idx_from, *bv_blocks_ptr_);
1174 
1175  BM_ASSERT(rank == bv_null->count_range(0, idx_from) - bv_null->test(idx_from));
1176 
1177  bvector_enumerator_type en_i = bv_null->get_enumerator(idx_from);
1178  BM_ASSERT(en_i.valid());
1179 
1180  if (zero_mem)
1181  ::memset(arr, 0, sizeof(value_type)*size);
1182 
1183  sparse_vector_const_iterator it = sv_.get_const_iterator(rank);
1184  size_type i = 0;
1185  if (it.valid())
1186  {
1187  do
1188  {
1189  size_type en_idx = *en_i;
1190  size_type delta = en_idx - idx_from;
1191  idx_from += delta;
1192  i += delta;
1193  if (i >= size)
1194  return size;
1195  arr[i++] = it.value();
1196  if (!en_i.advance())
1197  break;
1198  if (!it.advance())
1199  break;
1200  ++idx_from;
1201  } while (i < size);
1202  }
1203  return i;
1204 }
1205 
1206 
1207 template<class Val, class SV>
1210  value_type* arr_buf_tmp,
1211  size_type idx_from,
1212  size_type size,
1213  bool zero_mem) const BMNOEXCEPT
1214 {
1215  if (!size || (idx_from >= this->size()))
1216  return 0;
1217 
1218  BM_ASSERT(arr && arr_buf_tmp);
1219  BM_ASSERT(arr != arr_buf_tmp);
1220  BM_ASSERT(in_sync_); // call sync() before decoding
1221  BM_ASSERT(bv_blocks_ptr_);
1222 
1223  if ((bm::id_max - size) <= idx_from)
1224  size = bm::id_max - idx_from;
1225  if ((idx_from + size) > this->size())
1226  size = this->size() - idx_from;
1227 
1228  if (zero_mem)
1229  ::memset(arr, 0, sizeof(value_type)*size);
1230 
1231  const bvector_type* bv_null = sv_.get_null_bvector();
1232  size_type rank = bv_null->rank_corrected(idx_from, *bv_blocks_ptr_);
1233 
1234  BM_ASSERT(rank == bv_null->count_range(0, idx_from) - bv_null->test(idx_from));
1235 
1236  bvector_enumerator_type en_i = bv_null->get_enumerator(idx_from);
1237  if (!en_i.valid())
1238  return size;
1239 
1240  size_type i = en_i.value();
1241  if (idx_from + size <= i) // empty space (all zeros)
1242  return size;
1243 
1244  size_type extract_cnt =
1245  bv_null->count_range(idx_from, idx_from + size - 1, *bv_blocks_ptr_);
1246 
1247  BM_ASSERT(extract_cnt <= this->size());
1248  auto ex_sz = sv_.decode(arr_buf_tmp, rank, extract_cnt, true);
1249  BM_ASSERT(ex_sz == extract_cnt); (void) ex_sz;
1250 
1251  for (i = 0; i < extract_cnt; ++i)
1252  {
1253  BM_ASSERT(en_i.valid());
1254  size_type en_idx = *en_i;
1255  arr[en_idx-idx_from] = arr_buf_tmp[i];
1256  en_i.advance();
1257  } // for i
1258 
1259  return size;
1260 }
1261 
1262 
1263 //---------------------------------------------------------------------
1264 
1265 template<class Val, class SV>
1267 {
1268  if (bv_blocks_ptr_)
1269  return;
1270  bv_blocks_ptr_ =
1271  (rs_index_type*) bm::aligned_new_malloc(sizeof(rs_index_type));
1272  bv_blocks_ptr_ = new(bv_blocks_ptr_) rs_index_type(); // placement new
1273 }
1274 
1275 //---------------------------------------------------------------------
1276 
1277 template<class Val, class SV>
1278 void rsc_sparse_vector<Val, SV>::free_bv_blocks()
1279 {
1280  if (bv_blocks_ptr_)
1281  {
1282  bv_blocks_ptr_->~rs_index_type();
1283  bm::aligned_free(bv_blocks_ptr_);
1284  }
1285 }
1286 
1287 //---------------------------------------------------------------------
1288 
1289 template<class Val, class SV>
1291  const rsc_sparse_vector<Val, SV>& csv,
1292  size_type left, size_type right)
1293 {
1294  if (left > right)
1295  bm::xor_swap(left, right);
1296 
1297  if (left >= csv.size())
1298  return;
1299 
1300  size_ = csv.size_; max_id_ = csv.max_id_;
1301  in_sync_ = false;
1302 
1303  const bvector_type* arg_bv_null = csv.sv_.get_null_bvector();
1304  size_type sv_left, sv_right;
1305  bool range_valid = csv.resolve_range(left, right, &sv_left, &sv_right);
1306  if (!range_valid)
1307  {
1308  sv_.clear(); sv_.resize(size_);
1309  bvector_type* bv_null = sv_.get_null_bvect();
1310  bv_null->copy_range(*arg_bv_null, 0, right);
1311  return;
1312  }
1313  bvector_type* bv_null = sv_.get_null_bvect();
1314  bv_null->copy_range(*arg_bv_null, 0, right); // not NULL vector gets a full copy
1315  sv_.copy_range(csv.sv_, sv_left, sv_right, bm::no_null); // don't copy NULL
1316 }
1317 
1318 
1319 
1320 
1321 //---------------------------------------------------------------------
1322 //
1323 //---------------------------------------------------------------------
1324 
1325 
1326 template<class Val, class SV>
1328 : csv_(0)
1329 {}
1330 
1331 
1332 //---------------------------------------------------------------------
1333 
1334 template<class Val, class SV>
1337 {
1338  csv_ = csv;
1339  sv_bi_ = csv->sv_.get_back_inserter();
1340  sv_bi_.disable_set_null(); // NULL is handled outside
1341 }
1342 
1343 //---------------------------------------------------------------------
1344 
1345 template<class Val, class SV>
1347 {
1348  this->flush();
1349 }
1350 
1351 //---------------------------------------------------------------------
1352 
1353 template<class Val, class SV>
1356 {
1357  BM_ASSERT(csv_);
1358  sv_bi_.add_value_no_null(v);
1359  bvector_type* bv_null = sv_bi_.get_null_bvect();
1360  BM_ASSERT(bv_null);
1361  bv_null->set_bit_no_check(csv_->size_);
1362 
1363  csv_->max_id_++;
1364  csv_->size_++;
1365 }
1366 
1367 //---------------------------------------------------------------------
1368 
1369 template<class Val, class SV>
1371 {
1372  BM_ASSERT(csv_);
1373  csv_->max_id_++;
1374  csv_->size_++;
1375 }
1376 
1377 //---------------------------------------------------------------------
1378 
1379 template<class Val, class SV>
1382 {
1383  BM_ASSERT(csv_);
1384  csv_->max_id_+=count;
1385  csv_->size_+=count;
1386 }
1387 
1388 //---------------------------------------------------------------------
1389 
1390 template<class Val, class SV>
1392 {
1393  sv_bi_.flush();
1394  csv_->in_sync_ = false;
1395 }
1396 
1397 //---------------------------------------------------------------------
1398 //
1399 //---------------------------------------------------------------------
1400 
1401 template<class Val, class BV>
1403 : csv_(0), pos_(bm::id_max), buf_ptr_(0)
1404 {}
1405 
1406 //---------------------------------------------------------------------
1407 
1408 template<class Val, class SV>
1411 : csv_(it.csv_), pos_(it.pos_), buf_ptr_(0)
1412 {}
1413 
1414 //---------------------------------------------------------------------
1415 
1416 template<class Val, class SV>
1419  ) BMNOEXCEPT
1420 : csv_(csv), buf_ptr_(0)
1421 {
1422  BM_ASSERT(csv_);
1423  pos_ = csv_->empty() ? bm::id_max : 0u;
1424 }
1425 
1426 //---------------------------------------------------------------------
1427 
1428 template<class Val, class SV>
1432 : csv_(csv), buf_ptr_(0)
1433 {
1434  BM_ASSERT(csv_);
1435  this->go_to(pos);
1436 }
1437 
1438 //---------------------------------------------------------------------
1439 
1440 template<class Val, class SV>
1442 {
1443  pos_ = (!csv_ || pos >= csv_->size()) ? bm::id_max : pos;
1444  buf_ptr_ = 0;
1445 }
1446 
1447 //---------------------------------------------------------------------
1448 
1449 template<class Val, class SV>
1451 {
1452  if (pos_ == bm::id_max) // nothing to do, we are at the end
1453  return false;
1454  ++pos_;
1455  if (pos_ >= csv_->size())
1456  {
1457  this->invalidate();
1458  return false;
1459  }
1460  if (buf_ptr_)
1461  {
1462  ++buf_ptr_;
1463  if (buf_ptr_ - ((value_type*)vbuffer_.data()) >= n_buf_size)
1464  buf_ptr_ = 0;
1465  }
1466  return true;
1467 }
1468 
1469 //---------------------------------------------------------------------
1470 
1471 template<class Val, class SV>
1474 {
1475  BM_ASSERT(this->valid());
1476  value_type v;
1477 
1478  if (!buf_ptr_)
1479  {
1480  vbuffer_.reserve(n_buf_size * sizeof(value_type));
1481  tbuffer_.reserve(n_buf_size * sizeof(value_type));
1482  buf_ptr_ = (value_type*)(vbuffer_.data());
1483  value_type* tmp_buf_ptr = (value_type*) (tbuffer_.data());
1484 
1485  csv_->decode_buf(buf_ptr_, tmp_buf_ptr, pos_, n_buf_size, true);
1486  }
1487  v = *buf_ptr_;
1488  return v;
1489 }
1490 
1491 //---------------------------------------------------------------------
1492 
1493 template<class Val, class SV>
1495 {
1496  value_type v = value();
1497  if (buf_ptr_)
1498  {
1499  v = *buf_ptr_;
1500  value_type* buf_end = ((value_type*)vbuffer_.data()) + n_buf_size;
1501  while(!v)
1502  {
1503  ++pos_;
1504  if (++buf_ptr_ < buf_end)
1505  v = *buf_ptr_;
1506  else
1507  break;
1508  }
1509  if (pos_ >= csv_->size())
1510  {
1511  pos_ = bm::id_max;
1512  return;
1513  }
1514  if (buf_ptr_ >= buf_end)
1515  buf_ptr_ = 0;
1516  }
1517 }
1518 
1519 //---------------------------------------------------------------------
1520 
1521 template<class Val, class SV>
1523 {
1524  return csv_->is_null(pos_);
1525 }
1526 
1527 
1528 //---------------------------------------------------------------------
1529 
1530 
1531 
1532 } // namespace bm
1533 
1534 #include "bmundef.h"
1535 
1536 
1537 #endif
bm::rsc_sparse_vector::allocator_type
bvector_type::allocator_type allocator_type
Definition: bmsparsevec_compr.h:75
bm::rsc_sparse_vector::plains
static unsigned plains() BMNOEXCEPT
get total number of bit-plains in the vector
Definition: bmsparsevec_compr.h:652
bm::rsc_sparse_vector::empty
bool empty() const
return true if vector is empty
Definition: bmsparsevec_compr.h:361
bm::rsc_sparse_vector::const_iterator::operator++
const_iterator & operator++() BMNOEXCEPT
Advance to the next available value.
Definition: bmsparsevec_compr.h:170
bm::rsc_sparse_vector::max_vector_size
@ max_vector_size
Definition: bmsparsevec_compr.h:83
bm::rank_compressor::decompress
void decompress(BV &bv_target, const BV &bv_idx, const BV &bv_src)
Rank decompression.
Definition: bmalgo.h:525
bm::rsc_sparse_vector::const_iterator::rsc_sparse_vector_type_ptr
rsc_sparse_vector_type * rsc_sparse_vector_type_ptr
Definition: bmsparsevec_compr.h:133
bm::rsc_sparse_vector::const_iterator::reference
value_type & reference
Definition: bmsparsevec_compr.h:144
bm::rsc_sparse_vector::reference
Reference class to access elements via common [] operator.
Definition: bmsparsevec_compr.h:98
bm::rsc_sparse_vector::equal
bool equal(const rsc_sparse_vector< Val, SV > &csv) const BMNOEXCEPT
check if another vector has the same content
Definition: bmsparsevec_compr.h:875
bm::rsc_sparse_vector::calc_stat
void calc_stat(struct rsc_sparse_vector< Val, SV >::statistics *st) const BMNOEXCEPT
Calculates memory statistics.
Definition: bmsparsevec_compr.h:1107
bm::rsc_sparse_vector::back_insert_iterator::add
void add(value_type v)
add value to the container
Definition: bmsparsevec_compr.h:1354
bm::bvector::rs_index_type
rs_index< allocator_type > rs_index_type
Definition: bm.h:831
bm::rsc_sparse_vector::const_iterator::size_type
rsc_sparse_vector_type::size_type size_type
Definition: bmsparsevec_compr.h:135
bm::rsc_sparse_vector::decode
size_type decode(value_type *arr, size_type idx_from, size_type size, bool zero_mem=true) const
C-style decode.
Definition: bmsparsevec_compr.h:1152
bm::sparse_vector_deserializer
sparse vector de-serializer
Definition: bmsparsevec_serial.h:223
bm::rsc_sparse_vector::set
void set(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
Definition: bmsparsevec_compr.h:847
bm::rsc_sparse_vector::resolve_range
bool resolve_range(size_type from, size_type to, size_type *idx_from, size_type *idx_to) const BMNOEXCEPT
Definition: bmsparsevec_compr.h:1008
bm::rsc_sparse_vector::back_insert_iterator::rsc_sparse_vector_type
rsc_sparse_vector< Val, SV > rsc_sparse_vector_type
Definition: bmsparsevec_compr.h:235
bm::rsc_sparse_vector::const_iterator::value_type
rsc_sparse_vector_type::value_type value_type
Definition: bmsparsevec_compr.h:134
bm::rsc_sparse_vector::const_iterator::invalidate
void invalidate() BMNOEXCEPT
Invalidate current iterator.
Definition: bmsparsevec_compr.h:187
bm::rsc_sparse_vector::size_internal
size_type size_internal() const BMNOEXCEPT
Definition: bmsparsevec_compr.h:702
bm::rsc_sparse_vector::load_to
void load_to(sparse_vector_type &sv) const
Exort compressed vector to a sparse vector (with NULLs)
Definition: bmsparsevec_compr.h:930
bm::rsc_sparse_vector::bit_plains
bit_plains
Definition: bmsparsevec_compr.h:61
bm::bvector::optmode
optmode
Optimization mode Every next level means additional checks (better compression vs time)
Definition: bm.h:129
bm::rsc_sparse_vector::statistics
Definition: bmsparsevec_compr.h:91
bm::rsc_sparse_vector::rs_index_type
bvector_type::rs_index_type rs_index_type
Definition: bmsparsevec_compr.h:77
bm::rsc_sparse_vector::effective_plains
unsigned effective_plains() const BMNOEXCEPT
Definition: bmsparsevec_compr.h:646
bm::aligned_new_malloc
void * aligned_new_malloc(size_t size)
Aligned malloc (unlike classic malloc it throws bad_alloc exception)
Definition: bmalloc.h:396
bm::rsc_sparse_vector::const_iterator::go_to
void go_to(size_type pos) BMNOEXCEPT
re-position to a specified position
Definition: bmsparsevec_compr.h:1441
bm::rsc_sparse_vector::reference::operator==
bool operator==(const reference &ref) const BMNOEXCEPT
Definition: bmsparsevec_compr.h:105
bm::no_null
@ no_null
do not support NULL values
Definition: bmconst.h:216
bm::rsc_sparse_vector::resize_internal
void resize_internal(size_type sz)
Definition: bmsparsevec_compr.h:701
bm::rsc_sparse_vector::clear
void clear() BMNOEXCEPT
resize to zero, free memory
Definition: bmsparsevec_compr.h:1098
bm::rsc_sparse_vector::in_sync
bool in_sync() const BMNOEXCEPT
returns true if prefix sum table is in sync with the vector
Definition: bmsparsevec_compr.h:621
bm::rank_compressor::compress
void compress(BV &bv_target, const BV &bv_idx, const BV &bv_src)
Rank compression algorithm based on two palallel iterators/enumerators set of source vector gets re-m...
Definition: bmalgo.h:452
bm::rsc_sparse_vector::back_insert_iterator::operator++
back_insert_iterator & operator++(int)
noop
Definition: bmsparsevec_compr.h:266
bm::rsc_sparse_vector::const_iterator
Const iterator to traverse the rsc sparse vector.
Definition: bmsparsevec_compr.h:124
bm::rsc_sparse_vector::const_iterator::allocator_pool_type
bvector_type::allocator_type::allocator_pool_type allocator_pool_type
Definition: bmsparsevec_compr.h:139
bmsparsevec.h
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
bm::rsc_sparse_vector::back_insert_iterator::add_null
void add_null() BMNOEXCEPT
add NULL (no-value) to the container
Definition: bmsparsevec_compr.h:1370
bm::bvector::enumerator
Constant iterator designed to enumerate "ON" bits.
Definition: bm.h:599
bm::sparse_vector_scanner
algorithms for sparse_vector scan/search
Definition: bmsparsevec_algo.h:481
bm::rsc_sparse_vector::resolve
bool resolve(size_type idx, size_type *idx_to) const BMNOEXCEPT
Resolve logical address to access via rank compressed address.
Definition: bmsparsevec_compr.h:988
bm::rsc_sparse_vector::operator[]
value_type operator[](size_type idx) const
get specified element without bounds checking
Definition: bmsparsevec_compr.h:374
bm::rsc_sparse_vector::back_insert_iterator::~back_insert_iterator
~back_insert_iterator()
Definition: bmsparsevec_compr.h:1346
bm::bvector::allocator_type
Alloc allocator_type
Definition: bm.h:110
bm::rsc_sparse_vector::size_type
SV::size_type size_type
Definition: bmsparsevec_compr.h:69
bm::rsc_sparse_vector::const_iterator::operator<
bool operator<(const const_iterator &it) const BMNOEXCEPT
Definition: bmsparsevec_compr.h:156
bm::rsc_sparse_vector::set_remap
void set_remap() BMNOEXCEPT
Definition: bmsparsevec_compr.h:708
bm::rsc_sparse_vector::effective_vector_max
size_type effective_vector_max() const BMNOEXCEPT
Always 1 (non-matrix type)
Definition: bmsparsevec_compr.h:672
bm::rsc_sparse_vector::back_insert_iterator::operator++
back_insert_iterator & operator++()
noop
Definition: bmsparsevec_compr.h:264
bm::rsc_sparse_vector::bvector_type_const_ptr
const typedef bvector_type * bvector_type_const_ptr
Definition: bmsparsevec_compr.h:74
bm::rsc_sparse_vector::const_iterator::operator++
const_iterator & operator++(int)
Advance to the next available value.
Definition: bmsparsevec_compr.h:173
bm::bvector
Bitvector Bit-vector container with runtime compression of bits.
Definition: bm.h:107
bmundef.h
pre-processor un-defines to avoid global space pollution (internal)
bm::rsc_sparse_vector::const_iterator::rsc_sparse_vector_type
rsc_sparse_vector< Val, SV > rsc_sparse_vector_type
Definition: bmsparsevec_compr.h:132
bm::rsc_sparse_vector::const_iterator::const_iterator
const_iterator() BMNOEXCEPT
Definition: bmsparsevec_compr.h:1402
bm::rsc_sparse_vector::const_iterator::value
value_type value() const
Get current position (value)
Definition: bmsparsevec_compr.h:1473
bm::use_null
@ use_null
support "non-assigned" or "NULL" logic
Definition: bmconst.h:215
bm::id_max
const unsigned id_max
Definition: bmconst.h:108
bm::rsc_sparse_vector::back_insert_iterator::sparse_vector_type
rsc_sparse_vector_type::sparse_vector_type sparse_vector_type
add value to the buffer without changing the NULL vector
Definition: bmsparsevec_compr.h:288
bm::rsc_sparse_vector::const_iterator::buffer_type
bm::byte_buffer< allocator_type > buffer_type
Definition: bmsparsevec_compr.h:140
bm::xor_swap
void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two scalar variables.
Definition: bmfunc.h:909
bm::bvector::allocator_pool_type
allocator_type::allocator_pool_type allocator_pool_type
Definition: bm.h:111
bm::rsc_sparse_vector::const_iterator::skip_zero_values
void skip_zero_values() BMNOEXCEPT
Definition: bmsparsevec_compr.h:1494
bm::bvector::iterator_base::valid
bool valid() const BMNOEXCEPT
Checks if iterator is still valid. Analog of != 0 comparison for pointers.
Definition: bm.h:280
bm::rsc_sparse_vector::back_insert_iterator::iterator_category
std::output_iterator_tag iterator_category
Definition: bmsparsevec_compr.h:233
bm::rsc_sparse_vector::bmatrix_type
SV::bmatrix_type bmatrix_type
Definition: bmsparsevec_compr.h:79
bm::rank_compressor< bvector_type >
bm::rsc_sparse_vector::back_insert_iterator::reference
void reference
Definition: bmsparsevec_compr.h:243
bm::rsc_sparse_vector::effective_size
size_type effective_size() const BMNOEXCEPT
size of internal dense vector
Definition: bmsparsevec_compr.h:667
bm::rsc_sparse_vector::sv_plains
@ sv_plains
Definition: bmsparsevec_compr.h:63
bm::rsc_sparse_vector::value_type
Val value_type
Definition: bmsparsevec_compr.h:67
BMNOEXCEPT
#define BMNOEXCEPT
Definition: bmdef.h:79
bm::rsc_sparse_vector::unsync
void unsync() BMNOEXCEPT
Unsync the prefix sum table.
Definition: bmsparsevec_compr.h:626
bm::bvector::opt_compress
@ opt_compress
compress blocks when possible (GAP/prefix sum)
Definition: bm.h:134
bm::bvector::allocation_policy
memory allocation policy
Definition: bm.h:819
bm::rsc_sparse_vector::is_remap_support::value
@ value
Definition: bmsparsevec_compr.h:86
bm::rsc_sparse_vector::vector_capacity
vector_capacity
Definition: bmsparsevec_compr.h:81
bm::rsc_sparse_vector::get_bmatrix
const bmatrix_type & get_bmatrix() const BMNOEXCEPT
Definition: bmsparsevec_compr.h:677
bm::rsc_sparse_vector::const_iterator::operator>
bool operator>(const const_iterator &it) const BMNOEXCEPT
Definition: bmsparsevec_compr.h:160
bm::rsc_sparse_vector::const_iterator::is_null
bool is_null() const BMNOEXCEPT
Get NULL status.
Definition: bmsparsevec_compr.h:1522
bm::rsc_sparse_vector::back_insert_iterator::difference_type
void difference_type
Definition: bmsparsevec_compr.h:241
bm::rsc_sparse_vector::is_null
bool is_null(size_type idx) const BMNOEXCEPT
test if specified element is NULL
Definition: bmsparsevec_compr.h:1071
bm::rsc_sparse_vector::back_insert_iterator::size_type
rsc_sparse_vector_type::size_type size_type
Definition: bmsparsevec_compr.h:238
bm::rsc_sparse_vector::decode_buf
size_type decode_buf(value_type *arr, value_type *arr_buf_tmp, size_type idx_from, size_type size, bool zero_mem=true) const BMNOEXCEPT
C-style decode (variant with external memory) Analog of decode, but requires two arrays.
Definition: bmsparsevec_compr.h:1209
bm::rsc_sparse_vector::remap_size
size_t remap_size() const BMNOEXCEPT
Definition: bmsparsevec_compr.h:705
BM_ASSERT
#define BM_ASSERT
Definition: bmdef.h:130
bm::rsc_sparse_vector::operator=
rsc_sparse_vector< Val, SV > & operator=(rsc_sparse_vector< Val, SV > &&csv) BMNOEXCEPT
Definition: bmsparsevec_compr.h:332
bvector_type
bm::bvector bvector_type
Definition: strsvsample01.cpp:39
bm::rsc_sparse_vector::bvector_type_ptr
bvector_type * bvector_type_ptr
Definition: bmsparsevec_compr.h:73
bm::rsc_sparse_vector::const_iterator::valid
bool valid() const BMNOEXCEPT
Returns true if iterator is at a valid position.
Definition: bmsparsevec_compr.h:184
bm::rsc_sparse_vector::load_from
void load_from(const sparse_vector_type &sv_src)
Load compressed vector from a sparse vector (with NULLs)
Definition: bmsparsevec_compr.h:889
bm::rsc_sparse_vector::find_rank
bool find_rank(size_type rank, size_type &idx) const BMNOEXCEPT
find position of compressed element by its rank
Definition: bmsparsevec_compr.h:1134
bm::rsc_sparse_vector::sv_octet_plains
@ sv_octet_plains
Definition: bmsparsevec_compr.h:685
bm::rsc_sparse_vector::back_insert_iterator::flush
void flush()
flush the accumulated buffer
Definition: bmsparsevec_compr.h:1391
bm::rsc_sparse_vector::get_back_inserter
back_insert_iterator get_back_inserter()
Definition: bmsparsevec_compr.h:547
bm::rsc_sparse_vector::back_insert_iterator::operator=
back_insert_iterator & operator=(value_type v)
push value to the vector
Definition: bmsparsevec_compr.h:259
bm::rsc_sparse_vector::sync
void sync()
Re-calculate prefix sum table used for rank search (if necessary)
Definition: bmsparsevec_compr.h:616
bmdef.h
Definitions(internal)
bm::rsc_sparse_vector::const_reference
const typedef value_type & const_reference
Definition: bmsparsevec_compr.h:68
bm::rsc_sparse_vector::back_insert_iterator::back_insert_iterator
back_insert_iterator() BMNOEXCEPT
Definition: bmsparsevec_compr.h:1327
bm::rsc_sparse_vector::const_iterator::pos
size_type pos() const BMNOEXCEPT
Current position (index) in the vector.
Definition: bmsparsevec_compr.h:190
bm::rsc_sparse_vector::sparse_vector_type
SV sparse_vector_type
Definition: bmsparsevec_compr.h:70
bm::rsc_sparse_vector::size
size_type size() const BMNOEXCEPT
return size of the vector
Definition: bmsparsevec_compr.h:790
bm::rsc_sparse_vector::reference::reference
reference(rsc_sparse_vector< Val, SV > &csv, size_type idx) BMNOEXCEPT
Definition: bmsparsevec_compr.h:101
bm::rsc_sparse_vector::is_remap
bool is_remap() const BMNOEXCEPT
Definition: bmsparsevec_compr.h:704
bm::rsc_sparse_vector::bvector_type
SV::bvector_type bvector_type
Definition: bmsparsevec_compr.h:72
bm::rsc_sparse_vector::const_iterator::bvector_type
rsc_sparse_vector_type::bvector_type bvector_type
Definition: bmsparsevec_compr.h:136
bm::rsc_sparse_vector::init_remap_buffer
unsigned char * init_remap_buffer() BMNOEXCEPT
Definition: bmsparsevec_compr.h:707
bm::rsc_sparse_vector::octet_plains
octet_plains
Definition: bmsparsevec_compr.h:683
bm::rsc_sparse_vector::back_insert_iterator
Back insert iterator implements buffered insert, faster than generic access assignment.
Definition: bmsparsevec_compr.h:229
bm::aligned_free
void aligned_free(void *ptr) BMNOEXCEPT
Aligned free.
Definition: bmalloc.h:424
bm::rsc_sparse_vector::is_remap_support::trait
trait
Definition: bmsparsevec_compr.h:86
bm::rsc_sparse_vector
Rank-Select compressed sparse vector.
Definition: bmsparsevec_compr.h:58
bm::rsc_sparse_vector::~rsc_sparse_vector
~rsc_sparse_vector()
Definition: bmsparsevec_compr.h:750
bm::bvector::enumerator::value
size_type value() const BMNOEXCEPT
Get current position (value)
Definition: bm.h:641
bm::rsc_sparse_vector::is_compressed
static bool is_compressed()
trait if sparse vector is "compressed" (true)
Definition: bmsparsevec_compr.h:492
bm::rsc_sparse_vector::back_insert_iterator::bvector_type
rsc_sparse_vector_type::bvector_type bvector_type
Definition: bmsparsevec_compr.h:239
bm::rsc_sparse_vector::is_nullable
bool is_nullable() const
if container supports NULL(unassigned) values (true)
Definition: bmsparsevec_compr.h:487
bm::rsc_sparse_vector::get_plain
bvector_type_ptr get_plain(unsigned i) BMNOEXCEPT
Definition: bmsparsevec_compr.h:640
bm::rsc_sparse_vector::begin
const_iterator begin() const BMNOEXCEPT
Provide const iterator access to container content
Definition: bmsparsevec_compr.h:534
bm::rsc_sparse_vector::is_rsc_support::value
@ value
Definition: bmsparsevec_compr.h:87
bm::rsc_sparse_vector::optimize
void optimize(bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, statistics *stat=0)
run memory optimization for all vector plains
Definition: bmsparsevec_compr.h:1081
bm::rsc_sparse_vector::is_rsc_support
Definition: bmsparsevec_compr.h:87
bm::rsc_sparse_vector::get_null_bvector
const bvector_type * get_null_bvector() const BMNOEXCEPT
Get bit-vector of assigned values (or NULL)
Definition: bmsparsevec_compr.h:1125
bm::rsc_sparse_vector::push_back
void push_back(size_type idx, value_type v)
set specified element with bounds checking and automatic resize
Definition: bmsparsevec_compr.h:798
bm::rsc_sparse_vector::const_iterator::operator==
bool operator==(const const_iterator &it) const BMNOEXCEPT
Definition: bmsparsevec_compr.h:152
bm::rsc_sparse_vector::const_iterator::operator!=
bool operator!=(const const_iterator &it) const BMNOEXCEPT
Definition: bmsparsevec_compr.h:154
bm::rsc_sparse_vector::const_iterator::advance
bool advance() BMNOEXCEPT
advance iterator forward by one
Definition: bmsparsevec_compr.h:1450
bm::rsc_sparse_vector::const_iterator::operator>=
bool operator>=(const const_iterator &it) const BMNOEXCEPT
Definition: bmsparsevec_compr.h:162
bm
Definition: bm.h:76
bm::rsc_sparse_vector::is_remap_support
Definition: bmsparsevec_compr.h:86
bm::rsc_sparse_vector::is_rsc_support::trait
trait
Definition: bmsparsevec_compr.h:87
bm::rsc_sparse_vector::sv_value_plains
@ sv_value_plains
Definition: bmsparsevec_compr.h:64
bm::rsc_sparse_vector::const_iterator::difference_type
unsigned difference_type
Definition: bmsparsevec_compr.h:142
bm::rsc_sparse_vector::reference::is_null
bool is_null() const BMNOEXCEPT
Definition: bmsparsevec_compr.h:107
bm::rsc_sparse_vector::const_iterator::operator*
value_type operator*() const
Get current position (value)
Definition: bmsparsevec_compr.h:166
bm::null_support
null_support
NULL-able value support.
Definition: bmconst.h:213
bm::rsc_sparse_vector::push_back_no_check
void push_back_no_check(size_type idx, value_type v)
Definition: bmsparsevec_compr.h:813
bm::rsc_sparse_vector::const_iterator::operator<=
bool operator<=(const const_iterator &it) const BMNOEXCEPT
Definition: bmsparsevec_compr.h:158
bm::rsc_sparse_vector::const_iterator::allocator_type
bvector_type::allocator_type allocator_type
Definition: bmsparsevec_compr.h:137
bm::rsc_sparse_vector::allocation_policy_type
bvector_type::allocation_policy allocation_policy_type
Definition: bmsparsevec_compr.h:76
bm::rsc_sparse_vector::bvector_enumerator_type
bvector_type::enumerator bvector_enumerator_type
Definition: bmsparsevec_compr.h:78
bm::rsc_sparse_vector::get_plain
bvector_type_const_ptr get_plain(unsigned i) const BMNOEXCEPT
get access to bit-plain, function checks and creates a plain
Definition: bmsparsevec_compr.h:637
bm::word_t
unsigned int word_t
Definition: bmconst.h:38
bm::rsc_sparse_vector::rsc_sparse_vector
rsc_sparse_vector(bm::null_support null_able=bm::use_null, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type())
Definition: bmsparsevec_compr.h:735
bm::rsc_sparse_vector::stored_plains
static unsigned stored_plains()
Number of stored bit-plains (value plains + extra.
Definition: bmsparsevec_compr.h:656
bm::rsc_sparse_vector::back_insert_iterator::rsc_sparse_vector_type_ptr
rsc_sparse_vector_type * rsc_sparse_vector_type_ptr
Definition: bmsparsevec_compr.h:236
bm::rsc_sparse_vector::set_null
void set_null(size_type idx)
set specified element to NULL RSC vector actually erases element when it is set to NULL (expensive).
Definition: bmsparsevec_compr.h:829
bm::rsc_sparse_vector::const_iterator::pointer
unsigned * pointer
Definition: bmsparsevec_compr.h:143
bm::rsc_sparse_vector::back_insert_iterator::pointer
void pointer
Definition: bmsparsevec_compr.h:242
bm::rsc_sparse_vector::get_remap_buffer
const unsigned char * get_remap_buffer() const BMNOEXCEPT
Definition: bmsparsevec_compr.h:706
bm::rsc_sparse_vector::back_insert_iterator::operator*
back_insert_iterator & operator*()
noop
Definition: bmsparsevec_compr.h:262
bm::rsc_sparse_vector::end
const_iterator end() const BMNOEXCEPT
Provide const iterator access to the end
Definition: bmsparsevec_compr.h:538
bm::bvector::enumerator::advance
bool advance() BMNOEXCEPT
Definition: bm.h:662
bm::rsc_sparse_vector::back_insert_iterator::value_type
rsc_sparse_vector_type::value_type value_type
Definition: bmsparsevec_compr.h:237
bm::rsc_sparse_vector::at
value_type at(size_type idx) const
access specified element with bounds checking
Definition: bmsparsevec_compr.h:1040
bm::sparse_vector_serializer
Definition: bmsparsevec_serial.h:160
bm::bv_statistics
Structure with statistical information about memory allocation footprint, serialization projection,...
Definition: bmfunc.h:54
bm::rsc_sparse_vector::back_insert_iterator::sparse_vector_bi
sparse_vector_type::back_insert_iterator sparse_vector_bi
Definition: bmsparsevec_compr.h:290
bm::rsc_sparse_vector::copy_range
void copy_range(const rsc_sparse_vector< Val, SV > &csv, size_type left, size_type right)
copy range of values from another sparse vector
Definition: bmsparsevec_compr.h:1290
bm::rsc_sparse_vector::get_const_iterator
const_iterator get_const_iterator(size_type idx) const BMNOEXCEPT
Get const_itertor re-positioned to specific element.
Definition: bmsparsevec_compr.h:544
bm::rsc_sparse_vector::get_sv
const sparse_vector_type & get_sv() const BMNOEXCEPT
access dense vector
Definition: bmsparsevec_compr.h:662
bm::rsc_sparse_vector::const_iterator::iterator_category
std::input_iterator_tag iterator_category
Definition: bmsparsevec_compr.h:130
bm::rsc_sparse_vector::sparse_vector_const_iterator
SV::const_iterator sparse_vector_const_iterator
Definition: bmsparsevec_compr.h:71
bm::rsc_sparse_vector::get
value_type get(size_type idx) const BMNOEXCEPT
get specified element without bounds checking
Definition: bmsparsevec_compr.h:1058