BitMagic-C++
bmsparsevec.h
Go to the documentation of this file.
1 #ifndef BMSPARSEVEC_H__INCLUDED__
2 #define BMSPARSEVEC_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.h
22  \brief Sparse constainer sparse_vector<> for integer types using
23  bit-transposition transform
24 */
25 
26 #include <memory.h>
27 
28 #ifndef BM_NO_STL
29 #include <stdexcept>
30 #endif
31 
32 #ifndef BM__H__INCLUDED__
33 // BitMagic utility headers do not include main "bm.h" declaration
34 // #include "bm.h" or "bm64.h" explicitly
35 # error missing include (bm.h or bm64.h)
36 #endif
37 
38 
39 #include "bmtrans.h"
40 #include "bmalgo.h"
41 #include "bmbuffer.h"
42 #include "bmbmatrix.h"
43 #include "bmdef.h"
44 
45 namespace bm
46 {
47 
48 /** \defgroup svector Sparse and compressed vectors
49  Sparse vector for integer types using bit transposition transform
50 
51  @ingroup bmagic
52  */
53 
54 
55 /** \defgroup sv sparse_vector<>
56  Sparse vector for integer types using bit transposition transform
57 
58  @ingroup bmagic
59  */
60 
61 
62 /*!
63  \brief sparse vector with runtime compression using bit transposition method
64 
65  Sparse vector implements variable bit-depth storage model.
66  Initial data is bit-transposed into bit-planes so each element
67  may use less memory than the original native data type prescribes.
68  For example, 32-bit integer may only use 20 bits.
69 
70  Another level of compression is provided by bit-vector (BV template parameter)
71  used for storing bit planes. bvector<> implements varians of on the fly block
72  compression, so if a significant area of a sparse vector uses less bits - it
73  will save memory.
74 
75  Overall it provides variable bit-depth compression, sparse compression in
76  bit-plains.
77 
78  @ingroup sv
79 */
80 template<class Val, class BV>
81 class sparse_vector : public base_sparse_vector<Val, BV, 1>
82 {
83 public:
84  typedef Val value_type;
85  typedef BV bvector_type;
86  typedef bvector_type* bvector_type_ptr;
89  typedef const bvector_type* bvector_type_const_ptr;
90  typedef const value_type& const_reference;
91  typedef typename BV::allocator_type allocator_type;
94  typedef typename allocator_type::allocator_pool_type allocator_pool_type;
97 
98 
99  /*! Statistical information about memory allocation details. */
100  struct statistics : public bv_statistics
101  {};
102 
103  /*! Traits and features used in algorithms to correctly run
104  on a particular type of sparse vector
105  */
106  struct is_remap_support { enum trait { value = false }; };
107  struct is_rsc_support { enum trait { value = false }; };
108 
109  /**
110  Reference class to access elements via common [] operator
111  @ingroup sv
112  */
113  class reference
114  {
115  public:
117  : sv_(sv), idx_(idx)
118  {}
119  operator value_type() const { return sv_.get(idx_); }
121  {
122  sv_.set(idx_, (value_type)ref);
123  return *this;
124  }
125  reference& operator=(value_type val)
126  {
127  sv_.set(idx_, val);
128  return *this;
129  }
130  bool operator==(const reference& ref) const
131  { return bool(*this) == bool(ref); }
132  bool is_null() const { return sv_.is_null(idx_); }
133  private:
135  size_type idx_;
136  };
137 
138 
139  /**
140  Const iterator to traverse the sparse vector.
141 
142  Implementation uses buffer for decoding so, competing changes
143  to the original vector may not match the iterator returned values.
144 
145  This iterator keeps an operational buffer for 8K elements,
146  so memory footprint is not negligable (about 64K for unsigned int)
147 
148  @ingroup sv
149  */
151  {
152  public:
153  friend class sparse_vector;
154 
155 #ifndef BM_NO_STL
156  typedef std::input_iterator_tag iterator_category;
157 #endif
159  typedef sparse_vector_type* sparse_vector_type_ptr;
165  typedef bm::byte_buffer<allocator_type> buffer_type;
166 
167  typedef unsigned difference_type;
168  typedef unsigned* pointer;
169  typedef value_type& reference;
170 
171  public:
172  const_iterator();
173  const_iterator(const sparse_vector_type* sv);
174  const_iterator(const sparse_vector_type* sv, size_type pos);
175  const_iterator(const const_iterator& it);
176 
177  bool operator==(const const_iterator& it) const
178  { return (pos_ == it.pos_) && (sv_ == it.sv_); }
179  bool operator!=(const const_iterator& it) const
180  { return ! operator==(it); }
181  bool operator < (const const_iterator& it) const
182  { return pos_ < it.pos_; }
183  bool operator <= (const const_iterator& it) const
184  { return pos_ <= it.pos_; }
185  bool operator > (const const_iterator& it) const
186  { return pos_ > it.pos_; }
187  bool operator >= (const const_iterator& it) const
188  { return pos_ >= it.pos_; }
189 
190  /// \brief Get current position (value)
191  value_type operator*() const { return this->value(); }
192 
193 
194  /// \brief Advance to the next available value
195  const_iterator& operator++() { this->advance(); return *this; }
196 
197  /// \brief Advance to the next available value
199  { const_iterator tmp(*this);this->advance(); return tmp; }
200 
201 
202  /// \brief Get current position (value)
203  value_type value() const;
204 
205  /// \brief Get NULL status
206  bool is_null() const;
207 
208  /// Returns true if iterator is at a valid position
209  bool valid() const { return pos_ != bm::id_max; }
210 
211  /// Invalidate current iterator
212  void invalidate() { pos_ = bm::id_max; }
213 
214  /// Current position (index) in the vector
215  size_type pos() const { return pos_; }
216 
217  /// re-position to a specified position
218  void go_to(size_type pos);
219 
220  /// advance iterator forward by one
221  void advance();
222 
223  void skip_zero_values();
224  private:
225  enum buf_size_e
226  {
227  n_buf_size = 1024 * 8
228  };
229 
230  private:
231  const sparse_vector_type* sv_; ///!< ptr to parent
232  size_type pos_; ///!< Position
233  mutable buffer_type buffer_; ///!< value buffer
234  mutable value_type* buf_ptr_; ///!< position in the buffer
235  mutable allocator_pool_type pool_;
236  };
237 
238  /**
239  Back insert iterator implements buffered insert, faster than generic
240  access assignment.
241 
242  Limitations for buffered inserter:
243  1. Do not use more than one inserter (into one vector) at the same time
244  2. Use method flush() at the end to send the rest of accumulated buffer
245  flush is happening automatically on destruction, but if flush produces an
246  exception (for whatever reason) it will be an exception in destructor.
247  As such, explicit flush() is safer way to finilize the sparse vector load.
248 
249  @ingroup sv
250  */
252  {
253  public:
254 #ifndef BM_NO_STL
255  typedef std::output_iterator_tag iterator_category;
256 #endif
258  typedef sparse_vector_type* sparse_vector_type_ptr;
264  typedef bm::byte_buffer<allocator_type> buffer_type;
265 
266  typedef void difference_type;
267  typedef void pointer;
268  typedef void reference;
269 
270  public:
272  back_insert_iterator(sparse_vector_type* sv);
274 
276  {
277  BM_ASSERT(bi.empty());
278  this->flush(); sv_ = bi.sv_;
279  return *this;
280  }
281 
283 
284  /** push value to the vector */
285  back_insert_iterator& operator=(value_type v) { this->add(v); return *this; }
286  /** noop */
287  back_insert_iterator& operator*() { return *this; }
288  /** noop */
289  back_insert_iterator& operator++() { return *this; }
290  /** noop */
291  back_insert_iterator& operator++( int ) { return *this; }
292 
293  /** add value to the container*/
294  void add(value_type v);
295 
296  /** add NULL (no-value) to the container */
297  void add_null();
298 
299  /** add a series of consequitve NULLs (no-value) to the container */
300  void add_null(size_type count);
301 
302  /** return true if insertion buffer is empty */
303  bool empty() const;
304 
305  /** flush the accumulated buffer */
306  void flush();
307  protected:
308 
309  /** add value to the buffer without changing the NULL vector
310  @param v - value to push back
311  @return index of added value in the internal buffer
312  @internal
313  */
314  size_type add_value(value_type v);
315 
316  private:
317  enum buf_size_e
318  {
319  n_buf_size = 1024 * 8
320  };
321 
322  private:
323  bm::sparse_vector<Val, BV>* sv_; ///!< pointer on the parent vector
324  bvector_type* bv_null_; ///!< not NULL vector pointer
325  buffer_type buffer_; ///!< value buffer
326  value_type* buf_ptr_; ///!< position in the buffer
327  };
328 
331 
332 public:
333  // ------------------------------------------------------------
334  /*! @name Construction and assignment */
335  ///@{
336 
337  /*!
338  \brief Sparse vector constructor
339 
340  \param null_able - defines if vector supports NULL values flag
341  by default it is OFF, use bm::use_null to enable it
342  \param ap - allocation strategy for underlying bit-vectors
343  Default allocation policy uses BM_BIT setting (fastest access)
344  \param bv_max_size - maximum possible size of underlying bit-vectors
345  Please note, this is NOT size of svector itself, it is dynamic upper limit
346  which should be used very carefully if we surely know the ultimate size
347  \param alloc - allocator for bit-vectors
348 
349  \sa bvector<>
350  \sa bm::bvector<>::allocation_policy
351  \sa bm::startegy
352  */
354  allocation_policy_type ap = allocation_policy_type(),
355  size_type bv_max_size = bm::id_max,
356  const allocator_type& alloc = allocator_type());
357 
358  /*! copy-ctor */
360 
361  /*! copy assignmment operator */
363  {
364  if (this != &sv)
366  return *this;
367  }
368 
369 #ifndef BM_NO_CXX11
370  /*! move-ctor */
372 
373 
374  /*! move assignmment operator */
376  {
377  if (this != &sv)
378  {
379  clear();
380  swap(sv);
381  }
382  return *this;
383  }
384 #endif
385 
387  ///@}
388 
389 
390  // ------------------------------------------------------------
391  /*! @name Element access */
392  ///@{
393 
394  /** \brief Operator to get write access to an element */
395  reference operator[](size_type idx) { return reference(*this, idx); }
396 
397  /*!
398  \brief get specified element without bounds checking
399  \param idx - element index
400  \return value of the element
401  */
402  value_type operator[](size_type idx) const { return this->get(idx); }
403 
404  /*!
405  \brief access specified element with bounds checking
406  \param idx - element index
407  \return value of the element
408  */
409  value_type at(size_type idx) const;
410  /*!
411  \brief get specified element without bounds checking
412  \param idx - element index
413  \return value of the element
414  */
415  value_type get(size_type idx) const;
416 
417  /*!
418  \brief set specified element with bounds checking and automatic resize
419  \param idx - element index
420  \param v - element value
421  */
422  void set(size_type idx, value_type v);
423 
424  /*!
425  \brief increment specified element by one
426  \param idx - element index
427  */
428  void inc(size_type idx);
429 
430  /*!
431  \brief push value back into vector
432  \param v - element value
433  */
434  void push_back(value_type v);
435 
436  /*!
437  \brief push back specified amount of NULL values
438  \param count - number of NULLs to push back
439  */
440  void push_back_null(size_type count);
441 
442  /*!
443  \brief insert specified element into container
444  \param idx - element index
445  \param v - element value
446  */
447  void insert(size_type idx, value_type v);
448 
449  /*!
450  \brief erase specified element from container
451  \param idx - element index
452  */
453  void erase(size_type idx);
454 
455  /*!
456  \brief clear specified element with bounds checking and automatic resize
457  \param idx - element index
458  \param set_null - if true the value receives NULL (unassigned) value
459  */
460  void clear(size_type idx, bool set_null = false);
461 
462  ///@}
463 
464  // ------------------------------------------------------------
465  /*! @name Iterator access */
466  //@{
467 
468  /** Provide const iterator access to container content */
469  const_iterator begin() const;
470 
471  /** Provide const iterator access to the end */
472  const_iterator end() const { return const_iterator(this, bm::id_max); }
473 
474  /** Get const_itertor re-positioned to specific element
475  @param idx - position in the sparse vector
476  */
477  const_iterator get_const_iterator(size_type idx) const { return const_iterator(this, idx); }
478 
479  /** Provide back insert iterator
480  Back insert iterator implements buffered insertion,
481  which is faster, than random access or push_back
482  */
484  ///@}
485 
486 
487  // ------------------------------------------------------------
488  /*! @name Various traits */
489  //@{
490 
491  /** \brief set specified element to unassigned value (NULL)
492  \param idx - element index
493  */
494  void set_null(size_type idx);
495 
496  /** \brief trait if sparse vector is "compressed" (false)
497  */
498  static
499  bool is_compressed() { return false; }
500 
501  ///@}
502 
503 
504  // ------------------------------------------------------------
505  /*! @name Loading of sparse vector from C-style array */
506  //@{
507 
508  /*!
509  \brief Import list of elements from a C-style array
510  \param arr - source array
511  \param arr_size - source size
512  \param offset - target index in the sparse vector
513  */
514  void import(const value_type* arr, size_type arr_size, size_type offset = 0);
515 
516  /*!
517  \brief Import list of elements from a C-style array (pushed back)
518  \param arr - source array
519  \param srr_size - source size
520  */
521  void import_back(const value_type* arr, size_type arr_size);
522  ///@}
523 
524  // ------------------------------------------------------------
525  /*! @name Export content to C-style array */
526  ///@{
527 
528  /*!
529  \brief Bulk export list of elements to a C-style array
530 
531  For efficiency, this is left as a low level function,
532  it does not do any bounds checking on the target array, it will
533  override memory and crash if you are not careful with allocation
534  and request size.
535 
536  \param arr - dest array
537  \param idx_from - index in the sparse vector to export from
538  \param dec_size - decoding size (array allocation should match)
539  \param zero_mem - set to false if target array is pre-initialized
540  with 0s to avoid performance penalty
541 
542  \return number of actually exported elements (can be less than requested)
543 
544  \sa gather
545  */
546  size_type decode(value_type* arr,
547  size_type idx_from,
548  size_type dec_size,
549  bool zero_mem = true) const;
550 
551 
552  /*!
553  \brief Gather elements to a C-style array
554 
555  Gather collects values from different locations, for best
556  performance feed it with sorted list of indexes.
557 
558  Faster than one-by-one random access.
559 
560  For efficiency, this is left as a low level function,
561  it does not do any bounds checking on the target array, it will
562  override memory and crash if you are not careful with allocation
563  and request size.
564 
565  \param arr - dest array
566  \param idx - index list to gather elements
567  \param size - decoding index list size (array allocation should match)
568  \param sorted_idx - sort order directive for the idx array
569  (BM_UNSORTED, BM_SORTED, BM_UNKNOWN)
570  Sort order affects both performance and correctness(!), use BM_UNKNOWN
571  if not sure.
572 
573  \return number of actually exported elements (can be less than requested)
574 
575  \sa decode
576  */
577  size_type gather(value_type* arr,
578  const size_type* idx,
579  size_type size,
580  bm::sort_order sorted_idx) const;
581  ///@}
582 
583  /*! \brief content exchange
584  */
586 
587  // ------------------------------------------------------------
588  /*! @name Clear */
589  ///@{
590 
591  /*! \brief resize to zero, free memory */
592  void clear() BMNOEXEPT;
593 
594  /*!
595  \brief clear range (assign bit 0 for all plains)
596  \param left - interval start
597  \param right - interval end (closed interval)
598  \param set_null - set cleared values to unassigned (NULL)
599  */
600  sparse_vector<Val, BV>& clear_range(size_type left,
601  size_type right,
602  bool set_null = false);
603 
604  ///@}
605 
606  // ------------------------------------------------------------
607  /*! @name Size, etc */
608  ///@{
609 
610  /*! \brief return size of the vector
611  \return size of sparse vector
612  */
613  size_type size() const { return this->size_; }
614 
615  /*! \brief return true if vector is empty
616  \return true if empty
617  */
618  bool empty() const { return (size() == 0); }
619 
620  /*! \brief resize vector
621  \param sz - new size
622  */
623  void resize(size_type sz) { parent_type::resize(sz); }
624  ///@}
625 
626  // ------------------------------------------------------------
627  /*! @name Comparison */
628  ///@{
629 
630  /*!
631  \brief check if another sparse vector has the same content and size
632 
633  \param sv - sparse vector for comparison
634  \param null_able - flag to consider NULL vector in comparison (default)
635  or compare only value content plains
636 
637  \return true, if it is the same
638  */
639  bool equal(const sparse_vector<Val, BV>& sv,
640  bm::null_support null_able = bm::use_null) const;
641  ///@}
642 
643  // ------------------------------------------------------------
644  /*! @name Element comparison */
645  ///@{
646 
647  /**
648  \brief Compare vector element with argument
649 
650  \param idx - vactor element index
651  \param val - argument to compare with
652 
653  \return 0 - equal, < 0 - vect[i] < str, >0 otherwise
654  */
655  int compare(size_type idx, const value_type val) const;
656 
657  ///@}
658 
659  // ------------------------------------------------------------
660  /*! @name Memory optimization */
661  ///@{
662 
663  /*!
664  \brief run memory optimization for all vector plains
665  \param temp_block - pre-allocated memory block to avoid unnecessary re-allocs
666  \param opt_mode - requested compression depth
667  \param stat - memory allocation statistics after optimization
668  */
669  void optimize(bm::word_t* temp_block = 0,
671  typename sparse_vector<Val, BV>::statistics* stat = 0);
672  /*!
673  \brief Optimize sizes of GAP blocks
674 
675  This method runs an analysis to find optimal GAP levels for all bit plains
676  of the vector.
677  */
678  void optimize_gap_size();
679 
680  /*!
681  @brief Calculates memory statistics.
682 
683  Function fills statistics structure containing information about how
684  this vector uses memory and estimation of max. amount of memory
685  bvector needs to serialize itself.
686 
687  @param st - pointer on statistics structure to be filled in.
688 
689  @sa statistics
690  */
691  void calc_stat(struct sparse_vector<Val, BV>::statistics* st) const;
692  ///@}
693 
694  // ------------------------------------------------------------
695  /*! @name Merge, split, partition data */
696  ///@{
697 
698  /*!
699  \brief join all with another sparse vector using OR operation
700  \param sv - argument vector to join with
701  \return slf reference
702  @sa merge
703  */
705 
706  /*!
707  \brief merge with another sparse vector using OR operation
708  Merge is different from join(), because it borrows data from the source
709  vector, so it gets modified.
710 
711  \param sv - [in, out]argument vector to join with (vector mutates)
712 
713  \return slf reference
714  @sa join
715  */
717 
718 
719  /**
720  @brief copy range of values from another sparse vector
721 
722  Copy [left..right] values from the source vector,
723  clear everything outside the range.
724 
725  \param sv - source vector
726  \param left - index from in losed diapason of [left..right]
727  \param right - index to in losed diapason of [left..right]
728  */
729  void copy_range(const sparse_vector<Val, BV>& sv,
730  size_type left, size_type right);
731 
732  /**
733  @brief Apply value filter, defined by mask vector
734 
735  All bit-plains are ANDed against the filter mask.
736  */
737  void filter(const bvector_type& bv_mask);
738 
739  ///@}
740 
741 
742  // ------------------------------------------------------------
743  /*! @name Access to internals */
744  ///@{
745 
746 
747  /*! \brief syncronize internal structures */
748  void sync(bool /*force*/) {}
749 
750 
751  /*!
752  \brief Bulk export list of elements to a C-style array
753 
754  Use of all extract() methods is restricted.
755  Please consider decode() for the same purpose.
756 
757  \param arr - dest array
758  \param size - dest size
759  \param offset - target index in the sparse vector to export from
760  \param zero_mem - set to false if target array is pre-initialized
761  with 0s to avoid performance penalty
762 
763  \return number of exported elements
764 
765  \sa decode
766 
767  @internal
768  */
769  size_type extract(value_type* arr,
770  size_type size,
771  size_type offset = 0,
772  bool zero_mem = true,
773  allocator_pool_type* pool_ptr = 0) const;
774 
775  /** \brief extract small window without use of masking vector
776  \sa decode
777  @internal
778  */
779  size_type extract_range(value_type* arr,
780  size_type size,
781  size_type offset,
782  bool zero_mem = true) const;
783 
784  /** \brief extract medium window without use of masking vector
785  \sa decode
786  @internal
787  */
788  size_type extract_plains(value_type* arr,
789  size_type size,
790  size_type offset,
791  bool zero_mem = true) const;
792 
793  /** \brief address translation for this type of container
794  \internal
795  */
796  static
797  size_type translate_address(size_type i) { return i; }
798 
799  /**
800  \brief throw range error
801  \internal
802  */
803  static
804  void throw_range_error(const char* err_msg);
805 
806  /**
807  \brief throw bad alloc
808  \internal
809  */
810  static
811  void throw_bad_alloc();
812 
813 
814  /**
815  \brief find position of compressed element by its rank
816  */
817  static
818  bool find_rank(size_type rank, size_type& pos);
819 
820  /**
821  \brief size of sparse vector (may be different for RSC)
822  */
823  size_type effective_size() const { return size(); }
824 
825  /**
826  \brief Always 1 (non-matrix type)
827  */
828  size_type effective_vector_max() const { return 1; }
829 
830  ///@}
831 
832  /// Set allocator pool for local (non-threaded)
833  /// memory cyclic(lots of alloc-free ops) opertations
834  ///
835  void set_allocator_pool(allocator_pool_type* pool_ptr);
836 
837 protected:
839  {
841  };
842 
843 
844  /*! \brief set value without checking boundaries */
845  void set_value(size_type idx, value_type v);
846 
847  /*! \brief set value without checking boundaries or support of NULL */
848  void set_value_no_null(size_type idx, value_type v);
849 
850  /*! \brief push value back into vector without NULL semantics */
851  void push_back_no_null(value_type v);
852 
853  /*! \brief insert value without checking boundaries */
854  void insert_value(size_type idx, value_type v);
855  /*! \brief insert value without checking boundaries or support of NULL */
856  void insert_value_no_null(size_type idx, value_type v);
857 
858  void resize_internal(size_type sz) { resize(sz); }
859  size_type size_internal() const { return size(); }
860 
861  bool is_remap() const { return false; }
862  size_t remap_size() const { return 0; }
863  const unsigned char* get_remap_buffer() const { return 0; }
864  unsigned char* init_remap_buffer() { return 0; }
865  void set_remap() { }
866 
867 protected:
868  template<class V, class SV> friend class rsc_sparse_vector;
869  template<class SVect> friend class sparse_vector_scanner;
870  template<class SVect> friend class sparse_vector_serializer;
871  template<class SVect> friend class sparse_vector_deserializer;
872 
873 };
874 
875 
876 //---------------------------------------------------------------------
877 //---------------------------------------------------------------------
878 
879 
880 template<class Val, class BV>
882  bm::null_support null_able,
883  allocation_policy_type ap,
884  size_type bv_max_size,
885  const allocator_type& alloc)
886 : parent_type(null_able, ap, bv_max_size, alloc)
887 {}
888 
889 //---------------------------------------------------------------------
890 
891 template<class Val, class BV>
893 : parent_type(sv)
894 {}
895 
896 //---------------------------------------------------------------------
897 #ifndef BM_NO_CXX11
898 
899 template<class Val, class BV>
901 {
902  parent_type::swap(sv);
903 }
904 
905 #endif
906 
907 
908 //---------------------------------------------------------------------
909 
910 template<class Val, class BV>
912 {}
913 
914 //---------------------------------------------------------------------
915 
916 template<class Val, class BV>
918 {
919  parent_type::swap(sv);
920 }
921 
922 //---------------------------------------------------------------------
923 
924 template<class Val, class BV>
926 {
927 #ifndef BM_NO_STL
928  throw std::range_error(err_msg);
929 #else
930  BM_ASSERT_THROW(false, BM_ERR_RANGE);
931 #endif
932 }
933 
934 //---------------------------------------------------------------------
935 
936 template<class Val, class BV>
938 {
939  BV::throw_bad_alloc();
940 }
941 
942 //---------------------------------------------------------------------
943 
944 template<class Val, class BV>
946 {
947  clear(idx, true);
948 }
949 
950 //---------------------------------------------------------------------
951 
952 template<class Val, class BV>
953 void sparse_vector<Val, BV>::import(const value_type* arr,
954  size_type arr_size,
955  size_type offset)
956 {
957  unsigned char b_list[sizeof(Val)*8];
958  unsigned row_len[sizeof(Val)*8] = {0, };
959 
960  const unsigned transpose_window = 256;
962 
963  if (arr_size == 0)
964  throw_range_error("sparse_vector range error (import size 0)");
965 
966  if (offset < this->size_) // in case it touches existing elements
967  {
968  // clear all plains in the range to provide corrrect import of 0 values
969  this->clear_range(offset, offset + arr_size - 1);
970  }
971 
972  // transposition algorithm uses bitscan to find index bits and store it
973  // in temporary matrix (list for each bit plain), matrix here works
974  // when array gets to big - the list gets loaded into bit-vector using
975  // bulk load algorithm, which is faster than single bit access
976  //
977 
978  size_type i;
979  for (i = 0; i < arr_size; ++i)
980  {
981  unsigned bcnt = bm::bitscan(arr[i], b_list);
982  const size_type bit_idx = i + offset;
983 
984  for (unsigned j = 0; j < bcnt; ++j)
985  {
986  unsigned p = b_list[j];
987  unsigned rl = row_len[p];
988  tm.row(p)[rl] = bit_idx;
989  row_len[p] = ++rl;
990 
991  if (rl == transpose_window)
992  {
993  bvector_type* bv = this->get_plain(p);
994  const size_type* r = tm.row(p);
995  bv->set(r, rl, BM_SORTED);
996  row_len[p] = 0;
997  tm.row(p)[0] = 0;
998  }
999  } // for j
1000  } // for i
1001 
1002  // process incomplete transposition lines
1003  //
1004  for (unsigned k = 0; k < tm.rows(); ++k)
1005  {
1006  unsigned rl = row_len[k];
1007  if (rl)
1008  {
1009  bvector_type* bv = this->get_plain(k);
1010  const size_type* r = tm.row(k);
1011  bv->set(r, rl, BM_SORTED);
1012  }
1013  } // for k
1014 
1015 
1016  if (i + offset > this->size_)
1017  this->size_ = i + offset;
1018 
1019  bvector_type* bv_null = this->get_null_bvect();
1020  if (bv_null) // configured to support NULL assignments
1021  {
1022  bv_null->set_range(offset, offset + arr_size - 1);
1023  }
1024 }
1025 
1026 //---------------------------------------------------------------------
1027 
1028 template<class Val, class BV>
1029 void sparse_vector<Val, BV>::import_back(const value_type* arr,
1030  size_type arr_size)
1031 {
1032  this->import(arr, arr_size, this->size());
1033 }
1034 
1035 //---------------------------------------------------------------------
1036 
1037 template<class Val, class BV>
1040  size_type idx_from,
1041  size_type dec_size,
1042  bool zero_mem) const
1043 {
1044  if (dec_size < 32)
1045  {
1046  return extract_range(arr, dec_size, idx_from, zero_mem);
1047  }
1048  return extract_plains(arr, dec_size, idx_from, zero_mem);
1049  // TODO: write proper extract() based on for_each_range() and a visitor
1050  /*
1051  if (dec_size < 1024)
1052  {
1053  return extract_plains(arr, dec_size, idx_from, zero_mem);
1054  }
1055  return extract(arr, dec_size, idx_from, zero_mem);
1056  */
1057 }
1058 
1059 //---------------------------------------------------------------------
1060 
1061 template<class Val, class BV>
1064  const size_type* idx,
1065  size_type size,
1066  bm::sort_order sorted_idx) const
1067 {
1068  BM_ASSERT(arr);
1069  BM_ASSERT(idx);
1070  BM_ASSERT(size);
1071 
1072  if (size == 1) // corner case: get 1 value
1073  {
1074  arr[0] = this->get(idx[0]);
1075  return size;
1076  }
1077  ::memset(arr, 0, sizeof(value_type)*size);
1078 
1079  for (size_type i = 0; i < size;)
1080  {
1081  bool sorted_block = true;
1082 
1083  // look ahead for the depth of the same block
1084  // (speculate more than one index lookup per block)
1085  //
1086  block_idx_type nb = (idx[i] >> bm::set_block_shift);
1087  size_type r = i;
1088 
1089  switch (sorted_idx)
1090  {
1091  case BM_UNKNOWN:
1092  {
1093  size_type idx_prev = idx[r];
1094  for (; (r < size) && (nb == (idx[r] >> bm::set_block_shift)); ++r)
1095  {
1096  sorted_block = !(idx[r] < idx_prev); // sorted check
1097  idx_prev = idx[r];
1098  }
1099  }
1100  break;
1101  case BM_UNSORTED:
1102  sorted_block = false;
1103  for (; r < size; ++r)
1104  {
1105  block_idx_type nb_next = (idx[r] >> bm::set_block_shift);
1106  if (nb != nb_next)
1107  break;
1108  } // for r
1109  break;
1110  // no break(!) intentional fall through
1111  case BM_SORTED:
1112  #ifdef BM64ADDR
1113  r = bm::idx_arr_block_lookup_u64(idx, size, nb, r);
1114  #else
1115  r = bm::idx_arr_block_lookup_u32(idx, size, nb, r);
1116  #endif
1117  break;
1118  case BM_SORTED_UNIFORM:
1119  r = size;
1120  break;
1121  default:
1122  BM_ASSERT(0);
1123  } // switch
1124 
1125  // single element hit, use plain random access
1126  if (r == i+1)
1127  {
1128  arr[i] = this->get(idx[i]);
1129  ++i;
1130  continue;
1131  }
1132 
1133  // process block co-located elements at ones for best (CPU cache opt)
1134  //
1135  unsigned i0 = unsigned(nb >> bm::set_array_shift); // top block address
1136  unsigned j0 = unsigned(nb & bm::set_array_mask); // address in sub-block
1137 
1138  unsigned eff_plains = this->effective_plains(); // TODO: get real effective plains for [i,j]
1139  for (unsigned j = 0; j < eff_plains; ++j)
1140  {
1141  const bm::word_t* blk = this->bmatr_.get_block(j, i0, j0);
1142  if (!blk)
1143  continue;
1144  value_type vm;
1145  const value_type mask1 = 1;
1146 
1147  if (blk == FULL_BLOCK_FAKE_ADDR)
1148  {
1149  vm = (mask1 << j);
1150  for (size_type k = i; k < r; ++k)
1151  arr[k] |= vm;
1152  continue;
1153  }
1154  if (BM_IS_GAP(blk))
1155  {
1156  const bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
1157  unsigned is_set;
1158 
1159  if (sorted_block) // b-search hybrid with scan lookup
1160  {
1161  for (size_type k = i; k < r; )
1162  {
1163  unsigned nbit = unsigned(idx[k] & bm::set_block_mask);
1164 
1165  unsigned gidx = bm::gap_bfind(gap_blk, nbit, &is_set);
1166  unsigned gap_value = gap_blk[gidx];
1167  if (is_set)
1168  {
1169  arr[k] |= vm = (mask1 << j);
1170  for (++k; k < r; ++k) // speculative look-up
1171  {
1172  if (unsigned(idx[k] & bm::set_block_mask) <= gap_value)
1173  arr[k] |= vm;
1174  else
1175  break;
1176  }
1177  }
1178  else // 0 GAP - skip. not set
1179  {
1180  for (++k;
1181  (k < r) &&
1182  (unsigned(idx[k] & bm::set_block_mask) <= gap_value);
1183  ++k) {}
1184  }
1185  } // for k
1186  }
1187  else // unsorted block gather request: b-search lookup
1188  {
1189  for (size_type k = i; k < r; ++k)
1190  {
1191  unsigned nbit = unsigned(idx[k] & bm::set_block_mask);
1192  is_set = bm::gap_test_unr(gap_blk, nbit);
1193  arr[k] |= (value_type(bool(is_set)) << j);
1194  } // for k
1195  }
1196  continue;
1197  }
1198  bm::bit_block_gather_scatter(arr, blk, idx, r, i, j);
1199  } // for (each plain)
1200 
1201  i = r;
1202 
1203  } // for i
1204 
1205  return size;
1206 }
1207 
1208 //---------------------------------------------------------------------
1209 
1210 template<class Val, class BV>
1213  size_type size,
1214  size_type offset,
1215  bool zero_mem) const
1216 {
1217  if (size == 0)
1218  return 0;
1219  if (zero_mem)
1220  ::memset(arr, 0, sizeof(value_type)*size);
1221 
1222  size_type start = offset;
1223  size_type end = start + size;
1224  if (end > this->size_)
1225  {
1226  end = this->size_;
1227  }
1228 
1229  // calculate logical block coordinates and masks
1230  //
1231  block_idx_type nb = (start >> bm::set_block_shift);
1232  unsigned i0 = unsigned(nb >> bm::set_array_shift); // top block address
1233  unsigned j0 = unsigned(nb & bm::set_array_mask); // address in sub-block
1234  unsigned nbit = unsigned(start & bm::set_block_mask);
1235  unsigned nword = unsigned(nbit >> bm::set_word_shift);
1236  unsigned mask0 = 1u << (nbit & bm::set_word_mask);
1237  const bm::word_t* blk = 0;
1238  unsigned is_set;
1239 
1240  for (unsigned j = 0; j < sizeof(Val)*8; ++j)
1241  {
1242  blk = this->bmatr_.get_block(j, i0, j0);
1243  bool is_gap = BM_IS_GAP(blk);
1244 
1245  for (size_type k = start; k < end; ++k)
1246  {
1247  block_idx_type nb1 = (k >> bm::set_block_shift);
1248  if (nb1 != nb) // block switch boundaries
1249  {
1250  nb = nb1;
1251  i0 = unsigned(nb >> bm::set_array_shift);
1252  j0 = unsigned(nb & bm::set_array_mask);
1253  blk = this->bmatr_.get_block(j, i0, j0);
1254  is_gap = BM_IS_GAP(blk);
1255  }
1256  if (!blk)
1257  continue;
1258  nbit = unsigned(k & bm::set_block_mask);
1259  if (is_gap)
1260  {
1261  is_set = bm::gap_test_unr(BMGAP_PTR(blk), nbit);
1262  }
1263  else
1264  {
1265  if (blk == FULL_BLOCK_FAKE_ADDR)
1266  {
1267  is_set = 1;
1268  }
1269  else
1270  {
1271  BM_ASSERT(!IS_FULL_BLOCK(blk));
1272  nword = unsigned(nbit >> bm::set_word_shift);
1273  mask0 = 1u << (nbit & bm::set_word_mask);
1274  is_set = (blk[nword] & mask0);
1275  }
1276  }
1277  size_type idx = k - offset;
1278  value_type vm = (bool) is_set;
1279  vm <<= j;
1280  arr[idx] |= vm;
1281 
1282  } // for k
1283 
1284  } // for j
1285  return 0;
1286 }
1287 
1288 //---------------------------------------------------------------------
1289 
1290 template<class Val, class BV>
1293  size_type size,
1294  size_type offset,
1295  bool zero_mem) const
1296 {
1297  if (size == 0)
1298  return 0;
1299 
1300  if (zero_mem)
1301  ::memset(arr, 0, sizeof(value_type)*size);
1302 
1303  size_type start = offset;
1304  size_type end = start + size;
1305  if (end > this->size_)
1306  {
1307  end = this->size_;
1308  }
1309 
1310  for (size_type i = 0; i < parent_type::value_bits(); ++i)
1311  {
1312  const bvector_type* bv = this->bmatr_.get_row(i);
1313  if (!bv)
1314  continue;
1315 
1316  value_type mask = 1;
1317  mask <<= i;
1318  typename BV::enumerator en(bv, offset);
1319  for (;en.valid(); ++en)
1320  {
1321  size_type idx = *en - offset;
1322  if (idx >= size)
1323  break;
1324  arr[idx] |= mask;
1325  } // for
1326 
1327  } // for i
1328 
1329  return 0;
1330 }
1331 
1332 
1333 //---------------------------------------------------------------------
1334 
1335 template<class Val, class BV>
1338  size_type size,
1339  size_type offset,
1340  bool zero_mem,
1341  allocator_pool_type* pool_ptr) const
1342 {
1343  /// Decoder functor
1344  /// @internal
1345  ///
1346  struct sv_decode_visitor_func
1347  {
1348  sv_decode_visitor_func(value_type* varr,
1349  value_type mask,
1350  size_type off)
1351  : arr_(varr), mask_(mask), off_(off)
1352  {}
1353 
1354  void add_bits(size_type arr_offset, const unsigned char* bits, unsigned bits_size)
1355  {
1356  size_type idx_base = arr_offset - off_;
1357  const value_type m = mask_;
1358  unsigned i = 0;
1359  for (; i < bits_size; ++i)
1360  arr_[idx_base + bits[i]] |= m;
1361  }
1362 
1363  void add_range(size_type arr_offset, unsigned sz)
1364  {
1365  size_type idx_base = arr_offset - off_;
1366  const value_type m = mask_;
1367  for (unsigned i = 0; i < sz; ++i)
1368  arr_[i + idx_base] |= m;
1369  }
1370  value_type* arr_;
1371  value_type mask_;
1372  size_type off_;
1373  };
1374 
1375 
1376  if (size == 0)
1377  return 0;
1378 
1379  if (zero_mem)
1380  ::memset(arr, 0, sizeof(value_type)*size);
1381 
1382  size_type start = offset;
1383  size_type end = start + size;
1384  if (end > this->size_)
1385  {
1386  end = this->size_;
1387  }
1388 
1389  bool masked_scan = !(offset == 0 && size == this->size());
1390  if (masked_scan) // use temp vector to decompress the area
1391  {
1392  bvector_type bv_mask;
1393  bv_mask.set_allocator_pool(pool_ptr);
1394 
1395  for (size_type i = 0; i < parent_type::value_bits(); ++i)
1396  {
1397  const bvector_type* bv = this->bmatr_.get_row(i);
1398  if (bv)
1399  {
1400  bv_mask.copy_range(*bv, offset, end - 1);
1401  sv_decode_visitor_func func(arr, (value_type(1) << i), offset);
1402  bm::for_each_bit(bv_mask, func);
1403  }
1404  } // for i
1405  }
1406  else
1407  {
1408  for (size_type i = 0; i < parent_type::value_bits(); ++i)
1409  {
1410  const bvector_type* bv = this->bmatr_.get_row(i);
1411  if (bv)
1412  {
1413  sv_decode_visitor_func func(arr, (value_type(1) << i), 0);
1414  bm::for_each_bit(*bv, func);
1415  }
1416  } // for i
1417  }
1418 
1419  return end - start;
1420 }
1421 
1422 //---------------------------------------------------------------------
1423 
1424 template<class Val, class BV>
1427 {
1428  if (idx >= this->size_)
1429  throw_range_error("sparse vector range error");
1430  return this->get(idx);
1431 }
1432 
1433 //---------------------------------------------------------------------
1434 
1435 template<class Val, class BV>
1438 {
1439  BM_ASSERT(i < bm::id_max);
1440  BM_ASSERT(i < size());
1441 
1442  value_type v = 0;
1443  unsigned eff_plains = this->effective_plains();
1444  for (unsigned j = 0; j < eff_plains; j+=4)
1445  {
1446  bool b = this->bmatr_.test_4rows(j);
1447  if (b)
1448  {
1449  value_type vm = this->bmatr_.get_half_octet(i, j);
1450  v |= vm << j;
1451  }
1452  } // for j
1453  return v;
1454 }
1455 
1456 
1457 //---------------------------------------------------------------------
1458 
1459 template<class Val, class BV>
1460 void sparse_vector<Val, BV>::set(size_type idx, value_type v)
1461 {
1462  if (idx >= size())
1463  {
1464  this->size_ = idx+1;
1465  }
1466  set_value(idx, v);
1467 }
1468 
1469 //---------------------------------------------------------------------
1470 
1471 template<class Val, class BV>
1472 void sparse_vector<Val, BV>::clear(size_type idx, bool set_null)
1473 {
1474  if (idx >= size())
1475  this->size_ = idx+1;
1476 
1477  set_value(idx, (value_type)0);
1478  if (set_null)
1479  {
1480  bvector_type* bv_null = this->get_null_bvect();
1481  if (bv_null)
1482  bv_null->set(idx, false);
1483  }
1484 }
1485 
1486 //---------------------------------------------------------------------
1487 
1488 template<class Val, class BV>
1490 {
1491  set_value(this->size_, v);
1492  ++(this->size_);
1493 }
1494 
1495 //---------------------------------------------------------------------
1496 
1497 template<class Val, class BV>
1499 {
1500  BM_ASSERT(count);
1501  BM_ASSERT(bm::id_max - count > this->size_);
1502  BM_ASSERT(this->is_nullable());
1503 
1504  this->size_ += count;
1505 }
1506 
1507 
1508 //---------------------------------------------------------------------
1509 
1510 template<class Val, class BV>
1511 void sparse_vector<Val, BV>::insert(size_type idx, value_type v)
1512 {
1513  if (idx >= size())
1514  {
1515  this->size_ = idx+1;
1516  set_value(idx, v);
1517  return;
1518  }
1519  insert_value(idx, v);
1520 }
1521 
1522 //---------------------------------------------------------------------
1523 
1524 template<class Val, class BV>
1525 void sparse_vector<Val, BV>::insert_value(size_type idx, value_type v)
1526 {
1527  insert_value_no_null(idx, v);
1528  this->insert_null(idx, true);
1529 }
1530 
1531 //---------------------------------------------------------------------
1532 
1533 template<class Val, class BV>
1534 void sparse_vector<Val, BV>::insert_value_no_null(size_type idx, value_type v)
1535 {
1536  unsigned bsr = v ? bm::bit_scan_reverse(v) : 0u;
1537  value_type mask = 1u;
1538  unsigned i = 0;
1539  for (; i <= bsr; ++i)
1540  {
1541  if (v & mask)
1542  {
1543  bvector_type* bv = this->get_plain(i);
1544  bv->insert(idx, true);
1545  }
1546  else
1547  {
1548  bvector_type_ptr bv = this->bmatr_.get_row(i);
1549  if (bv)
1550  bv->insert(idx, false);
1551  }
1552  mask <<= 1;
1553  } // for i
1554  // insert 0 into all other existing plains
1555  unsigned eff_plains = this->effective_plains();
1556  for (; i < eff_plains; ++i)
1557  {
1558  bvector_type* bv = this->bmatr_.get_row(i);
1559  if (bv)
1560  bv->insert(idx, false);
1561  } // for i
1562 
1563  this->size_++;
1564 }
1565 
1566 //---------------------------------------------------------------------
1567 
1568 template<class Val, class BV>
1570 {
1571  BM_ASSERT(idx < this->size_);
1572  if (idx >= this->size_)
1573  return;
1574  this->erase_column(idx);
1575  this->size_--;
1576 }
1577 
1578 
1579 //---------------------------------------------------------------------
1580 
1581 template<class Val, class BV>
1583 {
1584  set_value_no_null(this->size_, v);
1585  ++(this->size_);
1586 }
1587 
1588 //---------------------------------------------------------------------
1589 
1590 template<class Val, class BV>
1591 void sparse_vector<Val, BV>::set_value(size_type idx, value_type v)
1592 {
1593  set_value_no_null(idx, v);
1594  bvector_type* bv_null = this->get_null_bvect();
1595  if (bv_null)
1596  bv_null->set_bit_no_check(idx);
1597 }
1598 
1599 //---------------------------------------------------------------------
1600 
1601 template<class Val, class BV>
1602 void sparse_vector<Val, BV>::set_value_no_null(size_type idx, value_type v)
1603 {
1604  // calculate logical block coordinates and masks
1605  //
1606  block_idx_type nb = (idx >> bm::set_block_shift);
1607  unsigned i0 = unsigned(nb >> bm::set_array_shift); // top block address
1608  unsigned j0 = unsigned(nb & bm::set_array_mask); // address in sub-block
1609 
1610  // clear the plains where needed
1611  unsigned eff_plains = this->effective_plains();
1612  unsigned bsr = v ? bm::bit_scan_reverse(v) : 0u;
1613 
1614  for (unsigned i = bsr; i < eff_plains; ++i)
1615  {
1616  const bm::word_t* blk = this->bmatr_.get_block(i, i0, j0);
1617  if (blk)
1618  {
1619  bvector_type* bv = this->bmatr_.get_row(i);
1620  if (bv)
1621  bv->clear_bit_no_check(idx);
1622  }
1623  }
1624  if (v)
1625  {
1626  value_type mask = 1u;
1627  for (unsigned j = 0; j <= bsr; ++j)
1628  {
1629  if (v & mask)
1630  {
1631  bvector_type* bv = this->get_plain(j);
1632  bv->set_bit_no_check(idx);
1633  }
1634  else
1635  {
1636  const bm::word_t* blk = this->bmatr_.get_block(j, i0, j0);
1637  if (blk)
1638  {
1639  bvector_type* bv = this->bmatr_.get_row(j);
1640  bv->clear_bit_no_check(idx);
1641  }
1642  }
1643  mask <<= 1;
1644  }
1645  }
1646 }
1647 
1648 //---------------------------------------------------------------------
1649 
1650 template<class Val, class BV>
1651 void sparse_vector<Val, BV>::inc(size_type idx)
1652 {
1653  if (idx >= this->size_)
1654  this->size_ = idx+1;
1655 
1656  for (unsigned i = 0; i < parent_type::sv_value_plains; ++i)
1657  {
1658  bvector_type* bv = this->get_plain(i);
1659  bool carry_over = bv->inc(idx);
1660  if (!carry_over)
1661  break;
1662  }
1663  bvector_type* bv_null = this->get_null_bvect();
1664  if (bv_null)
1665  bv_null->set_bit_no_check(idx);
1666 }
1667 
1668 //---------------------------------------------------------------------
1669 
1670 template<class Val, class BV>
1672 {
1673  parent_type::clear();
1674 }
1675 
1676 //---------------------------------------------------------------------
1677 
1678 template<class Val, class BV>
1679 bool sparse_vector<Val, BV>::find_rank(size_type rank, size_type& pos)
1680 {
1681  BM_ASSERT(rank);
1682  pos = rank - 1;
1683  return true;
1684 }
1685 
1686 //---------------------------------------------------------------------
1687 
1688 template<class Val, class BV>
1691  typename sparse_vector<Val, BV>::size_type left,
1692  typename sparse_vector<Val, BV>::size_type right,
1693  bool set_null)
1694 {
1695  parent_type::clear_range(left, right, set_null);
1696  return *this;
1697 }
1698 
1699 //---------------------------------------------------------------------
1700 
1701 template<class Val, class BV>
1703  struct sparse_vector<Val, BV>::statistics* st) const
1704 {
1705  BM_ASSERT(st);
1706  typename bvector_type::statistics stbv;
1707  parent_type::calc_stat(&stbv);
1708  if (st)
1709  {
1710  st->reset();
1711  st->add(stbv);
1712  }
1713 }
1714 
1715 //---------------------------------------------------------------------
1716 
1717 template<class Val, class BV>
1719  bm::word_t* temp_block,
1720  typename bvector_type::optmode opt_mode,
1722 {
1723  typename bvector_type::statistics stbv;
1724  stbv.reset();
1725  parent_type::optimize(temp_block, opt_mode, st ? &stbv : 0);
1726 
1727  if (st)
1728  {
1729  st->reset();
1730  st->add(stbv);
1731  }
1732 }
1733 
1734 //---------------------------------------------------------------------
1735 
1736 template<class Val, class BV>
1738 {
1739  unsigned stored_plains = this->stored_plains();
1740  for (unsigned j = 0; j < stored_plains; ++j)
1741  {
1742  bvector_type* bv = this->bmatr_.get_row(j);
1743  if (bv)
1744  {
1745  bv->optimize_gap_size();
1746  }
1747  }
1748 }
1749 
1750 //---------------------------------------------------------------------
1751 
1752 template<class Val, class BV>
1755 {
1756  size_type arg_size = sv.size();
1757  if (this->size_ < arg_size)
1758  {
1759  resize(arg_size);
1760  }
1761  bvector_type* bv_null = this->get_null_bvect();
1762  unsigned plains;
1763  if (bv_null)
1764  plains = this->stored_plains();
1765  else
1766  plains = this->plains();
1767 
1768  for (unsigned j = 0; j < plains; ++j)
1769  {
1770  const bvector_type* arg_bv = sv.bmatr_.row(j);
1771  if (arg_bv)
1772  {
1773  bvector_type* bv = this->bmatr_.get_row(j);
1774  if (!bv)
1775  bv = this->get_plain(j);
1776  *bv |= *arg_bv;
1777  }
1778  } // for j
1779 
1780  // our vector is NULL-able but argument is not (assumed all values are real)
1781  if (bv_null && !sv.is_nullable())
1782  {
1783  bv_null->set_range(0, arg_size-1);
1784  }
1785 
1786  return *this;
1787 }
1788 
1789 //---------------------------------------------------------------------
1790 
1791 template<class Val, class BV>
1794 {
1795  size_type arg_size = sv.size();
1796  if (this->size_ < arg_size)
1797  {
1798  resize(arg_size);
1799  }
1800  bvector_type* bv_null = this->get_null_bvect();
1801  unsigned plains;
1802  if (bv_null)
1803  plains = this->stored_plains();
1804  else
1805  plains = this->plains();
1806 
1807  for (unsigned j = 0; j < plains; ++j)
1808  {
1809  bvector_type* arg_bv = sv.bmatr_.get_row(j);//sv.plains_[j];
1810  if (arg_bv)
1811  {
1812  bvector_type* bv = this->bmatr_.get_row(j);//this->plains_[j];
1813  if (!bv)
1814  bv = this->get_plain(j);
1815  bv->merge(*arg_bv);
1816  }
1817  } // for j
1818 
1819  // our vector is NULL-able but argument is not (assumed all values are real)
1820  if (bv_null && !sv.is_nullable())
1821  {
1822  bv_null->set_range(0, arg_size-1);
1823  }
1824 
1825  return *this;
1826 }
1827 
1828 //---------------------------------------------------------------------
1829 
1830 template<class Val, class BV>
1832  typename sparse_vector<Val, BV>::size_type left,
1833  typename sparse_vector<Val, BV>::size_type right)
1834 {
1835  if (left > right)
1836  bm::xor_swap(left, right);
1837 
1838  bvector_type* bv_null = this->get_null_bvect();
1839  unsigned plains;
1840  if (bv_null)
1841  {
1842  plains = this->stored_plains();
1843  const bvector_type* bv_null_arg = sv.get_null_bvector();
1844  if (bv_null_arg)
1845  bv_null->copy_range(*bv_null_arg, left, right);
1846  }
1847  else
1848  plains = this->plains();
1849 
1850  for (unsigned j = 0; j < plains; ++j)
1851  {
1852  const bvector_type* arg_bv = sv.bmatr_.row(j);
1853  if (arg_bv)
1854  {
1855  bvector_type* bv = this->bmatr_.get_row(j);
1856  if (!bv)
1857  bv = this->get_plain(j);
1858  bv->copy_range(*arg_bv, left, right);
1859  }
1860  } // for j
1861  this->resize(sv.size());
1862 }
1863 //---------------------------------------------------------------------
1864 
1865 template<class Val, class BV>
1867  const typename sparse_vector<Val, BV>::bvector_type& bv_mask)
1868 {
1869  bvector_type* bv_null = this->get_null_bvect();
1870  unsigned plains;
1871  if (bv_null)
1872  {
1873  plains = this->stored_plains();
1874  bv_null->bit_and(bv_mask);
1875  }
1876  else
1877  plains = this->plains();
1878 
1879  for (unsigned j = 0; j < plains; ++j)
1880  {
1881  bvector_type* bv = this->bmatr_.get_row(j);
1882  if (bv)
1883  bv->bit_and(bv_mask);
1884  }
1885 }
1886 
1887 //---------------------------------------------------------------------
1888 
1889 template<class Val, class BV>
1890 int sparse_vector<Val, BV>::compare(size_type idx, const value_type val) const
1891 {
1892  // TODO: consider bit-by-bit comparison to minimize CPU hit miss in plans get()
1893  value_type sv_value = get(idx);
1894  return (sv_value > val) - (sv_value < val);
1895 }
1896 
1897 //---------------------------------------------------------------------
1898 
1899 template<class Val, class BV>
1901  bm::null_support null_able) const
1902 {
1903  return parent_type::equal(sv, null_able);
1904 }
1905 
1906 //---------------------------------------------------------------------
1907 
1908 template<class Val, class BV>
1911 {
1912  typedef typename sparse_vector<Val, BV>::const_iterator it_type;
1913  return it_type(this);
1914 }
1915 
1916 //---------------------------------------------------------------------
1917 
1918 template<class Val, class BV>
1921 {
1922  this->bmatr_.set_allocator_pool(pool_ptr);
1923 }
1924 
1925 
1926 //---------------------------------------------------------------------
1927 //
1928 //---------------------------------------------------------------------
1929 
1930 
1931 template<class Val, class BV>
1933 : sv_(0), pos_(bm::id_max), buf_ptr_(0)
1934 {}
1935 
1936 //---------------------------------------------------------------------
1937 
1938 template<class Val, class BV>
1940  const typename sparse_vector<Val, BV>::const_iterator& it)
1941 : sv_(it.sv_), pos_(it.pos_), buf_ptr_(0)
1942 {}
1943 
1944 //---------------------------------------------------------------------
1945 
1946 template<class Val, class BV>
1949 : sv_(sv), buf_ptr_(0)
1950 {
1951  BM_ASSERT(sv_);
1952  pos_ = sv_->empty() ? bm::id_max : 0u;
1953 }
1954 
1955 //---------------------------------------------------------------------
1956 
1957 template<class Val, class BV>
1961 : sv_(sv), buf_ptr_(0)
1962 {
1963  BM_ASSERT(sv_);
1964  this->go_to(pos);
1965 }
1966 
1967 //---------------------------------------------------------------------
1968 
1969 template<class Val, class BV>
1971 {
1972  pos_ = (!sv_ || pos >= sv_->size()) ? bm::id_max : pos;
1973  buf_ptr_ = 0;
1974 }
1975 
1976 //---------------------------------------------------------------------
1977 
1978 template<class Val, class BV>
1980 {
1981  if (pos_ == bm::id_max) // nothing to do, we are at the end
1982  return;
1983  ++pos_;
1984  if (pos_ >= sv_->size())
1985  this->invalidate();
1986  else
1987  {
1988  if (buf_ptr_)
1989  {
1990  ++buf_ptr_;
1991  if (buf_ptr_ - ((value_type*)buffer_.data()) >= n_buf_size)
1992  buf_ptr_ = 0;
1993  }
1994  }
1995 }
1996 
1997 //---------------------------------------------------------------------
1998 
1999 template<class Val, class BV>
2002 {
2003  BM_ASSERT(this->valid());
2004  value_type v;
2005 
2006  if (!buf_ptr_)
2007  {
2008  buffer_.reserve(n_buf_size * sizeof(value_type));
2009  buf_ptr_ = (value_type*)(buffer_.data());
2010  sv_->extract(buf_ptr_, n_buf_size, pos_, true, &pool_);
2011  }
2012  v = *buf_ptr_;
2013  return v;
2014 }
2015 
2016 //---------------------------------------------------------------------
2017 
2018 template<class Val, class BV>
2020 {
2021  value_type v = value();
2022  if (buf_ptr_)
2023  {
2024  v = *buf_ptr_;
2025  value_type* buf_end = ((value_type*)buffer_.data()) + n_buf_size;
2026  while(!v)
2027  {
2028  ++pos_;
2029  if (++buf_ptr_ < buf_end)
2030  v = *buf_ptr_;
2031  else
2032  break;
2033  }
2034  if (pos_ >= sv_->size())
2035  {
2036  pos_ = bm::id_max;
2037  return;
2038  }
2039  if (buf_ptr_ >= buf_end)
2040  buf_ptr_ = 0;
2041  }
2042 }
2043 
2044 //---------------------------------------------------------------------
2045 
2046 template<class Val, class BV>
2048 {
2049  return sv_->is_null(pos_);
2050 }
2051 
2052 
2053 //---------------------------------------------------------------------
2054 //
2055 //---------------------------------------------------------------------
2056 
2057 
2058 template<class Val, class BV>
2060 : sv_(0), bv_null_(0), buf_ptr_(0)
2061 {}
2062 
2063 //---------------------------------------------------------------------
2064 
2065 template<class Val, class BV>
2068 : sv_(sv), buf_ptr_(0)
2069 {
2070  bv_null_ = sv_? sv_->get_null_bvect() : 0;
2071 }
2072 
2073 //---------------------------------------------------------------------
2074 
2075 template<class Val, class BV>
2078 : sv_(bi.sv_), bv_null_(bi.bv_null_), buf_ptr_(0)
2079 {
2080  BM_ASSERT(bi.empty());
2081 }
2082 
2083 //---------------------------------------------------------------------
2084 
2085 template<class Val, class BV>
2087 {
2088  this->flush();
2089 }
2090 
2091 //---------------------------------------------------------------------
2092 
2093 template<class Val, class BV>
2096 {
2097  size_type buf_idx = this->add_value(v);
2098  if (bv_null_)
2099  {
2100  typename sparse_vector<Val, BV>::size_type sz = sv_->size();
2101  bv_null_->set_bit_no_check(sz + buf_idx);
2102  }
2103 }
2104 
2105 //---------------------------------------------------------------------
2106 
2107 template<class Val, class BV>
2111 {
2112  BM_ASSERT(sv_);
2113  if (!buf_ptr_) // not allocated (yet)
2114  {
2115  buffer_.reserve(n_buf_size * sizeof(value_type));
2116  buf_ptr_ = (value_type*)(buffer_.data());
2117  *buf_ptr_ = v;
2118  ++buf_ptr_;
2119  return 0;
2120  }
2121  if (buf_ptr_ - ((value_type*)buffer_.data()) >= n_buf_size)
2122  {
2123  this->flush();
2124  buf_ptr_ = (value_type*)(buffer_.data());
2125  }
2126 
2127  *buf_ptr_ = v;
2128  size_type buf_idx = size_type(buf_ptr_ - ((value_type*)buffer_.data()));
2129  ++buf_ptr_;
2130  return buf_idx;
2131 }
2132 
2133 //---------------------------------------------------------------------
2134 
2135 template<class Val, class BV>
2137 {
2138  this->add(value_type(0));
2139 }
2140 
2141 //---------------------------------------------------------------------
2142 
2143 template<class Val, class BV>
2146 {
2147  if (count < 32)
2148  {
2149  for (size_type i = 0; i < count; ++i)
2150  this->add(value_type(0));
2151  }
2152  else
2153  {
2154  this->flush();
2155  sv_->push_back_null(count);
2156  }
2157 }
2158 
2159 //---------------------------------------------------------------------
2160 
2161 template<class Val, class BV>
2163 {
2164  return (!buf_ptr_ || !sv_);
2165 }
2166 
2167 //---------------------------------------------------------------------
2168 
2169 template<class Val, class BV>
2171 {
2172  if (this->empty())
2173  return;
2174  value_type* d = (value_type*)buffer_.data();
2175  sv_->import_back(d, size_type(buf_ptr_ - d));
2176  buf_ptr_ = 0;
2177 }
2178 
2179 //---------------------------------------------------------------------
2180 
2181 
2182 } // namespace bm
2183 
2184 #include "bmundef.h"
2185 
2186 
2187 #endif
memory allocation policy
Definition: bm.h:1243
std::input_iterator_tag iterator_category
Definition: bmsparsevec.h:156
back_insert_iterator & operator++(int)
noop
Definition: bmsparsevec.h:291
value_type at(size_type idx) const
access specified element with bounds checking
Definition: bmsparsevec.h:1426
size_type effective_vector_max() const
Always 1 (non-matrix type)
Definition: bmsparsevec.h:828
void clear_bit_no_check(size_type n)
Clears bit n without precondiion checks.
Definition: bm.h:1606
void filter(const bvector_type &bv_mask)
Apply value filter, defined by mask vector.
Definition: bmsparsevec.h:1866
bool is_nullable() const
check if container supports NULL(unassigned) values
Definition: bmbmatrix.h:313
bm::basic_bmatrix< BV > bmatrix_type
Definition: bmsparsevec.h:95
back_insert_iterator & operator=(value_type v)
push value to the vector
Definition: bmsparsevec.h:285
void erase(size_type idx)
erase specified element from container
Definition: bmsparsevec.h:1569
bvector_type * bvector_type_ptr
Definition: bmsparsevec.h:86
unsigned char * init_remap_buffer()
Definition: bmsparsevec.h:864
friend back_insert_iterator
Definition: bmsparsevec.h:330
Base class for bit-transposed sparse vector construction.
Definition: bmbmatrix.h:244
const unsigned set_word_shift
Definition: bmconst.h:70
const value_type & const_reference
Definition: bmsparsevec.h:90
sparse_vector_type::value_type value_type
Definition: bmsparsevec.h:160
void optimize_gap_size()
Optimize sizes of GAP blocks.
Definition: bm.h:3182
const unsigned set_array_shift
Definition: bmconst.h:92
back_insert_iterator & operator*()
noop
Definition: bmsparsevec.h:287
bm::byte_buffer< allocator_type > buffer_type
Definition: bmsparsevec.h:165
void optimize(bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename sparse_vector< Val, BV >::statistics *stat=0)
run memory optimization for all vector plains
Definition: bmsparsevec.h:1718
bool valid() const
Returns true if iterator is at a valid position.
Definition: bmsparsevec.h:209
void insert(size_type idx, value_type v)
insert specified element into container
Definition: bmsparsevec.h:1511
bool is_null() const
Get NULL status.
Definition: bmsparsevec.h:2047
void add(value_type v)
add value to the container
Definition: bmsparsevec.h:2094
bm::id_t size_type
Definition: bm.h:117
Rank-Select compressed sparse vector.
sparse_vector< Val, BV > & merge(sparse_vector< Val, BV > &sv)
merge with another sparse vector using OR operation Merge is different from join(), because it borrows data from the source vector, so it gets modified.
Definition: bmsparsevec.h:1793
Definition: bm.h:76
basic bit-matrix class and utilities
void add_null()
add NULL (no-value) to the container
Definition: bmsparsevec.h:2136
static bool find_rank(size_type rank, size_type &pos)
find position of compressed element by its rank
Definition: bmsparsevec.h:1679
pre-processor un-defines to avoid global space pollution (internal)
const bvector_type * row(size_type i) const
Definition: bmbmatrix.h:527
static unsigned rows()
Definition: bmtrans.h:61
void resize_internal(size_type sz)
Definition: bmsparsevec.h:858
#define BMNOEXEPT
Definition: bmdef.h:78
algorithms for sparse_vector scan/seach
size_type decode(value_type *arr, size_type idx_from, size_type dec_size, bool zero_mem=true) const
Bulk export list of elements to a C-style array.
Definition: bmsparsevec.h:1039
bool inc(size_type n)
Increment the specified element.
Definition: bm.h:3736
sparse_vector_type::size_type size_type
Definition: bmsparsevec.h:260
Back insert iterator implements buffered insert, faster than generic access assignment.
Definition: bmsparsevec.h:251
static bool is_compressed()
trait if sparse vector is "compressed" (false)
Definition: bmsparsevec.h:499
void xor_swap(W &x, W &y)
XOR swap two scalar variables.
Definition: bmfunc.h:876
bvector_type::allocator_type allocator_type
Definition: bmsparsevec.h:262
back_insert_iterator & operator=(const back_insert_iterator &bi)
Definition: bmsparsevec.h:275
void inc(size_type idx)
increment specified element by one
Definition: bmsparsevec.h:1651
compress blocks when possible (GAP/prefix sum)
Definition: bm.h:134
void insert_value_no_null(size_type idx, value_type v)
insert value without checking boundaries or support of NULL
Definition: bmsparsevec.h:1534
const bvector_type * get_null_bvector() const
Get bit-vector of assigned values or NULL (if not constructed that way)
Definition: bmbmatrix.h:319
void go_to(size_type pos)
re-position to a specified position
Definition: bmsparsevec.h:1970
sparse_vector< Val, BV > & join(const sparse_vector< Val, BV > &sv)
join all with another sparse vector using OR operation
Definition: bmsparsevec.h:1754
do not support NULL values
Definition: bmconst.h:217
const unsigned id_max
Definition: bmconst.h:105
void set_value_no_null(size_type idx, value_type v)
set value without checking boundaries or support of NULL
Definition: bmsparsevec.h:1602
Statistical information about bitset&#39;s memory allocation details.
Definition: bm.h:121
Algorithms for bvector<> (main include)
bool operator!=(const const_iterator &it) const
Definition: bmsparsevec.h:179
void optimize_gap_size()
Optimize sizes of GAP blocks.
Definition: bmsparsevec.h:1737
void set_allocator_pool(allocator_pool_type *pool_ptr)
Set allocator pool for local (non-threaded) memory cyclic(lots of alloc-free ops) opertations...
Definition: bmsparsevec.h:1919
unsigned idx_arr_block_lookup_u32(const unsigned *idx, unsigned size, unsigned nb, unsigned start)
block boundaries look ahead U32
Definition: bmfunc.h:7614
void import_back(const value_type *arr, size_type arr_size)
Import list of elements from a C-style array (pushed back)
Definition: bmsparsevec.h:1029
sort order unknown
Definition: bmconst.h:194
void push_back_null(size_type count)
push back specified amount of NULL values
Definition: bmsparsevec.h:1498
bvector_type::enumerator bvector_enumerator_type
Definition: bmsparsevec.h:93
sparse vector with runtime compression using bit transposition method
Definition: bmsparsevec.h:81
null_support
NULL-able value support.
Definition: bmconst.h:214
blocks_manager_type::block_idx_type block_idx_type
Definition: bm.h:113
unsigned bit_scan_reverse(T value)
Definition: bmfunc.h:172
Alloc allocator_type
Definition: bm.h:110
void copy_range(const bvector< Alloc > &bvect, size_type left, size_type right)
Copy all bits in the specified closed interval [left,right].
Definition: bm.h:6560
input set is sorted (ascending order)
Definition: bmconst.h:192
bvector_type::allocator_type::allocator_pool_type allocator_pool_type
Definition: bmsparsevec.h:263
int compare(size_type idx, const value_type val) const
Compare vector element with argument.
Definition: bmsparsevec.h:1890
void flush()
flush the accumulated buffer
Definition: bmsparsevec.h:2170
sort_order
Sort order declaration.
Definition: bmconst.h:189
bvector< Alloc > & set(size_type n, bool val=true)
Sets bit n if val is true, clears bit n if val is false.
Definition: bm.h:3539
unsigned int word_t
Definition: bmconst.h:38
#define IS_FULL_BLOCK(addr)
Definition: bmdef.h:140
size_type pos() const
Current position (index) in the vector.
Definition: bmsparsevec.h:215
size_type extract(value_type *arr, size_type size, size_type offset=0, bool zero_mem=true, allocator_pool_type *pool_ptr=0) const
Bulk export list of elements to a C-style array.
Definition: bmsparsevec.h:1337
void for_each_bit(const BV &bv, Func &bit_functor)
bit-vector visitor scanner to traverse each 1 bit using C++ visitor
Definition: bmalgo.h:65
const_iterator & operator++(int)
Advance to the next available value.
Definition: bmsparsevec.h:198
void push_back(value_type v)
push value back into vector
Definition: bmsparsevec.h:1489
bvector_type::allocator_type::allocator_pool_type allocator_pool_type
Definition: bmsparsevec.h:164
const_iterator begin() const
Provide const iterator access to container content.
Definition: bmsparsevec.h:1910
bvector_type::allocation_policy allocation_policy_type
Definition: bmsparsevec.h:92
support "non-assigned" or "NULL" logic
Definition: bmconst.h:216
Basic dense bit-matrix class.
Definition: bmbmatrix.h:53
void resize(size_type new_size)
Definition: bmbmatrix.h:1213
unsigned gap_bfind(const T *buf, unsigned pos, unsigned *is_set)
Definition: bmfunc.h:1185
sparse_vector< Val, BV > sparse_vector_type
Definition: bmsparsevec.h:257
size_type extract_plains(value_type *arr, size_type size, size_type offset, bool zero_mem=true) const
extract medium window without use of masking vector
Definition: bmsparsevec.h:1292
bool operator==(const const_iterator &it) const
Definition: bmsparsevec.h:177
unsigned gap_test_unr(const T *buf, const unsigned pos)
Tests if bit = pos is true. Analog of bm::gap_test with SIMD unrolling.
Definition: bmfunc.h:1256
reference operator[](size_type idx)
Operator to get write access to an element.
Definition: bmsparsevec.h:395
bool empty() const
return true if vector is empty
Definition: bmsparsevec.h:618
sparse_vector< Val, BV > & clear_range(size_type left, size_type right, bool set_null=false)
clear range (assign bit 0 for all plains)
Definition: bmsparsevec.h:1690
bool empty() const
return true if insertion buffer is empty
Definition: bmsparsevec.h:2162
sparse_vector_type::bvector_type bvector_type
Definition: bmsparsevec.h:162
void resize(size_type sz)
resize vector
Definition: bmsparsevec.h:623
value_type value() const
Get current position (value)
Definition: bmsparsevec.h:2001
bool is_remap() const
Definition: bmsparsevec.h:861
void sync(bool)
syncronize internal structures
Definition: bmsparsevec.h:748
const unsigned set_array_mask
Definition: bmconst.h:93
size_type add_value(value_type v)
add value to the buffer without changing the NULL vector
Definition: bmsparsevec.h:2109
unsigned short gap_word_t
Definition: bmconst.h:76
sparse_vector< Val, BV > sparse_vector_type
Definition: bmsparsevec.h:158
back_insert_iterator get_back_inserter()
Provide back insert iterator Back insert iterator implements buffered insertion, which is faster...
Definition: bmsparsevec.h:483
sparse_vector_type::value_type value_type
Definition: bmsparsevec.h:259
bvector_type::block_idx_type block_idx_type
Definition: bmsparsevec.h:88
size_type extract_range(value_type *arr, size_type size, size_type offset, bool zero_mem=true) const
extract small window without use of masking vector
Definition: bmsparsevec.h:1212
sparse_vector_type * sparse_vector_type_ptr
Definition: bmsparsevec.h:159
size_t remap_size() const
Definition: bmsparsevec.h:862
BV::allocator_type allocator_type
Definition: bmsparsevec.h:91
static size_type translate_address(size_type i)
address translation for this type of container
Definition: bmsparsevec.h:797
bvector< Alloc > & set_range(size_type left, size_type right, bool value=true)
Sets all bits in the specified closed interval [left,right] Interval must be inside the bvector&#39;s siz...
Definition: bm.h:2451
bvector_type::allocator_type allocator_type
Definition: bmsparsevec.h:163
void set_null(size_type idx)
set specified element to unassigned value (NULL)
Definition: bmsparsevec.h:945
bm::id64_t idx_arr_block_lookup_u64(const bm::id64_t *idx, bm::id64_t size, bm::id64_t nb, bm::id64_t start)
block boundaries look ahead U32
Definition: bmfunc.h:7589
void reset()
Reset statisctics.
Definition: bmfunc.h:93
sparse_vector_type::bvector_type bvector_type
Definition: bmsparsevec.h:261
bool is_null(size_type idx) const
test if specified element is NULL
Definition: bmbmatrix.h:1231
size_type gather(value_type *arr, const size_type *idx, size_type size, bm::sort_order sorted_idx) const
Gather elements to a C-style array.
Definition: bmsparsevec.h:1063
allocator_type::allocator_pool_type allocator_pool_type
Definition: bm.h:111
const unsigned char * get_remap_buffer() const
Definition: bmsparsevec.h:863
value_type operator[](size_type idx) const
get specified element without bounds checking
Definition: bmsparsevec.h:402
const_iterator & operator++()
Advance to the next available value.
Definition: bmsparsevec.h:195
Definitions(internal)
void copy_from(const base_sparse_vector< Val, BV, MAX_SIZE > &bsv)
Definition: bmbmatrix.h:1121
#define BM_ASSERT_THROW(x, xerrcode)
Definition: bmdef.h:388
Serialize sparse vector into a memory buffer(s) structure.
reference(sparse_vector< Val, BV > &sv, size_type idx) BMNOEXEPT
Definition: bmsparsevec.h:116
static void throw_range_error(const char *err_msg)
throw range error
Definition: bmsparsevec.h:925
back_insert_iterator & operator++()
noop
Definition: bmsparsevec.h:289
const bvector_type * bvector_type_const_ptr
Definition: bmsparsevec.h:89
#define BM_IS_GAP(ptr)
Definition: bmdef.h:168
Utilities for bit transposition (internal) (experimental!)
void merge(bm::bvector< Alloc > &bvect)
Merge/move content from another vector.
Definition: bm.h:4657
void copy_range(const sparse_vector< Val, BV > &sv, size_type left, size_type right)
copy range of values from another sparse vector
Definition: bmsparsevec.h:1831
void insert_value(size_type idx, value_type v)
insert value without checking boundaries
Definition: bmsparsevec.h:1525
void calc_stat(struct sparse_vector< Val, BV >::statistics *st) const
Calculates memory statistics.
Definition: bmsparsevec.h:1702
size_type size() const
return size of the vector
Definition: bmsparsevec.h:613
std::output_iterator_tag iterator_category
Definition: bmsparsevec.h:255
const unsigned set_block_mask
Definition: bmconst.h:56
void clear() BMNOEXEPT
resize to zero, free memory
Definition: bmsparsevec.h:1671
bvector_type_const_ptr get_row(size_type i) const
Definition: bmbmatrix.h:537
Constant iterator designed to enumerate "ON" bits.
Definition: bm.h:590
optmode
Optimization mode Every next level means additional checks (better compression vs time) ...
Definition: bm.h:129
allocator_type::allocator_pool_type allocator_pool_type
Definition: bmsparsevec.h:94
#define BMGAP_PTR(ptr)
Definition: bmdef.h:166
Const iterator to traverse the sparse vector.
Definition: bmsparsevec.h:150
bool equal(const sparse_vector< Val, BV > &sv, bm::null_support null_able=bm::use_null) const
check if another sparse vector has the same content and size
Definition: bmsparsevec.h:1900
~sparse_vector() BMNOEXEPT
Definition: bmsparsevec.h:911
base_sparse_vector< Val, BV, 1 > parent_type
Definition: bmsparsevec.h:96
sparse vector de-serializer
reference & operator=(const reference &ref)
Definition: bmsparsevec.h:120
const unsigned set_word_mask
Definition: bmconst.h:71
Reference class to access elements via common [] operator.
Definition: bmsparsevec.h:113
bm::bvector< Alloc > & bit_and(const bm::bvector< Alloc > &bv1, const bm::bvector< Alloc > &bv2, typename bm::bvector< Alloc >::optmode opt_mode)
3-operand AND : this := bv1 AND bv2
Definition: bm.h:4927
bool operator==(const reference &ref) const
Definition: bmsparsevec.h:130
void invalidate()
Invalidate current iterator.
Definition: bmsparsevec.h:212
bvector_type::size_type size_type
Definition: bmsparsevec.h:87
input set is NOT sorted
Definition: bmconst.h:191
void advance()
advance iterator forward by one
Definition: bmsparsevec.h:1979
const_iterator get_const_iterator(size_type idx) const
Get const_itertor re-positioned to specific element.
Definition: bmsparsevec.h:477
size_type size_internal() const
Definition: bmsparsevec.h:859
unsigned short bitscan(V w, B *bits)
Definition: bmfunc.h:519
reference & operator=(value_type val)
Definition: bmsparsevec.h:125
#define BM_ASSERT
Definition: bmdef.h:117
void push_back_no_null(value_type v)
push value back into vector without NULL semantics
Definition: bmsparsevec.h:1582
void set_allocator_pool(allocator_pool_type *pool_ptr)
Set allocator pool for local (non-threaded) memory cyclic(lots of alloc-free ops) opertations...
Definition: bm.h:1448
void set_value(size_type idx, value_type v)
set value without checking boundaries
Definition: bmsparsevec.h:1591
value_type operator*() const
Get current position (value)
Definition: bmsparsevec.h:191
bmatrix_type bmatr_
bit-transposed matrix
Definition: bmbmatrix.h:462
Structure with statistical information about memory allocation footprint, serialization projection...
Definition: bmfunc.h:54
const unsigned set_block_shift
Definition: bmconst.h:55
void add(const bv_statistics &st)
Sum data from another sttructure.
Definition: bmfunc.h:102
const_iterator end() const
Provide const iterator access to the end.
Definition: bmsparsevec.h:472
Mini-matrix for bit transposition purposes.
Definition: bmtrans.h:40
size_type effective_size() const
size of sparse vector (may be different for RSC)
Definition: bmsparsevec.h:823
void bit_block_gather_scatter(unsigned *arr, const bm::word_t *blk, const unsigned *idx, unsigned size, unsigned start, unsigned bit_idx)
bit index to word gather-scatter algorithm (SIMD)
Definition: bmfunc.h:7520
sparse_vector_type * sparse_vector_type_ptr
Definition: bmsparsevec.h:258
const T * row(unsigned row_idx) const
Definition: bmtrans.h:64
static void throw_bad_alloc()
throw bad alloc
Definition: bmsparsevec.h:937
void set_bit_no_check(size_type n)
Set bit without checking preconditions (size, etc)
Definition: bm.h:3425
bm::byte_buffer< allocator_type > buffer_type
Definition: bmsparsevec.h:264
#define FULL_BLOCK_FAKE_ADDR
Definition: bmdef.h:136
sorted and in one block (internal!)
Definition: bmconst.h:193
sparse_vector_type::size_type size_type
Definition: bmsparsevec.h:161
bool insert(size_type n, bool value)
Insert bit into specified position All the vector content after insert position is shifted right...
Definition: bm.h:4311
sparse_vector(bm::null_support null_able=bm::no_null, allocation_policy_type ap=allocation_policy_type(), size_type bv_max_size=bm::id_max, const allocator_type &alloc=allocator_type())
Sparse vector constructor.
Definition: bmsparsevec.h:881
void swap(sparse_vector< Val, BV > &sv) BMNOEXEPT
content exchange
Definition: bmsparsevec.h:917
sparse_vector< Val, BV > & operator=(const sparse_vector< Val, BV > &sv)
Definition: bmsparsevec.h:362