BitMagic-C++
bmsparsevec_algo.h
Go to the documentation of this file.
1 #ifndef BMSPARSEVEC_ALGO__H__INCLUDED__
2 #define BMSPARSEVEC_ALGO__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 /*! \file bmsparsevec_algo.h
21  \brief Algorithms for sparse_vector<>
22 */
23 
24 #include "bmdef.h"
25 #include "bmsparsevec.h"
26 #include "bmaggregator.h"
27 #include "bmbuffer.h"
28 #include "bmdef.h"
29 
30 #ifdef _MSC_VER
31 # pragma warning( disable: 4146 )
32 #endif
33 
34 
35 /** \defgroup svalgo Sparse vector algorithms
36  Sparse vector algorithms
37  \ingroup svector
38  */
39 
40 
41 namespace bm
42 {
43 
44 
45 /*!
46  \brief Clip dynamic range for signal higher than specified
47 
48  \param svect - sparse vector to do clipping
49  \param high_bit - max bit (inclusive) allowed for this signal vector
50 
51 
52  \ingroup svalgo
53  \sa dynamic_range_clip_low
54 */
55 template<typename SV>
56 void dynamic_range_clip_high(SV& svect, unsigned high_bit)
57 {
58  unsigned sv_plains = svect.plains();
59 
60  BM_ASSERT(sv_plains > high_bit && high_bit > 0);
61 
62  typename SV::bvector_type bv_acc;
63  unsigned i;
64 
65  // combine all the high bits into accumulator vector
66  for (i = high_bit+1; i < sv_plains; ++i)
67  {
68  typename SV::bvector_type* bv_plain = svect.plain(i);
69  if (bv_plain)
70  {
71  bv_acc.bit_or(*bv_plain);
72  svect.free_plain(i);
73  }
74  } // for i
75 
76  // set all bits ON for all low vectors, which happen to be clipped
77  for (i = high_bit; true; --i)
78  {
79  typename SV::bvector_type* bv_plain = svect.get_plain(i);
80  bv_plain->bit_or(bv_acc);
81  if (i == 0)
82  break;
83  } // for i
84 }
85 
86 
87 /*!
88  \brief Clip dynamic range for signal lower than specified (boost)
89 
90  \param svect - sparse vector to do clipping
91  \param low_bit - low bit (inclusive) allowed for this signal vector
92 
93  \ingroup svalgo
94  \sa dynamic_range_clip_high
95 */
96 template<typename SV>
97 void dynamic_range_clip_low(SV& svect, unsigned low_bit)
98 {
99  if (low_bit == 0) return; // nothing to do
100  BM_ASSERT(svect.plains() > low_bit);
101 
102  unsigned sv_plains = svect.plains();
103  typename SV::bvector_type bv_acc1;
104  unsigned i;
105 
106  // combine all the high bits into accumulator vector
107  for (i = low_bit+1; i < sv_plains; ++i)
108  {
109  typename SV::bvector_type* bv_plain = svect.plain(i);
110  if (bv_plain)
111  bv_acc1.bit_or(*bv_plain);
112  } // for i
113 
114  // accumulate all vectors below the clipping point
115  typename SV::bvector_type bv_acc2;
116  typename SV::bvector_type* bv_low_plain = svect.get_plain(low_bit);
117 
118  for (i = low_bit-1; true; --i)
119  {
120  typename SV::bvector_type* bv_plain = svect.plain(i);
121  if (bv_plain)
122  {
123  bv_acc2.bit_or(*bv_plain);
124  svect.free_plain(i);
125  if (i == 0)
126  break;
127  }
128  } // for i
129 
130  // now we want to set 1 in the clipping low plain based on
131  // exclusive or (XOR) between upper and lower parts)
132  // as a result high signal (any bits in the upper plains) gets
133  // slightly lower value (due to clipping) low signal gets amplified
134  // (lower contrast algorithm)
135 
136  bv_acc1.bit_xor(bv_acc2);
137  bv_low_plain->bit_or(bv_acc1);
138 }
139 
140 
141 /**
142  \brief algorithms for sparse_vector scan/seach
143 
144  Scanner uses properties of bit-vector plains to answer questions
145  like "find all sparse vector elements equivalent to XYZ".
146 
147  Class uses fast algorithms based on properties of bit-plains.
148  This is NOT a brute force, direct scan.
149 
150  @ingroup svalgo
151  @ingroup setalgo
152 */
153 template<typename SV>
155 {
156 public:
157  typedef typename SV::bvector_type bvector_type;
158  typedef const bvector_type* bvector_type_const_ptr;
159  typedef bvector_type* bvector_type_ptr;
160  typedef typename SV::value_type value_type;
161  typedef typename SV::size_type size_type;
162  typedef typename bvector_type::allocator_type::allocator_pool_type allocator_pool_type;
163 
164 public:
166 
167  /**
168  \brief bind sparse vector for all searches
169 
170  \param sv - input sparse vector to bind for searches
171  \param sorted - source index is sorted, build index for binary search
172  */
173  void bind(const SV& sv, bool sorted);
174 
175  /**
176  \brief reset sparse vector binding
177  */
178  void reset_binding();
179 
180  /**
181  \brief find all sparse vector elements EQ to search value
182 
183  Find all sparse vector elements equivalent to specified value
184 
185  \param sv - input sparse vector
186  \param value - value to search for
187  \param bv_out - output bit-vector (search result masks 1 elements)
188  */
189  void find_eq(const SV& sv,
190  typename SV::value_type value,
191  typename SV::bvector_type& bv_out);
192 
193  /**
194  \brief find first sparse vector element
195 
196  Find all sparse vector elements equivalent to specified value.
197  Works well if sperse vector represents unordered set
198 
199  \param sv - input sparse vector
200  \param value - value to search for
201  \param pos - output found sparse vector element index
202 
203  \return true if found
204  */
205  bool find_eq(const SV& sv,
206  typename SV::value_type value,
207  typename SV::size_type& pos);
208 
209  /**
210  \brief find first sparse vector element (string)
211  */
212  bool find_eq_str(const SV& sv,
213  const typename SV::value_type* str,
214  typename SV::size_type& pos);
215 
216  /**
217  \brief binary find first sparse vector element (string)
218  Sparse vector must be attached (bind())
219  @sa bind
220  */
221  bool find_eq_str(const typename SV::value_type* str,
222  typename SV::size_type& pos);
223 
224  /**
225  \brief binary find first sparse vector element (string)
226  Sparse vector must be sorted.
227  */
228  bool bfind_eq_str(const SV& sv,
229  const typename SV::value_type* str,
230  typename SV::size_type& pos);
231 
232  /**
233  \brief binary find first sparse vector element (string)
234  Sparse vector must be sorted and attached
235  @sa bind
236  */
237  bool bfind_eq_str(const typename SV::value_type* str,
238  typename SV::size_type& pos);
239 
240  /**
241  \brief find all sparse vector elements EQ to 0
242  \param sv - input sparse vector
243  \param bv_out - output bit-vector (search result masks 1 elements)
244  */
245  void find_zero(const SV& sv,
246  typename SV::bvector_type& bv_out);
247 
248  /*!
249  \brief Find non-zero elements
250  Output vector is computed as a logical OR (join) of all plains
251 
252  \param sv - input sparse vector
253  \param bv_out - output bit-bector of non-zero elements
254  */
255  void find_nonzero(const SV& sv, typename SV::bvector_type& bv_out);
256 
257  /**
258  \brief invert search result ("EQ" to "not EQ")
259 
260  \param sv - input sparse vector
261  \param bv_out - output bit-bector of non-zero elements
262  */
263  void invert(const SV& sv, typename SV::bvector_type& bv_out);
264 
265  /**
266  \brief find all values A IN (C, D, E, F)
267  \param sv - input sparse vector
268  \param start - start iterator (set to search)
269  \param end - end iterator (set to search)
270  \param bv_out - output bit-bector of non-zero elements
271  */
272  template<typename It>
273  void find_eq(const SV& sv,
274  It start,
275  It end,
276  typename SV::bvector_type& bv_out)
277  {
278  typename bvector_type::mem_pool_guard mp_guard;
279  mp_guard.assign_if_not_set(pool_, bv_out); // set algorithm-local memory pool to avoid heap contention
280 
281  bvector_type bv1;
282  typename bvector_type::mem_pool_guard mp_guard1(pool_, bv1);
283  bool any_zero = false;
284  for (; start < end; ++start)
285  {
286  value_type v = *start;
287  any_zero |= (v == 0);
288  bool found = find_eq_with_nulls(sv, v, bv1);
289  if (found)
290  bv_out.bit_or(bv1);
291  else
292  {
293  BM_ASSERT(!bv1.any());
294  }
295  } // for
296  if (any_zero)
297  correct_nulls(sv, bv_out);
298  }
299 
300  /// For testing purposes only
301  ///
302  /// @internal
303  void find_eq_with_nulls_horizontal(const SV& sv,
304  typename SV::value_type value,
305  typename SV::bvector_type& bv_out);
306 
307  /** Exclude possible NULL values from the result vector
308  \param sv - input sparse vector
309  \param bv_out - output bit-bector of non-zero elements
310  */
311  void correct_nulls(const SV& sv, typename SV::bvector_type& bv_out);
312 
313 protected:
314 
315  /// set search boundaries (hint for the aggregator)
316  void set_search_range(size_type from, size_type to);
317 
318  /// reset (disable) search range
319  void reset_search_range();
320 
321  /// find value (may include NULL indexes)
322  bool find_eq_with_nulls(const SV& sv,
323  typename SV::value_type value,
324  typename SV::bvector_type& bv_out,
325  typename SV::size_type search_limit = 0);
326 
327  /// find first value (may include NULL indexes)
328  bool find_first_eq(const SV& sv,
329  typename SV::value_type value,
330  bm::id_t& idx);
331 
332  /// find first string value (may include NULL indexes)
333  bool find_first_eq(const SV& sv,
334  const typename SV::value_type* str,
335  bm::id_t& idx,
336  bool remaped);
337 
338 
339  /// Prepare aggregator for AND-SUB (EQ) search
340  bool prepare_and_sub_aggregator(const SV& sv,
341  typename SV::value_type value);
342 
343  /// Prepare aggregator for AND-SUB (EQ) search (string)
344  bool prepare_and_sub_aggregator(const SV& sv,
345  const typename SV::value_type* str,
346  unsigned octet_start);
347 
348  /// Rank-Select decompression for RSC vectors
349  void decompress(const SV& sv, typename SV::bvector_type& bv_out);
350 
351  int compare_str(const SV& sv, size_type idx, const value_type* str);
352 
353 protected:
355  void operator=(const sparse_vector_scanner&) = delete;
356 
357 protected:
358 
360  {
361  max_columns = SV::max_vector_size
362  };
363 
364  typedef bm::heap_matrix<value_type,
366  max_columns,
367  typename bvector_type::allocator_type> heap_matrix_type0;
368  typedef bm::heap_matrix<value_type,
369  bm::set_total_blocks*3,
370  max_columns,
371  typename bvector_type::allocator_type> heap_matrix_type3;
372 
373 private:
374  allocator_pool_type pool_;
375  bvector_type bv_tmp_;
378 
379  size_type mask_from_;
380  size_type mask_to_;
381  bool mask_set_;
382 
383  const SV* bound_sv_;
384  heap_matrix_type0 block0_elements_cache_; ///< cache for elements[0] of each block
385  heap_matrix_type3 block3_elements_cache_; ///< cache for elements[16384x] of each block
386  size_type effective_str_max_;
387 
388  value_type remap_value_vect_[SV::max_vector_size];
389  /// masks of allocated bit-plains (1 - means there is a bit-plain)
390  bm::id64_t vector_plain_masks_[SV::max_vector_size];
391 };
392 
393 
394 /*!
395  \brief Integer set to set transformation (functional image in groups theory)
396  https://en.wikipedia.org/wiki/Image_(mathematics)
397 
398  Input sets gets translated through the function, which is defined as
399  "one to one (or NULL)" binary relation object (sparse_vector).
400  Also works for M:1 relationships.
401 
402  \ingroup svalgo
403  \ingroup setalgo
404 */
405 template<typename SV>
407 {
408 public:
409  typedef typename SV::bvector_type bvector_type;
410  typedef typename SV::value_type value_type;
411  typedef typename SV::size_type size_type;
412  typedef typename bvector_type::allocator_type::allocator_pool_type allocator_pool_type;
413 public:
414 
417 
418 
419  /** Get read access to zero-elements vector
420  Zero vector gets populated after attach_sv() is called
421  or as a side-effect of remap() with immediate sv param
422  */
423  const bvector_type& get_bv_zero() const { return bv_zero_; }
424 
425  /** Perform remapping (Image function) (based on attached translation table)
426 
427  \param bv_in - input set, defined as a bit-vector
428  \param bv_out - output set as a bit-vector
429 
430  @sa attach_sv
431  */
432  void remap(const bvector_type& bv_in,
433  bvector_type& bv_out);
434 
435  /** Perform remapping (Image function)
436 
437  \param bv_in - input set, defined as a bit-vector
438  \param sv_brel - binary relation (translation table) sparse vector
439  \param bv_out - output set as a bit-vector
440  */
441  void remap(const bvector_type& bv_in,
442  const SV& sv_brel,
443  bvector_type& bv_out);
444 
445  /** Remap single set element
446 
447  \param id_from - input value
448  \param sv_brel - translation table sparse vector
449  \param id_to - out value
450 
451  \return - true if value was found and remapped
452  */
453  bool remap(size_type id_from, const SV& sv_brel, size_type& id_to);
454 
455 
456  /** Run remap transformation
457 
458  \param bv_in - input set, defined as a bit-vector
459  \param sv_brel - translation table sparse vector
460  \param bv_out - output set as a bit-vector
461 
462  @sa remap
463  */
464  void run(const bvector_type& bv_in,
465  const SV& sv_brel,
466  bvector_type& bv_out)
467  {
468  remap(bv_in, sv_brel, bv_out);
469  }
470 
471  /** Attach a translation table vector for remapping (Image function)
472 
473  \param sv_brel - binary relation sparse vector pointer
474  (pass NULL to detach)
475  \param compute_stats - flag to perform computation of some statistics
476  later used in remapping. This only make sense
477  for series of remappings on the same translation
478  vector.
479  @sa remap
480  */
481  void attach_sv(const SV* sv_brel, bool compute_stats = false);
482 
483 
484 protected:
485  void one_pass_run(const bvector_type& bv_in,
486  const SV& sv_brel,
487  bvector_type& bv_out);
488 
489  /// @internal
490  template<unsigned BSIZE>
492  {
493  size_type BM_VECT_ALIGN gather_idx_[BSIZE] BM_VECT_ALIGN_ATTR;
494  value_type BM_VECT_ALIGN buffer_[BSIZE] BM_VECT_ALIGN_ATTR;
495  };
496 
498  {
499  sv_g_size = 1024 * 8
500  };
502 
503 
504 protected:
506  void operator=(const set2set_11_transform&) = delete;
507 
508 protected:
509  const SV* sv_ptr_; ///< current translation table vector
510  gather_buffer_type* gb_; ///< intermediate buffers
511  bvector_type bv_product_;///< temp vector
512 
513  bool have_stats_; ///< flag of statistics presense
514  bvector_type bv_zero_; ///< bit-vector for zero elements
515 
516  allocator_pool_type pool_;
517 };
518 
519 
520 
521 //----------------------------------------------------------------------------
522 //
523 //----------------------------------------------------------------------------
524 
525 template<typename SV>
527 : sv_ptr_(0), gb_(0), have_stats_(false)
528 {
529  gb_ = (gather_buffer_type*)::malloc(sizeof(gather_buffer_type));
530  if (!gb_)
531  {
532  SV::throw_bad_alloc();
533  }
534 }
535 
536 //----------------------------------------------------------------------------
537 
538 template<typename SV>
540 {
541  if (gb_)
542  ::free(gb_);
543 }
544 
545 
546 //----------------------------------------------------------------------------
547 
548 template<typename SV>
549 void set2set_11_transform<SV>::attach_sv(const SV* sv_brel, bool compute_stats)
550 {
551  sv_ptr_ = sv_brel;
552  if (!sv_ptr_)
553  {
554  have_stats_ = false;
555  }
556  else
557  {
558  if (sv_brel->empty() || !compute_stats)
559  return; // nothing to do
560  const bvector_type* bv_non_null = sv_brel->get_null_bvector();
561  if (bv_non_null)
562  return; // already have 0 elements vector
563 
564 
565  typename bvector_type::mem_pool_guard mp_g_z;
566  mp_g_z.assign_if_not_set(pool_, bv_zero_);
567 
569  scanner.find_zero(*sv_brel, bv_zero_);
570  have_stats_ = true;
571  }
572 }
573 
574 //----------------------------------------------------------------------------
575 
576 template<typename SV>
578  const SV& sv_brel,
579  size_type& id_to)
580 {
581  if (sv_brel.empty())
582  return false; // nothing to do
583 
584  const bvector_type* bv_non_null = sv_brel.get_null_bvector();
585  if (bv_non_null)
586  {
587  if (!bv_non_null->test(id_from))
588  return false;
589  }
590  size_type idx = sv_brel.translate_address(id_from);
591  id_to = sv_brel.get(idx);
592  return true;
593 }
594 
595 //----------------------------------------------------------------------------
596 
597 template<typename SV>
599  const SV& sv_brel,
600  bvector_type& bv_out)
601 {
602  typename bvector_type::mem_pool_guard mp_g_out, mp_g_p, mp_g_z;
603  mp_g_out.assign_if_not_set(pool_, bv_out);
604  mp_g_p.assign_if_not_set(pool_, bv_product_);
605  mp_g_z.assign_if_not_set(pool_, bv_zero_);
606 
607  attach_sv(&sv_brel);
608 
609  remap(bv_in, bv_out);
610 
611  attach_sv(0); // detach translation table
612 }
613 
614 template<typename SV>
616  bvector_type& bv_out)
617 {
619 
620  bv_out.clear();
621 
622  if (sv_ptr_ == 0 || sv_ptr_->empty())
623  return; // nothing to do
624 
625  bv_out.init(); // just in case to "fast set" later
626 
627  typename bvector_type::mem_pool_guard mp_g_out, mp_g_p, mp_g_z;
628  mp_g_out.assign_if_not_set(pool_, bv_out);
629  mp_g_p.assign_if_not_set(pool_, bv_product_);
630  mp_g_z.assign_if_not_set(pool_, bv_zero_);
631 
632 
633  const bvector_type* enum_bv;
634 
635  const bvector_type * bv_non_null = sv_ptr_->get_null_bvector();
636  if (bv_non_null)
637  {
638  // TODO: optimize with 2-way ops
639  bv_product_ = bv_in;
640  bv_product_.bit_and(*bv_non_null);
641  enum_bv = &bv_product_;
642  }
643  else // non-NULL vector is not available
644  {
645  enum_bv = &bv_in;
646  // if we have any elements mapping into "0" on the other end
647  // we map it once (chances are there are many duplicates)
648  //
649 
650  if (have_stats_) // pre-attached translation statistics
651  {
652  bv_product_ = bv_in;
653  unsigned cnt1 = bv_product_.count();
654  bv_product_.bit_sub(bv_zero_);
655  unsigned cnt2 = bv_product_.count();
656 
657  BM_ASSERT(cnt2 <= cnt1);
658 
659  if (cnt1 != cnt2) // mapping included 0 elements
660  bv_out.set_bit_no_check(0);
661 
662  enum_bv = &bv_product_;
663  }
664  }
665 
666 
667 
668  unsigned buf_cnt, nb_old, nb;
669  buf_cnt = nb_old = 0;
670 
671  typename bvector_type::enumerator en(enum_bv->first());
672  for (; en.valid(); ++en)
673  {
674  typename SV::size_type idx = *en;
675  idx = sv_ptr_->translate_address(idx);
676 
677  nb = unsigned(idx >> bm::set_block_shift);
678  if (nb != nb_old) // new blocks
679  {
680  if (buf_cnt)
681  {
682  sv_ptr_->gather(&gb_->buffer_[0], &gb_->gather_idx_[0], buf_cnt, BM_SORTED_UNIFORM);
683  bv_out.set(&gb_->buffer_[0], buf_cnt, BM_SORTED);
684  buf_cnt ^= buf_cnt;
685  }
686  nb_old = nb;
687  gb_->gather_idx_[buf_cnt++] = idx;
688  }
689  else
690  {
691  gb_->gather_idx_[buf_cnt++] = idx;
692  }
693 
694  if (buf_cnt == sv_g_size)
695  {
696  sv_ptr_->gather(&gb_->buffer_[0], &gb_->gather_idx_[0], buf_cnt, BM_SORTED_UNIFORM);
697  bv_out.set(&gb_->buffer_[0], buf_cnt, bm::BM_SORTED);
698  buf_cnt ^= buf_cnt;
699  }
700  } // for en
701  if (buf_cnt)
702  {
703  sv_ptr_->gather(&gb_->buffer_[0], &gb_->gather_idx_[0], buf_cnt, BM_SORTED_UNIFORM);
704  bv_out.set(&gb_->buffer_[0], buf_cnt, bm::BM_SORTED);
705  }
706 }
707 
708 
709 //----------------------------------------------------------------------------
710 
711 template<typename SV>
713  const SV& sv_brel,
714  bvector_type& bv_out)
715 {
716  if (sv_brel.empty())
717  return; // nothing to do
718 
719  bv_out.init();
720 
721  typename SV::const_iterator it = sv_brel.begin();
722  for (; it.valid(); ++it)
723  {
724  typename SV::value_type t_id = *it;
725  bm::id_t idx = it.pos();
726  if (bv_in.test(idx))
727  {
728  bv_out.set_bit_no_check(t_id);
729  }
730  } // for
731 }
732 
733 
734 //----------------------------------------------------------------------------
735 //
736 //----------------------------------------------------------------------------
737 
738 template<typename SV>
740 {
741  mask_set_ = false;
742  mask_from_ = mask_to_ = bm::id_max;
743 
744  bound_sv_ = 0;
745  effective_str_max_ = 0;
746 }
747 
748 //----------------------------------------------------------------------------
749 
750 template<typename SV>
751 void sparse_vector_scanner<SV>::bind(const SV& sv, bool sorted)
752 {
753  bound_sv_ = &sv;
754  if (sorted)
755  {
756  block0_elements_cache_.init();
757  block0_elements_cache_.set_zero();
758  block3_elements_cache_.init();
759  block3_elements_cache_.set_zero();
760 
761  effective_str_max_ = sv.effective_vector_max();
762  // fill in elements cache
763  for (size_type i = 0; i < sv.size(); i+= bm::gap_max_bits)
764  {
765  unsigned nb = unsigned(i >> bm::set_block_shift);
766  value_type* s0 = block0_elements_cache_.row(nb);
767  sv.get(i, s0, block0_elements_cache_.cols());
768 
769  for (size_type k = 0; k < 3; ++k)
770  {
771  value_type* s1 = block3_elements_cache_.row(nb * 3 + k);
772  size_type idx = i + (k+1) * bm::sub_block3_size;
773  sv.get(idx, s1, block3_elements_cache_.cols());
774  } // for k
775  } // for i
776  }
777  // pre-calculate vector plain masks
778  //
779  for (unsigned i = 0; i < SV::max_vector_size; ++i)
780  {
781  vector_plain_masks_[i] = sv.get_plains_mask(i);
782  } // for i
783 
784 }
785 
786 //----------------------------------------------------------------------------
787 
788 template<typename SV>
790 {
791  bound_sv_ = 0;
792  effective_str_max_ = 0;
793 }
794 
795 //----------------------------------------------------------------------------
796 
797 template<typename SV>
799  typename SV::bvector_type& bv_out)
800 {
801  if (sv.size() == 0)
802  {
803  bv_out.clear();
804  return;
805  }
806 
807  find_nonzero(sv, bv_out);
808  if (sv.is_compressed())
809  {
810  bv_out.invert();
811  bv_out.set_range(sv.effective_size(), bm::id_max - 1, false);
812  decompress(sv, bv_out);
813  }
814  else
815  {
816  invert(sv, bv_out);
817  }
818  correct_nulls(sv, bv_out);
819 }
820 
821 //----------------------------------------------------------------------------
822 
823 template<typename SV>
824 void sparse_vector_scanner<SV>::invert(const SV& sv, typename SV::bvector_type& bv_out)
825 {
826  if (sv.size() == 0)
827  {
828  bv_out.clear();
829  return;
830  }
831  bv_out.invert();
832  const bvector_type* bv_null = sv.get_null_bvector();
833  if (bv_null) // correct result to only use not NULL elements
834  bv_out &= *bv_null;
835  else
836  bv_out.set_range(sv.size(), bm::id_max - 1, false);
837 }
838 
839 //----------------------------------------------------------------------------
840 
841 template<typename SV>
843  typename SV::bvector_type& bv_out)
844 {
845  const bvector_type* bv_null = sv.get_null_bvector();
846  if (bv_null) // correct result to only use not NULL elements
847  bv_out.bit_and(*bv_null);
848 }
849 
850 //----------------------------------------------------------------------------
851 
852 template<typename SV>
854  typename SV::value_type value,
855  typename SV::bvector_type& bv_out,
856  typename SV::size_type search_limit)
857 {
858  if (sv.empty())
859  return false; // nothing to do
860 
861  if (!value)
862  {
863  find_zero(sv, bv_out);
864  return bv_out.any();
865  }
866  agg_.reset();
867 
868  bool found = prepare_and_sub_aggregator(sv, value);
869  if (!found)
870  {
871  bv_out.clear();
872  return found;
873  }
874 
875  bool any = (search_limit == 1);
876  found = agg_.combine_and_sub(bv_out, any);
877  agg_.reset();
878  return found;
879 }
880 
881 //----------------------------------------------------------------------------
882 
883 template<typename SV>
885  typename SV::value_type value,
886  bm::id_t& idx)
887 {
888  if (sv.empty())
889  return false; // nothing to do
890 
891  BM_ASSERT(value); // cannot handle zero values
892  if (!value)
893  return false;
894 
895  agg_.reset();
896  bool found = prepare_and_sub_aggregator(sv, value);
897  if (!found)
898  return found;
899  found = agg_.find_first_and_sub(idx);
900  agg_.reset();
901  return found;
902 }
903 
904 
905 //----------------------------------------------------------------------------
906 
907 template<typename SV>
909  const typename SV::value_type* str,
910  bm::id_t& idx,
911  bool remaped)
912 {
913  if (sv.empty())
914  return false; // nothing to do
915  BM_ASSERT(*str);
916 
917  if (!*str)
918  return false;
919 
920  agg_.reset();
921  unsigned common_prefix_len = 0;
922 
923  if (mask_set_)
924  {
925  agg_.set_range_hint(mask_from_, mask_to_);
926  common_prefix_len = sv.common_prefix_length(mask_from_, mask_to_);
927  }
928 
929  if (remaped)
930  {
931  str = remap_value_vect_;
932  }
933  else
934  {
935  if (sv.is_remap() && str != remap_value_vect_)
936  {
937  bool r = sv.remap_tosv(remap_value_vect_, SV::max_vector_size, str);
938  if (!r)
939  return r;
940  str = remap_value_vect_;
941  }
942  }
943 
944  bool found = prepare_and_sub_aggregator(sv, str, common_prefix_len);
945  if (!found)
946  return found;
947 
948  found = agg_.find_first_and_sub(idx);
949  agg_.reset();
950  return found;
951 }
952 
953 //----------------------------------------------------------------------------
954 
955 template<typename SV>
957  const typename SV::value_type* str,
958  unsigned octet_start)
959 {
960  unsigned char bits[64];
961 
962  int len = 0;
963  for (; str[len] != 0; ++len)
964  {}
965  BM_ASSERT(len);
966 
967  // use reverse order (faster for sorted arrays)
968  for (int octet_idx = len-1; octet_idx >= 0; --octet_idx)
969  {
970  if (unsigned(octet_idx) < octet_start) // common prefix
971  break;
972 
973  unsigned value = unsigned(str[octet_idx]) & 0xFF;
974  BM_ASSERT(value != 0);
975 
976  bm::id64_t plains_mask;
977  if (&sv == bound_sv_)
978  plains_mask = vector_plain_masks_[octet_idx];
979  else
980  plains_mask = sv.get_plains_mask(unsigned(octet_idx));
981 
982  if ((value & plains_mask) != value) // pre-screen for impossible values
983  return false; // found non-existing plain
984 
985  // prep the lists for combined AND-SUB aggregator
986  //
987  unsigned short bit_count_v = bm::bitscan(value, bits);
988  for (unsigned i = 0; i < bit_count_v; ++i)
989  {
990  unsigned bit_idx = bits[i];
991  BM_ASSERT(value & (value_type(1) << bit_idx));
992  unsigned plain_idx = (unsigned(octet_idx) * 8) + bit_idx;
993  const bvector_type* bv = sv.get_plain(plain_idx);
994  agg_.add(bv);
995  } // for i
996 
997  unsigned vinv = unsigned(value);
998  if (bm::conditional<sizeof(value_type) == 1>::test())
999  {
1000  vinv ^= 0xFF;
1001  }
1002  else // 2-byte char
1003  {
1004  BM_ASSERT(sizeof(value_type) == 2);
1005  vinv ^= 0xFFFF;
1006  }
1007  // exclude the octet bits which are all not set (no vectors)
1008  vinv &= unsigned(plains_mask);
1009  for (unsigned octet_plain = (unsigned(octet_idx) * 8); vinv; vinv &= vinv-1)
1010  {
1011  bm::id_t t = vinv & -vinv;
1012  unsigned bit_idx = bm::word_bitcount(t - 1);
1013  unsigned plain_idx = octet_plain + bit_idx;
1014  const bvector_type* bv = sv.get_plain(plain_idx);
1015  BM_ASSERT(bv);
1016  agg_.add(bv, 1); // agg to SUB group
1017  } // for
1018  } // for octet_idx
1019 
1020  // add all vectors above string len to the SUB operation group
1021  //
1022  typename SV::size_type plain_idx = unsigned(len * 8) + 1;
1023  typename SV::size_type plains;
1024  if (&sv == bound_sv_)
1025  plains = effective_str_max_ * unsigned(sizeof(value_type)) * 8;
1026  else
1027  plains = sv.plains();
1028  for (; plain_idx < plains; ++plain_idx)
1029  {
1030  bvector_type_const_ptr bv = sv.get_plain(plain_idx);
1031  if (bv)
1032  agg_.add(bv, 1); // agg to SUB group
1033  } // for
1034  return true;
1035 }
1036 
1037 //----------------------------------------------------------------------------
1038 
1039 template<typename SV>
1041  typename SV::value_type value)
1042 {
1043  unsigned char bits[sizeof(value) * 8];
1044  unsigned short bit_count_v = bm::bitscan(value, bits);
1045  BM_ASSERT(bit_count_v);
1046 
1047  // prep the lists for combined AND-SUB aggregator
1048  // (backward order has better chance for bit reduction on AND)
1049  //
1050  for (unsigned i = bit_count_v; i > 0; --i)
1051  {
1052  unsigned bit_idx = bits[i-1];
1053  BM_ASSERT(value & (value_type(1) << bit_idx));
1054  const bvector_type* bv = sv.get_plain(bit_idx);
1055  if (bv)
1056  agg_.add(bv);
1057  else
1058  return false;
1059  }
1060 
1061  unsigned sv_plains = sv.effective_plains();
1062  for (unsigned i = 0; (i < sv_plains) && value; ++i)
1063  {
1064  bvector_type_const_ptr bv = sv.get_plain(i);
1065  if (bv && !(value & (value_type(1) << i)))
1066  agg_.add(bv, 1); // agg to SUB group
1067  } // for i
1068  return true;
1069 }
1070 
1071 
1072 //----------------------------------------------------------------------------
1073 
1074 template<typename SV>
1076  typename SV::value_type value,
1077  typename SV::bvector_type& bv_out)
1078 {
1079  if (sv.empty())
1080  return; // nothing to do
1081 
1082  if (!value)
1083  {
1084  find_zero(sv, bv_out);
1085  return;
1086  }
1087 
1088  unsigned char bits[sizeof(value) * 8];
1089  unsigned short bit_count_v = bm::bitscan(value, bits);
1090  BM_ASSERT(bit_count_v);
1091 
1092  // aggregate AND all matching vectors
1093  {
1094  const bvector_type* bv_plain = sv.get_plain(bits[--bit_count_v]);
1095  if (bv_plain)
1096  bv_out = *bv_plain;
1097  else // plain not found
1098  {
1099  bv_out.clear();
1100  return;
1101  }
1102  }
1103  for (unsigned i = 0; i < bit_count_v; ++i)
1104  {
1105  const bvector_type* bv_plain = sv.get_plain(bits[i]);
1106  if (bv_plain)
1107  bv_out &= *bv_plain;
1108  else // mandatory plain not found - empty result!
1109  {
1110  bv_out.clear();
1111  return;
1112  }
1113  } // for i
1114 
1115  // SUB all other plains
1116  unsigned sv_plains = sv.effective_plains();
1117  for (unsigned i = 0; (i < sv_plains) && value; ++i)
1118  {
1119  const bvector_type* bv_plain = sv.get_plain(i);
1120  if (bv_plain && !(value & (value_type(1) << i)))
1121  bv_out -= *bv_plain;
1122  }
1123 }
1124 
1125 //----------------------------------------------------------------------------
1126 
1127 template<typename SV>
1128 bool sparse_vector_scanner<SV>::find_eq_str(const typename SV::value_type* str,
1129  typename SV::size_type& pos)
1130 {
1131  BM_ASSERT(bound_sv_);
1132  return find_eq_str(*bound_sv_, str, pos);
1133 }
1134 
1135 //----------------------------------------------------------------------------
1136 
1137 template<typename SV>
1139  const typename SV::value_type* str,
1140  typename SV::size_type& pos)
1141 {
1142  bool found = false;
1143  if (sv.empty())
1144  return found;
1145  if (*str)
1146  {
1147  bool remaped = false;
1148  if (bm::conditional<SV::is_remap_support::value>::test()) // test remapping trait
1149  {
1150  if (sv.is_remap() && str != remap_value_vect_)
1151  {
1152  remaped = sv.remap_tosv(remap_value_vect_, SV::max_vector_size, str);
1153  if (!remaped)
1154  return remaped;
1155  str = remap_value_vect_;
1156  }
1157  }
1158 
1159  bm::id_t found_pos;
1160  found = find_first_eq(sv, str, found_pos, remaped);
1161  if (found)
1162  {
1163  pos = found_pos;
1164  if (bm::conditional<SV::is_rsc_support::value>::test()) // test rank/select trait
1165  {
1166  if (sv.is_compressed()) // if compressed vector - need rank translation
1167  found = sv.find_rank(found_pos + 1, pos);
1168  }
1169  }
1170  }
1171  else // search for zero value
1172  {
1173  // TODO: implement optimized version which would work witout temp vector
1174  typename SV::bvector_type bv_zero;
1175  find_zero(sv, bv_zero);
1176  found = bv_zero.find(pos);
1177  }
1178  return found;
1179 }
1180 
1181 //----------------------------------------------------------------------------
1182 
1183 template<typename SV>
1185  const typename SV::value_type* str,
1186  typename SV::size_type& pos)
1187 {
1188  bool found = false;
1189  if (sv.empty())
1190  return found;
1191 
1192  if (*str)
1193  {
1194  bool remaped = false;
1195  // test search pre-condition based on remap tables
1197  {
1198  if (sv.is_remap() && str != remap_value_vect_)
1199  {
1200  remaped = sv.remap_tosv(
1201  remap_value_vect_, SV::max_vector_size, str);
1202  if (!remaped)
1203  return remaped;
1204  }
1205  }
1206 
1207  reset_search_range();
1208 
1209  // narrow down the search
1210  const unsigned min_distance_cutoff = bm::gap_max_bits + bm::gap_max_bits / 2;
1211  size_type l, r, dist;
1212  l = 0; r = sv.size()-1;
1213  bm::id_t found_pos;
1214 
1215  // binary search to narrow down the search window
1216  while (l <= r)
1217  {
1218  dist = r - l;
1219  if (dist < min_distance_cutoff)
1220  {
1221  // we are in an narrow <2 blocks window, but still may be in two
1222  // different neighboring blocks, lets try to narrow
1223  // to exactly one block
1224 
1225  unsigned nb_l = unsigned(l >> bm::set_block_shift);
1226  unsigned nb_r = unsigned(r >> bm::set_block_shift);
1227  if (nb_l != nb_r)
1228  {
1229  size_type mid = nb_r * bm::gap_max_bits;
1230  if (mid < r)
1231  {
1232  int cmp = this->compare_str(sv, mid, str);
1233  if (cmp < 0) // mid < str
1234  l = mid;
1235  else
1236  r = mid-(cmp!=0); // branchless if (cmp==0) r=mid;
1237  BM_ASSERT(l < r);
1238  }
1239  nb_l = unsigned(l >> bm::set_block_shift);
1240  nb_r = unsigned(r >> bm::set_block_shift);
1241  }
1242 
1243  if (nb_l == nb_r)
1244  {
1245  unsigned max_nb = sv.size() >> bm::set_block_shift;
1246  if (nb_l != max_nb)
1247  {
1248  // linear in-place fixed depth scan to identify the sub-range
1250  int cmp = this->compare_str(sv, mid, str);
1251  if (cmp < 0)
1252  {
1253  l = mid;
1254  mid = nb_r * bm::gap_max_bits + bm::sub_block3_size * 2;
1255  cmp = this->compare_str(sv, mid, str);
1256  if (cmp < 0)
1257  {
1258  l = mid;
1259  mid = nb_r * bm::gap_max_bits + bm::sub_block3_size * 3;
1260  cmp = this->compare_str(sv, mid, str);
1261  if (cmp < 0)
1262  l = mid;
1263  else
1264  r = mid;
1265  }
1266  else
1267  {
1268  r = mid;
1269  }
1270  }
1271  else
1272  {
1273  r = mid;
1274  }
1275  }
1276  }
1277 
1278  set_search_range(l, r);
1279  break;
1280  }
1281 
1282  typename SV::size_type mid = dist/2+l;
1283  unsigned nb = unsigned(mid >> bm::set_block_shift);
1284  mid = nb * bm::gap_max_bits;
1285  if (mid <= l)
1286  {
1287  if (nb == 0 && r > bm::gap_max_bits)
1288  mid = bm::gap_max_bits;
1289  else
1290  mid = dist / 2 + l;
1291  }
1292  BM_ASSERT(mid > l);
1293 
1294  int cmp = this->compare_str(sv, mid, str);
1295  if (cmp == 0)
1296  {
1297  found_pos = mid;
1298  found = true;
1299  set_search_range(l, mid);
1300  break;
1301  }
1302  if (cmp < 0)
1303  l = mid+1;
1304  else
1305  r = mid-1;
1306  } // while
1307 
1308  // use linear search (range is set)
1309  found = find_first_eq(sv, str, found_pos, remaped);
1310  if (found)
1311  {
1312  pos = found_pos;
1313  if (bm::conditional<SV::is_rsc_support::value>::test()) // test rank/select trait
1314  {
1315  if (sv.is_compressed()) // if compressed vector - need rank translation
1316  found = sv.find_rank(found_pos + 1, pos);
1317  }
1318  }
1319  reset_search_range();
1320  }
1321  else // search for zero value
1322  {
1323  // TODO: implement optimized version which would work without temp vector
1324  typename SV::bvector_type bv_zero;
1325  find_zero(sv, bv_zero);
1326  found = bv_zero.find(pos);
1327  }
1328  return found;
1329 }
1330 
1331 //----------------------------------------------------------------------------
1332 
1333 template<typename SV>
1334 bool sparse_vector_scanner<SV>::bfind_eq_str(const typename SV::value_type* str,
1335  typename SV::size_type& pos)
1336 {
1337  BM_ASSERT(bound_sv_);
1338  return bfind_eq_str(*bound_sv_, str, pos);
1339 }
1340 
1341 //----------------------------------------------------------------------------
1342 
1343 template<typename SV>
1345  size_type idx,
1346  const value_type* str)
1347 {
1348  if (bound_sv_ == &sv)
1349  {
1350  unsigned nb = unsigned(idx >> bm::set_block_shift);
1351  unsigned nbit = unsigned(idx & bm::set_block_mask);
1352  if (nbit == 0) // access to sentinel, first block element
1353  {
1354  value_type* s0 = block0_elements_cache_.row(nb);
1355  if (*s0 == 0) // uninitialized element
1356  {
1357  sv.get(idx, s0, block0_elements_cache_.cols());
1358  }
1359  int res = 0;
1360  for (unsigned i = 0; i < block0_elements_cache_.cols(); ++i)
1361  {
1362  char octet = str[i]; char value = s0[i];
1363  res = (value > octet) - (value < octet);
1364  if (res || !octet)
1365  break;
1366  } // for i
1367  BM_ASSERT(res == sv.compare(idx, str));
1368  return res;
1369  }
1370  else
1371  {
1372  if (nbit % bm::sub_block3_size == 0) // TODO: use AND mask here
1373  {
1374  size_type k = nbit / bm::sub_block3_size - 1;
1375  value_type* s1 = block3_elements_cache_.row(nb * 3 + k);
1376  int res = 0;
1377  for (unsigned i = 0; i < block3_elements_cache_.cols(); ++i)
1378  {
1379  char octet = str[i]; char value = s1[i];
1380  res = (value > octet) - (value < octet);
1381  if (res || !octet)
1382  break;
1383  } // for i
1384  BM_ASSERT(res == sv.compare(idx, str));
1385  return res;
1386  }
1387  }
1388  }
1389  return sv.compare(idx, str);
1390 }
1391 
1392 //----------------------------------------------------------------------------
1393 
1394 template<typename SV>
1396  typename SV::value_type value,
1397  typename SV::bvector_type& bv_out)
1398 {
1399  if (sv.empty())
1400  {
1401  bv_out.clear();
1402  return; // nothing to do
1403  }
1404  if (!value)
1405  {
1406  find_zero(sv, bv_out);
1407  return;
1408  }
1409 
1410  find_eq_with_nulls(sv, value, bv_out, 0);
1411 
1412  decompress(sv, bv_out);
1413  correct_nulls(sv, bv_out);
1414 }
1415 
1416 //----------------------------------------------------------------------------
1417 
1418 template<typename SV>
1420  typename SV::value_type value,
1421  typename SV::size_type& pos)
1422 {
1423  if (!value) // zero value - special case
1424  {
1425  bvector_type bv_zero;
1426  find_eq(sv, value, bv_zero);
1427  bool found = bv_zero.find(pos);
1428  return found;
1429  }
1430 
1431  bm::id_t found_pos;
1432  bool found = find_first_eq(sv, value, found_pos);
1433  if (found)
1434  {
1435  pos = found_pos;
1436  if (bm::conditional<SV::is_rsc_support::value>::test()) // test rank/select trait
1437  {
1438  if (sv.is_compressed()) // if compressed vector - need rank translation
1439  found = sv.find_rank(found_pos + 1, pos);
1440  }
1441  }
1442  return found;
1443 }
1444 
1445 //----------------------------------------------------------------------------
1446 
1447 template<typename SV>
1449  typename SV::bvector_type& bv_out)
1450 {
1451  agg_.reset(); // in case if previous scan was interrupted
1452  for (unsigned i = 0; i < sv.plains(); ++i)
1453  agg_.add(sv.get_plain(i));
1454  agg_.combine_or(bv_out);
1455  agg_.reset();
1456 }
1457 
1458 //----------------------------------------------------------------------------
1459 
1460 template<typename SV>
1462  typename SV::bvector_type& bv_out)
1463 {
1464  if (!sv.is_compressed())
1465  return; // nothing to do
1466  const bvector_type* bv_non_null = sv.get_null_bvector();
1467  BM_ASSERT(bv_non_null);
1468 
1469  // TODO: implement faster decompressor for small result-sets
1470  rank_compr_.decompress(bv_tmp_, *bv_non_null, bv_out);
1471  bv_out.swap(bv_tmp_);
1472 }
1473 
1474 //----------------------------------------------------------------------------
1475 
1476 template<typename SV>
1478 {
1479  BM_ASSERT(from < to);
1480  mask_from_ = from;
1481  mask_to_ = to;
1482  mask_set_ = true;
1483 }
1484 
1485 //----------------------------------------------------------------------------
1486 
1487 template<typename SV>
1489 {
1490  mask_set_ = false;
1491  mask_from_ = mask_to_ = bm::id_max;
1492 }
1493 
1494 
1495 //----------------------------------------------------------------------------
1496 //
1497 //----------------------------------------------------------------------------
1498 
1499 
1500 } // namespace bm
1501 
1502 #include "bmundef.h"
1503 
1504 #endif
bm::heap_matrix< value_type, bm::set_total_blocks *3, max_columns, typename bvector_type::allocator_type > heap_matrix_type3
SV::bvector_type bvector_type
const SV * sv_ptr_
current translation table vector
allocator_pool_type pool_
void find_eq(const SV &sv, typename SV::value_type value, typename SV::bvector_type &bv_out)
find all sparse vector elements EQ to search value
#define BM_VECT_ALIGN
Definition: bmdef.h:293
BMFORCEINLINE bm::id_t word_bitcount(bm::id_t w)
Definition: bmfunc.h:179
ad-hoc conditional expressions
Definition: bmfunc.h:123
gather_buffer_type * gb_
intermediate buffers
void dynamic_range_clip_low(SV &svect, unsigned low_bit)
Clip dynamic range for signal lower than specified (boost)
void bind(const SV &sv, bool sorted)
bind sparse vector for all searches
const bvector_type * bvector_type_const_ptr
void invert(const SV &sv, typename SV::bvector_type &bv_out)
invert search result ("EQ" to "not EQ")
unsigned long long int id64_t
Definition: bmconst.h:32
Sparse constainer sparse_vector<> for integer types using bit-transposition transform.
bvector_type bv_zero_
bit-vector for zero elements
void attach_sv(const SV *sv_brel, bool compute_stats=false)
Attach a translation table vector for remapping (Image function)
void find_eq(const SV &sv, It start, It end, typename SV::bvector_type &bv_out)
find all values A IN (C, D, E, F)
Definition: bm.h:69
bool find_eq_with_nulls(const SV &sv, typename SV::value_type value, typename SV::bvector_type &bv_out, typename SV::size_type search_limit=0)
find value (may include NULL indexes)
pre-processor un-defines to avoid global space pollution (internal)
algorithms for sparse_vector scan/seach
size_type BM_VECT_ALIGN gather_idx_ [BSIZE] BM_VECT_ALIGN_ATTR
void reset_binding()
reset sparse vector binding
gather_buffer< sv_g_size > gather_buffer_type
int compare_str(const SV &sv, size_type idx, const value_type *str)
const unsigned id_max
Definition: bmconst.h:44
void remap(const bvector_type &bv_in, bvector_type &bv_out)
Perform remapping (Image function) (based on attached translation table)
void reset_search_range()
reset (disable) search range
bvector_type bv_product_
temp vector
Algorithms for fast aggregation of N bvectors.
void operator=(const sparse_vector_scanner &)=delete
void set_search_range(size_type from, size_type to)
set search boundaries (hint for the aggregator)
input set is sorted (ascending order)
Definition: bmconst.h:168
const unsigned sub_block3_size
Definition: bmconst.h:96
void one_pass_run(const bvector_type &bv_in, const SV &sv_brel, bvector_type &bv_out)
bool prepare_and_sub_aggregator(const SV &sv, typename SV::value_type value)
Prepare aggregator for AND-SUB (EQ) search.
bool find_eq_str(const SV &sv, const typename SV::value_type *str, typename SV::size_type &pos)
find first sparse vector element (string)
Definitions(internal)
void find_zero(const SV &sv, typename SV::bvector_type &bv_out)
find all sparse vector elements EQ to 0
bm::heap_matrix< value_type, bm::set_total_blocks, max_columns, typename bvector_type::allocator_type > heap_matrix_type0
void find_nonzero(const SV &sv, typename SV::bvector_type &bv_out)
Find non-zero elements Output vector is computed as a logical OR (join) of all plains.
bool find_first_eq(const SV &sv, typename SV::value_type value, bm::id_t &idx)
find first value (may include NULL indexes)
const unsigned gap_max_bits
Definition: bmconst.h:73
value_type BM_VECT_ALIGN buffer_ [BSIZE] BM_VECT_ALIGN_ATTR
bvector_type::allocator_type::allocator_pool_type allocator_pool_type
const unsigned set_block_mask
Definition: bmconst.h:50
void find_eq_with_nulls_horizontal(const SV &sv, typename SV::value_type value, typename SV::bvector_type &bv_out)
For testing purposes only.
void run(const bvector_type &bv_in, const SV &sv_brel, bvector_type &bv_out)
Run remap transformation.
unsigned int id_t
Definition: bmconst.h:35
unsigned short bitscan(V w, B *bits)
Definition: bmfunc.h:503
SV::bvector_type bvector_type
void decompress(const SV &sv, typename SV::bvector_type &bv_out)
Rank-Select decompression for RSC vectors.
#define BM_ASSERT
Definition: bmdef.h:116
const unsigned set_total_blocks
Definition: bmconst.h:85
const bvector_type & get_bv_zero() const
Get read access to zero-elements vector Zero vector gets populated after attach_sv() is called or as ...
const unsigned set_block_shift
Definition: bmconst.h:49
void correct_nulls(const SV &sv, typename SV::bvector_type &bv_out)
Exclude possible NULL values from the result vector.
bvector_type::allocator_type::allocator_pool_type allocator_pool_type
void dynamic_range_clip_high(SV &svect, unsigned high_bit)
Clip dynamic range for signal higher than specified.
sorted and in one block (internal!)
Definition: bmconst.h:169
bool have_stats_
flag of statistics presense
bool bfind_eq_str(const SV &sv, const typename SV::value_type *str, typename SV::size_type &pos)
binary find first sparse vector element (string) Sparse vector must be sorted.
Integer set to set transformation (functional image in groups theory) https://en.wikipedia.org/wiki/Image_(mathematics)