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  //@{
301 
304  size_type bv_max_size = bm::id_max,
305  const allocator_type& alloc = allocator_type());
306 
307  /**
308  Contructor to pre-initialize the list of assigned (not NULL) elements.
309 
310  If the list of not NULL elements is known upfront it can help to
311  pre-declare it, enable rank-select index and then use set function.
312  This scenario gives significant speed boost, comparing random assignment
313 
314  @param bv_null - not NULL vector for the container
315  */
316  rsc_sparse_vector(const bvector_type& bv_null);
317 
319 
320  /*! copy-ctor */
321  rsc_sparse_vector(const rsc_sparse_vector<Val, SV>& csv);
322 
323 
324  /*! copy assignmment operator */
325  rsc_sparse_vector<Val,SV>& operator=(const rsc_sparse_vector<Val, SV>& csv)
326  {
327  if (this != &csv)
328  {
329  sv_ = csv.sv_;
330  size_ = csv.size_; max_id_ = csv.max_id_;
331  in_sync_ = csv.in_sync_;
332  if (in_sync_)
333  {
334  bv_blocks_ptr_->copy_from(*(csv.bv_blocks_ptr_));
335  }
336  }
337  return *this;
338  }
339 
340 #ifndef BM_NO_CXX11
341  /*! move-ctor */
343 
344  /*! move assignmment operator */
346  {
347  if (this != &csv)
348  {
349  clear();
350  sv_.swap(csv.sv_);
351  size_ = csv.size_; max_id_ = csv.max_id_; in_sync_ = csv.in_sync_;
352  if (in_sync_)
353  {
354  bv_blocks_ptr_->copy_from(*(csv.bv_blocks_ptr_));
355  }
356  }
357  return *this;
358  }
359 #endif
360 
361  //@}
362  // ------------------------------------------------------------
363  /*! @name Size, etc */
364  ///@{
365 
366  /*! \brief return size of the vector
367  \return size of sparse vector
368  */
369  size_type size() const BMNOEXCEPT;
370 
371  /*! \brief return true if vector is empty
372  \return true if empty
373  */
374  bool empty() const { return sv_.empty(); }
375 
376  ///@}
377 
378  // ------------------------------------------------------------
379  /*! @name Element access */
380  //@{
381 
382  /*!
383  \brief get specified element without bounds checking
384  \param idx - element index
385  \return value of the element
386  */
387  value_type operator[](size_type idx) const { return this->get(idx); }
388 
389  /*!
390  \brief access specified element with bounds checking
391  \param idx - element index
392  \return value of the element
393  */
394  value_type at(size_type idx) const;
395 
396  /*!
397  \brief get specified element without bounds checking
398  \param idx - element index
399  \return value of the element
400  */
401  value_type get(size_type idx) const BMNOEXCEPT;
402 
403  /*!
404  \brief set specified element with bounds checking and automatic resize
405 
406  Method cannot insert elements, so every new idx has to be greater or equal
407  than what it used before. Elements must be loaded in a sorted order.
408 
409  \param idx - element index
410  \param v - element value
411  */
412  void push_back(size_type idx, value_type v);
413 
414  /*!
415  \brief set specified element with bounds checking and automatic resize
416  \param idx - element index
417  \param v - element value
418  */
419  void set(size_type idx, value_type v);
420 
421 
422  /*!
423  \brief increment specified element by one
424  \param idx - element index
425  */
426  void inc(size_type idx);
427 
428  /*!
429  \brief increment specified element by one
430  \param idx - element index
431  \param v - increment value
432  */
433  void inc(size_type idx, value_type v);
434 
435  /*!
436  \brief increment specified element by one, element MUST be NOT NULL
437  Faster than just inc() if element is NULL - behavior is undefined
438  \param idx - element index
439  \param v - increment value
440  @sa inc
441  */
442  void inc_not_null(size_type idx, value_type v);
443 
444  /*!
445  \brief set specified element to NULL
446  RSC vector actually erases element when it is set to NULL (expensive).
447  \param idx - element index
448  */
449  void set_null(size_type idx);
450 
451 
452  /** \brief test if specified element is NULL
453  \param idx - element index
454  \return true if it is NULL false if it was assigned or container
455  is not configured to support assignment flags
456  */
457  bool is_null(size_type idx) const BMNOEXCEPT;
458 
459  /**
460  \brief Get bit-vector of assigned values (or NULL)
461  */
463 
464  /**
465  \brief find position of compressed element by its rank
466  \param rank - rank (virtual index in sparse vector)
467  \param idx - index (true position)
468  */
469  bool find_rank(size_type rank, size_type& idx) const BMNOEXCEPT;
470 
471  //@}
472 
473  // ------------------------------------------------------------
474  /*! @name Export content to C-stype array */
475  ///@{
476 
477  /**
478  \brief C-style decode
479  \param arr - decode target array (must be properly sized)
480  \param idx_from - start address to decode
481  \param size - number of elements to decode
482  \param zero_mem - flag if array needs to beset to zeros first
483 
484  @return actual decoded size
485  @sa decode_buf
486  */
488  size_type idx_from,
489  size_type size,
490  bool zero_mem = true) const;
491 
492 
493  /**
494  \brief C-style decode (variant with external memory)
495  Analog of decode, but requires two arrays.
496  Faster than decode in many cases.
497 
498  \param arr - decode target array (must be properly sized)
499  \param arr_buf_tmp - decode temp bufer (must be same size of arr)
500  \param idx_from - start address to decode
501  \param size - number of elements to decode
502  \param zero_mem - flag if array needs to beset to zeros first
503 
504  @return actual decoded size
505  @sa decode
506  */
508  value_type* arr_buf_tmp,
509  size_type idx_from,
510  size_type size,
511  bool zero_mem = true) const BMNOEXCEPT;
512 
513  ///@}
514 
515 
516  // ------------------------------------------------------------
517  /*! @name Various traits */
518  //@{
519  /**
520  \brief if container supports NULL(unassigned) values (true)
521  */
522  bool is_nullable() const { return true; }
523 
524  /** \brief trait if sparse vector is "compressed" (true)
525  */
526  static
527  bool is_compressed() { return true; }
528 
529  ///@}
530 
531 
532  // ------------------------------------------------------------
533  /*! @name Comparison */
534  //@{
535 
536  /*!
537  \brief check if another vector has the same content
538  \return true, if it is the same
539  */
540  bool equal(const rsc_sparse_vector<Val, SV>& csv) const BMNOEXCEPT;
541  //@}
542 
543 
544  // ------------------------------------------------------------
545  /*! @name Load-Export compressed vector with data */
546 
547  //@{
548 
549 
550  /*!
551  \brief Load compressed vector from a sparse vector (with NULLs)
552  \param sv_src - source sparse vector
553  */
554  void load_from(const sparse_vector_type& sv_src);
555 
556  /*!
557  \brief Exort compressed vector to a sparse vector (with NULLs)
558  \param sv - target sparse vector
559  */
560  void load_to(sparse_vector_type& sv) const;
561 
562  //@}
563 
564  // ------------------------------------------------------------
565  /*! @name Iterator access */
566  //@{
567 
568  /** Provide const iterator access to container content */
570  { return const_iterator(this); }
571 
572  /** Provide const iterator access to the end */
574  { return const_iterator(this, bm::id_max); }
575 
576  /** Get const_itertor re-positioned to specific element
577  @param idx - position in the sparse vector
578  */
580  { return const_iterator(this, idx); }
581 
583  ///@}
584 
585  // ------------------------------------------------------------
586  /*! @name Memory optimization */
587  ///@{
588 
589  /*!
590  \brief run memory optimization for all vector plains
591  \param temp_block - pre-allocated memory block to avoid unnecessary re-allocs
592  \param opt_mode - requested compression depth
593  \param stat - memory allocation statistics after optimization
594  */
595  void optimize(
596  bm::word_t* temp_block = 0,
598  statistics* stat = 0);
599 
600  /*! \brief resize to zero, free memory
601  */
602  void clear() BMNOEXCEPT;
603 
604  /*!
605  @brief Calculates memory statistics.
606 
607  Function fills statistics structure containing information about how
608  this vector uses memory and estimation of max. amount of memory
609  bvector needs to serialize itself.
610 
611  @param st - pointer on statistics structure to be filled in.
612 
613  @sa statistics
614  */
615  void calc_stat(
616  struct rsc_sparse_vector<Val, SV>::statistics* st) const BMNOEXCEPT;
617 
618  ///@}
619 
620  // ------------------------------------------------------------
621  /*! @name Merge, split, partition data */
622  ///@{
623 
624  /**
625  @brief copy range of values from another sparse vector
626 
627  Copy [left..right] values from the source vector,
628  clear everything outside the range.
629 
630  \param csv - source vector
631  \param left - index from in losed diapason of [left..right]
632  \param right - index to in losed diapason of [left..right]
633  */
634  void copy_range(const rsc_sparse_vector<Val, SV>& csv,
635  size_type left, size_type right);
636 
637  /**
638  @brief merge two vectors (argument gets destroyed)
639  It is important that both vectors have the same NULL vectors
640  @param csv - [in,out] argumnet vector to merge
641  (works like move so arg should not be used after the merge)
642  */
643  void merge_not_null(rsc_sparse_vector<Val, SV>& csv);
644 
645  ///@}
646 
647  // ------------------------------------------------------------
648  /*! @name Fast access structues sync */
649  //@{
650  /*!
651  \brief Re-calculate prefix sum table used for rank search
652  \param force - force recalculation even if it is already recalculated
653  */
654  void sync(bool force);
655 
656  /*!
657  \brief Re-calculate prefix sum table used for rank search (if necessary)
658  */
659  void sync() { sync(false); }
660 
661  /*!
662  \brief returns true if prefix sum table is in sync with the vector
663  */
664  bool in_sync() const BMNOEXCEPT { return in_sync_; }
665 
666  /*!
667  \brief Unsync the prefix sum table
668  */
669  void unsync() BMNOEXCEPT { in_sync_ = false; }
670  ///@}
671 
672  // ------------------------------------------------------------
673  /*! @name Access to internals */
674  ///@{
675 
676  /*!
677  \brief get access to bit-plain, function checks and creates a plain
678  \return bit-vector for the bit plain
679  */
681  { return sv_.get_plain(i); }
682 
684  { return sv_.get_plain(i); }
685 
686  /*!
687  Number of effective bit-plains in the value type
688  */
689  unsigned effective_plains() const BMNOEXCEPT
690  { return sv_.effective_plains(); }
691 
692  /*!
693  \brief get total number of bit-plains in the vector
694  */
695  static unsigned plains() BMNOEXCEPT
696  { return sparse_vector_type::plains(); }
697 
698  /** Number of stored bit-plains (value plains + extra */
699  static unsigned stored_plains()
700  { return sparse_vector_type::stored_plains(); }
701 
702  /*!
703  \brief access dense vector
704  */
705  const sparse_vector_type& get_sv() const BMNOEXCEPT { return sv_; }
706 
707  /*!
708  \brief size of internal dense vector
709  */
710  size_type effective_size() const BMNOEXCEPT { return sv_.size(); }
711 
712  /**
713  \brief Always 1 (non-matrix type)
714  */
716 
717  /*!
718  get read-only access to inetrnal bit-matrix
719  */
721  { return sv_.get_bmatrix(); }
722 
723  ///@}
724 
725 protected:
727  {
729  };
730 
731  /*!
732  \brief Resolve logical address to access via rank compressed address
733 
734  \param idx - input id to resolve
735  \param idx_to - output id
736 
737  \return true if id is known and resolved successfully
738  */
739  bool resolve(size_type idx, size_type* idx_to) const BMNOEXCEPT;
740 
741  bool resolve_range(size_type from, size_type to,
742  size_type* idx_from, size_type* idx_to) const BMNOEXCEPT;
743 
744  void resize_internal(size_type sz) { sv_.resize_internal(sz); }
745  size_type size_internal() const BMNOEXCEPT { return sv_.size(); }
746 
747  bool is_remap() const BMNOEXCEPT { return false; }
748  size_t remap_size() const BMNOEXCEPT { return 0; }
749  const unsigned char* get_remap_buffer() const BMNOEXCEPT { return 0; }
750  unsigned char* init_remap_buffer() BMNOEXCEPT { return 0; }
752 
754 
755 
756 private:
757 
758  /// Allocate memory for RS index
759  void construct_rs_index();
760  /// Free rs-index
761  void free_rs_index();
762 
763 protected:
764  template<class SVect> friend class sparse_vector_scanner;
765  template<class SVect> friend class sparse_vector_serializer;
766  template<class SVect> friend class sparse_vector_deserializer;
767 
768 private:
769  sparse_vector_type sv_; ///< transpose-sparse vector for "dense" packing
770  size_type size_; ///< vector size (logical)
771  size_type max_id_; ///< control variable for sorted load
772  bool in_sync_; ///< flag if prefix sum is in-sync with vector
773  rs_index_type* bv_blocks_ptr_ = 0; ///< prefix sum for rank translation
774 };
775 
776 //---------------------------------------------------------------------
777 //
778 //---------------------------------------------------------------------
779 
780 template<class Val, class SV>
783  size_type bv_max_size,
784  const allocator_type& alloc)
785 : sv_(null_able, ap, bv_max_size, alloc), in_sync_(false)
786 {
787  BM_ASSERT(null_able == bm::use_null);
788  BM_ASSERT(int(sv_value_plains) == int(SV::sv_value_plains));
789  size_ = max_id_ = 0;
790  construct_rs_index();
791 }
792 
793 //---------------------------------------------------------------------
794 
795 template<class Val, class SV>
797 : sv_(bm::use_null), in_sync_(false)
798 {
799  construct_rs_index();
800  bvector_type* bv = sv_.get_null_bvect();
801  BM_ASSERT(bv);
802  *bv = bv_null;
803 
804  bool found = bv->find_reverse(max_id_);
805  if (found)
806  {
807  size_ = max_id_ + 1;
808  size_type sz = bv->count();
809  sv_.resize(sz);
810  }
811  else
812  {
813  BM_ASSERT(!bv->any());
814  size_ = max_id_ = 0;
815  }
816 }
817 
818 //---------------------------------------------------------------------
819 
820 template<class Val, class SV>
822 {
823  free_rs_index();
824 }
825 
826 //---------------------------------------------------------------------
827 
828 template<class Val, class SV>
830  const rsc_sparse_vector<Val, SV>& csv)
831 : sv_(csv.sv_), size_(csv.size_), max_id_(csv.max_id_), in_sync_(csv.in_sync_)
832 {
833  BM_ASSERT(int(sv_value_plains) == int(SV::sv_value_plains));
834 
835  construct_rs_index();
836  if (in_sync_)
837  bv_blocks_ptr_->copy_from(*(csv.bv_blocks_ptr_));
838 }
839 
840 //---------------------------------------------------------------------
841 
842 template<class Val, class SV>
845 : sv_(bm::use_null),
846  size_(0),
847  max_id_(0), in_sync_(false)
848 {
849  if (this != &csv)
850  {
851  sv_.swap(csv.sv_);
852  size_ = csv.size_; max_id_ = csv.max_id_; in_sync_ = csv.in_sync_;
853  bv_blocks_ptr_ = csv.bv_blocks_ptr_; csv.bv_blocks_ptr_ = 0;
854  }
855 }
856 
857 //---------------------------------------------------------------------
858 
859 template<class Val, class SV>
862 {
863  return size_;
864 }
865 
866 //---------------------------------------------------------------------
867 
868 template<class Val, class SV>
870 {
871  if (sv_.empty())
872  {}
873  else
874  if (idx <= max_id_ && size_)
875  {
876  sv_.throw_range_error("compressed sparse vector push_back() range error");
877  }
878  push_back_no_check(idx, v);
879 }
880 
881 //---------------------------------------------------------------------
882 
883 template<class Val, class SV>
885 {
886  bvector_type* bv_null = sv_.get_null_bvect();
887  BM_ASSERT(bv_null);
888 
889  bv_null->set_bit_no_check(idx);
890  sv_.push_back_no_null(v);
891 
892  max_id_ = idx;
893  size_ = idx + 1;
894  in_sync_ = false;
895 }
896 
897 //---------------------------------------------------------------------
898 
899 template<class Val, class SV>
901 {
902  bvector_type* bv_null = sv_.get_null_bvect();
903  BM_ASSERT(bv_null);
904 
905  bool found = bv_null->test(idx);
906  if (found)
907  {
908  size_type sv_idx = bv_null->count_range(0, idx);
909  bv_null->clear_bit_no_check(idx);
910  sv_.erase(--sv_idx);
911  in_sync_ = false;
912  }
913 }
914 
915 //---------------------------------------------------------------------
916 
917 template<class Val, class SV>
919 {
920  bvector_type* bv_null = sv_.get_null_bvect();
921  BM_ASSERT(bv_null);
922 
923  size_type sv_idx;
924  bool found = bv_null->test(idx);
925 
926  sv_idx = in_sync_ ? bv_null->count_to(idx, *bv_blocks_ptr_)
927  : bv_null->count_range(0, idx); // TODO: make test'n'count
928 
929  if (found)
930  {
931  sv_.inc_no_null(--sv_idx);
932  }
933  else
934  {
935  sv_.insert_value_no_null(sv_idx, 1);
936  bv_null->set_bit_no_check(idx);
937 
938  if (idx > max_id_)
939  {
940  max_id_ = idx;
941  size_ = max_id_ + 1;
942  }
943  in_sync_ = false;
944  }
945 }
946 
947 //---------------------------------------------------------------------
948 
949 template<class Val, class SV>
951 {
952  bvector_type* bv_null = sv_.get_null_bvect();
953  BM_ASSERT(bv_null);
954 
955  size_type sv_idx;
956  bool found = bv_null->test(idx);
957 
958  sv_idx = in_sync_ ? bv_null->count_to(idx, *bv_blocks_ptr_)
959  : bv_null->count_range(0, idx); // TODO: make test'n'count
960 
961  if (found)
962  {
963  sv_.inc_no_null(--sv_idx, v);
964  }
965  else
966  {
967  sv_.insert_value_no_null(sv_idx, v);
968  bv_null->set_bit_no_check(idx);
969 
970  if (idx > max_id_)
971  {
972  max_id_ = idx;
973  size_ = max_id_ + 1;
974  }
975  in_sync_ = false;
976  }
977 }
978 
979 //---------------------------------------------------------------------
980 
981 template<class Val, class SV>
983 {
984  bvector_type* bv_null = sv_.get_null_bvect();
985  BM_ASSERT(bv_null->test(idx)); // idx must be NOT NULL
986 
987  size_type sv_idx;
988  sv_idx = in_sync_ ? bv_null->count_to(idx, *bv_blocks_ptr_)
989  : bv_null->count_range(0, idx); // TODO: make test'n'count
990  --sv_idx;
991  if (v == 1)
992  sv_.inc_no_null(sv_idx);
993  else
994  sv_.inc_no_null(sv_idx, v);
995 }
996 
997 
998 //---------------------------------------------------------------------
999 
1000 template<class Val, class SV>
1002 {
1003  bvector_type* bv_null = sv_.get_null_bvect();
1004  BM_ASSERT(bv_null);
1005 
1006  size_type sv_idx;
1007  bool found = bv_null->test(idx);
1008 
1009  sv_idx = in_sync_ ? bv_null->count_to(idx, *bv_blocks_ptr_)
1010  : bv_null->count_range(0, idx); // TODO: make test'n'count
1011 
1012  if (found)
1013  {
1014  sv_.set_value_no_null(--sv_idx, v);
1015  }
1016  else
1017  {
1018  sv_.insert_value_no_null(sv_idx, v);
1019  bv_null->set_bit_no_check(idx);
1020 
1021  if (idx > max_id_)
1022  {
1023  max_id_ = idx;
1024  size_ = max_id_ + 1;
1025  }
1026  in_sync_ = false;
1027  }
1028 }
1029 
1030 //---------------------------------------------------------------------
1031 
1032 template<class Val, class SV>
1034  const rsc_sparse_vector<Val, SV>& csv) const BMNOEXCEPT
1035 {
1036  if (this == &csv)
1037  return true;
1038  if (max_id_ != csv.max_id_ || size_ != csv.size_)
1039  return false;
1040  bool same_sv = sv_.equal(csv.sv_);
1041  return same_sv;
1042 }
1043 
1044 //---------------------------------------------------------------------
1045 
1046 template<class Val, class SV>
1048  const sparse_vector_type& sv_src)
1049 {
1050  max_id_ = size_ = 0;
1051 
1052  bvector_type* bv_null = sv_.get_null_bvect();
1053  BM_ASSERT(bv_null);
1054 
1055  const bvector_type* bv_null_src = sv_src.get_null_bvector();
1056  if (!bv_null_src) // dense vector (no NULL columns)
1057  {
1058  sv_ = sv_src;
1059  BM_ASSERT(sv_.get_null_bvect());
1060  }
1061  else
1062  {
1063  sv_.clear();
1064  *bv_null = *bv_null_src;
1065 
1066  bm::rank_compressor<bvector_type> rank_compr; // re-used for plains
1067 
1068  unsigned src_plains = sv_src.plains();
1069  for (unsigned i = 0; i < src_plains; ++i)
1070  {
1071  const bvector_type* bv_src_plain = sv_src.get_plain(i);
1072  if (bv_src_plain)
1073  {
1074  bvector_type* bv_plain = sv_.get_plain(i);
1075  rank_compr.compress(*bv_plain, *bv_null, *bv_src_plain);
1076  }
1077  } // for
1078  size_type count = bv_null->count(); // set correct sizes
1079  sv_.resize(count);
1080  }
1081 
1082  sync(true);
1083 }
1084 
1085 //---------------------------------------------------------------------
1086 
1087 template<class Val, class SV>
1089 {
1090  sv.clear();
1091 
1092  const bvector_type* bv_null_src = this->get_null_bvector();
1093  if (!bv_null_src)
1094  {
1095  BM_ASSERT(bv_null_src);
1096  return;
1097  }
1098 
1099  bvector_type* bv_null = sv.get_null_bvect();
1100  BM_ASSERT(bv_null);
1101  *bv_null = *bv_null_src;
1102 
1103  bm::rank_compressor<bvector_type> rank_compr; // re-used for plains
1104 
1105  unsigned src_plains = sv_.plains();
1106  for (unsigned i = 0; i < src_plains; ++i)
1107  {
1108  const bvector_type* bv_src_plain = sv_.get_plain(i);
1109  if (bv_src_plain)
1110  {
1111  bvector_type* bv_plain = sv.get_plain(i);
1112  rank_compr.decompress(*bv_plain, *bv_null, *bv_src_plain);
1113  }
1114  } // for
1115  sv.resize(this->size());
1116 }
1117 
1118 //---------------------------------------------------------------------
1119 
1120 template<class Val, class SV>
1122 {
1123  if (in_sync_ && force == false)
1124  return; // nothing to do
1125  const bvector_type* bv_null = sv_.get_null_bvector();
1126  BM_ASSERT(bv_null);
1127  bv_null->build_rs_index(bv_blocks_ptr_); // compute popcount prefix list
1128 
1129  // sync the max-id
1130  bool found = bv_null->find_reverse(max_id_);
1131  if (!found)
1132  {
1133  BM_ASSERT(!bv_null->any());
1134  max_id_ = size_ = 0;
1135  }
1136  else
1137  {
1138  size_ = max_id_ + 1;
1139  }
1140  in_sync_ = true;
1141 }
1142 
1143 //---------------------------------------------------------------------
1144 
1145 template<class Val, class SV>
1147  size_type* idx_to) const BMNOEXCEPT
1148 {
1149  BM_ASSERT(idx_to);
1150  const bvector_type* bv_null = sv_.get_null_bvector();
1151  if (in_sync_)
1152  {
1153  *idx_to = bv_null->count_to_test(idx, *bv_blocks_ptr_);
1154  }
1155  else // slow access
1156  {
1157  bool found = bv_null->test(idx);
1158  *idx_to = found ? bv_null->count_range(0, idx) : 0;
1159  }
1160  return bool(*idx_to);
1161 }
1162 
1163 //---------------------------------------------------------------------
1164 
1165 template<class Val, class SV>
1167  size_type from, size_type to,
1168  size_type* idx_from, size_type* idx_to) const BMNOEXCEPT
1169 {
1170  BM_ASSERT(idx_to && idx_from);
1171  const bvector_type* bv_null = sv_.get_null_bvector();
1172  size_type copy_sz, sv_left;
1173  if (in_sync_)
1174  copy_sz = bv_null->count_range(from, to, *bv_blocks_ptr_);
1175  else // slow access
1176  copy_sz = bv_null->count_range(from, to);
1177  if (!copy_sz)
1178  return false;
1179 
1180  if (in_sync_)
1181  sv_left = bv_null->rank_corrected(from, *bv_blocks_ptr_);
1182  else
1183  {
1184  sv_left = bv_null->count_range(0, from);
1185  bool tl = bv_null->test(from); // TODO: add count and test
1186  sv_left -= tl; // rank correction
1187  }
1188 
1189  *idx_from = sv_left; *idx_to = sv_left + copy_sz - 1;
1190  return true;
1191 }
1192 
1193 
1194 //---------------------------------------------------------------------
1195 
1196 template<class Val, class SV>
1199 {
1200  size_type sv_idx;
1201  if (idx >= size())
1202  sv_.throw_range_error("compressed collection access error");
1203 
1204  bool found = resolve(idx, &sv_idx);
1205  if (!found)
1206  {
1207  sv_.throw_range_error("compressed collection item not found");
1208  }
1209  return sv_.at(--sv_idx);
1210 }
1211 
1212 //---------------------------------------------------------------------
1213 
1214 template<class Val, class SV>
1217 {
1218  size_type sv_idx;
1219  bool found = resolve(idx, &sv_idx);
1220  if (!found)
1221  return value_type(0);
1222 
1223  return sv_.get(--sv_idx);
1224 }
1225 
1226 //---------------------------------------------------------------------
1227 
1228 template<class Val, class SV>
1230 {
1231  const bvector_type* bv_null = sv_.get_null_bvector();
1232  BM_ASSERT(bv_null);
1233  return !(bv_null->test(idx));
1234 }
1235 
1236 //---------------------------------------------------------------------
1237 
1238 template<class Val, class SV>
1240  typename bvector_type::optmode opt_mode,
1241  statistics* st)
1242 {
1243  sv_.optimize(temp_block, opt_mode, (typename sparse_vector_type::statistics*)st);
1244  if (st)
1245  {
1246  st->memory_used += sizeof(rs_index_type);
1247  st->memory_used += bv_blocks_ptr_->get_total() *
1248  (sizeof(typename rs_index_type::size_type)
1249  + sizeof(typename rs_index_type::sb_pair_type));
1250  }
1251 }
1252 
1253 //---------------------------------------------------------------------
1254 
1255 template<class Val, class SV>
1257 {
1258  sv_.clear();
1259  in_sync_ = false; max_id_ = size_ = 0;
1260 }
1261 
1262 //---------------------------------------------------------------------
1263 
1264 template<class Val, class SV>
1267 {
1268  BM_ASSERT(st);
1269  sv_.calc_stat((typename sparse_vector_type::statistics*)st);
1270  if (st)
1271  {
1272  st->memory_used += sizeof(rs_index_type);
1273  st->memory_used += bv_blocks_ptr_->get_total() *
1274  (sizeof(typename rs_index_type::size_type)
1275  + sizeof(typename rs_index_type::sb_pair_type));
1276  }
1277 }
1278 
1279 //---------------------------------------------------------------------
1280 
1281 template<class Val, class SV>
1284 {
1285  return sv_.get_null_bvector();
1286 }
1287 
1288 //---------------------------------------------------------------------
1289 
1290 template<class Val, class SV>
1291 bool
1293  size_type& idx) const BMNOEXCEPT
1294 {
1295  BM_ASSERT(rank);
1296  bool b;
1297  const bvector_type* bv_null = get_null_bvector();
1298  if (in_sync())
1299  b = bv_null->select(rank, idx, *bv_blocks_ptr_);
1300  else
1301  b = bv_null->find_rank(rank, 0, idx);
1302  return b;
1303 }
1304 
1305 //---------------------------------------------------------------------
1306 
1307 
1308 template<class Val, class SV>
1311  size_type idx_from,
1312  size_type size,
1313  bool zero_mem) const
1314 {
1315  if (size == 0)
1316  return 0;
1317 
1318  BM_ASSERT(arr);
1319  BM_ASSERT(in_sync_); // call sync() before decoding
1320  BM_ASSERT(bv_blocks_ptr_);
1321 
1322  if (idx_from >= this->size())
1323  return 0;
1324 
1325  if ((bm::id_max - size) <= idx_from)
1326  size = bm::id_max - idx_from;
1327  if ((idx_from + size) > this->size())
1328  size = this->size() - idx_from;
1329 
1330  const bvector_type* bv_null = sv_.get_null_bvector();
1331  size_type rank = bv_null->rank_corrected(idx_from, *bv_blocks_ptr_);
1332 
1333  BM_ASSERT(rank == bv_null->count_range(0, idx_from) - bv_null->test(idx_from));
1334 
1335  bvector_enumerator_type en_i = bv_null->get_enumerator(idx_from);
1336  BM_ASSERT(en_i.valid());
1337 
1338  if (zero_mem)
1339  ::memset(arr, 0, sizeof(value_type)*size);
1340 
1341  sparse_vector_const_iterator it = sv_.get_const_iterator(rank);
1342  size_type i = 0;
1343  if (it.valid())
1344  {
1345  do
1346  {
1347  size_type en_idx = *en_i;
1348  size_type delta = en_idx - idx_from;
1349  idx_from += delta;
1350  i += delta;
1351  if (i >= size)
1352  return size;
1353  arr[i++] = it.value();
1354  if (!en_i.advance())
1355  break;
1356  if (!it.advance())
1357  break;
1358  ++idx_from;
1359  } while (i < size);
1360  }
1361  return i;
1362 }
1363 
1364 
1365 template<class Val, class SV>
1368  value_type* arr_buf_tmp,
1369  size_type idx_from,
1370  size_type size,
1371  bool zero_mem) const BMNOEXCEPT
1372 {
1373  if (!size || (idx_from >= this->size()))
1374  return 0;
1375 
1376  BM_ASSERT(arr && arr_buf_tmp);
1377  BM_ASSERT(arr != arr_buf_tmp);
1378  BM_ASSERT(in_sync_); // call sync() before decoding
1379  BM_ASSERT(bv_blocks_ptr_);
1380 
1381  if ((bm::id_max - size) <= idx_from)
1382  size = bm::id_max - idx_from;
1383  if ((idx_from + size) > this->size())
1384  size = this->size() - idx_from;
1385 
1386  if (zero_mem)
1387  ::memset(arr, 0, sizeof(value_type)*size);
1388 
1389  const bvector_type* bv_null = sv_.get_null_bvector();
1390  size_type rank = bv_null->rank_corrected(idx_from, *bv_blocks_ptr_);
1391 
1392  BM_ASSERT(rank == bv_null->count_range(0, idx_from) - bv_null->test(idx_from));
1393 
1394  bvector_enumerator_type en_i = bv_null->get_enumerator(idx_from);
1395  if (!en_i.valid())
1396  return size;
1397 
1398  size_type i = en_i.value();
1399  if (idx_from + size <= i) // empty space (all zeros)
1400  return size;
1401 
1402  size_type extract_cnt =
1403  bv_null->count_range(idx_from, idx_from + size - 1, *bv_blocks_ptr_);
1404 
1405  BM_ASSERT(extract_cnt <= this->size());
1406  auto ex_sz = sv_.decode(arr_buf_tmp, rank, extract_cnt, true);
1407  BM_ASSERT(ex_sz == extract_cnt); (void) ex_sz;
1408 
1409  for (i = 0; i < extract_cnt; ++i)
1410  {
1411  BM_ASSERT(en_i.valid());
1412  size_type en_idx = *en_i;
1413  arr[en_idx-idx_from] = arr_buf_tmp[i];
1414  en_i.advance();
1415  } // for i
1416 
1417  return size;
1418 }
1419 
1420 
1421 //---------------------------------------------------------------------
1422 
1423 template<class Val, class SV>
1425 {
1426  if (bv_blocks_ptr_)
1427  return;
1428  bv_blocks_ptr_ =
1429  (rs_index_type*) bm::aligned_new_malloc(sizeof(rs_index_type));
1430  bv_blocks_ptr_ = new(bv_blocks_ptr_) rs_index_type(); // placement new
1431 }
1432 
1433 //---------------------------------------------------------------------
1434 
1435 template<class Val, class SV>
1436 void rsc_sparse_vector<Val, SV>::free_rs_index()
1437 {
1438  if (bv_blocks_ptr_)
1439  {
1440  bv_blocks_ptr_->~rs_index_type();
1441  bm::aligned_free(bv_blocks_ptr_);
1442  }
1443 }
1444 
1445 //---------------------------------------------------------------------
1446 
1447 template<class Val, class SV>
1449  const rsc_sparse_vector<Val, SV>& csv,
1450  size_type left, size_type right)
1451 {
1452  if (left > right)
1453  bm::xor_swap(left, right);
1454 
1455  if (left >= csv.size())
1456  return;
1457 
1458  size_ = csv.size_; max_id_ = csv.max_id_;
1459  in_sync_ = false;
1460 
1461  const bvector_type* arg_bv_null = csv.sv_.get_null_bvector();
1462  size_type sv_left, sv_right;
1463  bool range_valid = csv.resolve_range(left, right, &sv_left, &sv_right);
1464  if (!range_valid)
1465  {
1466  sv_.clear(); sv_.resize(size_);
1467  bvector_type* bv_null = sv_.get_null_bvect();
1468  bv_null->copy_range(*arg_bv_null, 0, right);
1469  return;
1470  }
1471  bvector_type* bv_null = sv_.get_null_bvect();
1472  bv_null->copy_range(*arg_bv_null, 0, right); // not NULL vector gets a full copy
1473  sv_.copy_range(csv.sv_, sv_left, sv_right, bm::no_null); // don't copy NULL
1474 }
1475 
1476 
1477 //---------------------------------------------------------------------
1478 
1479 template<class Val, class SV>
1481 {
1482  // MUST have the same NULL to work
1483  BM_ASSERT(sv_.get_null_bvector()->equal(*csv.sv_.get_null_bvector()));
1484 
1485  sv_.merge(csv.sv_);
1486 }
1487 
1488 
1489 //---------------------------------------------------------------------
1490 //
1491 //---------------------------------------------------------------------
1492 
1493 
1494 template<class Val, class SV>
1496 : csv_(0)
1497 {}
1498 
1499 
1500 //---------------------------------------------------------------------
1501 
1502 template<class Val, class SV>
1505 {
1506  csv_ = csv;
1507  sv_bi_ = csv->sv_.get_back_inserter();
1508  sv_bi_.disable_set_null(); // NULL is handled outside
1509 }
1510 
1511 //---------------------------------------------------------------------
1512 
1513 template<class Val, class SV>
1515 {
1516  this->flush();
1517 }
1518 
1519 //---------------------------------------------------------------------
1520 
1521 template<class Val, class SV>
1524 {
1525  BM_ASSERT(csv_);
1526  sv_bi_.add_value_no_null(v);
1527  bvector_type* bv_null = sv_bi_.get_null_bvect();
1528  BM_ASSERT(bv_null);
1529  bv_null->set_bit_no_check(csv_->size_);
1530 
1531  csv_->max_id_++;
1532  csv_->size_++;
1533 }
1534 
1535 //---------------------------------------------------------------------
1536 
1537 template<class Val, class SV>
1539 {
1540  BM_ASSERT(csv_);
1541  csv_->max_id_++;
1542  csv_->size_++;
1543 }
1544 
1545 //---------------------------------------------------------------------
1546 
1547 template<class Val, class SV>
1550 {
1551  BM_ASSERT(csv_);
1552  csv_->max_id_+=count;
1553  csv_->size_+=count;
1554 }
1555 
1556 //---------------------------------------------------------------------
1557 
1558 template<class Val, class SV>
1560 {
1561  sv_bi_.flush();
1562  csv_->in_sync_ = false;
1563 }
1564 
1565 //---------------------------------------------------------------------
1566 //
1567 //---------------------------------------------------------------------
1568 
1569 template<class Val, class BV>
1571 : csv_(0), pos_(bm::id_max), buf_ptr_(0)
1572 {}
1573 
1574 //---------------------------------------------------------------------
1575 
1576 template<class Val, class SV>
1579 : csv_(it.csv_), pos_(it.pos_), buf_ptr_(0)
1580 {}
1581 
1582 //---------------------------------------------------------------------
1583 
1584 template<class Val, class SV>
1587  ) BMNOEXCEPT
1588 : csv_(csv), buf_ptr_(0)
1589 {
1590  BM_ASSERT(csv_);
1591  pos_ = csv_->empty() ? bm::id_max : 0u;
1592 }
1593 
1594 //---------------------------------------------------------------------
1595 
1596 template<class Val, class SV>
1600 : csv_(csv), buf_ptr_(0)
1601 {
1602  BM_ASSERT(csv_);
1603  this->go_to(pos);
1604 }
1605 
1606 //---------------------------------------------------------------------
1607 
1608 template<class Val, class SV>
1610 {
1611  pos_ = (!csv_ || pos >= csv_->size()) ? bm::id_max : pos;
1612  buf_ptr_ = 0;
1613 }
1614 
1615 //---------------------------------------------------------------------
1616 
1617 template<class Val, class SV>
1619 {
1620  if (pos_ == bm::id_max) // nothing to do, we are at the end
1621  return false;
1622  ++pos_;
1623  if (pos_ >= csv_->size())
1624  {
1625  this->invalidate();
1626  return false;
1627  }
1628  if (buf_ptr_)
1629  {
1630  ++buf_ptr_;
1631  if (buf_ptr_ - ((value_type*)vbuffer_.data()) >= n_buf_size)
1632  buf_ptr_ = 0;
1633  }
1634  return true;
1635 }
1636 
1637 //---------------------------------------------------------------------
1638 
1639 template<class Val, class SV>
1642 {
1643  BM_ASSERT(this->valid());
1644  value_type v;
1645 
1646  if (!buf_ptr_)
1647  {
1648  vbuffer_.reserve(n_buf_size * sizeof(value_type));
1649  tbuffer_.reserve(n_buf_size * sizeof(value_type));
1650  buf_ptr_ = (value_type*)(vbuffer_.data());
1651  value_type* tmp_buf_ptr = (value_type*) (tbuffer_.data());
1652 
1653  csv_->decode_buf(buf_ptr_, tmp_buf_ptr, pos_, n_buf_size, true);
1654  }
1655  v = *buf_ptr_;
1656  return v;
1657 }
1658 
1659 //---------------------------------------------------------------------
1660 
1661 template<class Val, class SV>
1663 {
1664  value_type v = value();
1665  if (buf_ptr_)
1666  {
1667  v = *buf_ptr_;
1668  value_type* buf_end = ((value_type*)vbuffer_.data()) + n_buf_size;
1669  while(!v)
1670  {
1671  ++pos_;
1672  if (++buf_ptr_ < buf_end)
1673  v = *buf_ptr_;
1674  else
1675  break;
1676  }
1677  if (pos_ >= csv_->size())
1678  {
1679  pos_ = bm::id_max;
1680  return;
1681  }
1682  if (buf_ptr_ >= buf_end)
1683  buf_ptr_ = 0;
1684  }
1685 }
1686 
1687 //---------------------------------------------------------------------
1688 
1689 template<class Val, class SV>
1691 {
1692  return csv_->is_null(pos_);
1693 }
1694 
1695 
1696 //---------------------------------------------------------------------
1697 
1698 
1699 
1700 } // namespace bm
1701 
1702 #include "bmundef.h"
1703 
1704 
1705 #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:695
bm::rsc_sparse_vector::empty
bool empty() const
return true if vector is empty
Definition: bmsparsevec_compr.h:374
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:587
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:1033
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:1265
bm::rsc_sparse_vector::back_insert_iterator::add
void add(value_type v)
add value to the container
Definition: bmsparsevec_compr.h:1522
bm::bvector::rs_index_type
rs_index< allocator_type > rs_index_type
Definition: bm.h:845
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:1310
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:1001
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:1166
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:745
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:1088
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:689
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:1609
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:744
bm::rsc_sparse_vector::clear
void clear() BMNOEXCEPT
resize to zero, free memory
Definition: bmsparsevec_compr.h:1256
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:664
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:514
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:1538
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:1146
bm::rsc_sparse_vector::operator[]
value_type operator[](size_type idx) const
get specified element without bounds checking
Definition: bmsparsevec_compr.h:387
bm::rsc_sparse_vector::back_insert_iterator::~back_insert_iterator
~back_insert_iterator()
Definition: bmsparsevec_compr.h:1514
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:751
bm::rsc_sparse_vector::effective_vector_max
size_type effective_vector_max() const BMNOEXCEPT
Always 1 (non-matrix type)
Definition: bmsparsevec_compr.h:715
bm::rsc_sparse_vector::back_insert_iterator::operator++
back_insert_iterator & operator++()
noop
Definition: bmsparsevec_compr.h:264
bm::rsc_sparse_vector::merge_not_null
void merge_not_null(rsc_sparse_vector< Val, SV > &csv)
merge two vectors (argument gets destroyed) It is important that both vectors have the same NULL vect...
Definition: bmsparsevec_compr.h:1480
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:1570
bm::rsc_sparse_vector::const_iterator::value
value_type value() const
Get current position (value)
Definition: bmsparsevec_compr.h:1641
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:911
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:1662
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:710
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:669
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:833
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:720
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:1690
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:1229
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:1367
bvector_type
bm::bvector bvector_type
Definition: xsample07a.cpp:93
bm::rsc_sparse_vector::remap_size
size_t remap_size() const BMNOEXCEPT
Definition: bmsparsevec_compr.h:748
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:345
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:1047
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:1292
bm::rsc_sparse_vector::sv_octet_plains
@ sv_octet_plains
Definition: bmsparsevec_compr.h:728
bm::rsc_sparse_vector::back_insert_iterator::flush
void flush()
flush the accumulated buffer
Definition: bmsparsevec_compr.h:1559
bm::rsc_sparse_vector::get_back_inserter
back_insert_iterator get_back_inserter()
Definition: bmsparsevec_compr.h:582
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:659
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:1495
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:861
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:747
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:750
bm::rsc_sparse_vector::octet_plains
octet_plains
Definition: bmsparsevec_compr.h:726
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:821
bm::bvector::enumerator::value
size_type value() const BMNOEXCEPT
Get current position (value)
Definition: bm.h:655
bm::rsc_sparse_vector::is_compressed
static bool is_compressed()
trait if sparse vector is "compressed" (true)
Definition: bmsparsevec_compr.h:527
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:522
bm::rsc_sparse_vector::get_plain
bvector_type_ptr get_plain(unsigned i) BMNOEXCEPT
Definition: bmsparsevec_compr.h:683
bm::rsc_sparse_vector::begin
const_iterator begin() const BMNOEXCEPT
Provide const iterator access to container content
Definition: bmsparsevec_compr.h:569
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:1239
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:1283
bm::rsc_sparse_vector::inc_not_null
void inc_not_null(size_type idx, value_type v)
increment specified element by one, element MUST be NOT NULL Faster than just inc() if element is NUL...
Definition: bmsparsevec_compr.h:982
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:869
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:1618
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::inc
void inc(size_type idx)
increment specified element by one
Definition: bmsparsevec_compr.h:918
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:884
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:680
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:781
bm::rsc_sparse_vector::stored_plains
static unsigned stored_plains()
Number of stored bit-plains (value plains + extra.
Definition: bmsparsevec_compr.h:699
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:900
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:749
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:573
bm::bvector::enumerator::advance
bool advance() BMNOEXCEPT
Definition: bm.h:676
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:1198
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:1448
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:579
bm::rsc_sparse_vector::get_sv
const sparse_vector_type & get_sv() const BMNOEXCEPT
access dense vector
Definition: bmsparsevec_compr.h:705
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:1216