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