NCBI C++ ToolKit
bm.h
Go to the documentation of this file.

Go to the SVN repository for this file.

1 #ifndef BM__H__INCLUDED__
2 #define BM__H__INCLUDED__
3 /*
4 Copyright(c) 2002-2019 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5 
6 Licensed under the Apache License, Version 2.0 (the "License");
7 you may not use this file except in compliance with the License.
8 You may obtain a copy of the License at
9 
10  http://www.apache.org/licenses/LICENSE-2.0
11 
12 Unless required by applicable law or agreed to in writing, software
13 distributed under the License is distributed on an "AS IS" BASIS,
14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 See the License for the specific language governing permissions and
16 limitations under the License.
17 
18 For more information please visit: http://bitmagic.io
19 */
20 
21 /*! \file bm.h
22  \brief Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators
23 */
24 
25 
26 // define BM_NO_STL if you use BM in "STL free" environment and want
27 // to disable any references to STL headers
28 #ifndef BM_NO_STL
29 # include <iterator>
30 # include <initializer_list>
31 # include <stdexcept>
32 #endif
33 
34 #include <limits.h>
35 
36 #ifdef _MSC_VER
37 #pragma warning( push )
38 #pragma warning( disable : 4311 4312 4127)
39 #endif
40 
41 
42 #include "bmdef.h"
43 #include "bmconst.h"
44 #include "bmsimd.h"
45 #include "bmfwd.h"
46 
47 # define BM_DECLARE_TEMP_BLOCK(x) bm::bit_block_t x;
48 
49 #include "bmfunc.h"
50 #include "encoding.h"
51 #include "bmalloc.h"
52 #include "bmblocks.h"
53 #include "bmbuffer.h"
54 #include "bmdef.h"
55 
56 #include "bmrs.h"
57 
58 extern "C"
59 {
60 #ifdef BM64ADDR
61  typedef int (*bit_visitor_callback_type)(void* handle_ptr, bm::id64_t bit_idx);
62 #else
63  /**
64  Callback type to visit (callback style) bits in bit-vector(s)
65 
66  @param handle_ptr - custom pointer to callback specific data
67  @param bit_idx - number/index of visited bit
68  @return negative return code is recognised as a request to interrupt visiting
69 
70  @ingroup bvector
71  */
72  typedef int (*bit_visitor_callback_type)(void* handle_ptr, bm::id_t bit_idx);
73 #endif
74 }
75 
76 
77 namespace bm
78 {
79 
80 /** @defgroup bmagic BitMagic Library
81  BitMagic C++ Library
82  For more information please visit: http://bitmagic.io
83 */
84 
85 
86 /** @defgroup bvector bvector<> container
87  The Main bvector<> Group
88  bvector<> template: front end of the BitMagic library.
89 
90  @ingroup bmagic
91 */
92 
93 /** @defgroup bvit bvector<> iterators
94  Iterators for compressed bit-vector traversal
95  @ingroup bvector
96 */
97 
98 
99 
100 #ifdef BM64ADDR
102 #else
104 #endif
105 
106 
107 /*!
108  @brief Bitvector
109  Bit-vector container with runtime compression of bits
110 
111  @ingroup bvector
112 */
113 template<class Alloc>
114 class bvector
115 {
116 public:
118  typedef typename allocator_type::allocator_pool_type allocator_pool_type;
122 
123  /** Statistical information about bitset's memory allocation details. */
124  struct statistics : public bv_statistics
125  {};
126 
127  /*!
128  \brief Optimization mode
129  Every next level means additional checks (better compression vs time)
130  \sa optimize
131  */
132  enum optmode
133  {
134  opt_none = 0, ///< no optimization
135  opt_free_0 = 1, ///< Free unused 0 blocks
136  opt_free_01 = 2, ///< Free unused 0 and 1 blocks
137  opt_compress = 3 ///< compress blocks when possible (GAP/prefix sum)
138  };
139 
140 
141  /**
142  @brief Class reference implements an object for bit assignment.
143  Since C++ does not provide with build-in bit type supporting l-value
144  operations we have to emulate it.
145 
146  @ingroup bvector
147  */
148  class reference
149  {
150  public:
152  : bv_(bv),
153  position_(position)
154  {}
155 
157  : bv_(ref.bv_),
158  position_(ref.position_)
159  {
160  bv_.set(position_, ref.bv_.get_bit(position_));
161  }
162 
163  operator bool() const BMNOEXCEPT
164  {
165  return bv_.get_bit(position_);
166  }
167 
168  const reference& operator=(const reference& ref) const
169  {
170  bv_.set(position_, (bool)ref);
171  return *this;
172  }
173 
174  const reference& operator=(bool value) const BMNOEXCEPT
175  {
176  bv_.set(position_, value);
177  return *this;
178  }
179 
180  bool operator==(const reference& ref) const BMNOEXCEPT
181  {
182  return bool(*this) == bool(ref);
183  }
184 
185  /*! Bitwise AND. Performs operation: bit = bit AND value */
186  const reference& operator&=(bool value) const
187  {
188  bv_.set_bit_and(position_, value);
189  return *this;
190  }
191 
192  /*! Bitwise OR. Performs operation: bit = bit OR value */
193  const reference& operator|=(bool value) const
194  {
195  if (value != bv_.get_bit(position_))
196  {
197  bv_.set_bit(position_);
198  }
199  return *this;
200  }
201 
202  /*! Bitwise exclusive-OR (XOR). Performs operation: bit = bit XOR value */
203  const reference& operator^=(bool value) const
204  {
205  bv_.set(position_, value != bv_.get_bit(position_));
206  return *this;
207  }
208 
209  /*! Logical Not operator */
211  {
212  return !bv_.get_bit(position_);
213  }
214 
215  /*! Bit Not operator */
217  {
218  return !bv_.get_bit(position_);
219  }
220 
221  /*! Negates the bit value */
223  {
224  bv_.flip(position_);
225  return *this;
226  }
227 
228  private:
229  bvector<Alloc>& bv_; //!< Reference variable on the parent.
230  size_type position_; //!< Position in the parent bitvector.
231  };
232 
233  typedef bool const_reference;
234 
235  /*!
236  @brief Base class for all iterators.
237  @ingroup bvit
238  */
240  {
241  friend class bvector;
242  public:
244  : bv_(0), position_(bm::id_max), block_(0), block_type_(0),
245  block_idx_(0)
246  {}
247 
248  bool operator==(const iterator_base& it) const BMNOEXCEPT
249  {
250  return (position_ == it.position_) && (bv_ == it.bv_);
251  }
252 
253  bool operator!=(const iterator_base& it) const BMNOEXCEPT
254  {
255  return ! operator==(it);
256  }
257 
258  bool operator < (const iterator_base& it) const BMNOEXCEPT
259  {
260  return position_ < it.position_;
261  }
262 
263  bool operator <= (const iterator_base& it) const BMNOEXCEPT
264  {
265  return position_ <= it.position_;
266  }
267 
268  bool operator > (const iterator_base& it) const BMNOEXCEPT
269  {
270  return position_ > it.position_;
271  }
272 
273  bool operator >= (const iterator_base& it) const BMNOEXCEPT
274  {
275  return position_ >= it.position_;
276  }
277 
278  /**
279  \fn bool bm::bvector::iterator_base::valid() const
280  \brief Checks if iterator is still valid. Analog of != 0 comparison for pointers.
281  \returns true if iterator is valid.
282  */
283  bool valid() const BMNOEXCEPT { return position_ != bm::id_max; }
284 
285  /**
286  \fn bool bm::bvector::iterator_base::invalidate()
287  \brief Turns iterator into an invalid state.
288  */
290  { position_ = bm::id_max; block_type_ = ~0u;}
291 
292  /** \brief Compare FSMs for testing purposes
293  \internal
294  */
295  bool compare_state(const iterator_base& ib) const BMNOEXCEPT
296  {
297  if (this->bv_ != ib.bv_) return false;
298  if (this->position_ != ib.position_) return false;
299  if (this->block_ != ib.block_) return false;
300  if (this->block_type_ != ib.block_type_) return false;
301  if (this->block_idx_ != ib.block_idx_) return false;
302 
303  const block_descr& bd = this->bdescr_;
304  const block_descr& ib_db = ib.bdescr_;
305 
306  if (this->block_type_ == 0) // bit block
307  {
308  if (bd.bit_.ptr != ib_db.bit_.ptr) return false;
309  if (bd.bit_.idx != ib_db.bit_.idx) return false;
310  if (bd.bit_.cnt != ib_db.bit_.cnt) return false;
311  if (bd.bit_.pos != ib_db.bit_.pos) return false;
312  for (unsigned i = 0; i < bd.bit_.cnt; ++i)
313  {
314  if (bd.bit_.bits[i] != ib_db.bit_.bits[i]) return false;
315  }
316  }
317  else // GAP block
318  {
319  if (bd.gap_.ptr != ib_db.gap_.ptr) return false;
320  if (bd.gap_.gap_len != ib_db.gap_.gap_len) return false;
321  }
322  return true;
323  }
324 
325  public:
326 
327  /** Bit-block descriptor
328  @internal
329  */
331  {
332  const bm::word_t* ptr; //!< Word pointer.
333  unsigned char bits[set_bitscan_wave_size*32]; //!< bit list
334  unsigned short idx; //!< Current position in the bit list
335  unsigned short cnt; //!< Number of ON bits
336  size_type pos; //!< Last bit position decode before
337  };
338 
339  /** Information about current DGAP block.
340  @internal
341  */
342  struct dgap_descr
343  {
344  const gap_word_t* ptr; //!< Word pointer.
345  gap_word_t gap_len; //!< Current dgap length.
346  };
347 
348  protected:
349  bm::bvector<Alloc>* bv_; //!< Pointer on parent bitvector
350  size_type position_; //!< Bit position (bit idx)
351  const bm::word_t* block_; //!< Block pointer.(NULL-invalid)
352  unsigned block_type_; //!< Type of block. 0-Bit, 1-GAP
353  block_idx_type block_idx_; //!< Block index
354 
355  /*! Block type dependent information for current block. */
357  {
358  bitblock_descr bit_; //!< BitBlock related info.
359  dgap_descr gap_; //!< DGAP block related info.
361  };
362 
363  /*!
364  @brief Output iterator iterator designed to set "ON" bits based on
365  input sequence of integers (bit indeces).
366 
367  STL container can be converted to bvector using this iterator
368  Insert iterator guarantees the vector will be dynamically resized
369  (set_bit does not do that).
370 
371  @note
372  If you have many bits to set it is a good idea to use output iterator
373  instead of explicitly calling set, because iterator may implement
374  some performance specific tricks to make sure bulk insert is fast.
375 
376  @sa bulk_insert_iterator
377 
378  @ingroup bvit
379  */
381  {
382  friend class bulk_insert_iterator;
383  public:
384 #ifndef BM_NO_STL
385  typedef std::output_iterator_tag iterator_category;
386 #endif
389  typedef void difference_type;
390  typedef void pointer;
391  typedef void reference;
392 
394 
396  : bvect_(&bvect),
397  max_bit_(bvect.size())
398  {
399  bvect_->init();
400  }
401 
403  : bvect_(iit.bvect_),
404  max_bit_(iit.max_bit_)
405  {
406  }
407 
409  {
410  bvect_ = ii.bvect_; max_bit_ = ii.max_bit_;
411  return *this;
412  }
413 
415  {
417  BM_ASSERT_THROW(n < bm::id_max, BM_ERR_RANGE);
418 
419  if (n >= max_bit_)
420  {
421  max_bit_ = n;
422  if (n >= bvect_->size())
423  {
424  size_type new_size = (n == bm::id_max) ? bm::id_max : n + 1;
425  bvect_->resize(new_size);
426  }
427  }
429  return *this;
430  }
431  /*! Returns *this without doing anything (no-op) */
432  insert_iterator& operator*() { return *this; }
433  /*! Returns *this. This iterator does not move (no-op) */
434  insert_iterator& operator++() { return *this; }
435  /*! Returns *this. This iterator does not move (no-op)*/
436  insert_iterator& operator++(int) { return *this; }
437 
438  bvector_type* get_bvector() const { return bvect_; }
439 
440  protected:
443  };
444 
445 
446  /*!
447  @brief Output iterator iterator designed to set "ON" bits based on
448  input sequence of integers.
449 
450  STL container can be converted to bvector using this iterator
451  Insert iterator guarantees the vector will be dynamically resized
452  (set_bit does not do that).
453 
454  The difference from the canonical insert iterator, is that
455  bulk insert implements internal buffering, which needs
456  to flushed (or flushed automatically when goes out of scope).
457  Buffering creates a delayed effect, which needs to be
458  taken into account.
459 
460  @sa insert_iterator
461 
462  @ingroup bvit
463  */
465  {
466  public:
467 #ifndef BM_NO_STL
468  typedef std::output_iterator_tag iterator_category;
469 #endif
473  typedef void difference_type;
474  typedef void pointer;
475  typedef void reference;
476 
478  : bvect_(0), buf_(0), buf_size_(0), sorted_(BM_UNKNOWN) {}
479 
481  {
482  flush();
483  if (buf_)
484  bvect_->blockman_.get_allocator().free_bit_block((bm::word_t*)buf_);
485  }
486 
489  : bvect_(&bvect), sorted_(so)
490  {
491  bvect_->init();
492 
493  buf_ = (value_type*) bvect_->blockman_.get_allocator().alloc_bit_block();
494  buf_size_ = 0;
495  }
496 
498  : bvect_(iit.bvect_)
499  {
500  buf_ = bvect_->blockman_.get_allocator().alloc_bit_block();
501  buf_size_ = iit.buf_size_;
502  sorted_ = iit.sorted_;
503  ::memcpy(buf_, iit.buf_, buf_size_ * sizeof(*buf_));
504  }
505 
506  bulk_insert_iterator(const insert_iterator& iit)
507  : bvect_(iit.get_bvector())
508  {
509  buf_ = (value_type*) bvect_->blockman_.get_allocator().alloc_bit_block();
510  buf_size_ = 0;
512  }
513 
515  : bvect_(iit.bvect_)
516  {
517  buf_ = iit.buf_; iit.buf_ = 0;
518  buf_size_ = iit.buf_size_;
519  sorted_ = iit.sorted_;
520  }
521 
523  {
524  bvect_ = ii.bvect_;
525  if (!buf_)
526  buf_ = bvect_->allocate_tempblock();
527  buf_size_ = ii.buf_size_;
528  ::memcpy(buf_, ii.buf_, buf_size_ * sizeof(*buf_));
529  sorted_ = ii.sorted_;
530  return *this;
531  }
532 
534  {
535  bvect_ = ii.bvect_;
536  if (buf_)
537  bvect_->free_tempblock(buf_);
538  buf_ = ii.buf_; ii.buf_ = 0;
539  buf_size_ = ii.buf_size_;
540  sorted_ = ii.sorted_;
541  return *this;
542  }
543 
545  {
547  BM_ASSERT_THROW(n < bm::id_max, BM_ERR_RANGE);
548 
549  if (buf_size_ == buf_size_max())
550  {
552  buf_size_ = 0;
553  }
554  buf_[buf_size_++] = n;
555  return *this;
556  }
557 
558  /*! Returns *this without doing anything (no-op) */
559  bulk_insert_iterator& operator*() { return *this; }
560  /*! Returns *this. This iterator does not move (no-op) */
561  bulk_insert_iterator& operator++() { return *this; }
562  /*! Returns *this. This iterator does not move (no-op)*/
563  bulk_insert_iterator& operator++(int) { return *this; }
564 
565  /*! Flush the internal buffer into target bvector */
566  void flush()
567  {
568  BM_ASSERT(bvect_);
569  if (buf_size_)
570  {
572  buf_size_ = 0;
573  }
574  bvect_->sync_size();
575  }
576 
578 
579  protected:
580  static
582  {
583  #ifdef BM64ADDR
584  return bm::set_block_size / 2;
585  #else
586  return bm::set_block_size;
587  #endif
588  }
589 
590  protected:
591  bvector_type* bvect_; ///< target bvector
592  size_type* buf_; ///< bulk insert buffer
593  size_type buf_size_; ///< current buffer size
594  bm::sort_order sorted_; ///< sort order hint
595  };
596 
597 
598 
599  /*! @brief Constant iterator designed to enumerate "ON" bits
600  @ingroup bvit
601  */
602  class enumerator : public iterator_base
603  {
604  public:
605 #ifndef BM_NO_STL
606  typedef std::input_iterator_tag iterator_category;
607 #endif
609  typedef unsigned difference_type;
610  typedef unsigned* pointer;
611  typedef unsigned& reference;
612 
613  public:
615  {}
616 
617  /*! @brief Construct enumerator associated with a vector.
618  Important: This construction creates unpositioned iterator with status
619  valid() == false. It can be re-positioned using go_first() or go_to().
620  @sa go_to
621  */
623  : iterator_base()
624  {
625  this->bv_ = const_cast<bvector<Alloc>*>(bv);
626  }
627 
628  /*! @brief Construct enumerator for bit vector
629  @param bv bit-vector reference
630  @param pos bit position in the vector
631  if position is 0, it finds the next 1 or becomes not valid
632  (en.valid() == false)
633  */
635  : iterator_base()
636  {
637  this->bv_ = const_cast<bvector<Alloc>*>(&bv);
638  go_to(pos);
639  }
640 
641 
642  /*! @brief Construct enumerator for bit vector
643  @param bv bit-vector pointer
644  @param pos bit position in the vector
645  if position is 0, it finds the next 1 or becomes not valid
646  (en.valid() == false)
647  */
649  : iterator_base()
650  {
651  this->bv_ = const_cast<bvector<Alloc>*>(bv);
652  this->go_to(pos);
653  }
654 
655  /*! \brief Get current position (value) */
657 
658  /*! \brief Get current position (value) */
659  size_type value() const BMNOEXCEPT { return this->position_; }
660 
661  /*! \brief Advance enumerator forward to the next available bit */
662  enumerator& operator++() BMNOEXCEPT { this->go_up(); return *this; }
663 
664  /*! \brief Advance enumerator forward to the next available bit.
665  Possibly do NOT use this operator it is slower than the pre-fix increment.
666  */
667  enumerator operator++(int) BMNOEXCEPT
668  {
669  enumerator tmp = *this;
670  this->go_up();
671  return tmp;
672  }
673 
674  /*! \brief Position enumerator to the first available bit */
675  void go_first() BMNOEXCEPT;
676 
677  /*! advance iterator forward by one
678  @return true if advance was successfull and the enumerator is valid
679  */
680  bool advance() BMNOEXCEPT { return this->go_up(); }
681 
682  /*! \brief Advance enumerator to the next available bit */
683  bool go_up() BMNOEXCEPT;
684 
685  /*!
686  @brief Skip to specified relative rank
687  @param rank - number of ON bits to go for (must be: > 0)
688  @return true if skip was successfull and enumerator is valid
689  */
691  {
692  BM_ASSERT(rank);
693  --rank;
694  if (!rank)
695  return this->valid();
696  return skip(rank);
697  }
698 
699  /*!
700  @brief Skip specified number of bits from enumeration
701  @param rank - number of ON bits to skip
702  @return true if skip was successfull and enumerator is valid
703  */
704  bool skip(size_type rank) BMNOEXCEPT;
705 
706  /*!
707  @brief go to a specific position in the bit-vector (or next)
708  */
710 
711  private:
712  typedef typename iterator_base::block_descr block_descr_type;
713 
721 
722  };
723 
724  /*!
725  @brief Constant iterator designed to enumerate "ON" bits
726  counted_enumerator keeps bitcount, ie number of ON bits starting
727  from the position 0 in the bit string up to the currently enumerated bit
728 
729  When increment operator called current position is increased by 1.
730 
731  @ingroup bvit
732  */
734  {
735  public:
736 #ifndef BM_NO_STL
737  typedef std::input_iterator_tag iterator_category;
738 #endif
739  counted_enumerator() BMNOEXCEPT : bit_count_(0){}
740 
742  {
743  bit_count_ = this->valid(); // 0 || 1
744  }
745 
746  counted_enumerator& operator=(const enumerator& en) BMNOEXCEPT
747  {
748  enumerator* me = this;
749  *me = en;
750  if (this->valid())
751  this->bit_count_ = 1;
752  return *this;
753  }
754 
755  counted_enumerator& operator++() BMNOEXCEPT
756  {
757  this->go_up();
758  this->bit_count_ += this->valid();
759  return *this;
760  }
761 
762  counted_enumerator operator++(int)
763  {
764  counted_enumerator tmp(*this);
765  this->go_up();
766  this->bit_count_ += this->valid();
767  return tmp;
768  }
769 
770  /*! @brief Number of bits ON starting from the .
771 
772  Method returns number of ON bits fromn the bit 0 to the current bit
773  For the first bit in bitvector it is 1, for the second 2
774  */
775  size_type count() const BMNOEXCEPT { return bit_count_; }
776  private:
777  /*! Function closed for usage */
778  counted_enumerator& go_to(size_type pos);
779 
780  private:
782  };
783 
784  /*!
785  Resource guard for bvector<>::set_allocator_pool()
786  @ingroup bvector
787  @internal
788  */
789  typedef
791 
792  friend class iterator_base;
793  friend class enumerator;
794  template<class BV> friend class aggregator;
795  template<class BV> friend class operation_deserializer;
796  template<class BV, class DEC> friend class deserializer;
797 
798 public:
799  /*! @brief memory allocation policy
800 
801  Defualt memory allocation policy uses BM_BIT, and standard
802  GAP levels tune-ups
803  */
805  {
808 
811  : strat(s), glevel_len(glevels)
812  {}
813  };
814 
817 
818 public:
819  /*! @name Construction, initialization, assignment */
820  //@{
821 
822  /*!
823  \brief Constructs bvector class
824  \param strat - operation mode strategy,
825  BM_BIT - default strategy, bvector use plain bitset
826  blocks, (performance oriented strategy).
827  BM_GAP - memory effitent strategy, bvector allocates
828  blocks as array of intervals(gaps) and convert blocks
829  into plain bitsets only when enthropy grows.
830  \param glevel_len
831  - pointer on C-style array keeping GAP block sizes.
832  bm::gap_len_table<true>::_len - default value set
833  (use bm::gap_len_table_min<true>::_len for very sparse vectors)
834  (use bm::gap_len_table_nl<true>::_len non-linear GAP growth)
835  \param bv_size
836  - bvector size (number of bits addressable by bvector), bm::id_max means
837  "no limits" (recommended).
838  bit vector allocates this space dynamically on demand.
839  \param alloc - alllocator for this instance
840 
841  \sa bm::gap_len_table bm::gap_len_table_min set_new_blocks_strat
842  */
844  const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
845  size_type bv_size = bm::id_max,
846  const Alloc& alloc = Alloc())
847  : blockman_(glevel_len, bv_size, alloc),
848  new_blocks_strat_(strat),
849  size_(bv_size)
850  {}
851 
852  /*!
853  \brief Constructs bvector class
854  */
856  strategy strat = BM_BIT,
857  const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
858  const Alloc& alloc = Alloc())
859  : blockman_(glevel_len, bv_size, alloc),
860  new_blocks_strat_(strat),
861  size_(bv_size)
862  {}
863 
864  /*!
865  \brief Copy constructor
866  */
870  size_(bvect.size_)
871  {}
872 
873  /*!
874  \brief Copy constructor for range copy [left..right]
875  \sa copy_range
876  */
878  : blockman_(bvect.blockman_.glevel_len_, bvect.blockman_.max_bits_, bvect.blockman_.alloc_),
880  size_(bvect.size_)
881  {
882  if (!bvect.blockman_.is_init())
883  return;
884  if (left > right)
885  bm::xor_swap(left, right);
886  copy_range_no_check(bvect, left, right);
887  }
888 
889  /*!
890  \brief Copy-constructor for mutable/immutable initialization
891  */
893  : blockman_(bvect.blockman_.glevel_len_, bvect.blockman_.max_bits_, bvect.blockman_.alloc_),
895  size_(bvect.size_)
896  {
897  if (!bvect.blockman_.is_init())
898  return;
899  if (is_final == bm::finalization::READONLY)
901  else
903  }
904 
905 
907 
908  /*!
909  \brief Explicit post-construction initialization.
910  Must be caled to make sure safe use of *_no_check() methods
911  */
912  void init();
913 
914  /*!
915  \brief Explicit post-construction initialization.
916  Must be caled right after construction strickly before any modificating calls
917  to make sure safe use of *_no_check() methods.
918  This init can do pre-allocation of top level structures.
919 
920  @param top_size - request to do pre-allocation of the top level of a sparse bit-vector tree
921  (can be up to 256 for 32-bit mode)
922  @param alloc_subs - if true also allocates second level structures
923  */
924  void init(unsigned top_size, bool alloc_subs);
925 
926 
927  /*!
928  \brief Copy assignment operator
929  */
931  {
932  this->copy(bvect, bm::finalization::UNDEFINED);
933  return *this;
934  }
935 
936 #ifndef BM_NO_CXX11
937  /*!
938  \brief Move constructor
939  */
941  {
943  size_ = bvect.size_;
945  }
946 
947  /*!
948  \brief Brace constructor
949  */
950  bvector(std::initializer_list<size_type> il)
951  : blockman_(bm::gap_len_table<true>::_len, bm::id_max, Alloc()),
953  size_(bm::id_max)
954  {
955  init();
956  std::initializer_list<size_type>::const_iterator it_start = il.begin();
957  std::initializer_list<size_type>::const_iterator it_end = il.end();
958  for (; it_start < it_end; ++it_start)
959  this->set_bit_no_check(*it_start);
960  }
961 
962  /*!
963  \brief Move assignment operator
964  */
966  {
967  this->move_from(bvect);
968  return *this;
969  }
970 #endif
971 
972  /*!
973  \brief Copy bvector from the argument bvector
974  \param bvect - bit-vector to copy from
975  \param is_final - BM_READONLY - copies as immutable, BM_READWRITE - copies as mutable
976  even if the argument bvect is read-only vector,
977  BM_UNDEFINED - follow the argument type as is
978  */
979  void copy(const bvector<Alloc>& bvect, bm::finalization is_final);
980 
981  /*!
982  \brief Move bvector content from another bvector
983  */
985 
986  /*! \brief Exchanges content of bv and this bvector.
987  */
989 
990  /*! \brief Merge/move content from another vector
991 
992  Merge performs a logical OR operation, but the source vector
993  is not immutable. Source content gets destroyed (memory moved)
994  to create a union of two vectors.
995  Merge operation can be more efficient than OR if argument is
996  a temporary vector.
997 
998  @param bvect - [in, out] - source vector (NOT immutable)
999  */
1001 
1002  //@}
1003 
1005  {
1006  if (n >= size_)
1007  {
1008  size_type new_size = (n == bm::id_max) ? bm::id_max : n + 1;
1009  resize(new_size);
1010  }
1011  return reference(*this, n);
1012  }
1013 
1015  {
1016  BM_ASSERT(n < size_);
1017  return get_bit(n);
1018  }
1019 
1020  void operator &= (const bvector<Alloc>& bv) { bit_and(bv); }
1021  void operator ^= (const bvector<Alloc>& bv) { bit_xor(bv); }
1022  void operator |= (const bvector<Alloc>& bv) { bit_or(bv); }
1023  void operator -= (const bvector<Alloc>& bv) { bit_sub(bv); }
1024 
1025  bool operator < (const bvector<Alloc>& bv) const { return compare(bv)<0; }
1026  bool operator <= (const bvector<Alloc>& bv) const { return compare(bv)<=0; }
1027  bool operator > (const bvector<Alloc>& bv) const { return compare(bv)>0; }
1028  bool operator >= (const bvector<Alloc>& bv) const { return compare(bv) >= 0; }
1029  bool operator == (const bvector<Alloc>& bv) const BMNOEXCEPT { return equal(bv); }
1030  bool operator != (const bvector<Alloc>& bv) const BMNOEXCEPT { return !equal(bv); }
1031 
1032  bvector<Alloc> operator~() const { return bvector<Alloc>(*this).invert(); }
1033 
1035  { return blockman_.get_allocator(); }
1036 
1037  /// Set allocator pool for local (non-th readed)
1038  /// memory cyclic(lots of alloc-free ops) opertations
1039  ///
1041  { blockman_.get_allocator().set_pool(pool_ptr); }
1042 
1043  /// Get curent allocator pool (if set)
1044  /// @return pointer to the current pool or NULL
1046  { return blockman_.get_allocator().get_pool(); }
1047 
1048  // --------------------------------------------------------------------
1049  /*! @name Read-only / immutable vector methods */
1050  //@{
1051 
1052  /// Turn current vector to read-only (immutable vector).
1053  /// After calling this method any modification (non-const methods) will cause undefined behavior
1054  /// (likely crash or assert)
1055  ///
1056  /// \sa is_ro
1057  void freeze();
1058 
1059  /// Returns true if vector is read-only
1061 
1062  //@}
1063 
1064  // --------------------------------------------------------------------
1065  /*! @name Bit access/modification methods */
1066  //@{
1067 
1068  /*!
1069  \brief Sets bit n.
1070  \param n - index of the bit to be set.
1071  \param val - new bit value
1072  \return TRUE if bit was changed
1073  */
1074  bool set_bit(size_type n, bool val = true);
1075 
1076  /*!
1077  \brief Sets bit n using bit AND with the provided value.
1078  \param n - index of the bit to be set.
1079  \param val - new bit value
1080  \return TRUE if bit was changed
1081  */
1082  bool set_bit_and(size_type n, bool val = true);
1083 
1084  /*!
1085  \brief Increment the specified element
1086 
1087  Bit increment rules:
1088  0 + 1 = 1 (no carry over)
1089  1 + 1 = 0 (with carry over returned)
1090 
1091  \param n - index of the bit to be set
1092  \return TRUE if carry over created (1+1)
1093  */
1094  bool inc(size_type n);
1095 
1096 
1097  /*!
1098  \brief Sets bit n only if current value equals the condition
1099  \param n - index of the bit to be set.
1100  \param val - new bit value
1101  \param condition - expected current value
1102  \return TRUE if bit was changed
1103  */
1104  bool set_bit_conditional(size_type n, bool val, bool condition);
1105 
1106  /*!
1107  \brief Sets bit n if val is true, clears bit n if val is false
1108  \param n - index of the bit to be set
1109  \param val - new bit value
1110  \return *this
1111  */
1112  bvector<Alloc>& set(size_type n, bool val = true);
1113 
1114  /*!
1115  \brief Sets every bit in this bitset to 1.
1116  \return *this
1117  */
1119 
1120  /*!
1121  \brief Set list of bits in this bitset to 1.
1122 
1123  Method implements optimized bulk setting of multiple bits at once.
1124  The best results are achieved when the imput comes sorted.
1125  This is equivalent of OR (Set Union), argument set as an array.
1126 
1127  @param ids - pointer on array of indexes to set
1128  @param ids_size - size of the input (ids)
1129  @param so - sort order (use BM_SORTED for faster load)
1130 
1131  @sa keep, clear
1132  */
1133  void set(const size_type* ids, size_type ids_size,
1135 
1136  /*!
1137  \brief Keep list of bits in this bitset, others are cleared
1138 
1139  This is equivalent of AND (Set Intersect), argument set as an array.
1140 
1141  @param ids - pointer on array of indexes to set
1142  @param ids_size - size of the input (ids)
1143  @param so - sort order (use BM_SORTED for faster load)
1144 
1145  @sa set, clear
1146  */
1147  void keep(const size_type* ids, size_type ids_size,
1149 
1150  /*!
1151  \brief clear list of bits in this bitset
1152 
1153  This is equivalent of AND NOT (Set Substract), argument set as an array.
1154 
1155  @param ids - pointer on array of indexes to set
1156  @param ids_size - size of the input (ids)
1157  @param so - sort order (use BM_SORTED for faster load)
1158 
1159  @sa set, keep
1160  */
1161  void clear(const size_type* ids, size_type ids_size,
1163 
1164  /*!
1165  \brief swap values of bits
1166 
1167  @param idx1 - index of bit to swap with
1168  @param idx2 - index of bit to swap with
1169  */
1170  void swap(size_type idx1, size_type idx2);
1171 
1172 
1173  /*!
1174  \brief Set bit without checking preconditions (size, etc)
1175 
1176  Fast set bit method, without safety net.
1177  Make sure you call bvector<>::init() before setting bits with this
1178  function.
1179 
1180  \param n - bit number
1181  */
1183 
1184  /**
1185  \brief Set specified bit without checking preconditions (size, etc)
1186  */
1187  bool set_bit_no_check(size_type n, bool val);
1188 
1189  /*!
1190  \brief Sets all bits in the specified closed interval [left,right]
1191  Interval must be inside the bvector's size.
1192  This method DOES NOT resize vector.
1193 
1194  \param left - interval start
1195  \param right - interval end (closed interval)
1196  \param value - value to set interval in
1197 
1198  \return *this
1199  @sa clear_range
1200  */
1202  size_type right,
1203  bool value = true);
1204 
1205 
1206  /*!
1207  \brief Sets all bits to zero in the specified closed interval [left,right]
1208  Interval must be inside the bvector's size.
1209  This method DOES NOT resize vector.
1210 
1211  \param left - interval start
1212  \param right - interval end (closed interval)
1213 
1214  @sa set_range
1215  */
1216  void clear_range(size_type left, size_type right)
1217  { set_range(left, right, false); }
1218 
1219 
1220  /*!
1221  \brief Sets all bits to zero outside of the closed interval [left,right]
1222  Expected result: 00000...0[left, right]0....0000
1223 
1224  \param left - interval start
1225  \param right - interval end (closed interval)
1226 
1227  @sa set_range
1228  */
1229  void keep_range(size_type left, size_type right);
1230 
1231  /*!
1232  \brief Copy all bits in the specified closed interval [left,right]
1233 
1234  \param bvect - source bit-vector
1235  \param left - interval start
1236  \param right - interval end (closed interval)
1237  */
1239  size_type left,
1240  size_type right);
1241 
1242  /*!
1243  \brief Clears bit n.
1244  \param n - bit's index to be cleaned.
1245  \return true if bit was cleared
1246  */
1247  bool clear_bit(size_type n) { return set_bit(n, false); }
1248 
1249  /*!
1250  \brief Clears bit n without precondiion checks
1251  \param n - bit's index to be cleaned.
1252  */
1254 
1255  /*!
1256  \brief Clears every bit in the bitvector.
1257 
1258  \param free_mem if "true" (default) bvector frees the memory,
1259  otherwise sets blocks to 0.
1260  */
1261  void clear(bool free_mem = true) BMNOEXCEPT;
1262 
1263  /*!
1264  \brief Clears every bit in the bitvector.
1265  \return *this;
1266  */
1267  bvector<Alloc>& reset() BMNOEXCEPT { clear(true); return *this; }
1268 
1269  /*!
1270  \brief Flips bit n
1271  \return *this
1272  */
1273  bvector<Alloc>& flip(size_type n) { this->inc(n); return *this; }
1274 
1275  /*!
1276  \brief Flips all bits
1277  \return *this
1278  @sa invert
1279  */
1280  bvector<Alloc>& flip() { return invert(); }
1281 
1282  //@}
1283  // --------------------------------------------------------------------
1284 
1285 
1286  /*! Function erturns insert iterator for this bitvector */
1287  insert_iterator inserter() { return insert_iterator(*this); }
1288 
1289  // --------------------------------------------------------------------
1290  /*! @name Size and capacity
1291  By default bvector is dynamically sized, manual control methods
1292  available
1293  */
1294  //@{
1295 
1296  /** \brief Returns bvector's capacity (number of bits it can store) */
1297  //size_type capacity() const { return blockman_.capacity(); }
1298 
1299  /*! \brief return current size of the vector (bits) */
1301 
1302  /*!
1303  \brief Change size of the bvector
1304  \param new_size - new size in bits
1305  */
1306  void resize(size_type new_size);
1307 
1308  //@}
1309  // --------------------------------------------------------------------
1310 
1311  /*! @name Population counting, ranks, ranges and intervals
1312  */
1313  //@{
1314 
1315  /*!
1316  \brief population count (count of ON bits)
1317  \sa count_range
1318  \return Total number of bits ON
1319  */
1321 
1322  /*! \brief Computes bitcount values for all bvector blocks
1323  \param arr - pointer on array of block bit counts
1324  \return Index of the last block counted.
1325  This number +1 gives you number of arr elements initialized during the
1326  function call.
1327  */
1329 
1330 
1331  /*!
1332  \brief Returns count of 1 bits in the given range [left..right]
1333  Uses rank-select index to accelerate the search
1334  \param left - index of first bit start counting from
1335  \param right - index of last bit
1336  \param rs_idx - block count structure to accelerate search
1337  \sa build_rs_index
1338 
1339  \return population count in the diapason
1340  */
1342  size_type right,
1344 
1345  /*!
1346  \brief Returns count of 1 bits in the given range [left..right]
1347 
1348  \param left - index of first bit start counting from
1349  \param right - index of last bit
1350 
1351  \return population count in the diapason
1352  @sa count_range_no_check
1353  */
1355 
1356  /*!
1357  Returns count of 1 bits in the given range [left..right]
1358  Function expects that caller guarantees that left < right
1359 
1360  @sa count_range
1361  */
1363 
1364 
1365  /*!
1366  Returns count of 1 bits in the given range [left..right]
1367  Function expects that caller guarantees that left < right
1368 
1369  @sa count_range
1370  */
1372  size_type right,
1374 
1375  /*!
1376  \brief Returns true if all bits in the range are 1s (saturated interval)
1377  Function uses closed interval [left, right]
1378 
1379  \param left - index of first bit start checking
1380  \param right - index of last bit
1381 
1382  \return true if all bits are 1, false otherwise
1383  @sa any_range, count_range
1384  */
1386 
1387  /*!
1388  \brief Returns true if any bits in the range are 1s (non-empty interval)
1389  Function uses closed interval [left, right]
1390 
1391  \param left - index of first bit start checking
1392  \param right - index of last bit
1393 
1394  \return true if at least 1 bits is set
1395  @sa is_all_one_range, count_range
1396  */
1398 
1399 
1400  /*! \brief compute running total of all blocks in bit vector (rank-select index)
1401  \param rs_idx - [out] pointer to index / count structure
1402  \param bv_blocks - [out] list of block ids in the vector (internal, optional)
1403  Function will fill full array of running totals
1404  \sa count_to, select, find_rank
1405  */
1406  void build_rs_index(rs_index_type* rs_idx, bvector<Alloc>* bv_blocks=0) const;
1407 
1408  /*!
1409  \brief Returns count of 1 bits (population) in [0..right] range.
1410 
1411  This operation is also known as rank of bit N.
1412 
1413  \param n - index of bit to rank
1414  \param rs_idx - rank-select to accelerate search
1415  should be prepared using build_rs_index
1416  \return population count in the range [0..n]
1417  \sa build_rs_index
1418  \sa count_to_test, select, rank, rank_corrected
1419  */
1422 
1423 
1424  /*!
1425  \brief Returns rank of specified bit position (same as count_to())
1426 
1427  \param n - index of bit to rank
1428  \param rs_idx - rank-select index
1429  \return population count in the range [0..n]
1430  \sa build_rs_index
1431  \sa count_to_test, select, rank, rank_corrected
1432  */
1435  { return count_to(n, rs_idx); }
1436 
1437  /*!
1438  \brief Returns rank corrceted by the requested border value (as -1)
1439 
1440  This is rank function (bit-count) minus value of bit 'n'
1441  if bit-n is true function returns rank()-1 if false returns rank()
1442  faster than rank() + test().
1443 
1444 
1445  \param n - index of bit to rank
1446  \param rs_idx - rank-select index
1447  \return population count in the range [0..n] corrected as -1 by the value of n
1448  \sa build_rs_index
1449  \sa count_to_test, select, rank
1450  */
1452  const rs_index_type& rs_idx) const BMNOEXCEPT;
1453 
1454  /*!
1455  \brief popcount in [0..right] range if test(right) == true
1456 
1457  This is conditional rank operation, which is faster than test()
1458  plus count_to()
1459 
1460  \param n - index of bit to test and rank
1461  \param rs_idx - rank-select index
1462  (block count structure to accelerate search)
1463  should be prepared using build_rs_index()
1464 
1465  \return population count in the diapason or 0 if right bit test failed
1466 
1467  \sa build_rs_index
1468  \sa count_to
1469  */
1470  size_type
1472  const rs_index_type& rs_idx) const BMNOEXCEPT;
1473 
1474 
1475  /*! Recalculate bitcount (deprecated)
1476  */
1478 
1479  /*!
1480  Disables count cache. (deprecated).
1481  */
1483 
1484  //@}
1485 
1486  // --------------------------------------------------------------------
1487  /*! @name Bit access (read-only) */
1488  //@{
1489 
1490  /*!
1491  \brief returns true if bit n is set and false is bit n is 0.
1492  \param n - Index of the bit to check.
1493  \return Bit value (1 or 0)
1494  */
1496 
1497  /*!
1498  \brief returns true if bit n is set and false is bit n is 0.
1499  \param n - Index of the bit to check.
1500  \return Bit value (1 or 0)
1501  */
1502  bool test(size_type n) const BMNOEXCEPT { return get_bit(n); }
1503 
1504  //@}
1505 
1506  // --------------------------------------------------------------------
1507  /*! @name bit-shift and insert operations */
1508  //@{
1509 
1510  /*!
1511  \brief Shift right by 1 bit, fill with zero return carry out
1512  \return Carry over bit value (1 or 0)
1513  */
1514  bool shift_right();
1515 
1516  /*!
1517  \brief Shift left by 1 bit, fill with zero return carry out
1518  \return Carry over bit value (1 or 0)
1519  */
1520  bool shift_left();
1521 
1522  /*!
1523  \brief Insert bit into specified position
1524  All the vector content after insert position is shifted right.
1525 
1526  \param n - index of the bit to insert
1527  \param value - insert value
1528 
1529  \return Carry over bit value (1 or 0)
1530  */
1531  bool insert(size_type n, bool value);
1532 
1533  /*!
1534  \brief Erase bit in the specified position
1535  All the vector content after erase position is shifted left.
1536 
1537  \param n - index of the bit to insert
1538  */
1540 
1541  //@}
1542 
1543  // --------------------------------------------------------------------
1544  /*! @name Check for empty-ness of container */
1545  //@{
1546 
1547  /*!
1548  \brief Returns true if any bits in this bitset are set, and otherwise returns false.
1549  \return true if any bit is set
1550  */
1552 
1553  /*!
1554  \brief Returns true if no bits are set, otherwise returns false.
1555  */
1556  bool none() const BMNOEXCEPT { return !any(); }
1557 
1558  /**
1559  \brief Returns true if the set is empty (no bits are set, otherwise returns false)
1560  Please note that this is NOT a size check, it is an empty SET check (absense of 1s)
1561  */
1562  bool empty() const BMNOEXCEPT { return !any(); }
1563 
1564  //@}
1565  // --------------------------------------------------------------------
1566 
1567  /*! @name Scan and find bits and indexes */
1568  //@{
1569 
1570  /*!
1571  \fn bool bvector::find(bm::id_t& pos) const
1572  \brief Finds index of first 1 bit
1573  \param pos - [out] index of the found 1 bit
1574  \return true if search returned result
1575  \sa get_first, get_next, extract_next, find_reverse, find_first_mismatch
1576  */
1577  bool find(size_type& pos) const BMNOEXCEPT;
1578 
1579  /*!
1580  \fn bool bvector::find(bm::id_t from, bm::id_t& pos) const
1581  \brief Find index of 1 bit starting from position
1582  \param from - position to start search from, please note that if bit at from position
1583  is set then it will be found, function uses closed interval [from...
1584  \param pos - [out] index of the found 1 bit
1585  \return true if search returned result
1586  \sa get_first, get_next, extract_next, find_reverse, find_first_mismatch
1587  */
1588  bool find(size_type from, size_type& pos) const BMNOEXCEPT;
1589 
1590 
1591  /*!
1592  \fn bm::id_t bvector::get_first() const
1593  \brief find first 1 bit in vector.
1594  Function may return 0 and this requires an extra check if bit 0 is
1595  actually set or bit-vector is empty
1596 
1597  \return Index of the first 1 bit, may return 0
1598  \sa get_next, find, extract_next, find_reverse
1599  */
1601 
1602  /*!
1603  \fn bm::id_t bvector::get_next(bm::id_t prev) const
1604  \brief Finds the number of the next bit ON.
1605  \param prev - Index of the previously found bit.
1606  \return Index of the next bit which is ON or 0 if not found.
1607  \sa get_first, find, extract_next, find_reverse
1608  */
1610  { return (++prev == bm::id_max) ? 0 : check_or_next(prev); }
1611 
1612  /*!
1613  \fn bm::id_t bvector::extract_next(bm::id_t prev)
1614  \brief Finds the number of the next bit ON and sets it to 0.
1615  \param prev - Index of the previously found bit.
1616  \return Index of the next bit which is ON or 0 if not found.
1617  \sa get_first, get_next, find_reverse
1618  */
1620  {
1621  return (++prev == bm::id_max) ? 0 : check_or_next_extract(prev);
1622  }
1623 
1624  /*!
1625  \brief Finds last index of 1 bit
1626  \param pos - [out] index of the last found 1 bit
1627  \return true if search returned result
1628  \sa get_first, get_next, extract_next,
1629  \sa find, find_first_mismatch, find_range
1630  */
1632 
1633  /*!
1634  \brief Reverse finds next(prev) index of 1 bit
1635  \param from - index to search from
1636  \param pos - [out] found position index
1637  (undefined if method returns false)
1638  \return true if search returned result
1639  \sa get_first, get_next, extract_next,
1640  \sa find, find_first_mismatch, find_range
1641  */
1642  bool find_reverse(size_type from, size_type& pos) const BMNOEXCEPT;
1643 
1644  /*!
1645  \brief Finds dynamic range of bit-vector [first, last]
1646  \param first - index of the first found 1 bit
1647  \param last - index of the last found 1 bit
1648  \return true if search returned result
1649  \sa get_first, get_next, extract_next, find, find_reverse
1650  */
1652 
1653  /*!
1654  \brief Find bit-vector position for the specified rank(bitcount)
1655 
1656  Rank based search, counts number of 1s from specified position until
1657  finds the ranked position relative to start from position.
1658  In other words: range population count between from and pos == rank.
1659 
1660  \param rank - rank to find (bitcount)
1661  \param from - start positioon for rank search
1662  \param pos - position with speciefied rank (relative to from position)
1663 
1664  \return true if requested rank was found
1665  */
1667  size_type& pos) const BMNOEXCEPT;
1668 
1669  /*!
1670  \brief Find bit-vector position for the specified rank(bitcount)
1671 
1672  Rank based search, counts number of 1s from specified position until
1673  finds the ranked position relative to start from position.
1674  In other words: range population count between from and pos == rank.
1675 
1676  \param rank - rank to find (bitcount)
1677  \param from - start positioon for rank search
1678  \param pos - position with speciefied rank (relative to from position)
1679  \param rs_idx - rank-select index to accelarate search
1680  (should be prepared using build_rs_index)
1681 
1682  \sa build_rs_index, select
1683 
1684  \return true if requested rank was found
1685  */
1687  const rs_index_type& rs_idx) const BMNOEXCEPT;
1688 
1689  /*!
1690  \brief select bit-vector position for the specified rank(bitcount)
1691 
1692  Rank based search, counts number of 1s from specified position until
1693  finds the ranked position relative to start from position.
1694  Uses
1695  In other words: range population count between from and pos == rank.
1696 
1697  \param rank - rank to find (bitcount)
1698  \param pos - position with speciefied rank (relative to from position) [out]
1699  \param rs_idx - block count structure to accelerate rank search
1700 
1701  \sa running_count_blocks, find_rank
1702 
1703  \return true if requested rank was found
1704  */
1706  const rs_index_type& rs_idx) const BMNOEXCEPT;
1707 
1708  //@}
1709 
1710 
1711  // --------------------------------------------------------------------
1712  /*! @name Algebra of Sets operations */
1713  //@{
1714 
1715  /*!
1716  \brief 3-operand OR : this := bv1 OR bv2
1717  \param bv1 - Argument vector 1
1718  \param bv2 - Argument vector 2
1719  \param opt_mode - optimization compression
1720  (when it is performed on the fly it is faster than a separate
1721  call to optimize()
1722  @sa optimize, bit_or
1723  */
1725  const bm::bvector<Alloc>& bv2,
1726  typename bm::bvector<Alloc>::optmode opt_mode=opt_none);
1727 
1728  /*!
1729  \brief 3-operand XOR : this := bv1 XOR bv2
1730  \param bv1 - Argument vector 1
1731  \param bv2 - Argument vector 2
1732  \param opt_mode - optimization compression
1733  (when it is performed on the fly it is faster than a separate
1734  call to optimize()
1735  @sa optimize, bit_xor
1736  */
1738  const bm::bvector<Alloc>& bv2,
1739  typename bm::bvector<Alloc>::optmode opt_mode=opt_none);
1740 
1741  /*!
1742  \brief 3-operand AND : this := bv1 AND bv2
1743  \param bv1 - Argument vector 1
1744  \param bv2 - Argument vector 2
1745  \param opt_mode - optimization compression
1746  (when it is performed on the fly it is faster than a separate
1747  call to optimize()
1748  @sa optimize, bit_and
1749  */
1751  const bm::bvector<Alloc>& bv2,
1752  typename bm::bvector<Alloc>::optmode opt_mode=opt_none);
1753 
1754 
1755  /*!
1756  \brief 3-operand AND where result is ORed into the terget vector : this |= bv1 AND bv2
1757  TARGET := TARGET OR (BV1 AND BV2)
1758 
1759  \param bv1 - Argument vector 1
1760  \param bv2 - Argument vector 2
1761  \param opt_mode - optimization compression
1762  (when it is performed on the fly it is faster than a separate
1763  call to optimize()
1764  @sa optimize, bit_and
1765  */
1767  const bm::bvector<Alloc>& bv2,
1768  typename bm::bvector<Alloc>::optmode opt_mode=opt_none);
1769 
1770 
1771  /*!
1772  \brief 3-operand SUB : this := bv1 MINUS bv2
1773  SUBtraction is also known as AND NOT
1774  \param bv1 - Argument vector 1
1775  \param bv2 - Argument vector 2
1776  \param opt_mode - optimization compression
1777  (when it is performed on the fly it is faster than a separate
1778  call to optimize()
1779  @sa optimize, bit_sub
1780  */
1782  const bm::bvector<Alloc>& bv2,
1783  typename bm::bvector<Alloc>::optmode opt_mode=opt_none);
1784 
1785 
1786  /*!
1787  \brief 2 operand logical OR
1788  \param bv - Argument vector.
1789  */
1791  {
1792  BM_ASSERT(!is_ro());
1794  return *this;
1795  }
1796 
1797  /*!
1798  \brief 2 operand logical AND
1799  \param bv - argument vector
1800  \param opt_mode - set an immediate optimization
1801  */
1803  optmode opt_mode = opt_none)
1804  {
1805  BM_ASSERT(!is_ro());
1806  combine_operation_and(bv, opt_mode);
1807  return *this;
1808  }
1809 
1810  /*!
1811  \brief 2 operand logical XOR
1812  \param bv - argument vector.
1813  */
1815  {
1816  BM_ASSERT(!is_ro());
1818  return *this;
1819  }
1820 
1821  /*!
1822  \brief 2 operand logical SUB(AND NOT). Also known as MINUS.
1823  \param bv - argument vector.
1824  */
1826  {
1827  BM_ASSERT(!is_ro());
1829  return *this;
1830  }
1831 
1832  /*!
1833  \brief Invert/NEG all bits
1834  It should be noted, invert is affected by size()
1835  if size is set - it only inverts [0..size-1] bits
1836  */
1838 
1839 
1840  /*! \brief perform a set-algebra operation by operation code
1841  */
1843  bm::operation opcode);
1844 
1845  /*! \brief perform a set-algebra operation OR
1846  */
1848 
1849  /*! \brief perform a set-algebra operation AND
1850  */
1852  optmode opt_mode);
1853 
1854  /*! \brief perform a set-algebra operation MINUS (AND NOT)
1855  */
1857 
1858  /*! \brief perform a set-algebra operation XOR
1859  */
1861 
1862  // @}
1863 
1864  // --------------------------------------------------------------------
1865  /*! @name Iterator-traversal methods */
1866  //@{
1867 
1868  /**
1869  \brief Returns enumerator pointing on the first non-zero bit.
1870  */
1871  enumerator first() const { return get_enumerator(0); }
1872 
1873  /**
1874  \fn bvector::enumerator bvector::end() const
1875  \brief Returns enumerator pointing on the next bit after the last.
1876  */
1877  enumerator end() const
1878  { return typename bvector<Alloc>::enumerator(this); }
1879 
1880  /**
1881  \brief Returns enumerator pointing on specified or the next available bit.
1882  */
1884  { return typename bvector<Alloc>::enumerator(this, pos); }
1885 
1886  //@}
1887 
1888  // --------------------------------------------------------------------
1889  /*! @name Memory management and compression */
1890 
1891  //@{
1892 
1893  /*!
1894  @brief Calculates bitvector statistics.
1895 
1896  @param st - pointer on statistics structure to be filled in.
1897 
1898  Function fills statistics structure containing information about how
1899  this vector uses memory and estimation of max. amount of memory
1900  bvector needs to serialize itself.
1901 
1902  @sa statistics
1903  */
1905 
1906 
1907  /*!
1908  \brief Sets new blocks allocation strategy.
1909  \param strat - Strategy code 0 - bitblocks allocation only.
1910  1 - Blocks mutation mode (adaptive algorithm)
1911  */
1913 
1914  /*!
1915  \brief Returns blocks allocation strategy.
1916  \return - Strategy code 0 - bitblocks allocation only.
1917  1 - Blocks mutation mode (adaptive algorithm)
1918  \sa set_new_blocks_strat
1919  */
1921  { return new_blocks_strat_; }
1922 
1923  /*!
1924  \brief Optimize memory bitvector's memory allocation.
1925 
1926  Function analyze all blocks in the bitvector, compresses blocks
1927  with a regular structure, frees some memory. This function is recommended
1928  after a bulk modification of the bitvector using set_bit, clear_bit or
1929  logical operations.
1930 
1931  Optionally function can calculate vector post optimization statistics
1932 
1933  @param temp_block - externally allocated temp buffer for optimization
1934  BM_DECLARE_TEMP_BLOCK(tb)
1935  if NULL - it will allocated (and de-allocated upon exit)
1936  @param opt_mode - optimization level
1937  @param stat - statistics of memory consumption and serialization
1938  stat can also be computed by calc_stat() but it would require an extra pass
1939 
1940  @sa optmode, optimize_gap_size, calc_stat
1941  */
1942  void optimize(bm::word_t* temp_block = 0,
1943  optmode opt_mode = opt_compress,
1944  statistics* stat = 0);
1945 
1946  /*!
1947  Run partial vector optimization for the area [left..right] (specified in bit coordinates)
1948 
1949  @param left - bit index to optimize from (approximate, rounded up to a nearest block)
1950  @param right - bit index to optimize to
1951  Please note that left and right define range in bit coordinates but later rounded to blocks
1952  @param temp_block - external scratch memory (MUST be pre-allocated)
1953  @param opt_mode - optimization level
1954 
1955  @sa optimize
1956  */
1958  size_type left, size_type right,
1959  bm::word_t* temp_block,
1960  optmode opt_mode = opt_compress);
1961 
1962  /*!
1963  \brief Optimize sizes of GAP blocks
1964 
1965  This method runs an analysis to find optimal GAP levels for the
1966  specific vector. Current GAP compression algorithm uses several fixed
1967  GAP sizes. By default bvector uses some reasonable preset.
1968  */
1970 
1971  /*!
1972  @brief Sets new GAP lengths table. All GAP blocks will be reallocated
1973  to match the new scheme.
1974 
1975  @param glevel_len - pointer on C-style array keeping GAP block sizes.
1976  */
1977  void set_gap_levels(const gap_word_t* glevel_len);
1978 
1979  /**
1980  Return true if bvector is initialized at all
1981  @internal
1982  */
1984 
1985  /**
1986  Calculate blocks digest vector (for diagnostics purposes)
1987  1 is added if NB is a real, allocated block
1988 
1989  @param bv_blocks - [out] bvector of blocks statistics
1990  @internal
1991  */
1992  void fill_alloc_digest(bvector<Alloc>& bv_blocks) const;
1993 
1994  //@}
1995 
1996  // --------------------------------------------------------------------
1997 
1998  /*! @name Comparison */
1999  //@{
2000 
2001  /*!
2002  \brief Lexicographical comparison with a bitvector.
2003 
2004  Function compares current bitvector with the provided argument
2005  bit by bit and returns -1 if this bitvector less than the argument,
2006  1 - greater, 0 - equal
2007 
2008  @return 0 if this == arg, -1 if this < arg, 1 if this > arg
2009  @sa find_first_mismatch
2010  */
2012 
2013  /*!
2014  \brief Equal comparison with an agr bit-vector
2015  @return true if vectors are identical
2016  */
2018  {
2019  size_type pos;
2020  bool found = find_first_mismatch(bvect, pos);
2021  return !found;
2022  }
2023 
2024  /*!
2025  \brief Find index of first bit different between this and the agr vector
2026 
2027  @param bvect - argumnet vector to compare with
2028  @param pos - [out] position of the first difference
2029  @param search_to - search limiter [0..to] to avoid overscan
2030  (default: unlimited to the vectors end)
2031 
2032  @return true if didfference found, false - both vectors are equivalent
2033  @sa compare
2034  */
2036  size_type& pos,
2037  size_type search_to = bm::id_max
2038  ) const BMNOEXCEPT;
2039 
2040  //@}
2041 
2042  // --------------------------------------------------------------------
2043  /*! @name Open internals */
2044  //@{
2045 
2046  /*!
2047  @internal
2048  */
2050  const bm::word_t* arg_blk,
2051  bool arg_gap,
2052  bm::operation opcode);
2053  /**
2054  \brief get access to memory manager (internal)
2055  Use only if you are BitMagic library
2056  @internal
2057  */
2059  { return blockman_; }
2060 
2061  /**
2062  \brief get access to memory manager (internal)
2063  Use only if you are BitMagic library
2064  @internal
2065  */
2067  { return blockman_; }
2068 
2069  /**
2070  Import integers (set bits). (Fast, no checks).
2071  @internal
2072  */
2073  void import(const size_type* ids, size_type ids_size,
2074  bm::sort_order sorted_idx);
2075 
2076  /**
2077  Import sorted integers (set bits). (Fast, no checks).
2078  @internal
2079  */
2080  void import_sorted(const size_type* ids,
2081  const size_type ids_size, bool opt_flag);
2082 
2083  /**
2084  \brief Set range without validity/bounds checking
2085  */
2087  size_type right);
2088  /**
2089  \brief Clear range without validity/bounds checking
2090  */
2092  size_type right);
2093 
2094 
2095  //@}
2096 
2097  static void throw_bad_alloc();
2098 
2099 protected:
2100  /**
2101  Syncronize size if it got extended due to bulk import
2102  @internal
2103  */
2104  void sync_size();
2105 
2106 
2107  void import_block(const size_type* ids,
2108  block_idx_type nblock, size_type start, size_type stop);
2109 
2110 
2111 
2113 
2114  /// set bit in GAP block with GAP block length control
2116  bool val, block_idx_type nblock, unsigned nbit);
2117 
2118  /// set bit in GAP block with GAP block length control
2120  bool val, block_idx_type nblock,
2121  unsigned nbit);
2122 
2123  /// check if specified bit is 1, and set it to 0
2124  /// if specified bit is 0, scan for the next 1 and returns it
2125  /// if no 1 found returns 0
2127 
2128 
2129  /**
2130  \brief AND specified bit without checking preconditions (size, etc)
2131  */
2132  bool and_bit_no_check(size_type n, bool val);
2133 
2134  bool set_bit_conditional_impl(size_type n, bool val, bool condition);
2135 
2136 
2138  bool gap,
2139  bm::word_t* blk,
2140  const bm::word_t* arg_blk,
2141  bool arg_gap,
2142  bm::operation opcode);
2143 
2144  /**
2145  @return true if block optimization may be needed
2146  */
2148  unsigned j,
2149  const bm::word_t* arg_blk1,
2150  const bm::word_t* arg_blk2);
2152  unsigned j,
2153  const bm::word_t* arg_blk1,
2154  const bm::word_t* arg_blk2);
2156  unsigned j,
2157  const bm::word_t* arg_blk1,
2158  const bm::word_t* arg_blk2);
2159 
2161  unsigned j,
2162  const bm::word_t* arg_blk1,
2163  const bm::word_t* arg_blk2);
2165  unsigned j,
2166  const bm::word_t* arg_blk1,
2167  const bm::word_t* arg_blk2);
2168 
2169 
2171  unsigned j,
2172  bm::word_t* blk,
2173  const bm::word_t* arg_blk);
2174 
2176  unsigned j,
2177  bm::word_t* blk,
2178  const bm::word_t* arg_blk);
2179 
2181  unsigned j,
2182  bm::word_t* blk,
2183  const bm::word_t* arg_blk);
2184 
2186  unsigned j,
2187  bm::word_t* blk,
2188  const bm::word_t* arg_blk);
2189 
2191  size_type left,
2192  size_type right);
2193 
2194 private:
2195  /**
2196  \brief Clear outside the range without validity/bounds checking
2197  */
2199  size_type right);
2200 
2201  /**
2202  Compute rank in bit-block using rank-select index
2203  */
2204  static
2206  block_idx_type nb,
2207  unsigned nbit_right,
2208  const rs_index_type& rs_idx) BMNOEXCEPT;
2209  /**
2210  Compute rank in GAP block using rank-select index
2211  @param test_set - request to test nbit_right before computing count
2212  (returns 0 if not set)
2213  */
2214  static
2216  block_idx_type nb,
2217  unsigned nbit_right,
2218  const rs_index_type& rs_idx,
2219  bool test_set = false) BMNOEXCEPT;
2220  /**
2221  Return value of first bit in the block
2222  */
2224 
2225 private:
2226  blocks_manager_type blockman_; //!< bitblocks manager
2227  strategy new_blocks_strat_; //!< block allocation strategy
2228  size_type size_; //!< size in bits
2229 };
2230 
2231 
2232 //---------------------------------------------------------------------
2233 
2234 template<class Alloc>
2235 inline bvector<Alloc> operator& (const bvector<Alloc>& bv1,
2236  const bvector<Alloc>& bv2)
2237 {
2238  bvector<Alloc> ret;
2239  ret.bit_and(bv1, bv2, bvector<Alloc>::opt_none);
2240  return ret;
2241 }
2242 
2243 //---------------------------------------------------------------------
2244 
2245 template<class Alloc>
2247  const bvector<Alloc>& bv2)
2248 {
2249  bvector<Alloc> ret;
2250  ret.bit_or(bv1, bv2, bvector<Alloc>::opt_none);
2251  return ret;
2252 }
2253 
2254 //---------------------------------------------------------------------
2255 
2256 template<class Alloc>
2258  const bvector<Alloc>& bv2)
2259 {
2260  bvector<Alloc> ret;
2261  ret.bit_xor(bv1, bv2, bvector<Alloc>::opt_none);
2262  return ret;
2263 }
2264 
2265 //---------------------------------------------------------------------
2266 
2267 template<class Alloc>
2269  const bvector<Alloc>& bv2)
2270 {
2271  bvector<Alloc> ret;
2272  ret.bit_sub(bv1, bv2, bvector<Alloc>::opt_none);
2273  return ret;
2274 }
2275 
2276 
2277 // -----------------------------------------------------------------------
2278 
2279 template<typename Alloc>
2281 {
2282  BM_ASSERT(!is_ro());
2283  blockman_.init_tree();
2284 }
2285 
2286 // -----------------------------------------------------------------------
2287 
2288 template<typename Alloc>
2289 void bvector<Alloc>::init(unsigned top_size, bool alloc_subs)
2290 {
2291  BM_ASSERT(!is_ro());
2292  if (!blockman_.is_init())
2293  blockman_.init_tree(top_size);
2294  if (alloc_subs)
2295  for (unsigned nb = 0; nb < top_size; ++nb)
2297 }
2298 
2299 
2300 // -----------------------------------------------------------------------
2301 
2302 template<typename Alloc>
2304 {
2305  if (this != &bvect)
2306  {
2308  switch (is_final)
2309  {
2311  if (bvect.is_ro())
2312  {
2314  size_ = bvect.size();
2315  }
2316  else
2317  {
2319  resize(bvect.size());
2320  }
2321  break;
2324  size_ = bvect.size();
2325  break;
2328  resize(bvect.size());
2329  break;
2330  default:
2331  BM_ASSERT(0);
2332  break;
2333  } // switch
2334  }
2335 }
2336 
2337 // -----------------------------------------------------------------------
2338 
2339 template<typename Alloc>
2341 {
2342  if (this != &bvect)
2343  {
2345  size_ = bvect.size_;
2347  }
2348 }
2349 
2350 //---------------------------------------------------------------------
2351 
2352 template<class Alloc>
2354 {
2355  BM_ASSERT(!is_ro());
2356  if (!blockman_.is_init())
2357  return; // nothing to do
2358 
2359  if (right < left)
2360  bm::xor_swap(left, right);
2361 
2362  keep_range_no_check(left, right);
2363 }
2364 
2365 // -----------------------------------------------------------------------
2366 
2367 template<typename Alloc>
2369  size_type right,
2370  bool value)
2371 {
2372  BM_ASSERT(!is_ro());
2373 
2374  if (!blockman_.is_init() && !value)
2375  return *this; // nothing to do
2376 
2377  if (right < left)
2378  return set_range(right, left, value);
2379 
2380  BM_ASSERT_THROW(right < bm::id_max, BM_ERR_RANGE);
2381  if (right >= size_) // this vect shorter than the arg.
2382  {
2383  size_type new_size = (right == bm::id_max) ? bm::id_max : right + 1;
2384  resize(new_size);
2385  }
2386 
2387  BM_ASSERT(left <= right);
2388  BM_ASSERT(left < size_);
2389 
2390  if (value)
2391  set_range_no_check(left, right);
2392  else
2393  clear_range_no_check(left, right);
2394 
2395  return *this;
2396 }
2397 
2398 // -----------------------------------------------------------------------
2399 
2400 template<typename Alloc>
2402 {
2403  if (!blockman_.is_init())
2404  return 0;
2405 
2406  word_t*** blk_root = blockman_.top_blocks_root();
2407  BM_ASSERT(blk_root);
2408 
2409  size_type cnt = 0;
2410  unsigned top_blocks = blockman_.top_block_size();
2411  for (unsigned i = 0; i < top_blocks; ++i)
2412  {
2413  bm::word_t** blk_blk = blk_root[i];
2414  if (!blk_blk)
2415  {
2416  ++i;
2417  bool found = bm::find_not_null_ptr(blk_root, i, top_blocks, &i);
2418  if (!found)
2419  break;
2420  blk_blk = blk_root[i];
2421  BM_ASSERT(blk_blk);
2422  if (!blk_blk)
2423  break;
2424  }
2425  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
2426  {
2428  continue;
2429  }
2430  unsigned j = 0;
2431  do
2432  {
2433  if (blk_blk[j])
2434  cnt += blockman_.block_bitcount(blk_blk[j]);
2435  if (blk_blk[j+1])
2436  cnt += blockman_.block_bitcount(blk_blk[j+1]);
2437  if (blk_blk[j+2])
2438  cnt += blockman_.block_bitcount(blk_blk[j+2]);
2439  if (blk_blk[j+3])
2440  cnt += blockman_.block_bitcount(blk_blk[j+3]);
2441  j += 4;
2442  } while (j < bm::set_sub_array_size);
2443 
2444  } // for i
2445  return cnt;
2446 }
2447 
2448 // -----------------------------------------------------------------------
2449 
2450 template<typename Alloc>
2452 {
2453  word_t*** blk_root = blockman_.top_blocks_root();
2454  if (!blk_root)
2455  return false;
2457  return for_each_nzblock_if(blk_root, blockman_.top_block_size(), func);
2458 }
2459 
2460 // -----------------------------------------------------------------------
2461 
2462 template<typename Alloc>
2464 {
2465  BM_ASSERT(!is_ro());
2466 
2467  if (size_ == new_size) return; // nothing to do
2468  if (size_ < new_size) // size grows
2469  {
2470  if (!blockman_.is_init())
2471  blockman_.init_tree();
2472 
2473  blockman_.reserve(new_size);
2474  size_ = new_size;
2475  }
2476  else // shrink
2477  {
2478  set_range(new_size, size_ - 1, false); // clear the tail
2479  size_ = new_size;
2480  }
2481 }
2482 
2483 // -----------------------------------------------------------------------
2484 
2485 template<typename Alloc>
2487 {
2488  BM_ASSERT(!is_ro());
2489 
2490  if (size_ >= bm::id_max)
2491  return;
2493  bool found = find_reverse(last);
2494  if (found && last >= size_)
2495  resize(last+1);
2496 }
2497 
2498 // -----------------------------------------------------------------------
2499 
2500 template<typename Alloc>
2502  bvector<Alloc>* bv_blocks) const
2503 {
2504  BM_ASSERT(rs_idx);
2505  if (bv_blocks)
2506  {
2507  bv_blocks->clear();
2508  bv_blocks->init();
2509  }
2510 
2511  unsigned bcount[bm::set_sub_array_size];
2513 
2514  rs_idx->init();
2515  if (!blockman_.is_init())
2516  return;
2517 
2518  // resize the RS index to fit the vector
2519  //
2520  size_type last_bit;
2521  bool found = find_reverse(last_bit);
2522  if (!found)
2523  return;
2524  block_idx_type nb = (last_bit >> bm::set_block_shift);
2525  unsigned i0, j0;
2526  bm::get_block_coord(nb, i0, j0);
2527 
2528  unsigned real_top_blocks = blockman_.find_real_top_blocks();
2529  unsigned max_top_blocks = blockman_.find_max_top_blocks();
2530  if (nb < (max_top_blocks * bm::set_sub_array_size))
2531  nb = (max_top_blocks * bm::set_sub_array_size);
2532  rs_idx->set_total(nb + 1);
2533  rs_idx->resize(nb + 1);
2534  rs_idx->resize_effective_super_blocks(real_top_blocks);
2535 
2536  // index construction
2537  //
2538  BM_ASSERT(max_top_blocks <= blockman_.top_block_size());
2539  bm::word_t*** blk_root = blockman_.top_blocks_root();
2540  for (unsigned i = 0; i < max_top_blocks; ++i)
2541  {
2542  bm::word_t** blk_blk = blk_root[i];
2543  if (!blk_blk)
2544  {
2545  rs_idx->set_null_super_block(i);
2546  continue;
2547  }
2548  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
2549  {
2550  rs_idx->set_full_super_block(i);
2551  if (bv_blocks)
2552  {
2553  size_type nb_from = i * bm::set_sub_array_size;
2554  size_type nb_to = nb_from + bm::set_sub_array_size - 1;
2555  bv_blocks->set_range_no_check(nb_from, nb_to);
2556  }
2557  continue;
2558  }
2559 
2560  unsigned j = 0;
2561  do
2562  {
2563  const bm::word_t* block = blk_blk[j];
2564  if (!block)
2565  {
2566  bcount[j] = 0; sub_count[j] = 0;
2567  continue;
2568  }
2569  unsigned local_first, local_second, local_third;
2570  bm::id64_t aux0, aux1; // aux infomation to encode
2571  if (BM_IS_GAP(block))
2572  {
2573  const bm::gap_word_t* const gap_block = BMGAP_PTR(block);
2574  local_first =
2576  local_second =
2577  bm::gap_bit_count_range(gap_block,
2579  bm::rs3_border1);
2580  local_third =
2581  bm::gap_bit_count_range(gap_block,
2584 
2585  // for GAP block calculate borderline positions in GAP
2586  // and value (0|1), save to AUX
2587  //
2588  unsigned is_set;
2589  aux0 = bm::gap_bfind(gap_block, rs3_border0+1, &is_set);
2590  aux0 <<= 1;
2591  if (is_set) aux0 |= 1;
2592  aux1 = bm::gap_bfind(gap_block, rs3_border1+1, &is_set);
2593  aux1 <<= 1;
2594  if (is_set) aux1 |= 1;
2595  }
2596  else
2597  {
2598  block = BLOCK_ADDR_SAN(block); // TODO: optimize FULL
2599  local_first =
2601  local_second =
2603  bm::rs3_border0+1,
2604  bm::rs3_border1);
2605  local_third =
2607  bm::rs3_border1+1,
2608  bm::gap_max_bits-1);
2609  // compute inetrmediate points
2612  }
2613  unsigned cnt = local_first + local_second + local_third;
2615 
2616  bcount[j] = cnt;
2617  if (bv_blocks && cnt)
2618  bv_blocks->set_bit_no_check(i * bm::set_sub_array_size + j);
2619 
2620  BM_ASSERT(cnt >= local_first + local_second);
2621  sub_count[j] = bm::id64_t(local_first | (local_second << 16)) |
2622  (aux0 << 32) | (aux1 << 48);
2623 
2624  } while (++j < bm::set_sub_array_size);
2625 
2626  rs_idx->register_super_block(i, &bcount[0], &sub_count[0]);
2627 
2628  } // for i
2629 
2630 }
2631 
2632 
2633 // -----------------------------------------------------------------------
2634 
2635 template<typename Alloc>
2638 {
2639  bm::word_t*** blk_root = blockman_.top_blocks_root();
2640  if (blk_root == 0)
2641  return 0;
2643  bm::for_each_nzblock(blk_root, blockman_.top_block_size(), func);
2644  return func.last_block();
2645 }
2646 
2647 // -----------------------------------------------------------------------
2648 
2649 #define BM_BORDER_TEST(blk, idx) bool(blk[idx >> bm::set_word_shift] & (1u << (idx & bm::set_word_mask)))
2650 
2651 
2652 #if (defined(BMSSE42OPT) || defined(BMAVX2OPT) || defined(BMAVX512OPT) || \
2653  defined(BMWASMSIMDOPT) || defined(BMNEONOPT))
2654 
2655 
2656 template<typename Alloc>
2659  block_idx_type nb,
2660  unsigned nbit_right,
2661  const rs_index_type& rs_idx) BMNOEXCEPT
2662 {
2663  BM_ASSERT(IS_VALID_ADDR(block));
2664  size_type c;
2665 
2666  bm::id64_t sub = rs_idx.sub_count(nb);
2667  unsigned sub_cnt = unsigned(sub);
2668  unsigned first = sub_cnt & 0xFFFF;
2669  unsigned second = sub_cnt >> 16;
2670 
2673 
2674 
2675  {
2676  unsigned cnt, aux0(bm::gap_word_t(sub >> 32)); (void)cnt; (void)aux0;
2678  unsigned cnt1, aux1(bm::gap_word_t(sub >> 48)); (void)aux1; (void) cnt1;
2679  BM_ASSERT(aux1 == (cnt1 =bm::bit_block_calc_count_to(block, bm::rs3_border1_1)));
2680  }
2681 
2682 
2683  #if defined(BM64_SSE4) || defined(BM64_AVX2) || defined(BM64_AVX512)
2684  const unsigned cutoff_bias = rs3_half_span/8;
2685  #else
2686  const unsigned cutoff_bias = 0;
2687  #endif
2688 
2689  unsigned sub_range = rs_idx.find_sub_range(nbit_right);
2690 
2691  // evaluate 3 sub-block intervals (and sub-intervals)
2692  // |--------[0]-----*-----[1]----*-----|
2693  switch(sub_range) // sub-range rank calc
2694  {
2695  case 0:
2696  // |--x-----[0]-----------[1]----------|
2697  if (nbit_right <= rs3_border0/2 + cutoff_bias)
2698  {
2699  c = bm::bit_block_calc_count_range<true, false>(block, 0, nbit_right);
2700  }
2701  else
2702  {
2703  // |--------[x]-----------[1]----------|
2704  if (nbit_right == rs3_border0)
2705  {
2706  c = first;
2707  }
2708  else
2709  {
2710  // |------x-[0]-----------[1]----------|
2711  c = bm::bit_block_calc_count_range(block, nbit_right+1,
2712  rs3_border0);
2713  c = first - c;
2714  }
2715  }
2716  break;
2717  case 1:
2718  {
2719  // |--------[0]-x---------[1]----------|
2720  if (nbit_right <= rs3_border0_1 + cutoff_bias)
2721  {
2722  c =
2723  bm::bit_block_calc_count_range<true, false>(block,
2725  nbit_right);
2726  c += first - BM_BORDER_TEST(block, bm::rs3_border0);
2727  }
2728  else
2729  {
2730  unsigned bc_second_range = first + second;
2731  // |--------[0]-----------[x]----------|
2732  if (nbit_right == rs3_border1)
2733  {
2734  c = bc_second_range;
2735  }
2736  else // sub-range processing
2737  {
2738  // |--------[0]--------x--[1]----------|
2739  BM_ASSERT(nbit_right > bm::rs3_border0_1);
2740  unsigned d1 = nbit_right - bm::rs3_border0_1;
2741  unsigned d2 = rs3_border1 - nbit_right;
2742  if (d2 < d1)
2743  {
2744  // |--------[0]----|----x-[1]----------|
2746  nbit_right+1,
2747  rs3_border1);
2748  c = bc_second_range - c;
2749  }
2750  else
2751  {
2752  // |--------[0]----|-x----[1]----------|
2753  c = bm::bit_block_calc_count_range<true, false>(
2754  block,
2756  nbit_right);
2757  unsigned aux0 = bm::gap_word_t(sub >> 32);
2758  c += aux0;
2759  c -= BM_BORDER_TEST(block, bm::rs3_border0_1);
2760  }
2761  }
2762  }
2763  }
2764  break;
2765  case 2:
2766  {
2767  // |--------[0]-----------[1]-x---*----|
2768  if (nbit_right <= rs3_border1_1)
2769  {
2770  unsigned d1 = nbit_right - bm::rs3_border1;
2771  unsigned d2 = (rs3_border1_1 + cutoff_bias) - nbit_right;
2772  if (d1 < d2) // |--------[0]-----------[1]-x---*----|
2773  {
2774  c = bm::bit_block_calc_count_range<true, false>(block,
2776  nbit_right);
2777  c += first + second; //bc_second_range;
2778  c -= BM_BORDER_TEST(block, bm::rs3_border1);
2779  }
2780  else // |--------[0]-----------[1]---x-*----|
2781  {
2782  if (nbit_right == rs3_border1_1)
2783  {
2784  unsigned aux1 = bm::gap_word_t(sub >> 48);
2785  c = aux1;
2786  }
2787  else
2788  {
2790  nbit_right+1,
2791  rs3_border1_1);
2792  unsigned aux1 = bm::gap_word_t(sub >> 48);
2793  c = aux1 - c;
2794  }
2795  }
2796  }
2797  else
2798  {
2799  // |--------[0]-----------[1]----------x
2800  if (nbit_right == bm::gap_max_bits-1)
2801  {
2802  c = rs_idx.count(nb);
2803  }
2804  else // sub-range processing
2805  {
2806  // |--------[0]-----------[1]-------x--|
2807  BM_ASSERT(nbit_right > bm::rs3_border1_1);
2808  unsigned d1 = nbit_right - bm::rs3_border1_1;
2809  unsigned d2 = bm::gap_max_bits - nbit_right;
2810  if (d2 < d1)
2811  {
2812  // |--------[0]----------[1]----*---x-|
2814  nbit_right+1,
2815  bm::gap_max_bits-1);
2816  size_type cnt = rs_idx.count(nb);
2817  c = cnt - c;
2818  }
2819  else
2820  {
2821  // |--------[0]----------[1]----*-x---|
2822  c = bm::bit_block_calc_count_range<true, false>(block,
2824  nbit_right);
2825  unsigned aux1 = bm::gap_word_t(sub >> 48);
2826  c += aux1;
2827  c -= BM_BORDER_TEST(block, bm::rs3_border1_1);
2828  }
2829  }
2830  }
2831  }
2832  break;
2833  default:
2834  BM_ASSERT(0);
2835  c = 0;
2836  } // switch
2837 
2838  BM_ASSERT(c == bm::bit_block_calc_count_to(block, nbit_right));
2839  return c;
2840 }
2841 
2842 #else // non-SIMD version
2843 
2844 template<typename Alloc>
2847  block_idx_type nb,
2848  unsigned nbit_right,
2849  const rs_index_type& rs_idx) BMNOEXCEPT
2850 {
2851  BM_ASSERT(block);
2852 
2853  bm::id64_t sub = rs_idx.sub_count(nb);
2854  unsigned sub_cnt = unsigned(sub);
2855  unsigned first = sub_cnt & 0xFFFF;
2856  unsigned second = sub_cnt >> 16;
2857 
2860 
2861 
2862  {
2863  unsigned cnt, aux0(bm::gap_word_t(sub >> 32)); (void)cnt; (void)aux0;
2865  unsigned cnt1, aux1(bm::gap_word_t(sub >> 48)); (void)aux1; (void) cnt1;
2866  BM_ASSERT(aux1 == (cnt1 =bm::bit_block_calc_count_to(block, bm::rs3_border1_1)));
2867  }
2868 
2869  size_type c=0;
2870  unsigned sub_choice =
2871  bm::get_nibble(bm::rs_intervals<true>::_c._lut, nbit_right);
2872 
2873  switch(sub_choice)
2874  {
2875  case 0:
2876  c = bm::bit_block_calc_count_range<true, false>(block, 0, nbit_right);
2877  break;
2878  case 1:
2879  c = first;
2880  break;
2881  case 2:
2882  c = bm::bit_block_calc_count_range(block, nbit_right+1, rs3_border0);
2883  c = first - c;
2884  break;
2885  case 3:
2886  c = bm::bit_block_calc_count_range<true, false>(block,
2888  nbit_right);
2889  c += first - BM_BORDER_TEST(block, bm::rs3_border0);
2890  break;
2891  case 4:
2892  c = first + second;
2893  break;
2894  case 5:
2895  c = bm::bit_block_calc_count_range(block, nbit_right+1, rs3_border1);
2896  c = first + second - c;
2897  break;
2898  case 6:
2899  c = bm::bit_block_calc_count_range<true, false>(
2900  block,
2902  nbit_right);
2903  c += bm::gap_word_t(sub >> 32); // aux0
2904  c -= BM_BORDER_TEST(block, bm::rs3_border0_1);
2905  break;
2906  case 7:
2907  c = bm::bit_block_calc_count_range<true, false>(block,
2909  nbit_right);
2910  c += first + second; //bc_second_range;
2911  c -= BM_BORDER_TEST(block, bm::rs3_border1);
2912  break;
2913  case 8:
2914  c = bm::gap_word_t(sub >> 48); // aux1;
2915  break;
2916  case 9:
2918  nbit_right+1,
2919  rs3_border1_1);
2920  c = bm::gap_word_t(sub >> 48) - c; // aux1 - c
2921  break;
2922  case 10:
2923  c = rs_idx.count(nb);
2924  break;
2925  case 11:
2927  nbit_right+1,
2928  bm::gap_max_bits-1);
2929  c = rs_idx.count(nb) - c;
2930  break;
2931  case 12:
2932  c = bm::bit_block_calc_count_range<true, false>(block,
2934  nbit_right);
2935  c += bm::gap_word_t(sub >> 48); // aux1;
2936  c -= BM_BORDER_TEST(block, bm::rs3_border1_1);
2937  break;
2938  default:
2939  BM_ASSERT(0);
2940  } // switch
2941  BM_ASSERT(c == bm::bit_block_calc_count_to(block, nbit_right));
2942  return c;
2943 }
2944 #endif
2945 
2946 #undef BM_BORDER_TEST
2947 
2948 // -----------------------------------------------------------------------
2949 
2950 template<typename Alloc>
2953  block_idx_type nb,
2954  unsigned nbit_right,
2955  const rs_index_type& rs_idx,
2956  bool test_set) BMNOEXCEPT
2957 {
2958  BM_ASSERT(gap_block);
2959  size_type c;
2960 
2961 
2962  if (test_set)
2963  {
2964  bool is_set = bm::gap_test_unr(gap_block, (gap_word_t)nbit_right);
2965  if (!is_set)
2966  return 0;
2967  }
2968 /*
2969  {
2970  unsigned len = bm::gap_length(gap_block);
2971  if (len < 64)
2972  {
2973  c = bm::gap_bit_count_to(gap_block, (gap_word_t)nbit_right);
2974  return c;
2975  }
2976  }
2977 */
2978  bm::id64_t sub = rs_idx.sub_count(nb);
2979  if (!sub)
2980  {
2981  c = 0;
2982  BM_ASSERT(c == bm::gap_bit_count_to(gap_block, (gap_word_t)nbit_right));
2983  return c;
2984  }
2985 
2986  unsigned sub_cnt = unsigned(sub);
2987  unsigned first = bm::gap_word_t(sub_cnt);
2988  unsigned second = (sub_cnt >> 16);
2989 
2990 
2992  BM_ASSERT(second == bm::gap_bit_count_range(gap_block, rs3_border0+1, rs3_border1));
2993 
2994  // evaluate 3 sub-block intervals
2995  // |--------[0]-----------[1]----------|
2996  const unsigned cutoff_bias = rs3_half_span/8;
2997  unsigned sub_range = rs_idx.find_sub_range(nbit_right);
2998  switch(sub_range) // sub-range rank calc
2999  {
3000  case 0:
3001  // |--x-----[0]-----------[1]----------|
3002  if (nbit_right <= (rs3_border0/2 + cutoff_bias))
3003  {
3004  c = bm::gap_bit_count_to(gap_block,(gap_word_t)nbit_right);
3005  }
3006  else
3007  {
3008  // |--------[x]-----------[1]----------|
3009  if (nbit_right == rs3_border0)
3010  {
3011  c = first;
3012  }
3013  else
3014  {
3015  // |------x-[0]-----------[1]----------|
3016  c =
3017  bm::gap_bit_count_range(gap_block, nbit_right+1, rs3_border0);
3018  c = first - c;
3019  }
3020  }
3021  break;
3022  case 1:
3023  // |--------[0]-x---------[1]----------|
3024  if (nbit_right <= (rs3_border0 + rs3_half_span + cutoff_bias))
3025  {
3026  unsigned aux0 = bm::gap_word_t(sub >> 32);
3027  c = bm::gap_bit_count_range_hint(gap_block,
3028  rs3_border0+1, nbit_right, aux0);
3029  c += first;
3030  }
3031  else
3032  {
3033  // |--------[0]-----------[x]----------|
3034  if (nbit_right == rs3_border1)
3035  {
3036  c = first + second;
3037  }
3038  else
3039  {
3040  // |--------[0]--------x--[1]----------|
3041  c =
3042  bm::gap_bit_count_range(gap_block, nbit_right+1, rs3_border1);
3043  c = first + second - c;
3044  }
3045  }
3046  break;
3047  case 2:
3048  {
3049  // |--------[0]-----------[1]-x--------|
3050  if (nbit_right <= (rs3_border1 + rs3_half_span + cutoff_bias))
3051  {
3052  unsigned aux1 = bm::gap_word_t(sub >> 48);
3053  c = bm::gap_bit_count_range_hint(gap_block,
3054  rs3_border1 + 1, nbit_right, aux1);
3055  c += first + second; // += bc_second_range
3056  }
3057  else
3058  {
3059  // |--------[0]-----------[1]----------x
3060  if (nbit_right == bm::gap_max_bits-1)
3061  {
3062  c = rs_idx.count(nb);
3063  }
3064  else
3065  {
3066  // |--------[0]-----------[1]-------x--|
3067  c = bm::gap_bit_count_range<bm::gap_word_t, true> (gap_block,
3068  nbit_right+1, bm::gap_max_bits-1);
3069  size_type cnt = rs_idx.count(nb);
3070  c = cnt - c;
3071  }
3072  }
3073  }
3074  break;
3075  default:
3076  BM_ASSERT(0);
3077  c = 0;
3078  } // switch
3079 
3080  BM_ASSERT(c == bm::gap_bit_count_to(gap_block, (gap_word_t)nbit_right));
3081  return c;
3082 }
3083 
3084 // -----------------------------------------------------------------------
3085 
3086 template<typename Alloc>
3087 typename bvector<Alloc>::size_type
3089  const rs_index_type& rs_idx) const BMNOEXCEPT
3090 {
3091  BM_ASSERT(right < bm::id_max);
3092  if (!blockman_.is_init())
3093  return 0;
3094 
3095  unsigned nb_right = unsigned(right >> bm::set_block_shift);
3096 
3097  // running count of all blocks before target
3098  //
3099  size_type cnt;
3100  if (nb_right >= rs_idx.get_total())
3101  {
3102  cnt = rs_idx.count();
3103  return cnt;
3104  }
3105  cnt = nb_right ? rs_idx.rcount(nb_right-1) : 0;
3106 
3107  unsigned i, j;
3108  bm::get_block_coord(nb_right, i, j);
3109  const bm::word_t* block = blockman_.get_block_ptr(i, j);
3110 
3111  if (block)
3112  {
3113  size_type c;
3114  unsigned nbit_right = unsigned(right & bm::set_block_mask);
3115  if (BM_IS_GAP(block))
3116  {
3117  const bm::gap_word_t* gap_block = BMGAP_PTR(block);
3118  c = this->gap_count_to(gap_block, nb_right, nbit_right, rs_idx);
3119  }
3120  else
3121  {
3122  if (block == FULL_BLOCK_FAKE_ADDR) // TODO: misses REAL full sometimes
3123  {
3124  return cnt + nbit_right + 1;
3125  }
3126  else // real bit-block
3127  {
3128  c = this->block_count_to(block, nb_right, nbit_right, rs_idx);
3129  }
3130  }
3131  cnt += c;
3132 
3133  }
3134  return cnt;
3135 }
3136 
3137 // -----------------------------------------------------------------------
3138 
3139 template<typename Alloc>
3140 typename bvector<Alloc>::size_type
3142  const rs_index_type& rs_idx) const BMNOEXCEPT
3143 {
3144  BM_ASSERT(right < bm::id_max);
3145  if (!blockman_.is_init())
3146  return 0;
3147 
3148  unsigned nb_right = unsigned(right >> bm::set_block_shift);
3149 
3150  unsigned i, j;
3151  bm::get_block_coord(nb_right, i, j);
3152  const bm::word_t* block = blockman_.get_block_ptr(i, j);
3153  if (!block)
3154  return 0;
3155 
3156  unsigned nbit_right = unsigned(right & bm::set_block_mask);
3157  size_type cnt = nbit_right + 1; // default for FULL BLOCK
3158  if (BM_IS_GAP(block))
3159  {
3160  bm::gap_word_t *gap_blk = BMGAP_PTR(block);
3161  cnt = gap_count_to(gap_blk, nb_right, nbit_right, rs_idx, true);
3162  if (!cnt)
3163  return cnt;
3164  BM_ASSERT(cnt == bm::gap_bit_count_to(gap_blk, (gap_word_t)nbit_right));
3165  /*
3166  if (bm::gap_test_unr(gap_blk, (gap_word_t)nbit_right))
3167  {
3168  cnt = gap_count_to(gap_blk, nb_right, nbit_right, rs_idx);
3169  BM_ASSERT(cnt == bm::gap_bit_count_to(gap_blk, (gap_word_t)nbit_right));
3170  }
3171  else
3172  return 0;
3173  */
3174  }
3175  else
3176  {
3177  if (block != FULL_BLOCK_FAKE_ADDR)
3178  {
3179  unsigned w = block[nbit_right >> bm::set_word_shift]; // nword
3180  if (w &= (1u << (nbit_right & bm::set_word_mask)))
3181  {
3182  cnt = block_count_to(block, nb_right, nbit_right, rs_idx);
3183  BM_ASSERT(cnt == bm::bit_block_calc_count_to(block, nbit_right));
3184  }
3185  else
3186  return 0;
3187  }
3188  }
3189  cnt += nb_right ? rs_idx.rcount(nb_right - 1) : 0;
3190  return cnt;
3191 }
3192 
3193 // -----------------------------------------------------------------------
3194 
3195 template<typename Alloc>
3198  const rs_index_type& rs_idx) const BMNOEXCEPT
3199 {
3200  BM_ASSERT(right < bm::id_max);
3201  if (!blockman_.is_init())
3202  return 0;
3203 
3204  unsigned nblock_right = unsigned(right >> bm::set_block_shift);
3205  unsigned nbit_right = unsigned(right & bm::set_block_mask);
3206 
3207  size_type cnt = nblock_right ? rs_idx.rcount(nblock_right - 1) : 0;
3208 
3209  unsigned i, j;
3210  bm::get_block_coord(nblock_right, i, j);
3211  const bm::word_t* block = blockman_.get_block_ptr(i, j);
3212 
3213  if (!block)
3214  return cnt;
3215 
3216  bool gap = BM_IS_GAP(block);
3217  if (gap)
3218  {
3219  cnt += bm::gap_bit_count_to<bm::gap_word_t, true>(
3220  BMGAP_PTR(block), (gap_word_t)nbit_right);
3221  }
3222  else
3223  {
3224  if (block == FULL_BLOCK_FAKE_ADDR)
3225  cnt += nbit_right;
3226  else
3227  {
3228  cnt += block_count_to(block, nblock_right, nbit_right, rs_idx);
3229  unsigned w = block[nbit_right >> bm::set_word_shift] &
3230  (1u << (nbit_right & bm::set_word_mask));
3231  cnt -= bool(w); // rank correction
3232  }
3233  }
3234  return cnt;
3235 }
3236 
3237 
3238 // -----------------------------------------------------------------------
3239 
3240 template<typename Alloc>
3243 {
3244  BM_ASSERT(left < bm::id_max && right < bm::id_max);
3245  if (!blockman_.is_init())
3246  return 0;
3247  if (left > right)
3248  bm::xor_swap(left, right);
3249  if (right == bm::id_max)
3250  --right;
3251  return count_range_no_check(left, right);
3252 }
3253 
3254 // -----------------------------------------------------------------------
3255 
3256 template<typename Alloc>
3259 {
3260  size_type cnt = 0;
3261 
3262  // calculate logical number of start and destination blocks
3263  block_idx_type nblock_left = (left >> bm::set_block_shift);
3264  block_idx_type nblock_right = (right >> bm::set_block_shift);
3265 
3266  unsigned i0, j0;
3267  bm::get_block_coord(nblock_left, i0, j0);
3268  const bm::word_t* block = blockman_.get_block(i0, j0);
3269 
3270  bool left_gap = BM_IS_GAP(block);
3271 
3272  unsigned nbit_left = unsigned(left & bm::set_block_mask);
3273  unsigned nbit_right = unsigned(right & bm::set_block_mask);
3274 
3275  unsigned r =
3276  (nblock_left == nblock_right) ? nbit_right : (bm::bits_in_block-1);
3277 
3279 
3280  if (block)
3281  {
3282  if ((nbit_left == 0) && (r == (bm::bits_in_block-1))) // whole block
3283  {
3284  func(block);
3285  cnt += func.count();
3286  }
3287  else
3288  {
3289  if (left_gap)
3290  {
3292  (gap_word_t)nbit_left,
3293  (gap_word_t)r);
3294  }
3295  else
3296  {
3297  cnt += bm::bit_block_calc_count_range(block, nbit_left, r);
3298  }
3299  }
3300  }
3301 
3302  if (nblock_left == nblock_right) // in one block
3303  return cnt;
3304 
3305  // process all full mid-blocks
3306  {
3307  func.reset();
3308  word_t*** blk_root = blockman_.top_blocks_root();
3309  block_idx_type top_blocks_size = blockman_.top_block_size();
3310 
3311  bm::for_each_nzblock_range(blk_root, top_blocks_size,
3312  nblock_left+1, nblock_right-1, func);
3313  cnt += func.count();
3314  }
3315 
3316  bm::get_block_coord(nblock_right, i0, j0);
3317  block = blockman_.get_block(i0, j0);
3318  bool right_gap = BM_IS_GAP(block);
3319 
3320  if (block)
3321  {
3322  if (right_gap)
3323  {
3324  cnt +=
3325  bm::gap_bit_count_to(BMGAP_PTR(block), (gap_word_t)nbit_right);
3326  }
3327  else
3328  {
3329  cnt += bm::bit_block_calc_count_range(block, 0, nbit_right);
3330  }
3331  }
3332  return cnt;
3333 }
3334 
3335 // -----------------------------------------------------------------------
3336 
3337 template<typename Alloc>
3339  size_type right) const BMNOEXCEPT
3340 {
3341  if (!blockman_.is_init())
3342  return false; // nothing to do
3343 
3344  if (right < left)
3345  bm::xor_swap(left, right);
3346  if (right == bm::id_max)
3347  --right;
3348  if (left == right)
3349  return test(left);
3350 
3351  BM_ASSERT(left < bm::id_max && right < bm::id_max);
3352 
3353  block_idx_type nblock_left = (left >> bm::set_block_shift);
3354  block_idx_type nblock_right = (right >> bm::set_block_shift);
3355 
3356  unsigned i0, j0;
3357  bm::get_block_coord(nblock_left, i0, j0);
3358  const bm::word_t* block = blockman_.get_block(i0, j0);
3359 
3360  if (nblock_left == nblock_right) // hit in the same block
3361  {
3362  unsigned nbit_left = unsigned(left & bm::set_block_mask);
3363  unsigned nbit_right = unsigned(right & bm::set_block_mask);
3364  return bm::block_is_all_one_range(block, nbit_left, nbit_right);
3365  }
3366 
3367  // process entry point block
3368  {
3369  unsigned nbit_left = unsigned(left & bm::set_block_mask);
3370  bool all_one = bm::block_is_all_one_range(block,
3371  nbit_left, (bm::gap_max_bits-1));
3372  if (!all_one)
3373  return all_one;
3374  ++nblock_left;
3375  }
3376 
3377  // process tail block
3378  {
3379  bm::get_block_coord(nblock_right, i0, j0);
3380  block = blockman_.get_block(i0, j0);
3381  unsigned nbit_right = unsigned(right & bm::set_block_mask);
3382  bool all_one = bm::block_is_all_one_range(block, 0, nbit_right);
3383  if (!all_one)
3384  return all_one;
3385  --nblock_right;
3386  }
3387 
3388  // check all blocks in the middle
3389  //
3390  if (nblock_left <= nblock_right)
3391  {
3392  unsigned i_from, j_from, i_to, j_to;
3393  bm::get_block_coord(nblock_left, i_from, j_from);
3394  bm::get_block_coord(nblock_right, i_to, j_to);
3395 
3396  bm::word_t*** blk_root = blockman_.top_blocks_root();
3397 
3398  for (unsigned i = i_from; i <= i_to; ++i)
3399  {
3400  bm::word_t** blk_blk = blk_root[i];
3401  if (!blk_blk)
3402  return false;
3403  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
3404  continue;
3405 
3406  unsigned j = (i == i_from) ? j_from : 0;
3407  unsigned j_limit = (i == i_to) ? j_to+1 : bm::set_sub_array_size;
3408  do
3409  {
3410  bool all_one = bm::check_block_one(blk_blk[j], true);
3411  if (!all_one)
3412  return all_one;
3413  } while (++j < j_limit);
3414  } // for i
3415  }
3416  return true;
3417 }
3418 
3419 // -----------------------------------------------------------------------
3420 
3421 template<typename Alloc>
3423 {
3424  BM_ASSERT(left < bm::id_max && right < bm::id_max);
3425 
3426  if (!blockman_.is_init())
3427  return false; // nothing to do
3428 
3429  if (right < left)
3430  bm::xor_swap(left, right);
3431  if (right == bm::id_max)
3432  --right;
3433  if (left == right)
3434  return test(left);
3435 
3436  block_idx_type nblock_left = (left >> bm::set_block_shift);
3437  block_idx_type nblock_right = (right >> bm::set_block_shift);
3438 
3439  unsigned i0, j0;
3440  bm::get_block_coord(nblock_left, i0, j0);
3441  const bm::word_t* block = blockman_.get_block(i0, j0);
3442 
3443  if (nblock_left == nblock_right) // hit in the same block
3444  {
3445  unsigned nbit_left = unsigned(left & bm::set_block_mask);
3446  unsigned nbit_right = unsigned(right & bm::set_block_mask);
3447  return bm::block_any_range(block, nbit_left, nbit_right);
3448  }
3449 
3450  // process entry point block
3451  {
3452  unsigned nbit_left = unsigned(left & bm::set_block_mask);
3453  bool any_one = bm::block_any_range(block,
3454  nbit_left, (bm::gap_max_bits-1));
3455  if (any_one)
3456  return any_one;
3457  ++nblock_left;
3458  }
3459 
3460  // process tail block
3461  {
3462  bm::get_block_coord(nblock_right, i0, j0);
3463  block = blockman_.get_block(i0, j0);
3464  unsigned nbit_right = unsigned(right & bm::set_block_mask);
3465  bool any_one = bm::block_any_range(block, 0, nbit_right);
3466  if (any_one)
3467  return any_one;
3468  --nblock_right;
3469  }
3470 
3471  // check all blocks in the middle
3472  //
3473  if (nblock_left <= nblock_right)
3474  {
3475  unsigned i_from, j_from, i_to, j_to;
3476  bm::get_block_coord(nblock_left, i_from, j_from);
3477  bm::get_block_coord(nblock_right, i_to, j_to);
3478 
3479  bm::word_t*** blk_root = blockman_.top_blocks_root();
3480  {
3482  if (i_from >= top_size)
3483  return false;
3484  if (i_to >= top_size)
3485  {
3486  i_to = unsigned(top_size-1);
3487  j_to = bm::set_sub_array_size-1;
3488  }
3489  }
3490 
3491  for (unsigned i = i_from; i <= i_to; ++i)
3492  {
3493  bm::word_t** blk_blk = blk_root[i];
3494  if (!blk_blk)
3495  continue;
3496  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
3497  return true;
3498 
3499  unsigned j = (i == i_from) ? j_from : 0;
3500  unsigned j_limit = (i == i_to) ? j_to+1 : bm::set_sub_array_size;
3501  do
3502  {
3503  bool any_one = bm::block_any(blk_blk[j]);
3504  if (any_one)
3505  return any_one;
3506  } while (++j < j_limit);
3507  } // for i
3508  }
3509  return false;
3510 }
3511 
3512 // -----------------------------------------------------------------------
3513 
3514 template<typename Alloc>
3517  size_type right,
3518  const rs_index_type& rs_idx) const BMNOEXCEPT
3519 {
3520  if (left > right)
3521  bm::xor_swap(left, right);
3522  BM_ASSERT_THROW(right < bm::id_max, BM_ERR_RANGE);
3523  return count_range_no_check(left, right, rs_idx);
3524 }
3525 
3526 // -----------------------------------------------------------------------
3527 
3528 template<typename Alloc>
3531  size_type right,
3532  const rs_index_type& rs_idx) const BMNOEXCEPT
3533 {
3534  BM_ASSERT(left <= right);
3535  if (left == right)
3536  return this->test(left);
3537  size_type cnt_l, cnt_r;
3538  if (left)
3539  cnt_l = this->count_to(left-1, rs_idx);
3540  else
3541  cnt_l = left; // == 0
3542  cnt_r = this->count_to(right, rs_idx);
3543  BM_ASSERT(cnt_r >= cnt_l);
3544  return cnt_r - cnt_l;
3545 }
3546 
3547 // -----------------------------------------------------------------------
3548 
3549 template<typename Alloc>
3551 {
3552  BM_ASSERT(!is_ro());
3553 
3554  if (!size_)
3555  return *this; // cannot invert a set of power 0
3556 
3557  unsigned top_blocks = blockman_.reserve_top_blocks(bm::set_top_array_size);
3558  bm::word_t*** blk_root = blockman_.top_blocks_root();
3559  for (unsigned i = 0; i < top_blocks; ++i)
3560  {
3561  bm::word_t** blk_blk = blk_root[i];
3562  if (!blk_blk)
3563  {
3564  blk_root[i] = (bm::word_t**)FULL_BLOCK_FAKE_ADDR;
3565  continue;
3566  }
3567  if (blk_blk == (bm::word_t**)FULL_BLOCK_FAKE_ADDR)
3568  {
3569  blk_root[i] = 0;
3570  continue;
3571  }
3572  unsigned j = 0; bm::word_t* blk;
3573  do
3574  {
3575  blk = blk_blk[j];
3576  if (!blk)
3578  else
3579  if (IS_FULL_BLOCK(blk))
3580  blockman_.set_block_ptr(i, j, 0);
3581  else
3582  {
3583  if (BM_IS_GAP(blk))
3584  bm::gap_invert(BMGAP_PTR(blk));
3585  else
3586  bm::bit_invert((wordop_t*)blk);
3587  }
3588  } while (++j < bm::set_sub_array_size);
3589  } // for i
3590 
3591  if (size_ == bm::id_max)
3592  set_bit_no_check(bm::id_max, false);
3593  else
3595 
3596  return *this;
3597 }
3598 
3599 // -----------------------------------------------------------------------
3600 
3601 template<typename Alloc>
3603 {
3604  BM_ASSERT(n < size_);
3605  BM_ASSERT_THROW((n < size_), BM_ERR_RANGE);
3606 
3607  // calculate logical block number
3608  unsigned nb = unsigned(n >> bm::set_block_shift);
3609  unsigned i, j;
3610  bm::get_block_coord(nb, i, j);
3611 
3613  return false;
3614 
3615  const bm::word_t* const* blk_blk = blockman_.top_blocks_[i];
3616  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
3617  return true;
3618  if (!blk_blk) return false;
3619  if (const bm::word_t* block = blk_blk[j])
3620  {
3621  if (block == FULL_BLOCK_FAKE_ADDR)
3622  return true;
3623  unsigned nbit = unsigned(n & bm::set_block_mask);
3624  if (BM_IS_GAP(block))
3625  return bm::gap_test_unr(BMGAP_PTR(block), nbit);
3626  return block[nbit >> bm::set_word_shift] &
3627  (1u << (nbit & bm::set_word_mask));
3628  }
3629  return false;
3630 }
3631 
3632 // -----------------------------------------------------------------------
3633 
3634 template<typename Alloc>
3636  optmode opt_mode,
3637  statistics* stat)
3638 {
3639  BM_ASSERT(!is_ro());
3640 
3641  if (!blockman_.is_init())
3642  {
3643  if (stat)
3644  calc_stat(stat);
3645  return;
3646  }
3647  if (!temp_block)
3648  temp_block = blockman_.check_allocate_tempblock();
3649 
3650  if (stat)
3651  {
3652  stat->reset();
3653  ::memcpy(stat->gap_levels,
3654  blockman_.glen(), sizeof(gap_word_t) * bm::gap_levels);
3655  stat->max_serialize_mem = (unsigned)sizeof(bm::id_t) * 4;
3656  }
3657  blockman_.optimize_tree(temp_block, opt_mode, stat);
3658  if (stat)
3659  {
3660  blockman_.stat_correction(stat);
3661  stat->memory_used += (unsigned)(sizeof(*this) - sizeof(blockman_));
3662  }
3663 
3664  // don't need to keep temp block if we optimizing memory usage
3666 }
3667 
3668 // -----------------------------------------------------------------------
3669 
3670 template<typename Alloc>
3672  size_type left,
3673  size_type right,
3674  bm::word_t* temp_block,
3675  optmode opt_mode)
3676 {
3677  BM_ASSERT(!is_ro());
3678  BM_ASSERT(left <= right);
3679  BM_ASSERT(temp_block);
3680 
3681  block_idx_type nblock_left = (left >> bm::set_block_shift);
3682  block_idx_type nblock_right = (right >> bm::set_block_shift);
3683 
3684  for (; nblock_left <= nblock_right; ++nblock_left)
3685  {
3686  unsigned i0, j0;
3687  bm::get_block_coord(nblock_left, i0, j0);
3688  if (i0 >= blockman_.top_block_size())
3689  break;
3690  bm::word_t* block = blockman_.get_block_ptr(i0, j0);
3691  if (block)
3692  blockman_.optimize_block(i0, j0, block, temp_block, opt_mode, 0);
3693  } // for
3694 
3695 }
3696 
3697 // -----------------------------------------------------------------------
3698 
3699 template<typename Alloc>
3701 {
3702 #if 0
3703  if (!blockman_.is_init())
3704  return;
3705 
3706  struct bvector<Alloc>::statistics st;
3707  calc_stat(&st);
3708 
3709  if (!st.gap_blocks)
3710  return;
3711 
3712  gap_word_t opt_glen[bm::gap_levels];
3713  ::memcpy(opt_glen, st.gap_levels, bm::gap_levels * sizeof(*opt_glen));
3714 
3715  improve_gap_levels(st.gap_length,
3716  st.gap_length + st.gap_blocks,
3717  opt_glen);
3718 
3719  set_gap_levels(opt_glen);
3720 #endif
3721 }
3722 
3723 // -----------------------------------------------------------------------
3724 
3725 template<typename Alloc>
3726 void bvector<Alloc>::set_gap_levels(const gap_word_t* glevel_len)
3727 {
3728  BM_ASSERT(!is_ro());
3729 
3730  if (blockman_.is_init())
3731  {
3732  word_t*** blk_root = blockman_.top_blocks_root();
3733  typename
3734  blocks_manager_type::gap_level_func gl_func(blockman_, glevel_len);
3735  for_each_nzblock(blk_root, blockman_.top_block_size(),gl_func);
3736  }
3737 
3738  blockman_.set_glen(glevel_len);
3739 }
3740 
3741 // -----------------------------------------------------------------------
3742 
3743 template<typename Alloc>
3745 {
3746  int res;
3747  unsigned top_blocks = blockman_.top_block_size();
3748  unsigned bvect_top_blocks = bv.blockman_.top_block_size();
3749 
3750  if (bvect_top_blocks > top_blocks) top_blocks = bvect_top_blocks;
3751 
3752  for (unsigned i = 0; i < top_blocks; ++i)
3753  {
3754  const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
3755  const bm::word_t* const* arg_blk_blk = bv.blockman_.get_topblock(i);
3756 
3757  if (blk_blk == arg_blk_blk)
3758  continue;
3759 
3760  for (unsigned j = 0; j < bm::set_sub_array_size; ++j)
3761  {
3762  const bm::word_t* arg_blk; const bm::word_t* blk;
3763  if ((bm::word_t*)arg_blk_blk == FULL_BLOCK_FAKE_ADDR)
3764  arg_blk = FULL_BLOCK_REAL_ADDR;
3765  else
3766  {
3767  arg_blk = arg_blk_blk ? arg_blk_blk[j] : 0;
3768  if (arg_blk == FULL_BLOCK_FAKE_ADDR)
3769  arg_blk = FULL_BLOCK_REAL_ADDR;
3770  }
3771  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
3772  blk = FULL_BLOCK_REAL_ADDR;
3773  else
3774  {
3775  blk = blk_blk ? blk_blk[j] : 0;
3776  if (blk == FULL_BLOCK_FAKE_ADDR)
3777  blk = FULL_BLOCK_REAL_ADDR;
3778  }
3779  if (blk == arg_blk) continue;
3780 
3781  // If one block is zero we check if the other one has at least
3782  // one bit ON
3783 
3784  if (!blk || !arg_blk)
3785  {
3786  const bm::word_t* pblk; bool is_gap;
3787 
3788  if (blk)
3789  {
3790  pblk = blk;
3791  res = 1;
3792  is_gap = BM_IS_GAP(blk);
3793  }
3794  else
3795  {
3796  pblk = arg_blk;
3797  res = -1;
3798  is_gap = BM_IS_GAP(arg_blk);
3799  }
3800 
3801  if (is_gap)
3802  {
3803  if (!bm::gap_is_all_zero(BMGAP_PTR(pblk)))
3804  return res;
3805  }
3806  else
3807  {
3808  if (!bm::bit_is_all_zero(pblk))
3809  return res;
3810  }
3811  continue;
3812  }
3813  bool arg_gap = BM_IS_GAP(arg_blk);
3814  bool gap = BM_IS_GAP(blk);
3815 
3816  if (arg_gap != gap)
3817  {
3818  BM_DECLARE_TEMP_BLOCK(temp_blk)
3819  bm::wordop_t* blk1; bm::wordop_t* blk2;
3820 
3821  if (gap)
3822  {
3824  BMGAP_PTR(blk));
3825  blk1 = (bm::wordop_t*)temp_blk;
3826  blk2 = (bm::wordop_t*)arg_blk;
3827  }
3828  else
3829  {
3831  BMGAP_PTR(arg_blk));
3832  blk1 = (bm::wordop_t*)blk;
3833  blk2 = (bm::wordop_t*)temp_blk;
3834  }
3835  res = bm::bitcmp(blk1, blk2, bm::set_block_size_op);
3836  }
3837  else
3838  {
3839  if (gap)
3840  {
3841  res = bm::gapcmp(BMGAP_PTR(blk), BMGAP_PTR(arg_blk));
3842  }
3843  else
3844  {
3845  res = bm::bitcmp((bm::wordop_t*)blk,
3846  (bm::wordop_t*)arg_blk,
3848  }
3849  }
3850  if (res != 0)
3851  return res;
3852  } // for j
3853 
3854  } // for i
3855 
3856  return 0;
3857 }
3858 
3859 // -----------------------------------------------------------------------
3860 
3861 template<typename Alloc>
3863  const bvector<Alloc>& bvect, size_type& pos,
3864  size_type search_to) const BMNOEXCEPT
3865 {
3866  unsigned top_blocks = blockman_.top_block_size();
3867  bm::word_t*** top_root = blockman_.top_blocks_root();
3868 
3869  if (!top_blocks || !top_root)
3870  {
3871  return bvect.find(pos);
3872  }
3873  bm::word_t*** arg_top_root = bvect.blockman_.top_blocks_root();
3874  unsigned i_to, j_to;
3875  {
3876  unsigned bvect_top_blocks = bvect.blockman_.top_block_size();
3877  if (!bvect_top_blocks || !arg_top_root)
3878  {
3879  bool f = this->find(pos);
3880  if (f)
3881  {
3882  if (pos > search_to)
3883  return false;
3884  }
3885  return f;
3886  }
3887 
3888  if (bvect_top_blocks > top_blocks)
3889  top_blocks = bvect_top_blocks;
3890  block_idx_type nb_to = (search_to >> bm::set_block_shift);
3891  bm::get_block_coord(nb_to, i_to, j_to);
3892  }
3893  if (i_to < top_blocks)
3894  top_blocks = i_to+1;
3895 
3896  for (unsigned i = 0; i < top_blocks; ++i)
3897  {
3898  const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
3899  const bm::word_t* const* arg_blk_blk = bvect.blockman_.get_topblock(i);
3900 
3901  if (blk_blk == arg_blk_blk)
3902  {
3903  /* TODO: fix buffer overrread here
3904  unsigned arg_top_blocks = bvect.blockman_.top_block_size_;
3905  if (top_blocks < arg_top_blocks)
3906  arg_top_blocks = top_blocks;
3907  if (i_to < arg_top_blocks)
3908  arg_top_blocks = i_to+1;
3909 
3910  // look ahead for top level mismatch
3911  for (++i; i < arg_top_blocks; ++i)
3912  {
3913  if (top_root[i] != arg_top_root[i])
3914  {
3915  blk_blk = blockman_.get_topblock(i);
3916  arg_blk_blk = bvect.blockman_.get_topblock(i);
3917  BM_ASSERT(blk_blk != arg_blk_blk);
3918  goto find_sub_block;
3919  }
3920  }
3921  */
3922  continue;
3923  }
3924  //find_sub_block:
3925  unsigned j = 0;
3926  do
3927  {
3928  const bm::word_t* arg_blk; const bm::word_t* blk;
3929  arg_blk = ((bm::word_t*)arg_blk_blk == FULL_BLOCK_FAKE_ADDR) ?
3931  arg_blk_blk ? (BLOCK_ADDR_SAN(arg_blk_blk[j])) : 0;
3932  blk = ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR) ?
3934  (blk_blk ? (BLOCK_ADDR_SAN(blk_blk[j])) : 0);
3935  if (blk == arg_blk)
3936  continue;
3937 
3938  unsigned block_pos;
3939  bool found = bm::block_find_first_diff(blk, arg_blk, &block_pos);
3940  if (found)
3941  {
3942  pos =
3944  (size_type(j) * bm::gap_max_bits) + block_pos;
3945  if (pos > search_to)
3946  return false;
3947  return true;
3948  }
3949 
3950  if (i == i_to)
3951  {
3952  if (j >= j_to)
3953  return false;
3954  }
3955 
3956  } while (++j < bm::set_sub_array_size);
3957  } // for i
3958 
3959  return false;
3960 
3961 }
3962 
3963 // -----------------------------------------------------------------------
3964 
3965 template<typename Alloc>
3967 {
3968  if (this != &bvect)
3969  {
3972  }
3973 }
3974 
3975 // -----------------------------------------------------------------------
3976 
3977 template<typename Alloc>
3979  struct bvector<Alloc>::statistics* st) const BMNOEXCEPT
3980 {
3981  BM_ASSERT(st);
3982 
3983  st->reset();
3984  ::memcpy(st->gap_levels,
3985  blockman_.glen(), sizeof(gap_word_t) * bm::gap_levels);
3986 
3987  st->max_serialize_mem = unsigned(sizeof(bm::id_t) * 4);
3988  unsigned top_size = blockman_.top_block_size();
3989 
3990  size_t blocks_mem = sizeof(blockman_);
3991  blocks_mem +=
3993  blocks_mem += sizeof(bm::word_t**) * top_size;
3994  bm::word_t*** blk_root = blockman_.top_blocks_root();
3995 
3996  if (blk_root)
3997  {
3998  for (unsigned i = 0; i < top_size; ++i)
3999  {
4000  const bm::word_t* const* blk_blk = blk_root[i];
4001  if (!blk_blk)
4002  {
4003  ++i;
4004  bool found = bm::find_not_null_ptr(blk_root, i, top_size, &i);
4005  if (!found)
4006  break;
4007  blk_blk = blk_root[i];
4008  BM_ASSERT(blk_blk);
4009  if (!blk_blk)
4010  break;
4011  }
4012  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
4013  continue;
4014  st->ptr_sub_blocks++;
4015  for (unsigned j = 0; j < bm::set_sub_array_size; ++j)
4016  {
4017  const bm::word_t* blk = blk_blk[j];
4018  if (IS_VALID_ADDR(blk))
4019  {
4020  if (BM_IS_GAP(blk))
4021  {
4022  const bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
4023  unsigned cap;
4024  unsigned len = gap_length(gap_blk);
4025  cap = is_ro() ? len
4026  : bm::gap_capacity(gap_blk, blockman_.glen());
4027  unsigned level = bm::gap_level(gap_blk);
4028  st->add_gap_block(cap, len, level);
4029  }
4030  else // bit block
4031  st->add_bit_block();
4032  }
4033  } // for j
4034  } // for i
4035 
4036  size_t full_null_size = blockman_.calc_serialization_null_full();
4037  st->max_serialize_mem += full_null_size;
4038 
4039  } // if blk_root
4040 
4041  size_t safe_inc = st->max_serialize_mem / 10; // 10% increment
4042  if (!safe_inc) safe_inc = 256;
4043  st->max_serialize_mem += safe_inc;
4044 
4045  // Calc size of different odd and temporary things.
4046  st->memory_used += unsigned(sizeof(*this) - sizeof(blockman_));
4047  blocks_mem += st->ptr_sub_blocks * (sizeof(void*) * bm::set_sub_array_size);
4048  st->memory_used += blocks_mem;
4049  if (is_ro())
4050  st->memory_used += sizeof(typename blocks_manager_type::arena);
4051  st->bv_count = 1;
4052 
4053 }
4054 
4055 // -----------------------------------------------------------------------
4056 
4057 template<typename Alloc>
4059 {
4060  bv_blocks.init();
4061 
4062  unsigned top_size = blockman_.top_block_size();
4063  bm::word_t*** blk_root = blockman_.top_blocks_root();
4064  if (blk_root)
4065  {
4066  for (unsigned i = 0; i < top_size; ++i)
4067  {
4068  const bm::word_t* const* blk_blk = blk_root[i];
4069  if (!blk_blk || ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR))
4070  continue;
4071  for (unsigned j = 0; j < bm::set_sub_array_size; ++j)
4072  {
4073  const bm::word_t* blk = blk_blk[j];
4074  if (IS_VALID_ADDR(blk))
4075  {
4076  size_type nb = i * bm::set_sub_array_size + j;
4077  bv_blocks.set_bit_no_check(nb);
4078  }
4079  } // for j
4080  } // for i
4081  } // if blk_root
4082 }
4083 
4084 
4085 // -----------------------------------------------------------------------
4086 
4087 template<class Alloc>
4089  size_type ids_size, bm::sort_order so)
4090 {
4091  BM_ASSERT(!is_ro());
4092 
4093  if (!ids || !ids_size)
4094  return; // nothing to do
4095  if (!blockman_.is_init())
4096  blockman_.init_tree();
4097 
4098  import(ids, ids_size, so);
4099  sync_size();
4100 }
4101 
4102 // -----------------------------------------------------------------------
4103 
4104 template<class Alloc>
4105 void bvector<Alloc>::keep(const size_type* ids, size_type ids_size,
4106  bm::sort_order so)
4107 {
4108  BM_ASSERT(!is_ro());
4109 
4110  if (!ids || !ids_size || !blockman_.is_init())
4111  {
4112  clear();
4113  return;
4114  }
4115  bvector<Alloc> bv_tmp; // TODO: better optimize for SORTED case (avoid temp)
4116  bv_tmp.import(ids, ids_size, so);
4117 
4118  size_type last;
4119  bool found = bv_tmp.find_reverse(last);
4120  if (found)
4121  {
4122  bv_tmp.resize(last+1);
4123  bit_and(bv_tmp);
4124  }
4125  else
4126  {
4127  BM_ASSERT(0);
4128  clear();
4129  }
4130 }
4131 
4132 // -----------------------------------------------------------------------
4133 
4134 template<class Alloc>
4136 {
4137  if (is_ro())
4138  {
4139  BM_ASSERT(free_mem);
4141  }
4142  else
4143  blockman_.set_all_zero(free_mem);
4144 }
4145 
4146 // -----------------------------------------------------------------------
4147 
4148 template<class Alloc>
4150  size_type ids_size, bm::sort_order so)
4151 {
4152  BM_ASSERT(!is_ro());
4153 
4154  if (!ids || !ids_size || !blockman_.is_init())
4155  {
4156  return;
4157  }
4158  bvector<Alloc> bv_tmp; // TODO: better optimize for SORTED case (avoid temp)
4159  bv_tmp.import(ids, ids_size, so);
4160 
4161  size_type last;
4162  bool found = bv_tmp.find_reverse(last);
4163  if (found)
4164  {
4165  bv_tmp.resize(last+1);
4166  bit_sub(bv_tmp);
4167  }
4168  else
4169  {
4170  BM_ASSERT(0);
4171  }
4172 }
4173 
4174 // -----------------------------------------------------------------------
4175 
4176 template<class Alloc>
4178 {
4179  BM_ASSERT(!is_ro());
4180 
4181  set_range(0, size_ - 1, true);
4182  return *this;
4183 }
4184 
4185 // -----------------------------------------------------------------------
4186 
4187 template<class Alloc>
4189 {
4190  BM_ASSERT(!is_ro());
4191 
4192  set_bit(n, val);
4193  return *this;
4194 }
4195 
4196 // -----------------------------------------------------------------------
4197 
4198 template<class Alloc>
4199 bool bvector<Alloc>::set_bit_conditional(size_type n, bool val, bool condition)
4200 {
4201  if (val == condition) return false;
4202  if (n >= size_)
4203  {
4204  size_type new_size = (n == bm::id_max) ? bm::id_max : n + 1;
4205  resize(new_size);
4206  }
4207  return set_bit_conditional_impl(n, val, condition);
4208 }
4209 
4210 // -----------------------------------------------------------------------
4211 
4212 template<class Alloc>
4214 {
4215  BM_ASSERT(!is_ro());
4216  BM_ASSERT(n < size_);
4217  BM_ASSERT_THROW(n < size_, BM_ERR_RANGE);
4218 
4219  if (!blockman_.is_init())
4220  blockman_.init_tree();
4221  return and_bit_no_check(n, val);
4222 }
4223 
4224 // -----------------------------------------------------------------------
4225 
4226 template<class Alloc>
4228 {
4229  BM_ASSERT(!is_ro());
4230  BM_ASSERT_THROW(n < bm::id_max, BM_ERR_RANGE);
4231 
4232  if (!blockman_.is_init())
4233  blockman_.init_tree();
4234  if (n >= size_)
4235  {
4236  size_type new_size = (n == bm::id_max) ? bm::id_max : n + 1;
4237  resize(new_size);
4238  }
4239  return set_bit_no_check(n, val);
4240 }
4241 
4242 // -----------------------------------------------------------------------
4243 
4244 template<class Alloc>
4245 void bvector<Alloc>::import(const size_type* ids, size_type size_in,
4246  bm::sort_order sorted_idx)
4247 {
4248  BM_ASSERT(!is_ro());
4249 
4250  if (!size_in)
4251  return;
4252 
4253  size_type n, start(0), stop(size_in);
4254  block_idx_type nblock;
4255 
4256  n = ids[start];
4257  nblock = (n >> bm::set_block_shift);
4258 
4259  switch(sorted_idx)
4260  {
4261  case BM_SORTED:
4262  {
4263  block_idx_type nblock_end = (ids[size_in-1] >> bm::set_block_shift);
4264  if (nblock == nblock_end) // special case: one block import
4265  {
4266  import_block(ids, nblock, 0, stop);
4267  return;
4268  }
4269  // multi-block import, do top block space reservation
4270  unsigned i, j;
4271  bm::get_block_coord(nblock_end, i, j);
4273  }
4274  break;
4275  default:
4276  break;
4277  } // switch
4278 
4279  do
4280  {
4281  n = ids[start];
4282  nblock = (n >> bm::set_block_shift);
4283  #ifdef BM64ADDR
4284  stop = bm::idx_arr_block_lookup_u64(ids, size_in, nblock, start);
4285  #else
4286  stop = bm::idx_arr_block_lookup_u32(ids, size_in, nblock, start);
4287  #endif
4288  BM_ASSERT(start < stop);
4289  import_block(ids, nblock, start, stop);
4290  start = stop;
4291  } while (start < size_in);
4292 }
4293 
4294 // -----------------------------------------------------------------------
4295 
4296 template<class Alloc>
4298  const size_type size_in,
4299  bool opt_flag)
4300 {
4301  BM_ASSERT(size_in);
4302  BM_ASSERT(ids[0] < bm::id_max); // limit is 2^31-1 (for 32-bit mode)
4303  BM_ASSERT(ids[size_in-1] < bm::id_max);
4304 
4305  size_type n, start(0), stop = size_in;
4306  block_idx_type nblock, nblock_end;
4307 
4308  n = ids[start];
4309  nblock = (n >> bm::set_block_shift);
4310  nblock_end = (ids[size_in-1] >> bm::set_block_shift);
4311 
4312  if (nblock == nblock_end) // special (but frequent)case: one block import
4313  {
4314  import_block(ids, nblock, 0, stop);
4315  unsigned nbit = unsigned(ids[size_in-1] & bm::set_block_mask);
4316  if (opt_flag && nbit == 65535) // last bit in block
4317  {
4318  unsigned i, j;
4319  bm::get_block_coord(nblock, i, j);
4321  }
4322  }
4323  else
4324  {
4325  do
4326  {
4327  // TODO: use one-sided binary search to find the block limits
4328  #ifdef BM64ADDR
4329  stop = bm::idx_arr_block_lookup_u64(ids, size_in, nblock, start);
4330  #else
4331  stop = bm::idx_arr_block_lookup_u32(ids, size_in, nblock, start);
4332  #endif
4333  BM_ASSERT(start < stop);
4334 
4335  import_block(ids, nblock, start, stop);
4336  start = stop;
4337  nblock = (ids[stop] >> bm::set_block_shift);
4338  } while (start < size_in);
4339 
4340 
4341  if (opt_flag) // multi-block sorted import, lets optimize
4342  {
4343  n = ids[start];
4344  nblock = (n >> bm::set_block_shift);
4345  nblock_end = (ids[size_in-1] >> bm::set_block_shift);
4346  unsigned nbit = unsigned(ids[size_in-1] & bm::set_block_mask);
4347  nblock_end += bool(nbit == 65535);
4348  do
4349  {
4350  unsigned i, j;
4351  bm::get_block_coord(nblock++, i, j);
4353  } while (nblock < nblock_end);
4354  }
4355 
4356  }
4357 }
4358 
4359 
4360 // -----------------------------------------------------------------------
4361 
4362 template<class Alloc>
4364  block_idx_type nblock,
4365  size_type start,
4366  size_type stop)
4367 {
4368  BM_ASSERT(stop > start);
4369  int block_type;
4370  bm::word_t* blk =
4371  blockman_.check_allocate_block(nblock, 1, 0, &block_type,
4372  true/*allow NULL ret*/);
4373  if (!IS_FULL_BLOCK(blk))
4374  {
4375  if (BM_IS_GAP(blk))
4376  {
4377  if (stop-start == 1)
4378  {
4379  unsigned nbit = unsigned(ids[0] & bm::set_block_mask);
4380  gap_block_set_no_ret(BMGAP_PTR(blk), true, nblock, nbit);
4381  return;
4382  }
4383  blk = blockman_.deoptimize_block(nblock); // TODO: try to avoid
4384  }
4385  #ifdef BM64ADDR
4386  bm::set_block_bits_u64(blk, ids, start, stop);
4387  #else
4388  bm::set_block_bits_u32(blk, ids, start, stop);
4389  #endif
4390  if (new_blocks_strat_ == BM_GAP) // optimization required
4391  {
4392  BM_DECLARE_TEMP_BLOCK(temp_blk);
4393  unsigned i0, j0;
4394  bm::get_block_coord(nblock, i0, j0);
4395  blockman_.optimize_block(i0, j0, blk, temp_blk, opt_compress, 0);
4396  }
4397 
4398  if (nblock == bm::set_total_blocks-1)
4399  blk[bm::set_block_size-1] &= ~(1u<<31); // clear the "impossible" last just in case
4400  }
4401 }
4402 
4403 // -----------------------------------------------------------------------
4404 
4405 template<class Alloc>
4407 {
4408  BM_ASSERT(!is_ro());
4409  BM_ASSERT_THROW(idx1 < bm::id_max, BM_ERR_RANGE);
4410  BM_ASSERT_THROW(idx2 < bm::id_max, BM_ERR_RANGE);
4411 
4412  block_idx_type nb1 = (idx1 >> bm::set_block_shift);
4413  block_idx_type nb2 = (idx2 >> bm::set_block_shift);
4414 
4415  bm::word_t* block1, *block2;
4416  unsigned nbit1, nbit2;
4417  nbit1 = unsigned(idx1 & bm::set_block_mask);
4418  nbit2 = unsigned(idx2 & bm::set_block_mask);
4419 
4420  if (nb1 == nb2) // same block hit
4421  {
4422  unsigned i0, j0;
4423  bm::get_block_coord(nb1, i0, j0);
4424  block1 = blockman_.get_block_ptr(i0, j0);
4425  if (!block1 || (block1==FULL_BLOCK_FAKE_ADDR)) // nothing to do?
4426  return;
4427 
4428  if (BM_IS_GAP(block1))
4429  {
4430  bm::gap_word_t* gblk = BMGAP_PTR(block1);
4431  bool b1 = bm::gap_test_unr(gblk, nbit1);
4432  bool b2 = bm::gap_test_unr(gblk, nbit2);
4433  if (b1 != b2)
4434  {
4435  this->gap_block_set_no_ret(gblk, b2, nb1, nbit1);
4436  block2 = blockman_.get_block_ptr(i0, j0);
4437  if (block1 == block2) // same block
4438  this->gap_block_set_no_ret(gblk, b1, nb1, nbit2);
4439  else
4440  set_bit_no_check(idx2, b1);
4441  }
4442  return;
4443  }
4444  unsigned nword1 = unsigned(nbit1 >> bm::set_word_shift);
4445  unsigned nword2 = unsigned(nbit2 >> bm::set_word_shift);
4446  nbit1 &= bm::set_word_mask; nbit2 &= bm::set_word_mask;
4447  bool b1 = block1[nword1] & (1u << nbit1);
4448  bool b2 = block1[nword2] & (1u << nbit2);
4449  if (b1 != b2)
4450  {
4451  nbit1 = 1u << nbit1; nbit2 = 1u << nbit2;
4452  auto w = block1[nword1];
4453  (b2) ? w |= nbit1 : w &= ~nbit1;
4454  block1[nword1] = w;
4455  w = block1[nword2];
4456  (b1) ? w |= nbit2 : w &= ~nbit2;
4457  block1[nword2] = w;
4458  }
4459  return;
4460  } // if (same block)
4461 
4462  {
4463  unsigned i0, j0;
4464  bm::get_block_coord(nb1, i0, j0);
4465  block1 = blockman_.get_block_ptr(i0, j0);
4466  bm::get_block_coord(nb2, i0, j0);
4467  block2 = blockman_.get_block_ptr(i0, j0);
4468  }
4469  if (block1 == block2) // nothing to do
4470  return;
4471 
4472  bm::gap_word_t *gblk1{0}, *gblk2{0};
4473  unsigned cpos1{ 0 }, cpos2{ 0 };
4474  bool b1, b2, b1real, b2real;
4475 
4476  if (!block1)
4477  {
4478  b1 = false; b1real = false;
4479  }
4480  else
4481  if (block1 == FULL_BLOCK_FAKE_ADDR)
4482  {
4483  b1 = true; b1real = false;
4484  }
4485  else
4486  {
4487  b1real = true;
4488  nbit1 = unsigned(idx1 & bm::set_block_mask);
4489  if (BM_IS_GAP(block1))
4490  {
4491  gblk1 = BMGAP_PTR(block1);
4492  unsigned is_set;
4493  cpos1 = bm::gap_bfind(gblk1, nbit1, &is_set);
4494  b1 = is_set;
4495  }
4496  else // bit block
4497  {
4498  unsigned nword1 = unsigned(nbit1 >> bm::set_word_shift);
4499  b1 = block1[nword1] & (1u << (nbit1 & bm::set_word_mask));
4500  }
4501  }
4502 
4503  if (!block2)
4504  {
4505  b2 = false; b2real = false;
4506  }
4507  else
4508  if (block2 == FULL_BLOCK_FAKE_ADDR)
4509  {
4510  b2 = true; b2real = false;
4511  }
4512  else
4513  {
4514  b2real = true;
4515  nbit2 = unsigned(idx2 & bm::set_block_mask);
4516  if (BM_IS_GAP(block2))
4517  {
4518  gblk2 = BMGAP_PTR(block2);
4519  unsigned is_set;
4520  cpos2 = bm::gap_bfind(gblk2, nbit2, &is_set);
4521  b2 = is_set;
4522  }
4523  else // bit block
4524  {
4525  unsigned nword2 = unsigned(nbit2 >> bm::set_word_shift);
4526  b2 = block2[nword2] & (1u << (nbit2 & bm::set_word_mask));
4527  }
4528  }
4529 
4530  if (b1 == b2)
4531  return;
4532 
4533  if (b1real)
4534  {
4535  if (BM_IS_GAP(block1))
4536  {
4537  unsigned new_len, old_len;
4538  unsigned is_set = b1;
4539  old_len = bm::gap_length(gblk1)-1;
4540  new_len = bm::gap_set_value_cpos(b2, gblk1, nbit1, &is_set, cpos1);
4541  if (old_len < new_len)
4542  {
4543  unsigned threshold = bm::gap_limit(gblk1, blockman_.glen());
4544  if (new_len > threshold)
4545  blockman_.extend_gap_block(nb1, gblk1);
4546  }
4547  }
4548  else // bit block
4549  {
4550  unsigned nword1 = unsigned(nbit1 >> bm::set_word_shift);
4551  nbit1 = 1u << (nbit1 & bm::set_word_mask);
4552  auto w = block1[nword1];
4553  (b2) ? w |= nbit1 : w &= ~nbit1;
4554  block1[nword1] = w;
4555  }
4556  }
4557  else // block
4558  {
4559  set_bit_no_check(idx1, b2);
4560  }
4561 
4562  if (b2real)
4563  {
4564  if (BM_IS_GAP(block2))
4565  {
4566  unsigned new_len, old_len;
4567  unsigned is_set = b2;
4568  old_len = bm::gap_length(gblk2)-1;
4569  new_len = bm::gap_set_value_cpos(b1, gblk2, nbit2, &is_set, cpos2);
4570  if (old_len < new_len)
4571  {
4572  unsigned threshold = bm::gap_limit(gblk2, blockman_.glen());
4573  if (new_len > threshold)
4574  blockman_.extend_gap_block(nb2, gblk2);
4575  }
4576  }
4577  else // bit block
4578  {
4579  unsigned nword2 = unsigned(nbit2 >> bm::set_word_shift);
4580  nbit2 = 1u << (nbit2 & bm::set_word_mask);
4581  auto w = block2[nword2];
4582  (b1) ? w |= nbit2 : w &= ~nbit2;
4583  block2[nword2] = w;
4584  }
4585  }
4586  else
4587  {
4588  set_bit_no_check(idx2, b1);
4589  }
4590 
4591 
4592 }
4593 
4594 // -----------------------------------------------------------------------
4595 
4596 template<class Alloc>
4598 {
4599  BM_ASSERT(!is_ro());
4600  BM_ASSERT_THROW(n < bm::id_max, BM_ERR_RANGE);
4601 
4602  // calculate logical block number
4603  block_idx_type nblock = (n >> bm::set_block_shift);
4604 
4605  int block_type;
4606  bm::word_t* blk =
4608  val,
4610  &block_type);
4611 
4612  if (!IS_VALID_ADDR(blk))
4613  return false;
4614 
4615  // calculate word number in block and bit
4616  unsigned nbit = unsigned(n & bm::set_block_mask);
4617  if (block_type) // gap
4618  {
4619  return gap_block_set(BMGAP_PTR(blk), val, nblock, nbit);
4620  }
4621  else // bit block
4622  {
4623  unsigned nword = unsigned(nbit >> bm::set_word_shift);
4624  nbit &= bm::set_word_mask;
4625  bm::word_t* word = blk + nword;
4626  bm::word_t mask = (((bm::word_t)1) << nbit);
4627 
4628  if (val)
4629  {
4630  val = ~(*word & mask);
4631  *word |= mask; // set bit
4632  return val;
4633  }
4634  else
4635  {
4636  val = ~(*word & mask);
4637  *word &= ~mask; // clear bit
4638  return val;
4639  }
4640  }
4641 }
4642 
4643 // -----------------------------------------------------------------------
4644 
4645 template<class Alloc>
4647 {
4648  BM_ASSERT(!is_ro());
4649  BM_ASSERT_THROW(n < bm::id_max, BM_ERR_RANGE);
4650 
4651  const bool val = true; // set bit
4652 
4653  block_idx_type nblock = (n >> bm::set_block_shift);
4654  unsigned nbit = unsigned(n & bm::set_block_mask);
4655 
4656  int block_type;
4657  bm::word_t* blk =
4659  val,
4661  &block_type);
4662  if (!IS_VALID_ADDR(blk))
4663  return;
4664 
4665  if (block_type) // gap block
4666  {
4667  this->gap_block_set_no_ret(BMGAP_PTR(blk), val, nblock, nbit);
4668  }
4669  else // bit block
4670  {
4671  unsigned nword = nbit >> bm::set_word_shift;
4672  nbit &= bm::set_word_mask;
4673  blk[nword] |= (1u << nbit); // set bit
4674  }
4675 }
4676 
4677 // -----------------------------------------------------------------------
4678 
4679 template<class Alloc>
4681 {
4682  BM_ASSERT(!is_ro());
4683  BM_ASSERT_THROW(n < bm::id_max, BM_ERR_RANGE);
4684 
4685  const bool val = false; // clear bit
4686 
4687  block_idx_type nblock = (n >> bm::set_block_shift);
4688  int block_type;
4689  bm::word_t* blk =
4691  val,
4693  &block_type);
4694  if (!blk)
4695  return;
4696 
4697  unsigned nbit = unsigned(n & bm::set_block_mask);
4698  if (block_type) // gap
4699  {
4700  this->gap_block_set_no_ret(BMGAP_PTR(blk), val, nblock, nbit);
4701  }
4702  else // bit block
4703  {
4704  unsigned nword = unsigned(nbit >> bm::set_word_shift);
4705  nbit &= bm::set_word_mask;
4706  blk[nword] &= ~(1u << nbit); // clear bit
4707  }
4708 }
4709 
4710 
4711 // -----------------------------------------------------------------------
4712 
4713 template<class Alloc>
4715  bool val, block_idx_type nblock,
4716  unsigned nbit)
4717 {
4718  unsigned is_set, new_len, old_len;
4719  old_len = bm::gap_length(gap_blk)-1;
4720  new_len = bm::gap_set_value(val, gap_blk, nbit, &is_set);
4721  if (old_len < new_len)
4722  {
4723  unsigned threshold = bm::gap_limit(gap_blk, blockman_.glen());
4724  if (new_len > threshold)
4725  blockman_.extend_gap_block(nblock, gap_blk);
4726  }
4727  return is_set;
4728 }
4729 
4730 // -----------------------------------------------------------------------
4731 
4732 template<class Alloc>
4734  bool val, block_idx_type nblock, unsigned nbit)
4735 {
4736  unsigned new_len, old_len;
4737  old_len = bm::gap_length(gap_blk)-1;
4738  new_len = bm::gap_set_value(val, gap_blk, nbit);
4739  if (old_len < new_len)
4740  {
4741  unsigned threshold = bm::gap_limit(gap_blk, blockman_.glen());
4742  if (new_len > threshold)
4743  blockman_.extend_gap_block(nblock, gap_blk);
4744  }
4745 }
4746 
4747 
4748 // -----------------------------------------------------------------------
4749 
4750 template<class Alloc>
4752 {
4753  BM_ASSERT(!is_ro());
4754  // calculate logical block number
4755  block_idx_type nblock = (n >> bm::set_block_shift);
4756  bm::word_t* blk =
4759  BM_ASSERT(IS_VALID_ADDR(blk));
4760 
4761  unsigned nbit = unsigned(n & bm::set_block_mask);
4762  unsigned is_set;
4763  if (BM_IS_GAP(blk))
4764  {
4765  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
4766  is_set = (bm::gap_test_unr(gap_blk, nbit) != 0);
4767  this->gap_block_set(gap_blk, !is_set, nblock, nbit); // flip
4768  }
4769  else // bit block
4770  {
4771  unsigned nword = unsigned(nbit >> bm::set_word_shift);
4772  nbit &= bm::set_word_mask;
4773  bm::word_t* word = blk + nword;
4774  const bm::word_t mask = (((bm::word_t)1) << nbit);
4775  is_set = ((*word) & mask);
4776  *word ^= mask; // flip the bit
4777  }
4778  return is_set;
4779 }
4780 
4781 // -----------------------------------------------------------------------
4782 
4783 template<class Alloc>
4785  bool val,
4786  bool condition)
4787 {
4788  // calculate logical block number
4789  block_idx_type nblock = (n >> bm::set_block_shift);
4790  int block_type;
4791  bm::word_t* blk =
4793  val,
4795  &block_type);
4796  if (!IS_VALID_ADDR(blk))
4797  return false;
4798 
4799  // calculate word number in block and bit
4800  unsigned nbit = unsigned(n & bm::set_block_mask);
4801 
4802  if (block_type == 1) // gap
4803  {
4804  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
4805  unsigned is_set = gap_block_set(gap_blk, val, nblock, nbit);
4806  return is_set;
4807  }
4808  else // bit block
4809  {
4810  unsigned nword = unsigned(nbit >> bm::set_word_shift);
4811  nbit &= bm::set_word_mask;
4812 
4813  bm::word_t* word = blk + nword;
4814  bm::word_t mask = (((bm::word_t)1) << nbit);
4815  bool is_set = ((*word) & mask) != 0;
4816 
4817  if (is_set != condition)
4818  return false;
4819  if (is_set != val) // need to change bit
4820  {
4821  if (val) // set bit
4822  *word |= mask;
4823  else // clear bit
4824  *word &= ~mask;
4825  return true;
4826  }
4827  }
4828  return false;
4829 
4830 }
4831 
4832 // -----------------------------------------------------------------------
4833 
4834 
4835 template<class Alloc>
4837 {
4838  BM_ASSERT(!is_ro());
4839  // calculate logical block number
4840  block_idx_type nblock = (n >> bm::set_block_shift);
4841 
4842  int block_type;
4843  bm::word_t* blk =
4845  val,
4847  &block_type);
4848  if (!IS_VALID_ADDR(blk))
4849  return false;
4850 
4851  // calculate word number in block and bit
4852  unsigned nbit = unsigned(n & bm::set_block_mask);
4853 
4854  if (block_type == 1) // gap
4855  {
4856  bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
4857  bool old_val = (bm::gap_test_unr(gap_blk, nbit) != 0);
4858 
4859  bool new_val = val & old_val;
4860  if (new_val != old_val)
4861  {
4862  unsigned is_set = gap_block_set(gap_blk, val, nblock, nbit);
4863  BM_ASSERT(is_set);
4864  return is_set;
4865  }
4866  }
4867  else // bit block
4868  {
4869  unsigned nword = unsigned(nbit >> bm::set_word_shift);
4870  nbit &= bm::set_word_mask;
4871 
4872  bm::word_t* word = blk + nword;
4873  bm::word_t mask = (((bm::word_t)1) << nbit);
4874  bool is_set = ((*word) & mask) != 0;
4875 
4876  bool new_val = is_set & val;
4877  if (new_val != val) // need to change bit
4878  {
4879  if (new_val) // set bit
4880  {
4881  *word |= mask;
4882  }
4883  else // clear bit
4884  {
4885  *word &= ~mask;
4886  }
4887  return true;
4888  }
4889  }
4890  return false;
4891 }
4892 
4893 //---------------------------------------------------------------------
4894 
4895 template<class Alloc>
4897 {
4898  if (from == bm::id_max)
4899  return false;
4900  if (!from)
4901  {
4902  return find(pos);
4903  }
4904  pos = check_or_next(from);
4905  return (pos != 0);
4906 }
4907 
4908 //---------------------------------------------------------------------
4909 
4910 template<class Alloc>
4912 {
4913  bool found;
4914 
4915  unsigned top_blocks = blockman_.top_block_size();
4916  if (!top_blocks)
4917  return false;
4918  for (unsigned i = top_blocks-1; true; --i)
4919  {
4920  const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
4921  if (blk_blk)
4922  {
4923  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
4924  blk_blk = FULL_SUB_BLOCK_REAL_ADDR;
4925 
4926  for (unsigned short j = bm::set_sub_array_size-1; true; --j)
4927  {
4928  const bm::word_t* blk = blk_blk[j];
4929  if (blk)
4930  {
4931  unsigned block_pos;
4932  if (blk == FULL_BLOCK_FAKE_ADDR)
4933  {
4934  block_pos = bm::gap_max_bits-1;
4935  found = true;
4936  }
4937  else
4938  {
4939  bool is_gap = BM_IS_GAP(blk);
4940  found = is_gap ? bm::gap_find_last(BMGAP_PTR(blk), &block_pos)
4941  : bm::bit_find_last(blk, &block_pos);
4942  }
4943  if (found)
4944  {
4945  block_idx_type base_idx =
4948  base_idx += j * bm::gap_max_bits;
4949  pos = base_idx + block_pos;
4950  return found;
4951  }
4952  }
4953 
4954  if (j == 0)
4955  break;
4956  } // for j
4957  } // if blk_blk
4958 
4959  if (i == 0)
4960  break;
4961  } // for i
4962  return false;
4963 }
4964 
4965 //---------------------------------------------------------------------
4966 
4967 template<class Alloc>
4969 {
4970  bool found;
4971  if (!blockman_.is_init())
4972  return false; // nothing to do
4973  if (!from)
4974  {
4975  pos = from;
4976  return this->test(from);
4977  }
4978 
4979  block_idx_type nb = (from >> bm::set_block_shift);
4980  unsigned i0, j0;
4981  bm::get_block_coord(nb, i0, j0);
4982 
4983  const bm::word_t* block = blockman_.get_block_ptr(i0, j0);
4984  if (block)
4985  {
4986  size_type base_idx;
4987  unsigned found_nbit;
4988  unsigned nbit = unsigned(from & bm::set_block_mask);
4989  found = bm::block_find_reverse(block, nbit, &found_nbit);
4990  if (found)
4991  {
4992  base_idx = bm::get_block_start<size_type>(i0, j0);
4993  pos = base_idx + found_nbit;
4994  return found;
4995  }
4996  }
4997 
4998  if (nb)
4999  --nb;
5000  else
5001  return false;
5002  bm::get_block_coord(nb, i0, j0);
5003 
5004  const bm::word_t* const* blk_blk = blockman_.get_topblock(i0);
5005  if (blk_blk)
5006  {
5007  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
5008  blk_blk = FULL_SUB_BLOCK_REAL_ADDR;
5009  for (unsigned j = j0; true; --j)
5010  {
5011  const bm::word_t* blk = blk_blk[j];
5012  if (blk)
5013  {
5014  unsigned block_pos;
5015  if (blk == FULL_BLOCK_FAKE_ADDR)
5016  {
5017  block_pos = bm::gap_max_bits-1;
5018  found = true;
5019  }
5020  else
5021  {
5022  bool is_gap = BM_IS_GAP(blk);
5023  found = is_gap ? bm::gap_find_last(BMGAP_PTR(blk), &block_pos)
5024  : bm::bit_find_last(blk, &block_pos);
5025  }
5026  if (found)
5027  {
5028  block_idx_type base_idx =
5031  base_idx += j * bm::gap_max_bits;
5032  pos = base_idx + block_pos;
5033  return found;
5034  }
5035  }
5036  if (!j)
5037  break;
5038  } // for j
5039  }
5040  if (i0)
5041  --i0;
5042  else
5043  return false;
5044 
5045  for (unsigned i = i0; true; --i)
5046  {
5047  blk_blk = blockman_.get_topblock(i);
5048  if (blk_blk)
5049  {
5050  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
5051  blk_blk = FULL_SUB_BLOCK_REAL_ADDR;
5052  for (unsigned short j = bm::set_sub_array_size-1; true; --j)
5053  {
5054  const bm::word_t* blk = blk_blk[j];
5055  if (blk)
5056  {
5057  unsigned block_pos;
5058  if (blk == FULL_BLOCK_FAKE_ADDR)
5059  {
5060  block_pos = bm::gap_max_bits-1;
5061  found = true;
5062  }
5063  else
5064  {
5065  bool is_gap = BM_IS_GAP(blk);
5066  found = is_gap ? bm::gap_find_last(BMGAP_PTR(blk), &block_pos)
5067  : bm::bit_find_last(blk, &block_pos);
5068  }
5069  if (found)
5070  {
5071  block_idx_type base_idx =
5074  base_idx += j * bm::gap_max_bits;
5075  pos = base_idx + block_pos;
5076  return found;
5077  }
5078  }
5079  if (!j)
5080  break;
5081  } // for j
5082  }
5083  if (i == 0)
5084  break;
5085  } // for i
5086 
5087  return false;
5088 }
5089 
5090 //---------------------------------------------------------------------
5091 
5092 template<class Alloc>
5094 {
5095  bool found;
5096 
5097  unsigned top_blocks = blockman_.top_block_size();
5098  for (unsigned i = 0; i < top_blocks; ++i)
5099  {
5100  const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
5101  if (blk_blk)
5102  {
5103  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
5104  blk_blk = FULL_SUB_BLOCK_REAL_ADDR;
5105 
5106  for (unsigned j = 0; j < bm::set_sub_array_size; ++j)
5107  {
5108  const bm::word_t* blk = blk_blk[j];
5109  if (blk)
5110  {
5111  unsigned block_pos;
5112  if (blk == FULL_BLOCK_FAKE_ADDR)
5113  {
5114  found = true; block_pos = 0;
5115  }
5116  else
5117  {
5118  bool is_gap = BM_IS_GAP(blk);
5119  found = (is_gap) ? bm::gap_find_first(BMGAP_PTR(blk), &block_pos)
5120  : bm::bit_find_first(blk, &block_pos);
5121  }
5122  if (found)
5123  {
5125  base_idx += j * bm::gap_max_bits;
5126  pos = base_idx + block_pos;
5127  return found;
5128  }
5129  }
5130  } // for j
5131  } // if blk_blk
5132  } // for i
5133  return false;
5134 }
5135 
5136 //---------------------------------------------------------------------
5137 
5138 template<class Alloc>
5140  size_type& in_last) const BMNOEXCEPT
5141 {
5142  bool found = find(in_first);
5143  if (found)
5144  {
5145  found = find_reverse(in_last);
5146  BM_ASSERT(found);
5147  BM_ASSERT(in_first <= in_last);
5148  }
5149  else
5150  {
5151  in_first = in_last = 0; // zero the output just in case
5152  }
5153  return found;
5154 }
5155 
5156 //---------------------------------------------------------------------
5157 
5158 template<class Alloc>
5160  size_type from,
5161  size_type& pos) const BMNOEXCEPT
5162 {
5163  BM_ASSERT_THROW(from < bm::id_max, BM_ERR_RANGE);
5164 
5165  bool ret = false;
5166 
5167  if (!rank_in || !blockman_.is_init())
5168  return ret;
5169 
5170  block_idx_type nb = (from >> bm::set_block_shift);
5172  unsigned bit_pos = 0;
5173 
5174  for (; nb < bm::set_total_blocks; ++nb)
5175  {
5176  int no_more_blocks;
5177  const bm::word_t* block = blockman_.get_block(nb, &no_more_blocks);
5178  if (block)
5179  {
5180  if (!nbit && (rank_in > bm::gap_max_bits)) // requested rank cannot be in this block
5181  {
5182  unsigned cnt = blockman_.block_bitcount(block);
5183  BM_ASSERT(cnt < rank_in);
5184  rank_in -= cnt;
5185  continue;
5186  }
5187  else
5188  {
5189  rank_in = bm::block_find_rank(block, rank_in, nbit, bit_pos);
5190  if (!rank_in) // target found
5191  {
5192  pos = bit_pos + (nb * bm::set_block_size * 32);
5193  return true;
5194  }
5195  }
5196  }
5197  else
5198  {
5199  // TODO: better next block search
5200  if (no_more_blocks)
5201  break;
5202  }
5203  nbit ^= nbit; // zero start bit after first scanned block
5204  } // for nb
5205 
5206  return ret;
5207 }
5208 
5209 //---------------------------------------------------------------------
5210 
5211 template<class Alloc>
5213  size_type from,
5214  size_type& pos,
5215  const rs_index_type& rs_idx) const BMNOEXCEPT
5216 {
5217  BM_ASSERT_THROW(from < bm::id_max, BM_ERR_RANGE);
5218 
5219  bool ret = false;
5220 
5221  if (!rank_in ||
5222  !blockman_.is_init() ||
5223  (rs_idx.count() < rank_in))
5224  return ret;
5225 
5226  block_idx_type nb;
5227  if (from)
5228  nb = (from >> bm::set_block_shift);
5229  else
5230  {
5231  nb = rs_idx.find(rank_in);
5232  BM_ASSERT(rs_idx.rcount(nb) >= rank_in);
5233  if (nb)
5234  rank_in -= rs_idx.rcount(nb-1);
5235  }
5236 
5238  unsigned bit_pos = 0;
5239 
5240  for (; nb < rs_idx.get_total(); ++nb)
5241  {
5242  int no_more_blocks;
5243  const bm::word_t* block = blockman_.get_block(nb, &no_more_blocks);
5244  if (block)
5245  {
5246  if (!nbit) // check if the whole block can be skipped
5247  {
5248  unsigned block_bc = rs_idx.count(nb);
5249  if (rank_in <= block_bc) // target block
5250  {
5251  nbit = rs_idx.select_sub_range(nb, rank_in);
5252  rank_in = bm::block_find_rank(block, rank_in, nbit, bit_pos);
5253  BM_ASSERT(rank_in == 0);
5254  pos = bit_pos + (nb * bm::set_block_size * 32);
5255  return true;
5256  }
5257  rank_in -= block_bc;
5258  continue;
5259  }
5260 
5261  rank_in = bm::block_find_rank(block, rank_in, nbit, bit_pos);
5262  if (!rank_in) // target found
5263  {
5264  pos = bit_pos + (nb * bm::set_block_size * 32);
5265  return true;
5266  }
5267  }
5268  else
5269  {
5270  // TODO: better next block search
5271  if (no_more_blocks)
5272  break;
5273  }
5274  nbit ^= nbit; // zero start bit after first scanned block
5275  } // for nb
5276 
5277  return ret;
5278 }
5279 
5280 //---------------------------------------------------------------------
5281 
5282 template<class Alloc>
5284  const rs_index_type& rs_idx) const BMNOEXCEPT
5285 {
5286  bool ret = false;
5287 
5288  if (!rank_in ||
5289  !blockman_.is_init() ||
5290  (rs_idx.count() < rank_in))
5291  return ret;
5292 
5293  block_idx_type nb;
5294  bm::gap_word_t sub_range_from;
5295  bool found = rs_idx.find(&rank_in, &nb, &sub_range_from);
5296  if (!found)
5297  return found;
5298 
5299  unsigned i, j;
5300  bm::get_block_coord(nb, i, j);
5301  const bm::word_t* block = blockman_.get_block_ptr(i, j);
5302  BM_ASSERT(block);
5303  BM_ASSERT(rank_in <= rs_idx.count(nb));
5304 
5305  unsigned bit_pos = 0;
5306  if (block == FULL_BLOCK_FAKE_ADDR)
5307  {
5308  BM_ASSERT(rank_in <= bm::gap_max_bits);
5309  bit_pos = sub_range_from + unsigned(rank_in) - 1;
5310  }
5311  else
5312  {
5313  rank_in = bm::block_find_rank(block, rank_in, sub_range_from, bit_pos);
5314  BM_ASSERT(rank_in == 0);
5315  }
5316  pos = bit_pos + (nb * bm::set_block_size * 32);
5317  return true;
5318 }
5319 
5320 //---------------------------------------------------------------------
5321 
5322 template<class Alloc>
5323 typename bvector<Alloc>::size_type
5325 {
5326  if (!blockman_.is_init())
5327  return 0;
5328 
5329  // calculate logical block number
5331  unsigned i, j;
5332  bm::get_block_coord(nb, i, j);
5333  const bm::word_t* block = blockman_.get_block_ptr(i, j);
5334 
5335  if (block)
5336  {
5337  unsigned block_pos;
5338  bool found = false;
5339  // calculate word number in block and bit
5340  unsigned nbit = unsigned(prev & bm::set_block_mask);
5341  if (BM_IS_GAP(block))
5342  {
5343  if (bm::gap_block_find(BMGAP_PTR(block), nbit, &block_pos))
5344  {
5345  prev = (size_type(nb) * bm::gap_max_bits) + block_pos;
5346  return prev;
5347  }
5348  }
5349  else
5350  {
5351  if (block == FULL_BLOCK_FAKE_ADDR)
5352  return prev;
5353  found = bm::bit_block_find(block, nbit, &block_pos);
5354  if (found)
5355  {
5356  prev = (size_type(nb) * bm::gap_max_bits) + block_pos;
5357  return prev;
5358  }
5359  }
5360  }
5361  ++j;
5362  block_idx_type top_blocks = blockman_.top_block_size();
5363  for (; i < top_blocks; ++i)
5364  {
5365  const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
5366  if (blk_blk)
5367  {
5368  if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
5369  blk_blk = FULL_SUB_BLOCK_REAL_ADDR;
5370 
5371  for (; j < bm::set_sub_array_size; ++j)
5372  {
5373  const bm::word_t* blk = blk_blk[j];
5374  if (blk)
5375  {
5376  bool found;
5377  unsigned block_pos;
5378  if (blk == FULL_BLOCK_FAKE_ADDR)