vs10/bm/bm.h

Go to the documentation of this file.

#ifndef BM__H__INCLUDED__
#define BM__H__INCLUDED__
/*
Copyright(c) 2002-2010 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)

Permission is hereby granted, free of charge, to any person 
obtaining a copy of this software and associated documentation 
files (the "Software"), to deal in the Software without restriction, 
including without limitation the rights to use, copy, modify, merge, 
publish, distribute, sublicense, and/or sell copies of the Software, 
and to permit persons to whom the Software is furnished to do so, 
subject to the following conditions:

The above copyright notice and this permission notice shall be included 
in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 
DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 
OTHER DEALINGS IN THE SOFTWARE.

For more information please visit:  http://bmagic.sourceforge.net

*/


// define BM_NO_STL if you use BM in "STL free" environment and want
// to disable any references to STL headers
#ifndef BM_NO_STL
# include <iterator>
#endif

#ifdef _MSC_VER
#pragma warning( push )
#pragma warning( disable : 4311 4312 4127)
#endif


#ifdef BMSSE42OPT
# ifdef BM64OPT
#   undef BM64OPT
#   define BM64_SSE4
# endif
# undef BMSSE2OPT
#endif


#include "bmconst.h"
#include "bmdef.h"


#ifdef BMSSE42OPT
# define BMVECTOPT
# include "bmsse4.h"
#endif

#ifdef BMSSE2OPT
# undef BM64OPT
# define BMVECTOPT
# include "bmsse2.h"
#endif


#include "bmfwd.h"
#include "bmfunc.h"
#include "encoding.h"
#include "bmalloc.h"
#include "bmblocks.h"

namespace bm
{


#ifdef BMCOUNTOPT

# define BMCOUNT_INC ++count_;
# define BMCOUNT_DEC --count_;
# define BMCOUNT_VALID(x) count_is_valid_ = x;
# define BMCOUNT_SET(x) count_ = x; count_is_valid_ = true;
# define BMCOUNT_ADJ(x) if (x) ++count_; else --count_;

#else

# define BMCOUNT_INC
# define BMCOUNT_DEC
# define BMCOUNT_VALID(x)
# define BMCOUNT_SET(x)
# define BMCOUNT_ADJ(x)

#endif



//typedef bm::miniset<bm::block_allocator, bm::set_total_blocks> mem_save_set;


template<class Alloc> 
class bvector
{
public:

    typedef Alloc  allocator_type;
    typedef blocks_manager<Alloc>      blocks_manager_type;
    typedef bm::id_t                   size_type; 

    struct statistics : public bv_statistics
    {};

    class reference
    {
    public:
        reference(bvector<Alloc>& bv, bm::id_t position) 
        : bv_(bv),
          position_(position)
        {}

        reference(const reference& ref)
        : bv_(ref.bv_), 
          position_(ref.position_)
        {
            bv_.set(position_, ref.bv_.get_bit(position_));
        }
        
        operator bool() const
        {
            return bv_.get_bit(position_);
        }

        const reference& operator=(const reference& ref) const
        {
            bv_.set(position_, (bool)ref);
            return *this;
        }

        const reference& operator=(bool value) const
        {
            bv_.set(position_, value);
            return *this;
        }

        bool operator==(const reference& ref) const
        {
            return bool(*this) == bool(ref);
        }

        const reference& operator&=(bool value) const
        {
            bv_.set_bit_and(position_, value);
            return *this;
        }

        const reference& operator|=(bool value) const
        {
            if (value != bv_.get_bit(position_))
            {
                bv_.set_bit(position_);
            }
            return *this;
        }

        const reference& operator^=(bool value) const
        {
            bv_.set(position_, value != bv_.get_bit(position_));
            return *this;
        }

        bool operator!() const
        {
            return !bv_.get_bit(position_);
        }

        bool operator~() const
        {
            return !bv_.get_bit(position_);
        }

        reference& flip()
        {
            bv_.flip(position_);
            return *this;
        }

    private:
        bvector<Alloc>&   bv_;       
        bm::id_t          position_; 
    };

    typedef bool const_reference;

    class iterator_base
    {
    friend class bvector;
    public:
        iterator_base() : bv_(0), position_(bm::id_max), block_(0) {}

        bool operator==(const iterator_base& it) const
        {
            return (position_ == it.position_) && (bv_ == it.bv_);
        }

        bool operator!=(const iterator_base& it) const
        {
            return ! operator==(it);
        }

        bool operator < (const iterator_base& it) const
        {
            return position_ < it.position_;
        }

        bool operator <= (const iterator_base& it) const
        {
            return position_ <= it.position_;
        }

        bool operator > (const iterator_base& it) const
        {
            return position_ > it.position_;
        }

        bool operator >= (const iterator_base& it) const
        {
            return position_ >= it.position_;
        }

        bool valid() const
        {
            return position_ != bm::id_max;
        }

        void invalidate()
        {
            position_ = bm::id_max;
        }

    public:

        struct bitblock_descr
        {
            const bm::word_t*   ptr;      
            unsigned            bits[32]; 
            unsigned            idx;      
            unsigned            cnt;      
            bm::id_t            pos;      
        };

        struct dgap_descr
        {
            const gap_word_t*   ptr;       
            gap_word_t          gap_len;   
        };

    protected:
        bm::bvector<Alloc>*     bv_;         
        bm::id_t                position_;   
        const bm::word_t*       block_;      
        unsigned                block_type_; 
        unsigned                block_idx_;  

        union block_descr
        {
            bitblock_descr   bit_;  
            dgap_descr       gap_;  
        } bdescr_;
    };

    class insert_iterator
    {
    public:
#ifndef BM_NO_STL
        typedef std::output_iterator_tag  iterator_category;
#endif
        typedef unsigned value_type;
        typedef void difference_type;
        typedef void pointer;
        typedef void reference;

        insert_iterator(bvector<Alloc>& bvect)
            : bvect_(bvect), 
              max_bit_(bvect.size())
        {
        }
        
        insert_iterator& operator=(bm::id_t n)
        {
            BM_ASSERT(n < bm::id_max);

            if (n >= max_bit_) 
            {
                max_bit_ = n;
                if (n >= bvect_.size()) 
                {
                    bvect_.resize(n + 1);
                }
            }

            bvect_.set(n);
            return *this;
        }
        
        insert_iterator& operator*() { return *this; }
        insert_iterator& operator++() { return *this; }
        insert_iterator& operator++(int) { return *this; }
        
    protected:
        bm::bvector<Alloc>&   bvect_;
        bm::id_t              max_bit_;
    };

    class enumerator : public iterator_base
    {
    public:
#ifndef BM_NO_STL
        typedef std::input_iterator_tag  iterator_category;
#endif
        typedef unsigned   value_type;
        typedef unsigned   difference_type;
        typedef unsigned*  pointer;
        typedef unsigned&  reference;

    public:
        enumerator() : iterator_base() {}
        enumerator(const bvector<Alloc>* bvect, int position)
            : iterator_base()
        { 
            this->bv_ = const_cast<bvector<Alloc>*>(bvect);
            if (position == 0)
            {
                go_first();
            }
            else
            {
                this->invalidate();
            }
        }

        bm::id_t operator*() const
        { 
            return this->position_; 
        }

        bm::id_t value() const
        {
            return this->position_;
        }

        enumerator& operator++()
        {
            return this->go_up();
        }

        enumerator operator++(int)
        {
            enumerator tmp = *this;
            this->go_up();
            return tmp;
        }


        void go_first()
        {
            BM_ASSERT(this->bv_);

        #ifdef BMCOUNTOPT
            if (this->bv_->count_is_valid_ && 
                this->bv_->count_ == 0)
            {
                this->invalidate();
                return;
            }
        #endif

            blocks_manager_type* bman = &(this->bv_->blockman_);
            bm::word_t*** blk_root = bman->blocks_root();

            this->block_idx_ = this->position_= 0;
            unsigned i, j;

            for (i = 0; i < bman->top_block_size(); ++i)
            {
                bm::word_t** blk_blk = blk_root[i];

                if (blk_blk == 0) // not allocated
                {
                    this->block_idx_ += bm::set_array_size;
                    this->position_ += bm::bits_in_array;
                    continue;
                }


                for (j = 0; j < bm::set_array_size; ++j,++(this->block_idx_))
                {
                    this->block_ = blk_blk[j];

                    if (this->block_ == 0)
                    {
                        this->position_ += bits_in_block;
                        continue;
                    }

                    if (BM_IS_GAP(this->block_))
                    {
                        this->block_type_ = 1;
                        if (search_in_gapblock())
                        {
                            return;
                        }
                    }
                    else
                    {
                        this->block_type_ = 0;
                        if (search_in_bitblock())
                        {
                            return;
                        }
                    }
            
                } // for j

            } // for i

            this->invalidate();
        }

        enumerator& go_up()
        {
            // Current block search.
            ++this->position_;
            typedef typename iterator_base::block_descr block_descr_type;
            
            block_descr_type* bdescr = &(this->bdescr_);

            switch (this->block_type_)
            {
            case 0:   //  BitBlock
                {

                // check if we can get the value from the 
                // bits cache

                unsigned idx = ++(bdescr->bit_.idx);
                if (idx < bdescr->bit_.cnt)
                {
                    this->position_ = bdescr->bit_.pos + 
                                      bdescr->bit_.bits[idx];
                    return *this; 
                }
                this->position_ += 31 - bdescr->bit_.bits[--idx];

                const bm::word_t* pend = this->block_ + bm::set_block_size;

                while (++(bdescr->bit_.ptr) < pend)
                {
                    bm::word_t w = *(bdescr->bit_.ptr);
                    if (w)
                    {
                        bdescr->bit_.idx = 0;
                        bdescr->bit_.pos = this->position_;
                        bdescr->bit_.cnt = bm::bit_list_4(w, bdescr->bit_.bits); 
                        this->position_ += bdescr->bit_.bits[0];
                        return *this;
                    }
                    else
                    {
                        this->position_ += 32;
                    }
                }
    
                }
                break;

            case 1:   // DGAP Block
                {
                    if (--(bdescr->gap_.gap_len))
                    {
                        return *this;
                    }

                    // next gap is "OFF" by definition.
                    if (*(bdescr->gap_.ptr) == bm::gap_max_bits - 1)
                    {
                        break;
                    }
                    gap_word_t prev = *(bdescr->gap_.ptr);
                    unsigned int val = *(++(bdescr->gap_.ptr));

                    this->position_ += val - prev;
                    // next gap is now "ON"

                    if (*(bdescr->gap_.ptr) == bm::gap_max_bits - 1)
                    {
                        break;
                    }
                    prev = *(bdescr->gap_.ptr);
                    val = *(++(bdescr->gap_.ptr));
                    bdescr->gap_.gap_len = (gap_word_t)val - prev;
                    return *this;  // next "ON" found;
                }

            default:
                BM_ASSERT(0);

            } // switch


            // next bit not present in the current block
            // keep looking in the next blocks.
            ++(this->block_idx_);
            unsigned i = this->block_idx_ >> bm::set_array_shift;
            unsigned top_block_size = this->bv_->blockman_.top_block_size();
            for (; i < top_block_size; ++i)
            {
                bm::word_t** blk_blk = this->bv_->blockman_.blocks_root()[i];
                if (blk_blk == 0)
                {
                    this->block_idx_ += bm::set_array_size;
                    this->position_ += bm::bits_in_array;
                    continue;
                }

                unsigned j = this->block_idx_ & bm::set_array_mask;

                for(; j < bm::set_array_size; ++j, ++(this->block_idx_))
                {
                    this->block_ = blk_blk[j];

                    if (this->block_ == 0)
                    {
                        this->position_ += bm::bits_in_block;
                        continue;
                    }

                    if (BM_IS_GAP(this->block_))
                    {
                        this->block_type_ = 1;
                        if (search_in_gapblock())
                        {
                            return *this;
                        }
                    }
                    else
                    {
                        this->block_type_ = 0;
                        if (search_in_bitblock())
                        {
                            return *this;
                        }
                    }

            
                } // for j

            } // for i


            this->invalidate();
            return *this;
        }


    private:
        bool search_in_bitblock()
        {
            BM_ASSERT(this->block_type_ == 0);
            
            typedef typename iterator_base::block_descr block_descr_type;
            block_descr_type* bdescr = &(this->bdescr_);            

            // now lets find the first bit in block.
            bdescr->bit_.ptr = this->block_;

            const word_t* ptr_end = this->block_ + bm::set_block_size;

            do
            {
                register bm::word_t w = *(bdescr->bit_.ptr);

                if (w)  
                {
                    bdescr->bit_.idx = 0;
                    bdescr->bit_.pos = this->position_;
                    bdescr->bit_.cnt = 
                              bm::bit_list_4(w, bdescr->bit_.bits);
                    this->position_ += bdescr->bit_.bits[0];

                    return true;
                }
                else
                {
                    this->position_ += 32;
                }

            } 
            while (++(bdescr->bit_.ptr) < ptr_end);

            return false;
        }

        bool search_in_gapblock()
        {
            BM_ASSERT(this->block_type_ == 1);

            typedef typename iterator_base::block_descr block_descr_type;
            block_descr_type* bdescr = &(this->bdescr_);            

            bdescr->gap_.ptr = BMGAP_PTR(this->block_);
            unsigned bitval = *(bdescr->gap_.ptr) & 1;

            ++(bdescr->gap_.ptr);

            for (;true;)
            {
                register unsigned val = *(bdescr->gap_.ptr);

                if (bitval)
                {
                    gap_word_t* first = BMGAP_PTR(this->block_) + 1;
                    if (bdescr->gap_.ptr == first)
                    {
                        bdescr->gap_.gap_len = (gap_word_t)val + 1;
                    }
                    else
                    {
                        bdescr->gap_.gap_len = 
                             (gap_word_t)(val - *(bdescr->gap_.ptr-1));
                    }
           
                    return true;
                }
                this->position_ += val + 1;

                if (val == bm::gap_max_bits - 1)
                {
                    break;
                }

                bitval ^= 1;
                ++(bdescr->gap_.ptr);

            }

            return false;
        }

    };
    
    class counted_enumerator : public enumerator
    {
    public:
#ifndef BM_NO_STL
        typedef std::input_iterator_tag  iterator_category;
#endif
        counted_enumerator() : bit_count_(0){}
        
        counted_enumerator(const enumerator& en)
        : enumerator(en)
        {
            if (this->valid())
                bit_count_ = 1;
        }
        
        counted_enumerator& operator=(const enumerator& en)
        {
            enumerator* me = this;
            *me = en;
            if (this->valid())
                this->bit_count_ = 1;
            return *this;
        }
        
        counted_enumerator& operator++()
        {
            this->go_up();
            if (this->valid())
                ++(this->bit_count_);
            return *this;
        }

        counted_enumerator operator++(int)
        {
            counted_enumerator tmp(*this);
            this->go_up();
            if (this->valid())
                ++bit_count_;
            return tmp;
        }
        
        bm::id_t count() const { return bit_count_; }
        
    private:
        bm::id_t   bit_count_;
    };

    friend class iterator_base;
    friend class enumerator;

public:

#ifdef BMCOUNTOPT
    bvector(strategy          strat      = BM_BIT,
            const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
            size_type         bv_size    = bm::id_max,
            const Alloc&      alloc      = Alloc()) 
    : count_(0),
      count_is_valid_(true),
      blockman_(glevel_len, bv_size, alloc),
      new_blocks_strat_(strat),
      size_(bv_size)
    {}

    bvector(size_type         bv_size,
            bm::strategy      strat      = BM_BIT,
            const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
            const Alloc&      alloc = Alloc()) 
    : count_(0),
      count_is_valid_(true),
      blockman_(glevel_len, bv_size, alloc),
      new_blocks_strat_(strat),
      size_(bv_size)
    {}


    bvector(const bm::bvector<Alloc>& bvect)
     : count_(bvect.count_),
       count_is_valid_(bvect.count_is_valid_),
       blockman_(bvect.blockman_),
       new_blocks_strat_(bvect.new_blocks_strat_),
       size_(bvect.size_)
    {}

#else

    bvector(strategy          strat      = BM_BIT,
            const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
            size_type         bv_size    = bm::id_max,
            const Alloc&      alloc      = Alloc()) 
    : blockman_(glevel_len, bv_size, alloc),
      new_blocks_strat_(strat),
      size_(bv_size)
    {}

    bvector(size_type         bv_size,
            strategy          strat      = BM_BIT,
            const gap_word_t* glevel_len = bm::gap_len_table<true>::_len,
            const Alloc&      alloc      = Alloc()) 
    : blockman_(glevel_len, bv_size, alloc),
      new_blocks_strat_(strat),
      size_(bv_size)
    {}


    bvector(const bvector<Alloc>& bvect)
        :  blockman_(bvect.blockman_),
           new_blocks_strat_(bvect.new_blocks_strat_),
           size_(bvect.size_)
    {}

#endif

    bvector& operator=(const bvector<Alloc>& bvect)
    {
        clear(true); // memory free cleaning
        resize(bvect.size());
        bit_or(bvect);
        return *this;
    }

    reference operator[](bm::id_t n)
    {
        BM_ASSERT(n < size_);
        return reference(*this, n);
    }


    bool operator[](bm::id_t n) const
    {
        BM_ASSERT(n < size_);
        return get_bit(n);
    }

    void operator &= (const bvector<Alloc>& bvect)
    {
        bit_and(bvect);
    }

    void operator ^= (const bvector<Alloc>& bvect)
    {
        bit_xor(bvect);
    }

    void operator |= (const bvector<Alloc>& bvect)
    {
        bit_or(bvect);
    }

    void operator -= (const bvector<Alloc>& bvect)
    {
        bit_sub(bvect);
    }

    bool operator < (const bvector<Alloc>& bvect) const
    {
        return compare(bvect) < 0;
    }

    bool operator <= (const bvector<Alloc>& bvect) const
    {
        return compare(bvect) <= 0;
    }

    bool operator > (const bvector<Alloc>& bvect) const
    {
        return compare(bvect) > 0;
    }

    bool operator >= (const bvector<Alloc>& bvect) const
    {
        return compare(bvect) >= 0;
    }

    bool operator == (const bvector<Alloc>& bvect) const
    {
        return compare(bvect) == 0;
    }

    bool operator != (const bvector<Alloc>& bvect) const
    {
        return compare(bvect) != 0;
    }

    bvector<Alloc> operator~() const
    {
        return bvector<Alloc>(*this).invert();
    }
    
    Alloc get_allocator() const
    {
        return blockman_.get_allocator();
    }


    bool set_bit(bm::id_t n, bool val = true)
    {
        BM_ASSERT(n < size_);
        return set_bit_no_check(n, val);
    }

    bool set_bit_and(bm::id_t n, bool val = true)
    {
        BM_ASSERT(n < size_);
        return and_bit_no_check(n, val);
    }

    bool set_bit_conditional(bm::id_t n, bool val, bool condition)
    {
        BM_ASSERT(n < size_);
        if (val == condition) return false;
        return set_bit_conditional_impl(n, val, condition);
    }


    bvector<Alloc>& set(bm::id_t n, bool val = true)
    {
        set_bit(n, val);
        return *this;
    }



    bvector<Alloc>& set()
    {
        BMCOUNT_VALID(false)
        set_range(0, size_ - 1, true);
        return *this;
    }


    bvector<Alloc>& set_range(bm::id_t left,
                              bm::id_t right,
                              bool     value = true);

    
    insert_iterator inserter()
    {
        return insert_iterator(*this);
    }


    void clear_bit(bm::id_t n)
    {
        set(n, false);
    }


    void clear(bool free_mem = false)
    {
        blockman_.set_all_zero(free_mem);
        BMCOUNT_SET(0);
    }

    bvector<Alloc>& reset()
    {
        clear();
        return *this;
    }


    bm::id_t count() const;

    size_type capacity() const 
    {
        return blockman_.capacity();
    }

    size_type size() const 
    {
        return size_;
    }

    void resize(size_type new_size);

    unsigned count_blocks(unsigned* arr) const
    {
        bm::word_t*** blk_root = blockman_.get_rootblock();
        typename blocks_manager_type::block_count_arr_func func(blockman_, &(arr[0]));
        for_each_nzblock(blk_root, blockman_.effective_top_block_size(), 
                         func);
        return func.last_block();
    }

    bm::id_t count_range(bm::id_t left, 
                         bm::id_t right, 
                         unsigned* block_count_arr=0) const;


    bm::id_t recalc_count()
    {
        BMCOUNT_VALID(false)
        return count();
    }
    
    void forget_count()
    {
        BMCOUNT_VALID(false)    
    }

    bvector<Alloc>& invert();


    bool get_bit(bm::id_t n) const;

    bool test(bm::id_t n) const 
    { 
        return get_bit(n); 
    }

    bool any() const
    {
    #ifdef BMCOUNTOPT
        if (count_is_valid_ && count_) return true;
    #endif
        
        word_t*** blk_root = blockman_.get_rootblock();
        if (!blk_root) 
            return false;
        typename blocks_manager_type::block_any_func func(blockman_);
        return for_each_nzblock_if(blk_root, 
                                   blockman_.effective_top_block_size(),
                                   func);
    }

    bool none() const
    {
        return !any();
    }

    bvector<Alloc>& flip(bm::id_t n) 
    {
        set(n, !get_bit(n));
        return *this;
    }

    bvector<Alloc>& flip() 
    {
        return invert();
    }

    void swap(bvector<Alloc>& bv)
    {
        if (this != &bv) 
        {
            blockman_.swap(bv.blockman_);
            bm::xor_swap(size_,bv.size_);
    #ifdef BMCOUNTOPT
            BMCOUNT_VALID(false)
            bv.recalc_count();
    #endif
        }
    }


    bm::id_t get_first() const { return check_or_next(0); }

    bm::id_t get_next(bm::id_t prev) const
    {
        return (++prev == bm::id_max) ? 0 : check_or_next(prev);
    }

    bm::id_t extract_next(bm::id_t prev)
    {
        return (++prev == bm::id_max) ? 0 : check_or_next_extract(prev);
    }


    void calc_stat(struct bm::bvector<Alloc>::statistics* st) const;

    bm::bvector<Alloc>& bit_or(const  bm::bvector<Alloc>& vect)
    {
        BMCOUNT_VALID(false);
        combine_operation(vect, BM_OR);
        return *this;
    }

    bm::bvector<Alloc>& bit_and(const bm::bvector<Alloc>& vect)
    {
        BMCOUNT_VALID(false);
        combine_operation(vect, BM_AND);
        return *this;
    }

    bm::bvector<Alloc>& bit_xor(const bm::bvector<Alloc>& vect)
    {
        BMCOUNT_VALID(false);
        combine_operation(vect, BM_XOR);
        return *this;
    }

    bm::bvector<Alloc>& bit_sub(const bm::bvector<Alloc>& vect)
    {
        BMCOUNT_VALID(false);
        combine_operation(vect, BM_SUB);
        return *this;
    }


    void set_new_blocks_strat(strategy strat) 
    { 
        new_blocks_strat_ = strat; 
    }

    strategy  get_new_blocks_strat() const 
    { 
        return new_blocks_strat_; 
    }


    enum optmode
    {
        opt_free_0    = 1, 
        opt_free_01   = 2, 
        opt_compress  = 3  
    };

    void optimize(bm::word_t* temp_block = 0, 
                  optmode opt_mode       = opt_compress,
                  statistics* stat       = 0);

    void optimize_gap_size();


    void set_gap_levels(const gap_word_t* glevel_len);

    int compare(const bvector<Alloc>& bvect) const;

    bm::word_t* allocate_tempblock() const
    {
        blocks_manager_type* bm = 
            const_cast<blocks_manager_type*>(&blockman_);
        return bm->get_allocator().alloc_bit_block();
    }

    void free_tempblock(bm::word_t* block) const
    {
        blocks_manager_type* bm = 
            const_cast<blocks_manager_type*>(&blockman_);
        bm->get_allocator().free_bit_block(block);
    }

    enumerator first() const
    {
        typedef typename bvector<Alloc>::enumerator enumerator_type;
        return enumerator_type(this, 0);
    }

    enumerator end() const
    {
        typedef typename bvector<Alloc>::enumerator enumerator_type;
        return enumerator_type(this, 1);
    }


    const bm::word_t* get_block(unsigned nb) const 
    { 
        return blockman_.get_block(nb); 
    }
    
    void combine_operation(const bm::bvector<Alloc>& bvect, 
                            bm::operation            opcode);
    
private:

    bm::id_t check_or_next(bm::id_t prev) const;
    
    bm::id_t check_or_next_extract(bm::id_t prev);

    bool set_bit_no_check(bm::id_t n, bool val);

    bool and_bit_no_check(bm::id_t n, bool val);

    bool set_bit_conditional_impl(bm::id_t n, bool val, bool condition);


    void combine_operation_with_block(unsigned nb,
                                      unsigned gap,
                                      bm::word_t* blk,
                                      const bm::word_t* arg_blk,
                                      int arg_gap,
                                      bm::operation opcode);
public:
    void combine_operation_with_block(unsigned nb,
                                      const bm::word_t* arg_blk,
                                      int arg_gap,
                                      bm::operation opcode)
    {
        bm::word_t* blk = const_cast<bm::word_t*>(get_block(nb));
        bool gap = BM_IS_GAP(blk);
        combine_operation_with_block(nb, gap, blk, arg_blk, arg_gap, opcode);
    }
private:
    void combine_count_operation_with_block(unsigned nb,
                                            const bm::word_t* arg_blk,
                                            int arg_gap,
                                            bm::operation opcode)
    {
        const bm::word_t* blk = get_block(nb);
        bool gap = BM_IS_GAP(blk);
        combine_count_operation_with_block(nb, gap, blk, arg_blk, arg_gap, opcode);
    }


    void extend_gap_block(unsigned nb, gap_word_t* blk)
    {
        blockman_.extend_gap_block(nb, blk);
    }

    void set_range_no_check(bm::id_t left,
                            bm::id_t right,
                            bool     value);
public:

    const blocks_manager_type& get_blocks_manager() const
    {
        return blockman_;
    }

    blocks_manager_type& get_blocks_manager()
    {
        return blockman_;
    }


private:

// This block defines two additional hidden variables used for bitcount
// optimization, in rare cases can make bitvector thread unsafe.
#ifdef BMCOUNTOPT
    mutable id_t      count_;            
    mutable bool      count_is_valid_;   
#endif

    blocks_manager_type  blockman_;         
    strategy             new_blocks_strat_; 
    size_type            size_;             
};





//---------------------------------------------------------------------

template<class Alloc> 
inline bvector<Alloc> operator& (const bvector<Alloc>& v1,
                                 const bvector<Alloc>& v2)
{
#ifdef BM_USE_EXPLICIT_TEMP
    bvector<Alloc, MS> ret(v1);
    ret.bit_and(v2);
    return ret;
#else    
    return bvector<Alloc>(v1).bit_and(v2);
#endif
}

//---------------------------------------------------------------------

template<class Alloc> 
inline bvector<Alloc> operator| (const bvector<Alloc>& v1,
                                 const bvector<Alloc>& v2)
{
#ifdef BM_USE_EXPLICIT_TEMP
    bvector<Alloc, MS> ret(v1);
    ret.bit_or(v2);
    return ret;
#else    
    return bvector<Alloc>(v1).bit_or(v2);
#endif
}

//---------------------------------------------------------------------

template<class Alloc> 
inline bvector<Alloc> operator^ (const bvector<Alloc>& v1,
                                 const bvector<Alloc>& v2)
{
#ifdef BM_USE_EXPLICIT_TEMP
    bvector<Alloc, MS> ret(v1);
    ret.bit_xor(v2);
    return ret;
#else    
    return bvector<Alloc>(v1).bit_xor(v2);
#endif
}

//---------------------------------------------------------------------

template<class Alloc> 
inline bvector<Alloc> operator- (const bvector<Alloc>& v1,
                                 const bvector<Alloc>& v2)
{
#ifdef BM_USE_EXPLICIT_TEMP
    bvector<Alloc, MS> ret(v1);
    ret.bit_sub(v2);
    return ret;
#else    
    return bvector<Alloc>(v1).bit_sub(v2);
#endif
}




// -----------------------------------------------------------------------

template<typename Alloc> 
bvector<Alloc>& bvector<Alloc>::set_range(bm::id_t left,
                                          bm::id_t right,
                                          bool     value)
{
    if (right < left)
    {
        return set_range(right, left, value);
    }

    BM_ASSERT(left < size_);
    BM_ASSERT(right < size_);

    BMCOUNT_VALID(false)
    BM_SET_MMX_GUARD

    set_range_no_check(left, right, value);

    return *this;
}

// -----------------------------------------------------------------------

template<typename Alloc> 
bm::id_t bvector<Alloc>::count() const
{
#ifdef BMCOUNTOPT
    if (count_is_valid_) return count_;
#endif
    word_t*** blk_root = blockman_.get_rootblock();
    if (!blk_root) 
    {
        BMCOUNT_SET(0);
        return 0;
    }    
    typename blocks_manager_type::block_count_func func(blockman_);
    for_each_nzblock2(blk_root, blockman_.effective_top_block_size(), 
                      func);

    BMCOUNT_SET(func.count());
    return func.count();
}

// -----------------------------------------------------------------------

template<typename Alloc> 
void bvector<Alloc>::resize(size_type new_size)
{
    if (size_ == new_size) return; // nothing to do
    if (size_ < new_size) // size grows 
    {
        blockman_.reserve(new_size);
        size_ = new_size;
    }
    else // shrink
    {
        set_range(new_size, size_ - 1, false); // clear the tail
        size_ = new_size;
    }
}

// -----------------------------------------------------------------------

template<typename Alloc> 
bm::id_t bvector<Alloc>::count_range(bm::id_t left, 
                                         bm::id_t right, 
                                         unsigned* block_count_arr) const
{
    BM_ASSERT(left <= right);

    unsigned count = 0;

    // calculate logical number of start and destination blocks
    unsigned nblock_left  = unsigned(left  >>  bm::set_block_shift);
    unsigned nblock_right = unsigned(right >>  bm::set_block_shift);

    const bm::word_t* block = blockman_.get_block(nblock_left);
    bool left_gap = BM_IS_GAP(block);

    unsigned nbit_left  = unsigned(left  & bm::set_block_mask); 
    unsigned nbit_right = unsigned(right & bm::set_block_mask); 

    unsigned r = 
        (nblock_left == nblock_right) ? nbit_right : (bm::bits_in_block-1);

    typename blocks_manager_type::block_count_func func(blockman_);

    if (block)
    {
        if ((nbit_left == 0) && (r == (bm::bits_in_block-1))) // whole block
        {
            if (block_count_arr)
            {
                count += block_count_arr[nblock_left];
            }
            else
            {
                func(block);//, nblock_left);
            }
        }
        else
        {
            if (left_gap)
            {
                count += gap_bit_count_range(BMGAP_PTR(block), 
                                            (gap_word_t)nbit_left,
                                            (gap_word_t)r);
            }
            else
            {
                count += bit_block_calc_count_range(block, nbit_left, r);
            }
        }
    }

    if (nblock_left == nblock_right)  // in one block
    {
        return count + func.count();
    }

    for (unsigned nb = nblock_left+1; nb < nblock_right; ++nb)
    {
        block = blockman_.get_block(nb);
        if (block_count_arr)
        {
            count += block_count_arr[nb];
        }
        else 
        {
            if (block)
                func(block);
        }
    }
    count += func.count();

    block = blockman_.get_block(nblock_right);
    bool right_gap = BM_IS_GAP(block);

    if (block)
    {
        if (right_gap)
        {
            count += gap_bit_count_range(BMGAP_PTR(block),
                                        (gap_word_t)0,
                                        (gap_word_t)nbit_right);
        }
        else
        {
            count += bit_block_calc_count_range(block, 0, nbit_right);
        }
    }

    return count;
}

// -----------------------------------------------------------------------

template<typename Alloc>
bvector<Alloc>& bvector<Alloc>::invert()
{
    BMCOUNT_VALID(false)
    BM_SET_MMX_GUARD

    bm::word_t*** blk_root = blockman_.get_rootblock();
    typename blocks_manager_type::block_invert_func func(blockman_);    
    for_each_block(blk_root, blockman_.top_block_size(), func);
    if (size_ == bm::id_max) 
    {
        set_bit_no_check(bm::id_max, false);
    } 
    else
    {
        set_range_no_check(size_, bm::id_max, false);
    }

    return *this;
}

// -----------------------------------------------------------------------

template<typename Alloc> 
bool bvector<Alloc>::get_bit(bm::id_t n) const
{    
    BM_ASSERT(n < size_);

    // calculate logical block number
    unsigned nblock = unsigned(n >>  bm::set_block_shift); 

    const bm::word_t* block = blockman_.get_block(nblock);

    if (block)
    {
        // calculate word number in block and bit
        unsigned nbit = unsigned(n & bm::set_block_mask); 
        unsigned is_set;

        if (BM_IS_GAP(block))
        {
            is_set = gap_test(BMGAP_PTR(block), nbit);
        }
        else 
        {
            unsigned nword  = unsigned(nbit >> bm::set_word_shift); 
            nbit &= bm::set_word_mask;

            is_set = (block[nword] & (((bm::word_t)1) << nbit));
        }
        return is_set != 0;
    }
    return false;
}

// -----------------------------------------------------------------------

template<typename Alloc> 
void bvector<Alloc>::optimize(bm::word_t* temp_block, 
                              optmode     opt_mode,
                              statistics* stat)
{
    word_t*** blk_root = blockman_.blocks_root();

    if (!temp_block)
        temp_block = blockman_.check_allocate_tempblock();

    typename 
        blocks_manager_type::block_opt_func  opt_func(blockman_, 
                                                temp_block, 
                                                (int)opt_mode,
                                                stat);
    if (stat)
    {
        stat->bit_blocks = stat->gap_blocks 
                         = stat->max_serialize_mem 
                         = stat->memory_used 
                         = 0;
        ::memcpy(stat->gap_levels, 
                blockman_.glen(), sizeof(gap_word_t) * bm::gap_levels);
        stat->max_serialize_mem = sizeof(id_t) * 4;

    }

    for_each_nzblock(blk_root, blockman_.effective_top_block_size(),
                     opt_func);

    if (stat)
    {
        unsigned safe_inc = stat->max_serialize_mem / 10; // 10% increment
        if (!safe_inc) safe_inc = 256;
        stat->max_serialize_mem += safe_inc;
        stat->memory_used += sizeof(*this) - sizeof(blockman_);
        stat->memory_used += blockman_.mem_used();
    }
}

// -----------------------------------------------------------------------

template<typename Alloc> 
void bvector<Alloc>::optimize_gap_size()
{
    struct bvector<Alloc>::statistics st;
    calc_stat(&st);

    if (!st.gap_blocks)
        return;

    gap_word_t opt_glen[bm::gap_levels];
    ::memcpy(opt_glen, st.gap_levels, bm::gap_levels * sizeof(*opt_glen));

    improve_gap_levels(st.gap_length, 
                            st.gap_length + st.gap_blocks, 
                            opt_glen);
    
    set_gap_levels(opt_glen);
}

// -----------------------------------------------------------------------

template<typename Alloc> 
void bvector<Alloc>::set_gap_levels(const gap_word_t* glevel_len)
{
    word_t*** blk_root = blockman_.blocks_root();
    typename 
        blocks_manager_type::gap_level_func  gl_func(blockman_, glevel_len);
    for_each_nzblock(blk_root, blockman_.top_block_size(),gl_func);

    blockman_.set_glen(glevel_len);
}

// -----------------------------------------------------------------------

template<typename Alloc> 
int bvector<Alloc>::compare(const bvector<Alloc>& bvect) const
{
    int res;
    unsigned bn = 0;

    unsigned top_blocks = blockman_.effective_top_block_size();
    unsigned bvect_top_blocks = bvect.blockman_.effective_top_block_size();

    if (bvect_top_blocks > top_blocks) top_blocks = bvect_top_blocks;

    for (unsigned i = 0; i < top_blocks; ++i)
    {
        const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
        const bm::word_t* const* arg_blk_blk = 
                                bvect.blockman_.get_topblock(i);

        if (blk_blk == arg_blk_blk) 
        {
            bn += bm::set_array_size;
            continue;
        }

        for (unsigned j = 0; j < bm::set_array_size; ++j, ++bn)
        {
            const bm::word_t* arg_blk = arg_blk_blk ? arg_blk_blk[j] : 0;
            const bm::word_t* blk = blk_blk ? blk_blk[j] : 0;
            if (blk == arg_blk) continue;

            // If one block is zero we check if the other one has at least 
            // one bit ON

            if (!blk || !arg_blk)  
            {
                const bm::word_t*  pblk;
                bool is_gap;

                if (blk)
                {
                    pblk = blk;
                    res = 1;
                    is_gap = BM_IS_GAP(blk);
                }
                else
                {
                    pblk = arg_blk;
                    res = -1;
                    is_gap = BM_IS_GAP(arg_blk);
                }

                if (is_gap)
                {
                    if (!gap_is_all_zero(BMGAP_PTR(pblk), bm::gap_max_bits))
                    {
                        return res;
                    }
                }
                else
                {
                    bm::wordop_t* blk1 = (wordop_t*)pblk;
                    bm::wordop_t* blk2 = 
                        (wordop_t*)(pblk + bm::set_block_size);
                    if (!bit_is_all_zero(blk1, blk2))
                    {
                        return res;
                    }
                }

                continue;
            }

            bool arg_gap = BM_IS_GAP(arg_blk);
            bool gap = BM_IS_GAP(blk);

            if (arg_gap != gap)
            {
                bm::wordop_t temp_blk[bm::set_block_size_op]; 
                bm::wordop_t* blk1;
                bm::wordop_t* blk2;

                if (gap)
                {
                    gap_convert_to_bitset((bm::word_t*)temp_blk, 
                                            BMGAP_PTR(blk));

                    blk1 = (bm::wordop_t*)temp_blk;
                    blk2 = (bm::wordop_t*)arg_blk;
                }
                else
                {
                    gap_convert_to_bitset((bm::word_t*)temp_blk, 
                                            BMGAP_PTR(arg_blk));

                    blk1 = (bm::wordop_t*)blk;
                    blk2 = (bm::wordop_t*)temp_blk;

                }                        
                res = bitcmp(blk1, blk2, bm::set_block_size_op);  

            }
            else
            {
                if (gap)
                {
                    res = gapcmp(BMGAP_PTR(blk), BMGAP_PTR(arg_blk));
                }
                else
                {
                    res = bitcmp((bm::wordop_t*)blk, 
                                    (bm::wordop_t*)arg_blk, 
                                    bm::set_block_size_op);
                }
            }

            if (res != 0)
            {
                return res;
            }
        

        } // for j

    } // for i

    return 0;
}


// -----------------------------------------------------------------------

template<typename Alloc> 
void bvector<Alloc>::calc_stat(struct bvector<Alloc>::statistics* st) const
{
    st->bit_blocks = st->gap_blocks 
                   = st->max_serialize_mem 
                   = st->memory_used = 0;

    ::memcpy(st->gap_levels, 
             blockman_.glen(), sizeof(gap_word_t) * bm::gap_levels);

    unsigned empty_blocks = 0;
    unsigned blocks_memory = 0;
    gap_word_t* gapl_ptr = st->gap_length;

    st->max_serialize_mem = sizeof(id_t) * 4;

    unsigned block_idx = 0;

    unsigned top_size = blockman_.effective_top_block_size();
    // Walk the blocks, calculate statistics.
    for (unsigned i = 0; i < top_size; ++i)
    {
        const bm::word_t* const* blk_blk = blockman_.get_topblock(i);

        if (!blk_blk) 
        {
            block_idx += bm::set_array_size;
            st->max_serialize_mem += sizeof(unsigned) + 1;
            continue;
        }

        for (unsigned j = 0;j < bm::set_array_size; ++j, ++block_idx)
        {
            const bm::word_t* blk = blk_blk[j];
            if (IS_VALID_ADDR(blk))
            {
                st->max_serialize_mem += empty_blocks << 2;
                empty_blocks = 0;

                if (BM_IS_GAP(blk))
                {
                    ++(st->gap_blocks);

                    bm::gap_word_t* gap_blk = BMGAP_PTR(blk);

                    unsigned mem_used = 
                        bm::gap_capacity(gap_blk, blockman_.glen()) 
                        * sizeof(gap_word_t);

                    *gapl_ptr = gap_length(gap_blk);

                    st->max_serialize_mem += *gapl_ptr * sizeof(gap_word_t);
                    blocks_memory += mem_used;

                    ++gapl_ptr;
                }
                else // bit block
                {
                    ++(st->bit_blocks);
                    unsigned mem_used = sizeof(bm::word_t) * bm::set_block_size;
                    st->max_serialize_mem += mem_used;
                    blocks_memory += mem_used;
                }
            }
            else
            {
                ++empty_blocks;
            }
        }
    }  

    unsigned safe_inc = st->max_serialize_mem / 10; // 10% increment
    if (!safe_inc) safe_inc = 256;
    st->max_serialize_mem += safe_inc;

    // Calc size of different odd and temporary things.

    st->memory_used += sizeof(*this) - sizeof(blockman_);
    st->memory_used += blockman_.mem_used();
    st->memory_used += blocks_memory;
}


// -----------------------------------------------------------------------


template<class Alloc> 
bool bvector<Alloc>::set_bit_no_check(bm::id_t n, bool val)
{
    // calculate logical block number
    unsigned nblock = unsigned(n >>  bm::set_block_shift); 

    int block_type;

    bm::word_t* blk = 
        blockman_.check_allocate_block(nblock, 
                                        val,
                                        get_new_blocks_strat(), 
                                        &block_type);

    if (!blk) return false;

    // calculate word number in block and bit
    unsigned nbit   = unsigned(n & bm::set_block_mask); 

    if (block_type == 1) // gap
    {
        unsigned is_set;
        unsigned new_block_len;
        
        new_block_len = 
            gap_set_value(val, BMGAP_PTR(blk), nbit, &is_set);
        if (is_set)
        {
            BMCOUNT_ADJ(val)

            unsigned threshold = 
            bm::gap_limit(BMGAP_PTR(blk), blockman_.glen());

            if (new_block_len > threshold) 
            {
                extend_gap_block(nblock, BMGAP_PTR(blk));
            }
            return true;
        }
    }
    else  // bit block
    {
        unsigned nword  = unsigned(nbit >> bm::set_word_shift); 
        nbit &= bm::set_word_mask;

        bm::word_t* word = blk + nword;
        bm::word_t  mask = (((bm::word_t)1) << nbit);

        if (val)
        {
            if ( ((*word) & mask) == 0 )
            {
                *word |= mask; // set bit
                BMCOUNT_INC;
                return true;
            }
        }
        else
        {
            if ((*word) & mask)
            {
                *word &= ~mask; // clear bit
                BMCOUNT_DEC;
                return true;
            }
        }
    }
    return false;
}

// -----------------------------------------------------------------------

template<class Alloc> 
bool bvector<Alloc>::set_bit_conditional_impl(bm::id_t n, 
                                              bool     val, 
                                              bool     condition)
{
    // calculate logical block number
    unsigned nblock = unsigned(n >>  bm::set_block_shift); 

    int block_type;
    bm::word_t* blk = 
        blockman_.check_allocate_block(nblock, 
                                       val,
                                       get_new_blocks_strat(), 
                                       &block_type);
    if (!blk) 
        return false;

    // calculate word number in block and bit
    unsigned nbit   = unsigned(n & bm::set_block_mask); 

    if (block_type == 1) // gap
    {
        bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
        bool old_val = (gap_test(gap_blk, nbit) != 0);

        if (old_val != condition) 
        {
            return false;
        }

        if (val != old_val)
        {
            unsigned is_set;
            unsigned new_block_len = 
                gap_set_value(val, gap_blk, nbit, &is_set);
            BM_ASSERT(is_set);
            BMCOUNT_ADJ(val)

            unsigned threshold = 
                bm::gap_limit(gap_blk, blockman_.glen());
            if (new_block_len > threshold) 
            {
                extend_gap_block(nblock, gap_blk);
            }
            return true;
        }
    }
    else  // bit block
    {
        unsigned nword  = unsigned(nbit >> bm::set_word_shift); 
        nbit &= bm::set_word_mask;

        bm::word_t* word = blk + nword;
        bm::word_t  mask = (((bm::word_t)1) << nbit);
        bool is_set = ((*word) & mask) != 0;

        if (is_set != condition)
        {
            return false;
        }
        if (is_set != val)    // need to change bit
        {
            if (val)          // set bit
            {
                *word |= mask;
                BMCOUNT_INC;
            }
            else               // clear bit
            {
                *word &= ~mask;
                BMCOUNT_DEC;
            }
            return true;
        }
    }
    return false;

}

// -----------------------------------------------------------------------


template<class Alloc> 
bool bvector<Alloc>::and_bit_no_check(bm::id_t n, bool val)
{
    // calculate logical block number
    unsigned nblock = unsigned(n >>  bm::set_block_shift); 

    int block_type;
    bm::word_t* blk = 
        blockman_.check_allocate_block(nblock, 
                                       val,
                                       get_new_blocks_strat(), 
                                       &block_type);
    if (!blk) return false;

    // calculate word number in block and bit
    unsigned nbit   = unsigned(n & bm::set_block_mask); 

    if (block_type == 1) // gap
    {
        bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
        bool old_val = (gap_test(gap_blk, nbit) != 0);

        bool new_val = val & old_val;
        if (new_val != old_val)
        {
            unsigned is_set;
            unsigned new_block_len = 
                gap_set_value(new_val, gap_blk, nbit, &is_set);
            BM_ASSERT(is_set);
            BMCOUNT_ADJ(val)

            unsigned threshold = 
                bm::gap_limit(gap_blk, blockman_.glen());
            if (new_block_len > threshold) 
            {
                extend_gap_block(nblock, gap_blk);
            }
            return true;
        }
    }
    else  // bit block
    {
        unsigned nword  = unsigned(nbit >> bm::set_word_shift); 
        nbit &= bm::set_word_mask;

        bm::word_t* word = blk + nword;
        bm::word_t  mask = (((bm::word_t)1) << nbit);
        bool is_set = ((*word) & mask) != 0;

        bool new_val = is_set & val;
        if (new_val != val)    // need to change bit
        {
            if (new_val)       // set bit
            {
                *word |= mask;
                BMCOUNT_INC;
            }
            else               // clear bit
            {
                *word &= ~mask;
                BMCOUNT_DEC;
            }
            return true;
        }
    }
    return false;
}


//---------------------------------------------------------------------

template<class Alloc> 
bm::id_t bvector<Alloc>::check_or_next(bm::id_t prev) const
{
    for (;;)
    {
        unsigned nblock = unsigned(prev >> bm::set_block_shift); 
        if (nblock >= bm::set_total_blocks) 
            break;

        if (blockman_.is_subblock_null(nblock >> bm::set_array_shift))
        {
            prev += (bm::set_blkblk_mask + 1) -
                            (prev & bm::set_blkblk_mask);
        }
        else
        {
            unsigned nbit = unsigned(prev & bm::set_block_mask);
            int no_more_blocks;
            const bm::word_t* block = 
                blockman_.get_block(nblock, &no_more_blocks);

            if (no_more_blocks) 
            {
                BM_ASSERT(block == 0);
                break;
            }

            if (block)
            {
                if (IS_FULL_BLOCK(block)) return prev;
                if (BM_IS_GAP(block))
                {
                    if (bm::gap_find_in_block(BMGAP_PTR(block),
                                                nbit,
                                                &prev))
                    {
                        return prev;
                    }
                }
                else
                {
                    if (bm::bit_find_in_block(block, nbit, &prev)) 
                    {
                        return prev;
                    }
                }
            }
            else
            {
                prev += (bm::set_block_mask + 1) - 
                            (prev & bm::set_block_mask);
            }

        }
        if (!prev) break;
    }

    return 0;
}


//---------------------------------------------------------------------

template<class Alloc> 
bm::id_t bvector<Alloc>::check_or_next_extract(bm::id_t prev)
{
    for (;;)
    {
        unsigned nblock = unsigned(prev >> bm::set_block_shift); 
        if (nblock >= bm::set_total_blocks) break;

        if (blockman_.is_subblock_null(nblock >> bm::set_array_shift))
        {
            prev += (bm::set_blkblk_mask + 1) -
                            (prev & bm::set_blkblk_mask);
        }
        else
        {
            unsigned nbit = unsigned(prev & bm::set_block_mask);

            int no_more_blocks;
            bm::word_t* block = 
                blockman_.get_block(nblock, &no_more_blocks);

            if (no_more_blocks) 
            {
                BM_ASSERT(block == 0);
                break;
            }


            if (block)
            {
                if (IS_FULL_BLOCK(block))
                {
                    set(prev, false);
                    return prev;
                }
                if (BM_IS_GAP(block))
                {
                    unsigned is_set;
                    unsigned new_block_len = 
                        gap_set_value(0, BMGAP_PTR(block), nbit, &is_set);
                    if (is_set) {
                        BMCOUNT_DEC
                        unsigned threshold = 
                            bm::gap_limit(BMGAP_PTR(block), blockman_.glen());
                        if (new_block_len > threshold) 
                        {
                            extend_gap_block(nblock, BMGAP_PTR(block));
                        }
                        return prev;
                    } else {
                        if (bm::gap_find_in_block(BMGAP_PTR(block),
                                                    nbit,
                                                    &prev))
                        {
                            set(prev, false);
                            return prev;
                        }
                    }
                }
                else // bit block
                {
                    if (bm::bit_find_in_block(block, nbit, &prev)) 
                    {
                        BMCOUNT_DEC

                        unsigned nbit = 
                            unsigned(prev & bm::set_block_mask); 
                        unsigned nword = 
                            unsigned(nbit >> bm::set_word_shift);
                        nbit &= bm::set_word_mask;
                        bm::word_t* word = block + nword;
                        bm::word_t  mask = ((bm::word_t)1) << nbit;
                        *word &= ~mask;

                        return prev;
                    }
                }
            }
            else
            {
                prev += (bm::set_block_mask + 1) - 
                            (prev & bm::set_block_mask);
            }

        }
        if (!prev) break;
    }

    return 0;
}

//---------------------------------------------------------------------

template<class Alloc> 
void bvector<Alloc>::combine_operation(
                                  const bm::bvector<Alloc>& bvect, 
                                  bm::operation             opcode)
{
    typedef void (*block_bit_op)(bm::word_t*, const bm::word_t*);
    typedef void (*block_bit_op_next)(bm::word_t*, 
                                      const bm::word_t*, 
                                      bm::word_t*, 
                                      const bm::word_t*);

    unsigned top_blocks = blockman_.top_block_size();
    unsigned bvect_top_blocks = bvect.blockman_.top_block_size();

    if (size_ == bvect.size_) 
    {
        BM_ASSERT(top_blocks >= bvect_top_blocks);
    }
    else
    if (size_ < bvect.size_) // this vect shorter than the arg.
    {
        size_ = bvect.size_;
        // stretch our capacity
        blockman_.reserve_top_blocks(bvect_top_blocks);
        top_blocks = blockman_.top_block_size();
    }
    else 
    if (size_ > bvect.size_) // this vector larger
    {
        if (opcode == BM_AND) // clear the tail with zeros
        {
            set_range(bvect.size_, size_ - 1, false);
            if (bvect_top_blocks < top_blocks)
            {
                // not to scan blocks we already swiped
                top_blocks = bvect_top_blocks;
            }
        }
    }
    
    bm::word_t*** blk_root = blockman_.blocks_root();
    unsigned block_idx = 0;
    unsigned i, j;

    BM_SET_MMX_GUARD

    // calculate effective top size to avoid overscan
    top_blocks = blockman_.effective_top_block_size();
    if (top_blocks < bvect.blockman_.effective_top_block_size())
    {
        if (opcode != BM_AND)
        {
            top_blocks = bvect.blockman_.effective_top_block_size();
        }
    }

    for (i = 0; i < top_blocks; ++i)
    {
        bm::word_t** blk_blk = blk_root[i];
        if (blk_blk == 0) // not allocated
        {
            if (opcode == BM_AND) // 0 AND anything == 0
            {
                block_idx += bm::set_array_size;
                continue; 
            }
            const bm::word_t* const* bvbb = bvect.blockman_.get_topblock(i);
            if (bvbb == 0) // skip it because 0 OP 0 == 0 
            {
                block_idx += bm::set_array_size;
                continue; 
            }
            // 0 - self, non-zero argument
            unsigned r = i * bm::set_array_size;
            for (j = 0; j < bm::set_array_size; ++j)
            {
                const bm::word_t* arg_blk = bvect.blockman_.get_block(i, j);
                if (arg_blk )
                    combine_operation_with_block(r + j,
                                                 0, 0, 
                                                 arg_blk, BM_IS_GAP(arg_blk), 
                                                 opcode);
            } // for j
            continue;
        }

        if (opcode == BM_AND)
        {
            unsigned r = i * bm::set_array_size;
            for (j = 0; j < bm::set_array_size; ++j)
            {            
                bm::word_t* blk = blk_blk[j];
                if (blk)
                {
                    const bm::word_t* arg_blk = bvect.blockman_.get_block(i, j);            
                    if (arg_blk)
                        combine_operation_with_block(r + j,
                                                     BM_IS_GAP(blk), blk, 
                                                     arg_blk, BM_IS_GAP(arg_blk),
                                                     opcode);                    
                    else
                        blockman_.zero_block(i, j);
                }

            } // for j
        }
        else // OR, SUB, XOR
        {
            unsigned r = i * bm::set_array_size;
            for (j = 0; j < bm::set_array_size; ++j)
            {            
                bm::word_t* blk = blk_blk[j];
                const bm::word_t* arg_blk = bvect.blockman_.get_block(i, j);            
                if (arg_blk || blk)
                    combine_operation_with_block(r + j, BM_IS_GAP(blk), blk, 
                                                 arg_blk, BM_IS_GAP(arg_blk),
                                                 opcode);
            } // for j
        }
    } // for i

}


//---------------------------------------------------------------------


template<class Alloc> 
void 
bvector<Alloc>::combine_operation_with_block(unsigned          nb,
                                             unsigned          gap,
                                             bm::word_t*       blk,
                                             const bm::word_t* arg_blk,
                                             int               arg_gap,
                                             bm::operation     opcode)
{
    gap_word_t tmp_buf[bm::gap_equiv_len * 3]; // temporary result            
    const bm::gap_word_t* res;
    unsigned res_len;
    int      level;
    unsigned threshold;


    if (opcode == BM_OR || opcode == BM_XOR)
    {        
        if (!blk && arg_gap) 
        {
            res = BMGAP_PTR(arg_blk);
            res_len = bm::gap_length(res);
            level = -1;
            threshold = 0;
            goto assign_gap_result;
        }
    }

        if (gap) // our block GAP-type
        {
            if (arg_gap)  // both blocks GAP-type
            {
                {
                    gap_operation_func_type gfunc = 
                        operation_functions<true>::gap_operation(opcode);
                    BM_ASSERT(gfunc);
                    res = (*gfunc)(BMGAP_PTR(blk), 
                                   BMGAP_PTR(arg_blk), 
                                   tmp_buf,
                                   res_len);
                }
                BM_ASSERT(res == tmp_buf);
                ++res_len;// = bm::gap_length(res);

                BM_ASSERT(!(res == tmp_buf && res_len == 0));

                // if as a result of the operation gap block turned to zero
                // we can now replace it with NULL
                if (gap_is_all_zero(res, bm::gap_max_bits))
                {
                    blockman_.zero_block(nb);
                    return;
                }

                // mutation check

                level = gap_level(BMGAP_PTR(blk));
                threshold = blockman_.glen(level)-4;

            assign_gap_result:
                int new_level = gap_calc_level(res_len, blockman_.glen());
                if (new_level == -1)
                {
                    blockman_.convert_gap2bitset(nb, res, res_len-1);
                    return;
                }

                if (res_len > threshold)
                {
                    gap_word_t* new_blk = 
                        blockman_.allocate_gap_block(new_level, res);
                    set_gap_level(new_blk, new_level);

                    bm::word_t* p = (bm::word_t*)new_blk;
                    BMSET_PTRGAP(p);

                    if (blk)
                    {
                        blockman_.set_block_ptr(nb, p);
                        blockman_.get_allocator().free_gap_block(BMGAP_PTR(blk), 
                                                                 blockman_.glen());
                    }
                    else
                    {
                        blockman_.set_block(nb, p, true); // set GAP block
                    }
                    return;
                }

                // gap operation result is in the temporary buffer
                // we copy it back to the gap_block

                BM_ASSERT(blk);

                set_gap_level(tmp_buf, level);
                ::memcpy(BMGAP_PTR(blk), tmp_buf, res_len * sizeof(gap_word_t));
                return;
            }
            else // argument is BITSET-type (own block is GAP)
            {
                // since we can not combine blocks of mixed type
                // we need to convert our block to bitset
               
                if (arg_blk == 0)  // Combining against an empty block
                {
                    switch (opcode)
                    {
                    case BM_AND:  // ("Value" AND  0) == 0
                        blockman_.zero_block(nb);
                        return;
                    case BM_OR: case BM_SUB: case BM_XOR:
                        return; // nothing to do
                    }
                }
                gap_word_t* gap_blk = BMGAP_PTR(blk);
                if (opcode == BM_AND)
                {
                    unsigned gap_cnt = gap_bit_count(gap_blk);
                    if (gap_cnt < 128)
                    {
                        gap_word_t tmp_buf[bm::gap_equiv_len * 3];         
                        gap_word_t arr_len = 
                            gap_convert_to_arr(tmp_buf, gap_blk, 
                                               bm::gap_equiv_len-10);
                        BM_ASSERT(gap_cnt == arr_len);
                        blockman_.zero_block(nb);
                        unsigned arr_i = 0;
                        int block_type;
                        blk =
                            blockman_.check_allocate_block(nb,
                                                           true,
                                                           BM_GAP,
                                                           &block_type,
                                                           false //no null return
                                                           );
                        BM_ASSERT(block_type==1); // GAP
                        gap_blk = BMGAP_PTR(blk);
                        unsigned threshold = bm::gap_limit(gap_blk, blockman_.glen());
                        for (; arr_i < arr_len; ++arr_i)
                        {
                            gap_word_t bit_idx = tmp_buf[arr_i];
                            if (bm::test_bit(arg_blk, bit_idx))
                            {
                                unsigned is_set;
                                unsigned new_block_len =
                                    gap_set_value(true, gap_blk, bit_idx, &is_set);
                                BM_ASSERT(is_set);
                                if (new_block_len > threshold) 
                                {
                                    gap_blk = 
                                        blockman_.extend_gap_block(nb, gap_blk);
                                    if (gap_blk == 0) // mutated into bit-block
                                    {
                                        blk = blockman_.check_allocate_block(
                                                         nb,
                                                         true,
                                                         this->get_new_blocks_strat(),
                                                         &block_type,
                                                         false // no null return
                                                         );  
                                        BM_ASSERT(block_type == 0); // BIT
                                        // target block degraded into plain bit-block
                                        for (++arr_i; arr_i < arr_len; ++arr_i)
                                        {
                                            bit_idx = tmp_buf[arr_i];
                                            if (bm::test_bit(arg_blk, bit_idx))
                                            {
                                                or_bit_block(blk, bit_idx, 1);
                                            }
                                        } // for arr_i
                                        return;
                                    } // if gap mutated
                                }
                            } // for arr_i
                        }

                        return;
                    }                    
                } // BM_AND

                blk = blockman_.convert_gap2bitset(nb, gap_blk);
            }
        } 
        else // our block is BITSET-type
        {
            if (arg_gap) // argument block is GAP-type
            {
                if (IS_VALID_ADDR(blk))
                {
                    // special case, maybe we can do the job without 
                    // converting the GAP argument to bitblock
                    gap_operation_to_bitset_func_type gfunc = 
                        operation_functions<true>::gap_op_to_bit(opcode);
                    BM_ASSERT(gfunc);
                    (*gfunc)(blk, BMGAP_PTR(arg_blk));
                    return;
                }
                
                // the worst case we need to convert argument block to 
                // bitset type.
                gap_word_t* temp_blk = (gap_word_t*) blockman_.check_allocate_tempblock();
                arg_blk = 
                    gap_convert_to_bitset_smart((bm::word_t*)temp_blk, 
                                                BMGAP_PTR(arg_blk), 
                                                bm::gap_max_bits);
            
            }   
        }
    
        // Now here we combine two plain bitblocks using supplied bit function.
        bm::word_t* dst = blk;

        bm::word_t* ret; 
        if (dst == 0 && arg_blk == 0)
        {
            return;
        }

        switch (opcode)
        {
        case BM_AND:
            ret = bit_operation_and(dst, arg_blk);
            goto copy_block;
        case BM_XOR:
            ret = bit_operation_xor(dst, arg_blk);
            if (ret && (ret == arg_blk) && IS_FULL_BLOCK(dst))
            {
                ret = blockman_.get_allocator().alloc_bit_block();
#ifdef BMVECTOPT
            VECT_XOR_ARR_2_MASK(ret, 
                                arg_blk, 
                                arg_blk + bm::set_block_size, 
                                bm::all_bits_mask);
#else
                bm::wordop_t* dst_ptr = (wordop_t*)ret;
                const bm::wordop_t* wrd_ptr = (wordop_t*) arg_blk;
                const bm::wordop_t* wrd_end = 
                (wordop_t*) (arg_blk + bm::set_block_size);

                do
                {
                    dst_ptr[0] = bm::all_bits_mask ^ wrd_ptr[0];
                    dst_ptr[1] = bm::all_bits_mask ^ wrd_ptr[1];
                    dst_ptr[2] = bm::all_bits_mask ^ wrd_ptr[2];
                    dst_ptr[3] = bm::all_bits_mask ^ wrd_ptr[3];

                    dst_ptr+=4;
                    wrd_ptr+=4;

                } while (wrd_ptr < wrd_end);
#endif
                break;
            }
            goto copy_block;
        case BM_OR:
            ret = bit_operation_or(dst, arg_blk);
        copy_block:
            if (ret && (ret == arg_blk) && !IS_FULL_BLOCK(ret))
            {
            ret = blockman_.get_allocator().alloc_bit_block();
            bit_block_copy(ret, arg_blk);
            }
            break;

        case BM_SUB:
            ret = bit_operation_sub(dst, arg_blk);
            if (ret && ret == arg_blk)
            {
                ret = blockman_.get_allocator().alloc_bit_block();
#ifdef BMVECTOPT
                VECT_ANDNOT_ARR_2_MASK(ret, 
                                    arg_blk,
                                    arg_blk + bm::set_block_size,
                                    bm::all_bits_mask);
#else

                bm::wordop_t* dst_ptr = (wordop_t*)ret;
                const bm::wordop_t* wrd_ptr = (wordop_t*) arg_blk;
                const bm::wordop_t* wrd_end = 
                (wordop_t*) (arg_blk + bm::set_block_size);

                do
                {
                    dst_ptr[0] = bm::all_bits_mask & ~wrd_ptr[0];
                    dst_ptr[1] = bm::all_bits_mask & ~wrd_ptr[1];
                    dst_ptr[2] = bm::all_bits_mask & ~wrd_ptr[2];
                    dst_ptr[3] = bm::all_bits_mask & ~wrd_ptr[3];

                    dst_ptr+=4;
                    wrd_ptr+=4;

                } while (wrd_ptr < wrd_end);
#endif
            }
            break;
        default:
            BM_ASSERT(0);
            ret = 0;
        }

        if (ret != dst) // block mutation
        {
            blockman_.set_block(nb, ret);
            blockman_.get_allocator().free_bit_block(dst);
        }
}

//---------------------------------------------------------------------

template<class Alloc> 
void bvector<Alloc>::set_range_no_check(bm::id_t left,
                                        bm::id_t right,
                                        bool     value)
{
    // calculate logical number of start and destination blocks
    unsigned nblock_left  = unsigned(left  >>  bm::set_block_shift);
    unsigned nblock_right = unsigned(right >>  bm::set_block_shift);

    bm::word_t* block = blockman_.get_block(nblock_left);
    bool left_gap = BM_IS_GAP(block);

    unsigned nbit_left  = unsigned(left  & bm::set_block_mask); 
    unsigned nbit_right = unsigned(right & bm::set_block_mask); 

    unsigned r = 
        (nblock_left == nblock_right) ? nbit_right :(bm::bits_in_block-1);

        bm::gap_word_t tmp_gap_blk[5] = {0,};

    // Set bits in the starting block

    unsigned nb;
    if ((nbit_left == 0) && (r == bm::bits_in_block - 1)) // full block
    {
        nb = nblock_left;
    }
    else
    {
        gap_init_range_block<gap_word_t>(tmp_gap_blk,
                                         (gap_word_t)nbit_left, 
                                         (gap_word_t)r, 
                                         (gap_word_t)value, 
                                         bm::bits_in_block);

        combine_operation_with_block(nblock_left, 
                                    left_gap, 
                                    block,
                                    (bm::word_t*) tmp_gap_blk,
                                    1,
                                    value ? BM_OR : BM_AND);

        if (nblock_left == nblock_right)  // in one block
            return;
        nb = nblock_left+1;
    }

    // Set (or clear) all full blocks between left and right
    
    unsigned nb_to = nblock_right + (nbit_right ==(bm::bits_in_block-1));
            
    if (value)
    {
        for (; nb < nb_to; ++nb)
        {
            block = blockman_.get_block(nb);
            if (IS_FULL_BLOCK(block)) 
                continue;

            blockman_.set_block(nb, FULL_BLOCK_ADDR);
            blockman_.free_block(block);
        } // for
    }
    else // value == 0
    {
        for (; nb < nb_to; ++nb)
        {
            block = blockman_.get_block(nb);
            if (block == 0)  // nothing to do
                continue;
            blockman_.set_block(nb, 0, false /*bit*/);
            blockman_.free_block(block);

        } // for
    } // if value else 

    if (nb_to > nblock_right)
        return;

    block = blockman_.get_block(nblock_right);
    bool right_gap = BM_IS_GAP(block);

    gap_init_range_block<gap_word_t>(tmp_gap_blk, 
                                     (gap_word_t)0, 
                                     (gap_word_t)nbit_right, 
                                     (gap_word_t)value, 
                                     bm::bits_in_block);

    combine_operation_with_block(nblock_right, 
                                    right_gap, 
                                    block,
                                    (bm::word_t*) tmp_gap_blk,
                                    1,
                                    value ? BM_OR : BM_AND);

}

//---------------------------------------------------------------------


} // namespace

#include "bmundef.h"

#ifdef _MSC_VER
#pragma warning( pop )
#endif


#endif