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 bm::sparse_vector
22 */
23 
24 #ifndef BM__H__INCLUDED__
25 // BitMagic utility headers do not include main "bm.h" declaration
26 // #include "bm.h" or "bm64.h" explicitly
27 # error missing include (bm.h or bm64.h)
28 #endif
29 
30 #include "bmdef.h"
31 #include "bmsparsevec.h"
32 #include "bmaggregator.h"
33 #include "bmbuffer.h"
34 #include "bmalgo.h"
35 #include "bmdef.h"
36 
37 #ifdef _MSC_VER
38 # pragma warning( disable: 4146 )
39 #endif
40 
41 
42 
43 /** \defgroup svalgo Sparse vector algorithms
44  Sparse vector algorithms
45  \ingroup svector
46  */
47 
48 
49 namespace bm
50 {
51 
52 
53 /*!
54  \brief Clip dynamic range for signal higher than specified
55 
56  \param svect - sparse vector to do clipping
57  \param high_bit - max bit (inclusive) allowed for this signal vector
58 
59 
60  \ingroup svalgo
61  \sa dynamic_range_clip_low
62 */
63 template<typename SV>
64 void dynamic_range_clip_high(SV& svect, unsigned high_bit)
65 {
66  unsigned sv_plains = svect.plains();
67 
68  BM_ASSERT(sv_plains > high_bit && high_bit > 0);
69 
70  typename SV::bvector_type bv_acc;
71  unsigned i;
72 
73  // combine all the high bits into accumulator vector
74  for (i = high_bit+1; i < sv_plains; ++i)
75  {
76  typename SV::bvector_type* bv_plain = svect.plain(i);
77  if (bv_plain)
78  {
79  bv_acc.bit_or(*bv_plain);
80  svect.free_plain(i);
81  }
82  } // for i
83 
84  // set all bits ON for all low vectors, which happen to be clipped
85  for (i = high_bit; true; --i)
86  {
87  typename SV::bvector_type* bv_plain = svect.get_plain(i);
88  bv_plain->bit_or(bv_acc);
89  if (i == 0)
90  break;
91  } // for i
92 }
93 
94 
95 /*!
96  \brief Clip dynamic range for signal lower than specified (boost)
97 
98  \param svect - sparse vector to do clipping
99  \param low_bit - low bit (inclusive) allowed for this signal vector
100 
101  \ingroup svalgo
102  \sa dynamic_range_clip_high
103 */
104 template<typename SV>
105 void dynamic_range_clip_low(SV& svect, unsigned low_bit)
106 {
107  if (low_bit == 0) return; // nothing to do
108  BM_ASSERT(svect.plains() > low_bit);
109 
110  unsigned sv_plains = svect.plains();
111  typename SV::bvector_type bv_acc1;
112  unsigned i;
113 
114  // combine all the high bits into accumulator vector
115  for (i = low_bit+1; i < sv_plains; ++i)
116  {
117  typename SV::bvector_type* bv_plain = svect.plain(i);
118  if (bv_plain)
119  bv_acc1.bit_or(*bv_plain);
120  } // for i
121 
122  // accumulate all vectors below the clipping point
123  typename SV::bvector_type bv_acc2;
124  typename SV::bvector_type* bv_low_plain = svect.get_plain(low_bit);
125 
126  for (i = low_bit-1; true; --i)
127  {
128  typename SV::bvector_type* bv_plain = svect.plain(i);
129  if (bv_plain)
130  {
131  bv_acc2.bit_or(*bv_plain);
132  svect.free_plain(i);
133  if (i == 0)
134  break;
135  }
136  } // for i
137 
138  // now we want to set 1 in the clipping low plain based on
139  // exclusive or (XOR) between upper and lower parts)
140  // as a result high signal (any bits in the upper plains) gets
141  // slightly lower value (due to clipping) low signal gets amplified
142  // (lower contrast algorithm)
143 
144  bv_acc1.bit_xor(bv_acc2);
145  bv_low_plain->bit_or(bv_acc1);
146 }
147 
148 /**
149  Find first mismatch (element which is different) between two sparse vectors
150  (uses linear scan in bit-vector plains)
151 
152  Function works with both NULL and NOT NULL vectors
153  NULL means unassigned (uncertainty), so first mismatch NULL is a mismatch
154  even if values in vectors can be formally the same (i.e. 0)
155 
156  @param sv1 - vector 1
157  @param sv2 - vector 2
158  @param midx - mismatch index
159  @param null_proc - defines if we want to include (not) NULL
160  vector into comparison (bm::use_null) or not.
161  By default search takes NULL vector into account
162 
163  @return true if mismatch found
164 
165  @sa sparse_vector_find_mismatch
166 
167  \ingroup svalgo
168 */
169 template<typename SV>
171  const SV& sv2,
172  typename SV::size_type& midx,
173  bm::null_support null_proc = bm::use_null)
174 {
175  typename SV::size_type mismatch = bm::id_max;
176  bool found = false;
177 
178  unsigned sv_idx = 0;
179 
180  unsigned plains1 = sv1.plains();
181  BM_ASSERT(plains1);
182 
183  // for RSC vector do NOT compare NULL plains
184 
186  {
187  //--plains1;
188  }
189  else // regular sparse vector - may have NULL plains
190  {
191  if (null_proc == bm::use_null)
192  {
193  typename SV::bvector_type_const_ptr bv_null1 = sv1.get_null_bvector();
194  typename SV::bvector_type_const_ptr bv_null2 = sv2.get_null_bvector();
195  if (bv_null1 && bv_null2) // both (not) NULL vectors present
196  {
197  bool f = bv_null1->find_first_mismatch(*bv_null2, midx, mismatch);
198  if (f && (midx < mismatch)) // better mismatch found
199  {
200  found = f; mismatch = midx;
201  }
202 
203  }
204  else // one or both NULL vectors are not present
205  {
206  if (bv_null1)
207  {
208  typename SV::bvector_type bv_tmp; // TODO: get rid of temp bv
209  bv_tmp.resize(sv2.size());
210  bv_tmp.invert(); // turn into true NULL vector
211 
212  // find first NULL value (mismatch)
213  bool f = bv_null1->find_first_mismatch(bv_tmp, midx, mismatch);
214  if (f && (midx < mismatch)) // better mismatch found
215  {
216  found = f; mismatch = midx;
217  }
218  }
219  if (bv_null2)
220  {
221  typename SV::bvector_type bv_tmp; // TODO: get rid of temp bv
222  bv_tmp.resize(sv1.size());
223  bv_tmp.invert();
224 
225  bool f = bv_null2->find_first_mismatch(bv_tmp, midx, mismatch);
226  if (f && (midx < mismatch)) // better mismatch found
227  {
228  found = f; mismatch = midx;
229  }
230  }
231  }
232  } // null_proc
233  }
234 
235  for (unsigned i = 0; mismatch && (i < plains1); ++i)
236  {
237  typename SV::bvector_type_const_ptr bv1 = sv1.get_plain(i);
238  typename SV::bvector_type_const_ptr bv2 = sv2.get_plain(i);
239  if (!bv1)
240  {
241  if (!bv2)
242  continue;
243  bool f = bv2->find(midx);
244  if (f && (midx < mismatch))
245  {
246  found = f; sv_idx = 2; mismatch = midx;
247  }
248  continue;
249  }
250  if (!bv2)
251  {
252  BM_ASSERT(bv1);
253  bool f = bv1->find(midx);
254  if (f && (midx < mismatch))
255  {
256  found = f; sv_idx = 1; mismatch = midx;
257  }
258  continue;
259  }
260  // both plains are not NULL
261  //
262  bool f = bv1->find_first_mismatch(*bv2, midx, mismatch);
263  if (f && (midx < mismatch)) // better mismatch found
264  {
265  found = f; mismatch = midx;
266  // which vector has '1' at mismatch position?
268  sv_idx = (bv1->test(mismatch)) ? 1 : 2;
269  }
270 
271  } // for i
272 
273  // RSC address translation here
274  //
276  {
277  if (found) // RSC address translation
278  {
279  BM_ASSERT(sv1.is_compressed());
280  BM_ASSERT(sv2.is_compressed());
281 
282  switch (sv_idx)
283  {
284  case 1:
285  found = sv1.find_rank(midx + 1, mismatch);
286  break;
287  case 2:
288  found = sv2.find_rank(midx + 1, mismatch);
289  break;
290  default: // unknown, try both
291  BM_ASSERT(0);
292  }
293  BM_ASSERT(found);
294  }
295  else // search for mismatch in the NOT NULL vectors
296  {
297  if (null_proc == bm::use_null)
298  {
299  // no need for address translation in this case
300  typename SV::bvector_type_const_ptr bv_null1 = sv1.get_null_bvector();
301  typename SV::bvector_type_const_ptr bv_null2 = sv2.get_null_bvector();
302  found = bv_null1->find_first_mismatch(*bv_null2, mismatch);
303  }
304  }
305  }
306 
307  midx = mismatch; // minimal mismatch
308  return found;
309 }
310 
311 /**
312  Find mismatch vector, indicating positions of mismatch between two sparse vectors
313  (uses linear scan in bit-vector plains)
314 
315  Function works with both NULL and NOT NULL vectors
316 
317  @param bv - [out] - bit-ector with mismatch positions indicated as 1s
318  @param sv1 - vector 1
319  @param sv2 - vector 2
320  @param null_proc - rules of processing for (not) NULL plain
321  bm::no_null - NULLs from both vectors are treated as uncertainty
322  and NOT included into final result
323  bm::use_null - difference in NULLs accounted into the result
324 
325  @sa sparse_vector_find_first_mismatch
326 
327  \ingroup svalgo
328 */
329 template<typename SV1, typename SV2>
331  const SV1& sv1,
332  const SV2& sv2,
333  bm::null_support null_proc)
334 {
335  typedef typename SV1::bvector_type bvector_type;
336  typedef typename bvector_type::allocator_type allocator_type;
337  typedef typename allocator_type::allocator_pool_type allocator_pool_type;
338 
339  allocator_pool_type pool; // local pool for blocks
340  typename bvector_type::mem_pool_guard mp_guard_bv;
341  mp_guard_bv.assign_if_not_set(pool, bv);
342 
343 
345  {
346  BM_ASSERT(0); // TODO: fixme
347  }
349  {
350  BM_ASSERT(0); // TODO: fixme
351  }
352 
353  bv.clear();
354 
355  unsigned plains = sv1.plains();
356  if (plains < sv2.plains())
357  plains = sv2.plains();
358 
359  for (unsigned i = 0; i < plains; ++i)
360  {
361  typename SV1::bvector_type_const_ptr bv1 = sv1.get_plain(i);
362  typename SV2::bvector_type_const_ptr bv2 = sv2.get_plain(i);
363 
364  if (!bv1)
365  {
366  if (!bv2)
367  continue;
368  bv |= *bv2;
369  continue;
370  }
371  if (!bv2)
372  {
373  BM_ASSERT(bv1);
374  bv |= *bv1;
375  continue;
376  }
377 
378  // both plains are not NULL, compute XOR diff
379  //
380  bvector_type bv_xor;
381  typename bvector_type::mem_pool_guard mp_guard;
382  mp_guard.assign_if_not_set(pool, bv_xor);
383 
384  bv_xor.bit_xor(*bv1, *bv2, SV1::bvector_type::opt_none);
385  bv |= bv_xor;
386 
387  } // for i
388 
389  // size mismatch check
390  {
391  typename SV1::size_type sz1 = sv1.size();
392  typename SV2::size_type sz2 = sv2.size();
393  if (sz1 != sz2)
394  {
395  if (sz1 < sz2)
396  {
397  }
398  else
399  {
400  bm::xor_swap(sz1, sz2);
401  }
402  bv.set_range(sz1, sz2-1);
403  }
404  }
405 
406  // NULL processings
407  //
408  typename SV1::bvector_type_const_ptr bv_null1 = sv1.get_null_bvector();
409  typename SV2::bvector_type_const_ptr bv_null2 = sv2.get_null_bvector();
410 
411  switch (null_proc)
412  {
413  case bm::no_null:
414  // NULL correction to exclude all NULL (unknown) values from the result set
415  // (AND with NOT NULL vector)
416  if (bv_null1 && bv_null2)
417  {
418  bvector_type bv_or;
419  typename bvector_type::mem_pool_guard mp_guard;
420  mp_guard.assign_if_not_set(pool, bv_or);
421 
422  bv_or.bit_or(*bv_null1, *bv_null2, bvector_type::opt_none);
423  bv &= bv_or;
424  }
425  else
426  {
427  if (bv_null1)
428  bv &= *bv_null1;
429  if (bv_null2)
430  bv &= *bv_null2;
431  }
432  break;
433  case bm::use_null:
434  if (bv_null1 && bv_null2)
435  {
436  bvector_type bv_xor;
437  typename bvector_type::mem_pool_guard mp_guard;
438  mp_guard.assign_if_not_set(pool, bv_xor);
439 
440  bv_xor.bit_xor(*bv_null1, *bv_null2, bvector_type::opt_none);
441  bv |= bv_xor;
442  }
443  else
444  {
445  bvector_type bv_null;
446  typename bvector_type::mem_pool_guard mp_guard;
447  mp_guard.assign_if_not_set(pool, bv_null);
448  if (bv_null1)
449  {
450  bv_null = *bv_null1;
451  bv_null.resize(sv1.size());
452  }
453  if (bv_null2)
454  {
455  bv_null = *bv_null2;
456  bv_null.resize(sv2.size());
457  }
458  bv_null.invert();
459  bv |= bv_null;
460  }
461  break;
462  default:
463  BM_ASSERT(0);
464  }
465 }
466 
467 
468 /**
469  \brief algorithms for sparse_vector scan/search
470 
471  Scanner uses properties of bit-vector plains to answer questions
472  like "find all sparse vector elements equivalent to XYZ".
473 
474  Class uses fast algorithms based on properties of bit-plains.
475  This is NOT a brute force, direct scan.
476 
477  @ingroup svalgo
478  @ingroup setalgo
479 */
480 template<typename SV>
482 {
483 public:
484  typedef typename SV::bvector_type bvector_type;
485  typedef const bvector_type* bvector_type_const_ptr;
486  typedef bvector_type* bvector_type_ptr;
487  typedef typename SV::value_type value_type;
488  typedef typename SV::size_type size_type;
489 
491  typedef typename allocator_type::allocator_pool_type allocator_pool_type;
492 
493 public:
495 
496  /**
497  \brief bind sparse vector for all searches
498 
499  \param sv - input sparse vector to bind for searches
500  \param sorted - source index is sorted, build index for binary search
501  */
502  void bind(const SV& sv, bool sorted);
503 
504  /**
505  \brief reset sparse vector binding
506  */
507  void reset_binding() BMNOEXCEPT;
508 
509 
510  /*! @name Find in scalar vector */
511  //@{
512 
513  /**
514  \brief find all sparse vector elements EQ to search value
515 
516  Find all sparse vector elements equivalent to specified value
517 
518  \param sv - input sparse vector
519  \param value - value to search for
520  \param bv_out - search result bit-vector (search result masks 1 elements)
521  */
522  void find_eq(const SV& sv,
523  typename SV::value_type value,
524  typename SV::bvector_type& bv_out);
525 
526  /**
527  \brief find first sparse vector element
528 
529  Find all sparse vector elements equivalent to specified value.
530  Works well if sperse vector represents unordered set
531 
532  \param sv - input sparse vector
533  \param value - value to search for
534  \param pos - output found sparse vector element index
535 
536  \return true if found
537  */
538  bool find_eq(const SV& sv,
539  typename SV::value_type value,
540  typename SV::size_type& pos);
541  /**
542  \brief lower bound search for an array position
543 
544  Method assumes the sparse array is sorted
545 
546  \param sv - input sparse vector
547  \param val - value to search for
548  \param pos - output sparse vector element index
549 
550  \return true if value found
551  */
552  bool lower_bound(const SV& sv,
553  const typename SV::value_type val,
554  typename SV::size_type& pos);
555 
556  //@}
557 
558 
559  // --------------------------------------------------
560  //
561  /*! @name Find in bit-transposed string vector */
562  //@{
563 
564 
565  /**
566  \brief find sparse vector elements (string)
567  @param sv - sparse vector of strings to search
568  @param str - string to search for
569  @param bv_out - search result bit-vector (search result masks 1 elements)
570  */
571  bool find_eq_str(const SV& sv,
572  const typename SV::value_type* str,
573  typename SV::bvector_type& bv_out);
574 
575  /**
576  \brief find sparse vector elementa (string) in the attached SV
577  @param str - string to search for
578  @param bv_out - search result bit-vector (search result masks 1 elements)
579  */
580  bool find_eq_str(const typename SV::value_type* str,
581  typename SV::bvector_type& bv_out);
582 
583  /**
584  \brief find first sparse vector element (string)
585  @param sv - sparse vector of strings to search
586  @param str - string to search for
587  @param pos - [out] index of the first found
588  */
589  bool find_eq_str(const SV& sv,
590  const typename SV::value_type* str,
591  typename SV::size_type& pos);
592 
593  /**
594  \brief binary find first sparse vector element (string)
595  Sparse vector must be attached (bind())
596  @param str - string to search for
597  @param pos - [out] index of the first found
598  @sa bind
599  */
600  bool find_eq_str(const typename SV::value_type* str,
601  typename SV::size_type& pos);
602 
603  /**
604  \brief find sparse vector elements with a given prefix (string)
605  @param sv - sparse vector of strings to search
606  @param str - string prefix to search for
607  "123" is a prefix for "1234567"
608  @param bv_out - search result bit-vector (search result masks 1 elements)
609  */
610  bool find_eq_str_prefix(const SV& sv,
611  const typename SV::value_type* str,
612  typename SV::bvector_type& bv_out);
613 
614 
615  /**
616  \brief binary find first sparse vector element (string)
617  Sparse vector must be sorted.
618  */
619  bool bfind_eq_str(const SV& sv,
620  const typename SV::value_type* str,
621  typename SV::size_type& pos);
622 
623  /**
624  \brief lower bound search for an array position
625 
626  Method assumes the sparse array is sorted
627 
628  \param sv - input sparse vector
629  \param str - value to search for
630  \param pos - output sparse vector element index
631 
632  \return true if value found
633  */
634  bool lower_bound_str(const SV& sv,
635  const typename SV::value_type* str,
636  typename SV::size_type& pos);
637 
638  /**
639  \brief binary find first sparse vector element (string)
640  Sparse vector must be sorted and attached
641  @sa bind
642  */
643  bool bfind_eq_str(const typename SV::value_type* str,
644  typename SV::size_type& pos);
645 
646  //@}
647 
648  /**
649  \brief find all sparse vector elements EQ to 0
650  \param sv - input sparse vector
651  \param bv_out - output bit-vector (search result masks 1 elements)
652  */
653  void find_zero(const SV& sv,
654  typename SV::bvector_type& bv_out);
655 
656  /*!
657  \brief Find non-zero elements
658  Output vector is computed as a logical OR (join) of all plains
659 
660  \param sv - input sparse vector
661  \param bv_out - output bit-bector of non-zero elements
662  */
663  void find_nonzero(const SV& sv, typename SV::bvector_type& bv_out);
664 
665  /**
666  \brief invert search result ("EQ" to "not EQ")
667 
668  \param sv - input sparse vector
669  \param bv_out - output bit-bector of non-zero elements
670  */
671  void invert(const SV& sv, typename SV::bvector_type& bv_out);
672 
673  /**
674  \brief find all values A IN (C, D, E, F)
675  \param sv - input sparse vector
676  \param start - start iterator (set to search)
677  \param end - end iterator (set to search)
678  \param bv_out - output bit-bector of non-zero elements
679  */
680  template<typename It>
681  void find_eq(const SV& sv,
682  It start,
683  It end,
684  typename SV::bvector_type& bv_out)
685  {
686  typename bvector_type::mem_pool_guard mp_guard;
687  mp_guard.assign_if_not_set(pool_, bv_out); // set algorithm-local memory pool to avoid heap contention
688 
689  bvector_type bv1;
690  typename bvector_type::mem_pool_guard mp_guard1(pool_, bv1);
691  bool any_zero = false;
692  for (; start < end; ++start)
693  {
694  value_type v = *start;
695  any_zero |= (v == 0);
696  bool found = find_eq_with_nulls(sv, v, bv1);
697  if (found)
698  bv_out.bit_or(bv1);
699  else
700  {
701  BM_ASSERT(!bv1.any());
702  }
703  } // for
704  if (any_zero)
705  correct_nulls(sv, bv_out);
706  }
707 
708  /// For testing purposes only
709  ///
710  /// @internal
711  void find_eq_with_nulls_horizontal(const SV& sv,
712  typename SV::value_type value,
713  typename SV::bvector_type& bv_out);
714 
715  /** Exclude possible NULL values from the result vector
716  \param sv - input sparse vector
717  \param bv_out - output bit-bector of non-zero elements
718  */
719  void correct_nulls(const SV& sv, typename SV::bvector_type& bv_out);
720 
721 protected:
722 
723  /// set search boundaries (hint for the aggregator)
724  void set_search_range(size_type from, size_type to);
725 
726  /// reset (disable) search range
727  void reset_search_range();
728 
729  /// find value (may include NULL indexes)
730  bool find_eq_with_nulls(const SV& sv,
731  typename SV::value_type value,
732  typename SV::bvector_type& bv_out,
733  typename SV::size_type search_limit = 0);
734 
735  /// find first value (may include NULL indexes)
736  bool find_first_eq(const SV& sv,
737  typename SV::value_type value,
738  size_type& idx);
739 
740  /// find first string value (may include NULL indexes)
741  bool find_first_eq(const SV& sv,
742  const typename SV::value_type* str,
743  size_type& idx,
744  bool remaped);
745 
746  /// find EQ str / prefix impl
747  bool find_eq_str_impl(const SV& sv,
748  const typename SV::value_type* str,
749  typename SV::bvector_type& bv_out,
750  bool prefix_sub);
751 
752  /// Prepare aggregator for AND-SUB (EQ) search
753  bool prepare_and_sub_aggregator(const SV& sv,
754  typename SV::value_type value);
755 
756  /// Prepare aggregator for AND-SUB (EQ) search (string)
757  bool prepare_and_sub_aggregator(const SV& sv,
758  const typename SV::value_type* str,
759  unsigned octet_start,
760  bool prefix_sub);
761 
762  /// Rank-Select decompression for RSC vectors
763  void decompress(const SV& sv, typename SV::bvector_type& bv_out);
764 
765  /// compare sv[idx] with input str
766  int compare_str(const SV& sv, size_type idx, const value_type* str);
767 
768  /// compare sv[idx] with input value
769  int compare(const SV& sv, size_type idx, const value_type val) BMNOEXCEPT;
770 
771 protected:
773  void operator=(const sparse_vector_scanner&) = delete;
774 
775 protected:
776 
778  {
779  max_columns = SV::max_vector_size
780  };
781 
783  {
786  };
787 
788  typedef bm::dynamic_heap_matrix<value_type, allocator_type> heap_matrix_type;
789  typedef bm::heap_matrix<typename SV::value_type,
791  SV::sv_octet_plains,
792  allocator_type> matrix_search_buf_type;
793 
794 
795 private:
796  allocator_pool_type pool_;
797  bvector_type bv_tmp_;
800 
801  size_type mask_from_;
802  size_type mask_to_;
803  bool mask_set_;
804 
805  const SV* bound_sv_;
806  heap_matrix_type block0_elements_cache_; ///< cache for elements[0] of each block
807  heap_matrix_type block3_elements_cache_; ///< cache for elements[16384x] of each block
808  size_type effective_str_max_;
809 
810  value_type remap_value_vect_[SV::max_vector_size];
811  /// masks of allocated bit-plains (1 - means there is a bit-plain)
812  bm::id64_t vector_plain_masks_[SV::max_vector_size];
813  matrix_search_buf_type hmatr_; ///< heap matrix for string search linear stage
814 };
815 
816 
817 /*!
818  \brief Integer set to set transformation (functional image in groups theory)
819  https://en.wikipedia.org/wiki/Image_(mathematics)
820 
821  Input sets gets translated through the function, which is defined as
822  "one to one (or NULL)" binary relation object (sparse_vector).
823  Also works for M:1 relationships.
824 
825  \ingroup svalgo
826  \ingroup setalgo
827 */
828 template<typename SV>
830 {
831 public:
832  typedef typename SV::bvector_type bvector_type;
833  typedef typename SV::value_type value_type;
834  typedef typename SV::size_type size_type;
836 public:
837 
840 
841 
842  /** Get read access to zero-elements vector
843  Zero vector gets populated after attach_sv() is called
844  or as a side-effect of remap() with immediate sv param
845  */
846  const bvector_type& get_bv_zero() const { return bv_zero_; }
847 
848  /** Perform remapping (Image function) (based on attached translation table)
849 
850  \param bv_in - input set, defined as a bit-vector
851  \param bv_out - output set as a bit-vector
852 
853  @sa attach_sv
854  */
855  void remap(const bvector_type& bv_in,
856  bvector_type& bv_out);
857 
858  /** Perform remapping (Image function)
859 
860  \param bv_in - input set, defined as a bit-vector
861  \param sv_brel - binary relation (translation table) sparse vector
862  \param bv_out - output set as a bit-vector
863  */
864  void remap(const bvector_type& bv_in,
865  const SV& sv_brel,
866  bvector_type& bv_out);
867 
868  /** Remap single set element
869 
870  \param id_from - input value
871  \param sv_brel - translation table sparse vector
872  \param id_to - out value
873 
874  \return - true if value was found and remapped
875  */
876  bool remap(size_type id_from, const SV& sv_brel, size_type& id_to);
877 
878 
879  /** Run remap transformation
880 
881  \param bv_in - input set, defined as a bit-vector
882  \param sv_brel - translation table sparse vector
883  \param bv_out - output set as a bit-vector
884 
885  @sa remap
886  */
887  void run(const bvector_type& bv_in,
888  const SV& sv_brel,
889  bvector_type& bv_out)
890  {
891  remap(bv_in, sv_brel, bv_out);
892  }
893 
894  /** Attach a translation table vector for remapping (Image function)
895 
896  \param sv_brel - binary relation sparse vector pointer
897  (pass NULL to detach)
898  \param compute_stats - flag to perform computation of some statistics
899  later used in remapping. This only make sense
900  for series of remappings on the same translation
901  vector.
902  @sa remap
903  */
904  void attach_sv(const SV* sv_brel, bool compute_stats = false);
905 
906 
907 protected:
908  void one_pass_run(const bvector_type& bv_in,
909  const SV& sv_brel,
910  bvector_type& bv_out);
911 
912  /// @internal
913  template<unsigned BSIZE>
915  {
916  size_type BM_VECT_ALIGN gather_idx_[BSIZE] BM_VECT_ALIGN_ATTR;
917  value_type BM_VECT_ALIGN buffer_[BSIZE] BM_VECT_ALIGN_ATTR;
918  };
919 
921  {
922  sv_g_size = 1024 * 8
923  };
925 
926 
927 protected:
929  void operator=(const set2set_11_transform&) = delete;
930 
931 protected:
932  const SV* sv_ptr_; ///< current translation table vector
933  gather_buffer_type* gb_; ///< intermediate buffers
934  bvector_type bv_product_;///< temp vector
935 
936  bool have_stats_; ///< flag of statistics presense
937  bvector_type bv_zero_; ///< bit-vector for zero elements
938 
939  allocator_pool_type pool_;
940 };
941 
942 
943 
944 //----------------------------------------------------------------------------
945 //
946 //----------------------------------------------------------------------------
947 
948 template<typename SV>
950 : sv_ptr_(0), gb_(0), have_stats_(false)
951 {
952  gb_ = (gather_buffer_type*)::malloc(sizeof(gather_buffer_type));
953  if (!gb_)
954  {
955  SV::throw_bad_alloc();
956  }
957 }
958 
959 //----------------------------------------------------------------------------
960 
961 template<typename SV>
963 {
964  if (gb_)
965  ::free(gb_);
966 }
967 
968 
969 //----------------------------------------------------------------------------
970 
971 template<typename SV>
972 void set2set_11_transform<SV>::attach_sv(const SV* sv_brel, bool compute_stats)
973 {
974  sv_ptr_ = sv_brel;
975  if (!sv_ptr_)
976  {
977  have_stats_ = false;
978  }
979  else
980  {
981  if (sv_brel->empty() || !compute_stats)
982  return; // nothing to do
983  const bvector_type* bv_non_null = sv_brel->get_null_bvector();
984  if (bv_non_null)
985  return; // already have 0 elements vector
986 
987 
988  typename bvector_type::mem_pool_guard mp_g_z;
990 
992  scanner.find_zero(*sv_brel, bv_zero_);
993  have_stats_ = true;
994  }
995 }
996 
997 //----------------------------------------------------------------------------
998 
999 template<typename SV>
1001  const SV& sv_brel,
1002  size_type& id_to)
1003 {
1004  if (sv_brel.empty())
1005  return false; // nothing to do
1006 
1007  const bvector_type* bv_non_null = sv_brel.get_null_bvector();
1008  if (bv_non_null)
1009  {
1010  if (!bv_non_null->test(id_from))
1011  return false;
1012  }
1013  size_type idx = sv_brel.translate_address(id_from);
1014  id_to = sv_brel.get(idx);
1015  return true;
1016 }
1017 
1018 //----------------------------------------------------------------------------
1019 
1020 template<typename SV>
1022  const SV& sv_brel,
1023  bvector_type& bv_out)
1024 {
1025  typename bvector_type::mem_pool_guard mp_g_out, mp_g_p, mp_g_z;
1026  mp_g_out.assign_if_not_set(pool_, bv_out);
1028  mp_g_z.assign_if_not_set(pool_, bv_zero_);
1029 
1030  attach_sv(&sv_brel);
1031 
1032  remap(bv_in, bv_out);
1033 
1034  attach_sv(0); // detach translation table
1035 }
1036 
1037 template<typename SV>
1039  bvector_type& bv_out)
1040 {
1041  BM_ASSERT(sv_ptr_);
1042 
1043  bv_out.clear();
1044 
1045  if (sv_ptr_ == 0 || sv_ptr_->empty())
1046  return; // nothing to do
1047 
1048  bv_out.init(); // just in case to "fast set" later
1049 
1050  typename bvector_type::mem_pool_guard mp_g_out, mp_g_p, mp_g_z;
1051  mp_g_out.assign_if_not_set(pool_, bv_out);
1053  mp_g_z.assign_if_not_set(pool_, bv_zero_);
1054 
1055 
1056  const bvector_type* enum_bv;
1057 
1058  const bvector_type * bv_non_null = sv_ptr_->get_null_bvector();
1059  if (bv_non_null)
1060  {
1061  // TODO: optimize with 2-way ops
1062  bv_product_ = bv_in;
1063  bv_product_.bit_and(*bv_non_null);
1064  enum_bv = &bv_product_;
1065  }
1066  else // non-NULL vector is not available
1067  {
1068  enum_bv = &bv_in;
1069  // if we have any elements mapping into "0" on the other end
1070  // we map it once (chances are there are many duplicates)
1071  //
1072 
1073  if (have_stats_) // pre-attached translation statistics
1074  {
1075  bv_product_ = bv_in;
1076  size_type cnt1 = bv_product_.count();
1077  bv_product_.bit_sub(bv_zero_);
1078  size_type cnt2 = bv_product_.count();
1079 
1080  BM_ASSERT(cnt2 <= cnt1);
1081 
1082  if (cnt1 != cnt2) // mapping included 0 elements
1083  bv_out.set_bit_no_check(0);
1084 
1085  enum_bv = &bv_product_;
1086  }
1087  }
1088 
1089 
1090 
1091  size_type buf_cnt, nb_old, nb;
1092  buf_cnt = nb_old = 0;
1093 
1094  typename bvector_type::enumerator en(enum_bv->first());
1095  for (; en.valid(); ++en)
1096  {
1097  typename SV::size_type idx = *en;
1098  idx = sv_ptr_->translate_address(idx);
1099 
1100  nb = unsigned(idx >> bm::set_block_shift);
1101  if (nb != nb_old) // new blocks
1102  {
1103  if (buf_cnt)
1104  {
1105  sv_ptr_->gather(&gb_->buffer_[0], &gb_->gather_idx_[0], buf_cnt, BM_SORTED_UNIFORM);
1106  bv_out.set(&gb_->buffer_[0], buf_cnt, BM_SORTED);
1107  buf_cnt = 0;
1108  }
1109  nb_old = nb;
1110  gb_->gather_idx_[buf_cnt++] = idx;
1111  }
1112  else
1113  {
1114  gb_->gather_idx_[buf_cnt++] = idx;
1115  }
1116 
1117  if (buf_cnt == sv_g_size)
1118  {
1119  sv_ptr_->gather(&gb_->buffer_[0], &gb_->gather_idx_[0], buf_cnt, BM_SORTED_UNIFORM);
1120  bv_out.set(&gb_->buffer_[0], buf_cnt, bm::BM_SORTED);
1121  buf_cnt = 0;
1122  }
1123  } // for en
1124  if (buf_cnt)
1125  {
1126  sv_ptr_->gather(&gb_->buffer_[0], &gb_->gather_idx_[0], buf_cnt, BM_SORTED_UNIFORM);
1127  bv_out.set(&gb_->buffer_[0], buf_cnt, bm::BM_SORTED);
1128  }
1129 }
1130 
1131 
1132 //----------------------------------------------------------------------------
1133 
1134 template<typename SV>
1136  const SV& sv_brel,
1137  bvector_type& bv_out)
1138 {
1139  if (sv_brel.empty())
1140  return; // nothing to do
1141 
1142  bv_out.init();
1143 
1144  typename SV::const_iterator it = sv_brel.begin();
1145  for (; it.valid(); ++it)
1146  {
1147  typename SV::value_type t_id = *it;
1148  size_type idx = it.pos();
1149  if (bv_in.test(idx))
1150  {
1151  bv_out.set_bit_no_check(t_id);
1152  }
1153  } // for
1154 }
1155 
1156 
1157 //----------------------------------------------------------------------------
1158 //
1159 //----------------------------------------------------------------------------
1160 
1161 template<typename SV>
1163 {
1164  mask_set_ = false;
1165  mask_from_ = mask_to_ = bm::id_max;
1166 
1167  bound_sv_ = 0;
1168  effective_str_max_ = 0;
1169 }
1170 
1171 //----------------------------------------------------------------------------
1172 
1173 template<typename SV>
1174 void sparse_vector_scanner<SV>::bind(const SV& sv, bool sorted)
1175 {
1176  bound_sv_ = &sv;
1177  if (sorted)
1178  {
1179  size_type sv_sz = sv.size();
1180  BM_ASSERT(sv_sz);
1181  size_type total_nb = sv_sz / bm::gap_max_bits + 1;
1182  effective_str_max_ = sv.effective_vector_max();
1183 
1184  block0_elements_cache_.resize(total_nb, effective_str_max_+1);
1185  block0_elements_cache_.set_zero();
1186 
1187  block3_elements_cache_.resize(total_nb * 3, effective_str_max_+1);
1188  block3_elements_cache_.set_zero();
1189 
1190  // fill in elements cache
1191  for (size_type i = 0; i < sv_sz; i+= bm::gap_max_bits)
1192  {
1193  size_type nb = (i >> bm::set_block_shift);
1194  value_type* s0 = block0_elements_cache_.row(nb);
1195  sv.get(i, s0, size_type(block0_elements_cache_.cols()));
1196 
1197  for (size_type k = 0; k < 3; ++k)
1198  {
1199  value_type* s1 = block3_elements_cache_.row(nb * 3 + k);
1200  size_type idx = i + (k+1) * bm::sub_block3_size;
1201  sv.get(idx, s1, size_type(block3_elements_cache_.cols()));
1202  } // for k
1203  } // for i
1204  }
1205  // pre-calculate vector plain masks
1206  //
1207  for (unsigned i = 0; i < SV::max_vector_size; ++i)
1208  {
1209  vector_plain_masks_[i] = sv.get_plains_mask(i);
1210  } // for i
1211 
1212 }
1213 
1214 //----------------------------------------------------------------------------
1215 
1216 template<typename SV>
1218 {
1219  bound_sv_ = 0;
1220  effective_str_max_ = 0;
1221 }
1222 
1223 //----------------------------------------------------------------------------
1224 
1225 template<typename SV>
1227  typename SV::bvector_type& bv_out)
1228 {
1229  if (sv.size() == 0)
1230  {
1231  bv_out.clear();
1232  return;
1233  }
1234  find_nonzero(sv, bv_out);
1235  if (sv.is_compressed())
1236  {
1237  bv_out.invert();
1238  bv_out.set_range(sv.effective_size(), bm::id_max - 1, false);
1239  decompress(sv, bv_out);
1240  }
1241  else
1242  {
1243  invert(sv, bv_out);
1244  }
1245  correct_nulls(sv, bv_out);
1246 }
1247 
1248 //----------------------------------------------------------------------------
1249 
1250 template<typename SV>
1251 void sparse_vector_scanner<SV>::invert(const SV& sv, typename SV::bvector_type& bv_out)
1252 {
1253  if (sv.size() == 0)
1254  {
1255  bv_out.clear();
1256  return;
1257  }
1258  // TODO: find a better algorithm (NAND?)
1259  bv_out.invert();
1260  const bvector_type* bv_null = sv.get_null_bvector();
1261  if (bv_null) // correct result to only use not NULL elements
1262  bv_out &= *bv_null;
1263  else
1264  {
1265  // TODO: use the shorter range to clear the tail
1266  bv_out.set_range(sv.size(), bm::id_max - 1, false);
1267  }
1268 }
1269 
1270 //----------------------------------------------------------------------------
1271 
1272 template<typename SV>
1274  typename SV::bvector_type& bv_out)
1275 {
1276  const bvector_type* bv_null = sv.get_null_bvector();
1277  if (bv_null) // correct result to only use not NULL elements
1278  bv_out.bit_and(*bv_null);
1279 }
1280 
1281 //----------------------------------------------------------------------------
1282 
1283 template<typename SV>
1285  typename SV::value_type value,
1286  typename SV::bvector_type& bv_out,
1287  typename SV::size_type search_limit)
1288 {
1289  if (sv.empty())
1290  return false; // nothing to do
1291 
1292  if (!value)
1293  {
1294  find_zero(sv, bv_out);
1295  return bv_out.any();
1296  }
1297  agg_.reset();
1298 
1299  bool found = prepare_and_sub_aggregator(sv, value);
1300  if (!found)
1301  {
1302  bv_out.clear();
1303  return found;
1304  }
1305 
1306  bool any = (search_limit == 1);
1307  found = agg_.combine_and_sub(bv_out, any);
1308  agg_.reset();
1309  return found;
1310 }
1311 
1312 //----------------------------------------------------------------------------
1313 
1314 template<typename SV>
1316  typename SV::value_type value,
1317  size_type& idx)
1318 {
1319  if (sv.empty())
1320  return false; // nothing to do
1321 
1322  BM_ASSERT(value); // cannot handle zero values
1323  if (!value)
1324  return false;
1325 
1326  agg_.reset();
1327  bool found = prepare_and_sub_aggregator(sv, value);
1328  if (!found)
1329  return found;
1330  found = agg_.find_first_and_sub(idx);
1331  agg_.reset();
1332  return found;
1333 }
1334 
1335 
1336 //----------------------------------------------------------------------------
1337 
1338 template<typename SV>
1340  const typename SV::value_type* str,
1341  size_type& idx,
1342  bool remaped)
1343 {
1344  if (sv.empty())
1345  return false; // nothing to do
1346  BM_ASSERT(*str);
1347 
1348  if (!*str)
1349  return false;
1350 
1351  agg_.reset();
1352  unsigned common_prefix_len = 0;
1353 
1354  if (mask_set_)
1355  {
1356  agg_.set_range_hint(mask_from_, mask_to_);
1357  common_prefix_len = sv.common_prefix_length(mask_from_, mask_to_);
1358  }
1359 
1360  if (remaped)
1361  {
1362  str = remap_value_vect_;
1363  }
1364  else
1365  {
1366  if (sv.is_remap() && str != remap_value_vect_)
1367  {
1368  bool r = sv.remap_tosv(remap_value_vect_, SV::max_vector_size, str);
1369  if (!r)
1370  return r;
1371  str = remap_value_vect_;
1372  }
1373  }
1374 
1375  bool found = prepare_and_sub_aggregator(sv, str, common_prefix_len, true);
1376  if (!found)
1377  return found;
1378 
1379  found = agg_.find_first_and_sub(idx);
1380  agg_.reset();
1381  return found;
1382 }
1383 
1384 //----------------------------------------------------------------------------
1385 
1386 template<typename SV>
1388  const typename SV::value_type* str,
1389  unsigned octet_start,
1390  bool prefix_sub)
1391 {
1392  unsigned char bits[64];
1393 
1394  int len = 0;
1395  for (; str[len] != 0; ++len)
1396  {}
1397  BM_ASSERT(len);
1398 
1399  // use reverse order (faster for sorted arrays)
1400  for (int octet_idx = len-1; octet_idx >= 0; --octet_idx)
1401  {
1402  if (unsigned(octet_idx) < octet_start) // common prefix
1403  break;
1404 
1405  unsigned value = unsigned(str[octet_idx]) & 0xFF;
1406  BM_ASSERT(value != 0);
1407 
1408  bm::id64_t plains_mask;
1409  if (&sv == bound_sv_)
1410  plains_mask = vector_plain_masks_[octet_idx];
1411  else
1412  plains_mask = sv.get_plains_mask(unsigned(octet_idx));
1413 
1414  if ((value & plains_mask) != value) // pre-screen for impossible values
1415  return false; // found non-existing plain
1416 
1417  // prep the lists for combined AND-SUB aggregator
1418  //
1419  unsigned short bit_count_v = bm::bitscan(value, bits);
1420  for (unsigned i = 0; i < bit_count_v; ++i)
1421  {
1422  unsigned bit_idx = bits[i];
1423  BM_ASSERT(value & (value_type(1) << bit_idx));
1424  unsigned plain_idx = (unsigned(octet_idx) * 8) + bit_idx;
1425  const bvector_type* bv = sv.get_plain(plain_idx);
1426  agg_.add(bv);
1427  } // for i
1428 
1429  unsigned vinv = unsigned(value);
1430  if (bm::conditional<sizeof(value_type) == 1>::test())
1431  {
1432  vinv ^= 0xFF;
1433  }
1434  else // 2-byte char
1435  {
1436  BM_ASSERT(sizeof(value_type) == 2);
1437  vinv ^= 0xFFFF;
1438  }
1439  // exclude the octet bits which are all not set (no vectors)
1440  vinv &= unsigned(plains_mask);
1441  for (unsigned octet_plain = (unsigned(octet_idx) * 8); vinv; vinv &= vinv-1)
1442  {
1443  bm::id_t t = vinv & -vinv;
1444  unsigned bit_idx = bm::word_bitcount(t - 1);
1445  unsigned plain_idx = octet_plain + bit_idx;
1446  const bvector_type* bv = sv.get_plain(plain_idx);
1447  BM_ASSERT(bv);
1448  agg_.add(bv, 1); // agg to SUB group
1449  } // for
1450  } // for octet_idx
1451 
1452  // add all vectors above string len to the SUB aggregation group
1453  //
1454  if (prefix_sub)
1455  {
1456  unsigned plain_idx = unsigned(len * 8);
1457  typename SV::size_type plains;
1458  if (&sv != bound_sv_)
1459  {
1460  effective_str_max_ = sv.effective_vector_max();
1461  }
1462  plains = effective_str_max_ * unsigned(sizeof(value_type)) * 8;
1463  for (; plain_idx < plains; ++plain_idx)
1464  {
1465  bvector_type_const_ptr bv = sv.get_plain(plain_idx);
1466  if (bv)
1467  agg_.add(bv, 1); // agg to SUB group
1468  } // for
1469  }
1470  return true;
1471 }
1472 
1473 //----------------------------------------------------------------------------
1474 
1475 template<typename SV>
1477  typename SV::value_type value)
1478 {
1479  unsigned char bits[sizeof(value) * 8];
1480  unsigned short bit_count_v = bm::bitscan(value, bits);
1481  BM_ASSERT(bit_count_v);
1482  const value_type mask1 = 1;
1483 
1484  // prep the lists for combined AND-SUB aggregator
1485  // (backward order has better chance for bit reduction on AND)
1486  //
1487  for (unsigned i = bit_count_v; i > 0; --i)
1488  {
1489  unsigned bit_idx = bits[i-1];
1490  BM_ASSERT(value & (mask1 << bit_idx));
1491  const bvector_type* bv = sv.get_plain(bit_idx);
1492  if (bv)
1493  agg_.add(bv);
1494  else
1495  return false;
1496  }
1497 
1498  unsigned sv_plains = sv.effective_plains();
1499  for (unsigned i = 0; i < sv_plains; ++i)
1500  {
1501  bvector_type_const_ptr bv = sv.get_plain(i);
1502  value_type mask = mask1 << i;
1503  if (bv && !(value & mask))
1504  agg_.add(bv, 1); // agg to SUB group
1505  } // for i
1506  return true;
1507 }
1508 
1509 
1510 //----------------------------------------------------------------------------
1511 
1512 template<typename SV>
1514  typename SV::value_type value,
1515  typename SV::bvector_type& bv_out)
1516 {
1517  if (sv.empty())
1518  return; // nothing to do
1519 
1520  if (!value)
1521  {
1522  find_zero(sv, bv_out);
1523  return;
1524  }
1525 
1526  unsigned char bits[sizeof(value) * 8];
1527  unsigned short bit_count_v = bm::bitscan(value, bits);
1528  BM_ASSERT(bit_count_v);
1529 
1530  // aggregate AND all matching vectors
1531  {
1532  const bvector_type* bv_plain = sv.get_plain(bits[--bit_count_v]);
1533  if (bv_plain)
1534  bv_out = *bv_plain;
1535  else // plain not found
1536  {
1537  bv_out.clear();
1538  return;
1539  }
1540  }
1541  for (unsigned i = 0; i < bit_count_v; ++i)
1542  {
1543  const bvector_type* bv_plain = sv.get_plain(bits[i]);
1544  if (bv_plain)
1545  bv_out &= *bv_plain;
1546  else // mandatory plain not found - empty result!
1547  {
1548  bv_out.clear();
1549  return;
1550  }
1551  } // for i
1552 
1553  // SUB all other plains
1554  unsigned sv_plains = sv.effective_plains();
1555  for (unsigned i = 0; (i < sv_plains) && value; ++i)
1556  {
1557  const bvector_type* bv_plain = sv.get_plain(i);
1558  if (bv_plain && !(value & (value_type(1) << i)))
1559  bv_out -= *bv_plain;
1560  }
1561 }
1562 
1563 //----------------------------------------------------------------------------
1564 
1565 template<typename SV>
1567  const typename SV::value_type* str,
1568  typename SV::bvector_type& bv_out)
1569 {
1570  return find_eq_str_impl(sv, str, bv_out, false);
1571 }
1572 
1573 
1574 //----------------------------------------------------------------------------
1575 
1576 template<typename SV>
1577 bool sparse_vector_scanner<SV>::find_eq_str(const typename SV::value_type* str,
1578  typename SV::size_type& pos)
1579 {
1580  BM_ASSERT(bound_sv_);
1581  return this->find_eq_str(*bound_sv_, str, pos);
1582 }
1583 
1584 //----------------------------------------------------------------------------
1585 
1586 template<typename SV>
1588  const typename SV::value_type* str,
1589  typename SV::size_type& pos)
1590 {
1591  bool found = false;
1592  if (sv.empty())
1593  return found;
1594  if (*str)
1595  {
1596  bool remaped = false;
1597  if (bm::conditional<SV::is_remap_support::value>::test()) // test remapping trait
1598  {
1599  if (sv.is_remap() && str != remap_value_vect_)
1600  {
1601  remaped = sv.remap_tosv(remap_value_vect_, SV::max_vector_size, str);
1602  if (!remaped)
1603  return remaped;
1604  str = remap_value_vect_;
1605  }
1606  }
1607 
1608  size_type found_pos;
1609  found = find_first_eq(sv, str, found_pos, remaped);
1610  if (found)
1611  {
1612  pos = found_pos;
1613  if (bm::conditional<SV::is_rsc_support::value>::test()) // test rank/select trait
1614  {
1615  if (sv.is_compressed()) // if compressed vector - need rank translation
1616  found = sv.find_rank(found_pos + 1, pos);
1617  }
1618  }
1619  }
1620  else // search for zero(empty str) value
1621  {
1622  // TODO: implement optimized version which would work witout temp vector
1623  typename SV::bvector_type bv_zero;
1624  find_zero(sv, bv_zero);
1625  found = bv_zero.find(pos);
1626  }
1627  return found;
1628 }
1629 
1630 //----------------------------------------------------------------------------
1631 
1632 template<typename SV>
1633 bool sparse_vector_scanner<SV>::find_eq_str(const typename SV::value_type* str,
1634  typename SV::bvector_type& bv_out)
1635 {
1636  BM_ASSERT(bound_sv_);
1637  return find_eq_str(*bound_sv_, str, bv_out);
1638 }
1639 
1640 //----------------------------------------------------------------------------
1641 
1642 template<typename SV>
1644  const typename SV::value_type* str,
1645  typename SV::bvector_type& bv_out)
1646 {
1647  return find_eq_str_impl(sv, str, bv_out, true);
1648 }
1649 
1650 //----------------------------------------------------------------------------
1651 
1652 template<typename SV>
1654  const typename SV::value_type* str,
1655  typename SV::bvector_type& bv_out,
1656  bool prefix_sub)
1657 {
1658  bool found = false;
1659  bv_out.clear(true);
1660  if (sv.empty())
1661  return false; // nothing to do
1662  if (bm::conditional<SV::is_rsc_support::value>::test()) // test rank/select trait
1663  {
1664  // search in RS compressed string vectors is not implemented
1665  BM_ASSERT(0);
1666  }
1667 
1668  if (*str)
1669  {
1670  bool remaped = false;
1671  if (bm::conditional<SV::is_remap_support::value>::test()) // test remapping trait
1672  {
1673  if (sv.is_remap() && str != remap_value_vect_)
1674  {
1675  remaped = sv.remap_tosv(remap_value_vect_, SV::max_vector_size, str);
1676  if (!remaped)
1677  return false; // not found because
1678  str = remap_value_vect_;
1679  }
1680  }
1681  /// aggregator search
1682  agg_.reset();
1683 
1684  const unsigned common_prefix_len = 0;
1685  found = prepare_and_sub_aggregator(sv, str, common_prefix_len,
1686  prefix_sub);
1687  if (!found)
1688  return found;
1689  found = agg_.combine_and_sub(bv_out);
1690 
1691  agg_.reset();
1692  }
1693  else // search for zero(empty str) value
1694  {
1695  find_zero(sv, bv_out);
1696  found = bv_out.any();
1697  }
1698  return found;
1699 
1700 }
1701 
1702 
1703 //----------------------------------------------------------------------------
1704 
1705 template<typename SV>
1707  const typename SV::value_type* str,
1708  typename SV::size_type& pos)
1709 {
1710  bool found = false;
1711  if (sv.empty())
1712  return found;
1713 
1714  if (*str)
1715  {
1716  bool remaped = false;
1717  // test search pre-condition based on remap tables
1719  {
1720  if (sv.is_remap() && str != remap_value_vect_)
1721  {
1722  remaped = sv.remap_tosv(
1723  remap_value_vect_, SV::max_vector_size, str);
1724  if (!remaped)
1725  return remaped;
1726  }
1727  }
1728 
1729  reset_search_range();
1730 
1731  // narrow down the search
1732  const unsigned min_distance_cutoff = bm::gap_max_bits + bm::gap_max_bits / 2;
1733  size_type l, r, dist;
1734  l = 0; r = sv.size()-1;
1735  size_type found_pos;
1736 
1737  // binary search to narrow down the search window
1738  while (l <= r)
1739  {
1740  dist = r - l;
1741  if (dist < min_distance_cutoff)
1742  {
1743  // we are in an narrow <2 blocks window, but still may be in two
1744  // different neighboring blocks, lets try to narrow
1745  // to exactly one block
1746 
1747  size_type nb_l = (l >> bm::set_block_shift);
1748  size_type nb_r = (r >> bm::set_block_shift);
1749  if (nb_l != nb_r)
1750  {
1751  size_type mid = nb_r * bm::gap_max_bits;
1752  if (mid < r)
1753  {
1754  int cmp = this->compare_str(sv, mid, str);
1755  if (cmp < 0) // mid < str
1756  l = mid;
1757  else
1758  r = mid-(cmp!=0); // branchless if (cmp==0) r=mid;
1759  BM_ASSERT(l < r);
1760  }
1761  nb_l = unsigned(l >> bm::set_block_shift);
1762  nb_r = unsigned(r >> bm::set_block_shift);
1763  }
1764 
1765  if (nb_l == nb_r)
1766  {
1767  size_type max_nb = sv.size() >> bm::set_block_shift;
1768  if (nb_l != max_nb)
1769  {
1770  // linear in-place fixed depth scan to identify the sub-range
1772  int cmp = this->compare_str(sv, mid, str);
1773  if (cmp < 0)
1774  {
1775  l = mid;
1776  mid = nb_r * bm::gap_max_bits + bm::sub_block3_size * 2;
1777  cmp = this->compare_str(sv, mid, str);
1778  if (cmp < 0)
1779  {
1780  l = mid;
1781  mid = nb_r * bm::gap_max_bits + bm::sub_block3_size * 3;
1782  cmp = this->compare_str(sv, mid, str);
1783  if (cmp < 0)
1784  l = mid;
1785  else
1786  r = mid;
1787  }
1788  else
1789  {
1790  r = mid;
1791  }
1792  }
1793  else
1794  {
1795  r = mid;
1796  }
1797  }
1798  }
1799 
1800  set_search_range(l, r);
1801  break;
1802  }
1803 
1804  typename SV::size_type mid = dist/2+l;
1805  size_type nb = (mid >> bm::set_block_shift);
1806  mid = nb * bm::gap_max_bits;
1807  if (mid <= l)
1808  {
1809  if (nb == 0 && r > bm::gap_max_bits)
1810  mid = bm::gap_max_bits;
1811  else
1812  mid = dist / 2 + l;
1813  }
1814  BM_ASSERT(mid > l);
1815 
1816  int cmp = this->compare_str(sv, mid, str);
1817  if (cmp == 0)
1818  {
1819  found_pos = mid;
1820  found = true;
1821  set_search_range(l, mid);
1822  break;
1823  }
1824  if (cmp < 0)
1825  l = mid+1;
1826  else
1827  r = mid-1;
1828  } // while
1829 
1830  // use linear search (range is set)
1831  found = find_first_eq(sv, str, found_pos, remaped);
1832  if (found)
1833  {
1834  pos = found_pos;
1835  if (bm::conditional<SV::is_rsc_support::value>::test()) // test rank/select trait
1836  {
1837  if (sv.is_compressed()) // if compressed vector - need rank translation
1838  found = sv.find_rank(found_pos + 1, pos);
1839  }
1840  }
1841  reset_search_range();
1842  }
1843  else // search for zero value
1844  {
1845  // TODO: implement optimized version which would work without temp vector
1846  typename SV::bvector_type bv_zero;
1847  find_zero(sv, bv_zero);
1848  found = bv_zero.find(pos);
1849  }
1850  return found;
1851 }
1852 
1853 //----------------------------------------------------------------------------
1854 
1855 template<typename SV>
1856 bool sparse_vector_scanner<SV>::bfind_eq_str(const typename SV::value_type* str,
1857  typename SV::size_type& pos)
1858 {
1859  BM_ASSERT(bound_sv_);
1860  return bfind_eq_str(*bound_sv_, str, pos);
1861 }
1862 
1863 //----------------------------------------------------------------------------
1864 
1865 template<typename SV>
1867  const typename SV::value_type val,
1868  typename SV::size_type& pos)
1869 {
1870  int cmp;
1871  size_type l = 0, r = sv.size();
1872  if (l == r) // empty vector
1873  {
1874  pos = 0;
1875  return false;
1876  }
1877  --r;
1878 
1879  // check initial boundary conditions if insert point is at tail/head
1880  cmp = this->compare(sv, l, val); // left (0) boundary check
1881  if (cmp > 0) // vect[x] > str
1882  {
1883  pos = 0;
1884  return false;
1885  }
1886  if (cmp == 0)
1887  {
1888  pos = 0;
1889  return true;
1890  }
1891  cmp = this->compare(sv, r, val); // right(size-1) boundary check
1892  if (cmp == 0)
1893  {
1894  pos = r;
1895  // back-scan to rewind all duplicates
1896  // TODO: adapt one-sided binary search to traverse large platos
1897  for (; r >= 0; --r)
1898  {
1899  cmp = this->compare(sv, r, val);
1900  if (cmp != 0)
1901  return true;
1902  pos = r;
1903  } // for i
1904  return true;
1905  }
1906  if (cmp < 0) // vect[x] < str
1907  {
1908  pos = r+1;
1909  return false;
1910  }
1911 
1912  size_type dist = r - l;
1913  if (dist < linear_cutoff1)
1914  {
1915  for (; l <= r; ++l)
1916  {
1917  cmp = this->compare(sv, l, val);
1918  if (cmp == 0)
1919  {
1920  pos = l;
1921  return true;
1922  }
1923  if (cmp > 0)
1924  {
1925  pos = l;
1926  return false;
1927  }
1928  } // for
1929  }
1930 
1931  while (l <= r)
1932  {
1933  size_type mid = (r-l)/2+l;
1934  cmp = this->compare(sv, mid, val);
1935  if (cmp == 0)
1936  {
1937  pos = mid;
1938  // back-scan to rewind all duplicates
1939  for (size_type i = mid-1; i >= 0; --i)
1940  {
1941  cmp = this->compare(sv, i, val);
1942  if (cmp != 0)
1943  return true;
1944  pos = i;
1945  } // for i
1946  pos = 0;
1947  return true;
1948  }
1949  if (cmp < 0)
1950  l = mid+1;
1951  else
1952  r = mid-1;
1953 
1954  dist = r - l;
1955  if (dist < linear_cutoff2) // do linear scan here
1956  {
1957  typename SV::const_iterator it(&sv, l);
1958  for (; it.valid(); ++it, ++l)
1959  {
1960  typename SV::value_type sv_value = it.value();
1961  if (sv_value == val)
1962  {
1963  pos = l;
1964  return true;
1965  }
1966  if (sv_value > val) // vect[x] > val
1967  {
1968  pos = l;
1969  return false;
1970  }
1971  } // for it
1972  BM_ASSERT(0);
1973  pos = l;
1974  return false;
1975  }
1976  } // while
1977 
1978  BM_ASSERT(0);
1979  return false;
1980 }
1981 
1982 
1983 //----------------------------------------------------------------------------
1984 
1985 template<typename SV>
1987  const SV& sv,
1988  const typename SV::value_type* str,
1989  typename SV::size_type& pos)
1990 {
1991  int cmp;
1992  size_type l = 0, r = sv.size();
1993 
1994  if (l == r) // empty vector
1995  {
1996  pos = 0;
1997  return false;
1998  }
1999  --r;
2000 
2001  // check initial boundary conditions if insert point is at tail/head
2002  cmp = this->compare_str(sv, l, str); // left (0) boundary check
2003  if (cmp > 0) // vect[x] > str
2004  {
2005  pos = 0;
2006  return false;
2007  }
2008  if (cmp == 0)
2009  {
2010  pos = 0;
2011  return true;
2012  }
2013  cmp = this->compare_str(sv, r, str); // right(size-1) boundary check
2014  if (cmp == 0)
2015  {
2016  pos = r;
2017  // back-scan to rewind all duplicates
2018  // TODO: adapt one-sided binary search to traverse large platos
2019  for (; r >= 0; --r)
2020  {
2021  cmp = this->compare_str(sv, r, str);
2022  if (cmp != 0)
2023  return true;
2024  pos = r;
2025  } // for i
2026  return true;
2027  }
2028  if (cmp < 0) // vect[x] < str
2029  {
2030  pos = r+1;
2031  return false;
2032  }
2033 
2034  size_type dist = r - l;
2035  if (dist < linear_cutoff1)
2036  {
2037  for (; l <= r; ++l)
2038  {
2039  cmp = this->compare_str(sv, l, str);
2040  if (cmp == 0)
2041  {
2042  pos = l;
2043  return true;
2044  }
2045  if (cmp > 0)
2046  {
2047  pos = l;
2048  return false;
2049  }
2050  } // for
2051  }
2052  while (l <= r)
2053  {
2054  size_type mid = (r-l)/2+l;
2055  cmp = this->compare_str(sv, mid, str);
2056  if (cmp == 0)
2057  {
2058  pos = mid;
2059  // back-scan to rewind all duplicates
2060  for (size_type i = mid-1; i >= 0; --i)
2061  {
2062  cmp = this->compare_str(sv, i, str);
2063  if (cmp != 0)
2064  return true;
2065  pos = i;
2066  } // for i
2067  pos = 0;
2068  return true;
2069  }
2070  if (cmp < 0)
2071  l = mid+1;
2072  else
2073  r = mid-1;
2074 
2075  dist = r - l;
2076  if (dist < linear_cutoff2) // do linear scan here
2077  {
2078  hmatr_.init();
2079 
2080  dist = sv.decode(hmatr_, l, dist+1);
2081  for (unsigned i = 0; i < dist; ++i, ++l)
2082  {
2083  const typename SV::value_type* hm_str = hmatr_.row(i);
2084  cmp = ::strcmp(hm_str, str);
2085  if (cmp == 0)
2086  {
2087  pos = l;
2088  return true;
2089  }
2090  if (cmp > 0) // vect[x] > str
2091  {
2092  pos = l;
2093  return false;
2094  }
2095  }
2096  cmp = this->compare_str(sv, l, str);
2097  if (cmp > 0) // vect[x] > str
2098  {
2099  pos = l;
2100  return false;
2101  }
2102  BM_ASSERT(0);
2103  pos = l;
2104  return false;
2105  }
2106  } // while
2107 
2108  BM_ASSERT(0);
2109  return false;
2110 }
2111 
2112 
2113 //----------------------------------------------------------------------------
2114 
2115 template<typename SV>
2117  size_type idx,
2118  const value_type* str)
2119 {
2120  if (bound_sv_ == &sv)
2121  {
2122  size_type nb = (idx >> bm::set_block_shift);
2123  size_type nbit = (idx & bm::set_block_mask);
2124  if (nbit == 0) // access to sentinel, first block element
2125  {
2126  value_type* s0 = block0_elements_cache_.row(nb);
2127  if (*s0 == 0) // uninitialized element
2128  {
2129  sv.get(idx, s0, size_type(block0_elements_cache_.cols()));
2130  }
2131  int res = 0;
2132  for (unsigned i = 0; i < block0_elements_cache_.cols(); ++i)
2133  {
2134  char octet = str[i]; char value = s0[i];
2135  res = (value > octet) - (value < octet);
2136  if (res || !octet)
2137  break;
2138  } // for i
2139 
2140  //BM_ASSERT(res == sv.compare(idx, str));
2141  return res;
2142  }
2143  else
2144  {
2145  if (nbit % bm::sub_block3_size == 0) // TODO: use AND mask here
2146  {
2147  size_type k = nbit / bm::sub_block3_size - 1;
2148  value_type* s1 = block3_elements_cache_.row(nb * 3 + k);
2149  int res = 0;
2150  for (unsigned i = 0; i < block3_elements_cache_.cols(); ++i)
2151  {
2152  char octet = str[i]; char value = s1[i];
2153  res = (value > octet) - (value < octet);
2154  if (res || !octet)
2155  break;
2156  } // for i
2157  //BM_ASSERT(res == sv.compare(idx, str));
2158  return res;
2159  }
2160  }
2161  }
2162  return sv.compare(idx, str);
2163 }
2164 
2165 //----------------------------------------------------------------------------
2166 
2167 template<typename SV>
2169  size_type idx,
2170  const value_type val) BMNOEXCEPT
2171 {
2172  // TODO: implement sentinel elements cache (similar to compare_str())
2173  return sv.compare(idx, val);
2174 }
2175 
2176 //----------------------------------------------------------------------------
2177 
2178 template<typename SV>
2180  typename SV::value_type value,
2181  typename SV::bvector_type& bv_out)
2182 {
2183  if (sv.empty())
2184  {
2185  bv_out.clear();
2186  return; // nothing to do
2187  }
2188  if (!value)
2189  {
2190  find_zero(sv, bv_out);
2191  return;
2192  }
2193 
2194  find_eq_with_nulls(sv, value, bv_out, 0);
2195 
2196  decompress(sv, bv_out);
2197  correct_nulls(sv, bv_out);
2198 }
2199 
2200 //----------------------------------------------------------------------------
2201 
2202 template<typename SV>
2204  typename SV::value_type value,
2205  typename SV::size_type& pos)
2206 {
2207  if (!value) // zero value - special case
2208  {
2209  bvector_type bv_zero;
2210  find_eq(sv, value, bv_zero);
2211  bool found = bv_zero.find(pos);
2212  return found;
2213  }
2214 
2215  size_type found_pos;
2216  bool found = find_first_eq(sv, value, found_pos);
2217  if (found)
2218  {
2219  pos = found_pos;
2220  if (bm::conditional<SV::is_rsc_support::value>::test()) // test rank/select trait
2221  {
2222  if (sv.is_compressed()) // if compressed vector - need rank translation
2223  found = sv.find_rank(found_pos + 1, pos);
2224  }
2225  }
2226  return found;
2227 }
2228 
2229 //----------------------------------------------------------------------------
2230 
2231 template<typename SV>
2233  typename SV::bvector_type& bv_out)
2234 {
2235  agg_.reset(); // in case if previous scan was interrupted
2236  for (unsigned i = 0; i < sv.plains(); ++i)
2237  agg_.add(sv.get_plain(i));
2238  agg_.combine_or(bv_out);
2239  agg_.reset();
2240 }
2241 
2242 //----------------------------------------------------------------------------
2243 
2244 template<typename SV>
2246  typename SV::bvector_type& bv_out)
2247 {
2248  if (!sv.is_compressed())
2249  return; // nothing to do
2250  const bvector_type* bv_non_null = sv.get_null_bvector();
2251  BM_ASSERT(bv_non_null);
2252 
2253  // TODO: implement faster decompressor for small result-sets
2254  rank_compr_.decompress(bv_tmp_, *bv_non_null, bv_out);
2255  bv_out.swap(bv_tmp_);
2256 }
2257 
2258 //----------------------------------------------------------------------------
2259 
2260 template<typename SV>
2262 {
2263  BM_ASSERT(from < to);
2264  mask_from_ = from;
2265  mask_to_ = to;
2266  mask_set_ = true;
2267 }
2268 
2269 //----------------------------------------------------------------------------
2270 
2271 template<typename SV>
2273 {
2274  mask_set_ = false;
2275  mask_from_ = mask_to_ = bm::id_max;
2276 }
2277 
2278 
2279 //----------------------------------------------------------------------------
2280 //
2281 //----------------------------------------------------------------------------
2282 
2283 
2284 } // namespace bm
2285 
2286 
2287 #endif
bm::heap_matrix< typename SV::value_type, linear_cutoff2, SV::sv_octet_plains, allocator_type > matrix_search_buf_type
void xor_swap(W &x, W &y) BMNOEXCEPT
XOR swap two scalar variables.
Definition: bmfunc.h:1290
SV::bvector_type bvector_type
const SV * sv_ptr_
current translation table vector
allocator_pool_type pool_
void sparse_vector_find_mismatch(typename SV1::bvector_type &bv, const SV1 &sv1, const SV2 &sv2, bm::null_support null_proc)
Find mismatch vector, indicating positions of mismatch between two sparse vectors (uses linear scan i...
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:369
ad-hoc conditional expressions
Definition: bmutil.h:110
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)
bool find_eq_str_impl(const SV &sv, const typename SV::value_type *str, typename SV::bvector_type &bv_out, bool prefix_sub)
find EQ str / prefix impl
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:34
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)
Definition: bm.h:76
void reset_binding() BMNOEXCEPT
reset sparse vector binding
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)
void assign_if_not_set(allocator_pool_type &pool, bvector< Alloc > &bv) BMNOEXCEPT
check if vector has no assigned allocator and set one
Definition: bm.h:803
algorithms for sparse_vector scan/search
bool sparse_vector_find_first_mismatch(const SV &sv1, const SV &sv2, typename SV::size_type &midx, bm::null_support null_proc=bm::use_null)
Find first mismatch (element which is different) between two sparse vectors (uses linear scan in bit-...
bm::bvector< Alloc > & bit_xor(const bm::bvector< Alloc > &bv1, const bm::bvector< Alloc > &bv2, typename bm::bvector< Alloc >::optmode opt_mode)
3-operand XOR : this := bv1 XOR bv2
Definition: bm.h:5059
size_type size() const BMNOEXCEPT
Returns bvector&#39;s capacity (number of bits it can store)
Definition: bm.h:1272
size_type BM_VECT_ALIGN gather_idx_ [BSIZE] BM_VECT_ALIGN_ATTR
gather_buffer< sv_g_size > gather_buffer_type
int compare_str(const SV &sv, size_type idx, const value_type *str)
compare sv[idx] with input str
do not support NULL values
Definition: bmconst.h:216
const unsigned id_max
Definition: bmconst.h:108
Algorithms for bvector<> (main include)
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
null_support
NULL-able value support.
Definition: bmconst.h:213
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)
Alloc allocator_type
Definition: bm.h:110
input set is sorted (ascending order)
Definition: bmconst.h:191
const unsigned sub_block3_size
Definition: bmconst.h:123
void one_pass_run(const bvector_type &bv_in, const SV &sv_brel, bvector_type &bv_out)
BMFORCEINLINE bm::id_t word_bitcount(bm::id_t w) BMNOEXCEPT
Definition: bmfunc.h:199
bool prepare_and_sub_aggregator(const SV &sv, typename SV::value_type value)
Prepare aggregator for AND-SUB (EQ) search.
support "non-assigned" or "NULL" logic
Definition: bmconst.h:215
no optimization
Definition: bm.h:131
bvector_type::allocator_type allocator_type
bool find_eq_str(const SV &sv, const typename SV::value_type *str, typename SV::bvector_type &bv_out)
find sparse vector elements (string)
allocator_type::allocator_pool_type allocator_pool_type
Definition: bm.h:111
Definitions(internal)
void find_zero(const SV &sv, typename SV::bvector_type &bv_out)
find all sparse vector elements EQ to 0
allocator_type::allocator_pool_type allocator_pool_type
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.
const unsigned gap_max_bits
Definition: bmconst.h:80
value_type BM_VECT_ALIGN buffer_ [BSIZE] BM_VECT_ALIGN_ATTR
bvector_type::allocator_type::allocator_pool_type allocator_pool_type
bool lower_bound_str(const SV &sv, const typename SV::value_type *str, typename SV::size_type &pos)
lower bound search for an array position
bool find_first_eq(const SV &sv, typename SV::value_type value, size_type &idx)
find first value (may include NULL indexes)
const unsigned set_block_mask
Definition: bmconst.h:56
bool find_eq_str_prefix(const SV &sv, const typename SV::value_type *str, typename SV::bvector_type &bv_out)
find sparse vector elements with a given prefix (string)
Constant iterator designed to enumerate "ON" bits.
Definition: bm.h:599
bool lower_bound(const SV &sv, const typename SV::value_type val, typename SV::size_type &pos)
lower bound search for an array position
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 resize(size_type new_size)
Change size of the bvector.
Definition: bm.h:2282
void run(const bvector_type &bv_in, const SV &sv_brel, bvector_type &bv_out)
Run remap transformation.
bvector< Alloc > & invert()
Invert/NEG all bits It should be noted, invert is affected by size() if size is set - it only inverts...
Definition: bm.h:3011
unsigned int id_t
Definition: bmconst.h:37
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:136
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 ...
#define BMNOEXCEPT
Definition: bmdef.h:81
bm::bvector bvector_type
Definition: xsample07a.cpp:94
const unsigned set_block_shift
Definition: bmconst.h:55
void correct_nulls(const SV &sv, typename SV::bvector_type &bv_out)
Exclude possible NULL values from the result vector.
void dynamic_range_clip_high(SV &svect, unsigned high_bit)
Clip dynamic range for signal higher than specified.
bm::bvector< Alloc > & bit_or(const bm::bvector< Alloc > &bv1, const bm::bvector< Alloc > &bv2, typename bm::bvector< Alloc >::optmode opt_mode)
3-operand OR : this := bv1 OR bv2
Definition: bm.h:4962
int compare(const SV &sv, size_type idx, const value_type val) BMNOEXCEPT
compare sv[idx] with input value
unsigned short bitscan(V w, B *bits) BMNOEXCEPT
Templated Bitscan with dynamic dispatch for best type.
Definition: bmfunc.h:785
sorted and in one block (internal!)
Definition: bmconst.h:192
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)
bm::dynamic_heap_matrix< value_type, allocator_type > heap_matrix_type