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 protected:
909  template<class V, class SV> friend class rsc_sparse_vector;
910  template<class SVect> friend class sparse_vector_scanner;
911  template<class SVect> friend class sparse_vector_serializer;
912  template<class SVect> friend class sparse_vector_deserializer;
913 
914 };
915 
916 
917 //---------------------------------------------------------------------
918 //---------------------------------------------------------------------
919 
920 
921 template<class Val, class BV>
923  bm::null_support null_able,
925  size_type bv_max_size,
926  const allocator_type& alloc)
927 : parent_type(null_able, ap, bv_max_size, alloc)
928 {}
929 
930 //---------------------------------------------------------------------
931 
932 template<class Val, class BV>
934 : parent_type(sv)
935 {}
936 
937 //---------------------------------------------------------------------
938 #ifndef BM_NO_CXX11
939 
940 template<class Val, class BV>
942 {
943  parent_type::swap(sv);
944 }
945 
946 #endif
947 
948 
949 //---------------------------------------------------------------------
950 
951 template<class Val, class BV>
953 {}
954 
955 //---------------------------------------------------------------------
956 
957 template<class Val, class BV>
959 {
960  parent_type::swap(sv);
961 }
962 
963 //---------------------------------------------------------------------
964 
965 template<class Val, class BV>
967 {
968 #ifndef BM_NO_STL
969  throw std::range_error(err_msg);
970 #else
971  BM_ASSERT_THROW(false, BM_ERR_RANGE);
972 #endif
973 }
974 
975 //---------------------------------------------------------------------
976 
977 template<class Val, class BV>
979 {
980  BV::throw_bad_alloc();
981 }
982 
983 //---------------------------------------------------------------------
984 
985 template<class Val, class BV>
987 {
988  clear(idx, true);
989 }
990 
991 //---------------------------------------------------------------------
992 
993 template<class Val, class BV>
994 void sparse_vector<Val, BV>::import(const value_type* arr,
995  size_type arr_size,
996  size_type offset,
997  bool set_not_null)
998 {
999  unsigned char b_list[sizeof(Val)*8];
1000  unsigned row_len[sizeof(Val)*8] = {0, };
1001 
1002  const unsigned transpose_window = 256;
1003  bm::tmatrix<size_type, sizeof(Val)*8, transpose_window> tm; // matrix accumulator
1004 
1005  if (arr_size == 0)
1006  throw_range_error("sparse_vector range error (import size 0)");
1007 
1008  if (offset < this->size_) // in case it touches existing elements
1009  {
1010  // clear all plains in the range to provide corrrect import of 0 values
1011  this->clear_range(offset, offset + arr_size - 1);
1012  }
1013 
1014  // transposition algorithm uses bitscan to find index bits and store it
1015  // in temporary matrix (list for each bit plain), matrix here works
1016  // when array gets to big - the list gets loaded into bit-vector using
1017  // bulk load algorithm, which is faster than single bit access
1018  //
1019 
1020  size_type i;
1021  for (i = 0; i < arr_size; ++i)
1022  {
1023  unsigned bcnt = bm::bitscan(arr[i], b_list);
1024  const size_type bit_idx = i + offset;
1025 
1026  for (unsigned j = 0; j < bcnt; ++j)
1027  {
1028  unsigned p = b_list[j];
1029  unsigned rl = row_len[p];
1030  tm.row(p)[rl] = bit_idx;
1031  row_len[p] = ++rl;
1032 
1033  if (rl == transpose_window)
1034  {
1035  bvector_type* bv = this->get_plain(p);
1036  const size_type* r = tm.row(p);
1037  bv->set(r, rl, BM_SORTED);
1038  row_len[p] = 0;
1039  tm.row(p)[0] = 0;
1040  }
1041  } // for j
1042  } // for i
1043 
1044  // process incomplete transposition lines
1045  //
1046  for (unsigned k = 0; k < tm.rows(); ++k)
1047  {
1048  unsigned rl = row_len[k];
1049  if (rl)
1050  {
1051  bvector_type* bv = this->get_plain(k);
1052  const size_type* r = tm.row(k);
1053  bv->set(r, rl, BM_SORTED);
1054  }
1055  } // for k
1056 
1057 
1058  if (i + offset > this->size_)
1059  this->size_ = i + offset;
1060 
1061  if (set_not_null)
1062  {
1063  bvector_type* bv_null = this->get_null_bvect();
1064  if (bv_null) // configured to support NULL assignments
1065  bv_null->set_range(offset, offset + arr_size - 1);
1066  }
1067 }
1068 
1069 //---------------------------------------------------------------------
1070 
1071 template<class Val, class BV>
1072 void sparse_vector<Val, BV>::import_back(const value_type* arr,
1073  size_type arr_size,
1074  bool set_not_null)
1075 {
1076  this->import(arr, arr_size, this->size(), set_not_null);
1077 }
1078 
1079 //---------------------------------------------------------------------
1080 
1081 template<class Val, class BV>
1084  size_type idx_from,
1085  size_type dec_size,
1086  bool zero_mem) const
1087 {
1088  return extract(arr, dec_size, idx_from, zero_mem);
1089 }
1090 
1091 //---------------------------------------------------------------------
1092 
1093 template<class Val, class BV>
1096  const size_type* idx,
1097  size_type size,
1098  bm::sort_order sorted_idx) const
1099 {
1100  BM_ASSERT(arr);
1101  BM_ASSERT(idx);
1102  BM_ASSERT(size);
1103 
1104  if (size == 1) // corner case: get 1 value
1105  {
1106  arr[0] = this->get(idx[0]);
1107  return size;
1108  }
1109  ::memset(arr, 0, sizeof(value_type)*size);
1110 
1111  for (size_type i = 0; i < size;)
1112  {
1113  bool sorted_block = true;
1114 
1115  // look ahead for the depth of the same block
1116  // (speculate more than one index lookup per block)
1117  //
1118  block_idx_type nb = (idx[i] >> bm::set_block_shift);
1119  size_type r = i;
1120 
1121  switch (sorted_idx)
1122  {
1123  case BM_UNKNOWN:
1124  {
1125  size_type idx_prev = idx[r];
1126  for (; (r < size) && (nb == (idx[r] >> bm::set_block_shift)); ++r)
1127  {
1128  sorted_block = !(idx[r] < idx_prev); // sorted check
1129  idx_prev = idx[r];
1130  }
1131  }
1132  break;
1133  case BM_UNSORTED:
1134  sorted_block = false;
1135  for (; r < size; ++r)
1136  {
1137  block_idx_type nb_next = (idx[r] >> bm::set_block_shift);
1138  if (nb != nb_next)
1139  break;
1140  } // for r
1141  break;
1142  // no break(!) intentional fall through
1143  case BM_SORTED:
1144  #ifdef BM64ADDR
1145  r = bm::idx_arr_block_lookup_u64(idx, size, nb, r);
1146  #else
1147  r = bm::idx_arr_block_lookup_u32(idx, size, nb, r);
1148  #endif
1149  break;
1150  case BM_SORTED_UNIFORM:
1151  r = size;
1152  break;
1153  default:
1154  BM_ASSERT(0);
1155  } // switch
1156 
1157  // single element hit, use plain random access
1158  if (r == i+1)
1159  {
1160  arr[i] = this->get(idx[i]);
1161  ++i;
1162  continue;
1163  }
1164 
1165  // process block co-located elements at ones for best (CPU cache opt)
1166  //
1167  unsigned i0 = unsigned(nb >> bm::set_array_shift); // top block address
1168  unsigned j0 = unsigned(nb & bm::set_array_mask); // address in sub-block
1169 
1170  unsigned eff_plains = this->effective_plains(); // TODO: get real effective plains for [i,j]
1171  for (unsigned j = 0; j < eff_plains; ++j)
1172  {
1173  const bm::word_t* blk = this->bmatr_.get_block(j, i0, j0);
1174  if (!blk)
1175  continue;
1176  value_type vm;
1177  const value_type mask1 = 1;
1178 
1179  if (blk == FULL_BLOCK_FAKE_ADDR)
1180  {
1181  vm = (mask1 << j);
1182  for (size_type k = i; k < r; ++k)
1183  arr[k] |= vm;
1184  continue;
1185  }
1186  if (BM_IS_GAP(blk))
1187  {
1188  const bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
1189  unsigned is_set;
1190 
1191  if (sorted_block) // b-search hybrid with scan lookup
1192  {
1193  for (size_type k = i; k < r; )
1194  {
1195  unsigned nbit = unsigned(idx[k] & bm::set_block_mask);
1196 
1197  unsigned gidx = bm::gap_bfind(gap_blk, nbit, &is_set);
1198  unsigned gap_value = gap_blk[gidx];
1199  if (is_set)
1200  {
1201  arr[k] |= vm = (mask1 << j);
1202  for (++k; k < r; ++k) // speculative look-up
1203  {
1204  if (unsigned(idx[k] & bm::set_block_mask) <= gap_value)
1205  arr[k] |= vm;
1206  else
1207  break;
1208  }
1209  }
1210  else // 0 GAP - skip. not set
1211  {
1212  for (++k;
1213  (k < r) &&
1214  (unsigned(idx[k] & bm::set_block_mask) <= gap_value);
1215  ++k) {}
1216  }
1217  } // for k
1218  }
1219  else // unsorted block gather request: b-search lookup
1220  {
1221  for (size_type k = i; k < r; ++k)
1222  {
1223  unsigned nbit = unsigned(idx[k] & bm::set_block_mask);
1224  is_set = bm::gap_test_unr(gap_blk, nbit);
1225  arr[k] |= (value_type(bool(is_set)) << j);
1226  } // for k
1227  }
1228  continue;
1229  }
1230  bm::bit_block_gather_scatter(arr, blk, idx, r, i, j);
1231  } // for (each plain)
1232 
1233  i = r;
1234 
1235  } // for i
1236 
1237  return size;
1238 }
1239 
1240 //---------------------------------------------------------------------
1241 
1242 template<class Val, class BV>
1245  size_type size,
1246  size_type offset,
1247  bool zero_mem) const
1248 {
1249  if (size == 0)
1250  return 0;
1251  if (zero_mem)
1252  ::memset(arr, 0, sizeof(value_type)*size);
1253 
1254  size_type start = offset;
1255  size_type end = start + size;
1256  if (end > this->size_)
1257  {
1258  end = this->size_;
1259  }
1260 
1261  // calculate logical block coordinates and masks
1262  //
1263  block_idx_type nb = (start >> bm::set_block_shift);
1264  unsigned i0 = unsigned(nb >> bm::set_array_shift); // top block address
1265  unsigned j0 = unsigned(nb & bm::set_array_mask); // address in sub-block
1266  unsigned nbit = unsigned(start & bm::set_block_mask);
1267  unsigned nword = unsigned(nbit >> bm::set_word_shift);
1268  unsigned mask0 = 1u << (nbit & bm::set_word_mask);
1269  const bm::word_t* blk = 0;
1270  unsigned is_set;
1271 
1272  for (unsigned j = 0; j < sizeof(Val)*8; ++j)
1273  {
1274  blk = this->bmatr_.get_block(j, i0, j0);
1275  bool is_gap = BM_IS_GAP(blk);
1276 
1277  for (size_type k = start; k < end; ++k)
1278  {
1279  block_idx_type nb1 = (k >> bm::set_block_shift);
1280  if (nb1 != nb) // block switch boundaries
1281  {
1282  nb = nb1;
1283  i0 = unsigned(nb >> bm::set_array_shift);
1284  j0 = unsigned(nb & bm::set_array_mask);
1285  blk = this->bmatr_.get_block(j, i0, j0);
1286  is_gap = BM_IS_GAP(blk);
1287  }
1288  if (!blk)
1289  continue;
1290  nbit = unsigned(k & bm::set_block_mask);
1291  if (is_gap)
1292  {
1293  is_set = bm::gap_test_unr(BMGAP_PTR(blk), nbit);
1294  }
1295  else
1296  {
1297  if (blk == FULL_BLOCK_FAKE_ADDR)
1298  {
1299  is_set = 1;
1300  }
1301  else
1302  {
1303  BM_ASSERT(!IS_FULL_BLOCK(blk));
1304  nword = unsigned(nbit >> bm::set_word_shift);
1305  mask0 = 1u << (nbit & bm::set_word_mask);
1306  is_set = (blk[nword] & mask0);
1307  }
1308  }
1309  size_type idx = k - offset;
1310  value_type vm = (bool) is_set;
1311  vm <<= j;
1312  arr[idx] |= vm;
1313 
1314  } // for k
1315 
1316  } // for j
1317  return 0;
1318 }
1319 
1320 //---------------------------------------------------------------------
1321 
1322 template<class Val, class BV>
1325  size_type size,
1326  size_type offset,
1327  bool zero_mem) const
1328 {
1329  if (size == 0)
1330  return 0;
1331 
1332  if (zero_mem)
1333  ::memset(arr, 0, sizeof(value_type)*size);
1334 
1335  size_type start = offset;
1336  size_type end = start + size;
1337  if (end > this->size_)
1338  {
1339  end = this->size_;
1340  }
1341 
1342  for (size_type i = 0; i < parent_type::value_bits(); ++i)
1343  {
1344  const bvector_type* bv = this->bmatr_.get_row(i);
1345  if (!bv)
1346  continue;
1347 
1348  value_type mask = 1;
1349  mask <<= i;
1350  typename BV::enumerator en(bv, offset);
1351  for (;en.valid(); ++en)
1352  {
1353  size_type idx = *en - offset;
1354  if (idx >= size)
1355  break;
1356  arr[idx] |= mask;
1357  } // for
1358 
1359  } // for i
1360 
1361  return 0;
1362 }
1363 
1364 
1365 //---------------------------------------------------------------------
1366 
1367 template<class Val, class BV>
1370  size_type size,
1371  size_type offset,
1372  bool zero_mem) const BMNOEXCEPT2
1373 {
1374  /// Decoder functor
1375  /// @internal
1376  ///
1377  struct sv_decode_visitor_func
1378  {
1379  sv_decode_visitor_func(value_type* BMRESTRICT varr,
1380  value_type mask,
1381  size_type off) BMNOEXCEPT2
1382  : arr_(varr), mask_(mask), sv_off_(off)
1383  {}
1384 
1385  void add_bits(size_type bv_offset,
1386  const unsigned char* bits, unsigned bits_size) BMNOEXCEPT
1387  {
1388  // can be negative (-1) when bv base offset = 0 and sv = 1,2..
1389  size_type base = bv_offset - sv_off_;
1390  value_type m = mask_;
1391  for (unsigned i = 0; i < bits_size; ++i)
1392  arr_[bits[i] + base] |= m;
1393  }
1394  void add_range(size_type bv_offset, size_type sz) BMNOEXCEPT
1395  {
1396  auto base = bv_offset - sv_off_;
1397  value_type m = mask_;
1398  for (size_type i = 0; i < sz; ++i)
1399  arr_[i + base] |= m;
1400  }
1401 
1402  value_type* BMRESTRICT arr_; ///< target array for reverse transpose
1403  value_type mask_; ///< bit-plane mask
1404  size_type sv_off_; ///< SV read offset
1405  };
1406 
1407  if (!size)
1408  return 0;
1409 
1410  if (zero_mem)
1411  ::memset(arr, 0, sizeof(value_type)*size);
1412 
1413  size_type end = offset + size;
1414  if (end > this->size_)
1415  end = this->size_;
1416 
1417  sv_decode_visitor_func func(arr, 0, offset);
1418 
1419  for (size_type i = 0; i < parent_type::value_bits(); ++i)
1420  {
1421  const bvector_type* bv = this->bmatr_.get_row(i);
1422  if (!bv)
1423  continue;
1424  func.mask_ = (value_type(1) << i); // set target plane OR mask
1425  bm::for_each_bit_range_no_check(*bv, offset, end-1, func);
1426  } // for i
1427  return end - offset;
1428 }
1429 
1430 //---------------------------------------------------------------------
1431 
1432 template<class Val, class BV>
1435 {
1436  if (idx >= this->size_)
1437  throw_range_error("sparse vector range error");
1438  return this->get(idx);
1439 }
1440 
1441 //---------------------------------------------------------------------
1442 
1443 template<class Val, class BV>
1447 {
1448  BM_ASSERT(i < bm::id_max);
1449  BM_ASSERT(i < size());
1450 
1451  value_type v = 0;
1452  unsigned eff_plains = this->effective_plains();
1453  for (unsigned j = 0; j < eff_plains; j+=4)
1454  {
1455  bool b = this->bmatr_.test_4rows(j);
1456  if (b)
1457  {
1458  value_type vm = (value_type)this->bmatr_.get_half_octet(i, j);
1459  v |= vm << j;
1460  }
1461  } // for j
1462  return v;
1463 }
1464 
1465 
1466 //---------------------------------------------------------------------
1467 
1468 template<class Val, class BV>
1470 {
1471  if (idx >= size())
1472  {
1473  this->size_ = idx+1;
1474  }
1475  set_value(idx, v);
1476 }
1477 
1478 //---------------------------------------------------------------------
1479 
1480 template<class Val, class BV>
1482 {
1483  if (idx >= size())
1484  this->size_ = idx+1;
1485 
1486  set_value(idx, (value_type)0);
1487  if (set_null)
1488  {
1489  bvector_type* bv_null = this->get_null_bvect();
1490  if (bv_null)
1491  bv_null->set(idx, false);
1492  }
1493 }
1494 
1495 //---------------------------------------------------------------------
1496 
1497 template<class Val, class BV>
1499 {
1500  set_value(this->size_, v);
1501  ++(this->size_);
1502 }
1503 
1504 //---------------------------------------------------------------------
1505 
1506 template<class Val, class BV>
1508 {
1509  BM_ASSERT(count);
1510  BM_ASSERT(bm::id_max - count > this->size_);
1511  BM_ASSERT(this->is_nullable());
1512 
1513  this->size_ += count;
1514 }
1515 
1516 
1517 //---------------------------------------------------------------------
1518 
1519 template<class Val, class BV>
1521 {
1522  if (idx >= size())
1523  {
1524  this->size_ = idx+1;
1525  set_value(idx, v);
1526  return;
1527  }
1528  insert_value(idx, v);
1529 }
1530 
1531 //---------------------------------------------------------------------
1532 
1533 template<class Val, class BV>
1535 {
1536  insert_value_no_null(idx, v);
1537  this->insert_null(idx, true);
1538 }
1539 
1540 //---------------------------------------------------------------------
1541 
1542 template<class Val, class BV>
1544 {
1545  unsigned bsr = v ? bm::bit_scan_reverse(v) : 0u;
1546  value_type mask = 1u;
1547  unsigned i = 0;
1548  for (; i <= bsr; ++i)
1549  {
1550  if (v & mask)
1551  {
1552  bvector_type* bv = this->get_plain(i);
1553  bv->insert(idx, true);
1554  }
1555  else
1556  {
1557  bvector_type_ptr bv = this->bmatr_.get_row(i);
1558  if (bv)
1559  bv->insert(idx, false);
1560  }
1561  mask <<= 1;
1562  } // for i
1563  // insert 0 into all other existing plains
1564  unsigned eff_plains = this->effective_plains();
1565  for (; i < eff_plains; ++i)
1566  {
1567  bvector_type* bv = this->bmatr_.get_row(i);
1568  if (bv)
1569  bv->insert(idx, false);
1570  } // for i
1571 
1572  this->size_++;
1573 }
1574 
1575 //---------------------------------------------------------------------
1576 
1577 template<class Val, class BV>
1579 {
1580  BM_ASSERT(idx < this->size_);
1581  if (idx >= this->size_)
1582  return;
1583  this->erase_column(idx);
1584  this->size_--;
1585 }
1586 
1587 
1588 //---------------------------------------------------------------------
1589 
1590 template<class Val, class BV>
1592 {
1593  set_value_no_null(this->size_, v);
1594  ++(this->size_);
1595 }
1596 
1597 //---------------------------------------------------------------------
1598 
1599 template<class Val, class BV>
1601 {
1602  set_value_no_null(idx, v);
1603  bvector_type* bv_null = this->get_null_bvect();
1604  if (bv_null)
1605  bv_null->set_bit_no_check(idx);
1606 }
1607 
1608 //---------------------------------------------------------------------
1609 
1610 template<class Val, class BV>
1612 {
1613  // calculate logical block coordinates and masks
1614  //
1615  block_idx_type nb = (idx >> bm::set_block_shift);
1616  unsigned i0 = unsigned(nb >> bm::set_array_shift); // top block address
1617  unsigned j0 = unsigned(nb & bm::set_array_mask); // address in sub-block
1618 
1619  // clear the plains where needed
1620  unsigned eff_plains = this->effective_plains();
1621  unsigned bsr = v ? bm::bit_scan_reverse(v) : 0u;
1622 
1623  for (unsigned i = bsr; i < eff_plains; ++i)
1624  {
1625  const bm::word_t* blk = this->bmatr_.get_block(i, i0, j0);
1626  if (blk)
1627  {
1628  bvector_type* bv = this->bmatr_.get_row(i);
1629  if (bv)
1630  bv->clear_bit_no_check(idx);
1631  }
1632  } // for i
1633 
1634  if (v)
1635  {
1636  value_type mask = 1u;
1637  for (unsigned j = 0; j <= bsr; ++j)
1638  {
1639  if (v & mask)
1640  {
1641  bvector_type* bv = this->get_plain(j);
1642  bv->set_bit_no_check(idx);
1643  }
1644  else
1645  {
1646  const bm::word_t* blk = this->bmatr_.get_block(j, i0, j0);
1647  if (blk)
1648  {
1649  bvector_type* bv = this->bmatr_.get_row(j);
1650  bv->clear_bit_no_check(idx);
1651  }
1652  }
1653  mask <<= 1;
1654  } // for j
1655  }
1656 }
1657 
1658 //---------------------------------------------------------------------
1659 
1660 template<class Val, class BV>
1662 {
1663  if (idx >= this->size_)
1664  this->size_ = idx+1;
1665 
1666  for (unsigned i = 0; i < parent_type::sv_value_plains; ++i)
1667  {
1668  bvector_type* bv = this->get_plain(i);
1669  bool carry_over = bv->inc(idx);
1670  if (!carry_over)
1671  break;
1672  }
1673  bvector_type* bv_null = this->get_null_bvect();
1674  if (bv_null)
1675  bv_null->set_bit_no_check(idx);
1676 }
1677 
1678 //---------------------------------------------------------------------
1679 
1680 template<class Val, class BV>
1682 {
1683  parent_type::clear();
1684 }
1685 
1686 //---------------------------------------------------------------------
1687 
1688 template<class Val, class BV>
1690 {
1691  BM_ASSERT(rank);
1692  pos = rank - 1;
1693  return true;
1694 }
1695 
1696 //---------------------------------------------------------------------
1697 
1698 template<class Val, class BV>
1701  typename sparse_vector<Val, BV>::size_type left,
1702  typename sparse_vector<Val, BV>::size_type right,
1703  bool set_null)
1704 {
1705  parent_type::clear_range(left, right, set_null);
1706  return *this;
1707 }
1708 
1709 //---------------------------------------------------------------------
1710 
1711 template<class Val, class BV>
1714 {
1715  BM_ASSERT(st);
1716  typename bvector_type::statistics stbv;
1717  parent_type::calc_stat(&stbv);
1718  if (st)
1719  {
1720  st->reset();
1721  st->add(stbv);
1722  }
1723 }
1724 
1725 //---------------------------------------------------------------------
1726 
1727 template<class Val, class BV>
1729  bm::word_t* temp_block,
1730  typename bvector_type::optmode opt_mode,
1732 {
1733  typename bvector_type::statistics stbv;
1734  stbv.reset();
1735  parent_type::optimize(temp_block, opt_mode, st ? &stbv : 0);
1736 
1737  if (st)
1738  {
1739  st->reset();
1740  st->add(stbv);
1741  }
1742 }
1743 
1744 //---------------------------------------------------------------------
1745 
1746 template<class Val, class BV>
1748 {
1749  unsigned stored_plains = this->stored_plains();
1750  for (unsigned j = 0; j < stored_plains; ++j)
1751  {
1752  bvector_type* bv = this->bmatr_.get_row(j);
1753  if (bv)
1754  {
1755  bv->optimize_gap_size();
1756  }
1757  }
1758 }
1759 
1760 //---------------------------------------------------------------------
1761 
1762 template<class Val, class BV>
1765 {
1766  size_type arg_size = sv.size();
1767  if (this->size_ < arg_size)
1768  {
1769  resize(arg_size);
1770  }
1771  bvector_type* bv_null = this->get_null_bvect();
1772  unsigned plains;
1773  if (bv_null)
1774  plains = this->stored_plains();
1775  else
1776  plains = this->plains();
1777 
1778  for (unsigned j = 0; j < plains; ++j)
1779  {
1780  const bvector_type* arg_bv = sv.bmatr_.row(j);
1781  if (arg_bv)
1782  {
1783  bvector_type* bv = this->bmatr_.get_row(j);
1784  if (!bv)
1785  bv = this->get_plain(j);
1786  *bv |= *arg_bv;
1787  }
1788  } // for j
1789 
1790  // our vector is NULL-able but argument is not (assumed all values are real)
1791  if (bv_null && !sv.is_nullable())
1792  {
1793  bv_null->set_range(0, arg_size-1);
1794  }
1795 
1796  return *this;
1797 }
1798 
1799 //---------------------------------------------------------------------
1800 
1801 template<class Val, class BV>
1804 {
1805  size_type arg_size = sv.size();
1806  if (this->size_ < arg_size)
1807  {
1808  resize(arg_size);
1809  }
1810  bvector_type* bv_null = this->get_null_bvect();
1811  unsigned plains;
1812  if (bv_null)
1813  plains = this->stored_plains();
1814  else
1815  plains = this->plains();
1816 
1817  for (unsigned j = 0; j < plains; ++j)
1818  {
1819  bvector_type* arg_bv = sv.bmatr_.get_row(j);//sv.plains_[j];
1820  if (arg_bv)
1821  {
1822  bvector_type* bv = this->bmatr_.get_row(j);//this->plains_[j];
1823  if (!bv)
1824  bv = this->get_plain(j);
1825  bv->merge(*arg_bv);
1826  }
1827  } // for j
1828 
1829  // our vector is NULL-able but argument is not (assumed all values are real)
1830  if (bv_null && !sv.is_nullable())
1831  {
1832  bv_null->set_range(0, arg_size-1);
1833  }
1834 
1835  return *this;
1836 }
1837 
1838 //---------------------------------------------------------------------
1839 
1840 template<class Val, class BV>
1842  typename sparse_vector<Val, BV>::size_type left,
1843  typename sparse_vector<Val, BV>::size_type right,
1844  bm::null_support splice_null)
1845 {
1846  if (left > right)
1847  bm::xor_swap(left, right);
1848  //this->clear();
1849  this->copy_range_plains(sv, left, right, splice_null);
1850  this->resize(sv.size());
1851 }
1852 //---------------------------------------------------------------------
1853 
1854 template<class Val, class BV>
1856  const typename sparse_vector<Val, BV>::bvector_type& bv_mask)
1857 {
1858  bvector_type* bv_null = this->get_null_bvect();
1859  unsigned plains;
1860  if (bv_null)
1861  {
1862  plains = this->stored_plains();
1863  bv_null->bit_and(bv_mask);
1864  }
1865  else
1866  plains = this->plains();
1867 
1868  for (unsigned j = 0; j < plains; ++j)
1869  {
1870  bvector_type* bv = this->bmatr_.get_row(j);
1871  if (bv)
1872  bv->bit_and(bv_mask);
1873  }
1874 }
1875 
1876 //---------------------------------------------------------------------
1877 
1878 template<class Val, class BV>
1880  const value_type val) const BMNOEXCEPT
1881 {
1882  // TODO: consider bit-by-bit comparison to minimize CPU hit miss in plans get()
1883  value_type sv_value = get(idx);
1884  return (sv_value > val) - (sv_value < val);
1885 }
1886 
1887 //---------------------------------------------------------------------
1888 
1889 template<class Val, class BV>
1891  bm::null_support null_able) const BMNOEXCEPT
1892 {
1893  return parent_type::equal(sv, null_able);
1894 }
1895 
1896 //---------------------------------------------------------------------
1897 
1898 template<class Val, class BV>
1901 {
1902  typedef typename sparse_vector<Val, BV>::const_iterator it_type;
1903  return it_type(this);
1904 }
1905 
1906 //---------------------------------------------------------------------
1907 
1908 template<class Val, class BV>
1911 {
1912  this->bmatr_.set_allocator_pool(pool_ptr);
1913 }
1914 
1915 
1916 //---------------------------------------------------------------------
1917 //
1918 //---------------------------------------------------------------------
1919 
1920 
1921 template<class Val, class BV>
1923 : sv_(0), pos_(bm::id_max), buf_ptr_(0)
1924 {}
1925 
1926 //---------------------------------------------------------------------
1927 
1928 template<class Val, class BV>
1931 : sv_(it.sv_), pos_(it.pos_), buf_ptr_(0)
1932 {}
1933 
1934 //---------------------------------------------------------------------
1935 
1936 template<class Val, class BV>
1939  ) BMNOEXCEPT
1940 : sv_(sv), buf_ptr_(0)
1941 {
1942  BM_ASSERT(sv_);
1943  pos_ = sv_->empty() ? bm::id_max : 0u;
1944 }
1945 
1946 //---------------------------------------------------------------------
1947 
1948 template<class Val, class BV>
1949 sparse_vector<Val, BV>::const_iterator::const_iterator(
1950  const typename sparse_vector<Val, BV>::const_iterator::sparse_vector_type* sv,
1951  typename sparse_vector<Val, BV>::size_type pos) BMNOEXCEPT
1952 : sv_(sv), buf_ptr_(0)
1953 {
1954  BM_ASSERT(sv_);
1955  this->go_to(pos);
1956 }
1957 
1958 //---------------------------------------------------------------------
1959 
1960 template<class Val, class BV>
1962 {
1963  pos_ = (!sv_ || pos >= sv_->size()) ? bm::id_max : pos;
1964  buf_ptr_ = 0;
1965 }
1966 
1967 //---------------------------------------------------------------------
1968 
1969 template<class Val, class BV>
1971 {
1972  if (pos_ == bm::id_max) // nothing to do, we are at the end
1973  return false;
1974  ++pos_;
1975  if (pos_ >= sv_->size())
1976  {
1977  this->invalidate();
1978  return false;
1979  }
1980  if (buf_ptr_)
1981  {
1982  ++buf_ptr_;
1983  if (buf_ptr_ - ((value_type*)buffer_.data()) >= n_buf_size)
1984  buf_ptr_ = 0;
1985  }
1986  return true;
1987 }
1988 
1989 //---------------------------------------------------------------------
1990 
1991 template<class Val, class BV>
1994 {
1995  BM_ASSERT(this->valid());
1996  value_type v;
1997 
1998  if (!buf_ptr_)
1999  {
2000  buffer_.reserve(n_buf_size * sizeof(value_type));
2001  buf_ptr_ = (value_type*)(buffer_.data());
2002  sv_->extract(buf_ptr_, n_buf_size, pos_, true);
2003  }
2004  v = *buf_ptr_;
2005  return v;
2006 }
2007 
2008 //---------------------------------------------------------------------
2009 
2010 template<class Val, class BV>
2012 {
2013  value_type v = value();
2014  if (buf_ptr_)
2015  {
2016  v = *buf_ptr_;
2017  value_type* buf_end = ((value_type*)buffer_.data()) + n_buf_size;
2018  while(!v)
2019  {
2020  ++pos_;
2021  if (++buf_ptr_ < buf_end)
2022  v = *buf_ptr_;
2023  else
2024  break;
2025  }
2026  if (pos_ >= sv_->size())
2027  {
2028  pos_ = bm::id_max;
2029  return;
2030  }
2031  if (buf_ptr_ >= buf_end)
2032  buf_ptr_ = 0;
2033  }
2034 }
2035 
2036 //---------------------------------------------------------------------
2037 
2038 template<class Val, class BV>
2040 {
2041  return sv_->is_null(pos_);
2042 }
2043 
2044 
2045 //---------------------------------------------------------------------
2046 //
2047 //---------------------------------------------------------------------
2048 
2049 
2050 template<class Val, class BV>
2052 : sv_(0), bv_null_(0), buf_ptr_(0), prev_nb_(0), set_not_null_(true)
2053 {}
2054 
2055 //---------------------------------------------------------------------
2056 
2057 template<class Val, class BV>
2060 : sv_(sv), buf_ptr_(0), set_not_null_(true)
2061 {
2062  if (sv)
2063  {
2064  prev_nb_ = sv_->size() >> bm::set_block_shift;
2065  bv_null_ = sv_->get_null_bvect();
2066  }
2067  else
2068  {
2069  bv_null_ = 0; prev_nb_ = 0;
2070  }
2071 }
2072 
2073 //---------------------------------------------------------------------
2074 
2075 template<class Val, class BV>
2078 : sv_(bi.sv_), bv_null_(bi.bv_null_), buf_ptr_(0), prev_nb_(bi.prev_nb_),
2079  set_not_null_(bi.set_not_null_)
2080 {
2081  BM_ASSERT(bi.empty());
2082 }
2083 
2084 //---------------------------------------------------------------------
2085 
2086 template<class Val, class BV>
2088 {
2089  this->flush();
2090 }
2091 
2092 //---------------------------------------------------------------------
2093 
2094 template<class Val, class BV>
2097 {
2098  size_type buf_idx = this->add_value_no_null(v);
2099  if (bv_null_)
2100  {
2101  typename sparse_vector<Val, BV>::size_type sz = sv_->size();
2102  bv_null_->set_bit_no_check(sz + buf_idx);
2103  }
2104 }
2105 
2106 //---------------------------------------------------------------------
2107 
2108 template<class Val, class BV>
2112 {
2113  BM_ASSERT(sv_);
2114  if (!buf_ptr_) // not allocated (yet)
2115  {
2116  buffer_.reserve(n_buf_size * sizeof(value_type));
2117  buf_ptr_ = (value_type*)(buffer_.data());
2118  *buf_ptr_ = v;
2119  ++buf_ptr_;
2120  return 0;
2121  }
2122  if (buf_ptr_ - ((value_type*)buffer_.data()) >= n_buf_size)
2123  {
2124  this->flush();
2125  buf_ptr_ = (value_type*)(buffer_.data());
2126  }
2127 
2128  *buf_ptr_ = v;
2129  size_type buf_idx = size_type(buf_ptr_ - ((value_type*)buffer_.data()));
2130  ++buf_ptr_;
2131  return buf_idx;
2132 }
2133 
2134 //---------------------------------------------------------------------
2135 
2136 template<class Val, class BV>
2138 {
2139  BM_ASSERT(bv_null_);
2140  this->add_value_no_null(value_type(0));
2141 }
2142 
2143 //---------------------------------------------------------------------
2144 
2145 template<class Val, class BV>
2148 {
2149  if (count < 32)
2150  {
2151  for (size_type i = 0; i < count; ++i)
2152  this->add_value_no_null(value_type(0));
2153  }
2154  else
2155  {
2156  this->flush();
2157  sv_->push_back_null(count);
2158  }
2159 }
2160 
2161 //---------------------------------------------------------------------
2162 
2163 template<class Val, class BV>
2165 {
2166  return (!buf_ptr_ || !sv_);
2167 }
2168 
2169 //---------------------------------------------------------------------
2170 
2171 template<class Val, class BV>
2173 {
2174  if (this->empty())
2175  return;
2176  value_type* d = (value_type*)buffer_.data();
2177  sv_->import_back(d, size_type(buf_ptr_ - d), false); //!set_not_null_);
2178  buf_ptr_ = 0;
2179  block_idx_type nb = sv_->size() >> bm::set_block_shift;
2180  if (nb != prev_nb_)
2181  {
2182  // optimize all previous blocks in all planes
2183  sv_->optimize_block(prev_nb_);
2184  prev_nb_ = nb;
2185  }
2186 }
2187 
2188 //---------------------------------------------------------------------
2189 
2190 
2191 } // namespace bm
2192 
2193 #include "bmundef.h"
2194 
2195 
2196 #endif
bm::bvector::inc
bool inc(size_type n)
Increment the specified element.
Definition: bm.h:3800
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:1700
bm::sparse_vector::push_back_null
void push_back_null(size_type count)
push back specified amount of NULL values
Definition: bmsparsevec.h:1507
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:2158
bm::sparse_vector::insert_value
void insert_value(size_type idx, value_type v)
insert value without checking boundaries
Definition: bmsparsevec.h:1534
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:1728
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:1611
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:2051
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:1922
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:5017
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::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:3468
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:1591
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:1543
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:978
bm::sparse_vector::back_insert_iterator::flush
void flush()
flush the accumulated buffer
Definition: bmsparsevec.h:2172
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:2095
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:1890
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:1909
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:554
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:1369
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:1879
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:1095
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:8546
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:3581
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:986
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:1244
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:909
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:952
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:8572
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:2137
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:1961
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:8471
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:819
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:1747
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:1578
bm::sparse_vector::calc_stat
void calc_stat(struct sparse_vector< Val, BV >::statistics *st) const BMNOEXCEPT
Calculates memory statistics.
Definition: bmsparsevec.h:1712
bm::sparse_vector::back_insert_iterator::empty
bool empty() const
return true if insertion buffer is empty
Definition: bmsparsevec.h:2164
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:1900
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:1445
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:1520
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:4378
bmdef.h
Definitions(internal)
bm::sparse_vector::push_back
void push_back(value_type v)
push value back into vector
Definition: bmsparsevec.h:1498
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:2110
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:922
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:1298
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:2011
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:1841
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:1803
bm::sparse_vector::const_iterator::advance
bool advance() BMNOEXCEPT
advance iterator forward by one
Definition: bmsparsevec.h:1970
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:1220
bm::bvector::clear_bit_no_check
void clear_bit_no_check(size_type n)
Clears bit n without precondiion checks.
Definition: bm.h:1211
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:1434
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:4724
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:3117
bm::sparse_vector::throw_range_error
static void throw_range_error(const char *err_msg)
throw range error
Definition: bmsparsevec.h:966
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:1083
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:1324
bm::sparse_vector::clear
void clear() BMNOEXCEPT
resize to zero, free memory
Definition: bmsparsevec.h:1681
bm::sparse_vector::back_insert_iterator::~back_insert_iterator
~back_insert_iterator()
Definition: bmsparsevec.h:2087
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:1855
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:1072
bm::sparse_vector::set_value
void set_value(size_type idx, value_type v)
set value without checking boundaries
Definition: bmsparsevec.h:1600
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:1764
bm::sparse_vector::const_iterator::value
value_type value() const
Get current position (value)
Definition: bmsparsevec.h:1993
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:2039
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:1469
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:1661
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:958
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:1689
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