Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Data Structures | Directories | File List | Namespace Members | Data Fields | Globals | Examples

bm.h

Go to the documentation of this file.
00001 /*
00002 Copyright(c) 2002-2005 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
00003 
00004 Permission is hereby granted, free of charge, to any person 
00005 obtaining a copy of this software and associated documentation 
00006 files (the "Software"), to deal in the Software without restriction, 
00007 including without limitation the rights to use, copy, modify, merge, 
00008 publish, distribute, sublicense, and/or sell copies of the Software, 
00009 and to permit persons to whom the Software is furnished to do so, 
00010 subject to the following conditions:
00011 
00012 The above copyright notice and this permission notice shall be included 
00013 in all copies or substantial portions of the Software.
00014 
00015 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
00016 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 
00017 OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
00018 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 
00019 DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 
00020 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 
00021 OTHER DEALINGS IN THE SOFTWARE.
00022 
00023 For more information please visit:  http://bmagic.sourceforge.net
00024 
00025 */
00026 
00027 #ifndef BM__H__INCLUDED__
00028 #define BM__H__INCLUDED__
00029 
00030 #include <string.h>
00031 #include <assert.h>
00032 #include <limits.h>
00033 
00034 // define BM_NO_STL if you use BM in "STL free" environment and want
00035 // to disable any references to STL headers
00036 #ifndef BM_NO_STL
00037 # include <iterator>
00038 #endif
00039 
00040 #ifdef _MSC_VER
00041 #pragma warning( disable : 4311 4312)
00042 #endif
00043 
00044 
00045 
00046 #include "bmconst.h"
00047 #include "bmdef.h"
00048 
00049 
00050 // Vector based optimizations are incompatible with 64-bit optimization
00051 // which is considered a form of vectorization
00052 #ifdef BMSSE2OPT
00053 # undef BM64OPT
00054 # define BMVECTOPT
00055 # include "bmsse2.h"
00056 #endif
00057 
00058 #include "bmfwd.h"
00059 #include "bmfunc.h"
00060 #include "bmvmin.h"
00061 #include "encoding.h"
00062 #include "bmalloc.h"
00063 #include "bmblocks.h"
00064 
00065 namespace bm
00066 {
00067 
00068 
00069 #ifdef BMCOUNTOPT
00070 
00071 # define BMCOUNT_INC ++count_;
00072 # define BMCOUNT_DEC --count_;
00073 # define BMCOUNT_VALID(x) count_is_valid_ = x;
00074 # define BMCOUNT_SET(x) count_ = x; count_is_valid_ = true;
00075 # define BMCOUNT_ADJ(x) if (x) ++count_; else --count_;
00076 
00077 #else
00078 
00079 # define BMCOUNT_INC
00080 # define BMCOUNT_DEC
00081 # define BMCOUNT_VALID(x)
00082 # define BMCOUNT_SET(x)
00083 # define BMCOUNT_ADJ(x)
00084 
00085 #endif
00086 
00087 
00088 
00089 typedef bm::miniset<bm::block_allocator, bm::set_total_blocks> mem_save_set;
00090 
00091 
00092 /** @defgroup bmagic BitMagic C++ Library
00093  *  For more information please visit:  http://bmagic.sourceforge.net
00094  *  
00095  */
00096 
00097 
00098 /** @defgroup bvector The Main bvector<> Group
00099  *  This is the main group. It includes bvector template: front end of the bm library.
00100  *  @ingroup bmagic 
00101  */
00102 
00103 
00104 
00105 
00106 /*!
00107    @brief bitvector with runtime compression of bits.
00108    @ingroup bvector
00109 */
00110 
00111 template<class Alloc, class MS> 
00112 class bvector
00113 {
00114 public:
00115 
00116     typedef Alloc  allocator_type;
00117     typedef blocks_manager<Alloc, MS>  blocks_manager_type;
00118     /** Type used to count bits in the bit vector */
00119     typedef bm::id_t                   size_type; 
00120 
00121     /** Statistical information about bitset's memory allocation details. */
00122     struct statistics : public bv_statistics
00123     {};
00124 
00125     /**
00126         @brief Class reference implements an object for bit assignment.
00127         Since C++ does not provide with build-in bit type supporting l-value 
00128         operations we have to emulate it.
00129 
00130         @ingroup bvector
00131     */
00132     class reference
00133     {
00134     public:
00135         reference(bvector<Alloc, MS>& bv, bm::id_t position) 
00136         : bv_(bv),
00137           position_(position)
00138         {}
00139 
00140         reference(const reference& ref)
00141         : bv_(ref.bv_), 
00142           position_(ref.position_)
00143         {
00144             bv_.set(position_, ref.bv_.get_bit(position_));
00145         }
00146         
00147         operator bool() const
00148         {
00149             return bv_.get_bit(position_);
00150         }
00151 
00152         const reference& operator=(const reference& ref) const
00153         {
00154             bv_.set(position_, (bool)ref);
00155             return *this;
00156         }
00157 
00158         const reference& operator=(bool value) const
00159         {
00160             bv_.set(position_, value);
00161             return *this;
00162         }
00163 
00164         bool operator==(const reference& ref) const
00165         {
00166             return bool(*this) == bool(ref);
00167         }
00168 
00169         /*! Bitwise AND. Performs operation: bit = bit AND value */
00170         const reference& operator&=(bool value) const
00171         {
00172             bv_.set_bit_and(position_, value);
00173             return *this;
00174         }
00175 
00176         /*! Bitwise OR. Performs operation: bit = bit OR value */
00177         const reference& operator|=(bool value) const
00178         {
00179             if (value != bv_.get_bit(position_))
00180             {
00181                 bv_.set_bit(position_);
00182             }
00183             return *this;
00184         }
00185 
00186         /*! Bitwise exclusive-OR (XOR). Performs operation: bit = bit XOR value */
00187         const reference& operator^=(bool value) const
00188         {
00189             bv_.set(position_, value != bv_.get_bit(position_));
00190             return *this;
00191         }
00192 
00193         /*! Logical Not operator */
00194         bool operator!() const
00195         {
00196             return !bv_.get_bit(position_);
00197         }
00198 
00199         /*! Bit Not operator */
00200         bool operator~() const
00201         {
00202             return !bv_.get_bit(position_);
00203         }
00204 
00205         /*! Negates the bit value */
00206         reference& flip()
00207         {
00208             bv_.flip(position_);
00209             return *this;
00210         }
00211 
00212     private:
00213         bvector<Alloc, MS>& bv_;       //!< Reference variable on the parent.
00214         bm::id_t            position_; //!< Position in the parent bitvector.
00215     };
00216 
00217     typedef bool const_reference;
00218 
00219     /*!
00220         @brief Base class for all iterators.
00221         @ingroup bvector
00222     */
00223     class iterator_base
00224     {
00225     friend class bvector;
00226     public:
00227         iterator_base() : bv_(0), position_(bm::id_max), block_(0) {}
00228 
00229         bool operator==(const iterator_base& it) const
00230         {
00231             return (position_ == it.position_) && (bv_ == it.bv_);
00232         }
00233 
00234         bool operator!=(const iterator_base& it) const
00235         {
00236             return ! operator==(it);
00237         }
00238 
00239         bool operator < (const iterator_base& it) const
00240         {
00241             return position_ < it.position_;
00242         }
00243 
00244         bool operator <= (const iterator_base& it) const
00245         {
00246             return position_ <= it.position_;
00247         }
00248 
00249         bool operator > (const iterator_base& it) const
00250         {
00251             return position_ > it.position_;
00252         }
00253 
00254         bool operator >= (const iterator_base& it) const
00255         {
00256             return position_ >= it.position_;
00257         }
00258 
00259         /**
00260            \fn bool bm::bvector::iterator_base::valid() const
00261            \brief Checks if iterator is still valid. Analog of != 0 comparison for pointers.
00262            \returns true if iterator is valid.
00263         */
00264         bool valid() const
00265         {
00266             return position_ != bm::id_max;
00267         }
00268 
00269         /**
00270            \fn bool bm::bvector::iterator_base::invalidate() 
00271            \brief Turns iterator into an invalid state.
00272         */
00273         void invalidate()
00274         {
00275             position_ = bm::id_max;
00276         }
00277 
00278     public:
00279 
00280         /** Information about current bitblock. */
00281         struct bitblock_descr
00282         {
00283             const bm::word_t*   ptr;      //!< Word pointer.
00284             unsigned            bits[32]; //!< Unpacked list of ON bits
00285             unsigned            idx;      //!< Current position in the bit list
00286             unsigned            cnt;      //!< Number of ON bits
00287             bm::id_t            pos;      //!< Last bit position before 
00288         };
00289 
00290         /** Information about current DGAP block. */
00291         struct dgap_descr
00292         {
00293             const gap_word_t*   ptr;       //!< Word pointer.
00294             gap_word_t          gap_len;   //!< Current dgap length.
00295         };
00296 
00297     protected:
00298         bm::bvector<Alloc, MS>* bv_;         //!< Pointer on parent bitvector
00299         bm::id_t                position_;   //!< Bit position (bit idx)
00300         const bm::word_t*       block_;      //!< Block pointer.(NULL-invalid)
00301         unsigned                block_type_; //!< Type of block. 0-Bit, 1-GAP
00302         unsigned                block_idx_;  //!< Block index
00303 
00304         /*! Block type dependent information for current block. */
00305         union block_descr
00306         {
00307             bitblock_descr   bit_;  //!< BitBlock related info.
00308             dgap_descr       gap_;  //!< DGAP block related info.
00309         } bdescr_;
00310     };
00311 
00312     /*!
00313         @brief Output iterator iterator designed to set "ON" bits based on
00314         input sequence of integers (bit indeces).
00315 
00316         STL container can be converted to bvector using this iterator
00317         Insert iterator guarantees the vector will be dynamically resized
00318         (set_bit does not do that).
00319 
00320         @note
00321         If you have many bits to set it is a good idea to use output iterator
00322         instead of explicitly calling set, because iterator may implement
00323         some performance specific tricks to make sure bulk insert is fast.
00324 
00325         @ingroup bvector
00326     */
00327     class insert_iterator
00328     {
00329     public:
00330 #ifndef BM_NO_STL
00331         typedef std::output_iterator_tag  iterator_category;
00332 #endif
00333         typedef unsigned value_type;
00334         typedef void difference_type;
00335         typedef void pointer;
00336         typedef void reference;
00337 
00338         insert_iterator(bvector<Alloc, MS>& bvect)
00339             : bvect_(bvect), 
00340               max_bit_(bvect.size())
00341         {
00342         }
00343         
00344         insert_iterator& operator=(bm::id_t n)
00345         {
00346             BM_ASSERT(n < bm::id_max);
00347 
00348             if (n >= max_bit_) 
00349             {
00350                 max_bit_ = n;
00351                 if (n >= bvect_.size()) 
00352                 {
00353                     bvect_.resize(n + 1);
00354                 }
00355             }
00356 
00357             bvect_.set(n);
00358             return *this;
00359         }
00360         
00361         /*! Returns *this without doing anything (no-op) */
00362         insert_iterator& operator*() { return *this; }
00363         /*! Returns *this. This iterator does not move (no-op) */
00364         insert_iterator& operator++() { return *this; }
00365         /*! Returns *this. This iterator does not move (no-op)*/
00366         insert_iterator& operator++(int) { return *this; }
00367         
00368     protected:
00369         bm::bvector<Alloc, MS>&   bvect_;
00370         bm::id_t                  max_bit_;
00371     };
00372 
00373     /*!
00374         @brief Constant input iterator designed to enumerate "ON" bits
00375         @ingroup bvector
00376     */
00377     class enumerator : public iterator_base
00378     {
00379     public:
00380 #ifndef BM_NO_STL
00381         typedef std::input_iterator_tag  iterator_category;
00382 #endif
00383         typedef unsigned   value_type;
00384         typedef unsigned   difference_type;
00385         typedef unsigned*  pointer;
00386         typedef unsigned&  reference;
00387 
00388     public:
00389         enumerator() : iterator_base() {}
00390         enumerator(const bvector<Alloc, MS>* bvect, int position)
00391             : iterator_base()
00392         { 
00393             this->bv_ = const_cast<bvector<Alloc, MS>*>(bvect);
00394             if (position == 0)
00395             {
00396                 go_first();
00397             }
00398             else
00399             {
00400                 this->invalidate();
00401             }
00402         }
00403 
00404         bm::id_t operator*() const
00405         { 
00406             return this->position_; 
00407         }
00408 
00409         enumerator& operator++()
00410         {
00411             return this->go_up();
00412         }
00413 
00414         enumerator operator++(int)
00415         {
00416             enumerator tmp = *this;
00417             this->go_up();
00418             return tmp;
00419         }
00420 
00421 
00422         void go_first()
00423         {
00424             BM_ASSERT(this->bv_);
00425 
00426         #ifdef BMCOUNTOPT
00427             if (this->bv_->count_is_valid_ && 
00428                 this->bv_->count_ == 0)
00429             {
00430                 this->invalidate();
00431                 return;
00432             }
00433         #endif
00434 
00435             blocks_manager_type* bman = &(this->bv_->blockman_);
00436             bm::word_t*** blk_root = bman->blocks_root();
00437 
00438             this->block_idx_ = this->position_= 0;
00439             unsigned i, j;
00440 
00441             for (i = 0; i < bman->top_block_size(); ++i)
00442             {
00443                 bm::word_t** blk_blk = blk_root[i];
00444 
00445                 if (blk_blk == 0) // not allocated
00446                 {
00447                     this->block_idx_ += bm::set_array_size;
00448                     this->position_ += bm::bits_in_array;
00449                     continue;
00450                 }
00451 
00452 
00453                 for (j = 0; j < bm::set_array_size; ++j,++(this->block_idx_))
00454                 {
00455                     this->block_ = blk_blk[j];
00456 
00457                     if (this->block_ == 0)
00458                     {
00459                         this->position_ += bits_in_block;
00460                         continue;
00461                     }
00462 
00463                     if (BM_IS_GAP((*bman), this->block_, this->block_idx_))
00464                     {
00465                         this->block_type_ = 1;
00466                         if (search_in_gapblock())
00467                         {
00468                             return;
00469                         }
00470                     }
00471                     else
00472                     {
00473                         this->block_type_ = 0;
00474                         if (search_in_bitblock())
00475                         {
00476                             return;
00477                         }
00478                     }
00479             
00480                 } // for j
00481 
00482             } // for i
00483 
00484             this->invalidate();
00485         }
00486 
00487         enumerator& go_up()
00488         {
00489             // Current block search.
00490             ++this->position_;
00491             typedef typename iterator_base::block_descr block_descr_type;
00492             
00493             block_descr_type* bdescr = &(this->bdescr_);
00494 
00495             switch (this->block_type_)
00496             {
00497             case 0:   //  BitBlock
00498                 {
00499 
00500                 // check if we can get the value from the 
00501                 // bits cache
00502 
00503                 unsigned idx = ++(bdescr->bit_.idx);
00504                 if (idx < bdescr->bit_.cnt)
00505                 {
00506                     this->position_ = bdescr->bit_.pos + 
00507                                       bdescr->bit_.bits[idx];
00508                     return *this; 
00509                 }
00510                 this->position_ += 31 - bdescr->bit_.bits[--idx];
00511 
00512                 const bm::word_t* pend = this->block_ + bm::set_block_size;
00513 
00514                 while (++(bdescr->bit_.ptr) < pend)
00515                 {
00516                     bm::word_t w = *(bdescr->bit_.ptr);
00517                     if (w)
00518                     {
00519                         bdescr->bit_.idx = 0;
00520                         bdescr->bit_.pos = this->position_;
00521                         bdescr->bit_.cnt = bm::bit_list(w, bdescr->bit_.bits); 
00522                         this->position_ += bdescr->bit_.bits[0];
00523                         return *this;
00524                     }
00525                     else
00526                     {
00527                         this->position_ += 32;
00528                     }
00529                 }
00530     
00531                 }
00532                 break;
00533 
00534             case 1:   // DGAP Block
00535                 {
00536                     if (--(bdescr->gap_.gap_len))
00537                     {
00538                         return *this;
00539                     }
00540 
00541                     // next gap is "OFF" by definition.
00542                     if (*(bdescr->gap_.ptr) == bm::gap_max_bits - 1)
00543                     {
00544                         break;
00545                     }
00546                     gap_word_t prev = *(bdescr->gap_.ptr);
00547                     register unsigned val = *(++(bdescr->gap_.ptr));
00548 
00549                     this->position_ += val - prev;
00550                     // next gap is now "ON"
00551 
00552                     if (*(bdescr->gap_.ptr) == bm::gap_max_bits - 1)
00553                     {
00554                         break;
00555                     }
00556                     prev = *(bdescr->gap_.ptr);
00557                     val = *(++(bdescr->gap_.ptr));
00558                     bdescr->gap_.gap_len = val - prev;
00559                     return *this;  // next "ON" found;
00560                 }
00561 
00562             default:
00563                 BM_ASSERT(0);
00564 
00565             } // switch
00566 
00567 
00568             // next bit not present in the current block
00569             // keep looking in the next blocks.
00570             ++(this->block_idx_);
00571             unsigned i = this->block_idx_ >> bm::set_array_shift;
00572             unsigned top_block_size = this->bv_->blockman_.top_block_size();
00573             for (; i < top_block_size; ++i)
00574             {
00575                 bm::word_t** blk_blk = this->bv_->blockman_.blocks_root()[i];
00576                 if (blk_blk == 0)
00577                 {
00578                     this->block_idx_ += bm::set_array_size;
00579                     this->position_ += bm::bits_in_array;
00580                     continue;
00581                 }
00582 
00583                 unsigned j = this->block_idx_ & bm::set_array_mask;
00584 
00585                 for(; j < bm::set_array_size; ++j, ++(this->block_idx_))
00586                 {
00587                     this->block_ = blk_blk[j];
00588 
00589                     if (this->block_ == 0)
00590                     {
00591                         this->position_ += bm::bits_in_block;
00592                         continue;
00593                     }
00594 
00595                     if (BM_IS_GAP((this->bv_->blockman_), 
00596                                    this->block_, 
00597                                    this->block_idx_))
00598                     {
00599                         this->block_type_ = 1;
00600                         if (search_in_gapblock())
00601                         {
00602                             return *this;
00603                         }
00604                     }
00605                     else
00606                     {
00607                         this->block_type_ = 0;
00608                         if (search_in_bitblock())
00609                         {
00610                             return *this;
00611                         }
00612                     }
00613 
00614             
00615                 } // for j
00616 
00617             } // for i
00618 
00619 
00620             this->invalidate();
00621             return *this;
00622         }
00623 
00624 
00625     private:
00626         bool search_in_bitblock()
00627         {
00628             BM_ASSERT(this->block_type_ == 0);
00629             
00630             typedef typename iterator_base::block_descr block_descr_type;
00631             block_descr_type* bdescr = &(this->bdescr_);            
00632 
00633             // now lets find the first bit in block.
00634             bdescr->bit_.ptr = this->block_;
00635 
00636             const word_t* ptr_end = this->block_ + bm::set_block_size;
00637 
00638             do
00639             {
00640                 register bm::word_t w = *(bdescr->bit_.ptr);
00641 
00642                 if (w)  
00643                 {
00644                     bdescr->bit_.idx = 0;
00645                     bdescr->bit_.pos = this->position_;
00646                     bdescr->bit_.cnt = 
00647                               bm::bit_list(w, bdescr->bit_.bits);
00648                     this->position_ += bdescr->bit_.bits[0];
00649 
00650                     return true;
00651                 }
00652                 else
00653                 {
00654                     this->position_ += 32;
00655                 }
00656 
00657             } 
00658             while (++(bdescr->bit_.ptr) < ptr_end);
00659 
00660             return false;
00661         }
00662 
00663         bool search_in_gapblock()
00664         {
00665             BM_ASSERT(this->block_type_ == 1);
00666 
00667             typedef typename iterator_base::block_descr block_descr_type;
00668             block_descr_type* bdescr = &(this->bdescr_);            
00669 
00670             bdescr->gap_.ptr = BMGAP_PTR(this->block_);
00671             unsigned bitval = *(bdescr->gap_.ptr) & 1;
00672 
00673             ++(bdescr->gap_.ptr);
00674 
00675             do
00676             {
00677                 register unsigned val = *(bdescr->gap_.ptr);
00678 
00679                 if (bitval)
00680                 {
00681                     gap_word_t* first = BMGAP_PTR(this->block_) + 1;
00682                     if (bdescr->gap_.ptr == first)
00683                     {
00684                         bdescr->gap_.gap_len = val + 1;
00685                     }
00686                     else
00687                     {
00688                         bdescr->gap_.gap_len = 
00689                              val - *(bdescr->gap_.ptr-1);
00690                     }
00691            
00692                     return true;
00693                 }
00694                 this->position_ += val + 1;
00695 
00696                 if (val == bm::gap_max_bits - 1)
00697                 {
00698                     break;
00699                 }
00700 
00701                 bitval ^= 1;
00702                 ++(bdescr->gap_.ptr);
00703 
00704             } while (1);
00705 
00706             return false;
00707         }
00708 
00709     };
00710     
00711     /*!
00712         @brief Constant input iterator designed to enumerate "ON" bits
00713         counted_enumerator keeps bitcount, ie number of ON bits starting
00714         from the position 0 in the bit string up to the currently enumerated bit
00715         
00716         When increment operator called current position is increased by 1.
00717         
00718         @ingroup bvector
00719     */
00720     class counted_enumerator : public enumerator
00721     {
00722     public:
00723 #ifndef BM_NO_STL
00724         typedef std::input_iterator_tag  iterator_category;
00725 #endif
00726         counted_enumerator() : bit_count_(0){}
00727         
00728         counted_enumerator(const enumerator& en)
00729         : enumerator(en)
00730         {
00731             if (this->valid())
00732                 bit_count_ = 1;
00733         }
00734         
00735         counted_enumerator& operator=(const enumerator& en)
00736         {
00737             enumerator* me = this;
00738             *me = en;
00739             if (this->valid())
00740                 this->bit_count_ = 1;
00741             return *this;
00742         }
00743         
00744         counted_enumerator& operator++()
00745         {
00746             this->go_up();
00747             if (this->valid())
00748                 ++(this->bit_count_);
00749             return *this;
00750         }
00751 
00752         counted_enumerator operator++(int)
00753         {
00754             counted_enumerator tmp(*this);
00755             this->go_up();
00756             if (this->valid())
00757                 ++bit_count_;
00758             return tmp;
00759         }
00760         
00761         /*! @brief Number of bits ON starting from the .
00762         
00763             Method returns number of ON bits fromn the bit 0 to the current bit 
00764             For the first bit in bitvector it is 1, for the second 2 
00765         */
00766         bm::id_t count() const { return bit_count_; }
00767         
00768     private:
00769         bm::id_t   bit_count_;
00770     };
00771 
00772     friend class iterator_base;
00773     friend class enumerator;
00774 
00775 public:
00776 
00777 #ifdef BMCOUNTOPT
00778     bvector(strategy          strat      = BM_BIT,
00779             const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
00780             size_type         bv_size    = bm::id_max,
00781             const Alloc&      alloc      = Alloc()) 
00782     : count_(0),
00783       count_is_valid_(true),
00784       blockman_(glevel_len, bv_size, alloc),
00785       new_blocks_strat_(strat),
00786       size_(bv_size)
00787     {}
00788 
00789     bvector(size_type         bv_size,
00790             bm::strategy      strat      = BM_BIT,
00791             const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
00792             const Alloc&      alloc = Alloc()) 
00793     : count_(0),
00794       count_is_valid_(true),
00795       blockman_(glevel_len, bv_size, alloc),
00796       new_blocks_strat_(strat),
00797       size_(bv_size)
00798     {}
00799 
00800 
00801     bvector(const bm::bvector<Alloc, MS>& bvect)
00802      : count_(bvect.count_),
00803        count_is_valid_(bvect.count_is_valid_),
00804        blockman_(bvect.blockman_),
00805        new_blocks_strat_(bvect.new_blocks_strat_),
00806        size_(bvect.size_)
00807     {}
00808 
00809 #else
00810     /*!
00811         \brief Constructs bvector class
00812         \param strat - operation mode strategy, 
00813                        BM_BIT - default strategy, bvector use plain bitset 
00814                        blocks, (performance oriented strategy).
00815                        BM_GAP - memory effitent strategy, bvector allocates 
00816                        blocks as array of intervals(gaps) and convert blocks 
00817                        into plain bitsets only when enthropy grows.
00818         \param glevel_len 
00819            - pointer on C-style array keeping GAP block sizes. 
00820             (Put bm::gap_len_table_min<true>::_len for GAP memory saving mode)
00821         \param bv_size 
00822           - bvector size (number of bits addressable by bvector), bm::id_max means 
00823           "no limits" (recommended). 
00824           bit vector allocates this space dynamically on demand.
00825 
00826         \sa bm::gap_len_table bm::gap_len_table_min set_new_blocks_strat
00827     */
00828     bvector(strategy          strat      = BM_BIT,
00829             const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
00830             size_type         bv_size    = bm::id_max,
00831             const Alloc&      alloc      = Alloc()) 
00832     : blockman_(glevel_len, bv_size, alloc),
00833       new_blocks_strat_(strat),
00834       size_(bv_size)
00835     {}
00836 
00837     /*!
00838         \brief Constructs bvector class
00839     */
00840     bvector(size_type         bv_size,
00841             strategy          strat      = BM_BIT,
00842             const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
00843             const Alloc&      alloc      = Alloc()) 
00844     : blockman_(glevel_len, bv_size, alloc),
00845       new_blocks_strat_(strat),
00846       size_(bv_size)
00847     {}
00848 
00849 
00850     bvector(const bvector<Alloc, MS>& bvect)
00851         :  blockman_(bvect.blockman_),
00852            new_blocks_strat_(bvect.new_blocks_strat_),
00853            size_(bvect.size_)
00854     {}
00855 
00856 #endif
00857 
00858     bvector& operator=(const bvector<Alloc, MS>& bvect)
00859     {
00860         clear(true); // memory free cleaning
00861         resize(bvect.size());
00862         bit_or(bvect);
00863         return *this;
00864     }
00865 
00866     reference operator[](bm::id_t n)
00867     {
00868         BM_ASSERT(n < size_);
00869         return reference(*this, n);
00870     }
00871 
00872 
00873     bool operator[](bm::id_t n) const
00874     {
00875         BM_ASSERT(n < size_);
00876         return get_bit(n);
00877     }
00878 
00879     void operator &= (const bvector<Alloc, MS>& bvect)
00880     {
00881         bit_and(bvect);
00882     }
00883 
00884     void operator ^= (const bvector<Alloc, MS>& bvect)
00885     {
00886         bit_xor(bvect);
00887     }
00888 
00889     void operator |= (const bvector<Alloc, MS>& bvect)
00890     {
00891         bit_or(bvect);
00892     }
00893 
00894     void operator -= (const bvector<Alloc, MS>& bvect)
00895     {
00896         bit_sub(bvect);
00897     }
00898 
00899     bool operator < (const bvector<Alloc, MS>& bvect) const
00900     {
00901         return compare(bvect) < 0;
00902     }
00903 
00904     bool operator <= (const bvector<Alloc, MS>& bvect) const
00905     {
00906         return compare(bvect) <= 0;
00907     }
00908 
00909     bool operator > (const bvector<Alloc, MS>& bvect) const
00910     {
00911         return compare(bvect) > 0;
00912     }
00913 
00914     bool operator >= (const bvector<Alloc, MS>& bvect) const
00915     {
00916         return compare(bvect) >= 0;
00917     }
00918 
00919     bool operator == (const bvector<Alloc, MS>& bvect) const
00920     {
00921         return compare(bvect) == 0;
00922     }
00923 
00924     bool operator != (const bvector<Alloc, MS>& bvect) const
00925     {
00926         return compare(bvect) != 0;
00927     }
00928 
00929     bvector<Alloc, MS> operator~() const
00930     {
00931         return bvector<Alloc, MS>(*this).invert();
00932     }
00933     
00934     Alloc get_allocator() const
00935     {
00936         return blockman_.get_allocator();
00937     }
00938 
00939 
00940     /*!
00941        \brief Sets bit n.
00942        \param n - index of the bit to be set. 
00943        \param val - new bit value
00944        \return  TRUE if bit was changed
00945     */
00946     bool set_bit(bm::id_t n, bool val = true)
00947     {
00948         BM_ASSERT(n < size_);
00949         return set_bit_no_check(n, val);
00950     }
00951 
00952     /*!
00953        \brief Sets bit n using bit AND with the provided value.
00954        \param n - index of the bit to be set. 
00955        \param val - new bit value
00956        \return  TRUE if bit was changed
00957     */
00958     bool set_bit_and(bm::id_t n, bool val = true)
00959     {
00960         BM_ASSERT(n < size_);
00961         return and_bit_no_check(n, val);
00962     }
00963 
00964     /*!
00965        \brief Sets bit n only if current value is equal to the condition
00966        \param n - index of the bit to be set. 
00967        \param val - new bit value
00968        \param condition - expected current value
00969        \return TRUE if bit was changed
00970     */
00971     bool set_bit_conditional(bm::id_t n, bool val, bool condition)
00972     {
00973         BM_ASSERT(n < size_);
00974         if (val == condition) return false;
00975         return set_bit_conditional_impl(n, val, condition);
00976     }
00977 
00978 
00979     /*!
00980         \brief Sets bit n if val is true, clears bit n if val is false
00981         \param n - index of the bit to be set
00982         \param val - new bit value
00983         \return *this
00984     */
00985     bvector<Alloc, MS>& set(bm::id_t n, bool val = true)
00986     {
00987         set_bit(n, val);
00988         return *this;
00989     }
00990 
00991 
00992 
00993     /*!
00994        \brief Sets every bit in this bitset to 1.
00995        \return *this
00996     */
00997     bvector<Alloc, MS>& set()
00998     {
00999         BMCOUNT_VALID(false)
01000         set_range(0, size_ - 1, true);
01001         return *this;
01002     }
01003 
01004 
01005     /*!
01006         \brief Sets all bits in the specified closed interval [left,right]
01007         Interval must be inside the bvector's size. 
01008         This method DOES NOT resize vector.
01009         
01010         \param left  - interval start
01011         \param right - interval end (closed interval)
01012         \param value - value to set interval in
01013         
01014         \return *this
01015     */
01016     bvector<Alloc, MS>& set_range(bm::id_t left,
01017                                   bm::id_t right,
01018                                   bool     value = true);
01019 
01020     
01021     /*! Function erturns insert iterator for this bitvector */
01022     insert_iterator inserter()
01023     {
01024         return insert_iterator(*this);
01025     }
01026 
01027 
01028     /*!
01029        \brief Clears bit n.
01030        \param n - bit's index to be cleaned.
01031     */
01032     void clear_bit(bm::id_t n)
01033     {
01034         set(n, false);
01035     }
01036 
01037 
01038     /*!
01039        \brief Clears every bit in the bitvector.
01040 
01041        \param free_mem if "true" (default) bvector frees the memory,
01042        otherwise sets blocks to 0.
01043     */
01044     void clear(bool free_mem = false)
01045     {
01046         blockman_.set_all_zero(free_mem);
01047         BMCOUNT_SET(0);
01048     }
01049 
01050     /*!
01051        \brief Clears every bit in the bitvector.
01052        \return *this;
01053     */
01054     bvector<Alloc, MS>& reset()
01055     {
01056         clear();
01057         return *this;
01058     }
01059 
01060 
01061     /*!
01062        \brief Returns count of bits which are 1.
01063        \return Total number of bits ON. 
01064     */
01065     bm::id_t count() const;
01066 
01067     /**
01068         \brief Returns bvector's capacity (number of bits it can store)
01069     */
01070     size_type capacity() const 
01071     {
01072         return blockman_.capacity();
01073     }
01074 
01075     /*!
01076         \brief return current size of the vector (bits)
01077     */
01078     size_type size() const 
01079     {
01080         return size_;
01081     }
01082 
01083     /*!
01084         \brief Change size of the bvector
01085         \param new_size - new size in bits
01086     */
01087     void resize(size_type new_size);
01088 
01089     /*! \brief Computes bitcount values for all bvector blocks
01090         \param arr - pointer on array of block bit counts
01091         \return Index of the last block counted. 
01092         This number +1 gives you number of arr elements initialized during the
01093         function call.
01094     */
01095     unsigned count_blocks(unsigned* arr) const
01096     {
01097         bm::word_t*** blk_root = blockman_.get_rootblock();
01098         typename blocks_manager_type::block_count_arr_func func(blockman_, &(arr[0]));
01099         for_each_nzblock(blk_root, blockman_.effective_top_block_size(), 
01100                                    bm::set_array_size, func);
01101         return func.last_block();
01102     }
01103 
01104     /*!
01105        \brief Returns count of 1 bits in the given diapason.
01106        \param left - index of first bit start counting from
01107        \param right - index of last bit 
01108        \param block_count_arr - optional parameter (bitcount by bvector blocks)
01109               calculated by count_blocks method. Used to improve performance of
01110               wide range searches
01111        \return Total number of bits ON. 
01112     */
01113     bm::id_t count_range(bm::id_t left, 
01114                          bm::id_t right, 
01115                          unsigned* block_count_arr=0) const;
01116 
01117 
01118     bm::id_t recalc_count()
01119     {
01120         BMCOUNT_VALID(false)
01121         return count();
01122     }
01123     
01124     /*!
01125         Disables count cache. Next call to count() or recalc_count()
01126         restores count caching.
01127         
01128         @note Works only if BMCOUNTOPT enabled(defined). 
01129         Othewise does nothing.
01130     */
01131     void forget_count()
01132     {
01133         BMCOUNT_VALID(false)    
01134     }
01135 
01136     /*!
01137         \brief Inverts all bits.
01138     */
01139     bvector<Alloc, MS>& invert();
01140 
01141 
01142     /*!
01143        \brief returns true if bit n is set and false is bit n is 0. 
01144        \param n - Index of the bit to check.
01145        \return Bit value (1 or 0)
01146     */
01147     bool get_bit(bm::id_t n) const;
01148 
01149     /*!
01150        \brief returns true if bit n is set and false is bit n is 0. 
01151        \param n - Index of the bit to check.
01152        \return Bit value (1 or 0)
01153     */
01154     bool test(bm::id_t n) const 
01155     { 
01156         return get_bit(n); 
01157     }
01158 
01159     /*!
01160        \brief Returns true if any bits in this bitset are set, and otherwise returns false.
01161        \return true if any bit is set
01162     */
01163     bool any() const
01164     {
01165     #ifdef BMCOUNTOPT
01166         if (count_is_valid_ && count_) return true;
01167     #endif
01168         
01169         word_t*** blk_root = blockman_.get_rootblock();
01170         if (!blk_root) 
01171             return false;
01172         typename blocks_manager_type::block_any_func func(blockman_);
01173         return for_each_nzblock_if(blk_root, 
01174                                    blockman_.effective_top_block_size(),
01175                                    bm::set_array_size, 
01176                                    func);
01177     }
01178 
01179     /*!
01180         \brief Returns true if no bits are set, otherwise returns false.
01181     */
01182     bool none() const
01183     {
01184         return !any();
01185     }
01186 
01187     /*!
01188        \brief Flips bit n
01189        \return *this
01190     */
01191     bvector<Alloc, MS>& flip(bm::id_t n) 
01192     {
01193         set(n, !get_bit(n));
01194         return *this;
01195     }
01196 
01197     /*!
01198        \brief Flips all bits
01199        \return *this
01200     */
01201     bvector<Alloc, MS>& flip() 
01202     {
01203         return invert();
01204     }
01205 
01206     /*! \brief Exchanges content of bv and this bitvector.
01207     */
01208     void swap(bvector<Alloc, MS>& bv)
01209     {
01210         if (this != &bv) 
01211         {
01212             blockman_.swap(bv.blockman_);
01213             bm::xor_swap(size_,bv.size_);
01214     #ifdef BMCOUNTOPT
01215             BMCOUNT_VALID(false)
01216             bv.recalc_count();
01217     #endif
01218         }
01219     }
01220 
01221 
01222     /*!
01223        \fn bm::id_t bvector::get_first() const
01224        \brief Gets number of first bit which is ON.
01225        \return Index of the first 1 bit.
01226        \sa get_next, extract_next
01227     */
01228     bm::id_t get_first() const { return check_or_next(0); }
01229 
01230     /*!
01231        \fn bm::id_t bvector::get_next(bm::id_t prev) const
01232        \brief Finds the number of the next bit ON.
01233        \param prev - Index of the previously found bit. 
01234        \return Index of the next bit which is ON or 0 if not found.
01235        \sa get_first, extract_next
01236     */
01237     bm::id_t get_next(bm::id_t prev) const
01238     {
01239         return (++prev == bm::id_max) ? 0 : check_or_next(prev);
01240     }
01241 
01242     /*!
01243        \fn bm::id_t bvector::extract_next(bm::id_t prev)
01244        \brief Finds the number of the next bit ON and sets it to 0.
01245        \param prev - Index of the previously found bit. 
01246        \return Index of the next bit which is ON or 0 if not found.
01247        \sa get_first, get_next, 
01248     */
01249     bm::id_t extract_next(bm::id_t prev)
01250     {
01251         return (++prev == bm::id_max) ? 0 : check_or_next_extract(prev);
01252     }
01253 
01254 
01255     /*!
01256        @brief Calculates bitvector statistics.
01257 
01258        @param st - pointer on statistics structure to be filled in. 
01259 
01260        Function fills statistics structure containing information about how 
01261        this vector uses memory and estimation of max. amount of memory 
01262        bvector needs to serialize itself.
01263 
01264        @sa statistics
01265     */
01266     void calc_stat(struct statistics* st) const;
01267 
01268     /*!
01269        \brief Logical OR operation.
01270        \param vect - Argument vector.
01271     */
01272     bm::bvector<Alloc, MS>& bit_or(const  bm::bvector<Alloc, MS>& vect)
01273     {
01274         BMCOUNT_VALID(false);
01275         combine_operation(vect, BM_OR);
01276         return *this;
01277     }
01278 
01279     /*!
01280        \brief Logical AND operation.
01281        \param vect - Argument vector.
01282     */
01283     bm::bvector<Alloc, MS>& bit_and(const bm::bvector<Alloc, MS>& vect)
01284     {
01285         BMCOUNT_VALID(false);
01286         combine_operation(vect, BM_AND);
01287         return *this;
01288     }
01289 
01290     /*!
01291        \brief Logical XOR operation.
01292        \param vect - Argument vector.
01293     */
01294     bm::bvector<Alloc, MS>& bit_xor(const bm::bvector<Alloc, MS>& vect)
01295     {
01296         BMCOUNT_VALID(false);
01297         combine_operation(vect, BM_XOR);
01298         return *this;
01299     }
01300 
01301     /*!
01302        \brief Logical SUB operation.
01303        \param vect - Argument vector.
01304     */
01305     bm::bvector<Alloc, MS>& bit_sub(const bm::bvector<Alloc, MS>& vect)
01306     {
01307         BMCOUNT_VALID(false);
01308         combine_operation(vect, BM_SUB);
01309         return *this;
01310     }
01311 
01312 
01313     /*!
01314        \brief Sets new blocks allocation strategy.
01315        \param strat - Strategy code 0 - bitblocks allocation only.
01316                       1 - Blocks mutation mode (adaptive algorithm)
01317     */
01318     void set_new_blocks_strat(strategy strat) 
01319     { 
01320         new_blocks_strat_ = strat; 
01321     }
01322 
01323     /*!
01324        \brief Returns blocks allocation strategy.
01325        \return - Strategy code 0 - bitblocks allocation only.
01326                  1 - Blocks mutation mode (adaptive algorithm)
01327        \sa set_new_blocks_strat
01328     */
01329     strategy  get_new_blocks_strat() const 
01330     { 
01331         return new_blocks_strat_; 
01332     }
01333 
01334     void stat(unsigned blocks=0) const;
01335 
01336     /*! 
01337         \brief Optimization mode
01338         Every next level means additional checks (better compression vs time)
01339         \sa optimize
01340     */
01341     enum optmode
01342     {
01343         opt_free_0    = 1, ///< Free unused 0 blocks
01344         opt_free_01   = 2, ///< Free unused 0 and 1 blocks
01345         opt_compress  = 3  ///< compress blocks when possible
01346     };
01347 
01348     /*!
01349        \brief Optimize memory bitvector's memory allocation.
01350    
01351        Function analyze all blocks in the bitvector, compresses blocks 
01352        with a regular structure, frees some memory. This function is recommended
01353        after a bulk modification of the bitvector using set_bit, clear_bit or
01354        logical operations.
01355 
01356        Optionally function can calculate vector post optimization statistics
01357        
01358        @sa optmode, optimize_gap_size
01359     */
01360     void optimize(bm::word_t* temp_block = 0, 
01361                   optmode opt_mode       = opt_compress,
01362                   statistics* stat       = 0);
01363 
01364     /*!
01365        \brief Optimize sizes of GAP blocks
01366 
01367        This method runs an analysis to find optimal GAP levels for the 
01368        specific vector. Current GAP compression algorithm uses several fixed
01369        GAP sizes. By default bvector uses some reasonable preset. 
01370     */
01371     void optimize_gap_size();
01372 
01373 
01374     /*!
01375         @brief Sets new GAP lengths table. All GAP blocks will be reallocated 
01376         to match the new scheme.
01377 
01378         @param glevel_len - pointer on C-style array keeping GAP block sizes. 
01379     */
01380     void set_gap_levels(const gap_word_t* glevel_len);
01381 
01382     /*!
01383         \brief Lexicographical comparison with a bitvector.
01384 
01385         Function compares current bitvector with the provided argument 
01386         bit by bit and returns -1 if our bitvector less than the argument, 
01387         1 - greater, 0 - equal.
01388     */
01389     int compare(const bvector<Alloc, MS>& bvect) const;
01390 
01391     /*! @brief Allocates temporary block of memory. 
01392 
01393         Temp block can be passed to bvector functions requiring some temp memory
01394         for their operation. (like serialize)
01395         
01396         @note method is marked const, but it's not quite true, since
01397         it can in some cases modify the state of the block allocator
01398         (if it has a state). (Can be important in MT programs).
01399 
01400         @sa free_tempblock
01401     */
01402     bm::word_t* allocate_tempblock() const
01403     {
01404         blocks_manager_type* bm = 
01405             const_cast<blocks_manager_type*>(&blockman_);
01406         return bm->get_allocator().alloc_bit_block();
01407     }
01408 
01409     /*! @brief Frees temporary block of memory. 
01410 
01411         @note method is marked const, but it's not quite true, since
01412         it can in some cases modify the state of the block allocator
01413         (if it has a state). (Can be important in MT programs).
01414 
01415         @sa allocate_tempblock
01416     */
01417     void free_tempblock(bm::word_t* block) const
01418     {
01419         blocks_manager_type* bm = 
01420             const_cast<blocks_manager_type*>(&blockman_);
01421         bm->get_allocator().free_bit_block(block);
01422     }
01423 
01424     /**
01425        \brief Returns enumerator pointing on the first non-zero bit.
01426     */
01427     enumerator first() const
01428     {
01429         typedef typename bvector<Alloc, MS>::enumerator enumerator_type;
01430         return enumerator_type(this, 0);
01431     }
01432 
01433     /**
01434        \fn bvector::enumerator bvector::end() const
01435        \brief Returns enumerator pointing on the next bit after the last.
01436     */
01437     enumerator end() const
01438     {
01439         typedef typename bvector<Alloc, MS>::enumerator enumerator_type;
01440         return enumerator_type(this, 1);
01441     }
01442 
01443 
01444     const bm::word_t* get_block(unsigned nb) const 
01445     { 
01446         return blockman_.get_block(nb); 
01447     }
01448     
01449     void combine_operation(const bm::bvector<Alloc, MS>& bvect, 
01450                             bm::operation                opcode);
01451     
01452 private:
01453 
01454     bm::id_t check_or_next(bm::id_t prev) const;
01455     
01456     /// check if specified bit is 1, and set it to 0
01457     /// if specified bit is 0, scan for the next 1 and returns it
01458     /// if no 1 found returns 0
01459     bm::id_t check_or_next_extract(bm::id_t prev);
01460 
01461     /**
01462         \brief Set specified bit without checking preconditions (size, etc)
01463     */
01464     bool set_bit_no_check(bm::id_t n, bool val);
01465 
01466     /**
01467         \brief AND specified bit without checking preconditions (size, etc)
01468     */
01469     bool and_bit_no_check(bm::id_t n, bool val);
01470 
01471     bool set_bit_conditional_impl(bm::id_t n, bool val, bool condition);
01472 
01473 
01474     void combine_operation_with_block(unsigned nb,
01475                                       unsigned gap,
01476                                       bm::word_t* blk,
01477                                       const bm::word_t* arg_blk,
01478                                       int arg_gap,
01479                                       bm::operation opcode);
01480 public:
01481     void combine_operation_with_block(unsigned nb,
01482                                       const bm::word_t* arg_blk,
01483                                       int arg_gap,
01484                                       bm::operation opcode)
01485     {
01486         bm::word_t* blk = const_cast<bm::word_t*>(get_block(nb));
01487         bool gap = BM_IS_GAP((*this), blk, nb);
01488         combine_operation_with_block(nb, gap, blk, arg_blk, arg_gap, opcode);
01489     }
01490 private:
01491     void combine_count_operation_with_block(unsigned nb,
01492                                             const bm::word_t* arg_blk,
01493                                             int arg_gap,
01494                                             bm::operation opcode)
01495     {
01496         const bm::word_t* blk = get_block(nb);
01497         bool gap = BM_IS_GAP((*this), blk, nb);
01498         combine_count_operation_with_block(nb, gap, blk, arg_blk, arg_gap, opcode);
01499     }
01500 
01501 
01502     /**
01503        \brief Extends GAP block to the next level or converts it to bit block.
01504        \param nb - Block's linear index.
01505        \param blk - Blocks's pointer 
01506     */
01507     void extend_gap_block(unsigned nb, gap_word_t* blk)
01508     {
01509         blockman_.extend_gap_block(nb, blk);
01510     }
01511 
01512     /**
01513        \brief Set range without validity checking
01514     */
01515     void set_range_no_check(bm::id_t left,
01516                             bm::id_t right,
01517                             bool     value);
01518 public:
01519 
01520     const blocks_manager_type& get_blocks_manager() const
01521     {
01522         return blockman_;
01523     }
01524 
01525     blocks_manager_type& get_blocks_manager()
01526     {
01527         return blockman_;
01528     }
01529 
01530 
01531 private:
01532 
01533 // This block defines two additional hidden variables used for bitcount
01534 // optimization, in rare cases can make bitvector thread unsafe.
01535 #ifdef BMCOUNTOPT
01536     mutable id_t      count_;            //!< number of 1 bits in the vector
01537     mutable bool      count_is_valid_;   //!< actualization flag
01538 #endif
01539 
01540     blocks_manager_type  blockman_;         //!< bitblocks manager
01541     strategy             new_blocks_strat_; //!< block allocation strategy
01542     size_type            size_;             //!< size in bits
01543 };
01544 
01545 
01546 
01547 
01548 
01549 //---------------------------------------------------------------------
01550 
01551 template<class Alloc, class MS> 
01552 inline bvector<Alloc, MS> operator& (const bvector<Alloc, MS>& v1,
01553                                      const bvector<Alloc, MS>& v2)
01554 {
01555 #ifdef BM_USE_EXPLICIT_TEMP
01556     bvector<Alloc, MS> ret(v1);
01557     ret.bit_and(v2);
01558     return ret;
01559 #else    
01560     return bvector<Alloc, MS>(v1).bit_and(v2);
01561 #endif
01562 }
01563 
01564 //---------------------------------------------------------------------
01565 
01566 template<class Alloc, class MS> 
01567 inline bvector<Alloc, MS> operator| (const bvector<Alloc, MS>& v1,
01568                                      const bvector<Alloc>& v2)
01569 {
01570 #ifdef BM_USE_EXPLICIT_TEMP
01571     bvector<Alloc, MS> ret(v1);
01572     ret.bit_or(v2);
01573     return ret;
01574 #else    
01575     return bvector<Alloc, MS>(v1).bit_or(v2);
01576 #endif
01577 }
01578 
01579 //---------------------------------------------------------------------
01580 
01581 template<class Alloc, class MS> 
01582 inline bvector<Alloc, MS> operator^ (const bvector<Alloc, MS>& v1,
01583                                      const bvector<Alloc, MS>& v2)
01584 {
01585 #ifdef BM_USE_EXPLICIT_TEMP
01586     bvector<Alloc, MS> ret(v1);
01587     ret.bit_xor(v2);
01588     return ret;
01589 #else    
01590     return bvector<Alloc, MS>(v1).bit_xor(v2);
01591 #endif
01592 }
01593 
01594 //---------------------------------------------------------------------
01595 
01596 template<class Alloc, class MS> 
01597 inline bvector<Alloc, MS> operator- (const bvector<Alloc, MS>& v1,
01598                                      const bvector<Alloc, MS>& v2)
01599 {
01600 #ifdef BM_USE_EXPLICIT_TEMP
01601     bvector<Alloc, MS> ret(v1);
01602     ret.bit_sub(v2);
01603     return ret;
01604 #else    
01605     return bvector<Alloc, MS>(v1).bit_sub(v2);
01606 #endif
01607 }
01608 
01609 
01610 
01611 
01612 // -----------------------------------------------------------------------
01613 
01614 template<typename Alloc, typename MS> 
01615 bvector<Alloc, MS>& bvector<Alloc, MS>::set_range(bm::id_t left,
01616                                                   bm::id_t right,
01617                                                   bool     value)
01618 {
01619     if (right < left)
01620     {
01621         return set_range(right, left, value);
01622     }
01623 
01624     BM_ASSERT(left < size_);
01625     BM_ASSERT(right < size_);
01626 
01627     BMCOUNT_VALID(false)
01628     BM_SET_MMX_GUARD
01629 
01630     set_range_no_check(left, right, value);
01631 
01632     return *this;
01633 }
01634 
01635 // -----------------------------------------------------------------------
01636 
01637 template<typename Alloc, typename MS> 
01638 bm::id_t bvector<Alloc, MS>::count() const
01639 {
01640 #ifdef BMCOUNTOPT
01641     if (count_is_valid_) return count_;
01642 #endif
01643     word_t*** blk_root = blockman_.get_rootblock();
01644     if (!blk_root) 
01645     {
01646         BMCOUNT_SET(0);
01647         return 0;
01648     }    
01649     typename blocks_manager_type::block_count_func func(blockman_);
01650     for_each_nzblock(blk_root, blockman_.effective_top_block_size(), 
01651                                 bm::set_array_size, func);
01652 
01653     BMCOUNT_SET(func.count());
01654     return func.count();
01655 }
01656 
01657 // -----------------------------------------------------------------------
01658 
01659 template<typename Alloc, typename MS> 
01660 void bvector<Alloc, MS>::resize(size_type new_size)
01661 {
01662     if (size_ == new_size) return; // nothing to do
01663     if (size_ < new_size) // size grows 
01664     {
01665         blockman_.reserve(new_size);
01666         size_ = new_size;
01667     }
01668     else // shrink
01669     {
01670         set_range(new_size, size_ - 1, false); // clear the tail
01671         size_ = new_size;
01672     }
01673 }
01674 
01675 // -----------------------------------------------------------------------
01676 
01677 template<typename Alloc, typename MS> 
01678 bm::id_t bvector<Alloc, MS>::count_range(bm::id_t left, 
01679                                          bm::id_t right, 
01680                                          unsigned* block_count_arr) const
01681 {
01682     BM_ASSERT(left <= right);
01683 
01684     unsigned count = 0;
01685 
01686     // calculate logical number of start and destination blocks
01687     unsigned nblock_left  = unsigned(left  >>  bm::set_block_shift);
01688     unsigned nblock_right = unsigned(right >>  bm::set_block_shift);
01689 
01690     const bm::word_t* block = blockman_.get_block(nblock_left);
01691     bool left_gap = BM_IS_GAP(blockman_, block, nblock_left);
01692 
01693     unsigned nbit_left  = unsigned(left  & bm::set_block_mask); 
01694     unsigned nbit_right = unsigned(right & bm::set_block_mask); 
01695 
01696     unsigned r = 
01697         (nblock_left == nblock_right) ? nbit_right : (bm::bits_in_block-1);
01698 
01699     typename blocks_manager_type::block_count_func func(blockman_);
01700 
01701     if (block)
01702     {
01703         if ((nbit_left == 0) && (r == (bm::bits_in_block-1))) // whole block
01704         {
01705             if (block_count_arr)
01706             {
01707                 count += block_count_arr[nblock_left];
01708             }
01709             else
01710             {
01711                 func(block, nblock_left);
01712             }
01713         }
01714         else
01715         {
01716             if (left_gap)
01717             {
01718                 count += gap_bit_count_range(BMGAP_PTR(block), 
01719                                             (gap_word_t)nbit_left,
01720                                             (gap_word_t)r);
01721             }
01722             else
01723             {
01724                 count += bit_block_calc_count_range(block, nbit_left, r);
01725             }
01726         }
01727     }
01728 
01729     if (nblock_left == nblock_right)  // in one block
01730     {
01731         return count + func.count();
01732     }
01733 
01734     for (unsigned nb = nblock_left+1; nb < nblock_right; ++nb)
01735     {
01736         block = blockman_.get_block(nb);
01737         if (block_count_arr)
01738         {
01739             count += block_count_arr[nb];
01740         }
01741         else 
01742         {
01743             if (block)
01744                 func(block, nb);
01745         }
01746     }
01747     count += func.count();
01748 
01749     block = blockman_.get_block(nblock_right);
01750     bool right_gap = BM_IS_GAP(blockman_, block, nblock_right);
01751 
01752     if (block)
01753     {
01754         if (right_gap)
01755         {
01756             count += gap_bit_count_range(BMGAP_PTR(block),
01757                                         (gap_word_t)0,
01758                                         (gap_word_t)nbit_right);
01759         }
01760         else
01761         {
01762             count += bit_block_calc_count_range(block, 0, nbit_right);
01763         }
01764     }
01765 
01766     return count;
01767 }
01768 
01769 // -----------------------------------------------------------------------
01770 
01771 template<typename Alloc, typename MS>
01772 bvector<Alloc, MS>& bvector<Alloc, MS>::invert()
01773 {
01774     BMCOUNT_VALID(false)
01775     BM_SET_MMX_GUARD
01776 
01777     bm::word_t*** blk_root = blockman_.get_rootblock();
01778     typename blocks_manager_type::block_invert_func func(blockman_);    
01779     for_each_block(blk_root, blockman_.top_block_size(),
01780                                 bm::set_array_size, func);
01781     if (size_ == bm::id_max) 
01782     {
01783         set_bit_no_check(bm::id_max, false);
01784     } 
01785     else
01786     {
01787         set_range_no_check(size_, bm::id_max, false);
01788     }
01789 
01790     return *this;
01791 }
01792 
01793 // -----------------------------------------------------------------------
01794 
01795 template<typename Alloc, typename MS> 
01796 bool bvector<Alloc, MS>::get_bit(bm::id_t n) const
01797 {    
01798     BM_ASSERT(n < size_);
01799 
01800     // calculate logical block number
01801     unsigned nblock = unsigned(n >>  bm::set_block_shift); 
01802 
01803     const bm::word_t* block = blockman_.get_block(nblock);
01804 
01805     if (block)
01806     {
01807         // calculate word number in block and bit
01808         unsigned nbit = unsigned(n & bm::set_block_mask); 
01809         unsigned is_set;
01810 
01811         if (BM_IS_GAP(blockman_, block, nblock))
01812         {
01813             is_set = gap_test(BMGAP_PTR(block), nbit);
01814         }
01815         else 
01816         {
01817             unsigned nword  = unsigned(nbit >> bm::set_word_shift); 
01818             nbit &= bm::set_word_mask;
01819 
01820             is_set = (block[nword] & (((bm::word_t)1) << nbit));
01821         }
01822         return is_set != 0;
01823     }
01824     return false;
01825 }
01826 
01827 // -----------------------------------------------------------------------
01828 
01829 template<typename Alloc, typename MS> 
01830 void bvector<Alloc, MS>::optimize(bm::word_t* temp_block, 
01831                                   optmode     opt_mode,
01832                                   statistics* stat)
01833 {
01834     word_t*** blk_root = blockman_.blocks_root();
01835 
01836     if (!temp_block)
01837         temp_block = blockman_.check_allocate_tempblock();
01838 
01839     typename 
01840         blocks_manager_type::block_opt_func  opt_func(blockman_, 
01841                                                 temp_block, 
01842                                                 (int)opt_mode,
01843                                                 stat);
01844     if (stat)
01845     {
01846         stat->bit_blocks = stat->gap_blocks 
01847                          = stat->max_serialize_mem 
01848                          = stat->memory_used 
01849                          = 0;
01850         ::memcpy(stat->gap_levels, 
01851                 blockman_.glen(), sizeof(gap_word_t) * bm::gap_levels);
01852         stat->max_serialize_mem = sizeof(id_t) * 4;
01853 
01854     }
01855 
01856     for_each_nzblock(blk_root, blockman_.effective_top_block_size(),
01857                                bm::set_array_size, opt_func);
01858 
01859     if (stat)
01860     {
01861         unsigned safe_inc = stat->max_serialize_mem / 10; // 10% increment
01862         if (!safe_inc) safe_inc = 256;
01863         stat->max_serialize_mem += safe_inc;
01864         stat->memory_used += sizeof(*this) - sizeof(blockman_);
01865         stat->memory_used += blockman_.mem_used();
01866     }
01867 }
01868 
01869 // -----------------------------------------------------------------------
01870 
01871 template<typename Alloc, typename MS> 
01872 void bvector<Alloc, MS>::optimize_gap_size()
01873 {
01874     struct bvector<Alloc, MS>::statistics st;
01875     calc_stat(&st);
01876 
01877     if (!st.gap_blocks)
01878         return;
01879 
01880     gap_word_t opt_glen[bm::gap_levels];
01881     ::memcpy(opt_glen, st.gap_levels, bm::gap_levels * sizeof(*opt_glen));
01882 
01883     improve_gap_levels(st.gap_length, 
01884                             st.gap_length + st.gap_blocks, 
01885                             opt_glen);
01886     
01887     set_gap_levels(opt_glen);
01888 }
01889 
01890 // -----------------------------------------------------------------------
01891 
01892 template<typename Alloc, typename MS> 
01893 void bvector<Alloc, MS>::set_gap_levels(const gap_word_t* glevel_len)
01894 {
01895     word_t*** blk_root = blockman_.blocks_root();
01896 
01897     typename 
01898         blocks_manager_type::gap_level_func  gl_func(blockman_, glevel_len);
01899 
01900     for_each_nzblock(blk_root, blockman_.top_block_size(),
01901                                 bm::set_array_size, gl_func);
01902 
01903     blockman_.set_glen(glevel_len);
01904 }
01905 
01906 // -----------------------------------------------------------------------
01907 
01908 template<typename Alloc, typename MS> 
01909 int bvector<Alloc, MS>::compare(const bvector<Alloc, MS>& bvect) const
01910 {
01911     int res;
01912     unsigned bn = 0;
01913 
01914     unsigned top_blocks = blockman_.effective_top_block_size();
01915     unsigned bvect_top_blocks = bvect.blockman_.effective_top_block_size();
01916 
01917     if (bvect_top_blocks > top_blocks) top_blocks = bvect_top_blocks;
01918 
01919     for (unsigned i = 0; i < top_blocks; ++i)
01920     {
01921         const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
01922         const bm::word_t* const* arg_blk_blk = 
01923                                 bvect.blockman_.get_topblock(i);
01924 
01925         if (blk_blk == arg_blk_blk) 
01926         {
01927             bn += bm::set_array_size;
01928             continue;
01929         }
01930 
01931         for (unsigned j = 0; j < bm::set_array_size; ++j, ++bn)
01932         {
01933             const bm::word_t* arg_blk = arg_blk_blk ? arg_blk_blk[j] : 0;
01934             const bm::word_t* blk = blk_blk ? blk_blk[j] : 0;
01935 
01936             if (blk == arg_blk) continue;
01937 
01938             // If one block is zero we check if the other one has at least 
01939             // one bit ON
01940 
01941             if (!blk || !arg_blk)  
01942             {
01943                 const bm::word_t*  pblk;
01944                 bool is_gap;
01945 
01946                 if (blk)
01947                 {
01948                     pblk = blk;
01949                     res = 1;
01950                     is_gap = BM_IS_GAP((*this), blk, bn);
01951                 }
01952                 else
01953                 {
01954                     pblk = arg_blk;
01955                     res = -1;
01956                     is_gap = BM_IS_GAP(bvect, arg_blk, bn);
01957                 }
01958 
01959                 if (is_gap)
01960                 {
01961                     if (!gap_is_all_zero(BMGAP_PTR(pblk), bm::gap_max_bits))
01962                     {
01963                         return res;
01964                     }
01965                 }
01966                 else
01967                 {
01968                     bm::wordop_t* blk1 = (wordop_t*)pblk;
01969                     bm::wordop_t* blk2 = 
01970                         (wordop_t*)(pblk + bm::set_block_size);
01971                     if (!bit_is_all_zero(blk1, blk2))
01972                     {
01973                         return res;
01974                     }
01975                 }
01976 
01977                 continue;
01978             }
01979 
01980             bool arg_gap = BM_IS_GAP(bvect, arg_blk, bn);
01981             bool gap = BM_IS_GAP((*this), blk, bn);
01982 
01983             if (arg_gap != gap)
01984             {
01985                 bm::wordop_t temp_blk[bm::set_block_size_op]; 
01986                 bm::wordop_t* blk1;
01987                 bm::wordop_t* blk2;
01988 
01989                 if (gap)
01990                 {
01991                     gap_convert_to_bitset((bm::word_t*)temp_blk, 
01992                                             BMGAP_PTR(blk));
01993 
01994                     blk1 = (bm::wordop_t*)temp_blk;
01995                     blk2 = (bm::wordop_t*)arg_blk;
01996                 }
01997                 else
01998                 {
01999                     gap_convert_to_bitset((bm::word_t*)temp_blk, 
02000                                             BMGAP_PTR(arg_blk));
02001 
02002                     blk1 = (bm::wordop_t*)blk;
02003                     blk2 = (bm::wordop_t*)temp_blk;
02004 
02005                 }                        
02006                 res = bitcmp(blk1, blk2, bm::set_block_size_op);  
02007 
02008             }
02009             else
02010             {
02011                 if (gap)
02012                 {
02013                     res = gapcmp(BMGAP_PTR(blk), BMGAP_PTR(arg_blk));
02014                 }
02015                 else
02016                 {
02017                     res = bitcmp((bm::wordop_t*)blk, 
02018                                     (bm::wordop_t*)arg_blk, 
02019                                     bm::set_block_size_op);
02020                 }
02021             }
02022 
02023             if (res != 0)
02024             {
02025                 return res;
02026             }
02027         
02028 
02029         } // for j
02030 
02031     } // for i
02032 
02033     return 0;
02034 }
02035 
02036 
02037 // -----------------------------------------------------------------------
02038 
02039 template<typename Alloc, typename MS> 
02040 void bvector<Alloc, MS>::calc_stat(typename bvector<Alloc, MS>::statistics* st) const
02041 {
02042     st->bit_blocks = st->gap_blocks 
02043                    = st->max_serialize_mem 
02044                    = st->memory_used = 0;
02045 
02046     ::memcpy(st->gap_levels, 
02047              blockman_.glen(), sizeof(gap_word_t) * bm::gap_levels);
02048 
02049     unsigned empty_blocks = 0;
02050     unsigned blocks_memory = 0;
02051     gap_word_t* gapl_ptr = st->gap_length;
02052 
02053     st->max_serialize_mem = sizeof(id_t) * 4;
02054 
02055     unsigned block_idx = 0;
02056 
02057     unsigned top_size = blockman_.effective_top_block_size();
02058     // Walk the blocks, calculate statistics.
02059     for (unsigned i = 0; i < top_size; ++i)
02060     {
02061         const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
02062 
02063         if (!blk_blk) 
02064         {
02065             block_idx += bm::set_array_size;
02066             st->max_serialize_mem += sizeof(unsigned) + 1;
02067             continue;
02068         }
02069 
02070         for (unsigned j = 0;j < bm::set_array_size; ++j, ++block_idx)
02071         {
02072             const bm::word_t* blk = blk_blk[j];
02073             if (IS_VALID_ADDR(blk))
02074             {
02075                 st->max_serialize_mem += empty_blocks << 2;
02076                 empty_blocks = 0;
02077 
02078                 if (BM_IS_GAP(blockman_, blk, block_idx)) // gap block
02079                 {
02080                     ++(st->gap_blocks);
02081 
02082                     bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
02083 
02084                     unsigned mem_used = 
02085                         bm::gap_capacity(gap_blk, blockman_.glen()) 
02086                         * sizeof(gap_word_t);
02087 
02088                     *gapl_ptr = gap_length(gap_blk);
02089 
02090                     st->max_serialize_mem += *gapl_ptr * sizeof(gap_word_t);
02091                     blocks_memory += mem_used;
02092 
02093                     ++gapl_ptr;
02094                 }
02095                 else // bit block
02096                 {
02097                     ++(st->bit_blocks);
02098                     unsigned mem_used = sizeof(bm::word_t) * bm::set_block_size;
02099                     st->max_serialize_mem += mem_used;
02100                     blocks_memory += mem_used;
02101                 }
02102             }
02103             else
02104             {
02105                 ++empty_blocks;
02106             }
02107         }
02108     }  
02109 
02110     unsigned safe_inc = st->max_serialize_mem / 10; // 10% increment
02111     if (!safe_inc) safe_inc = 256;
02112     st->max_serialize_mem += safe_inc;
02113 
02114     // Calc size of different odd and temporary things.
02115 
02116     st->memory_used += sizeof(*this) - sizeof(blockman_);
02117     st->memory_used += blockman_.mem_used();
02118     st->memory_used += blocks_memory;
02119 }
02120 
02121 
02122 // -----------------------------------------------------------------------
02123 
02124 
02125 template<class Alloc, class MS> 
02126 bool bvector<Alloc, MS>::set_bit_no_check(bm::id_t n, bool val)
02127 {
02128     // calculate logical block number
02129     unsigned nblock = unsigned(n >>  bm::set_block_shift); 
02130 
02131     int block_type;
02132 
02133     bm::word_t* blk = 
02134         blockman_.check_allocate_block(nblock, 
02135                                         val,
02136                                         get_new_blocks_strat(), 
02137                                         &block_type);
02138 
02139     if (!blk) return false;
02140 
02141     // calculate word number in block and bit
02142     unsigned nbit   = unsigned(n & bm::set_block_mask); 
02143 
02144     if (block_type == 1) // gap
02145     {
02146         unsigned is_set;
02147         unsigned new_block_len;
02148         
02149         new_block_len = 
02150             gap_set_value(val, BMGAP_PTR(blk), nbit, &is_set);
02151         if (is_set)
02152         {
02153             BMCOUNT_ADJ(val)
02154 
02155             unsigned threshold = 
02156             bm::gap_limit(BMGAP_PTR(blk), blockman_.glen());
02157 
02158             if (new_block_len > threshold) 
02159             {
02160                 extend_gap_block(nblock, BMGAP_PTR(blk));
02161             }
02162             return true;
02163         }
02164     }
02165     else  // bit block
02166     {
02167         unsigned nword  = unsigned(nbit >> bm::set_word_shift); 
02168         nbit &= bm::set_word_mask;
02169 
02170         bm::word_t* word = blk + nword;
02171         bm::word_t  mask = (((bm::word_t)1) << nbit);
02172 
02173         if (val)
02174         {
02175             if ( ((*word) & mask) == 0 )
02176             {
02177                 *word |= mask; // set bit
02178                 BMCOUNT_INC;
02179                 return true;
02180             }
02181         }
02182         else
02183         {
02184             if ((*word) & mask)
02185             {
02186                 *word &= ~mask; // clear bit
02187                 BMCOUNT_DEC;
02188                 return true;
02189             }
02190         }
02191     }
02192     return false;
02193 }
02194 
02195 // -----------------------------------------------------------------------
02196 
02197 template<class Alloc, class MS> 
02198 bool bvector<Alloc, MS>::set_bit_conditional_impl(bm::id_t n, 
02199                                                   bool     val, 
02200                                                   bool     condition)
02201 {
02202     // calculate logical block number
02203     unsigned nblock = unsigned(n >>  bm::set_block_shift); 
02204 
02205     int block_type;
02206     bm::word_t* blk = 
02207         blockman_.check_allocate_block(nblock, 
02208                                        val,
02209                                        get_new_blocks_strat(), 
02210                                        &block_type);
02211     if (!blk) 
02212         return false;
02213 
02214     // calculate word number in block and bit
02215     unsigned nbit   = unsigned(n & bm::set_block_mask); 
02216 
02217     if (block_type == 1) // gap
02218     {
02219         bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
02220         bool old_val = (gap_test(gap_blk, nbit) != 0);
02221 
02222         if (old_val != condition) 
02223         {
02224             return false;
02225         }
02226 
02227         if (val != old_val)
02228         {
02229             unsigned is_set;
02230             unsigned new_block_len = 
02231                 gap_set_value(val, gap_blk, nbit, &is_set);
02232             BM_ASSERT(is_set);
02233             BMCOUNT_ADJ(val)
02234 
02235             unsigned threshold = 
02236                 bm::gap_limit(gap_blk, blockman_.glen());
02237             if (new_block_len > threshold) 
02238             {
02239                 extend_gap_block(nblock, gap_blk);
02240             }
02241             return true;
02242         }
02243     }
02244     else  // bit block
02245     {
02246         unsigned nword  = unsigned(nbit >> bm::set_word_shift); 
02247         nbit &= bm::set_word_mask;
02248 
02249         bm::word_t* word = blk + nword;
02250         bm::word_t  mask = (((bm::word_t)1) << nbit);
02251         bool is_set = ((*word) & mask) != 0;
02252 
02253         if (is_set != condition)
02254         {
02255             return false;
02256         }
02257         if (is_set != val)    // need to change bit
02258         {
02259             if (val)          // set bit
02260             {
02261                 *word |= mask;
02262                 BMCOUNT_INC;
02263             }
02264             else               // clear bit
02265             {
02266                 *word &= ~mask;
02267                 BMCOUNT_DEC;
02268             }
02269             return true;
02270         }
02271     }
02272     return false;
02273 
02274 }
02275 
02276 // -----------------------------------------------------------------------
02277 
02278 
02279 template<class Alloc, class MS> 
02280 bool bvector<Alloc, MS>::and_bit_no_check(bm::id_t n, bool val)
02281 {
02282     // calculate logical block number
02283     unsigned nblock = unsigned(n >>  bm::set_block_shift); 
02284 
02285     int block_type;
02286     bm::word_t* blk = 
02287         blockman_.check_allocate_block(nblock, 
02288                                        val,
02289                                        get_new_blocks_strat(), 
02290                                        &block_type);
02291     if (!blk) return false;
02292 
02293     // calculate word number in block and bit
02294     unsigned nbit   = unsigned(n & bm::set_block_mask); 
02295 
02296     if (block_type == 1) // gap
02297     {
02298         bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
02299         bool old_val = (gap_test(gap_blk, nbit) != 0);
02300 
02301         bool new_val = val & old_val;
02302         if (new_val != old_val)
02303         {
02304             unsigned is_set;
02305             unsigned new_block_len = 
02306                 gap_set_value(new_val, gap_blk, nbit, &is_set);
02307             BM_ASSERT(is_set);
02308             BMCOUNT_ADJ(val)
02309 
02310             unsigned threshold = 
02311                 bm::gap_limit(gap_blk, blockman_.glen());
02312             if (new_block_len > threshold) 
02313             {
02314                 extend_gap_block(nblock, gap_blk);
02315             }
02316             return true;
02317         }
02318     }
02319     else  // bit block
02320     {
02321         unsigned nword  = unsigned(nbit >> bm::set_word_shift); 
02322         nbit &= bm::set_word_mask;
02323 
02324         bm::word_t* word = blk + nword;
02325         bm::word_t  mask = (((bm::word_t)1) << nbit);
02326         bool is_set = ((*word) & mask) != 0;
02327 
02328         bool new_val = is_set & val;
02329         if (new_val != val)    // need to change bit
02330         {
02331             if (new_val)       // set bit
02332             {
02333                 *word |= mask;
02334                 BMCOUNT_INC;
02335             }
02336             else               // clear bit
02337             {
02338                 *word &= ~mask;
02339                 BMCOUNT_DEC;
02340             }
02341             return true;
02342         }
02343     }
02344     return false;
02345 }
02346 
02347 
02348 // -----------------------------------------------------------------------
02349 
02350 template<class Alloc, class MS> 
02351 void bvector<Alloc, MS>::stat(unsigned blocks) const
02352 {
02353     register bm::id_t count = 0;
02354     int printed = 0;
02355 
02356     int total_gap_eff = 0;
02357 
02358     if (!blocks)
02359     {
02360         blocks = bm::set_total_blocks;
02361     }
02362 
02363     unsigned nb;
02364     for (nb = 0; nb < blocks; ++nb)
02365     {
02366         register const bm::word_t* blk = blockman_.get_block(nb);
02367 
02368         if (blk == 0)
02369         {
02370            continue;
02371         }
02372 
02373         if (IS_FULL_BLOCK(blk))
02374         {
02375            if (blockman_.is_block_gap(nb)) // gap block
02376            {
02377                printf("[Alert!%i]", nb);
02378                assert(0);
02379            }
02380            
02381            unsigned start = nb; 
02382            for(unsigned i = nb+1; i < bm::set_total_blocks; ++i, ++nb)
02383            {
02384                blk = blockman_.get_block(nb);
02385                if (IS_FULL_BLOCK(blk))
02386                {
02387                  if (blockman_.is_block_gap(nb)) // gap block
02388                  {
02389                      printf("[Alert!%i]", nb);
02390                      assert(0);
02391                      --nb;
02392                      break;
02393                  }
02394 
02395                }
02396                else
02397                {
02398                   --nb;
02399                   break;
02400                }
02401            }
02402 
02403            printf("{F.%i:%i}",start, nb);
02404            ++printed;
02405         }
02406         else
02407         {
02408             if (blockman_.is_block_gap(nb)) // gap block
02409             {
02410                unsigned bc = gap_bit_count(BMGAP_PTR(blk));
02411                /*unsigned sum = */gap_control_sum(BMGAP_PTR(blk));
02412                unsigned level = gap_level(BMGAP_PTR(blk));
02413                 count += bc;
02414                unsigned len = gap_length(BMGAP_PTR(blk))-1;
02415                unsigned raw_size=bc*2;
02416                unsigned cmr_len=len*2;
02417                int mem_eff = raw_size - cmr_len;
02418                total_gap_eff += mem_eff;
02419                
02420                unsigned i,j;
02421                blockman_.get_block_coord(nb, &i, &j);
02422                printf("[ GAP %i(%i,%i)=%i:%i-%i(%i) ]", nb, i, j, bc, level, len, mem_eff);
02423                 ++printed;
02424             }
02425             else // bitset
02426             {
02427                 const bm::word_t* blk_end = blk + bm::set_block_size;
02428                 unsigned bc = bit_block_calc_count(blk, blk_end);
02429 
02430                 unsigned zw = 0;
02431                 for (unsigned i = 0; i < bm::set_block_size; ++i) 
02432                 {
02433                     zw += (blk[i] == 0);
02434                 }
02435 
02436                 count += bc;
02437                 printf("( BIT %i=%i[%i] )", nb, bc, zw);
02438                 ++printed;
02439                 
02440             }
02441         }
02442         if (printed == 10)
02443         {
02444             printed = 0;
02445             printf("\n");
02446         }
02447     } // for nb
02448     printf("\n");
02449     printf("gap_efficiency=%i\n", total_gap_eff); 
02450 
02451 }
02452 
02453 //---------------------------------------------------------------------
02454 
02455 template<class Alloc, class MS> 
02456 bm::id_t bvector<Alloc, MS>::check_or_next(bm::id_t prev) const
02457 {
02458     for (;;)
02459     {
02460         unsigned nblock = unsigned(prev >> bm::set_block_shift); 
02461         if (nblock >= bm::set_total_blocks) 
02462             break;
02463 
02464         if (blockman_.is_subblock_null(nblock >> bm::set_array_shift))
02465         {
02466             prev += (bm::set_blkblk_mask + 1) -
02467                             (prev & bm::set_blkblk_mask);
02468         }
02469         else
02470         {
02471             unsigned nbit = unsigned(prev & bm::set_block_mask);
02472             int no_more_blocks;
02473             const bm::word_t* block = 
02474                 blockman_.get_block(nblock, &no_more_blocks);
02475 
02476             if (no_more_blocks) 
02477             {
02478                 BM_ASSERT(block == 0);
02479                 break;
02480             }
02481 
02482             if (block)
02483             {
02484                 if (IS_FULL_BLOCK(block)) return prev;
02485                 if (BM_IS_GAP(blockman_, block, nblock))
02486                 {
02487                     if (bm::gap_find_in_block(BMGAP_PTR(block),
02488                                                 nbit,
02489                                                 &prev))
02490                     {
02491                         return prev;
02492                     }
02493                 }
02494                 else
02495                 {
02496                     if (bm::bit_find_in_block(block, nbit, &prev)) 
02497                     {
02498                         return prev;
02499                     }
02500                 }
02501             }
02502             else
02503             {
02504                 prev += (bm::set_block_mask + 1) - 
02505                             (prev & bm::set_block_mask);
02506             }
02507 
02508         }
02509         if (!prev) break;
02510     }
02511 
02512     return 0;
02513 }
02514 
02515 
02516 //---------------------------------------------------------------------
02517 
02518 template<class Alloc, class MS> 
02519 bm::id_t bvector<Alloc, MS>::check_or_next_extract(bm::id_t prev)
02520 {
02521     for (;;)
02522     {
02523         unsigned nblock = unsigned(prev >> bm::set_block_shift); 
02524         if (nblock >= bm::set_total_blocks) break;
02525 
02526         if (blockman_.is_subblock_null(nblock >> bm::set_array_shift))
02527         {
02528             prev += (bm::set_blkblk_mask + 1) -
02529                             (prev & bm::set_blkblk_mask);
02530         }
02531         else
02532         {
02533             unsigned nbit = unsigned(prev & bm::set_block_mask);
02534 
02535             int no_more_blocks;
02536             bm::word_t* block = 
02537                 blockman_.get_block(nblock, &no_more_blocks);
02538 
02539             if (no_more_blocks) 
02540             {
02541                 BM_ASSERT(block == 0);
02542                 break;
02543             }
02544 
02545 
02546             if (block)
02547             {
02548                 if (IS_FULL_BLOCK(block))
02549                 {
02550                     set(prev, false);
02551                     return prev;
02552                 }
02553                 if (BM_IS_GAP(blockman_, block, nblock))
02554                 {
02555                     unsigned is_set;
02556                     unsigned new_block_len = 
02557                         gap_set_value(0, BMGAP_PTR(block), nbit, &is_set);
02558                     if (is_set) {
02559                         BMCOUNT_DEC
02560                         unsigned threshold = 
02561                             bm::gap_limit(BMGAP_PTR(block), blockman_.glen());
02562                         if (new_block_len > threshold) 
02563                         {
02564                             extend_gap_block(nblock, BMGAP_PTR(block));
02565                         }
02566                         return prev;
02567                     } else {
02568                         if (bm::gap_find_in_block(BMGAP_PTR(block),
02569                                                     nbit,
02570                                                     &prev))
02571                         {
02572                             set(prev, false);
02573                             return prev;
02574                         }
02575                     }
02576                 }
02577                 else // bit block
02578                 {
02579                     if (bm::bit_find_in_block(block, nbit, &prev)) 
02580                     {
02581                         BMCOUNT_DEC
02582 
02583                         unsigned nbit = 
02584                             unsigned(prev & bm::set_block_mask); 
02585                         unsigned nword = 
02586                             unsigned(nbit >> bm::set_word_shift);
02587                         nbit &= bm::set_word_mask;
02588                         bm::word_t* word = block + nword;
02589                         bm::word_t  mask = ((bm::word_t)1) << nbit;
02590                         *word &= ~mask;
02591 
02592                         return prev;
02593                     }
02594                 }
02595             }
02596             else
02597             {
02598                 prev += (bm::set_block_mask + 1) - 
02599                             (prev & bm::set_block_mask);
02600             }
02601 
02602         }
02603         if (!prev) break;
02604     }
02605 
02606     return 0;
02607 }
02608 
02609 //---------------------------------------------------------------------
02610 
02611 template<class Alloc, class MS> 
02612 void bvector<Alloc, MS>::combine_operation(
02613                                   const bm::bvector<Alloc, MS>& bvect, 
02614                                   bm::operation                 opcode)
02615 {
02616     typedef void (*block_bit_op)(bm::word_t*, const bm::word_t*);
02617     typedef void (*block_bit_op_next)(bm::word_t*, 
02618                                         const bm::word_t*, 
02619                                         bm::word_t*, 
02620                                         const bm::word_t*);
02621 
02622     unsigned top_blocks = blockman_.top_block_size();
02623     unsigned bvect_top_blocks = bvect.blockman_.top_block_size();
02624 
02625     if (size_ == bvect.size_) 
02626     {
02627         BM_ASSERT(top_blocks >= bvect_top_blocks);
02628     }
02629     else
02630     if (size_ < bvect.size_) // this vect shorter than the arg.
02631     {
02632         size_ = bvect.size_;
02633         // stretch our capacity
02634         blockman_.reserve_top_blocks(bvect_top_blocks);
02635         top_blocks = blockman_.top_block_size();
02636     }
02637     else 
02638     if (size_ > bvect.size_) // this vector larger
02639     {
02640         if (opcode == BM_AND) // clear the tail with zeros
02641         {
02642             set_range(bvect.size_, size_ - 1, false);
02643             if (bvect_top_blocks < top_blocks)
02644             {
02645                 // not to scan blocks we already swiped
02646                 top_blocks = bvect_top_blocks;
02647             }
02648         }
02649     }
02650     
02651     bm::word_t*** blk_root = blockman_.blocks_root();
02652     unsigned block_idx = 0;
02653     unsigned i, j;
02654 
02655     BM_SET_MMX_GUARD
02656 
02657     for (i = 0; i < top_blocks; ++i)
02658     {
02659         bm::word_t** blk_blk = blk_root[i];
02660 
02661         if (blk_blk == 0) // not allocated
02662         {
02663             const bm::word_t* const* bvbb = 
02664                             bvect.blockman_.get_topblock(i);
02665             if (bvbb == 0) 
02666             {
02667                 // skip it because 0 OP 0 = 0
02668                 block_idx += bm::set_array_size;
02669                 continue; 
02670             }
02671             // 0 - self, non-zero argument
02672             for (j = 0; j < bm::set_array_size; ++j,++block_idx)
02673             {
02674                 const bm::word_t* arg_blk = 
02675                     bvect.blockman_.get_block(i, j);
02676                 if (arg_blk != 0)
02677                 {
02678                     bool arg_gap = 
02679                         BM_IS_GAP(bvect.blockman_, arg_blk, block_idx);
02680                     combine_operation_with_block(block_idx, 0, 0, 
02681                                                 arg_blk, arg_gap, 
02682                                                 opcode);
02683                 }
02684 
02685             } // for j
02686             continue;
02687         }
02688 
02689         for (j = 0; j < bm::set_array_size; ++j, ++block_idx)
02690         {
02691             
02692             bm::word_t* blk = blk_blk[j];
02693             const bm::word_t* arg_blk = bvect.blockman_.get_block(i, j);
02694 
02695             if (arg_blk || blk)
02696             {
02697                 bool arg_gap = BM_IS_GAP(bvect.blockman_, arg_blk, block_idx);
02698                 bool gap = BM_IS_GAP((*this).blockman_, blk, block_idx);
02699                 
02700                 combine_operation_with_block(block_idx, gap, blk, 
02701                                             arg_blk, arg_gap,
02702                                             opcode);
02703             }
02704 
02705         } // for j
02706 
02707     } // for i
02708 
02709 }
02710 
02711 
02712 //---------------------------------------------------------------------
02713 
02714 
02715 template<class Alloc, class MS> 
02716 void bvector<Alloc, MS>::combine_operation_with_block(unsigned nb,
02717                                     unsigned gap,
02718                                     bm::word_t* blk,
02719                                     const bm::word_t* arg_blk,
02720                                     int arg_gap,
02721                                     bm::operation opcode)
02722 {
02723     if (!blk && arg_gap && get_new_blocks_strat() == BM_GAP) {
02724         blk = 
02725             blockman_.check_allocate_block(nb, 
02726                                         0,
02727                                         BM_GAP, 
02728                                         (int*)&gap,
02729                                         false /*no null return*/);
02730     }
02731 
02732         if (gap) // our block GAP-type
02733         {
02734             if (arg_gap)  // both blocks GAP-type
02735             {
02736                 gap_word_t tmp_buf[bm::gap_max_buff_len * 3]; // temporary result            
02737                 gap_word_t* res;
02738 
02739                 gap_operation_func_type gfunc = 
02740                     operation_functions<true>::gap_operation(opcode);
02741                 BM_ASSERT(gfunc);
02742                 res = (*gfunc)(BMGAP_PTR(blk), 
02743                                BMGAP_PTR(arg_blk), 
02744                                tmp_buf);
02745 /*
02746                 switch (opcode)
02747                 {
02748                 case BM_AND:
02749                     res = gap_operation_and(BMGAP_PTR(blk), 
02750                                             BMGAP_PTR(arg_blk), 
02751                                             tmp_buf);
02752                     break;
02753                 case BM_OR:
02754                     res = gap_operation_or(BMGAP_PTR(blk), 
02755                                         BMGAP_PTR(arg_blk), 
02756                                         tmp_buf);
02757                     break;
02758                 case BM_SUB:
02759                     res = gap_operation_sub(BMGAP_PTR(blk), 
02760                                             BMGAP_PTR(arg_blk), 
02761                                             tmp_buf);
02762                     break;
02763                 case BM_XOR:
02764                     res = gap_operation_xor(BMGAP_PTR(blk), 
02765                                             BMGAP_PTR(arg_blk), 
02766                                             tmp_buf);
02767                     break;
02768                 default:
02769                     assert(0);
02770                     res = 0;
02771                 }
02772 */
02773                 BM_ASSERT(res == tmp_buf);
02774                 unsigned res_len = bm::gap_length(res);
02775 
02776                 BM_ASSERT(!(res == tmp_buf && res_len == 0));
02777 
02778                 // if as a result of the operation gap block turned to zero
02779                 // we can now replace it with NULL
02780                 if (gap_is_all_zero(res, bm::gap_max_bits))
02781                 {
02782                     blockman_.set_block(nb, 0);
02783                     blockman_.set_block_bit(nb);
02784                     blockman_.get_allocator().free_gap_block(BMGAP_PTR(blk), 
02785                                                             blockman_.glen());
02786                     return;
02787                 }
02788 
02789                 // mutation check
02790 
02791                 int level = gap_level(BMGAP_PTR(blk));
02792                 unsigned threshold = blockman_.glen(level)-4;
02793                 int new_level = gap_calc_level(res_len, blockman_.glen());
02794 
02795                 if (new_level == -1)
02796                 {
02797                     blockman_.convert_gap2bitset(nb, res);
02798                     return;
02799                 }
02800 
02801                 if (res_len > threshold)
02802                 {
02803                     set_gap_level(res, new_level);
02804                     gap_word_t* new_blk = 
02805                         blockman_.allocate_gap_block(new_level, res);
02806 
02807                     bm::word_t* p = (bm::word_t*)new_blk;
02808                     BMSET_PTRGAP(p);
02809 
02810                     blockman_.set_block_ptr(nb, p);
02811                     blockman_.get_allocator().free_gap_block(BMGAP_PTR(blk), 
02812                                                             blockman_.glen());
02813                     return;
02814                 }
02815 
02816                 // gap opeartion result is in the temporary buffer
02817                 // we copy it back to the gap_block
02818 
02819                 set_gap_level(tmp_buf, level);
02820                 ::memcpy(BMGAP_PTR(blk), tmp_buf, res_len * sizeof(gap_word_t));
02821 
02822                 return;
02823             }
02824             else // argument is BITSET-type (own block is GAP)
02825             {
02826                 // since we can not combine blocks of mixed type
02827                 // we need to convert our block to bitset
02828                 
02829                 if (arg_blk == 0)  // Combining against an empty block
02830                 {
02831                     if (opcode == BM_OR  || 
02832                         opcode == BM_SUB || 
02833                         opcode == BM_XOR)
02834                     {
02835                         return; // nothing to do
02836                     }
02837                         
02838                     if (opcode == BM_AND) // ("Value" AND  0) == 0
02839                     {
02840                         blockman_.set_block_ptr(nb, 0);
02841                         blockman_.set_block_bit(nb);
02842                         blockman_.get_allocator().
02843                                         free_gap_block(BMGAP_PTR(blk),
02844                                                     blockman_.glen());
02845                         return;
02846                     }
02847                 }
02848 
02849                 blk = blockman_.convert_gap2bitset(nb, BMGAP_PTR(blk));
02850             }
02851         } 
02852         else // our block is BITSET-type
02853         {
02854             if (arg_gap) // argument block is GAP-type
02855             {
02856                 if (IS_VALID_ADDR(blk))
02857                 {
02858                     // special case, maybe we can do the job without 
02859                     // converting the GAP argument to bitblock
02860                     gap_operation_to_bitset_func_type gfunc = 
02861                         operation_functions<true>::gap_op_to_bit(opcode);
02862                     BM_ASSERT(gfunc);
02863                     (*gfunc)(blk, BMGAP_PTR(arg_blk));
02864                     return;
02865 /*
02866                     switch (opcode)
02867                     {
02868                     case BM_OR:
02869                             gap_add_to_bitset(blk, BMGAP_PTR(arg_blk));
02870                             return;                         
02871                     case BM_SUB:
02872                             gap_sub_to_bitset(blk, BMGAP_PTR(arg_blk));
02873                             return;
02874                     case BM_XOR:
02875                             gap_xor_to_bitset(blk, BMGAP_PTR(arg_blk));
02876                             return;
02877                     case BM_AND:
02878                             gap_and_to_bitset(blk, BMGAP_PTR(arg_blk));
02879                             return;                            
02880                     } // switch
02881 */
02882                 }
02883                 
02884                 // the worst case we need to convert argument block to 
02885                 // bitset type.
02886 
02887                 gap_word_t* temp_blk = (gap_word_t*) blockman_.check_allocate_tempblock();
02888                 arg_blk = 
02889                     gap_convert_to_bitset_smart((bm::word_t*)temp_blk, 
02890                                                 BMGAP_PTR(arg_blk), 
02891                                                 bm::gap_max_bits);
02892             
02893             }   
02894         }
02895     
02896         // Now here we combine two plain bitblocks using supplied bit function.
02897         bm::word_t* dst = blk;
02898 
02899         bm::word_t* ret; 
02900         if (dst == 0 && arg_blk == 0)
02901         {
02902             return;
02903         }
02904 
02905         switch (opcode)
02906         {
02907         case BM_AND:
02908             ret = bit_operation_and(dst, arg_blk);
02909             goto copy_block;
02910         case BM_XOR:
02911             ret = bit_operation_xor(dst, arg_blk);
02912             if (ret && (ret == arg_blk) && IS_FULL_BLOCK(dst))
02913             {
02914                 ret = blockman_.get_allocator().alloc_bit_block();
02915 #ifdef BMVECTOPT
02916             VECT_XOR_ARR_2_MASK(ret, 
02917                                 arg_blk, 
02918                                 arg_blk + bm::set_block_size, 
02919                                 bm::all_bits_mask);
02920 #else
02921                 bm::wordop_t* dst_ptr = (wordop_t*)ret;
02922                 const bm::wordop_t* wrd_ptr = (wordop_t*) arg_blk;
02923                 const bm::wordop_t* wrd_end = 
02924                 (wordop_t*) (arg_blk + bm::set_block_size);
02925 
02926                 do
02927                 {
02928                     dst_ptr[0] = bm::all_bits_mask ^ wrd_ptr[0];
02929                     dst_ptr[1] = bm::all_bits_mask ^ wrd_ptr[1];
02930                     dst_ptr[2] = bm::all_bits_mask ^ wrd_ptr[2];
02931                     dst_ptr[3] = bm::all_bits_mask ^ wrd_ptr[3];
02932 
02933                     dst_ptr+=4;
02934                     wrd_ptr+=4;
02935 
02936                 } while (wrd_ptr < wrd_end);
02937 #endif
02938                 break;
02939             }
02940             goto copy_block;
02941         case BM_OR:
02942             ret = bit_operation_or(dst, arg_blk);
02943         copy_block:
02944             if (ret && (ret == arg_blk) && !IS_FULL_BLOCK(ret))
02945             {
02946             ret = blockman_.get_allocator().alloc_bit_block();
02947             bit_block_copy(ret, arg_blk);
02948             }
02949             break;
02950 
02951         case BM_SUB:
02952             ret = bit_operation_sub(dst, arg_blk);
02953             if (ret && ret == arg_blk)
02954             {
02955                 ret = blockman_.get_allocator().alloc_bit_block();
02956 #ifdef BMVECTOPT
02957                 VECT_ANDNOT_ARR_2_MASK(ret, 
02958                                     arg_blk,
02959                                     arg_blk + bm::set_block_size,
02960                                     bm::all_bits_mask);
02961 #else
02962 
02963                 bm::wordop_t* dst_ptr = (wordop_t*)ret;
02964                 const bm::wordop_t* wrd_ptr = (wordop_t*) arg_blk;
02965                 const bm::wordop_t* wrd_end = 
02966                 (wordop_t*) (arg_blk + bm::set_block_size);
02967 
02968                 do
02969                 {
02970                     dst_ptr[0] = bm::all_bits_mask & ~wrd_ptr[0];
02971                     dst_ptr[1] = bm::all_bits_mask & ~wrd_ptr[1];
02972                     dst_ptr[2] = bm::all_bits_mask & ~wrd_ptr[2];
02973                     dst_ptr[3] = bm::all_bits_mask & ~wrd_ptr[3];
02974 
02975                     dst_ptr+=4;
02976                     wrd_ptr+=4;
02977 
02978                 } while (wrd_ptr < wrd_end);
02979 #endif
02980             }
02981             break;
02982         default:
02983             BM_ASSERT(0);
02984             ret = 0;
02985         }
02986 
02987         if (ret != dst) // block mutation
02988         {
02989             blockman_.set_block(nb, ret);
02990             blockman_.get_allocator().free_bit_block(dst);
02991         }
02992 }
02993 
02994 //---------------------------------------------------------------------
02995 
02996 template<class Alloc, class MS> 
02997 void bvector<Alloc, MS>::set_range_no_check(bm::id_t left,
02998                                             bm::id_t right,
02999                                             bool     value)
03000 {
03001     // calculate logical number of start and destination blocks
03002     unsigned nblock_left  = unsigned(left  >>  bm::set_block_shift);
03003     unsigned nblock_right = unsigned(right >>  bm::set_block_shift);
03004 
03005     bm::word_t* block = blockman_.get_block(nblock_left);
03006     bool left_gap = BM_IS_GAP(blockman_, block, nblock_left);
03007 
03008     unsigned nbit_left  = unsigned(left  & bm::set_block_mask); 
03009     unsigned nbit_right = unsigned(right & bm::set_block_mask); 
03010 
03011     unsigned r = 
03012         (nblock_left == nblock_right) ? nbit_right :(bm::bits_in_block-1);
03013 
03014         bm::gap_word_t tmp_gap_blk[5] = {0,};
03015 
03016     // Set bits in the starting block
03017 
03018     unsigned nb;
03019     if ((nbit_left == 0) && (r == bm::bits_in_block - 1)) // full block
03020     {
03021         nb = nblock_left;
03022     }
03023     else
03024     {
03025         gap_init_range_block(tmp_gap_blk,
03026                             nbit_left, r, value, bm::bits_in_block);
03027 
03028         combine_operation_with_block(nblock_left, 
03029                                     left_gap, 
03030                                     block,
03031                                     (bm::word_t*) tmp_gap_blk,
03032                                     1,
03033                                     value ? BM_OR : BM_AND);
03034 
03035         if (nblock_left == nblock_right)  // in one block
03036             return;
03037         nb = nblock_left+1;
03038     }
03039 
03040     // Set (or clear) all full blocks between left and right
03041     
03042     unsigned nb_to = nblock_right + (nbit_right ==(bm::bits_in_block-1));
03043             
03044     if (value)
03045     {
03046         for (; nb < nb_to; ++nb)
03047         {
03048             block = blockman_.get_block(nb);
03049             if (IS_FULL_BLOCK(block)) 
03050                 continue;
03051 
03052             bool is_gap = BM_IS_GAP(blockman_, block, nb);
03053 
03054             blockman_.set_block(nb, FULL_BLOCK_ADDR);
03055             blockman_.set_block_bit(nb);
03056             
03057             if (is_gap)
03058             {
03059                 blockman_.get_allocator().free_gap_block(BMGAP_PTR(block), 
03060                                                             blockman_.glen());
03061             }
03062             else
03063             {
03064                 blockman_.get_allocator().free_bit_block(block);
03065             }
03066             
03067         } // for
03068     }
03069     else // value == 0
03070     {
03071         for (; nb < nb_to; ++nb)
03072         {
03073             block = blockman_.get_block(nb);
03074             if (block == 0)  // nothing to do
03075                 continue;
03076             bool is_gap = BM_IS_GAP(blockman_, block, nb);
03077             blockman_.set_block(nb, 0, false /*bit*/);
03078             //blockman_.set_block_bit(nb);
03079 
03080             if (is_gap) 
03081             {
03082                 blockman_.get_allocator().free_gap_block(BMGAP_PTR(block),
03083                                                          blockman_.glen());
03084             }
03085             else
03086             {
03087                 blockman_.get_allocator().free_bit_block(block);
03088             }
03089 
03090         } // for
03091     } // if value else 
03092 
03093     if (nb_to > nblock_right)
03094         return;
03095 
03096     block = blockman_.get_block(nblock_right);
03097     bool right_gap = BM_IS_GAP(blockman_, block, nblock_right);
03098 
03099     gap_init_range_block(tmp_gap_blk, 
03100                             0, nbit_right, value, bm::bits_in_block);
03101 
03102     combine_operation_with_block(nblock_right, 
03103                                     right_gap, 
03104                                     block,
03105                                     (bm::word_t*) tmp_gap_blk,
03106                                     1,
03107                                     value ? BM_OR : BM_AND);
03108 
03109 }
03110 
03111 //---------------------------------------------------------------------
03112 
03113 
03114 } // namespace
03115 
03116 #include "bmundef.h"
03117 
03118 #ifdef _MSC_VER
03119 #pragma warning( default : 4311 4312)
03120 #endif
03121 
03122 
03123 #endif
03124 
03125 

Generated on Sun Aug 5 14:12:26 2007 for BitMagic by  doxygen 1.4.1