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  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
258  typedef sparse_vector_type* sparse_vector_type_ptr;
264  typedef bm::byte_buffer<allocator_type> buffer_type;
265 
266  typedef void difference_type;
267  typedef void pointer;
268  typedef void reference;
269 
270  public:
272  back_insert_iterator(sparse_vector_type* sv);
274 
276  {
277  BM_ASSERT(bi.empty());
278  this->flush(); sv_ = bi.sv_; 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  */
323  size_type add_value_no_null(value_type v);
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  */
373  allocation_policy_type ap = allocation_policy_type(),
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_all(true);
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  */
422  value_type operator[](size_type idx) const BMNOEXCEPT
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 */
493  const_iterator end() const BMNOEXCEPT
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  */
499  const_iterator get_const_iterator(size_type idx) const BMNOEXCEPT
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  */
577  size_type decode(value_type* arr,
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  */
608  size_type gather(value_type* arr,
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_all(bool free_mem) BMNOEXCEPT;
624 
625  /*! \brief resize to zero, free memory */
626  void clear() BMNOEXCEPT { clear_all(true); }
627 
628  /*!
629  \brief clear range (assign bit 0 for all plains)
630  \param left - interval start
631  \param right - interval end (closed interval)
632  \param set_null - set cleared values to unassigned (NULL)
633  */
634  sparse_vector<Val, BV>& clear_range(size_type left,
635  size_type right,
636  bool set_null = false);
637 
638  ///@}
639 
640  // ------------------------------------------------------------
641  /*! @name Size, etc */
642  ///@{
643 
644  /*! \brief return size of the vector
645  \return size of sparse vector
646  */
647  size_type size() const BMNOEXCEPT { return this->size_; }
648 
649  /*! \brief return true if vector is empty
650  \return true if empty
651  */
652  bool empty() const BMNOEXCEPT { return (size() == 0); }
653 
654  /*! \brief resize vector
655  \param sz - new size
656  */
657  void resize(size_type sz) { parent_type::resize(sz); }
658 
659  /**
660  \brief recalculate size to exclude tail NULL elements
661  After this call size() will return the true size of the vector
662  */
663  void sync_size() BMNOEXCEPT;
664 
665  ///@}
666 
667  // ------------------------------------------------------------
668  /*! @name Comparison */
669  ///@{
670 
671  /*!
672  \brief check if another sparse vector has the same content and size
673 
674  \param sv - sparse vector for comparison
675  \param null_able - flag to consider NULL vector in comparison (default)
676  or compare only value content plains
677 
678  \return true, if it is the same
679  */
680  bool equal(const sparse_vector<Val, BV>& sv,
681  bm::null_support null_able = bm::use_null) const BMNOEXCEPT;
682 
683  ///@}
684 
685  // ------------------------------------------------------------
686  /*! @name Element comparison */
687  ///@{
688 
689  /**
690  \brief Compare vector element with argument
691 
692  \param idx - vactor element index
693  \param val - argument to compare with
694 
695  \return 0 - equal, < 0 - vect[i] < str, >0 otherwise
696  */
697  int compare(size_type idx, const value_type val) const BMNOEXCEPT;
698 
699  ///@}
700 
701  // ------------------------------------------------------------
702  /*! @name Memory optimization */
703  ///@{
704 
705  /*!
706  \brief run memory optimization for all vector plains
707  \param temp_block - pre-allocated memory block to avoid unnecessary re-allocs
708  \param opt_mode - requested compression depth
709  \param stat - memory allocation statistics after optimization
710  */
711  void optimize(bm::word_t* temp_block = 0,
713  typename sparse_vector<Val, BV>::statistics* stat = 0);
714 
715  /*!
716  \brief Optimize sizes of GAP blocks
717 
718  This method runs an analysis to find optimal GAP levels for all bit plains
719  of the vector.
720  */
721  void optimize_gap_size();
722 
723  /*!
724  @brief Calculates memory statistics.
725 
726  Function fills statistics structure containing information about how
727  this vector uses memory and estimation of max. amount of memory
728  bvector needs to serialize itself.
729 
730  @param st - pointer on statistics structure to be filled in.
731 
732  @sa statistics
733  */
734  void calc_stat(
736  ///@}
737 
738  // ------------------------------------------------------------
739  /*! @name Merge, split, partition data */
740  ///@{
741 
742  /*!
743  \brief join all with another sparse vector using OR operation
744  \param sv - argument vector to join with
745  \return slf reference
746  @sa merge
747  */
749 
750  /*!
751  \brief merge with another sparse vector using OR operation
752  Merge is different from join(), because it borrows data from the source
753  vector, so it gets modified.
754 
755  \param sv - [in, out]argument vector to join with (vector mutates)
756 
757  \return slf reference
758  @sa join
759  */
761 
762 
763  /**
764  @brief copy range of values from another sparse vector
765 
766  Copy [left..right] values from the source vector,
767  clear everything outside the range.
768 
769  \param sv - source vector
770  \param left - index from in losed diapason of [left..right]
771  \param right - index to in losed diapason of [left..right]
772  \param splice_null - "use_null" copy range for NULL vector or
773  do not copy it
774  */
775  void copy_range(const sparse_vector<Val, BV>& sv,
776  size_type left, size_type right,
777  bm::null_support splice_null = bm::use_null);
778 
779  /**
780  @brief Apply value filter, defined by mask vector
781 
782  All bit-plains are ANDed against the filter mask.
783  */
784  void filter(const bvector_type& bv_mask);
785 
786  ///@}
787 
788 
789  // ------------------------------------------------------------
790  /*! @name Access to internals */
791  ///@{
792 
793 
794  /*! \brief syncronize internal structures */
795  void sync(bool /*force*/) {}
796 
797 
798  /*!
799  \brief Bulk export list of elements to a C-style array
800 
801  Use of all extract() methods is restricted.
802  Please consider decode() for the same purpose.
803 
804  \param arr - dest array
805  \param size - dest size
806  \param offset - target index in the sparse vector to export from
807  \param zero_mem - set to false if target array is pre-initialized
808  with 0s to avoid performance penalty
809  \return number of exported elements
810 
811  \sa decode
812 
813  @internal
814  */
815  size_type extract(value_type* arr,
816  size_type size,
817  size_type offset = 0,
818  bool zero_mem = true) const BMNOEXCEPT2;
819 
820  /** \brief extract small window without use of masking vector
821  \sa decode
822  @internal
823  */
824  size_type extract_range(value_type* arr,
825  size_type size,
826  size_type offset,
827  bool zero_mem = true) const;
828 
829  /** \brief extract medium window without use of masking vector
830  \sa decode
831  @internal
832  */
833  size_type extract_plains(value_type* arr,
834  size_type size,
835  size_type offset,
836  bool zero_mem = true) const;
837 
838  /** \brief address translation for this type of container
839  \internal
840  */
841  static
842  size_type translate_address(size_type i) BMNOEXCEPT { return i; }
843 
844  /**
845  \brief throw range error
846  \internal
847  */
848  static
849  void throw_range_error(const char* err_msg);
850 
851  /**
852  \brief throw bad alloc
853  \internal
854  */
855  static
856  void throw_bad_alloc();
857 
858 
859  /**
860  \brief find position of compressed element by its rank
861  */
862  static
863  bool find_rank(size_type rank, size_type& pos) BMNOEXCEPT;
864 
865  /**
866  \brief size of sparse vector (may be different for RSC)
867  */
868  size_type effective_size() const BMNOEXCEPT { return size(); }
869 
870  /**
871  \brief Always 1 (non-matrix type)
872  */
873  size_type effective_vector_max() const BMNOEXCEPT { return 1; }
874 
875  ///@}
876 
877  /// Set allocator pool for local (non-threaded)
878  /// memory cyclic(lots of alloc-free ops) opertations
879  ///
880  void set_allocator_pool(allocator_pool_type* pool_ptr) BMNOEXCEPT;
881 
882 protected:
884  {
886  };
887 
888 
889  /*! \brief set value without checking boundaries */
890  void set_value(size_type idx, value_type v);
891 
892  /*! \brief set value without checking boundaries or support of NULL */
893  void set_value_no_null(size_type idx, value_type v);
894 
895  /*! \brief push value back into vector without NULL semantics */
896  void push_back_no_null(value_type v);
897 
898  /*! \brief insert value without checking boundaries */
899  void insert_value(size_type idx, value_type v);
900  /*! \brief insert value without checking boundaries or support of NULL */
901  void insert_value_no_null(size_type idx, value_type v);
902 
903  void resize_internal(size_type sz) { resize(sz); }
904  size_type size_internal() const BMNOEXCEPT { return size(); }
905 
906  bool is_remap() const BMNOEXCEPT { return false; }
907  size_t remap_size() const BMNOEXCEPT { return 0; }
908  const unsigned char* get_remap_buffer() const BMNOEXCEPT { return 0; }
909  unsigned char* init_remap_buffer() BMNOEXCEPT { return 0; }
910  void set_remap() BMNOEXCEPT { }
911 
912  bool resolve_range(size_type from, size_type to,
913  size_type* idx_from, size_type* idx_to) const BMNOEXCEPT
914  {
915  *idx_from = from; *idx_to = to; return true;
916  }
917 
918  /// Increment element by 1 without chnaging NULL vector or size
919  void inc_no_null(size_type idx);
920 
921  /// increment by v without chnaging NULL vector or size
922  void inc_no_null(size_type idx, value_type v);
923 
924 protected:
925  template<class V, class SV> friend class rsc_sparse_vector;
926  template<class SVect> friend class sparse_vector_scanner;
927  template<class SVect> friend class sparse_vector_serializer;
928  template<class SVect> friend class sparse_vector_deserializer;
929 
930 };
931 
932 
933 //---------------------------------------------------------------------
934 //---------------------------------------------------------------------
935 
936 
937 template<class Val, class BV>
939  bm::null_support null_able,
940  allocation_policy_type ap,
941  size_type bv_max_size,
942  const allocator_type& alloc)
943 : parent_type(null_able, ap, bv_max_size, alloc)
944 {}
945 
946 //---------------------------------------------------------------------
947 
948 template<class Val, class BV>
950 : parent_type(sv)
951 {}
952 
953 //---------------------------------------------------------------------
954 #ifndef BM_NO_CXX11
955 
956 template<class Val, class BV>
958 {
959  parent_type::swap(sv);
960 }
961 
962 #endif
963 
964 
965 //---------------------------------------------------------------------
966 
967 template<class Val, class BV>
969 {}
970 
971 //---------------------------------------------------------------------
972 
973 template<class Val, class BV>
975 {
976  parent_type::swap(sv);
977 }
978 
979 //---------------------------------------------------------------------
980 
981 template<class Val, class BV>
983 {
984 #ifndef BM_NO_STL
985  throw std::range_error(err_msg);
986 #else
987  BM_ASSERT_THROW(false, BM_ERR_RANGE);
988 #endif
989 }
990 
991 //---------------------------------------------------------------------
992 
993 template<class Val, class BV>
995 {
996  BV::throw_bad_alloc();
997 }
998 
999 //---------------------------------------------------------------------
1000 
1001 template<class Val, class BV>
1003 {
1004  clear(idx, true);
1005 }
1006 
1007 //---------------------------------------------------------------------
1008 
1009 template<class Val, class BV>
1010 void sparse_vector<Val, BV>::import(const value_type* arr,
1011  size_type arr_size,
1012  size_type offset,
1013  bool set_not_null)
1014 {
1015  unsigned char b_list[sizeof(Val)*8];
1016  unsigned row_len[sizeof(Val)*8] = {0, };
1017 
1018  const unsigned transpose_window = 256;
1020 
1021  if (arr_size == 0)
1022  throw_range_error("sparse_vector range error (import size 0)");
1023 
1024  if (offset < this->size_) // in case it touches existing elements
1025  {
1026  // clear all plains in the range to provide corrrect import of 0 values
1027  this->clear_range(offset, offset + arr_size - 1);
1028  }
1029 
1030  // transposition algorithm uses bitscan to find index bits and store it
1031  // in temporary matrix (list for each bit plain), matrix here works
1032  // when array gets to big - the list gets loaded into bit-vector using
1033  // bulk load algorithm, which is faster than single bit access
1034  //
1035 
1036  size_type i;
1037  for (i = 0; i < arr_size; ++i)
1038  {
1039  unsigned bcnt = bm::bitscan(arr[i], b_list);
1040  const size_type bit_idx = i + offset;
1041 
1042  for (unsigned j = 0; j < bcnt; ++j)
1043  {
1044  unsigned p = b_list[j];
1045  unsigned rl = row_len[p];
1046  tm.row(p)[rl] = bit_idx;
1047  row_len[p] = ++rl;
1048 
1049  if (rl == transpose_window)
1050  {
1051  bvector_type* bv = this->get_plain(p);
1052  const size_type* r = tm.row(p);
1053  bv->set(r, rl, BM_SORTED);
1054  row_len[p] = 0;
1055  tm.row(p)[0] = 0;
1056  }
1057  } // for j
1058  } // for i
1059 
1060  // process incomplete transposition lines
1061  //
1062  for (unsigned k = 0; k < tm.rows(); ++k)
1063  {
1064  unsigned rl = row_len[k];
1065  if (rl)
1066  {
1067  bvector_type* bv = this->get_plain(k);
1068  const size_type* r = tm.row(k);
1069  bv->set(r, rl, BM_SORTED);
1070  }
1071  } // for k
1072 
1073 
1074  if (i + offset > this->size_)
1075  this->size_ = i + offset;
1076 
1077  if (set_not_null)
1078  {
1079  bvector_type* bv_null = this->get_null_bvect();
1080  if (bv_null) // configured to support NULL assignments
1081  bv_null->set_range(offset, offset + arr_size - 1);
1082  }
1083 }
1084 
1085 //---------------------------------------------------------------------
1086 
1087 template<class Val, class BV>
1089 {
1090  const bvector_type* bv_null = this->get_null_bvector();
1091  if (!bv_null)
1092  return;
1093  bool found = bv_null->find_reverse(this->size_);
1094  this->size_ += found;
1095 }
1096 
1097 //---------------------------------------------------------------------
1098 
1099 template<class Val, class BV>
1100 void sparse_vector<Val, BV>::import_back(const value_type* arr,
1101  size_type arr_size,
1102  bool set_not_null)
1103 {
1104  this->import(arr, arr_size, this->size(), set_not_null);
1105 }
1106 
1107 //---------------------------------------------------------------------
1108 
1109 template<class Val, class BV>
1112  size_type idx_from,
1113  size_type dec_size,
1114  bool zero_mem) const
1115 {
1116  return extract(arr, dec_size, idx_from, zero_mem);
1117 }
1118 
1119 //---------------------------------------------------------------------
1120 
1121 template<class Val, class BV>
1124  const size_type* idx,
1125  size_type size,
1126  bm::sort_order sorted_idx) const
1127 {
1128  BM_ASSERT(arr);
1129  BM_ASSERT(idx);
1130  BM_ASSERT(size);
1131 
1132  if (size == 1) // corner case: get 1 value
1133  {
1134  arr[0] = this->get(idx[0]);
1135  return size;
1136  }
1137  ::memset(arr, 0, sizeof(value_type)*size);
1138 
1139  for (size_type i = 0; i < size;)
1140  {
1141  bool sorted_block = true;
1142 
1143  // look ahead for the depth of the same block
1144  // (speculate more than one index lookup per block)
1145  //
1146  block_idx_type nb = (idx[i] >> bm::set_block_shift);
1147  size_type r = i;
1148 
1149  switch (sorted_idx)
1150  {
1151  case BM_UNKNOWN:
1152  {
1153  size_type idx_prev = idx[r];
1154  for (; (r < size) && (nb == (idx[r] >> bm::set_block_shift)); ++r)
1155  {
1156  sorted_block = !(idx[r] < idx_prev); // sorted check
1157  idx_prev = idx[r];
1158  }
1159  }
1160  break;
1161  case BM_UNSORTED:
1162  sorted_block = false;
1163  for (; r < size; ++r)
1164  {
1165  block_idx_type nb_next = (idx[r] >> bm::set_block_shift);
1166  if (nb != nb_next)
1167  break;
1168  } // for r
1169  break;
1170  // no break(!) intentional fall through
1171  case BM_SORTED:
1172  #ifdef BM64ADDR
1173  r = bm::idx_arr_block_lookup_u64(idx, size, nb, r);
1174  #else
1175  r = bm::idx_arr_block_lookup_u32(idx, size, nb, r);
1176  #endif
1177  break;
1178  case BM_SORTED_UNIFORM:
1179  r = size;
1180  break;
1181  default:
1182  BM_ASSERT(0);
1183  } // switch
1184 
1185  // single element hit, use plain random access
1186  if (r == i+1)
1187  {
1188  arr[i] = this->get(idx[i]);
1189  ++i;
1190  continue;
1191  }
1192 
1193  // process block co-located elements at ones for best (CPU cache opt)
1194  //
1195  unsigned i0 = unsigned(nb >> bm::set_array_shift); // top block address
1196  unsigned j0 = unsigned(nb & bm::set_array_mask); // address in sub-block
1197 
1198  unsigned eff_plains = this->effective_plains(); // TODO: get real effective plains for [i,j]
1199  for (unsigned j = 0; j < eff_plains; ++j)
1200  {
1201  const bm::word_t* blk = this->bmatr_.get_block(j, i0, j0);
1202  if (!blk)
1203  continue;
1204  value_type vm;
1205  const value_type mask1 = 1;
1206 
1207  if (blk == FULL_BLOCK_FAKE_ADDR)
1208  {
1209  vm = (mask1 << j);
1210  for (size_type k = i; k < r; ++k)
1211  arr[k] |= vm;
1212  continue;
1213  }
1214  if (BM_IS_GAP(blk))
1215  {
1216  const bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
1217  unsigned is_set;
1218 
1219  if (sorted_block) // b-search hybrid with scan lookup
1220  {
1221  for (size_type k = i; k < r; )
1222  {
1223  unsigned nbit = unsigned(idx[k] & bm::set_block_mask);
1224 
1225  unsigned gidx = bm::gap_bfind(gap_blk, nbit, &is_set);
1226  unsigned gap_value = gap_blk[gidx];
1227  if (is_set)
1228  {
1229  arr[k] |= vm = (mask1 << j);
1230  for (++k; k < r; ++k) // speculative look-up
1231  {
1232  if (unsigned(idx[k] & bm::set_block_mask) <= gap_value)
1233  arr[k] |= vm;
1234  else
1235  break;
1236  }
1237  }
1238  else // 0 GAP - skip. not set
1239  {
1240  for (++k;
1241  (k < r) &&
1242  (unsigned(idx[k] & bm::set_block_mask) <= gap_value);
1243  ++k) {}
1244  }
1245  } // for k
1246  }
1247  else // unsorted block gather request: b-search lookup
1248  {
1249  for (size_type k = i; k < r; ++k)
1250  {
1251  unsigned nbit = unsigned(idx[k] & bm::set_block_mask);
1252  is_set = bm::gap_test_unr(gap_blk, nbit);
1253  arr[k] |= (value_type(bool(is_set)) << j);
1254  } // for k
1255  }
1256  continue;
1257  }
1258  bm::bit_block_gather_scatter(arr, blk, idx, r, i, j);
1259  } // for (each plain)
1260 
1261  i = r;
1262 
1263  } // for i
1264 
1265  return size;
1266 }
1267 
1268 //---------------------------------------------------------------------
1269 
1270 template<class Val, class BV>
1273  size_type size,
1274  size_type offset,
1275  bool zero_mem) const
1276 {
1277  if (size == 0)
1278  return 0;
1279  if (zero_mem)
1280  ::memset(arr, 0, sizeof(value_type)*size);
1281 
1282  size_type start = offset;
1283  size_type end = start + size;
1284  if (end > this->size_)
1285  {
1286  end = this->size_;
1287  }
1288 
1289  // calculate logical block coordinates and masks
1290  //
1291  block_idx_type nb = (start >> bm::set_block_shift);
1292  unsigned i0 = unsigned(nb >> bm::set_array_shift); // top block address
1293  unsigned j0 = unsigned(nb & bm::set_array_mask); // address in sub-block
1294  unsigned nbit = unsigned(start & bm::set_block_mask);
1295  unsigned nword = unsigned(nbit >> bm::set_word_shift);
1296  unsigned mask0 = 1u << (nbit & bm::set_word_mask);
1297  const bm::word_t* blk = 0;
1298  unsigned is_set;
1299 
1300  for (unsigned j = 0; j < sizeof(Val)*8; ++j)
1301  {
1302  blk = this->bmatr_.get_block(j, i0, j0);
1303  bool is_gap = BM_IS_GAP(blk);
1304 
1305  for (size_type k = start; k < end; ++k)
1306  {
1307  block_idx_type nb1 = (k >> bm::set_block_shift);
1308  if (nb1 != nb) // block switch boundaries
1309  {
1310  nb = nb1;
1311  i0 = unsigned(nb >> bm::set_array_shift);
1312  j0 = unsigned(nb & bm::set_array_mask);
1313  blk = this->bmatr_.get_block(j, i0, j0);
1314  is_gap = BM_IS_GAP(blk);
1315  }
1316  if (!blk)
1317  continue;
1318  nbit = unsigned(k & bm::set_block_mask);
1319  if (is_gap)
1320  {
1321  is_set = bm::gap_test_unr(BMGAP_PTR(blk), nbit);
1322  }
1323  else
1324  {
1325  if (blk == FULL_BLOCK_FAKE_ADDR)
1326  {
1327  is_set = 1;
1328  }
1329  else
1330  {
1331  BM_ASSERT(!IS_FULL_BLOCK(blk));
1332  nword = unsigned(nbit >> bm::set_word_shift);
1333  mask0 = 1u << (nbit & bm::set_word_mask);
1334  is_set = (blk[nword] & mask0);
1335  }
1336  }
1337  size_type idx = k - offset;
1338  value_type vm = (bool) is_set;
1339  vm <<= j;
1340  arr[idx] |= vm;
1341 
1342  } // for k
1343 
1344  } // for j
1345  return 0;
1346 }
1347 
1348 //---------------------------------------------------------------------
1349 
1350 template<class Val, class BV>
1353  size_type size,
1354  size_type offset,
1355  bool zero_mem) const
1356 {
1357  if (size == 0)
1358  return 0;
1359 
1360  if (zero_mem)
1361  ::memset(arr, 0, sizeof(value_type)*size);
1362 
1363  size_type start = offset;
1364  size_type end = start + size;
1365  if (end > this->size_)
1366  {
1367  end = this->size_;
1368  }
1369 
1370  for (size_type i = 0; i < parent_type::value_bits(); ++i)
1371  {
1372  const bvector_type* bv = this->bmatr_.get_row(i);
1373  if (!bv)
1374  continue;
1375 
1376  value_type mask = 1;
1377  mask <<= i;
1378  typename BV::enumerator en(bv, offset);
1379  for (;en.valid(); ++en)
1380  {
1381  size_type idx = *en - offset;
1382  if (idx >= size)
1383  break;
1384  arr[idx] |= mask;
1385  } // for
1386 
1387  } // for i
1388 
1389  return 0;
1390 }
1391 
1392 
1393 //---------------------------------------------------------------------
1394 
1395 template<class Val, class BV>
1398  size_type size,
1399  size_type offset,
1400  bool zero_mem) const BMNOEXCEPT2
1401 {
1402  /// Decoder functor
1403  /// @internal
1404  ///
1405  struct sv_decode_visitor_func
1406  {
1407  sv_decode_visitor_func(value_type* BMRESTRICT varr,
1408  value_type mask,
1409  size_type off) BMNOEXCEPT2
1410  : arr_(varr), mask_(mask), sv_off_(off)
1411  {}
1412 
1413  void add_bits(size_type bv_offset,
1414  const unsigned char* bits, unsigned bits_size) BMNOEXCEPT
1415  {
1416  // can be negative (-1) when bv base offset = 0 and sv = 1,2..
1417  size_type base = bv_offset - sv_off_;
1418  value_type m = mask_;
1419  for (unsigned i = 0; i < bits_size; ++i)
1420  arr_[bits[i] + base] |= m;
1421  }
1422  void add_range(size_type bv_offset, size_type sz) BMNOEXCEPT
1423  {
1424  auto base = bv_offset - sv_off_;
1425  value_type m = mask_;
1426  for (size_type i = 0; i < sz; ++i)
1427  arr_[i + base] |= m;
1428  }
1429 
1430  value_type* BMRESTRICT arr_; ///< target array for reverse transpose
1431  value_type mask_; ///< bit-plane mask
1432  size_type sv_off_; ///< SV read offset
1433  };
1434 
1435  if (!size)
1436  return 0;
1437 
1438  if (zero_mem)
1439  ::memset(arr, 0, sizeof(value_type)*size);
1440 
1441  size_type end = offset + size;
1442  if (end > this->size_)
1443  end = this->size_;
1444 
1445  sv_decode_visitor_func func(arr, 0, offset);
1446 
1447  for (size_type i = 0; i < parent_type::value_bits(); ++i)
1448  {
1449  const bvector_type* bv = this->bmatr_.get_row(i);
1450  if (!bv)
1451  continue;
1452  func.mask_ = (value_type(1) << i); // set target plane OR mask
1453  bm::for_each_bit_range_no_check(*bv, offset, end-1, func);
1454  } // for i
1455  return end - offset;
1456 }
1457 
1458 //---------------------------------------------------------------------
1459 
1460 template<class Val, class BV>
1463 {
1464  if (idx >= this->size_)
1465  throw_range_error("sparse vector range error");
1466  return this->get(idx);
1467 }
1468 
1469 //---------------------------------------------------------------------
1470 
1471 template<class Val, class BV>
1475 {
1476  BM_ASSERT(i < bm::id_max);
1477  BM_ASSERT(i < size());
1478 
1479  value_type v = 0;
1480  unsigned eff_plains = this->effective_plains();
1481  for (unsigned j = 0; j < eff_plains; j+=4)
1482  {
1483  bool b = this->bmatr_.test_4rows(j);
1484  if (b)
1485  {
1486  value_type vm = (value_type)this->bmatr_.get_half_octet(i, j);
1487  v |= vm << j;
1488  }
1489  } // for j
1490  return v;
1491 }
1492 
1493 
1494 //---------------------------------------------------------------------
1495 
1496 template<class Val, class BV>
1497 void sparse_vector<Val, BV>::set(size_type idx, value_type v)
1498 {
1499  if (idx >= size())
1500  {
1501  this->size_ = idx+1;
1502  }
1503  set_value(idx, v);
1504 }
1505 
1506 //---------------------------------------------------------------------
1507 
1508 template<class Val, class BV>
1509 void sparse_vector<Val, BV>::clear(size_type idx, bool set_null)
1510 {
1511  if (idx >= size())
1512  this->size_ = idx+1;
1513 
1514  set_value(idx, value_type(0));
1515  if (set_null)
1516  {
1517  bvector_type* bv_null = this->get_null_bvect();
1518  if (bv_null)
1519  bv_null->set(idx, false);
1520  }
1521 }
1522 
1523 //---------------------------------------------------------------------
1524 
1525 template<class Val, class BV>
1527 {
1528  set_value(this->size_, v);
1529  ++(this->size_);
1530 }
1531 
1532 //---------------------------------------------------------------------
1533 
1534 template<class Val, class BV>
1536 {
1537  BM_ASSERT(count);
1538  BM_ASSERT(bm::id_max - count > this->size_);
1539  BM_ASSERT(this->is_nullable());
1540 
1541  this->size_ += count;
1542 }
1543 
1544 
1545 //---------------------------------------------------------------------
1546 
1547 template<class Val, class BV>
1548 void sparse_vector<Val, BV>::insert(size_type idx, value_type v)
1549 {
1550  if (idx >= size())
1551  {
1552  this->size_ = idx+1;
1553  set_value(idx, v);
1554  return;
1555  }
1556  insert_value(idx, v);
1557 }
1558 
1559 //---------------------------------------------------------------------
1560 
1561 template<class Val, class BV>
1562 void sparse_vector<Val, BV>::insert_value(size_type idx, value_type v)
1563 {
1564  insert_value_no_null(idx, v);
1565  this->insert_null(idx, true);
1566 }
1567 
1568 //---------------------------------------------------------------------
1569 
1570 template<class Val, class BV>
1571 void sparse_vector<Val, BV>::insert_value_no_null(size_type idx, value_type v)
1572 {
1573  unsigned bsr = v ? bm::bit_scan_reverse(v) : 0u;
1574  value_type mask = 1u;
1575  unsigned i = 0;
1576  for (; i <= bsr; ++i)
1577  {
1578  if (v & mask)
1579  {
1580  bvector_type* bv = this->get_plain(i);
1581  bv->insert(idx, true);
1582  }
1583  else
1584  {
1585  bvector_type_ptr bv = this->bmatr_.get_row(i);
1586  if (bv)
1587  bv->insert(idx, false);
1588  }
1589  mask <<= 1;
1590  } // for i
1591  // insert 0 into all other existing plains
1592  unsigned eff_plains = this->effective_plains();
1593  for (; i < eff_plains; ++i)
1594  {
1595  bvector_type* bv = this->bmatr_.get_row(i);
1596  if (bv)
1597  bv->insert(idx, false);
1598  } // for i
1599 
1600  this->size_++;
1601 }
1602 
1603 //---------------------------------------------------------------------
1604 
1605 template<class Val, class BV>
1607 {
1608  BM_ASSERT(idx < this->size_);
1609  if (idx >= this->size_)
1610  return;
1611  this->erase_column(idx);
1612  this->size_--;
1613 }
1614 
1615 
1616 //---------------------------------------------------------------------
1617 
1618 template<class Val, class BV>
1620 {
1621  set_value_no_null(this->size_, v);
1622  ++(this->size_);
1623 }
1624 
1625 //---------------------------------------------------------------------
1626 
1627 template<class Val, class BV>
1628 void sparse_vector<Val, BV>::set_value(size_type idx, value_type v)
1629 {
1630  set_value_no_null(idx, v);
1631  bvector_type* bv_null = this->get_null_bvect();
1632  if (bv_null)
1633  bv_null->set_bit_no_check(idx);
1634 }
1635 
1636 //---------------------------------------------------------------------
1637 
1638 template<class Val, class BV>
1639 void sparse_vector<Val, BV>::set_value_no_null(size_type idx, value_type v)
1640 {
1641  // calculate logical block coordinates and masks
1642  //
1643  block_idx_type nb = (idx >> bm::set_block_shift);
1644  unsigned i0 = unsigned(nb >> bm::set_array_shift); // top block address
1645  unsigned j0 = unsigned(nb & bm::set_array_mask); // address in sub-block
1646 
1647  // clear the plains where needed
1648  unsigned eff_plains = this->effective_plains();
1649  unsigned bsr = v ? bm::bit_scan_reverse(v) : 0u;
1650 
1651  for (unsigned i = bsr; i < eff_plains; ++i)
1652  {
1653  const bm::word_t* blk = this->bmatr_.get_block(i, i0, j0);
1654  if (blk)
1655  {
1656  bvector_type* bv = this->bmatr_.get_row(i);
1657  if (bv)
1658  bv->clear_bit_no_check(idx);
1659  }
1660  } // for i
1661 
1662  if (v)
1663  {
1664  value_type mask = 1u;
1665  for (unsigned j = 0; j <= bsr; ++j)
1666  {
1667  if (v & mask)
1668  {
1669  bvector_type* bv = this->get_plain(j);
1670  bv->set_bit_no_check(idx);
1671  }
1672  else
1673  {
1674  const bm::word_t* blk = this->bmatr_.get_block(j, i0, j0);
1675  if (blk)
1676  {
1677  bvector_type* bv = this->bmatr_.get_row(j);
1678  bv->clear_bit_no_check(idx);
1679  }
1680  }
1681  mask <<= 1;
1682  } // for j
1683  }
1684 }
1685 
1686 //---------------------------------------------------------------------
1687 
1688 template<class Val, class BV>
1689 void sparse_vector<Val, BV>::inc(size_type idx)
1690 {
1691  if (idx >= this->size_)
1692  this->size_ = idx+1;
1693  inc_no_null(idx);
1694  bvector_type* bv_null = this->get_null_bvect();
1695  if (bv_null)
1696  bv_null->set_bit_no_check(idx);
1697 }
1698 
1699 //---------------------------------------------------------------------
1700 
1701 template<class Val, class BV>
1703 {
1704  for (unsigned i = 0; i < parent_type::sv_value_plains; ++i)
1705  {
1706  bvector_type* bv = this->get_plain(i);
1707  bool carry_over = bv->inc(idx);
1708  if (!carry_over)
1709  break;
1710  }
1711 }
1712 
1713 //------------------------------------ ---------------------------------
1714 
1715 template<class Val, class BV>
1716 void sparse_vector<Val, BV>::inc_no_null(size_type idx, value_type v)
1717 {
1718  value_type v_prev = get(idx);
1719  set_value_no_null(idx, v + v_prev);
1720 }
1721 
1722 //---------------------------------------------------------------------
1723 
1724 template<class Val, class BV>
1726 {
1727  parent_type::clear_all(free_mem);
1728 }
1729 
1730 //---------------------------------------------------------------------
1731 
1732 template<class Val, class BV>
1733 bool sparse_vector<Val, BV>::find_rank(size_type rank, size_type& pos) BMNOEXCEPT
1734 {
1735  BM_ASSERT(rank);
1736  pos = rank - 1;
1737  return true;
1738 }
1739 
1740 //---------------------------------------------------------------------
1741 
1742 template<class Val, class BV>
1745  typename sparse_vector<Val, BV>::size_type left,
1746  typename sparse_vector<Val, BV>::size_type right,
1747  bool set_null)
1748 {
1749  parent_type::clear_range(left, right, set_null);
1750  return *this;
1751 }
1752 
1753 //---------------------------------------------------------------------
1754 
1755 template<class Val, class BV>
1758 {
1759  BM_ASSERT(st);
1760  typename bvector_type::statistics stbv;
1761  parent_type::calc_stat(&stbv);
1762  if (st)
1763  {
1764  st->reset();
1765  st->add(stbv);
1766  }
1767 }
1768 
1769 //---------------------------------------------------------------------
1770 
1771 template<class Val, class BV>
1773  bm::word_t* temp_block,
1774  typename bvector_type::optmode opt_mode,
1776 {
1777  typename bvector_type::statistics stbv;
1778  stbv.reset();
1779  parent_type::optimize(temp_block, opt_mode, st ? &stbv : 0);
1780 
1781  if (st)
1782  {
1783  st->reset();
1784  st->add(stbv);
1785  }
1786 }
1787 
1788 //---------------------------------------------------------------------
1789 
1790 template<class Val, class BV>
1792 {
1793  unsigned stored_plains = this->stored_plains();
1794  for (unsigned j = 0; j < stored_plains; ++j)
1795  {
1796  bvector_type* bv = this->bmatr_.get_row(j);
1797  if (bv)
1798  {
1799  bv->optimize_gap_size();
1800  }
1801  }
1802 }
1803 
1804 //---------------------------------------------------------------------
1805 
1806 template<class Val, class BV>
1809 {
1810  size_type arg_size = sv.size();
1811  if (this->size_ < arg_size)
1812  {
1813  resize(arg_size);
1814  }
1815  bvector_type* bv_null = this->get_null_bvect();
1816  unsigned plains;
1817  if (bv_null)
1818  plains = this->stored_plains();
1819  else
1820  plains = this->plains();
1821 
1822  for (unsigned j = 0; j < plains; ++j)
1823  {
1824  const bvector_type* arg_bv = sv.bmatr_.row(j);
1825  if (arg_bv)
1826  {
1827  bvector_type* bv = this->bmatr_.get_row(j);
1828  if (!bv)
1829  bv = this->get_plain(j);
1830  *bv |= *arg_bv;
1831  }
1832  } // for j
1833 
1834  // our vector is NULL-able but argument is not (assumed all values are real)
1835  if (bv_null && !sv.is_nullable())
1836  {
1837  bv_null->set_range(0, arg_size-1);
1838  }
1839 
1840  return *this;
1841 }
1842 
1843 //---------------------------------------------------------------------
1844 
1845 template<class Val, class BV>
1848 {
1849  size_type arg_size = sv.size();
1850  if (this->size_ < arg_size)
1851  {
1852  resize(arg_size);
1853  }
1854  bvector_type* bv_null = this->get_null_bvect();
1855  unsigned plains;
1856  if (bv_null)
1857  plains = this->stored_plains();
1858  else
1859  plains = this->plains();
1860 
1861  for (unsigned j = 0; j < plains; ++j)
1862  {
1863  bvector_type* arg_bv = sv.bmatr_.get_row(j);//sv.plains_[j];
1864  if (arg_bv)
1865  {
1866  bvector_type* bv = this->bmatr_.get_row(j);//this->plains_[j];
1867  if (!bv)
1868  bv = this->get_plain(j);
1869  bv->merge(*arg_bv);
1870  }
1871  } // for j
1872 
1873  // our vector is NULL-able but argument is not (assumed all values are real)
1874  if (bv_null && !sv.is_nullable())
1875  {
1876  bv_null->set_range(0, arg_size-1);
1877  }
1878 
1879  return *this;
1880 }
1881 
1882 //---------------------------------------------------------------------
1883 
1884 template<class Val, class BV>
1886  typename sparse_vector<Val, BV>::size_type left,
1887  typename sparse_vector<Val, BV>::size_type right,
1888  bm::null_support splice_null)
1889 {
1890  if (left > right)
1891  bm::xor_swap(left, right);
1892  //this->clear();
1893  this->copy_range_plains(sv, left, right, splice_null);
1894  this->resize(sv.size());
1895 }
1896 //---------------------------------------------------------------------
1897 
1898 template<class Val, class BV>
1900  const typename sparse_vector<Val, BV>::bvector_type& bv_mask)
1901 {
1902  bvector_type* bv_null = this->get_null_bvect();
1903  unsigned plains;
1904  if (bv_null)
1905  {
1906  plains = this->stored_plains();
1907  bv_null->bit_and(bv_mask);
1908  }
1909  else
1910  plains = this->plains();
1911 
1912  for (unsigned j = 0; j < plains; ++j)
1913  {
1914  bvector_type* bv = this->bmatr_.get_row(j);
1915  if (bv)
1916  bv->bit_and(bv_mask);
1917  }
1918 }
1919 
1920 //---------------------------------------------------------------------
1921 
1922 template<class Val, class BV>
1924  const value_type val) const BMNOEXCEPT
1925 {
1926  // TODO: consider bit-by-bit comparison to minimize CPU hit miss in plans get()
1927  value_type sv_value = get(idx);
1928  return (sv_value > val) - (sv_value < val);
1929 }
1930 
1931 //---------------------------------------------------------------------
1932 
1933 template<class Val, class BV>
1935  bm::null_support null_able) const BMNOEXCEPT
1936 {
1937  return parent_type::equal(sv, null_able);
1938 }
1939 
1940 //---------------------------------------------------------------------
1941 
1942 template<class Val, class BV>
1945 {
1946  typedef typename sparse_vector<Val, BV>::const_iterator it_type;
1947  return it_type(this);
1948 }
1949 
1950 //---------------------------------------------------------------------
1951 
1952 template<class Val, class BV>
1955 {
1956  this->bmatr_.set_allocator_pool(pool_ptr);
1957 }
1958 
1959 
1960 //---------------------------------------------------------------------
1961 //
1962 //---------------------------------------------------------------------
1963 
1964 
1965 template<class Val, class BV>
1967 : sv_(0), pos_(bm::id_max), buf_ptr_(0)
1968 {}
1969 
1970 //---------------------------------------------------------------------
1971 
1972 template<class Val, class BV>
1975 : sv_(it.sv_), pos_(it.pos_), buf_ptr_(0)
1976 {}
1977 
1978 //---------------------------------------------------------------------
1979 
1980 template<class Val, class BV>
1983  ) BMNOEXCEPT
1984 : sv_(sv), buf_ptr_(0)
1985 {
1986  BM_ASSERT(sv_);
1987  pos_ = sv_->empty() ? bm::id_max : 0u;
1988 }
1989 
1990 //---------------------------------------------------------------------
1991 
1992 template<class Val, class BV>
1996 : sv_(sv), buf_ptr_(0)
1997 {
1998  BM_ASSERT(sv_);
1999  this->go_to(pos);
2000 }
2001 
2002 //---------------------------------------------------------------------
2003 
2004 template<class Val, class BV>
2006 {
2007  pos_ = (!sv_ || pos >= sv_->size()) ? bm::id_max : pos;
2008  buf_ptr_ = 0;
2009 }
2010 
2011 //---------------------------------------------------------------------
2012 
2013 template<class Val, class BV>
2015 {
2016  if (pos_ == bm::id_max) // nothing to do, we are at the end
2017  return false;
2018  ++pos_;
2019  if (pos_ >= sv_->size())
2020  {
2021  this->invalidate();
2022  return false;
2023  }
2024  if (buf_ptr_)
2025  {
2026  ++buf_ptr_;
2027  if (buf_ptr_ - ((value_type*)buffer_.data()) >= n_buf_size)
2028  buf_ptr_ = 0;
2029  }
2030  return true;
2031 }
2032 
2033 //---------------------------------------------------------------------
2034 
2035 template<class Val, class BV>
2038 {
2039  BM_ASSERT(this->valid());
2040  value_type v;
2041 
2042  if (!buf_ptr_)
2043  {
2044  buffer_.reserve(n_buf_size * sizeof(value_type));
2045  buf_ptr_ = (value_type*)(buffer_.data());
2046  sv_->extract(buf_ptr_, n_buf_size, pos_, true);
2047  }
2048  v = *buf_ptr_;
2049  return v;
2050 }
2051 
2052 //---------------------------------------------------------------------
2053 
2054 template<class Val, class BV>
2056 {
2057  value_type v = value();
2058  if (buf_ptr_)
2059  {
2060  v = *buf_ptr_;
2061  value_type* buf_end = ((value_type*)buffer_.data()) + n_buf_size;
2062  while(!v)
2063  {
2064  ++pos_;
2065  if (++buf_ptr_ < buf_end)
2066  v = *buf_ptr_;
2067  else
2068  break;
2069  }
2070  if (pos_ >= sv_->size())
2071  {
2072  pos_ = bm::id_max;
2073  return;
2074  }
2075  if (buf_ptr_ >= buf_end)
2076  buf_ptr_ = 0;
2077  }
2078 }
2079 
2080 //---------------------------------------------------------------------
2081 
2082 template<class Val, class BV>
2084 {
2085  return sv_->is_null(pos_);
2086 }
2087 
2088 
2089 //---------------------------------------------------------------------
2090 //
2091 //---------------------------------------------------------------------
2092 
2093 
2094 template<class Val, class BV>
2096 : sv_(0), bv_null_(0), buf_ptr_(0), prev_nb_(0), set_not_null_(true)
2097 {}
2098 
2099 //---------------------------------------------------------------------
2100 
2101 template<class Val, class BV>
2104 : sv_(sv), buf_ptr_(0), set_not_null_(true)
2105 {
2106  if (sv)
2107  {
2108  prev_nb_ = sv_->size() >> bm::set_block_shift;
2109  bv_null_ = sv_->get_null_bvect();
2110  }
2111  else
2112  {
2113  bv_null_ = 0; prev_nb_ = 0;
2114  }
2115 }
2116 
2117 //---------------------------------------------------------------------
2118 
2119 template<class Val, class BV>
2122 : sv_(bi.sv_), bv_null_(bi.bv_null_), buf_ptr_(0), prev_nb_(bi.prev_nb_),
2123  set_not_null_(bi.set_not_null_)
2124 {
2125  BM_ASSERT(bi.empty());
2126 }
2127 
2128 //---------------------------------------------------------------------
2129 
2130 template<class Val, class BV>
2132 {
2133  this->flush();
2134 }
2135 
2136 //---------------------------------------------------------------------
2137 
2138 template<class Val, class BV>
2141 {
2142  size_type buf_idx = this->add_value_no_null(v);
2143  if (bv_null_)
2144  {
2145  typename sparse_vector<Val, BV>::size_type sz = sv_->size();
2146  bv_null_->set_bit_no_check(sz + buf_idx);
2147  }
2148 }
2149 
2150 //---------------------------------------------------------------------
2151 
2152 template<class Val, class BV>
2156 {
2157  BM_ASSERT(sv_);
2158  if (!buf_ptr_) // not allocated (yet)
2159  {
2160  buffer_.reserve(n_buf_size * sizeof(value_type));
2161  buf_ptr_ = (value_type*)(buffer_.data());
2162  *buf_ptr_ = v;
2163  ++buf_ptr_;
2164  return 0;
2165  }
2166  if (buf_ptr_ - ((value_type*)buffer_.data()) >= n_buf_size)
2167  {
2168  this->flush();
2169  buf_ptr_ = (value_type*)(buffer_.data());
2170  }
2171 
2172  *buf_ptr_ = v;
2173  size_type buf_idx = size_type(buf_ptr_ - ((value_type*)buffer_.data()));
2174  ++buf_ptr_;
2175  return buf_idx;
2176 }
2177 
2178 //---------------------------------------------------------------------
2179 
2180 template<class Val, class BV>
2182 {
2183  BM_ASSERT(bv_null_);
2184  this->add_value_no_null(value_type(0));
2185 }
2186 
2187 //---------------------------------------------------------------------
2188 
2189 template<class Val, class BV>
2192 {
2193  if (count < 32)
2194  {
2195  for (size_type i = 0; i < count; ++i)
2196  this->add_value_no_null(value_type(0));
2197  }
2198  else
2199  {
2200  this->flush();
2201  sv_->push_back_null(count);
2202  }
2203 }
2204 
2205 //---------------------------------------------------------------------
2206 
2207 template<class Val, class BV>
2209 {
2210  return (!buf_ptr_ || !sv_);
2211 }
2212 
2213 //---------------------------------------------------------------------
2214 
2215 template<class Val, class BV>
2217 {
2218  if (this->empty())
2219  return;
2220  value_type* d = (value_type*)buffer_.data();
2221  sv_->import_back(d, size_type(buf_ptr_ - d), false); //!set_not_null_);
2222  buf_ptr_ = 0;
2223  block_idx_type nb = sv_->size() >> bm::set_block_shift;
2224  if (nb != prev_nb_)
2225  {
2226  // optimize all previous blocks in all planes
2227  sv_->optimize_block(prev_nb_);
2228  prev_nb_ = nb;
2229  }
2230 }
2231 
2232 //---------------------------------------------------------------------
2233 
2234 
2235 } // namespace bm
2236 
2237 
2238 
2239 #endif
memory allocation policy
Definition: bm.h:833
void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two scalar variables.
Definition: bmfunc.h:1153
std::input_iterator_tag iterator_category
Definition: bmsparsevec.h:156
size_type size() const BMNOEXCEPT
return size of the vector
Definition: bmsparsevec.h:647
back_insert_iterator & operator++(int)
noop
Definition: bmsparsevec.h:291
value_type at(size_type idx) const
access specified element with bounds checking
Definition: bmsparsevec.h:1462
const_iterator end() const BMNOEXCEPT
Provide const iterator access to the end.
Definition: bmsparsevec.h:493
void filter(const bvector_type &bv_mask)
Apply value filter, defined by mask vector.
Definition: bmsparsevec.h:1899
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:1725
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:285
void erase(size_type idx)
erase specified element from container
Definition: bmsparsevec.h:1606
bvector_type * get_null_bvect() const BMNOEXCEPT
Get access to not-null vector.
Definition: bmsparsevec.h:316
bvector_type * bvector_type_ptr
Definition: bmsparsevec.h:86
friend back_insert_iterator
Definition: bmsparsevec.h:349
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:332
const unsigned set_array_shift
Definition: bmconst.h:95
back_insert_iterator & operator*()
noop
Definition: bmsparsevec.h:287
bm::byte_buffer< allocator_type > buffer_type
Definition: bmsparsevec.h:165
void optimize(bm::word_t *temp_block=0, typename bvector_type::optmode opt_mode=bvector_type::opt_compress, typename sparse_vector< Val, BV >::statistics *stat=0)
run memory optimization for all vector plains
Definition: bmsparsevec.h:1772
void insert(size_type idx, value_type v)
insert specified element into container
Definition: bmsparsevec.h:1548
unsigned idx_arr_block_lookup_u32(const unsigned *idx, unsigned size, unsigned nb, unsigned start) BMNOEXCEPT
block boundaries look ahead U32
Definition: bmfunc.h:8896
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:2139
bm::id_t size_type
Definition: bm.h:117
void clear() BMNOEXCEPT
resize to zero, free memory
Definition: bmsparsevec.h:626
Rank-Select compressed sparse vector.
size_type effective_size() const BMNOEXCEPT
size of sparse vector (may be different for RSC)
Definition: bmsparsevec.h:868
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:1847
Definition: bm.h:76
bool is_null(size_type idx) const BMNOEXCEPT
test if specified element is NULL
Definition: bmbmatrix.h:1311
basic bit-matrix class and utilities
void add_null()
add NULL (no-value) to the container
Definition: bmsparsevec.h:2181
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
static unsigned rows()
Definition: bmtrans.h:61
void resize_internal(size_type sz)
Definition: bmsparsevec.h:903
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:1111
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:1100
sparse_vector_type::size_type size_type
Definition: bmsparsevec.h:260
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:1397
const_iterator begin() const BMNOEXCEPT
Provide const iterator access to container content.
Definition: bmsparsevec.h:1944
Back insert iterator implements buffered insert, faster than generic access assignment.
Definition: bmsparsevec.h:251
unsigned char * init_remap_buffer() BMNOEXCEPT
Definition: bmsparsevec.h:909
bvector_type::allocator_type allocator_type
Definition: bmsparsevec.h:262
back_insert_iterator & operator=(const back_insert_iterator &bi)
Definition: bmsparsevec.h:275
void inc(size_type idx)
increment specified element by one
Definition: bmsparsevec.h:1689
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:1571
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:1885
sparse_vector< Val, BV > & join(const sparse_vector< Val, BV > &sv)
join all with another sparse vector using OR operation
Definition: bmsparsevec.h:1808
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:1639
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:1791
sort order unknown
Definition: bmconst.h:193
void push_back_null(size_type count)
push back specified amount of NULL values
Definition: bmsparsevec.h:1535
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:1733
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:1953
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:263
void flush()
flush the accumulated buffer
Definition: bmsparsevec.h:2216
sort_order
Sort order declaration.
Definition: bmconst.h:188
~sparse_vector() BMNOEXCEPT
Definition: bmsparsevec.h:968
unsigned int word_t
Definition: bmconst.h:38
bool is_remap() const BMNOEXCEPT
Definition: bmsparsevec.h:906
#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:904
void push_back(value_type v)
push value back into vector
Definition: bmsparsevec.h:1526
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:8870
const unsigned char * get_remap_buffer() const BMNOEXCEPT
Definition: bmsparsevec.h:908
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:1293
sparse_vector< Val, BV > sparse_vector_type
Definition: bmsparsevec.h:257
size_type extract_plains(value_type *arr, size_type size, size_type offset, bool zero_mem=true) const
extract medium window without use of masking vector
Definition: bmsparsevec.h:1352
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:1744
bool empty() const
return true if insertion buffer is empty
Definition: bmsparsevec.h:2208
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:567
sparse_vector_type::bvector_type bvector_type
Definition: bmsparsevec.h:162
void resize(size_type sz)
resize vector
Definition: bmsparsevec.h:657
size_type effective_vector_max() const BMNOEXCEPT
Always 1 (non-matrix type)
Definition: bmsparsevec.h:873
void sync(bool)
syncronize internal structures
Definition: bmsparsevec.h:795
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:1464
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:506
sparse_vector_type::value_type value_type
Definition: bmsparsevec.h:259
bvector_type::block_idx_type block_idx_type
Definition: bmsparsevec.h:88
size_type extract_range(value_type *arr, size_type size, size_type offset, bool zero_mem=true) const
extract small window without use of masking vector
Definition: bmsparsevec.h:1272
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:1702
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:328
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:1002
sparse_vector_type::bvector_type bvector_type
Definition: bmsparsevec.h:261
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:1123
static bool is_compressed() BMNOEXCEPT
trait if sparse vector is "compressed" (false)
Definition: bmsparsevec.h:523
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:1203
#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:1542
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:1934
void calc_stat(struct sparse_vector< Val, BV >::statistics *st) const BMNOEXCEPT
Calculates memory statistics.
Definition: bmsparsevec.h:1756
static void throw_range_error(const char *err_msg)
throw range error
Definition: bmsparsevec.h:982
size_type add_value_no_null(value_type v)
add value to the buffer without changing the NULL vector
Definition: bmsparsevec.h:2154
back_insert_iterator & operator++()
noop
Definition: bmsparsevec.h:289
const bvector_type * bvector_type_const_ptr
Definition: bmsparsevec.h:89
bool empty() const BMNOEXCEPT
return true if vector is empty
Definition: bmsparsevec.h:652
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:1562
std::output_iterator_tag iterator_category
Definition: bmsparsevec.h:255
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:1088
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
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:577
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:842
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:1619
#define BMNOEXCEPT
Definition: bmdef.h:81
void set_value(size_type idx, value_type v)
set value without checking boundaries
Definition: bmsparsevec.h:1628
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:912
bmatrix_type bmatr_
bit-transposed matrix
Definition: bmbmatrix.h:502
Structure with statistical information about memory allocation footprint, serialization projection...
Definition: bmfunc.h:54
const unsigned set_block_shift
Definition: bmconst.h:55
void set_remap() BMNOEXCEPT
Definition: bmsparsevec.h:910
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:8795
Mini-matrix for bit transposition purposes.
Definition: bmtrans.h:40
void swap(sparse_vector< Val, BV > &sv) BMNOEXCEPT
content exchange
Definition: bmsparsevec.h:974
value_type operator[](size_type idx) const BMNOEXCEPT
get specified element without bounds checking
Definition: bmsparsevec.h:422
sparse_vector_type * sparse_vector_type_ptr
Definition: bmsparsevec.h:258
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:499
static void throw_bad_alloc()
throw bad alloc
Definition: bmsparsevec.h:994
bm::byte_buffer< allocator_type > buffer_type
Definition: bmsparsevec.h:264
size_t remap_size() const BMNOEXCEPT
Definition: bmsparsevec.h:907
#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:779
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:1923
reference operator[](size_type idx) BMNOEXCEPT
Operator to get write access to an element.
Definition: bmsparsevec.h:414
#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:938
sparse_vector< Val, BV > & operator=(const sparse_vector< Val, BV > &sv)
Definition: bmsparsevec.h:381