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

Generated on Thu Apr 20 13:28:46 2006 for BitMagic by  doxygen 1.4.1