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 "bmdef.h"
28 
29 
30 /** \defgroup svalgo Sparse vector algorithms
31  Sparse vector algorithms
32  \ingroup svector
33  */
34 
35 
36 namespace bm
37 {
38 
39 
40 /*!
41  \brief Clip dynamic range for signal higher than specified
42 
43  \param svect - sparse vector to do clipping
44  \param high_bit - max bit (inclusive) allowed for this signal vector
45 
46 
47  \ingroup svalgo
48  \sa dynamic_range_clip_low
49 */
50 template<typename SV>
51 void dynamic_range_clip_high(SV& svect, unsigned high_bit)
52 {
53  unsigned sv_plains = svect.plains();
54 
55  BM_ASSERT(sv_plains > high_bit && high_bit > 0);
56 
57  typename SV::bvector_type bv_acc;
58  unsigned i;
59 
60  // combine all the high bits into accumulator vector
61  for (i = high_bit+1; i < sv_plains; ++i)
62  {
63  typename SV::bvector_type* bv_plain = svect.plain(i);
64  if (bv_plain)
65  {
66  bv_acc.bit_or(*bv_plain);
67  svect.free_plain(i);
68  }
69  } // for i
70 
71  // set all bits ON for all low vectors, which happen to be clipped
72  for (i = high_bit; true; --i)
73  {
74  typename SV::bvector_type* bv_plain = svect.get_plain(i);
75  bv_plain->bit_or(bv_acc);
76  if (i == 0)
77  break;
78  } // for i
79 }
80 
81 
82 /*!
83  \brief Clip dynamic range for signal lower than specified (boost)
84 
85  \param svect - sparse vector to do clipping
86  \param low_bit - low bit (inclusive) allowed for this signal vector
87 
88  \ingroup svalgo
89  \sa dynamic_range_clip_high
90 */
91 template<typename SV>
92 void dynamic_range_clip_low(SV& svect, unsigned low_bit)
93 {
94  if (low_bit == 0) return; // nothing to do
95  BM_ASSERT(svect.plains() > low_bit);
96 
97  unsigned sv_plains = svect.plains();
98  typename SV::bvector_type bv_acc1;
99  unsigned i;
100 
101  // combine all the high bits into accumulator vector
102  for (i = low_bit+1; i < sv_plains; ++i)
103  {
104  typename SV::bvector_type* bv_plain = svect.plain(i);
105  if (bv_plain)
106  bv_acc1.bit_or(*bv_plain);
107  } // for i
108 
109  // accumulate all vectors below the clipping point
110  typename SV::bvector_type bv_acc2;
111  typename SV::bvector_type* bv_low_plain = svect.get_plain(low_bit);
112 
113  for (i = low_bit-1; true; --i)
114  {
115  typename SV::bvector_type* bv_plain = svect.plain(i);
116  if (bv_plain)
117  {
118  bv_acc2.bit_or(*bv_plain);
119  svect.free_plain(i);
120  if (i == 0)
121  break;
122  }
123  } // for i
124 
125  // now we want to set 1 in the clipping low plain based on
126  // exclusive or (XOR) between upper and lower parts)
127  // as a result high signal (any bits in the upper plains) gets
128  // slightly lower value (due to clipping) low signal gets amplified
129  // (lower contrast algorithm)
130 
131  bv_acc1.bit_xor(bv_acc2);
132  bv_low_plain->bit_or(bv_acc1);
133 }
134 
135 
136 /**
137  \brief algorithms for sparse_vector scan/seach
138 
139  Scanner uses properties of bit-vector plains to answer questions
140  like "find all sparse vector elements equivalent to XYZ".
141 
142  Class uses fast algorithms based on properties of bit-plains.
143  This is NOT a brute force, direct scan.
144 
145  @ingroup svalgo
146  @ingroup setalgo
147 */
148 template<typename SV>
150 {
151 public:
152  typedef typename SV::bvector_type bvector_type;
153  typedef const bvector_type* bvector_type_const_ptr;
154  typedef bvector_type* bvector_type_ptr;
155  typedef typename SV::value_type value_type;
156  typedef typename SV::size_type size_type;
157  typedef typename bvector_type::allocator_type::allocator_pool_type allocator_pool_type;
158 
159 public:
161 
162  /**
163  \brief find all sparse vector elements EQ to search value
164 
165  Find all sparse vector elements equivalent to specified value
166 
167  \param sv - input sparse vector
168  \param value - value to search for
169  \param bv_out - output bit-vector (search result masks 1 elements)
170  */
171  void find_eq(const SV& sv,
172  typename SV::value_type value,
173  typename SV::bvector_type& bv_out);
174 
175  /**
176  \brief find first sparse vector element
177 
178  Find all sparse vector elements equivalent to specified value.
179  Works well if sperse vector represents unordered set
180 
181  \param sv - input sparse vector
182  \param value - value to search for
183  \param pos - output found sparse vector element index
184 
185  \return true if found
186  */
187  bool find_eq(const SV& sv,
188  typename SV::value_type value,
189  typename SV::size_type& pos);
190 
191 
192  /**
193  \brief find all sparse vector elements EQ to 0
194  \param sv - input sparse vector
195  \param bv_out - output bit-vector (search result masks 1 elements)
196  */
197  void find_zero(const SV& sv,
198  typename SV::bvector_type& bv_out);
199 
200  /*!
201  \brief Find non-zero elements
202  Output vector is computed as a logical OR (join) of all plains
203 
204  \param sv - input sparse vector
205  \param bv_out - output bit-bector of non-zero elements
206  */
207  void find_nonzero(const SV& sv, typename SV::bvector_type& bv_out);
208 
209  /**
210  \brief invert search result ("EQ" to "not EQ")
211 
212  \param sv - input sparse vector
213  \param bv_out - output bit-bector of non-zero elements
214  */
215  void invert(const SV& sv, typename SV::bvector_type& bv_out);
216 
217  /**
218  \brief find all values A IN (C, D, E, F)
219  \param sv - input sparse vector
220  \param start - start iterator (set to search)
221  \param end - end iterator (set to search)
222  \param bv_out - output bit-bector of non-zero elements
223  */
224  template<typename It>
225  void find_eq(const SV& sv,
226  It start,
227  It end,
228  typename SV::bvector_type& bv_out)
229  {
230  typename bvector_type::mem_pool_guard mp_guard;
231  mp_guard.assign_if_not_set(pool_, bv_out); // set algorithm-local memory pool to avoid heap contention
232 
233  bvector_type bv1;
234  typename bvector_type::mem_pool_guard mp_guard1(pool_, bv1);
235  bool any_zero = false;
236  for (; start < end; ++start)
237  {
238  value_type v = *start;
239  any_zero |= (v == 0);
240  bool found = find_eq_with_nulls(sv, v, bv1);
241  if (found)
242  bv_out.bit_or(bv1);
243  else
244  {
245  BM_ASSERT(!bv1.any());
246  }
247  } // for
248  if (any_zero)
249  correct_nulls(sv, bv_out);
250  }
251 
252  /// For testing purposes only
253  ///
254  /// @internal
255  void find_eq_with_nulls_horizontal(const SV& sv,
256  typename SV::value_type value,
257  typename SV::bvector_type& bv_out);
258 
259  /** Exclude possible NULL values from the result vector
260  \param sv - input sparse vector
261  \param bv_out - output bit-bector of non-zero elements
262  */
263  void correct_nulls(const SV& sv, typename SV::bvector_type& bv_out);
264 
265 protected:
266  /// find value (may include NULL indexes)
267  bool find_eq_with_nulls(const SV& sv,
268  typename SV::value_type value,
269  typename SV::bvector_type& bv_out,
270  typename SV::size_type search_limit = 0);
271 
272  /// find first value (may include NULL indexes)
273  bool find_first_eq(const SV& sv,
274  typename SV::value_type value,
275  bm::id_t& idx);
276 
277  /// Prepare aggregator for AND-SUB (EQ) search
278  bool prepare_and_sub_aggregator(const SV& sv,
279  typename SV::value_type value);
280 
281  /// Rank-Select decompression for RSC vectors
282  void decompress(const SV& sv, typename SV::bvector_type& bv_out);
283 protected:
285  void operator=(const sparse_vector_scanner&) = delete;
286 
287 private:
288  allocator_pool_type pool_;
289  bvector_type bv_tmp_;
292 };
293 
294 
295 /*!
296  \brief Integer set to set transformation (functional image in groups theory)
297  https://en.wikipedia.org/wiki/Image_(mathematics)
298 
299  Input sets gets translated through the function, which is defined as
300  "one to one (or NULL)" binary relation object (sparse_vector).
301  Also works for M:1 relationships.
302 
303  \ingroup svalgo
304  \ingroup setalgo
305 */
306 template<typename SV>
308 {
309 public:
310  typedef typename SV::bvector_type bvector_type;
311  typedef typename SV::value_type value_type;
312  typedef typename SV::size_type size_type;
313  typedef typename bvector_type::allocator_type::allocator_pool_type allocator_pool_type;
314 public:
315 
318 
319 
320  /** Get read access to zero-elements vector
321  Zero vector gets populated after attach_sv() is called
322  or as a side-effect of remap() with immediate sv param
323  */
324  const bvector_type& get_bv_zero() const { return bv_zero_; }
325 
326  /** Perform remapping (Image function) (based on attached translation table)
327 
328  \param bv_in - input set, defined as a bit-vector
329  \param bv_out - output set as a bit-vector
330 
331  @sa attach_sv
332  */
333  void remap(const bvector_type& bv_in,
334  bvector_type& bv_out);
335 
336  /** Perform remapping (Image function)
337 
338  \param bv_in - input set, defined as a bit-vector
339  \param sv_brel - binary relation (translation table) sparse vector
340  \param bv_out - output set as a bit-vector
341  */
342  void remap(const bvector_type& bv_in,
343  const SV& sv_brel,
344  bvector_type& bv_out);
345 
346  /** Remap single set element
347 
348  \param id_from - input value
349  \param sv_brel - translation table sparse vector
350  \param id_to - out value
351 
352  \return - true if value was found and remapped
353  */
354  bool remap(size_type id_from, const SV& sv_brel, size_type& id_to);
355 
356 
357  /** Run remap transformation
358 
359  \param bv_in - input set, defined as a bit-vector
360  \param sv_brel - translation table sparse vector
361  \param bv_out - output set as a bit-vector
362 
363  @sa remap
364  */
365  void run(const bvector_type& bv_in,
366  const SV& sv_brel,
367  bvector_type& bv_out)
368  {
369  remap(bv_in, sv_brel, bv_out);
370  }
371 
372  /** Attach a translation table vector for remapping (Image function)
373 
374  \param sv_brel - binary relation sparse vector pointer
375  (pass NULL to detach)
376  \param compute_stats - flag to perform computation of some statistics
377  later used in remapping. This only make sense
378  for series of remappings on the same translation
379  vector.
380  @sa remap
381  */
382  void attach_sv(const SV* sv_brel, bool compute_stats = false);
383 
384 
385 protected:
386  void one_pass_run(const bvector_type& bv_in,
387  const SV& sv_brel,
388  bvector_type& bv_out);
389 
390  /// @internal
391  template<unsigned BSIZE>
393  {
394  size_type BM_VECT_ALIGN gather_idx_[BSIZE] BM_VECT_ALIGN_ATTR;
395  value_type BM_VECT_ALIGN buffer_[BSIZE] BM_VECT_ALIGN_ATTR;
396  };
397 
399  {
400  sv_g_size = 1024 * 8
401  };
403 
404 
405 protected:
407  void operator=(const set2set_11_transform&) = delete;
408 
409 protected:
410  const SV* sv_ptr_; ///< current translation table vector
411  gather_buffer_type* gb_; ///< intermediate buffers
412  bvector_type bv_product_;///< temp vector
413 
414  bool have_stats_; ///< flag of statistics presense
415  bvector_type bv_zero_; ///< bit-vector for zero elements
416 
417  allocator_pool_type pool_;
418 };
419 
420 
421 
422 //----------------------------------------------------------------------------
423 //
424 //----------------------------------------------------------------------------
425 
426 template<typename SV>
428 : sv_ptr_(0), gb_(0), have_stats_(false)
429 {
430  gb_ = (gather_buffer_type*)::malloc(sizeof(gather_buffer_type));
431  if (!gb_)
432  {
433  SV::throw_bad_alloc();
434  }
435 }
436 
437 //----------------------------------------------------------------------------
438 
439 template<typename SV>
441 {
442  if (gb_)
443  ::free(gb_);
444 }
445 
446 
447 //----------------------------------------------------------------------------
448 
449 template<typename SV>
450 void set2set_11_transform<SV>::attach_sv(const SV* sv_brel, bool compute_stats)
451 {
452  sv_ptr_ = sv_brel;
453  if (!sv_ptr_)
454  {
455  have_stats_ = false;
456  }
457  else
458  {
459  if (sv_brel->empty() || !compute_stats)
460  return; // nothing to do
461  const bvector_type* bv_non_null = sv_brel->get_null_bvector();
462  if (bv_non_null)
463  return; // already have 0 elements vector
464 
465 
466  typename bvector_type::mem_pool_guard mp_g_z;
467  mp_g_z.assign_if_not_set(pool_, bv_zero_);
468 
470  scanner.find_zero(*sv_brel, bv_zero_);
471  have_stats_ = true;
472  }
473 }
474 
475 //----------------------------------------------------------------------------
476 
477 template<typename SV>
479  const SV& sv_brel,
480  size_type& id_to)
481 {
482  if (sv_brel.empty())
483  return false; // nothing to do
484 
485  const bvector_type* bv_non_null = sv_brel.get_null_bvector();
486  if (bv_non_null)
487  {
488  if (!bv_non_null->test(id_from))
489  return false;
490  }
491  size_type idx = sv_brel.translate_address(id_from);
492  id_to = sv_brel.get(idx);
493  return true;
494 }
495 
496 //----------------------------------------------------------------------------
497 
498 template<typename SV>
500  const SV& sv_brel,
501  bvector_type& bv_out)
502 {
503  typename bvector_type::mem_pool_guard mp_g_out, mp_g_p, mp_g_z;
504  mp_g_out.assign_if_not_set(pool_, bv_out);
505  mp_g_p.assign_if_not_set(pool_, bv_product_);
506  mp_g_z.assign_if_not_set(pool_, bv_zero_);
507 
508  attach_sv(&sv_brel);
509 
510  remap(bv_in, bv_out);
511 
512  attach_sv(0); // detach translation table
513 }
514 
515 template<typename SV>
517  bvector_type& bv_out)
518 {
520 
521  bv_out.clear();
522 
523  if (sv_ptr_ == 0 || sv_ptr_->empty())
524  return; // nothing to do
525 
526  bv_out.init(); // just in case to "fast set" later
527 
528  typename bvector_type::mem_pool_guard mp_g_out, mp_g_p, mp_g_z;
529  mp_g_out.assign_if_not_set(pool_, bv_out);
530  mp_g_p.assign_if_not_set(pool_, bv_product_);
531  mp_g_z.assign_if_not_set(pool_, bv_zero_);
532 
533 
534  const bvector_type* enum_bv;
535 
536  const bvector_type * bv_non_null = sv_ptr_->get_null_bvector();
537  if (bv_non_null)
538  {
539  // TODO: optimize with 2-way ops
540  bv_product_ = bv_in;
541  bv_product_.bit_and(*bv_non_null);
542  enum_bv = &bv_product_;
543  }
544  else // non-NULL vector is not available
545  {
546  enum_bv = &bv_in;
547  // if we have any elements mapping into "0" on the other end
548  // we map it once (chances are there are many duplicates)
549  //
550 
551  if (have_stats_) // pre-attached translation statistics
552  {
553  bv_product_ = bv_in;
554  unsigned cnt1 = bv_product_.count();
555  bv_product_.bit_sub(bv_zero_);
556  unsigned cnt2 = bv_product_.count();
557 
558  BM_ASSERT(cnt2 <= cnt1);
559 
560  if (cnt1 != cnt2) // mapping included 0 elements
561  bv_out.set_bit_no_check(0);
562 
563  enum_bv = &bv_product_;
564  }
565  }
566 
567 
568 
569  unsigned buf_cnt, nb_old, nb;
570  buf_cnt = nb_old = 0;
571 
572  typename bvector_type::enumerator en(enum_bv->first());
573  for (; en.valid(); ++en)
574  {
575  typename SV::size_type idx = *en;
576  idx = sv_ptr_->translate_address(idx);
577 
578  nb = unsigned(idx >> bm::set_block_shift);
579  if (nb != nb_old) // new blocks
580  {
581  if (buf_cnt)
582  {
583  sv_ptr_->gather(&gb_->buffer_[0], &gb_->gather_idx_[0], buf_cnt, BM_SORTED_UNIFORM);
584  bm::combine_or(bv_out, &gb_->buffer_[0], &gb_->buffer_[buf_cnt]);
585  buf_cnt ^= buf_cnt;
586  }
587  nb_old = nb;
588  gb_->gather_idx_[buf_cnt++] = idx;
589  }
590  else
591  {
592  gb_->gather_idx_[buf_cnt++] = idx;
593  }
594 
595  if (buf_cnt == sv_g_size)
596  {
597  sv_ptr_->gather(&gb_->buffer_[0], &gb_->gather_idx_[0], buf_cnt, BM_SORTED_UNIFORM);
598  bm::combine_or(bv_out, &gb_->buffer_[0], &gb_->buffer_[buf_cnt]);
599  buf_cnt ^= buf_cnt;
600  }
601  } // for en
602  if (buf_cnt)
603  {
604  sv_ptr_->gather(&gb_->buffer_[0], &gb_->gather_idx_[0], buf_cnt, BM_SORTED_UNIFORM);
605  bm::combine_or(bv_out, &gb_->buffer_[0], &gb_->buffer_[buf_cnt]);
606  }
607 
608 }
609 
610 
611 //----------------------------------------------------------------------------
612 
613 template<typename SV>
615  const SV& sv_brel,
616  bvector_type& bv_out)
617 {
618  if (sv_brel.empty())
619  return; // nothing to do
620 
621  bv_out.init();
622 
623  typename SV::const_iterator it = sv_brel.begin();
624  for (; it.valid(); ++it)
625  {
626  typename SV::value_type t_id = *it;
627  bm::id_t idx = it.pos();
628  if (bv_in.test(idx))
629  {
630  bv_out.set_bit_no_check(t_id);
631  }
632  } // for
633 }
634 
635 
636 //----------------------------------------------------------------------------
637 //
638 //----------------------------------------------------------------------------
639 
640 template<typename SV>
642  typename SV::bvector_type& bv_out)
643 {
644  if (sv.size() == 0)
645  {
646  bv_out.clear();
647  return;
648  }
649 
650  find_nonzero(sv, bv_out);
651  if (sv.is_compressed())
652  {
653  bv_out.invert();
654  bv_out.set_range(sv.effective_size(), bm::id_max - 1, false);
655  decompress(sv, bv_out);
656  }
657  else
658  {
659  invert(sv, bv_out);
660  }
661  correct_nulls(sv, bv_out);
662 }
663 
664 //----------------------------------------------------------------------------
665 
666 template<typename SV>
667 void sparse_vector_scanner<SV>::invert(const SV& sv, typename SV::bvector_type& bv_out)
668 {
669  if (sv.size() == 0)
670  {
671  bv_out.clear();
672  return;
673  }
674  bv_out.invert();
675  const bvector_type* bv_null = sv.get_null_bvector();
676  if (bv_null) // correct result to only use not NULL elements
677  bv_out &= *bv_null;
678  else
679  bv_out.set_range(sv.size(), bm::id_max - 1, false);
680 }
681 
682 //----------------------------------------------------------------------------
683 
684 template<typename SV>
686  typename SV::bvector_type& bv_out)
687 {
688  const bvector_type* bv_null = sv.get_null_bvector();
689  if (bv_null) // correct result to only use not NULL elements
690  bv_out.bit_and(*bv_null);
691 }
692 
693 //----------------------------------------------------------------------------
694 
695 template<typename SV>
697  typename SV::value_type value,
698  typename SV::bvector_type& bv_out,
699  typename SV::size_type search_limit)
700 {
701  if (sv.empty())
702  return false; // nothing to do
703 
704  if (!value)
705  {
706  find_zero(sv, bv_out);
707  return bv_out.any();
708  }
709  agg_.reset();
710 
711  bool found = prepare_and_sub_aggregator(sv, value);
712  if (!found)
713  {
714  bv_out.clear();
715  return found;
716  }
717 
718  bool any = (search_limit == 1);
719  found = agg_.combine_and_sub(bv_out, any);
720  agg_.reset();
721  return found;
722 }
723 
724 //----------------------------------------------------------------------------
725 
726 template<typename SV>
728  typename SV::value_type value,
729  bm::id_t& idx)
730 {
731  if (sv.empty())
732  return false; // nothing to do
733 
734  BM_ASSERT(value); // cannot handle zero values
735  if (!value)
736  return false;
737 
738  agg_.reset();
739  bool found = prepare_and_sub_aggregator(sv, value);
740  if (!found)
741  return found;
742  found = agg_.find_first_and_sub(idx);
743  agg_.reset();
744  return found;
745 }
746 
747 //----------------------------------------------------------------------------
748 
749 template<typename SV>
751  typename SV::value_type value)
752 {
753  unsigned char bits[sizeof(value) * 8];
754  unsigned short bit_count_v = bm::bitscan(value, bits);
755  BM_ASSERT(bit_count_v);
756 
757  // prep the lists for combined AND-SUB aggregator
758  // (backward order has better chance for bit reduction on AND)
759 
760  for (unsigned i = bit_count_v; i > 0; --i)
761  {
762  unsigned bit_idx = bits[i-1];
763  BM_ASSERT(value & (value_type(1) << bit_idx));
764  const bvector_type* bv = sv.get_plain(bit_idx);
765  if (bv)
766  agg_.add(bv);
767  else
768  {
769  return false;
770  }
771  }
772 
773  unsigned sv_plains = sv.effective_plains();
774  for (unsigned i = 0; (i < sv_plains) && value; ++i)
775  {
776  bvector_type_const_ptr bv = sv.get_plain(i);
777  if (bv && !(value & (value_type(1) << i)))
778  agg_.add(bv, 1); // agg to SUB group
779  } // for i
780  return true;
781 }
782 
783 
784 //----------------------------------------------------------------------------
785 
786 template<typename SV>
788  typename SV::value_type value,
789  typename SV::bvector_type& bv_out)
790 {
791  if (sv.empty())
792  return; // nothing to do
793 
794  if (!value)
795  {
796  find_zero(sv, bv_out);
797  return;
798  }
799 
800  unsigned char bits[sizeof(value) * 8];
801  unsigned short bit_count_v = bm::bitscan(value, bits);
802  BM_ASSERT(bit_count_v);
803 
804  // aggregate AND all matching vectors
805  {
806  const bvector_type* bv_plain = sv.get_plain(bits[--bit_count_v]);
807  if (bv_plain)
808  bv_out = *bv_plain;
809  else // plain not found
810  {
811  bv_out.clear();
812  return;
813  }
814  }
815  for (unsigned i = 0; i < bit_count_v; ++i)
816  {
817  const bvector_type* bv_plain = sv.get_plain(bits[i]);
818  if (bv_plain)
819  bv_out &= *bv_plain;
820  else // mandatory plain not found - empty result!
821  {
822  bv_out.clear();
823  return;
824  }
825  } // for i
826 
827  // SUB all other plains
828  unsigned sv_plains = sv.effective_plains();
829  for (unsigned i = 0; (i < sv_plains) && value; ++i)
830  {
831  const bvector_type* bv_plain = sv.get_plain(i);
832  if (bv_plain && !(value & (value_type(1) << i)))
833  bv_out -= *bv_plain;
834  }
835 }
836 
837 
838 //----------------------------------------------------------------------------
839 
840 template<typename SV>
842  typename SV::value_type value,
843  typename SV::bvector_type& bv_out)
844 {
845  if (sv.empty())
846  {
847  bv_out.clear();
848  return; // nothing to do
849  }
850 
851  if (!value)
852  {
853  find_zero(sv, bv_out);
854  return;
855  }
856 
857  find_eq_with_nulls(sv, value, bv_out, 0);
858 
859  decompress(sv, bv_out);
860  correct_nulls(sv, bv_out);
861 }
862 
863 //----------------------------------------------------------------------------
864 
865 template<typename SV>
867  typename SV::value_type value,
868  typename SV::size_type& pos)
869 {
870  if (!value) // zero value - special case
871  {
872  bvector_type bv_zero;
873  find_eq(sv, value, bv_zero);
874  bool found = bv_zero.find(pos);
875  return found;
876  }
877 
878  bm::id_t found_pos;
879  bool found = find_first_eq(sv, value, found_pos);
880  if (found)
881  {
882  if (sv.is_compressed()) // if compressed vector - need rank translation
883  found = sv.find_rank(found_pos + 1, pos);
884  else
885  pos = found_pos;
886  }
887  return found;
888 }
889 
890 //----------------------------------------------------------------------------
891 
892 template<typename SV>
894  typename SV::bvector_type& bv_out)
895 {
896  agg_.reset(); // in case if previous scan was interrupted
897  for (unsigned i = 0; i < sv.plains(); ++i)
898  agg_.add(sv.get_plain(i));
899  agg_.combine_or(bv_out);
900  agg_.reset();
901 }
902 
903 //----------------------------------------------------------------------------
904 
905 template<typename SV>
907  typename SV::bvector_type& bv_out)
908 {
909  if (!sv.is_compressed())
910  return; // nothing to do
911  const bvector_type* bv_non_null = sv.get_null_bvector();
912  BM_ASSERT(bv_non_null);
913 
914  // TODO: implement faster decompressor for small result-sets
915  rank_compr_.decompress(bv_tmp_, *bv_non_null, bv_out);
916  bv_out.swap(bv_tmp_);
917 }
918 
919 
920 //----------------------------------------------------------------------------
921 //
922 //----------------------------------------------------------------------------
923 
924 
925 } // namespace bm
926 
927 #include "bmundef.h"
928 
929 #endif
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
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)
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")
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:70
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
void combine_or(BV &bv, It first, It last)
OR Combine bitvector and the iterable sequence.
Definition: bmalgo_impl.h:1134
size_type BM_VECT_ALIGN gather_idx_ [BSIZE] BM_VECT_ALIGN_ATTR
gather_buffer< sv_g_size > gather_buffer_type
const unsigned id_max
Definition: bmconst.h:43
void remap(const bvector_type &bv_in, bvector_type &bv_out)
Perform remapping (Image function) (based on attached translation table)
bvector_type bv_product_
temp vector
Algorithms for fast aggregation of N bvectors.
void operator=(const sparse_vector_scanner &)=delete
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.
Definitions(internal)
void find_zero(const SV &sv, typename SV::bvector_type &bv_out)
find all sparse vector elements EQ to 0
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)
value_type BM_VECT_ALIGN buffer_ [BSIZE] BM_VECT_ALIGN_ATTR
bvector_type::allocator_type::allocator_pool_type allocator_pool_type
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:34
unsigned short bitscan(V w, B *bits)
Definition: bmfunc.h:529
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 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:48
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.
input set is sorted and belongs to one address block
Definition: bmconst.h:148
bool have_stats_
flag of statistics presense
Integer set to set transformation (functional image in groups theory) https://en.wikipedia.org/wiki/Image_(mathematics)