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