bm.h

Go to the documentation of this file.

Go to the SVN repository for this file.

#ifndef BM__H__INCLUDED__
#define BM__H__INCLUDED__
/*
Copyright(c) 2002-2019 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
 
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
 
    http://www.apache.org/licenses/LICENSE-2.0
 
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
 
For more information please visit:  http://bitmagic.io
*/
 
/*! \file bm.h
    \brief Compressed bit-vector bvector<> container, set algebraic methods, traversal iterators
*/
 
 
// 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>
# include <initializer_list>
# include <stdexcept>
#endif
 
#include <limits.h>
 
#ifdef _MSC_VER
#pragma warning( push )
#pragma warning( disable : 4311 4312 4127)
#endif
 
 
#include "bmdef.h"
#include "bmconst.h"
#include "bmsimd.h"
#include "bmfwd.h"
 
# define BM_DECLARE_TEMP_BLOCK(x) bm::bit_block_t x;
 
#include "bmfunc.h"
#include "encoding.h"
#include "bmalloc.h"
#include "bmblocks.h"
#include "bmbuffer.h"
#include "bmdef.h"
 
#include "bmrs.h"
 
extern "C"
{
#ifdef BM64ADDR
    typedef int (*bit_visitor_callback_type)(void* handle_ptr, bm::id64_t bit_idx);
#else
    /**
    Callback type to visit (callback style) bits in bit-vector(s)
    
    @param handle_ptr - custom pointer to callback specific data
    @param bit_idx - number/index of visited bit
    @return negative return code is recognised as a request to interrupt visiting
    
    @ingroup bvector
    */
    typedef int (*bit_visitor_callback_type)(void* handle_ptr, bm::id_t bit_idx);
#endif
}
 
 
namespace bm
{
 
/** @defgroup bmagic BitMagic Library
    BitMagic C++ Library
    For more information please visit: http://bitmagic.io
*/
 
 
/** @defgroup bvector bvector<> container
    The Main bvector<> Group
    bvector<> template: front end of the BitMagic library.
 
    @ingroup bmagic
*/
 
/** @defgroup bvit bvector<> iterators
    Iterators for compressed bit-vector traversal
    @ingroup bvector
*/
 
 
 
#ifdef BM64ADDR
    typedef bm::id64_t   bvector_size_type;
#else
    typedef bm::id_t     bvector_size_type;
#endif
 
 
/*!
   @brief Bitvector
   Bit-vector container with runtime compression of bits
 
   @ingroup bvector
*/
template<class Alloc> 
class bvector
{
public:
    typedef Alloc                                        allocator_type;
    typedef typename allocator_type::allocator_pool_type allocator_pool_type;
    typedef blocks_manager<Alloc>                        blocks_manager_type;
    typedef typename blocks_manager_type::block_idx_type block_idx_type;
    typedef bvector_size_type                            size_type;
 
    /** Statistical information about bitset's memory allocation details. */
    struct statistics : public bv_statistics
    {};
    
    /*!
        \brief Optimization mode
        Every next level means additional checks (better compression vs time)
        \sa optimize
    */
    enum optmode
    {
        opt_none      = 0, ///< no optimization
        opt_free_0    = 1, ///< Free unused 0 blocks
        opt_free_01   = 2, ///< Free unused 0 and 1 blocks
        opt_compress  = 3  ///< compress blocks when possible (GAP/prefix sum)
    };
 
 
    /**
        @brief Class reference implements an object for bit assignment.
        Since C++ does not provide with build-in bit type supporting l-value 
        operations we have to emulate it.
 
        @ingroup bvector
    */
    class reference
    {
    public:
        reference(bvector<Alloc>& bv, size_type position) BMNOEXCEPT
        : bv_(bv),
          position_(position)
        {}
 
        reference(const reference& ref) BMNOEXCEPT
        : bv_(ref.bv_), 
          position_(ref.position_)
        {
            bv_.set(position_, ref.bv_.get_bit(position_));
        }
        
        operator bool() const BMNOEXCEPT
        {
            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 BMNOEXCEPT
        {
            bv_.set(position_, value);
            return *this;
        }
 
        bool operator==(const reference& ref) const BMNOEXCEPT
        {
            return bool(*this) == bool(ref);
        }
 
        /*! Bitwise AND. Performs operation: bit = bit AND value */
        const reference& operator&=(bool value) const
        {
            bv_.set_bit_and(position_, value);
            return *this;
        }
 
        /*! Bitwise OR. Performs operation: bit = bit OR value */
        const reference& operator|=(bool value) const
        {
            if (value != bv_.get_bit(position_))
            {
                bv_.set_bit(position_);
            }
            return *this;
        }
 
        /*! Bitwise exclusive-OR (XOR). Performs operation: bit = bit XOR value */
        const reference& operator^=(bool value) const
        {
            bv_.set(position_, value != bv_.get_bit(position_));
            return *this;
        }
 
        /*! Logical Not operator */
        bool operator!() const BMNOEXCEPT
        {
            return !bv_.get_bit(position_);
        }
 
        /*! Bit Not operator */
        bool operator~() const BMNOEXCEPT
        {
            return !bv_.get_bit(position_);
        }
 
        /*! Negates the bit value */
        reference& flip()
        {
            bv_.flip(position_);
            return *this;
        }
 
    private:
        bvector<Alloc>&   bv_;       //!< Reference variable on the parent.
        size_type         position_; //!< Position in the parent bitvector.
    };
 
    typedef bool const_reference;
 
    /*!
        @brief Base class for all iterators.
        @ingroup bvit
    */
    class iterator_base
    {
    friend class bvector;
    public:
        iterator_base() BMNOEXCEPT 
            : bv_(0), position_(bm::id_max), block_(0), block_type_(0),
              block_idx_(0)
        {}
 
        bool operator==(const iterator_base& it) const BMNOEXCEPT
        {
            return (position_ == it.position_) && (bv_ == it.bv_);
        }
 
        bool operator!=(const iterator_base& it) const BMNOEXCEPT
        {
            return ! operator==(it);
        }
 
        bool operator < (const iterator_base& it) const BMNOEXCEPT
        {
            return position_ < it.position_;
        }
 
        bool operator <= (const iterator_base& it) const BMNOEXCEPT
        {
            return position_ <= it.position_;
        }
 
        bool operator > (const iterator_base& it) const BMNOEXCEPT
        {
            return position_ > it.position_;
        }
 
        bool operator >= (const iterator_base& it) const BMNOEXCEPT
        {
            return position_ >= it.position_;
        }
 
        /**
           \fn bool bm::bvector::iterator_base::valid() const
           \brief Checks if iterator is still valid. Analog of != 0 comparison for pointers.
           \returns true if iterator is valid.
        */
        bool valid() const BMNOEXCEPT { return position_ != bm::id_max; }
 
        /**
           \fn bool bm::bvector::iterator_base::invalidate() 
           \brief Turns iterator into an invalid state.
        */
        void invalidate() BMNOEXCEPT
            { position_ = bm::id_max; block_type_ = ~0u;}
        
        /** \brief Compare FSMs for testing purposes
            \internal
        */
        bool compare_state(const iterator_base& ib) const BMNOEXCEPT
        {
            if (this->bv_ != ib.bv_)                 return false;
            if (this->position_ != ib.position_)     return false;
            if (this->block_ != ib.block_)           return false;
            if (this->block_type_ != ib.block_type_) return false;
            if (this->block_idx_ != ib.block_idx_)   return false;
            
            const block_descr& bd = this->bdescr_;
            const block_descr& ib_db = ib.bdescr_;
 
            if (this->block_type_ == 0) // bit block
            {
                if (bd.bit_.ptr != ib_db.bit_.ptr) return false;
                if (bd.bit_.idx != ib_db.bit_.idx) return false;
                if (bd.bit_.cnt != ib_db.bit_.cnt) return false;
                if (bd.bit_.pos != ib_db.bit_.pos) return false;
                for (unsigned i = 0; i < bd.bit_.cnt; ++i)
                {
                    if (bd.bit_.bits[i] != ib_db.bit_.bits[i]) return false;
                }
            }
            else // GAP block
            {
                if (bd.gap_.ptr != ib_db.gap_.ptr) return false;
                if (bd.gap_.gap_len != ib_db.gap_.gap_len) return false;
            }
            return true;
        }
 
    public:
 
        /** Bit-block descriptor
            @internal
        */
        struct bitblock_descr
        {
            const bm::word_t*   ptr;      //!< Word pointer.
            unsigned char       bits[set_bitscan_wave_size*32]; //!< bit list
            unsigned short      idx;      //!< Current position in the bit list
            unsigned short      cnt;      //!< Number of ON bits
            size_type           pos;      //!< Last bit position decode before
        };
 
        /** Information about current DGAP block.
            @internal
        */
        struct dgap_descr
        {
            const gap_word_t*   ptr;       //!< Word pointer.
            gap_word_t          gap_len;   //!< Current dgap length.
        };
 
    protected:
        bm::bvector<Alloc>*     bv_;         //!< Pointer on parent bitvector
        size_type               position_;   //!< Bit position (bit idx)
        const bm::word_t*       block_;      //!< Block pointer.(NULL-invalid)
        unsigned                block_type_; //!< Type of block. 0-Bit, 1-GAP
        block_idx_type          block_idx_;  //!< Block index
 
        /*! Block type dependent information for current block. */
        union block_descr
        {
            bitblock_descr   bit_;  //!< BitBlock related info.
            dgap_descr       gap_;  //!< DGAP block related info.
        } bdescr_;
    };
 
    /*!
        @brief Output iterator iterator designed to set "ON" bits based on
        input sequence of integers (bit indeces).
 
        STL container can be converted to bvector using this iterator
        Insert iterator guarantees the vector will be dynamically resized
        (set_bit does not do that).
 
        @note
        If you have many bits to set it is a good idea to use output iterator
        instead of explicitly calling set, because iterator may implement
        some performance specific tricks to make sure bulk insert is fast.
 
        @sa bulk_insert_iterator
 
        @ingroup bvit
    */
    class insert_iterator
    {
    friend class bulk_insert_iterator;
    public:
#ifndef BM_NO_STL
        typedef std::output_iterator_tag  iterator_category;
#endif
        typedef bm::bvector<Alloc> bvector_type;
        typedef size_type          value_type;
        typedef void               difference_type;
        typedef void               pointer;
        typedef void               reference;
 
        insert_iterator() BMNOEXCEPT : bvect_(0), max_bit_(0) {}
 
        insert_iterator(bvector<Alloc>& bvect) BMNOEXCEPT
            : bvect_(&bvect), 
              max_bit_(bvect.size())
        {
            bvect_->init();
        }
        
        insert_iterator(const insert_iterator& iit)
        : bvect_(iit.bvect_),
          max_bit_(iit.max_bit_)
        {
        }
        
        insert_iterator& operator=(const insert_iterator& ii)
        {
            bvect_ = ii.bvect_; max_bit_ = ii.max_bit_;
            return *this;
        }
 
        insert_iterator& operator=(size_type n)
        {
            BM_ASSERT(n < bm::id_max);
            BM_ASSERT_THROW(n < bm::id_max, BM_ERR_RANGE);
 
            if (n >= max_bit_) 
            {
                max_bit_ = n;
                if (n >= bvect_->size()) 
                {
                    size_type new_size = (n == bm::id_max) ? bm::id_max : n + 1;
                    bvect_->resize(new_size);
                }
            }
            bvect_->set_bit_no_check(n);
            return *this;
        }
        /*! Returns *this without doing anything (no-op) */
        insert_iterator& operator*() { return *this; }
        /*! Returns *this. This iterator does not move (no-op) */
        insert_iterator& operator++() { return *this; }
        /*! Returns *this. This iterator does not move (no-op)*/
        insert_iterator& operator++(int) { return *this; }
        
        bvector_type* get_bvector() const { return bvect_; }
        
    protected:
        bvector_type*         bvect_;
        size_type             max_bit_;
    };
    
    
    /*!
        @brief Output iterator iterator designed to set "ON" bits based on
        input sequence of integers.
 
        STL container can be converted to bvector using this iterator
        Insert iterator guarantees the vector will be dynamically resized
        (set_bit does not do that).
     
        The difference from the canonical insert iterator, is that
        bulk insert implements internal buffering, which needs
        to flushed (or flushed automatically when goes out of scope).
        Buffering creates a delayed effect, which needs to be
        taken into account.
     
        @sa insert_iterator
 
        @ingroup bvit
    */
    class bulk_insert_iterator
    {
    public:
#ifndef BM_NO_STL
        typedef std::output_iterator_tag  iterator_category;
#endif
        typedef bm::bvector<Alloc>       bvector_type;
        typedef bvector_type::size_type  size_type;
        typedef bvector_type::size_type  value_type;
        typedef void                     difference_type;
        typedef void                     pointer;
        typedef void                     reference;
 
        bulk_insert_iterator() BMNOEXCEPT
            : bvect_(0), buf_(0), buf_size_(0), sorted_(BM_UNKNOWN) {}
        
        ~bulk_insert_iterator()
        {
            flush();
            if (buf_)
                bvect_->blockman_.get_allocator().free_bit_block((bm::word_t*)buf_);
        }
 
        bulk_insert_iterator(bvector<Alloc>& bvect,
                             bm::sort_order so = BM_UNKNOWN) BMNOEXCEPT
            : bvect_(&bvect), sorted_(so)
        {
            bvect_->init();
            
            buf_ = (value_type*) bvect_->blockman_.get_allocator().alloc_bit_block();
            buf_size_ = 0;
        }
 
        bulk_insert_iterator(const bulk_insert_iterator& iit)
            : bvect_(iit.bvect_)
        {
            buf_ = bvect_->blockman_.get_allocator().alloc_bit_block();
            buf_size_ = iit.buf_size_;
            sorted_ = iit.sorted_;
            ::memcpy(buf_, iit.buf_, buf_size_ * sizeof(*buf_));
        }
        
        bulk_insert_iterator(const insert_iterator& iit)
            : bvect_(iit.get_bvector())
        {
            buf_ = (value_type*) bvect_->blockman_.get_allocator().alloc_bit_block();
            buf_size_ = 0;
            sorted_ = BM_UNKNOWN;
        }
 
        bulk_insert_iterator(bulk_insert_iterator&& iit) BMNOEXCEPT
            : bvect_(iit.bvect_)
        {
            buf_ = iit.buf_; iit.buf_ = 0;
            buf_size_ = iit.buf_size_;
            sorted_ = iit.sorted_;
        }
        
        bulk_insert_iterator& operator=(const bulk_insert_iterator& ii)
        {
            bvect_ = ii.bvect_;
            if (!buf_)
                buf_ = bvect_->allocate_tempblock();
            buf_size_ = ii.buf_size_;
            ::memcpy(buf_, ii.buf_, buf_size_ * sizeof(*buf_));
            sorted_ = ii.sorted_;
            return *this;
        }
        
        bulk_insert_iterator& operator=(bulk_insert_iterator&& ii) BMNOEXCEPT
        {
            bvect_ = ii.bvect_;
            if (buf_)
                bvect_->free_tempblock(buf_);
            buf_ = ii.buf_; ii.buf_ = 0;
            buf_size_ = ii.buf_size_;
            sorted_ = ii.sorted_;
            return *this;
        }
 
        bulk_insert_iterator& operator=(size_type n)
        {
            BM_ASSERT(n < bm::id_max);
            BM_ASSERT_THROW(n < bm::id_max, BM_ERR_RANGE);
 
            if (buf_size_ == buf_size_max())
            {
                bvect_->import(buf_, buf_size_, sorted_);
                buf_size_ = 0;
            }
            buf_[buf_size_++] = n;
            return *this;
        }
        
        /*! Returns *this without doing anything (no-op) */
        bulk_insert_iterator& operator*() { return *this; }
        /*! Returns *this. This iterator does not move (no-op) */
        bulk_insert_iterator& operator++() { return *this; }
        /*! Returns *this. This iterator does not move (no-op)*/
        bulk_insert_iterator& operator++(int) { return *this; }
        
        /*! Flush the internal buffer into target bvector */
        void flush()
        {
            BM_ASSERT(bvect_);
            if (buf_size_)
            {
                bvect_->import(buf_, buf_size_, sorted_);
                buf_size_ = 0;
            }
            bvect_->sync_size();
        }
        
        bvector_type* get_bvector() const BMNOEXCEPT { return bvect_; }
        
    protected:
        static
        size_type buf_size_max() BMNOEXCEPT
        {
            #ifdef BM64ADDR
                return bm::set_block_size / 2;
            #else
                return bm::set_block_size;
            #endif
        }
 
    protected:
        bvector_type*         bvect_;    ///< target bvector
        size_type*            buf_;      ///< bulk insert buffer
        size_type             buf_size_; ///< current buffer size
        bm::sort_order        sorted_;   ///< sort order hint
    };
    
 
 
    /*! @brief Constant iterator designed to enumerate "ON" bits
        @ingroup bvit
    */
    class enumerator : public iterator_base
    {
    public:
#ifndef BM_NO_STL
        typedef std::input_iterator_tag  iterator_category;
#endif
        typedef size_type    value_type;
        typedef unsigned     difference_type;
        typedef unsigned*    pointer;
        typedef unsigned&    reference;
 
    public:
        enumerator() BMNOEXCEPT : iterator_base()
        {}
        
        /*! @brief Construct enumerator associated with a vector.
            Important: This construction creates unpositioned iterator with status
            valid() == false. It can be re-positioned using go_first() or go_to().
            @sa go_to
        */
        enumerator(const bvector<Alloc>* bv) BMNOEXCEPT
            : iterator_base()
        {
            this->bv_ = const_cast<bvector<Alloc>*>(bv);
        }
 
        /*! @brief Construct enumerator for bit vector
            @param bv  bit-vector reference
            @param pos bit position in the vector
                       if position is 0, it finds the next 1 or becomes not valid
                       (en.valid() == false)
        */
        enumerator(const bvector<Alloc>& bv, size_type pos = 0) BMNOEXCEPT
            : iterator_base()
        {
            this->bv_ = const_cast<bvector<Alloc>*>(&bv);
            go_to(pos);
        }
 
 
        /*! @brief Construct enumerator for bit vector
            @param bv  bit-vector pointer
            @param pos bit position in the vector
                       if position is 0, it finds the next 1 or becomes not valid
                       (en.valid() == false)
        */
        enumerator(const bvector<Alloc>* bv, size_type pos) BMNOEXCEPT
            : iterator_base()
        { 
            this->bv_ = const_cast<bvector<Alloc>*>(bv);
            this->go_to(pos);
        }
 
        /*! \brief Get current position (value) */
        size_type operator*() const BMNOEXCEPT { return this->position_; }
 
        /*! \brief Get current position (value) */
        size_type value() const BMNOEXCEPT { return this->position_; }
        
        /*! \brief Advance enumerator forward to the next available bit */
        enumerator& operator++() BMNOEXCEPT { this->go_up(); return *this; }
 
        /*! \brief Advance enumerator forward to the next available bit.
             Possibly do NOT use this operator it is slower than the pre-fix increment.
         */
        enumerator operator++(int) BMNOEXCEPT
        {
            enumerator tmp = *this;
            this->go_up();
            return tmp;
        }
 
        /*! \brief Position enumerator to the first available bit */
        void go_first() BMNOEXCEPT;
 
        /*! advance iterator forward by one
            @return true if advance was successfull and the enumerator is valid
        */
        bool advance() BMNOEXCEPT { return this->go_up(); }
 
        /*! \brief Advance enumerator to the next available bit */
        bool go_up() BMNOEXCEPT;
 
        /*!
            @brief Skip to specified relative rank
            @param rank - number of ON bits to go for (must be: > 0)
            @return true if skip was successfull and enumerator is valid
        */
        bool skip_to_rank(size_type rank) BMNOEXCEPT
        {
            BM_ASSERT(rank);
            --rank;
            if (!rank)
                return this->valid();
            return skip(rank);
        }
        
        /*!
            @brief Skip specified number of bits from enumeration
            @param rank - number of ON bits to skip
            @return true if skip was successfull and enumerator is valid
        */
        bool skip(size_type rank) BMNOEXCEPT;
 
        /*!
            @brief go to a specific position in the bit-vector (or next)
        */
        bool go_to(size_type pos) BMNOEXCEPT;
 
    private:
        typedef typename iterator_base::block_descr block_descr_type;
        
        static bool decode_wave(block_descr_type* bdescr) BMNOEXCEPT;
        bool decode_bit_group(block_descr_type* bdescr) BMNOEXCEPT;
        bool decode_bit_group(block_descr_type* bdescr,
                              size_type& rank) BMNOEXCEPT;
        bool search_in_bitblock() BMNOEXCEPT;
        bool search_in_gapblock() BMNOEXCEPT;
        bool search_in_blocks() BMNOEXCEPT;
 
    };
    
    /*!
        @brief Constant iterator designed to enumerate "ON" bits
        counted_enumerator keeps bitcount, ie number of ON bits starting
        from the position 0 in the bit string up to the currently enumerated bit
        
        When increment operator called current position is increased by 1.
        
        @ingroup bvit
    */
    class counted_enumerator : public enumerator
    {
    public:
#ifndef BM_NO_STL
        typedef std::input_iterator_tag  iterator_category;
#endif
        counted_enumerator() BMNOEXCEPT : bit_count_(0){}
        
        counted_enumerator(const enumerator& en) BMNOEXCEPT : enumerator(en)
        {
            bit_count_ = this->valid(); // 0 || 1
        }
        
        counted_enumerator& operator=(const enumerator& en) BMNOEXCEPT
        {
            enumerator* me = this;
            *me = en;
            if (this->valid())
                this->bit_count_ = 1;
            return *this;
        }
        
        counted_enumerator& operator++() BMNOEXCEPT
        {
            this->go_up();
            this->bit_count_ += this->valid();
            return *this;
        }
 
        counted_enumerator operator++(int)
        {
            counted_enumerator tmp(*this);
            this->go_up();
            this->bit_count_ += this->valid();
            return tmp;
        }
        
        /*! @brief Number of bits ON starting from the .
        
            Method returns number of ON bits fromn the bit 0 to the current bit 
            For the first bit in bitvector it is 1, for the second 2 
        */
        size_type count() const BMNOEXCEPT { return bit_count_; }
    private:
        /*! Function closed for usage */
        counted_enumerator& go_to(size_type pos);
 
    private:
        size_type   bit_count_;
    };
 
    /*! 
        Resource guard for bvector<>::set_allocator_pool()
        @ingroup bvector
        @internal
    */
    typedef
    bm::alloc_pool_guard<allocator_pool_type, bvector<Alloc> > mem_pool_guard;
 
    friend class iterator_base;
    friend class enumerator;
    template<class BV> friend class aggregator;
    template<class BV> friend class operation_deserializer;
    template<class BV, class DEC> friend class deserializer;
 
public:
    /*! @brief memory allocation policy
    
        Defualt memory allocation policy uses BM_BIT, and standard 
        GAP levels tune-ups
    */
    struct allocation_policy
    {
        bm::strategy  strat;
        const         gap_word_t* glevel_len;
        
        allocation_policy(bm::strategy s=BM_BIT,
            const gap_word_t* glevels = bm::gap_len_table<true>::_len) BMNOEXCEPT
        : strat(s), glevel_len(glevels)
        {}
    };
    
    typedef rs_index<allocator_type> blocks_count;
    typedef rs_index<allocator_type> rs_index_type;
    
public:
    /*! @name Construction, initialization, assignment */
    //@{
    
    /*!
        \brief Constructs bvector class
        \param strat - operation mode strategy, 
                       BM_BIT - default strategy, bvector use plain bitset 
                       blocks, (performance oriented strategy).
                       BM_GAP - memory effitent strategy, bvector allocates 
                       blocks as array of intervals(gaps) and convert blocks 
                       into plain bitsets only when enthropy grows.
        \param glevel_len 
           - pointer on C-style array keeping GAP block sizes. 
            bm::gap_len_table<true>::_len - default value set
            (use bm::gap_len_table_min<true>::_len for very sparse vectors)
            (use bm::gap_len_table_nl<true>::_len non-linear GAP growth)
        \param bv_size
          - bvector size (number of bits addressable by bvector), bm::id_max means 
          "no limits" (recommended). 
          bit vector allocates this space dynamically on demand.
        \param alloc - alllocator for this instance
         
        \sa bm::gap_len_table bm::gap_len_table_min set_new_blocks_strat
    */
    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)
    {}
 
    /*!
        \brief Constructs bvector class
    */
    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)
    {}
 
    /*!
        \brief Copy constructor
    */
    bvector(const bvector<Alloc>& bvect)
        :  blockman_(bvect.blockman_),
           new_blocks_strat_(bvect.new_blocks_strat_),
           size_(bvect.size_)
    {}
    
    /*!
        \brief Copy constructor for range copy [left..right]
        \sa copy_range
    */
    bvector(const bvector<Alloc>& bvect, size_type left, size_type right)
        : blockman_(bvect.blockman_.glevel_len_, bvect.blockman_.max_bits_, bvect.blockman_.alloc_),
          new_blocks_strat_(bvect.new_blocks_strat_),
          size_(bvect.size_)
    {
        if (!bvect.blockman_.is_init())
            return;
        if (left > right)
            bm::xor_swap(left, right);
        copy_range_no_check(bvect, left, right);
    }
 
    /*!
        \brief Copy-constructor for mutable/immutable initialization
    */
    bvector(const bvector<Alloc>& bvect, bm::finalization is_final)
    : blockman_(bvect.blockman_.glevel_len_, bvect.blockman_.max_bits_, bvect.blockman_.alloc_),
      new_blocks_strat_(bvect.new_blocks_strat_),
      size_(bvect.size_)
    {
        if (!bvect.blockman_.is_init())
            return;
        if (is_final == bm::finalization::READONLY)
            blockman_.copy_to_arena(bvect.blockman_);
        else
            blockman_.copy(bvect.blockman_);
    }
 
    
    ~bvector() BMNOEXCEPT {}
 
    /*!
        \brief Explicit post-construction initialization.
        Must be caled to make sure safe use of *_no_check() methods
    */
    void init();
 
    /*!
        \brief Explicit post-construction initialization.
        Must be caled right after construction strickly before any modificating calls
        to make sure safe use of *_no_check() methods.
        This init can do pre-allocation of top level structures.
 
        @param top_size - request to do pre-allocation of the top level of a sparse bit-vector tree
        (can be up to 256 for 32-bit mode)
        @param alloc_subs - if true also allocates second level structures
    */
    void init(unsigned top_size, bool alloc_subs);
 
 
    /*! 
        \brief Copy assignment operator
    */
    bvector& operator=(const bvector<Alloc>& bvect)
    {
        this->copy(bvect, bm::finalization::UNDEFINED);
        return *this;
    }
 
#ifndef BM_NO_CXX11
    /*!
        \brief Move constructor
    */
    bvector(bvector<Alloc>&& bvect) BMNOEXCEPT
    {
        blockman_.move_from(bvect.blockman_);
        size_ = bvect.size_;
        new_blocks_strat_ = bvect.new_blocks_strat_;
    }
 
    /*!
        \brief Brace constructor
    */
    bvector(std::initializer_list<size_type> il)
        : blockman_(bm::gap_len_table<true>::_len, bm::id_max, Alloc()),
          new_blocks_strat_(BM_BIT),
          size_(bm::id_max)
    {
        init();
        std::initializer_list<size_type>::const_iterator it_start = il.begin();
        std::initializer_list<size_type>::const_iterator it_end = il.end();
        for (; it_start < it_end; ++it_start)
            this->set_bit_no_check(*it_start);
    }
    
    /*! 
        \brief Move assignment operator
    */
    bvector& operator=(bvector<Alloc>&& bvect) BMNOEXCEPT
    {
        this->move_from(bvect);
        return *this;
    }
#endif
 
    /*!
        \brief Copy bvector from the argument bvector
        \param bvect - bit-vector to copy from
        \param is_final - BM_READONLY - copies as immutable, BM_READWRITE - copies as mutable
            even if the argument bvect is read-only vector,
            BM_UNDEFINED - follow the argument type as is
    */
    void copy(const bvector<Alloc>& bvect, bm::finalization is_final);
 
    /*!
        \brief Move bvector content from another bvector
    */
    void move_from(bvector<Alloc>& bvect) BMNOEXCEPT;
    
    /*! \brief Exchanges content of bv and this bvector.
    */
    void swap(bvector<Alloc>& bvect) BMNOEXCEPT;
 
    /*! \brief Merge/move content from another vector
    
        Merge performs a logical OR operation, but the source vector
        is not immutable. Source content gets destroyed (memory moved)
        to create a union of two vectors.
        Merge operation can be more efficient than OR if argument is
        a temporary vector.
    
        @param bvect - [in, out] - source vector (NOT immutable)
    */
    void merge(bm::bvector<Alloc>& bvect);
 
    //@}
 
    reference operator[](size_type n)
    {
        if (n >= size_)
        {
            size_type new_size = (n == bm::id_max) ? bm::id_max : n + 1;
            resize(new_size);
        }
        return reference(*this, n);
    }
 
    bool operator[](size_type n) const BMNOEXCEPT
    {
        BM_ASSERT(n < size_);
        return get_bit(n);
    }
 
    void operator &= (const bvector<Alloc>& bv) { bit_and(bv); }
    void operator ^= (const bvector<Alloc>& bv) { bit_xor(bv); }
    void operator |= (const bvector<Alloc>& bv) { bit_or(bv);  }
    void operator -= (const bvector<Alloc>& bv) { bit_sub(bv); }
 
    bool operator < (const bvector<Alloc>& bv) const { return compare(bv)<0; }
    bool operator <= (const bvector<Alloc>& bv) const { return compare(bv)<=0; }
    bool operator > (const bvector<Alloc>& bv) const { return compare(bv)>0; }
    bool operator >= (const bvector<Alloc>& bv) const { return compare(bv) >= 0; }
    bool operator == (const bvector<Alloc>& bv) const BMNOEXCEPT { return equal(bv); }
    bool operator != (const bvector<Alloc>& bv) const BMNOEXCEPT { return !equal(bv); }
 
    bvector<Alloc> operator~() const { return bvector<Alloc>(*this).invert(); }
    
    Alloc get_allocator() const
        { return blockman_.get_allocator(); }
 
    /// Set allocator pool for local (non-th readed) 
    /// memory cyclic(lots of alloc-free ops) opertations
    ///
    void set_allocator_pool(allocator_pool_type* pool_ptr) BMNOEXCEPT
                        { blockman_.get_allocator().set_pool(pool_ptr); }
 
    /// Get curent allocator pool (if set)
    /// @return pointer to the current pool or NULL
    allocator_pool_type* get_allocator_pool() BMNOEXCEPT
                        { return blockman_.get_allocator().get_pool(); }
 
    // --------------------------------------------------------------------
    /*! @name Read-only / immutable vector methods  */
    //@{
 
    /// Turn current vector to read-only (immutable vector).
    /// After calling this method any modification (non-const methods) will cause undefined behavior
    /// (likely crash or assert)
    ///
    /// \sa is_ro
    void freeze();
 
    /// Returns true if vector is read-only
    bool is_ro() const BMNOEXCEPT { return blockman_.arena_; }
 
    //@}
 
    // --------------------------------------------------------------------
    /*! @name Bit access/modification methods  */
    //@{
 
    /*!
       \brief Sets bit n.
       \param n - index of the bit to be set. 
       \param val - new bit value
       \return  TRUE if bit was changed
    */
    bool set_bit(size_type n, bool val = true);
 
    /*!
       \brief Sets bit n using bit AND with the provided value.
       \param n - index of the bit to be set. 
       \param val - new bit value
       \return  TRUE if bit was changed
    */
    bool set_bit_and(size_type n, bool val = true);
    
    /*!
       \brief Increment the specified element
     
       Bit increment rules:
        0 + 1 = 1 (no carry over)
        1 + 1 = 0 (with carry over returned)
     
       \param n - index of the bit to be set
       \return  TRUE if carry over created (1+1)
    */
    bool inc(size_type n);
    
 
    /*!
       \brief Sets bit n only if current value equals the condition
       \param n - index of the bit to be set. 
       \param val - new bit value
       \param condition - expected current value
       \return TRUE if bit was changed
    */
    bool set_bit_conditional(size_type n, bool val, bool condition);
 
    /*!
        \brief Sets bit n if val is true, clears bit n if val is false
        \param n - index of the bit to be set
        \param val - new bit value
        \return *this
    */
    bvector<Alloc>& set(size_type n, bool val = true);
 
    /*!
       \brief Sets every bit in this bitset to 1.
       \return *this
    */
    bvector<Alloc>& set();
    
    /*!
       \brief Set list of bits in this bitset to 1.
     
       Method implements optimized bulk setting of multiple bits at once.
       The best results are achieved when the imput comes sorted.
       This is equivalent of OR (Set Union), argument set as an array.
     
       @param ids  - pointer on array of indexes to set
       @param ids_size - size of the input (ids)
       @param so   - sort order (use BM_SORTED for faster load)
     
       @sa keep, clear
    */
    void set(const size_type* ids, size_type ids_size,
             bm::sort_order so=bm::BM_UNKNOWN);
    
    /*!
       \brief Keep list of bits in this bitset, others are cleared
     
       This is equivalent of AND (Set Intersect), argument set as an array.
     
       @param ids  - pointer on array of indexes to set
       @param ids_size - size of the input (ids)
       @param so   - sort order (use BM_SORTED for faster load)
     
       @sa set, clear
    */
    void keep(const size_type* ids, size_type ids_size,
              bm::sort_order so=bm::BM_UNKNOWN);
 
    /*!
       \brief clear list of bits in this bitset
     
       This is equivalent of AND NOT (Set Substract), argument set as an array.
     
       @param ids  - pointer on array of indexes to set
       @param ids_size - size of the input (ids)
       @param so   - sort order (use BM_SORTED for faster load)
     
       @sa set, keep
    */
    void clear(const size_type* ids, size_type ids_size,
               bm::sort_order so=bm::BM_UNKNOWN);
 
    /*!
       \brief swap values of bits
 
       @param idx1  - index of bit to swap with
       @param idx2  - index of bit to swap with
    */
    void swap(size_type idx1, size_type idx2);
 
 
    /*!
        \brief Set bit without checking preconditions (size, etc)
     
        Fast set bit method, without safety net.
        Make sure you call bvector<>::init() before setting bits with this
        function.
     
        \param n - bit number
    */
    void set_bit_no_check(size_type n);
 
    /**
        \brief Set specified bit without checking preconditions (size, etc)
    */
    bool set_bit_no_check(size_type n, bool val);
 
    /*!
        \brief Sets all bits in the specified closed interval [left,right]
        Interval must be inside the bvector's size. 
        This method DOES NOT resize vector.
        
        \param left  - interval start
        \param right - interval end (closed interval)
        \param value - value to set interval in
        
        \return *this
        @sa clear_range
    */
    bvector<Alloc>& set_range(size_type left,
                              size_type right,
                              bool     value = true);
 
 
    /*!
        \brief Sets all bits to zero in the specified closed interval [left,right]
        Interval must be inside the bvector's size.
        This method DOES NOT resize vector.
 
        \param left  - interval start
        \param right - interval end (closed interval)
 
        @sa set_range
    */
    void clear_range(size_type left, size_type right)
                        { set_range(left, right, false); }
 
 
    /*!
        \brief Sets all bits to zero outside of the closed interval [left,right]
        Expected result:  00000...0[left, right]0....0000
 
        \param left  - interval start
        \param right - interval end (closed interval)
 
        @sa set_range
    */
    void keep_range(size_type left, size_type right);
    
    /*!
        \brief Copy all bits in the specified closed interval [left,right]
 
        \param bvect - source bit-vector
        \param left  - interval start
        \param right - interval end (closed interval)
    */
    void copy_range(const bvector<Alloc>& bvect,
                    size_type left,
                    size_type right);
 
    /*!
       \brief Clears bit n.
       \param n - bit's index to be cleaned.
       \return true if bit was cleared
    */
    bool clear_bit(size_type n) { return set_bit(n, false); }
    
    /*!
       \brief Clears bit n without precondiion checks
       \param n - bit's index to be cleaned.
    */
    void clear_bit_no_check(size_type n);
    
    /*!
       \brief Clears every bit in the bitvector.
 
       \param free_mem if "true" (default) bvector frees the memory,
       otherwise sets blocks to 0.
    */
    void clear(bool free_mem = true) BMNOEXCEPT;
 
    /*!
       \brief Clears every bit in the bitvector.
       \return *this;
    */
    bvector<Alloc>& reset() BMNOEXCEPT { clear(true); return *this; }
    
    /*!
       \brief Flips bit n
       \return *this
    */
    bvector<Alloc>& flip(size_type n) { this->inc(n); return *this; }
 
    /*!
       \brief Flips all bits
       \return *this
       @sa invert
    */
    bvector<Alloc>& flip() { return invert(); }
 
    //@}
    // --------------------------------------------------------------------
 
    
    /*! Function erturns insert iterator for this bitvector */
    insert_iterator inserter() { return insert_iterator(*this); }
 
    // --------------------------------------------------------------------
    /*! @name Size and capacity
        By default bvector is dynamically sized, manual control methods
        available
    */
    //@{
 
    /** \brief Returns bvector's capacity (number of bits it can store) */
    //size_type capacity() const { return blockman_.capacity(); }
 
    /*! \brief return current size of the vector (bits) */
    size_type size() const BMNOEXCEPT { return size_; }
 
    /*!
        \brief Change size of the bvector
        \param new_size - new size in bits
    */
    void resize(size_type new_size);
    
    //@}
    // --------------------------------------------------------------------
 
    /*! @name Population counting, ranks, ranges and intervals
    */
    //@{
 
    /*!
       \brief population count (count of ON bits)
       \sa count_range
       \return Total number of bits ON
    */
    size_type count() const BMNOEXCEPT;
 
    /*! \brief Computes bitcount values for all bvector blocks
        \param arr - pointer on array of block bit counts
        \return Index of the last block counted. 
        This number +1 gives you number of arr elements initialized during the
        function call.
    */
    block_idx_type count_blocks(unsigned* arr) const BMNOEXCEPT;
 
 
    /*!
       \brief Returns count of 1 bits in the given range [left..right]
       Uses rank-select index to accelerate the search
       \param left   - index of first bit start counting from
       \param right  - index of last bit
       \param rs_idx - block count structure to accelerate search
       \sa build_rs_index
 
       \return population count in the diapason
    */
    size_type count_range(size_type left,
                          size_type right,
                          const rs_index_type&  rs_idx) const BMNOEXCEPT;
    
    /*!
       \brief Returns count of 1 bits in the given range [left..right]
     
       \param left - index of first bit start counting from
       \param right - index of last bit
 
       \return population count in the diapason
       @sa count_range_no_check
    */
    size_type count_range(size_type left, size_type right) const BMNOEXCEPT;
 
    /*!
        Returns count of 1 bits in the given range [left..right]
        Function expects that caller guarantees that left < right
 
        @sa count_range
    */
    size_type count_range_no_check(size_type left, size_type right) const BMNOEXCEPT;
 
 
    /*!
        Returns count of 1 bits in the given range [left..right]
        Function expects that caller guarantees that left < right
 
        @sa count_range
    */
    size_type count_range_no_check(size_type left,
                                   size_type right,
                                const rs_index_type&  rs_idx) const BMNOEXCEPT;
 
    /*!
       \brief Returns true if all bits in the range are 1s (saturated interval)
       Function uses closed interval [left, right]
 
       \param left - index of first bit start checking
       \param right - index of last bit
 
       \return true if all bits are 1, false otherwise
       @sa any_range, count_range
    */
    bool is_all_one_range(size_type left, size_type right) const BMNOEXCEPT;
 
    /*!
       \brief Returns true if any bits in the range are 1s (non-empty interval)
       Function uses closed interval [left, right]
 
       \param left - index of first bit start checking
       \param right - index of last bit
 
       \return true if at least 1 bits is set
       @sa is_all_one_range, count_range
    */
    bool any_range(size_type left, size_type right) const BMNOEXCEPT;
 
 
    /*! \brief compute running total of all blocks in bit vector (rank-select index)
        \param rs_idx - [out] pointer to index / count structure
        \param bv_blocks - [out] list of block ids in the vector (internal, optional)
        Function will fill full array of running totals
        \sa count_to, select, find_rank
    */
    void build_rs_index(rs_index_type* rs_idx, bvector<Alloc>* bv_blocks=0) const;
 
    /*!
       \brief Returns count of 1 bits (population) in [0..right] range.
     
       This operation is also known as rank of bit N.
     
       \param n - index of bit to rank
       \param rs_idx - rank-select to accelerate search
                       should be prepared using build_rs_index
       \return population count in the range [0..n]
       \sa build_rs_index
       \sa count_to_test, select, rank, rank_corrected
    */
    size_type count_to(size_type n,
                       const rs_index_type&  rs_idx) const BMNOEXCEPT;
    
    
    /*!
       \brief Returns rank of specified bit position (same as count_to())
     
       \param n - index of bit to rank
       \param rs_idx -  rank-select index
       \return population count in the range [0..n]
       \sa build_rs_index
       \sa count_to_test, select, rank, rank_corrected
    */
    size_type rank(size_type n, 
                   const rs_index_type&  rs_idx) const BMNOEXCEPT
                                    {  return count_to(n, rs_idx); }
    
    /*!
       \brief Returns rank corrceted by the requested border value (as -1)
 
       This is rank function (bit-count) minus value of bit 'n'
       if bit-n is true function returns rank()-1 if false returns rank()
       faster than rank() + test().
 
 
       \param n - index of bit to rank
       \param rs_idx -  rank-select index
       \return population count in the range [0..n] corrected as -1 by the value of n
       \sa build_rs_index
       \sa count_to_test, select, rank
    */
    size_type rank_corrected(size_type n,
                 const rs_index_type&  rs_idx) const BMNOEXCEPT;
 
    /*!
        \brief popcount in [0..right] range if test(right) == true
     
        This is conditional rank operation, which is faster than test()
        plus count_to()
     
        \param n - index of bit to test and rank
        \param rs_idx - rank-select index
                       (block count structure to accelerate search)
                        should be prepared using build_rs_index()
 
        \return population count in the diapason or 0 if right bit test failed
 
        \sa build_rs_index
        \sa count_to
    */
    size_type
    count_to_test(size_type n, 
                  const rs_index_type&  rs_idx) const BMNOEXCEPT;
 
 
    /*! Recalculate bitcount (deprecated)
    */
    size_type recalc_count() BMNOEXCEPT { return count(); }
    
    /*!
        Disables count cache. (deprecated).
    */
    void forget_count() BMNOEXCEPT {}
    
    //@}
    
    // --------------------------------------------------------------------
    /*! @name Bit access (read-only)  */
    //@{
 
    /*!
       \brief returns true if bit n is set and false is bit n is 0. 
       \param n - Index of the bit to check.
       \return Bit value (1 or 0)
    */
    bool get_bit(size_type n) const BMNOEXCEPT;
 
    /*!
       \brief returns true if bit n is set and false is bit n is 0. 
       \param n - Index of the bit to check.
       \return Bit value (1 or 0)
    */
    bool test(size_type n) const BMNOEXCEPT { return get_bit(n); }
    
    //@}
    
    // --------------------------------------------------------------------
    /*! @name bit-shift and insert operations  */
    //@{
    
    /*!
        \brief Shift right by 1 bit, fill with zero return carry out
        \return Carry over bit value (1 or 0)
    */
    bool shift_right();
 
    /*!
        \brief Shift left by 1 bit, fill with zero return carry out
        \return Carry over bit value (1 or 0)
    */
    bool shift_left();
 
    /*!
        \brief Insert bit into specified position
        All the vector content after insert position is shifted right.
     
        \param n - index of the bit to insert
        \param value - insert value
     
        \return Carry over bit value (1 or 0)
    */
    bool insert(size_type n, bool value);
 
    /*!
        \brief Erase bit in the specified position
        All the vector content after erase position is shifted left.
     
        \param n - index of the bit to insert
    */
    void erase(size_type n);
 
    //@}
 
    // --------------------------------------------------------------------
    /*! @name Check for empty-ness of container  */
    //@{
 
    /*!
       \brief Returns true if any bits in this bitset are set, and otherwise returns false.
       \return true if any bit is set
    */
    bool any() const BMNOEXCEPT;
 
    /*!
        \brief Returns true if no bits are set, otherwise returns false.
    */
    bool none() const BMNOEXCEPT { return !any(); }
 
    /**
        \brief Returns true if the set is empty (no bits are set, otherwise returns false)
        Please note that this is NOT a size check, it is an empty SET check (absense of 1s)
     */
    bool empty() const BMNOEXCEPT { return !any(); }
    
    //@}
    // --------------------------------------------------------------------
 
    /*! @name Scan and find bits and indexes */
    //@{
    
    /*!
       \fn bool bvector::find(bm::id_t& pos) const
       \brief Finds index of first 1 bit
       \param pos - [out] index of the found 1 bit
       \return true if search returned result
       \sa get_first, get_next, extract_next, find_reverse, find_first_mismatch
    */
    bool find(size_type& pos) const BMNOEXCEPT;
 
    /*!
       \fn bool bvector::find(bm::id_t from, bm::id_t& pos) const
       \brief Find index of 1 bit starting from position
       \param from - position to start search from, please note that if bit at from position
                    is set then it will be found, function uses closed interval [from...
       \param pos - [out] index of the found 1 bit
       \return true if search returned result
       \sa get_first, get_next, extract_next, find_reverse, find_first_mismatch
    */
    bool find(size_type from, size_type& pos) const BMNOEXCEPT;
 
 
    /*!
       \fn bm::id_t bvector::get_first() const
       \brief find first 1 bit in vector. 
       Function may return 0 and this requires an extra check if bit 0 is 
       actually set or bit-vector is empty
     
       \return Index of the first 1 bit, may return 0
       \sa get_next, find, extract_next, find_reverse
    */
    size_type get_first() const BMNOEXCEPT { return check_or_next(0); }
 
    /*!
       \fn bm::id_t bvector::get_next(bm::id_t prev) const
       \brief Finds the number of the next bit ON.
       \param prev - Index of the previously found bit. 
       \return Index of the next bit which is ON or 0 if not found.
       \sa get_first, find, extract_next, find_reverse
    */
    size_type get_next(size_type prev) const BMNOEXCEPT
                { return (++prev == bm::id_max) ? 0 : check_or_next(prev); }
 
    /*!
       \fn bm::id_t bvector::extract_next(bm::id_t prev)
       \brief Finds the number of the next bit ON and sets it to 0.
       \param prev - Index of the previously found bit. 
       \return Index of the next bit which is ON or 0 if not found.
       \sa get_first, get_next, find_reverse
    */
    size_type extract_next(size_type prev)
    {
        return (++prev == bm::id_max) ? 0 : check_or_next_extract(prev);
    }
 
    /*!
       \brief Finds last index of 1 bit
       \param pos - [out] index of the last found 1 bit
       \return true if search returned result
       \sa get_first, get_next, extract_next,
       \sa find, find_first_mismatch, find_range
    */
    bool find_reverse(size_type& pos) const BMNOEXCEPT;
 
    /*!
       \brief Reverse finds next(prev) index of 1 bit
       \param from - index to search from
       \param pos - [out] found position index
                    (undefined if method returns false)
       \return true if search returned result
       \sa get_first, get_next, extract_next,
       \sa find, find_first_mismatch, find_range
    */
    bool find_reverse(size_type from, size_type& pos) const BMNOEXCEPT;
    
    /*!
       \brief Finds dynamic range of bit-vector [first, last]
       \param first - index of the first found 1 bit
       \param last - index of the last found 1 bit
       \return true if search returned result
       \sa get_first, get_next, extract_next, find, find_reverse
    */
    bool find_range(size_type& first, size_type& last) const BMNOEXCEPT;
    
    /*!
        \brief Find bit-vector position for the specified rank(bitcount)
     
        Rank based search, counts number of 1s from specified position until
        finds the ranked position relative to start from position.
        In other words: range population count between from and pos == rank.
     
        \param rank - rank to find (bitcount)
        \param from - start positioon for rank search
        \param pos  - position with speciefied rank (relative to from position)
     
        \return true if requested rank was found
    */
    bool find_rank(size_type rank, size_type from,
                   size_type& pos) const BMNOEXCEPT;
 
    /*!
        \brief Find bit-vector position for the specified rank(bitcount)
     
        Rank based search, counts number of 1s from specified position until
        finds the ranked position relative to start from position.
        In other words: range population count between from and pos == rank.
     
        \param rank - rank to find (bitcount)
        \param from - start positioon for rank search
        \param pos  - position with speciefied rank (relative to from position)
        \param rs_idx - rank-select index to accelarate search 
                        (should be prepared using build_rs_index)
 
        \sa build_rs_index, select
 
        \return true if requested rank was found
    */
    bool find_rank(size_type rank, size_type from, size_type& pos,
                   const rs_index_type&  rs_idx) const BMNOEXCEPT;
    
    /*!
        \brief select bit-vector position for the specified rank(bitcount)
     
        Rank based search, counts number of 1s from specified position until
        finds the ranked position relative to start from position.
        Uses
        In other words: range population count between from and pos == rank.
     
        \param rank - rank to find (bitcount)
        \param pos  - position with speciefied rank (relative to from position) [out]
        \param rs_idx - block count structure to accelerate rank search
 
        \sa running_count_blocks, find_rank
 
        \return true if requested rank was found
    */
    bool select(size_type rank, size_type& pos,
                const rs_index_type&  rs_idx) const BMNOEXCEPT;
 
    //@}
 
 
    // --------------------------------------------------------------------
    /*! @name Algebra of Sets operations  */
    //@{
 
    /*!
       \brief 3-operand OR : this := bv1 OR bv2
       \param bv1 - Argument vector 1
       \param bv2 - Argument vector 2
       \param opt_mode - optimization compression
         (when it is performed on the fly it is faster than a separate
         call to optimize()
       @sa optimize, bit_or
    */
    bm::bvector<Alloc>& bit_or(const bm::bvector<Alloc>& bv1,
                               const bm::bvector<Alloc>& bv2,
                               typename bm::bvector<Alloc>::optmode opt_mode=opt_none);
 
    /*!
       \brief 3-operand XOR : this := bv1 XOR bv2
       \param bv1 - Argument vector 1
       \param bv2 - Argument vector 2
       \param opt_mode - optimization compression
         (when it is performed on the fly it is faster than a separate
         call to optimize()
       @sa optimize, bit_xor
    */
    bm::bvector<Alloc>& bit_xor(const bm::bvector<Alloc>& bv1,
                                const bm::bvector<Alloc>& bv2,
                                typename bm::bvector<Alloc>::optmode opt_mode=opt_none);
 
    /*!
       \brief 3-operand AND : this := bv1 AND bv2
       \param bv1 - Argument vector 1
       \param bv2 - Argument vector 2
       \param opt_mode - optimization compression
         (when it is performed on the fly it is faster than a separate
         call to optimize()
       @sa optimize, bit_and
    */
    bm::bvector<Alloc>& bit_and(const bm::bvector<Alloc>& bv1,
                                const bm::bvector<Alloc>& bv2,
                                typename bm::bvector<Alloc>::optmode opt_mode=opt_none);
 
 
    /*!
       \brief 3-operand AND where result is ORed into the terget vector : this |= bv1 AND bv2
       TARGET := TARGET OR (BV1 AND BV2)
 
       \param bv1 - Argument vector 1
       \param bv2 - Argument vector 2
       \param opt_mode - optimization compression
         (when it is performed on the fly it is faster than a separate
         call to optimize()
       @sa optimize, bit_and
    */
    bm::bvector<Alloc>& bit_or_and(const bm::bvector<Alloc>& bv1,
                                   const bm::bvector<Alloc>& bv2,
                                typename bm::bvector<Alloc>::optmode opt_mode=opt_none);
 
    
    /*!
       \brief 3-operand SUB : this := bv1 MINUS bv2
       SUBtraction is also known as AND NOT
       \param bv1 - Argument vector 1
       \param bv2 - Argument vector 2
       \param opt_mode - optimization compression
         (when it is performed on the fly it is faster than a separate
         call to optimize()
       @sa optimize, bit_sub
    */
    bm::bvector<Alloc>& bit_sub(const bm::bvector<Alloc>& bv1,
                                const bm::bvector<Alloc>& bv2,
                                typename bm::bvector<Alloc>::optmode opt_mode=opt_none);
 
 
    /*!
       \brief 2 operand logical OR
       \param bv - Argument vector.
    */
    bm::bvector<Alloc>& bit_or(const  bm::bvector<Alloc>& bv)
    {
        BM_ASSERT(!is_ro());
        combine_operation_or(bv);
        return *this;
    }
 
    /*!
       \brief 2 operand logical AND
       \param bv - argument vector
       \param opt_mode - set an immediate optimization
    */
    bm::bvector<Alloc>& bit_and(const bm::bvector<Alloc>& bv,
                                optmode opt_mode = opt_none)
    {
        BM_ASSERT(!is_ro());
        combine_operation_and(bv, opt_mode);
        return *this;
    }
 
    /*!
       \brief 2 operand logical XOR
       \param bv - argument vector.
    */
    bm::bvector<Alloc>& bit_xor(const bm::bvector<Alloc>& bv)
    {
        BM_ASSERT(!is_ro());
        combine_operation_xor(bv);
        return *this;
    }
 
    /*!
       \brief 2 operand logical SUB(AND NOT). Also known as MINUS.
       \param bv - argument vector.
    */
    bm::bvector<Alloc>& bit_sub(const bm::bvector<Alloc>& bv)
    {
        BM_ASSERT(!is_ro());
        combine_operation_sub(bv);
        return *this;
    }
    
    /*!
        \brief Invert/NEG all bits
        It should be noted, invert is affected by size()
        if size is set - it only inverts [0..size-1] bits
    */
    bvector<Alloc>& invert();
    
    
    /*! \brief perform a set-algebra operation by operation code
    */
    void combine_operation(const bm::bvector<Alloc>& bvect,
                            bm::operation            opcode);
 
    /*! \brief perform a set-algebra operation OR
    */
    void combine_operation_or(const bm::bvector<Alloc>& bvect);
 
    /*! \brief perform a set-algebra operation AND
    */
    void combine_operation_and(const bm::bvector<Alloc>& bvect,
                               optmode opt_mode);
 
    /*! \brief perform a set-algebra operation MINUS (AND NOT)
    */
    void combine_operation_sub(const bm::bvector<Alloc>& bvect);
 
    /*! \brief perform a set-algebra operation XOR
    */
    void combine_operation_xor(const bm::bvector<Alloc>& bvect);
 
    // @}
 
    // --------------------------------------------------------------------
    /*! @name Iterator-traversal methods  */
    //@{
 
    /**
       \brief Returns enumerator pointing on the first non-zero bit.
    */
    enumerator first() const { return get_enumerator(0); }
 
    /**
       \fn bvector::enumerator bvector::end() const
       \brief Returns enumerator pointing on the next bit after the last.
    */
    enumerator end() const
                    { return typename bvector<Alloc>::enumerator(this); }
    
    /**
       \brief Returns enumerator pointing on specified or the next available bit.
    */
    enumerator get_enumerator(size_type pos) const
                {  return typename bvector<Alloc>::enumerator(this, pos); }
    
    //@}
 
    // --------------------------------------------------------------------
    /*! @name Memory management and compression  */
    
    //@{
    
    /*!
       @brief Calculates bitvector statistics.
 
       @param st - pointer on statistics structure to be filled in.
 
       Function fills statistics structure containing information about how
       this vector uses memory and estimation of max. amount of memory
       bvector needs to serialize itself.
 
       @sa statistics
    */
    void calc_stat(struct bm::bvector<Alloc>::statistics* st) const BMNOEXCEPT;
 
 
    /*!
       \brief Sets new blocks allocation strategy.
       \param strat - Strategy code 0 - bitblocks allocation only.
                      1 - Blocks mutation mode (adaptive algorithm)
    */
    void set_new_blocks_strat(strategy strat) { new_blocks_strat_ = strat; }
 
    /*!
       \brief Returns blocks allocation strategy.
       \return - Strategy code 0 - bitblocks allocation only.
                 1 - Blocks mutation mode (adaptive algorithm)
       \sa set_new_blocks_strat
    */
    strategy  get_new_blocks_strat() const BMNOEXCEPT 
                             { return new_blocks_strat_; }
 
    /*!
       \brief Optimize memory bitvector's memory allocation.
   
       Function analyze all blocks in the bitvector, compresses blocks 
       with a regular structure, frees some memory. This function is recommended
       after a bulk modification of the bitvector using set_bit, clear_bit or
       logical operations.
 
       Optionally function can calculate vector post optimization statistics
 
       @param temp_block - externally allocated temp buffer for optimization
            BM_DECLARE_TEMP_BLOCK(tb)
            if NULL - it will allocated (and de-allocated upon exit)
       @param opt_mode - optimization level
       @param stat - statistics of memory consumption and serialization
         stat can also be computed by calc_stat() but it would require an extra pass
       
       @sa optmode, optimize_gap_size, calc_stat
    */
    void optimize(bm::word_t* temp_block = 0,
                  optmode opt_mode       = opt_compress,
                  statistics* stat       = 0);
 
    /*!
         Run partial vector optimization for the area [left..right] (specified in bit coordinates)
 
         @param left - bit index to optimize from (approximate, rounded up to a nearest block)
         @param right - bit index to optimize to
             Please note that left and right define range in bit coordinates but later rounded to blocks
         @param temp_block - external scratch memory (MUST be pre-allocated)
         @param opt_mode - optimization level
 
         @sa optimize
     */
    void optimize_range(
                  size_type left, size_type right,
                  bm::word_t* temp_block,
                  optmode opt_mode       = opt_compress);
 
    /*!
       \brief Optimize sizes of GAP blocks
 
       This method runs an analysis to find optimal GAP levels for the 
       specific vector. Current GAP compression algorithm uses several fixed
       GAP sizes. By default bvector uses some reasonable preset. 
    */
    void optimize_gap_size();
 
    /*!
        @brief Sets new GAP lengths table. All GAP blocks will be reallocated 
        to match the new scheme.
 
        @param glevel_len - pointer on C-style array keeping GAP block sizes. 
    */
    void set_gap_levels(const gap_word_t* glevel_len);
 
    /**
        Return true if bvector is initialized at all
        @internal
    */
    bool is_init() const BMNOEXCEPT { return blockman_.is_init(); }
 
    /**
        Calculate blocks digest vector (for diagnostics purposes)
        1 is added if NB is a real, allocated block
 
        @param bv_blocks - [out] bvector of blocks statistics
        @internal
     */
    void fill_alloc_digest(bvector<Alloc>& bv_blocks) const;
    
    //@}
    
    // --------------------------------------------------------------------
    
    /*! @name Comparison  */
    //@{
 
    /*!
        \brief Lexicographical comparison with a bitvector.
 
        Function compares current bitvector with the provided argument 
        bit by bit and returns -1 if this bitvector less than the argument,
        1 - greater, 0 - equal
 
        @return 0 if this == arg, -1 if this < arg, 1 if this > arg
        @sa find_first_mismatch
    */
    int compare(const bvector<Alloc>& bvect) const BMNOEXCEPT;
 
    /*!
        \brief Equal comparison with an agr bit-vector
        @return true if vectors are identical
    */
    bool equal(const bvector<Alloc>& bvect) const BMNOEXCEPT
    {
        size_type pos;
        bool found = find_first_mismatch(bvect, pos);
        return !found;
    }
 
    /*!
        \brief Find index of first bit different between this and the agr vector
 
        @param bvect - argumnet vector to compare with
        @param pos - [out] position of the first difference
        @param search_to - search limiter [0..to] to avoid overscan
                           (default: unlimited to the vectors end)
 
        @return true if didfference found, false - both vectors are equivalent
        @sa compare
    */
    bool find_first_mismatch(const bvector<Alloc>& bvect,
                                        size_type& pos,
                                        size_type  search_to = bm::id_max
                                        ) const BMNOEXCEPT;
    
    //@}
 
    // --------------------------------------------------------------------
    /*! @name Open internals   */
    //@{
    
    /*!
    @internal
    */
    void combine_operation_with_block(block_idx_type nb,
                                      const bm::word_t* arg_blk,
                                      bool arg_gap,
                                      bm::operation opcode);
    /**
        \brief get access to memory manager (internal)
        Use only if you are BitMagic library
        @internal
    */
    const blocks_manager_type& get_blocks_manager() const BMNOEXCEPT 
                                            { return blockman_; }
    
    /**
        \brief get access to memory manager (internal)
        Use only if you are BitMagic library
        @internal
    */
    blocks_manager_type& get_blocks_manager() BMNOEXCEPT 
                                    { return blockman_; }
 
    /**
        Import integers (set bits). (Fast, no checks).
        @internal
    */
    void import(const size_type* ids, size_type ids_size,
                bm::sort_order sorted_idx);
 
    /**
        Import sorted integers (set bits). (Fast, no checks).
        @internal
    */
    void import_sorted(const size_type* ids,
                       const size_type ids_size, bool opt_flag);
 
    /**
       \brief Set range without validity/bounds checking
    */
    void set_range_no_check(size_type left,
                            size_type right);
    /**
        \brief Clear range without validity/bounds checking
    */
    void clear_range_no_check(size_type left,
                              size_type right);
 
 
    //@}
    
    static void throw_bad_alloc();
    
protected:
    /**
        Syncronize size if it got extended due to bulk import
        @internal
    */
    void sync_size();
 
 
    void import_block(const size_type* ids,
                      block_idx_type nblock, size_type start, size_type stop);
 
 
 
    size_type check_or_next(size_type prev) const BMNOEXCEPT;
    
    /// set bit in GAP block with GAP block length control
    bool gap_block_set(bm::gap_word_t* gap_blk,
                       bool val, block_idx_type nblock, unsigned nbit);
 
    /// set bit in GAP block with GAP block length control
    void gap_block_set_no_ret(bm::gap_word_t* gap_blk,
                              bool val, block_idx_type nblock,
                              unsigned nbit);
 
    /// check if specified bit is 1, and set it to 0
    /// if specified bit is 0, scan for the next 1 and returns it
    /// if no 1 found returns 0
    size_type check_or_next_extract(size_type prev);
 
 
    /**
        \brief AND specified bit without checking preconditions (size, etc)
    */
    bool and_bit_no_check(size_type n, bool val);
 
    bool set_bit_conditional_impl(size_type n, bool val, bool condition);
 
 
    void combine_operation_with_block(block_idx_type nb,
                                      bool gap,
                                      bm::word_t* blk,
                                      const bm::word_t* arg_blk,
                                      bool arg_gap,
                                      bm::operation opcode);
 
    /**
        @return true if block optimization may be needed
    */
    bool combine_operation_block_or(unsigned i,
                                    unsigned j,
                                    const bm::word_t* arg_blk1,
                                    const bm::word_t* arg_blk2);
    bool combine_operation_block_xor(unsigned i,
                                     unsigned j,
                                     const bm::word_t* arg_blk1,
                                     const bm::word_t* arg_blk2);
    bool combine_operation_block_and(unsigned i,
                                     unsigned j,
                                     const bm::word_t* arg_blk1,
                                     const bm::word_t* arg_blk2);
 
    bool combine_operation_block_and_or(unsigned i,
                                        unsigned j,
                                        const bm::word_t* arg_blk1,
                                        const bm::word_t* arg_blk2);
    bool combine_operation_block_sub(unsigned i,
                                     unsigned j,
                                     const bm::word_t* arg_blk1,
                                     const bm::word_t* arg_blk2);
 
 
    void combine_operation_block_or(unsigned i,
                                    unsigned j,
                                    bm::word_t* blk,
                                    const bm::word_t* arg_blk);
    
    void combine_operation_block_xor(unsigned i,
                                     unsigned j,
                                     bm::word_t* blk,
                                     const bm::word_t* arg_blk);
 
    void combine_operation_block_and(unsigned i,
                                     unsigned j,
                                     bm::word_t* blk,
                                     const bm::word_t* arg_blk);
 
    void combine_operation_block_sub(unsigned i,
                                     unsigned j,
                                     bm::word_t* blk,
                                     const bm::word_t* arg_blk);
    
    void copy_range_no_check(const bvector<Alloc>& bvect,
                             size_type left,
                             size_type right);
 
private:
    /**
        \brief Clear outside the range without validity/bounds checking
    */
    void keep_range_no_check(size_type left,
                             size_type right);
 
    /**
        Compute rank in bit-block using rank-select index
    */
    static
    size_type block_count_to(const bm::word_t* block,
                            block_idx_type nb,
                            unsigned nbit_right,
                            const rs_index_type&  rs_idx) BMNOEXCEPT;
    /**
        Compute rank in GAP block using rank-select index
        @param test_set - request to test nbit_right before computing count
             (returns 0 if not set)
    */
    static
    size_type gap_count_to(const bm::gap_word_t* gap_block,
                            block_idx_type nb,
                            unsigned nbit_right,
                            const rs_index_type&  rs_idx,
                            bool  test_set = false) BMNOEXCEPT;
    /**
        Return value of first bit in the block
    */
    bool test_first_block_bit(block_idx_type nb) const BMNOEXCEPT;
    
private:
    blocks_manager_type  blockman_;         //!< bitblocks manager
    strategy             new_blocks_strat_; //!< block allocation strategy
    size_type            size_;             //!< size in bits
};
 
 
//---------------------------------------------------------------------
 
template<class Alloc> 
inline bvector<Alloc> operator& (const bvector<Alloc>& bv1,
                                 const bvector<Alloc>& bv2)
{
    bvector<Alloc> ret;
    ret.bit_and(bv1, bv2, bvector<Alloc>::opt_none);
    return ret;
}
 
//---------------------------------------------------------------------
 
template<class Alloc> 
inline bvector<Alloc> operator| (const bvector<Alloc>& bv1,
                                 const bvector<Alloc>& bv2)
{
    bvector<Alloc> ret;
    ret.bit_or(bv1, bv2, bvector<Alloc>::opt_none);
    return ret;
}
 
//---------------------------------------------------------------------
 
template<class Alloc> 
inline bvector<Alloc> operator^ (const bvector<Alloc>& bv1,
                                 const bvector<Alloc>& bv2)
{
    bvector<Alloc> ret;
    ret.bit_xor(bv1, bv2, bvector<Alloc>::opt_none);
    return ret;
}
 
//---------------------------------------------------------------------
 
template<class Alloc> 
inline bvector<Alloc> operator- (const bvector<Alloc>& bv1,
                                 const bvector<Alloc>& bv2)
{
    bvector<Alloc> ret;
    ret.bit_sub(bv1, bv2, bvector<Alloc>::opt_none);
    return ret;
}
 
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
void bvector<Alloc>::init()
{
    BM_ASSERT(!is_ro());
    blockman_.init_tree();
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
void bvector<Alloc>::init(unsigned top_size, bool alloc_subs)
{
    BM_ASSERT(!is_ro());
    if (!blockman_.is_init())
        blockman_.init_tree(top_size);
    if (alloc_subs)
        for (unsigned nb = 0; nb < top_size; ++nb)
            blockman_.alloc_top_subblock(nb);
}
 
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
void bvector<Alloc>::copy(const bvector<Alloc>& bvect, bm::finalization is_final)
{
    if (this != &bvect)
    {
        blockman_.deinit_tree();
        switch (is_final)
        {
        case bm::finalization::UNDEFINED:
            if (bvect.is_ro())
            {
                blockman_.copy_to_arena(bvect.blockman_);
                size_ = bvect.size();
            }
            else
            {
                blockman_.copy(bvect.blockman_);
                resize(bvect.size());
            }
            break;
        case bm::finalization::READONLY:
            blockman_.copy_to_arena(bvect.blockman_);
            size_ = bvect.size();
            break;
        case bm::finalization::READWRITE:
            blockman_.copy(bvect.blockman_);
            resize(bvect.size());
            break;
        default:
            BM_ASSERT(0);
            break;
        } // switch
    }
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
void bvector<Alloc>::move_from(bvector<Alloc>& bvect) BMNOEXCEPT
{
    if (this != &bvect)
    {
        blockman_.move_from(bvect.blockman_);
        size_ = bvect.size_;
        new_blocks_strat_ = bvect.new_blocks_strat_;
    }
}
 
//---------------------------------------------------------------------
 
template<class Alloc>
void bvector<Alloc>::keep_range(size_type left, size_type right)
{
    BM_ASSERT(!is_ro());
    if (!blockman_.is_init())
        return; // nothing to do
 
    if (right < left)
        bm::xor_swap(left, right);
 
    keep_range_no_check(left, right);
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc> 
bvector<Alloc>& bvector<Alloc>::set_range(size_type left,
                                          size_type right,
                                          bool     value)
{
    BM_ASSERT(!is_ro());
 
    if (!blockman_.is_init() && !value)
        return *this; // nothing to do
 
    if (right < left)
        return set_range(right, left, value);
 
    BM_ASSERT_THROW(right < bm::id_max, BM_ERR_RANGE);
    if (right >= size_) // this vect shorter than the arg.
    {
        size_type new_size = (right == bm::id_max) ? bm::id_max : right + 1;
        resize(new_size);
    }
 
    BM_ASSERT(left <= right);
    BM_ASSERT(left < size_);
 
    if (value)
        set_range_no_check(left, right);
    else
        clear_range_no_check(left, right);
 
    return *this;
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc> 
typename bvector<Alloc>::size_type bvector<Alloc>::count() const BMNOEXCEPT
{
    if (!blockman_.is_init())
        return 0;
    
    word_t*** blk_root = blockman_.top_blocks_root();
    BM_ASSERT(blk_root);
    
    size_type cnt = 0;
    unsigned top_blocks = blockman_.top_block_size();
    for (unsigned i = 0; i < top_blocks; ++i)
    {
        bm::word_t** blk_blk = blk_root[i];
        if (!blk_blk)
        {
            ++i;
            bool found = bm::find_not_null_ptr(blk_root, i, top_blocks, &i);
            if (!found)
                break;
            blk_blk = blk_root[i];
            BM_ASSERT(blk_blk);
            if (!blk_blk)
                break;
        }
        if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
        {
            cnt += bm::gap_max_bits * bm::set_sub_array_size;
            continue;
        }
        unsigned j = 0;
        do
        {
            if (blk_blk[j])
                cnt += blockman_.block_bitcount(blk_blk[j]);
            if (blk_blk[j+1])
                cnt += blockman_.block_bitcount(blk_blk[j+1]);
            if (blk_blk[j+2])
                cnt += blockman_.block_bitcount(blk_blk[j+2]);
            if (blk_blk[j+3])
                cnt += blockman_.block_bitcount(blk_blk[j+3]);
            j += 4;
        } while (j < bm::set_sub_array_size);
 
    } // for i
    return cnt;
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
bool bvector<Alloc>::any() const BMNOEXCEPT
{
    word_t*** blk_root = blockman_.top_blocks_root();
    if (!blk_root)
        return false;
    typename blocks_manager_type::block_any_func func(blockman_);
    return for_each_nzblock_if(blk_root, blockman_.top_block_size(), func);
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc> 
void bvector<Alloc>::resize(size_type new_size)
{
    BM_ASSERT(!is_ro());
 
    if (size_ == new_size) return; // nothing to do
    if (size_ < new_size) // size grows 
    {
        if (!blockman_.is_init())
            blockman_.init_tree();
    
        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>
void bvector<Alloc>::sync_size()
{
    BM_ASSERT(!is_ro());
 
    if (size_ >= bm::id_max)
        return;
    bvector<Alloc>::size_type last;
    bool found = find_reverse(last);
    if (found && last >= size_)
        resize(last+1);
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
void bvector<Alloc>::build_rs_index(rs_index_type* rs_idx,
                                    bvector<Alloc>* bv_blocks) const
{
    BM_ASSERT(rs_idx);
    if (bv_blocks)
    {
        bv_blocks->clear();
        bv_blocks->init();
    }
    
    unsigned bcount[bm::set_sub_array_size];
    bm::id64_t sub_count[bm::set_sub_array_size];
 
    rs_idx->init();
    if (!blockman_.is_init())
        return;
    
    // resize the RS index to fit the vector
    //
    size_type last_bit;
    bool found = find_reverse(last_bit);
    if (!found)
        return;
    block_idx_type nb = (last_bit >> bm::set_block_shift);
    unsigned i0, j0;
    bm::get_block_coord(nb, i0, j0);
 
    unsigned real_top_blocks = blockman_.find_real_top_blocks();
    unsigned max_top_blocks = blockman_.find_max_top_blocks();
    if (nb < (max_top_blocks * bm::set_sub_array_size))
        nb = (max_top_blocks * bm::set_sub_array_size);
    rs_idx->set_total(nb + 1);
    rs_idx->resize(nb + 1);
    rs_idx->resize_effective_super_blocks(real_top_blocks);
 
    // index construction
    //
    BM_ASSERT(max_top_blocks <= blockman_.top_block_size());
    bm::word_t*** blk_root = blockman_.top_blocks_root();
    for (unsigned i = 0; i < max_top_blocks; ++i)
    {
        bm::word_t** blk_blk = blk_root[i];
        if (!blk_blk)
        {
            rs_idx->set_null_super_block(i);
            continue;
        }
        if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
        {
            rs_idx->set_full_super_block(i);
            if (bv_blocks)
            {
                size_type nb_from = i * bm::set_sub_array_size;
                size_type nb_to = nb_from + bm::set_sub_array_size - 1;
                bv_blocks->set_range_no_check(nb_from, nb_to);
            }
            continue;
        }
        
        unsigned j = 0;
        do
        {
            const bm::word_t* block = blk_blk[j];
            if (!block)
            {
                bcount[j] = 0; sub_count[j] = 0;
                continue;
            }
            unsigned local_first, local_second, local_third;
            bm::id64_t aux0, aux1; // aux infomation to encode
            if (BM_IS_GAP(block))
            {
                const bm::gap_word_t* const gap_block = BMGAP_PTR(block);
                local_first =
                    bm::gap_bit_count_to(gap_block, (gap_word_t)bm::rs3_border0);
                local_second =
                    bm::gap_bit_count_range(gap_block,
                                            bm::gap_word_t(bm::rs3_border0+1),
                                            bm::rs3_border1);
                local_third =
                    bm::gap_bit_count_range(gap_block,
                                            bm::gap_word_t(bm::rs3_border1+1),
                                            bm::gap_word_t(bm::gap_max_bits-1));
 
                // for GAP block calculate borderline positions in GAP
                // and value (0|1), save to AUX
                //
                unsigned is_set;
                aux0 = bm::gap_bfind(gap_block, rs3_border0+1, &is_set);
                aux0 <<= 1;
                if (is_set) aux0 |= 1;
                aux1 = bm::gap_bfind(gap_block, rs3_border1+1, &is_set);
                aux1 <<= 1;
                if (is_set) aux1 |= 1;
            }
            else
            {
                block = BLOCK_ADDR_SAN(block); // TODO: optimize FULL
                local_first =
                    bm::bit_block_calc_count_to(block, bm::rs3_border0);
                local_second =
                    bm::bit_block_calc_count_range(block,
                                                   bm::rs3_border0+1,
                                                   bm::rs3_border1);
                local_third =
                    bm::bit_block_calc_count_range(block,
                                                   bm::rs3_border1+1,
                                                   bm::gap_max_bits-1);
                // compute inetrmediate points
                aux0 = bm::bit_block_calc_count_to(block, bm::rs3_border0_1);
                aux1 = bm::bit_block_calc_count_to(block, bm::rs3_border1_1);
            }
            unsigned cnt = local_first + local_second + local_third;
            BM_ASSERT(cnt == blockman_.block_bitcount(block));
 
            bcount[j] = cnt;
            if (bv_blocks && cnt)
                bv_blocks->set_bit_no_check(i * bm::set_sub_array_size + j);
 
            BM_ASSERT(cnt >= local_first + local_second);
            sub_count[j] = bm::id64_t(local_first | (local_second << 16)) |
                                      (aux0 << 32) | (aux1 << 48);
 
        } while (++j < bm::set_sub_array_size);
        
        rs_idx->register_super_block(i, &bcount[0], &sub_count[0]);
        
    } // for i
 
}
 
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
typename bvector<Alloc>::block_idx_type
bvector<Alloc>::count_blocks(unsigned* arr) const BMNOEXCEPT
{
    bm::word_t*** blk_root = blockman_.top_blocks_root();
    if (blk_root == 0)
        return 0;
    typename blocks_manager_type::block_count_arr_func func(blockman_, &(arr[0]));
    bm::for_each_nzblock(blk_root, blockman_.top_block_size(), func);
    return func.last_block();
}
 
// -----------------------------------------------------------------------
 
#define BM_BORDER_TEST(blk, idx) bool(blk[idx >> bm::set_word_shift] & (1u << (idx & bm::set_word_mask)))
 
 
#if (defined(BMSSE42OPT) || defined(BMAVX2OPT) || defined(BMAVX512OPT) || \
    defined(BMWASMSIMDOPT) || defined(BMNEONOPT))
 
 
template<typename Alloc>
typename bvector<Alloc>::size_type
bvector<Alloc>::block_count_to(const bm::word_t*    block,
                               block_idx_type       nb,
                               unsigned             nbit_right,
                               const rs_index_type& rs_idx) BMNOEXCEPT
{
    BM_ASSERT(IS_VALID_ADDR(block));
    size_type c;
 
    bm::id64_t sub = rs_idx.sub_count(nb);
    unsigned sub_cnt = unsigned(sub);
    unsigned first = sub_cnt & 0xFFFF;
    unsigned second = sub_cnt >> 16;
    
    BM_ASSERT(first == bm::bit_block_calc_count_to(block, rs3_border0));
    BM_ASSERT(second == bm::bit_block_calc_count_range(block, rs3_border0+1, rs3_border1));
 
 
    {
        unsigned cnt, aux0(bm::gap_word_t(sub >> 32)); (void)cnt; (void)aux0;
        BM_ASSERT(aux0 == (cnt =bm::bit_block_calc_count_to(block, bm::rs3_border0_1)));
        unsigned cnt1, aux1(bm::gap_word_t(sub >> 48)); (void)aux1; (void) cnt1;
        BM_ASSERT(aux1 == (cnt1 =bm::bit_block_calc_count_to(block, bm::rs3_border1_1)));
    }
 
 
    #if defined(BM64_SSE4) || defined(BM64_AVX2) || defined(BM64_AVX512)
    const unsigned cutoff_bias = rs3_half_span/8;
    #else
    const unsigned cutoff_bias = 0;
    #endif
 
    unsigned sub_range = rs_idx.find_sub_range(nbit_right);
 
    // evaluate 3 sub-block intervals (and sub-intervals)
    // |--------[0]-----*-----[1]----*-----|
    switch(sub_range)  // sub-range rank calc
    {
    case 0:
        // |--x-----[0]-----------[1]----------|
        if (nbit_right <= rs3_border0/2 + cutoff_bias)
        {
            c = bm::bit_block_calc_count_range<true, false>(block, 0, nbit_right);
        }
        else
        {
            // |--------[x]-----------[1]----------|
            if (nbit_right == rs3_border0)
            {
                c = first;
            }
            else
            {
                // |------x-[0]-----------[1]----------|
                c = bm::bit_block_calc_count_range(block, nbit_right+1,
                                                   rs3_border0);
                c = first - c;
            }
        }
    break;
    case 1:
    {
        // |--------[0]-x---------[1]----------|
        if (nbit_right <= rs3_border0_1 + cutoff_bias)
        {
            c =
            bm::bit_block_calc_count_range<true, false>(block,
                                                        bm::rs3_border0,
                                                        nbit_right);
            c += first - BM_BORDER_TEST(block, bm::rs3_border0);
        }
        else
        {
            unsigned bc_second_range = first + second;
            // |--------[0]-----------[x]----------|
            if (nbit_right == rs3_border1)
            {
                c = bc_second_range;
            }
            else  // sub-range processing
            {
                // |--------[0]--------x--[1]----------|
                BM_ASSERT(nbit_right > bm::rs3_border0_1);
                unsigned d1 = nbit_right - bm::rs3_border0_1;
                unsigned d2 = rs3_border1 - nbit_right;
                if (d2 < d1)
                {
                    // |--------[0]----|----x-[1]----------|
                    c = bm::bit_block_calc_count_range(block,
                                                       nbit_right+1,
                                                       rs3_border1);
                    c = bc_second_range - c;
                }
                else
                {
                    // |--------[0]----|-x----[1]----------|
                    c = bm::bit_block_calc_count_range<true, false>(
                                                       block,
                                                       bm::rs3_border0_1,
                                                       nbit_right);
                    unsigned aux0 = bm::gap_word_t(sub >> 32);
                    c += aux0;
                    c -= BM_BORDER_TEST(block, bm::rs3_border0_1);
                }
            }
        }
    }
    break;
    case 2:
    {
        // |--------[0]-----------[1]-x---*----|
        if (nbit_right <= rs3_border1_1)
        {
            unsigned d1 = nbit_right - bm::rs3_border1;
            unsigned d2 = (rs3_border1_1 + cutoff_bias) - nbit_right;
            if (d1 < d2) // |--------[0]-----------[1]-x---*----|
            {
                c = bm::bit_block_calc_count_range<true, false>(block,
                                                       bm::rs3_border1,
                                                       nbit_right);
                c += first + second; //bc_second_range;
                c -= BM_BORDER_TEST(block, bm::rs3_border1);
            }
            else // |--------[0]-----------[1]---x-*----|
            {
                if (nbit_right == rs3_border1_1)
                {
                    unsigned aux1 = bm::gap_word_t(sub >> 48);
                    c = aux1;
                }
                else
                {
                    c = bm::bit_block_calc_count_range(block,
                                                       nbit_right+1,
                                                       rs3_border1_1);
                    unsigned aux1 = bm::gap_word_t(sub >> 48);
                    c = aux1 - c;
                }
            }
        }
        else
        {
            // |--------[0]-----------[1]----------x
            if (nbit_right == bm::gap_max_bits-1)
            {
                c = rs_idx.count(nb);
            }
            else // sub-range processing
            {
                // |--------[0]-----------[1]-------x--|
                BM_ASSERT(nbit_right > bm::rs3_border1_1);
                unsigned d1 = nbit_right - bm::rs3_border1_1;
                unsigned d2 = bm::gap_max_bits - nbit_right;
                if (d2 < d1)
                {
                    // |--------[0]----------[1]----*---x-|
                    c = bm::bit_block_calc_count_range(block,
                                                       nbit_right+1,
                                                       bm::gap_max_bits-1);
                    size_type cnt = rs_idx.count(nb);
                    c = cnt - c;
                }
                else
                {
                    // |--------[0]----------[1]----*-x---|
                    c = bm::bit_block_calc_count_range<true, false>(block,
                                                           bm::rs3_border1_1,
                                                           nbit_right);
                    unsigned aux1 = bm::gap_word_t(sub >> 48);
                    c += aux1;
                    c -= BM_BORDER_TEST(block, bm::rs3_border1_1);
                }
            }
        }
    }
    break;
    default:
        BM_ASSERT(0);
        c = 0;
    } // switch
    
    BM_ASSERT(c == bm::bit_block_calc_count_to(block, nbit_right));
    return c;
}
 
#else // non-SIMD version
 
template<typename Alloc>
typename bvector<Alloc>::size_type
bvector<Alloc>::block_count_to(const bm::word_t*    block,
                               block_idx_type       nb,
                               unsigned             nbit_right,
                               const rs_index_type& rs_idx) BMNOEXCEPT
{
    BM_ASSERT(block);
 
    bm::id64_t sub = rs_idx.sub_count(nb);
    unsigned sub_cnt = unsigned(sub);
    unsigned first = sub_cnt & 0xFFFF;
    unsigned second = sub_cnt >> 16;
 
    BM_ASSERT(first == bm::bit_block_calc_count_to(block, rs3_border0));
    BM_ASSERT(second == bm::bit_block_calc_count_range(block, rs3_border0+1, rs3_border1));
 
 
    {
        unsigned cnt, aux0(bm::gap_word_t(sub >> 32)); (void)cnt; (void)aux0;
        BM_ASSERT(aux0 == (cnt =bm::bit_block_calc_count_to(block, bm::rs3_border0_1)));
        unsigned cnt1, aux1(bm::gap_word_t(sub >> 48)); (void)aux1; (void) cnt1;
        BM_ASSERT(aux1 == (cnt1 =bm::bit_block_calc_count_to(block, bm::rs3_border1_1)));
    }
 
    size_type c=0;
    unsigned sub_choice =
        bm::get_nibble(bm::rs_intervals<true>::_c._lut, nbit_right);
 
    switch(sub_choice)
    {
    case 0:
        c = bm::bit_block_calc_count_range<true, false>(block, 0, nbit_right);
        break;
    case 1:
        c = first;
        break;
    case 2:
        c = bm::bit_block_calc_count_range(block, nbit_right+1, rs3_border0);
        c = first - c;
        break;
    case 3:
        c = bm::bit_block_calc_count_range<true, false>(block,
                                                        bm::rs3_border0,
                                                        nbit_right);
        c += first - BM_BORDER_TEST(block, bm::rs3_border0);
        break;
    case 4:
        c = first + second;
        break;
    case 5:
        c = bm::bit_block_calc_count_range(block, nbit_right+1, rs3_border1);
        c = first + second - c;
        break;
    case 6:
        c = bm::bit_block_calc_count_range<true, false>(
                                           block,
                                           bm::rs3_border0_1,
                                           nbit_right);
        c += bm::gap_word_t(sub >> 32); // aux0
        c -= BM_BORDER_TEST(block, bm::rs3_border0_1);
        break;
    case 7:
        c = bm::bit_block_calc_count_range<true, false>(block,
                                               bm::rs3_border1,
                                               nbit_right);
        c += first + second; //bc_second_range;
        c -= BM_BORDER_TEST(block, bm::rs3_border1);
        break;
    case 8:
        c = bm::gap_word_t(sub >> 48); // aux1;
        break;
    case 9:
        c = bm::bit_block_calc_count_range(block,
                                           nbit_right+1,
                                           rs3_border1_1);
        c = bm::gap_word_t(sub >> 48) - c; // aux1 - c
        break;
    case 10:
        c = rs_idx.count(nb);
        break;
    case 11:
        c = bm::bit_block_calc_count_range(block,
                                           nbit_right+1,
                                           bm::gap_max_bits-1);
        c = rs_idx.count(nb) - c;
        break;
    case 12:
        c = bm::bit_block_calc_count_range<true, false>(block,
                                               bm::rs3_border1_1,
                                               nbit_right);
        c += bm::gap_word_t(sub >> 48); // aux1;
        c -= BM_BORDER_TEST(block, bm::rs3_border1_1);
        break;
    default:
        BM_ASSERT(0);
    } // switch
    BM_ASSERT(c == bm::bit_block_calc_count_to(block, nbit_right));
    return c;
}
#endif
 
#undef BM_BORDER_TEST
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
typename bvector<Alloc>::size_type
bvector<Alloc>::gap_count_to(const bm::gap_word_t* gap_block,
                             block_idx_type nb,
                             unsigned nbit_right,
                             const rs_index_type&  rs_idx,
                             bool test_set) BMNOEXCEPT
{
    BM_ASSERT(gap_block);
    size_type c;
 
 
    if (test_set)
    {
        bool is_set = bm::gap_test_unr(gap_block, (gap_word_t)nbit_right);
        if (!is_set)
            return 0;
    }
/*
    {
        unsigned len = bm::gap_length(gap_block);
        if (len < 64)
        {
            c = bm::gap_bit_count_to(gap_block, (gap_word_t)nbit_right);
            return c;
        }
    }
*/
    bm::id64_t sub = rs_idx.sub_count(nb);
    if (!sub)
    {
        c = 0;
        BM_ASSERT(c == bm::gap_bit_count_to(gap_block, (gap_word_t)nbit_right));
        return c;
    }
 
    unsigned sub_cnt = unsigned(sub);
    unsigned first =  bm::gap_word_t(sub_cnt);
    unsigned second = (sub_cnt >> 16);
 
 
    BM_ASSERT(first == bm::gap_bit_count_to(gap_block,(gap_word_t)rs3_border0));
    BM_ASSERT(second == bm::gap_bit_count_range(gap_block, rs3_border0+1, rs3_border1));
 
    // evaluate 3 sub-block intervals
    // |--------[0]-----------[1]----------|
    const unsigned cutoff_bias = rs3_half_span/8;
    unsigned sub_range = rs_idx.find_sub_range(nbit_right);
    switch(sub_range)  // sub-range rank calc
    {
    case 0:
        // |--x-----[0]-----------[1]----------|
        if (nbit_right <= (rs3_border0/2 + cutoff_bias))
        {
            c = bm::gap_bit_count_to(gap_block,(gap_word_t)nbit_right);
        }
        else
        {
            // |--------[x]-----------[1]----------|
            if (nbit_right == rs3_border0)
            {
                c = first;
            }
            else
            {
                // |------x-[0]-----------[1]----------|
                c =
                  bm::gap_bit_count_range(gap_block, nbit_right+1, rs3_border0);
                c = first - c;
            }
        }
    break;
    case 1:
        // |--------[0]-x---------[1]----------|
        if (nbit_right <= (rs3_border0 + rs3_half_span + cutoff_bias))
        {
            unsigned aux0 = bm::gap_word_t(sub >> 32);
            c = bm::gap_bit_count_range_hint(gap_block,
                                             rs3_border0+1, nbit_right, aux0);
            c += first;
        }
        else
        {
            // |--------[0]-----------[x]----------|
            if (nbit_right == rs3_border1)
            {
                c = first + second;
            }
            else
            {
                // |--------[0]--------x--[1]----------|
                c =
                bm::gap_bit_count_range(gap_block, nbit_right+1, rs3_border1);
                c = first + second - c;
            }
        }
    break;
    case 2:
    {
        // |--------[0]-----------[1]-x--------|
        if (nbit_right <= (rs3_border1 + rs3_half_span + cutoff_bias))
        {
            unsigned aux1 = bm::gap_word_t(sub >> 48);
            c = bm::gap_bit_count_range_hint(gap_block,
                                            rs3_border1 + 1, nbit_right, aux1);
            c += first + second; // += bc_second_range
        }
        else
        {
            // |--------[0]-----------[1]----------x
            if (nbit_right == bm::gap_max_bits-1)
            {
                c = rs_idx.count(nb);
            }
            else
            {
                // |--------[0]-----------[1]-------x--|
                c = bm::gap_bit_count_range<bm::gap_word_t, true> (gap_block,
                                            nbit_right+1, bm::gap_max_bits-1);
                size_type cnt = rs_idx.count(nb);
                c = cnt - c;
            }
        }
    }
    break;
    default:
        BM_ASSERT(0);
        c = 0;
    } // switch
 
    BM_ASSERT(c == bm::gap_bit_count_to(gap_block, (gap_word_t)nbit_right));
    return c;
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
typename bvector<Alloc>::size_type 
bvector<Alloc>::count_to(size_type right,
                         const rs_index_type&  rs_idx) const BMNOEXCEPT
{
    BM_ASSERT(right < bm::id_max);
    if (!blockman_.is_init())
        return 0;
 
    unsigned nb_right = unsigned(right >>  bm::set_block_shift);
 
    // running count of all blocks before target
    //
    size_type cnt;
    if (nb_right >= rs_idx.get_total())
    {
        cnt = rs_idx.count();
        return cnt;
    }
    cnt = nb_right ? rs_idx.rcount(nb_right-1) : 0;
 
    unsigned i, j;
    bm::get_block_coord(nb_right, i, j);
    const bm::word_t* block = blockman_.get_block_ptr(i, j);
 
    if (block)
    {
        size_type c;
        unsigned nbit_right = unsigned(right & bm::set_block_mask);
        if (BM_IS_GAP(block))
        {
            const bm::gap_word_t* gap_block = BMGAP_PTR(block);
            c = this->gap_count_to(gap_block, nb_right, nbit_right, rs_idx);
        }
        else
        {
            if (block == FULL_BLOCK_FAKE_ADDR) // TODO: misses REAL full sometimes
            {
                return cnt + nbit_right + 1;
            }
            else // real bit-block
            {
                c = this->block_count_to(block, nb_right, nbit_right, rs_idx);
            }
        }
        cnt += c;
 
    }
    return cnt;
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
typename bvector<Alloc>::size_type 
bvector<Alloc>::count_to_test(size_type right,
                              const rs_index_type&  rs_idx) const BMNOEXCEPT
{
    BM_ASSERT(right < bm::id_max);
    if (!blockman_.is_init())
        return 0;
 
    unsigned nb_right = unsigned(right >> bm::set_block_shift);
 
    unsigned i, j;
    bm::get_block_coord(nb_right, i, j);
    const bm::word_t* block = blockman_.get_block_ptr(i, j);
    if (!block)
        return 0;
 
    unsigned nbit_right = unsigned(right & bm::set_block_mask);
    size_type cnt = nbit_right + 1; // default for FULL BLOCK
    if (BM_IS_GAP(block))
    {
        bm::gap_word_t *gap_blk = BMGAP_PTR(block);
        cnt = gap_count_to(gap_blk, nb_right, nbit_right, rs_idx, true);
        if (!cnt)
            return cnt;
        BM_ASSERT(cnt == bm::gap_bit_count_to(gap_blk, (gap_word_t)nbit_right));
        /*
        if (bm::gap_test_unr(gap_blk, (gap_word_t)nbit_right))
        {
            cnt = gap_count_to(gap_blk, nb_right, nbit_right, rs_idx);
            BM_ASSERT(cnt == bm::gap_bit_count_to(gap_blk, (gap_word_t)nbit_right));
        }
        else
            return 0;
        */
    }
    else
    {
        if (block != FULL_BLOCK_FAKE_ADDR)
        {
            unsigned w = block[nbit_right >> bm::set_word_shift]; // nword
            if (w &= (1u << (nbit_right & bm::set_word_mask)))
            {
                cnt = block_count_to(block, nb_right, nbit_right, rs_idx);
                BM_ASSERT(cnt == bm::bit_block_calc_count_to(block, nbit_right));
            }
            else
                return 0;
        }
    }
    cnt += nb_right ? rs_idx.rcount(nb_right - 1) : 0;
    return cnt;
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
typename bvector<Alloc>::size_type
bvector<Alloc>::rank_corrected(size_type right,
                               const rs_index_type&  rs_idx) const BMNOEXCEPT
{
  BM_ASSERT(right < bm::id_max);
  if (!blockman_.is_init())
      return 0;
 
  unsigned nblock_right = unsigned(right >> bm::set_block_shift);
  unsigned nbit_right = unsigned(right & bm::set_block_mask);
 
  size_type cnt = nblock_right ? rs_idx.rcount(nblock_right - 1) : 0;
 
  unsigned i, j;
  bm::get_block_coord(nblock_right, i, j);
  const bm::word_t* block = blockman_.get_block_ptr(i, j);
 
  if (!block)
      return cnt;
 
  bool gap = BM_IS_GAP(block);
  if (gap)
  {
      cnt += bm::gap_bit_count_to<bm::gap_word_t, true>(
                    BMGAP_PTR(block), (gap_word_t)nbit_right);
  }
  else
  {
      if (block == FULL_BLOCK_FAKE_ADDR)
          cnt += nbit_right;
      else
      {
          cnt += block_count_to(block, nblock_right, nbit_right, rs_idx);
          unsigned w = block[nbit_right >> bm::set_word_shift] &
                       (1u << (nbit_right & bm::set_word_mask));
          cnt -= bool(w); // rank correction
      }
  }
  return cnt;
}
 
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
typename bvector<Alloc>::size_type
bvector<Alloc>::count_range(size_type left, size_type right) const BMNOEXCEPT
{
    BM_ASSERT(left < bm::id_max && right < bm::id_max);
    if (!blockman_.is_init())
        return 0;
    if (left > right)
        bm::xor_swap(left, right);
    if (right == bm::id_max)
        --right;
    return count_range_no_check(left, right);
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
typename bvector<Alloc>::size_type
bvector<Alloc>::count_range_no_check(size_type left, size_type right) const BMNOEXCEPT
{
    size_type cnt = 0;
 
    // calculate logical number of start and destination blocks
    block_idx_type nblock_left  = (left  >>  bm::set_block_shift);
    block_idx_type nblock_right = (right >>  bm::set_block_shift);
 
    unsigned i0, j0;
    bm::get_block_coord(nblock_left, i0, j0);
    const bm::word_t* block = blockman_.get_block(i0, j0);
 
    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
        {
            func(block);
            cnt += func.count();
        }
        else
        {
            if (left_gap)
            {
                cnt += bm::gap_bit_count_range(BMGAP_PTR(block),
                                               (gap_word_t)nbit_left,
                                               (gap_word_t)r);
            }
            else
            {
                cnt += bm::bit_block_calc_count_range(block, nbit_left, r);
            }
        }
    }
 
    if (nblock_left == nblock_right)  // in one block
        return cnt;
 
    // process all full mid-blocks
    {
        func.reset();
        word_t*** blk_root = blockman_.top_blocks_root();
        block_idx_type top_blocks_size = blockman_.top_block_size();
        
        bm::for_each_nzblock_range(blk_root, top_blocks_size,
                                   nblock_left+1, nblock_right-1, func);
        cnt += func.count();
    }
    
    bm::get_block_coord(nblock_right, i0, j0);
    block = blockman_.get_block(i0, j0);
    bool right_gap = BM_IS_GAP(block);
 
    if (block)
    {
        if (right_gap)
        {
            cnt +=
            bm::gap_bit_count_to(BMGAP_PTR(block), (gap_word_t)nbit_right);
        }
        else
        {
            cnt += bm::bit_block_calc_count_range(block, 0, nbit_right);
        }
    }
    return cnt;
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
bool bvector<Alloc>::is_all_one_range(size_type left,
                                      size_type right) const BMNOEXCEPT
{
    if (!blockman_.is_init())
        return false; // nothing to do
 
    if (right < left)
        bm::xor_swap(left, right);
    if (right == bm::id_max)
        --right;
    if (left == right)
        return test(left);
 
    BM_ASSERT(left < bm::id_max && right < bm::id_max);
 
    block_idx_type nblock_left  = (left  >> bm::set_block_shift);
    block_idx_type nblock_right = (right >> bm::set_block_shift);
 
    unsigned i0, j0;
    bm::get_block_coord(nblock_left, i0, j0);
    const bm::word_t* block = blockman_.get_block(i0, j0);
 
    if (nblock_left == nblock_right) // hit in the same block
    {
        unsigned nbit_left  = unsigned(left  & bm::set_block_mask);
        unsigned nbit_right = unsigned(right & bm::set_block_mask);
        return bm::block_is_all_one_range(block, nbit_left, nbit_right);
    }
 
    // process entry point block
    {
        unsigned nbit_left  = unsigned(left  & bm::set_block_mask);
        bool all_one = bm::block_is_all_one_range(block,
                                            nbit_left, (bm::gap_max_bits-1));
        if (!all_one)
            return all_one;
        ++nblock_left;
    }
 
    // process tail block
    {
        bm::get_block_coord(nblock_right, i0, j0);
        block = blockman_.get_block(i0, j0);
        unsigned nbit_right  = unsigned(right  & bm::set_block_mask);
        bool all_one = bm::block_is_all_one_range(block, 0, nbit_right);
        if (!all_one)
            return all_one;
        --nblock_right;
    }
 
    // check all blocks in the middle
    //
    if (nblock_left <= nblock_right)
    {
        unsigned i_from, j_from, i_to, j_to;
        bm::get_block_coord(nblock_left, i_from, j_from);
        bm::get_block_coord(nblock_right, i_to, j_to);
 
        bm::word_t*** blk_root = blockman_.top_blocks_root();
 
        for (unsigned i = i_from; i <= i_to; ++i)
        {
            bm::word_t** blk_blk = blk_root[i];
            if (!blk_blk)
                return false;
            if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
                continue;
 
            unsigned j = (i == i_from) ? j_from : 0;
            unsigned j_limit = (i == i_to) ? j_to+1 : bm::set_sub_array_size;
            do
            {
                bool all_one = bm::check_block_one(blk_blk[j], true);
                if (!all_one)
                    return all_one;
            } while (++j < j_limit);
        } // for i
    }
    return true;
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
bool bvector<Alloc>::any_range(size_type left, size_type right) const BMNOEXCEPT
{
    BM_ASSERT(left < bm::id_max && right < bm::id_max);
 
    if (!blockman_.is_init())
        return false; // nothing to do
 
    if (right < left)
        bm::xor_swap(left, right);
    if (right == bm::id_max)
        --right;
    if (left == right)
        return test(left);
 
    block_idx_type nblock_left  = (left  >> bm::set_block_shift);
    block_idx_type nblock_right = (right >> bm::set_block_shift);
 
    unsigned i0, j0;
    bm::get_block_coord(nblock_left, i0, j0);
    const bm::word_t* block = blockman_.get_block(i0, j0);
 
    if (nblock_left == nblock_right) // hit in the same block
    {
        unsigned nbit_left  = unsigned(left  & bm::set_block_mask);
        unsigned nbit_right = unsigned(right & bm::set_block_mask);
        return bm::block_any_range(block, nbit_left, nbit_right);
    }
 
    // process entry point block
    {
        unsigned nbit_left  = unsigned(left  & bm::set_block_mask);
        bool any_one = bm::block_any_range(block,
                                           nbit_left, (bm::gap_max_bits-1));
        if (any_one)
            return any_one;
        ++nblock_left;
    }
 
    // process tail block
    {
        bm::get_block_coord(nblock_right, i0, j0);
        block = blockman_.get_block(i0, j0);
        unsigned nbit_right  = unsigned(right  & bm::set_block_mask);
        bool any_one = bm::block_any_range(block, 0, nbit_right);
        if (any_one)
            return any_one;
        --nblock_right;
    }
 
    // check all blocks in the middle
    //
    if (nblock_left <= nblock_right)
    {
        unsigned i_from, j_from, i_to, j_to;
        bm::get_block_coord(nblock_left, i_from, j_from);
        bm::get_block_coord(nblock_right, i_to, j_to);
 
        bm::word_t*** blk_root = blockman_.top_blocks_root();
        {
            block_idx_type top_size = blockman_.top_block_size();
            if (i_from >= top_size)
                return false;
            if (i_to >= top_size)
            {
                i_to = unsigned(top_size-1);
                j_to = bm::set_sub_array_size-1;
            }
        }
 
        for (unsigned i = i_from; i <= i_to; ++i)
        {
            bm::word_t** blk_blk = blk_root[i];
            if (!blk_blk)
                continue;
            if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
                return true;
 
            unsigned j = (i == i_from) ? j_from : 0;
            unsigned j_limit = (i == i_to) ? j_to+1 : bm::set_sub_array_size;
            do
            {
                bool any_one = bm::block_any(blk_blk[j]);
                if (any_one)
                    return any_one;
            } while (++j < j_limit);
        } // for i
    }
    return false;
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
typename bvector<Alloc>::size_type
bvector<Alloc>::count_range(size_type left,
                            size_type right,
                            const rs_index_type&  rs_idx) const BMNOEXCEPT
{
    if (left > right)
        bm::xor_swap(left, right);
    BM_ASSERT_THROW(right < bm::id_max, BM_ERR_RANGE);
    return count_range_no_check(left, right, rs_idx);
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
typename bvector<Alloc>::size_type
bvector<Alloc>::count_range_no_check(size_type left,
                                     size_type right,
                               const rs_index_type&  rs_idx) const BMNOEXCEPT
{
    BM_ASSERT(left <= right);
    if (left == right)
        return this->test(left);
    size_type cnt_l, cnt_r;
    if (left)
        cnt_l = this->count_to(left-1, rs_idx);
    else
        cnt_l = left; // == 0
    cnt_r = this->count_to(right, rs_idx);
    BM_ASSERT(cnt_r >= cnt_l);
    return cnt_r - cnt_l;
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
bvector<Alloc>& bvector<Alloc>::invert()
{
    BM_ASSERT(!is_ro());
 
    if (!size_)
        return *this; // cannot invert a set of power 0
 
    unsigned top_blocks = blockman_.reserve_top_blocks(bm::set_top_array_size);
    bm::word_t*** blk_root = blockman_.top_blocks_root();
    for (unsigned i = 0; i < top_blocks; ++i)
    {
        bm::word_t** blk_blk = blk_root[i];
        if (!blk_blk)
        {
            blk_root[i] = (bm::word_t**)FULL_BLOCK_FAKE_ADDR;
            continue;
        }
        if (blk_blk == (bm::word_t**)FULL_BLOCK_FAKE_ADDR)
        {
            blk_root[i] = 0;
            continue;
        }
        unsigned j = 0; bm::word_t* blk;
        do
        {
            blk = blk_blk[j];
            if (!blk)
                blockman_.set_block_ptr(i, j, FULL_BLOCK_FAKE_ADDR);
            else
            if (IS_FULL_BLOCK(blk))
                blockman_.set_block_ptr(i, j, 0);
            else
            {
                if (BM_IS_GAP(blk))
                    bm::gap_invert(BMGAP_PTR(blk));
                else
                    bm::bit_invert((wordop_t*)blk);
            }
        } while (++j < bm::set_sub_array_size);
    } // for i
    
    if (size_ == bm::id_max) 
        set_bit_no_check(bm::id_max, false);
    else
        clear_range_no_check(size_, bm::id_max);
    
    return *this;
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc> 
bool bvector<Alloc>::get_bit(size_type n) const BMNOEXCEPT
{    
    BM_ASSERT(n < size_);
    BM_ASSERT_THROW((n < size_), BM_ERR_RANGE);
 
    // calculate logical block number
    unsigned nb = unsigned(n >>  bm::set_block_shift);
    unsigned i, j;
    bm::get_block_coord(nb, i, j);
 
    if (!blockman_.top_blocks_ || i >= blockman_.top_block_size_)
        return false;
 
    const bm::word_t* const* blk_blk = blockman_.top_blocks_[i];
    if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
        return true;
    if (!blk_blk) return false;
    if (const bm::word_t* block = blk_blk[j])
    {
        if (block == FULL_BLOCK_FAKE_ADDR)
            return true;
        unsigned nbit = unsigned(n & bm::set_block_mask);
        if (BM_IS_GAP(block))
            return bm::gap_test_unr(BMGAP_PTR(block), nbit);
        return block[nbit >> bm::set_word_shift] &
                  (1u << (nbit & bm::set_word_mask));
    }
    return false;
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc> 
void bvector<Alloc>::optimize(bm::word_t* temp_block,
                              optmode     opt_mode,
                              statistics* stat)
{
    BM_ASSERT(!is_ro());
 
    if (!blockman_.is_init())
    {
        if (stat)
            calc_stat(stat);
        return;
    }
    if (!temp_block)
        temp_block = blockman_.check_allocate_tempblock();
 
    if (stat)
    {
        stat->reset();
        ::memcpy(stat->gap_levels,
                 blockman_.glen(), sizeof(gap_word_t) * bm::gap_levels);
        stat->max_serialize_mem = (unsigned)sizeof(bm::id_t) * 4;
    }
    blockman_.optimize_tree(temp_block, opt_mode, stat);
    if (stat)
    {
        blockman_.stat_correction(stat);
        stat->memory_used += (unsigned)(sizeof(*this) - sizeof(blockman_));
    }
    
    // don't need to keep temp block if we optimizing memory usage
    blockman_.free_temp_block();
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
void bvector<Alloc>::optimize_range(
              size_type left,
              size_type right,
              bm::word_t* temp_block,
              optmode opt_mode)
{
    BM_ASSERT(!is_ro());
    BM_ASSERT(left <= right);
    BM_ASSERT(temp_block);
 
    block_idx_type nblock_left  = (left  >> bm::set_block_shift);
    block_idx_type nblock_right = (right >> bm::set_block_shift);
 
    for (; nblock_left <= nblock_right; ++nblock_left)
    {
        unsigned i0, j0;
        bm::get_block_coord(nblock_left, i0, j0);
        if (i0 >= blockman_.top_block_size())
            break;
        bm::word_t* block = blockman_.get_block_ptr(i0, j0);
        if (block)
            blockman_.optimize_block(i0, j0, block, temp_block, opt_mode, 0);
    } // for
 
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
void bvector<Alloc>::optimize_gap_size()
{
#if 0
    if (!blockman_.is_init())
        return;
 
    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);
#endif
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc> 
void bvector<Alloc>::set_gap_levels(const gap_word_t* glevel_len)
{
    BM_ASSERT(!is_ro());
 
    if (blockman_.is_init())
    {
        word_t*** blk_root = blockman_.top_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>& bv) const BMNOEXCEPT
{
    int res;
    unsigned top_blocks = blockman_.top_block_size();
    unsigned bvect_top_blocks = bv.blockman_.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 = bv.blockman_.get_topblock(i);
 
        if (blk_blk == arg_blk_blk) 
            continue;
 
        for (unsigned j = 0; j < bm::set_sub_array_size; ++j)
        {
            const bm::word_t* arg_blk; const bm::word_t* blk;
            if ((bm::word_t*)arg_blk_blk == FULL_BLOCK_FAKE_ADDR)
                arg_blk = FULL_BLOCK_REAL_ADDR;
            else
            {
                arg_blk = arg_blk_blk ? arg_blk_blk[j] : 0;
                if (arg_blk == FULL_BLOCK_FAKE_ADDR)
                    arg_blk = FULL_BLOCK_REAL_ADDR;
            }
            if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
                blk = FULL_BLOCK_REAL_ADDR;
            else
            {
                blk = blk_blk ? blk_blk[j] : 0;
                if (blk == FULL_BLOCK_FAKE_ADDR)
                    blk = FULL_BLOCK_REAL_ADDR;
            }
            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 (!bm::gap_is_all_zero(BMGAP_PTR(pblk)))
                        return res;
                }
                else
                {
                    if (!bm::bit_is_all_zero(pblk))
                        return res;
                }
                continue;
            }
            bool arg_gap = BM_IS_GAP(arg_blk);
            bool gap = BM_IS_GAP(blk);
            
            if (arg_gap != gap)
            {
                BM_DECLARE_TEMP_BLOCK(temp_blk)
                bm::wordop_t* blk1; bm::wordop_t* blk2;
 
                if (gap)
                {
                    bm::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
                {
                    bm::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 = bm::bitcmp(blk1, blk2, bm::set_block_size_op);
            }
            else
            {
                if (gap)
                {
                    res = bm::gapcmp(BMGAP_PTR(blk), BMGAP_PTR(arg_blk));
                }
                else
                {
                    res = bm::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>
bool bvector<Alloc>::find_first_mismatch(
                        const bvector<Alloc>& bvect, size_type& pos,
                        size_type search_to) const BMNOEXCEPT
{
    unsigned top_blocks = blockman_.top_block_size();
    bm::word_t*** top_root = blockman_.top_blocks_root();
 
    if (!top_blocks || !top_root)
    {
        return bvect.find(pos);
    }
    bm::word_t*** arg_top_root = bvect.blockman_.top_blocks_root();
    unsigned i_to, j_to;
    {
        unsigned bvect_top_blocks = bvect.blockman_.top_block_size();
        if (!bvect_top_blocks || !arg_top_root)
        {
            bool f = this->find(pos);
            if (f)
            {
                if (pos > search_to)
                    return false;
            }
            return f;
        }
 
        if (bvect_top_blocks > top_blocks)
            top_blocks = bvect_top_blocks;
        block_idx_type nb_to = (search_to >> bm::set_block_shift);
        bm::get_block_coord(nb_to, i_to, j_to);
    }
    if (i_to < top_blocks)
        top_blocks = i_to+1;
 
    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)
        {
        /* TODO: fix buffer overrread here
            unsigned arg_top_blocks = bvect.blockman_.top_block_size_;
            if (top_blocks < arg_top_blocks)
                arg_top_blocks = top_blocks;
            if (i_to < arg_top_blocks)
                arg_top_blocks = i_to+1;
 
            // look ahead for top level mismatch
            for (++i; i < arg_top_blocks; ++i)
            {
                if (top_root[i] != arg_top_root[i])
                {
                    blk_blk = blockman_.get_topblock(i);
                    arg_blk_blk = bvect.blockman_.get_topblock(i);
                    BM_ASSERT(blk_blk != arg_blk_blk);
                    goto find_sub_block;
                }
            }
            */
            continue;
        }
     //find_sub_block:
        unsigned j = 0;
        do
        {
            const bm::word_t* arg_blk; const bm::word_t* blk;
            arg_blk = ((bm::word_t*)arg_blk_blk == FULL_BLOCK_FAKE_ADDR) ?
                        FULL_BLOCK_REAL_ADDR :
                        arg_blk_blk ? (BLOCK_ADDR_SAN(arg_blk_blk[j])) : 0;
            blk = ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR) ?
                    FULL_BLOCK_REAL_ADDR :
                    (blk_blk ? (BLOCK_ADDR_SAN(blk_blk[j])) : 0);
            if (blk == arg_blk)
                continue;
 
            unsigned block_pos;
            bool found = bm::block_find_first_diff(blk, arg_blk, &block_pos);
            if (found)
            {
                pos =
                    (size_type(i) * bm::set_sub_array_size * bm::gap_max_bits) +
                    (size_type(j) * bm::gap_max_bits) + block_pos;
                if (pos > search_to)
                    return false;
                return true;
            }
 
            if (i == i_to)
            {
                if (j >= j_to)
                    return false;
            }
 
        } while (++j < bm::set_sub_array_size);
    } // for i
 
    return false;
 
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
void bvector<Alloc>::swap(bvector<Alloc>& bvect) BMNOEXCEPT
{
    if (this != &bvect)
    {
        blockman_.swap(bvect.blockman_);
        bm::xor_swap(size_,bvect.size_);
    }
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc> 
void bvector<Alloc>::calc_stat(
                   struct bvector<Alloc>::statistics* st) const BMNOEXCEPT
{
    BM_ASSERT(st);
    
    st->reset();
    ::memcpy(st->gap_levels, 
             blockman_.glen(), sizeof(gap_word_t) * bm::gap_levels);
 
    st->max_serialize_mem = unsigned(sizeof(bm::id_t) * 4);
    unsigned top_size = blockman_.top_block_size();
 
    size_t blocks_mem = sizeof(blockman_);
    blocks_mem +=
        (blockman_.temp_block_ ? sizeof(bm::word_t) * bm::set_block_size : 0);
    blocks_mem += sizeof(bm::word_t**) * top_size;
    bm::word_t*** blk_root = blockman_.top_blocks_root();
    
    if (blk_root)
    {
        for (unsigned i = 0; i < top_size; ++i)
        {
            const bm::word_t* const* blk_blk = blk_root[i];
            if (!blk_blk)
            {
                ++i;
                bool found = bm::find_not_null_ptr(blk_root, i, top_size, &i);
                if (!found)
                    break;
                blk_blk = blk_root[i];
                BM_ASSERT(blk_blk);
                if (!blk_blk)
                    break;
            }
            if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
                continue;
            st->ptr_sub_blocks++;
            for (unsigned j = 0; j < bm::set_sub_array_size; ++j)
            {
                const bm::word_t* blk = blk_blk[j];
                if (IS_VALID_ADDR(blk))
                {
                    if (BM_IS_GAP(blk))
                    {
                        const bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
                        unsigned cap;
                        unsigned len = gap_length(gap_blk);
                        cap = is_ro() ? len
                            : bm::gap_capacity(gap_blk, blockman_.glen());
                        unsigned level = bm::gap_level(gap_blk);
                        st->add_gap_block(cap, len, level);
                    }
                    else // bit block
                        st->add_bit_block();
                }
            } // for j
        } // for i
        
        size_t full_null_size = blockman_.calc_serialization_null_full();
        st->max_serialize_mem += full_null_size;
        
    } // if blk_root
    
    size_t 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 += unsigned(sizeof(*this) - sizeof(blockman_));
    blocks_mem += st->ptr_sub_blocks * (sizeof(void*) * bm::set_sub_array_size);
    st->memory_used += blocks_mem;
    if (is_ro())
        st->memory_used += sizeof(typename blocks_manager_type::arena);
    st->bv_count = 1;
 
}
 
// -----------------------------------------------------------------------
 
template<typename Alloc>
void bvector<Alloc>::fill_alloc_digest(bvector<Alloc>& bv_blocks) const
{
    bv_blocks.init();
 
    unsigned top_size = blockman_.top_block_size();
    bm::word_t*** blk_root = blockman_.top_blocks_root();
    if (blk_root)
    {
        for (unsigned i = 0; i < top_size; ++i)
        {
            const bm::word_t* const* blk_blk = blk_root[i];
            if (!blk_blk || ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR))
                continue;
            for (unsigned j = 0; j < bm::set_sub_array_size; ++j)
            {
                const bm::word_t* blk = blk_blk[j];
                if (IS_VALID_ADDR(blk))
                {
                    size_type nb = i * bm::set_sub_array_size + j;
                    bv_blocks.set_bit_no_check(nb);
                }
            } // for j
        } // for i
    } // if blk_root
}
 
 
// -----------------------------------------------------------------------
 
template<class Alloc>
void bvector<Alloc>::set(const size_type* ids,
                        size_type ids_size, bm::sort_order so)
{
    BM_ASSERT(!is_ro());
 
    if (!ids || !ids_size)
        return; // nothing to do
    if (!blockman_.is_init())
        blockman_.init_tree();
 
    import(ids, ids_size, so);
    sync_size();
}
 
// -----------------------------------------------------------------------
 
template<class Alloc>
void bvector<Alloc>::keep(const size_type* ids, size_type ids_size,
                          bm::sort_order so)
{
    BM_ASSERT(!is_ro());
 
    if (!ids || !ids_size || !blockman_.is_init())
    {
        clear();
        return;
    }
    bvector<Alloc> bv_tmp; // TODO: better optimize for SORTED case (avoid temp)
    bv_tmp.import(ids, ids_size, so);
 
    size_type last;
    bool found = bv_tmp.find_reverse(last);
    if (found)
    {
        bv_tmp.resize(last+1);
        bit_and(bv_tmp);
    }
    else
    {
        BM_ASSERT(0);
        clear();
    }
}
 
// -----------------------------------------------------------------------
 
template<class Alloc>
void bvector<Alloc>::clear(bool free_mem) BMNOEXCEPT
{
    if (is_ro())
    {
        BM_ASSERT(free_mem);
        blockman_.destroy_arena();
    }
    else
        blockman_.set_all_zero(free_mem);
}
 
// -----------------------------------------------------------------------
 
template<class Alloc>
void bvector<Alloc>::clear(const size_type* ids,
                           size_type ids_size, bm::sort_order so)
{
    BM_ASSERT(!is_ro());
 
    if (!ids || !ids_size || !blockman_.is_init())
    {
        return;
    }
    bvector<Alloc> bv_tmp; // TODO: better optimize for SORTED case (avoid temp)
    bv_tmp.import(ids, ids_size, so);
 
    size_type last;
    bool found = bv_tmp.find_reverse(last);
    if (found)
    {
        bv_tmp.resize(last+1);
        bit_sub(bv_tmp);
    }
    else
    {
        BM_ASSERT(0);
    }
}
 
// -----------------------------------------------------------------------
 
template<class Alloc>
bvector<Alloc>& bvector<Alloc>::set()
{
    BM_ASSERT(!is_ro());
 
    set_range(0, size_ - 1, true);
    return *this;
}
 
// -----------------------------------------------------------------------
 
template<class Alloc>
bvector<Alloc>& bvector<Alloc>::set(size_type n, bool val)
{
    BM_ASSERT(!is_ro());
 
    set_bit(n, val);
    return *this;
}
 
// -----------------------------------------------------------------------
 
template<class Alloc>
bool bvector<Alloc>::set_bit_conditional(size_type n, bool val, bool condition)
{
    if (val == condition) return false;
    if (n >= size_)
    {
        size_type new_size = (n == bm::id_max) ? bm::id_max : n + 1;
        resize(new_size);
    }
    return set_bit_conditional_impl(n, val, condition);
}
 
// -----------------------------------------------------------------------
 
template<class Alloc>
bool bvector<Alloc>::set_bit_and(size_type n, bool val)
{
    BM_ASSERT(!is_ro());
    BM_ASSERT(n < size_);
    BM_ASSERT_THROW(n < size_, BM_ERR_RANGE);
    
    if (!blockman_.is_init())
        blockman_.init_tree();
    return and_bit_no_check(n, val);
}
 
// -----------------------------------------------------------------------
 
template<class Alloc>
bool bvector<Alloc>::set_bit(size_type n, bool val)
{
    BM_ASSERT(!is_ro());
    BM_ASSERT_THROW(n < bm::id_max, BM_ERR_RANGE);
 
    if (!blockman_.is_init())
        blockman_.init_tree();
    if (n >= size_)
    {
        size_type new_size = (n == bm::id_max) ? bm::id_max : n + 1;
        resize(new_size);
    }
    return set_bit_no_check(n, val);
}
 
// -----------------------------------------------------------------------
 
template<class Alloc>
void bvector<Alloc>::import(const size_type* ids, size_type size_in,
                            bm::sort_order  sorted_idx)
{
    BM_ASSERT(!is_ro());
 
    size_type n, start(0), stop(size_in);
    block_idx_type nblock;
 
    n = ids[start];
    nblock = (n >> bm::set_block_shift);
 
    switch(sorted_idx)
    {
    case BM_SORTED:
    {
        block_idx_type nblock_end = (ids[size_in-1] >> bm::set_block_shift);
        if (nblock == nblock_end) // special case: one block import
        {
            import_block(ids, nblock, 0, stop);
            return;
        }
    }
    break;
    default:
        break;
    } // switch
 
    do
    {
        n = ids[start];
        nblock = (n >> bm::set_block_shift);
        #ifdef BM64ADDR
            stop = bm::idx_arr_block_lookup_u64(ids, size_in, nblock, start);
        #else
            stop = bm::idx_arr_block_lookup_u32(ids, size_in, nblock, start);
        #endif
        BM_ASSERT(start < stop);
        import_block(ids, nblock, start, stop);
        start = stop;
    } while (start < size_in);
}
 
// -----------------------------------------------------------------------
 
template<class Alloc>
void bvector<Alloc>::import_sorted(const size_type* ids,
                                   const size_type size_in,
                                   bool opt_flag)
{
    BM_ASSERT(size_in);
    BM_ASSERT(ids[0] < bm::id_max); // limit is 2^31-1 (for 32-bit mode)
    BM_ASSERT(ids[size_in-1] < bm::id_max);
 
    size_type n, start(0), stop = size_in;
    block_idx_type nblock, nblock_end;
 
    n = ids[start];
    nblock = (n >> bm::set_block_shift);
    nblock_end = (ids[size_in-1] >> bm::set_block_shift);
 
    if (nblock == nblock_end) // special (but frequent)case: one block import
    {
        import_block(ids, nblock, 0, stop);
        unsigned nbit = unsigned(ids[size_in-1] & bm::set_block_mask);
        if (opt_flag && nbit == 65535) // last bit in block
        {
            unsigned i, j;
            bm::get_block_coord(nblock, i, j);
            blockman_.optimize_bit_block(i, j, opt_compress);
        }
    }
    else
    {
        do
        {
            // TODO: use one-sided binary search to find the block limits
            #ifdef BM64ADDR
                stop = bm::idx_arr_block_lookup_u64(ids, size_in, nblock, start);
            #else
                stop = bm::idx_arr_block_lookup_u32(ids, size_in, nblock, start);
            #endif
            BM_ASSERT(start < stop);
 
            import_block(ids, nblock, start, stop);
            start = stop;
            nblock = (ids[stop] >> bm::set_block_shift);
        } while (start < size_in);
 
 
        if (opt_flag) // multi-block sorted import, lets optimize
        {
            n = ids[start];
            nblock = (n >> bm::set_block_shift);
            nblock_end = (ids[size_in-1] >> bm::set_block_shift);
            unsigned nbit = unsigned(ids[size_in-1] & bm::set_block_mask);
            nblock_end += bool(nbit == 65535);
            do
            {
                unsigned i, j;
                bm::get_block_coord(nblock++, i, j);
                blockman_.optimize_bit_block(i, j, opt_compress);
            } while (nblock < nblock_end);
        }
 
    }
}
 
 
// -----------------------------------------------------------------------
 
template<class Alloc>
void bvector<Alloc>::import_block(const size_type* ids,
                                  block_idx_type   nblock,
                                  size_type        start,
                                  size_type        stop)
{
    BM_ASSERT(stop > start);
    int block_type;
    bm::word_t* blk =
        blockman_.check_allocate_block(nblock, 1, 0, &block_type,
                                       true/*allow NULL ret*/);
    if (!IS_FULL_BLOCK(blk))
    {
        if (BM_IS_GAP(blk))
        {
            if (stop-start == 1)
            {
                unsigned nbit = unsigned(ids[0] & bm::set_block_mask);
                gap_block_set_no_ret(BMGAP_PTR(blk), true, nblock, nbit);
                return;
            }
            blk = blockman_.deoptimize_block(nblock); // TODO: try to avoid
        }
        #ifdef BM64ADDR
            bm::set_block_bits_u64(blk, ids, start, stop);
        #else
            bm::set_block_bits_u32(blk, ids, start, stop);
        #endif
        if (nblock == bm::set_total_blocks-1)
            blk[bm::set_block_size-1] &= ~(1u<<31);
    }
}
 
// -----------------------------------------------------------------------
 
template<class Alloc>
void bvector<Alloc>::swap(size_type idx1, size_type idx2)
{
    BM_ASSERT(!is_ro());
    BM_ASSERT_THROW(idx1 < bm::id_max, BM_ERR_RANGE);
    BM_ASSERT_THROW(idx2 < bm::id_max, BM_ERR_RANGE);
 
    block_idx_type nb1 = (idx1 >>  bm::set_block_shift);
    block_idx_type nb2 = (idx2 >>  bm::set_block_shift);
 
    bm::word_t* block1, *block2;
    unsigned nbit1, nbit2;
    nbit1 = unsigned(idx1 & bm::set_block_mask);
    nbit2 = unsigned(idx2 & bm::set_block_mask);
 
    if (nb1 == nb2) // same block hit
    {
        unsigned i0, j0;
        bm::get_block_coord(nb1, i0, j0);
        block1 = blockman_.get_block_ptr(i0, j0);
        if (!block1 || (block1==FULL_BLOCK_FAKE_ADDR)) // nothing to do?
            return;
 
        if (BM_IS_GAP(block1))
        {
            bm::gap_word_t* gblk = BMGAP_PTR(block1);
            bool b1 = bm::gap_test_unr(gblk, nbit1);
            bool b2 = bm::gap_test_unr(gblk, nbit2);
            if (b1 != b2)
            {
                this->gap_block_set_no_ret(gblk, b2, nb1, nbit1);
                block2 = blockman_.get_block_ptr(i0, j0);
                if (block1 == block2) // same block
                    this->gap_block_set_no_ret(gblk, b1, nb1, nbit2);
                else
                    set_bit_no_check(idx2, b1);
            }
            return;
        }
        unsigned nword1 = unsigned(nbit1 >> bm::set_word_shift);
        unsigned nword2 = unsigned(nbit2 >> bm::set_word_shift);
        nbit1 &= bm::set_word_mask; nbit2 &= bm::set_word_mask;
        bool b1 = block1[nword1] & (1u << nbit1);
        bool b2 = block1[nword2] & (1u << nbit2);
        if (b1 != b2)
        {
            nbit1 = 1u << nbit1; nbit2 = 1u << nbit2;
            auto w = block1[nword1];
            (b2) ? w |= nbit1 : w &= ~nbit1;
            block1[nword1] = w;
            w = block1[nword2];
            (b1) ? w |= nbit2 : w &= ~nbit2;
            block1[nword2] = w;
        }
        return;
    } // if (same block)
 
    {
        unsigned i0, j0;
        bm::get_block_coord(nb1, i0, j0);
        block1 = blockman_.get_block_ptr(i0, j0);
        bm::get_block_coord(nb2, i0, j0);
        block2 = blockman_.get_block_ptr(i0, j0);
    }
    if (block1 == block2) // nothing to do
        return;
 
    bm::gap_word_t *gblk1{0}, *gblk2{0};
    unsigned cpos1{ 0 }, cpos2{ 0 };
    bool b1, b2, b1real, b2real;
 
    if (!block1)
    {
        b1 = false; b1real = false;
    }
    else
    if (block1 == FULL_BLOCK_FAKE_ADDR)
    {
        b1 = true; b1real = false;
    }
    else
    {
        b1real = true;
        nbit1 = unsigned(idx1 & bm::set_block_mask);
        if (BM_IS_GAP(block1))
        {
            gblk1 = BMGAP_PTR(block1);
            unsigned is_set;
            cpos1 = bm::gap_bfind(gblk1, nbit1, &is_set);
            b1 = is_set;
        }
        else // bit block
        {
            unsigned nword1 = unsigned(nbit1 >> bm::set_word_shift);
            b1 = block1[nword1] & (1u << (nbit1 & bm::set_word_mask));
        }
    }
 
    if (!block2)
    {
        b2 = false; b2real = false;
    }
    else
    if (block2 == FULL_BLOCK_FAKE_ADDR)
    {
        b2 = true; b2real = false;
    }
    else
    {
        b2real = true;
        nbit2 = unsigned(idx2 & bm::set_block_mask);
        if (BM_IS_GAP(block2))
        {
            gblk2 = BMGAP_PTR(block2);
            unsigned is_set;
            cpos2 = bm::gap_bfind(gblk2, nbit2, &is_set);
            b2 = is_set;
        }
        else // bit block
        {
            unsigned nword2 = unsigned(nbit2 >> bm::set_word_shift);
            b2 = block2[nword2] & (1u << (nbit2 & bm::set_word_mask));
        }
    }
 
    if (b1 == b2)
        return;
 
    if (b1real)
    {
        if (BM_IS_GAP(block1))
        {
            unsigned new_len, old_len;
            unsigned is_set = b1;
            old_len = bm::gap_length(gblk1)-1;
            new_len = bm::gap_set_value_cpos(b2, gblk1, nbit1, &is_set, cpos1);
            if (old_len < new_len)
            {
                unsigned threshold = bm::gap_limit(gblk1, blockman_.glen());
                if (new_len > threshold)
                    blockman_.extend_gap_block(nb1, gblk1);
            }
        }
        else // bit block
        {
            unsigned nword1 = unsigned(nbit1 >> bm::set_word_shift);
            nbit1 = 1u << (nbit1 & bm::set_word_mask);
            auto w = block1[nword1];
            (b2) ? w |= nbit1 : w &= ~nbit1;
            block1[nword1] = w;
        }
    }
    else // block
    {
        set_bit_no_check(idx1, b2);
    }
 
    if (b2real)
    {
        if (BM_IS_GAP(block2))
        {
            unsigned new_len, old_len;
            unsigned is_set = b2;
            old_len = bm::gap_length(gblk2)-1;
            new_len = bm::gap_set_value_cpos(b1, gblk2, nbit2, &is_set, cpos2);
            if (old_len < new_len)
            {
                unsigned threshold = bm::gap_limit(gblk2, blockman_.glen());
                if (new_len > threshold)
                    blockman_.extend_gap_block(nb2, gblk2);
            }
        }
        else // bit block
        {
            unsigned nword2 = unsigned(nbit2 >> bm::set_word_shift);
            nbit2 = 1u << (nbit2 & bm::set_word_mask);
            auto w = block2[nword2];
            (b1) ? w |= nbit2 : w &= ~nbit2;
            block2[nword2] = w;
        }
    }
    else
    {
        set_bit_no_check(idx2, b1);
    }
 
 
}
 
// -----------------------------------------------------------------------
 
template<class Alloc> 
bool bvector<Alloc>::set_bit_no_check(size_type n, bool val)
{
    BM_ASSERT(!is_ro());
    BM_ASSERT_THROW(n < bm::id_max, BM_ERR_RANGE);
 
    // calculate logical block number
    block_idx_type nblock = (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 (!IS_VALID_ADDR(blk))
        return false;
 
    // calculate word number in block and bit
    unsigned nbit   = unsigned(n & bm::set_block_mask);
    if (block_type) // gap
    {
        return gap_block_set(BMGAP_PTR(blk), val, nblock, nbit);
    }
    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)
        {
            val = ~(*word & mask);
            *word |= mask; // set bit
            return val;
        }
        else
        {
            val = ~(*word & mask);
            *word &= ~mask; // clear bit
            return val;
        }
    }
}
 
// -----------------------------------------------------------------------
 
template<class Alloc>
void bvector<Alloc>::set_bit_no_check(size_type n)
{
    BM_ASSERT(!is_ro());
    BM_ASSERT_THROW(n < bm::id_max, BM_ERR_RANGE);
 
    const bool val = true; // set bit
 
    block_idx_type nblock = (n >>  bm::set_block_shift);
    unsigned nbit   = unsigned(n & bm::set_block_mask);
 
    int block_type;
    bm::word_t* blk =
        blockman_.check_allocate_block(nblock,
                                       val,
                                       get_new_blocks_strat(),
                                       &block_type);
    if (!IS_VALID_ADDR(blk))
        return;
 
    if (block_type) // gap block
    {
        this->gap_block_set_no_ret(BMGAP_PTR(blk), val, nblock, nbit);
    }
    else  // bit block
    {
        unsigned nword  = nbit >> bm::set_word_shift;
        nbit &= bm::set_word_mask;
        blk[nword] |= (1u << nbit); // set bit
    }
}
 
// -----------------------------------------------------------------------
 
template<class Alloc>
void bvector<Alloc>::clear_bit_no_check(size_type n)
{
    BM_ASSERT(!is_ro());
    BM_ASSERT_THROW(n < bm::id_max, BM_ERR_RANGE);
 
    const bool val = false; // clear bit
 
    block_idx_type nblock = (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;
 
    unsigned nbit = unsigned(n & bm::set_block_mask);
    if (block_type) // gap
    {
        this->gap_block_set_no_ret(BMGAP_PTR(blk), val, nblock, nbit);
    }
    else  // bit block
    {
        unsigned nword  = unsigned(nbit >> bm::set_word_shift);
        nbit &= bm::set_word_mask;
        blk[nword] &= ~(1u << nbit); // clear bit
    }
}
 
 
// -----------------------------------------------------------------------
 
template<class Alloc>
bool bvector<Alloc>::gap_block_set(bm::gap_word_t* gap_blk,
                                   bool val, block_idx_type nblock,
                                   unsigned nbit)
{
    unsigned is_set, new_len, old_len;
    old_len = bm::gap_length(gap_blk)-1;
    new_len = bm::gap_set_value(val, gap_blk, nbit, &is_set);
    if (old_len < new_len)
    {
        unsigned threshold = bm::gap_limit(gap_blk, blockman_.glen());
        if (new_len > threshold)
            blockman_.extend_gap_block(nblock, gap_blk);
    }
    return is_set;
}
 
// -----------------------------------------------------------------------
 
template<class Alloc>
void bvector<Alloc>::gap_block_set_no_ret(bm::gap_word_t* gap_blk,
                        bool val, block_idx_type nblock, unsigned nbit)
{
    unsigned new_len, old_len;
    old_len = bm::gap_length(gap_blk)-1;
    new_len = bm::gap_set_value(val, gap_blk, nbit);
    if (old_len < new_len)
    {
        unsigned threshold = bm::gap_limit(gap_blk, blockman_.glen());
        if (new_len > threshold)
            blockman_.extend_gap_block(nblock, gap_blk);
    }
}
 
 
// -----------------------------------------------------------------------
 
template<class Alloc>
bool bvector<Alloc>::inc(size_type n)
{
    BM_ASSERT(!is_ro());
    // calculate logical block number
    block_idx_type nblock = (n >>  bm::set_block_shift);
    bm::word_t* blk =
        blockman_.check_allocate_block(nblock,
                                       get_new_blocks_strat());
    BM_ASSERT(IS_VALID_ADDR(blk));
 
    unsigned nbit   = unsigned(n & bm::set_block_mask);
    unsigned is_set;
    if (BM_IS_GAP(blk))
    {
        bm::gap_word_t* gap_blk = BMGAP_PTR(blk);
        is_set = (bm::gap_test_unr(gap_blk, nbit) != 0);
        this->gap_block_set(gap_blk, !is_set, nblock, nbit); // flip
    }
    else // bit block
    {
        unsigned nword  = unsigned(nbit >> bm::set_word_shift);
        nbit &= bm::set_word_mask;
        bm::word_t* word = blk + nword;
        const bm::word_t  mask = (((bm::word_t)1) << nbit);
        is_set = ((*word) & mask);
        *word ^= mask; // flip the bit
    }
    return is_set;
}
 
// -----------------------------------------------------------------------
 
template<class Alloc> 
bool bvector<Alloc>::set_bit_conditional_impl(size_type n, 
                                              bool     val, 
                                              bool     condition)
{
    // calculate logical block number
    block_idx_type nblock = (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 (!IS_VALID_ADDR(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);
        unsigned is_set = gap_block_set(gap_blk, val, nblock, nbit);
        return is_set;
    }
    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;
            else               // clear bit
                *word &= ~mask;
            return true;
        }
    }
    return false;
 
}
 
// -----------------------------------------------------------------------
 
 
template<class Alloc> 
bool bvector<Alloc>::and_bit_no_check(size_type n, bool val)
{
    BM_ASSERT(!is_ro());
    // calculate logical block number
    block_idx_type nblock = (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 (!IS_VALID_ADDR(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 = (bm::gap_test_unr(gap_blk, nbit) != 0);
 
        bool new_val = val & old_val;
        if (new_val != old_val)
        {
            unsigned is_set = gap_block_set(gap_blk, val, nblock, nbit);
            BM_ASSERT(is_set);
            return is_set;
        }
    }
    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;
            }
            else               // clear bit
            {
                *word &= ~mask;
            }
            return true;
        }
    }
    return false;
}
 
//---------------------------------------------------------------------
 
template<class Alloc>
bool bvector<Alloc>::find(size_type from, size_type& pos) const BMNOEXCEPT
{
    if (from == bm::id_max)
        return false;
    if (!from)
    {
        return find(pos);
    }
    pos = check_or_next(from);
    return (pos != 0);
}
 
//---------------------------------------------------------------------
 
template<class Alloc>
bool bvector<Alloc>::find_reverse(size_type& pos) const BMNOEXCEPT
{
    bool found;
    
    unsigned top_blocks = blockman_.top_block_size();
    if (!top_blocks)
        return false;
    for (unsigned i = top_blocks-1; true; --i)
    {
        const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
        if (blk_blk)
        {
            if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
                blk_blk = FULL_SUB_BLOCK_REAL_ADDR;
 
            for (unsigned short j = bm::set_sub_array_size-1; true; --j)
            {
                const bm::word_t* blk = blk_blk[j];
                if (blk)
                {
                    unsigned block_pos;
                    if (blk == FULL_BLOCK_FAKE_ADDR)
                    {
                        block_pos = bm::gap_max_bits-1;
                        found = true;
                    }
                    else
                    {
                        bool is_gap = BM_IS_GAP(blk);
                        found = is_gap ? bm::gap_find_last(BMGAP_PTR(blk), &block_pos)
                                       : bm::bit_find_last(blk, &block_pos);
                    }
                    if (found)
                    {
                        block_idx_type base_idx =
                            block_idx_type(i) * bm::set_sub_array_size *
                            bm::gap_max_bits;
                        base_idx += j * bm::gap_max_bits;
                        pos = base_idx + block_pos;
                        return found;
                    }
                }
                
                if (j == 0)
                    break;
            } // for j
        } // if blk_blk
        
        if (i == 0)
            break;
    } // for i
    return false;
}
 
//---------------------------------------------------------------------
 
template<class Alloc>
bool bvector<Alloc>::find_reverse(size_type from, size_type& pos) const BMNOEXCEPT
{
    bool found;
    if (!blockman_.is_init())
        return false; // nothing to do
    if (!from)
    {
        pos = from;
        return this->test(from);
    }
 
    block_idx_type nb = (from >> bm::set_block_shift);
    unsigned i0, j0;
    bm::get_block_coord(nb, i0, j0);
 
    const bm::word_t* block = blockman_.get_block_ptr(i0, j0);
    if (block)
    {
        size_type base_idx;
        unsigned found_nbit;
        unsigned nbit = unsigned(from & bm::set_block_mask);
        found = bm::block_find_reverse(block, nbit, &found_nbit);
        if (found)
        {
            base_idx = bm::get_block_start<size_type>(i0, j0);
            pos = base_idx + found_nbit;
            return found;
        }
    }
 
    if (nb)
        --nb;
    else
        return false;
    bm::get_block_coord(nb, i0, j0);
 
    const bm::word_t* const* blk_blk = blockman_.get_topblock(i0);
    if (blk_blk)
    {
        if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
            blk_blk = FULL_SUB_BLOCK_REAL_ADDR;
        for (unsigned j = j0; true; --j)
        {
            const bm::word_t* blk = blk_blk[j];
            if (blk)
            {
                unsigned block_pos;
                if (blk == FULL_BLOCK_FAKE_ADDR)
                {
                    block_pos = bm::gap_max_bits-1;
                    found = true;
                }
                else
                {
                    bool is_gap = BM_IS_GAP(blk);
                    found = is_gap ? bm::gap_find_last(BMGAP_PTR(blk), &block_pos)
                                   : bm::bit_find_last(blk, &block_pos);
                }
                if (found)
                {
                    block_idx_type base_idx =
                        block_idx_type(i0) * bm::set_sub_array_size *
                        bm::gap_max_bits;
                    base_idx += j * bm::gap_max_bits;
                    pos = base_idx + block_pos;
                    return found;
                }
            }
            if (!j)
                break;
        } // for j
    }
    if (i0)
        --i0;
    else
        return false;
 
    for (unsigned i = i0; true; --i)
    {
        blk_blk = blockman_.get_topblock(i);
        if (blk_blk)
        {
            if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
                blk_blk = FULL_SUB_BLOCK_REAL_ADDR;
            for (unsigned short j = bm::set_sub_array_size-1; true; --j)
            {
                const bm::word_t* blk = blk_blk[j];
                if (blk)
                {
                    unsigned block_pos;
                    if (blk == FULL_BLOCK_FAKE_ADDR)
                    {
                        block_pos = bm::gap_max_bits-1;
                        found = true;
                    }
                    else
                    {
                        bool is_gap = BM_IS_GAP(blk);
                        found = is_gap ? bm::gap_find_last(BMGAP_PTR(blk), &block_pos)
                                       : bm::bit_find_last(blk, &block_pos);
                    }
                    if (found)
                    {
                        block_idx_type base_idx =
                            block_idx_type(i) * bm::set_sub_array_size *
                            bm::gap_max_bits;
                        base_idx += j * bm::gap_max_bits;
                        pos = base_idx + block_pos;
                        return found;
                    }
                }
                if (!j)
                    break;
            } // for j
        }
        if (i == 0)
            break;
    } // for i
 
    return false;
}
 
//---------------------------------------------------------------------
 
template<class Alloc>
bool bvector<Alloc>::find(size_type& pos) const BMNOEXCEPT
{
    bool found;
    
    unsigned top_blocks = blockman_.top_block_size();
    for (unsigned i = 0; i < top_blocks; ++i)
    {
        const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
        if (blk_blk)
        {
            if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
                blk_blk = FULL_SUB_BLOCK_REAL_ADDR;
 
            for (unsigned j = 0; j < bm::set_sub_array_size; ++j)
            {
                const bm::word_t* blk = blk_blk[j];
                if (blk)
                {
                    unsigned block_pos;
                    if (blk == FULL_BLOCK_FAKE_ADDR)
                    {
                        found = true; block_pos = 0;
                    }
                    else
                    {
                        bool is_gap = BM_IS_GAP(blk);
                        found = (is_gap) ? bm::gap_find_first(BMGAP_PTR(blk), &block_pos)
                                         : bm::bit_find_first(blk, &block_pos);
                    }
                    if (found)
                    {
                        size_type base_idx = block_idx_type(i) * bm::bits_in_array;
                        base_idx += j * bm::gap_max_bits;
                        pos = base_idx + block_pos;
                        return found;
                    }
                }
            } // for j
        } // if blk_blk
    } // for i
    return false;
}
 
//---------------------------------------------------------------------
 
template<class Alloc>
bool bvector<Alloc>::find_range(size_type& in_first,
                                size_type& in_last) const BMNOEXCEPT
{
    bool found = find(in_first);
    if (found)
    {
        found = find_reverse(in_last);
        BM_ASSERT(found);
        BM_ASSERT(in_first <= in_last);
    }
    else
    {
        in_first = in_last = 0; // zero the output just in case
    }
    return found;
}
 
//---------------------------------------------------------------------
 
template<class Alloc>
bool bvector<Alloc>::find_rank(size_type  rank_in, 
                               size_type  from, 
                               size_type& pos) const BMNOEXCEPT
{
    BM_ASSERT_THROW(from < bm::id_max, BM_ERR_RANGE);
 
    bool ret = false;
    
    if (!rank_in || !blockman_.is_init())
        return ret;
    
    block_idx_type nb  = (from  >>  bm::set_block_shift);
    bm::gap_word_t nbit = bm::gap_word_t(from & bm::set_block_mask);
    unsigned bit_pos = 0;
 
    for (; nb < bm::set_total_blocks; ++nb)
    {
        int no_more_blocks;
        const bm::word_t* block = blockman_.get_block(nb, &no_more_blocks);
        if (block)
        {
            if (!nbit && (rank_in > bm::gap_max_bits)) // requested rank cannot be in this block
            {
                unsigned cnt = blockman_.block_bitcount(block);
                BM_ASSERT(cnt < rank_in);
                rank_in -= cnt;
                continue;
            }
            else
            {
                rank_in = bm::block_find_rank(block, rank_in, nbit, bit_pos);
                if (!rank_in) // target found
                {
                    pos = bit_pos + (nb * bm::set_block_size * 32);
                    return true;
                }
            }
        }
        else
        {
            // TODO: better next block search
            if (no_more_blocks)
                break;
        }
        nbit ^= nbit; // zero start bit after first scanned block
    } // for nb
    
    return ret;
}
 
//---------------------------------------------------------------------
 
template<class Alloc>
bool bvector<Alloc>::find_rank(size_type             rank_in, 
                               size_type             from, 
                               size_type&            pos,
                               const rs_index_type&  rs_idx) const BMNOEXCEPT
{
    BM_ASSERT_THROW(from < bm::id_max, BM_ERR_RANGE);
 
    bool ret = false;
    
    if (!rank_in ||
        !blockman_.is_init() ||
        (rs_idx.count() < rank_in))
        return ret;
    
    block_idx_type nb;
    if (from)
        nb = (from >> bm::set_block_shift);
    else
    {
        nb = rs_idx.find(rank_in);
        BM_ASSERT(rs_idx.rcount(nb) >= rank_in);
        if (nb)
            rank_in -= rs_idx.rcount(nb-1);
    }
    
    bm::gap_word_t nbit = bm::gap_word_t(from & bm::set_block_mask);
    unsigned bit_pos = 0;
 
    for (; nb < rs_idx.get_total(); ++nb)
    {
        int no_more_blocks;
        const bm::word_t* block = blockman_.get_block(nb, &no_more_blocks);
        if (block)
        {
            if (!nbit) // check if the whole block can be skipped
            {
                unsigned block_bc = rs_idx.count(nb);
                if (rank_in <= block_bc) // target block
                {
                    nbit = rs_idx.select_sub_range(nb, rank_in);
                    rank_in = bm::block_find_rank(block, rank_in, nbit, bit_pos);
                    BM_ASSERT(rank_in == 0);
                    pos = bit_pos + (nb * bm::set_block_size * 32);
                    return true;
                }
                rank_in -= block_bc;
                continue;
            }
 
            rank_in = bm::block_find_rank(block, rank_in, nbit, bit_pos);
            if (!rank_in) // target found
            {
                pos = bit_pos + (nb * bm::set_block_size * 32);
                return true;
            }
        }
        else
        {
            // TODO: better next block search
            if (no_more_blocks)
                break;
        }
        nbit ^= nbit; // zero start bit after first scanned block
    } // for nb
    
    return ret;
}
 
//---------------------------------------------------------------------
 
template<class Alloc>
bool bvector<Alloc>::select(size_type rank_in, size_type& pos,
                            const rs_index_type&  rs_idx) const BMNOEXCEPT
{
    bool ret = false;
    
    if (!rank_in ||
        !blockman_.is_init() ||
        (rs_idx.count() < rank_in))
        return ret;
    
    block_idx_type nb;
    bm::gap_word_t sub_range_from;
    bool found = rs_idx.find(&rank_in, &nb, &sub_range_from);
    if (!found)
        return found;
 
    unsigned i, j;
    bm::get_block_coord(nb, i, j);
    const bm::word_t* block = blockman_.get_block_ptr(i, j);
    BM_ASSERT(block);
    BM_ASSERT(rank_in <= rs_idx.count(nb));
 
    unsigned bit_pos = 0;
    if (block == FULL_BLOCK_FAKE_ADDR)
    {
        BM_ASSERT(rank_in <= bm::gap_max_bits);
        bit_pos = sub_range_from + unsigned(rank_in) - 1;
    }
    else
    {
        rank_in = bm::block_find_rank(block, rank_in, sub_range_from, bit_pos);
        BM_ASSERT(rank_in == 0);
    }
    pos = bit_pos + (nb * bm::set_block_size * 32);
    return true;
}
 
//---------------------------------------------------------------------
 
template<class Alloc> 
typename bvector<Alloc>::size_type 
bvector<Alloc>::check_or_next(size_type prev) const BMNOEXCEPT
{
    if (!blockman_.is_init())
        return 0;
    
    // calculate logical block number
    block_idx_type nb = (prev >>  bm::set_block_shift);
    unsigned i, j;
    bm::get_block_coord(nb, i, j);
    const bm::word_t* block = blockman_.get_block_ptr(i, j);
 
    if (block)
    {
        unsigned block_pos;
        bool found = false;
        // calculate word number in block and bit
        unsigned nbit = unsigned(prev & bm::set_block_mask);
        if (BM_IS_GAP(block))
        {
            if (bm::gap_block_find(BMGAP_PTR(block), nbit, &block_pos))
            {
                prev = (size_type(nb) * bm::gap_max_bits) + block_pos;
                return prev;
            }
        }
        else
        {
            if (block == FULL_BLOCK_FAKE_ADDR)
                return prev;
            found = bm::bit_block_find(block, nbit, &block_pos);
            if (found)
            {
                prev = (size_type(nb) * bm::gap_max_bits) + block_pos;
                return prev;
            }
        }
    }
    ++j;
    block_idx_type top_blocks = blockman_.top_block_size();
    for (; i < top_blocks; ++i)
    {
        const bm::word_t* const* blk_blk = blockman_.get_topblock(i);
        if (blk_blk)
        {
            if ((bm::word_t*)blk_blk == FULL_BLOCK_FAKE_ADDR)
                blk_blk = FULL_SUB_BLOCK_REAL_ADDR;
 
            for (; j < bm::set_sub_array_size; ++j)
            {
                const bm::word_t* blk = blk_blk[j];
                if (blk)
                {
                    bool found;
                    unsigned block_pos;
                    if (blk == FULL_BLOCK_FAKE_ADDR)
                    {
                        found = true; block_pos = 0;
                    }
                    else
                    {
                        bool is_gap = BM_IS_GAP(blk);
                        found = (is_gap) ? bm::gap_find_first(BMGAP_PTR(blk), &block_pos)
                                         : bm::bit_find_first(blk, &block_pos);
                    }
                    if (found)
                    {
                        size_type base_idx = size_type(i) * bm::bits_in_array;
                        base_idx += j * bm::gap_max_bits;
                        prev = base_idx + block_pos;
                        return prev;
                    }
                }
            } // for j
        }