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