bm.h

ncbi源码

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

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

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


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

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

            typename bm::bvector<A, MS>::blocks_manager* bman
                = &this->bv_->blockman_;
            bm::word_t*** blk_root = bman->blocks_root();

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

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

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


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

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

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

            } // for i

            this->invalidate();
        }

        void go_up()
        {
            // Current block search.
            ++this->position_;

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

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

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

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

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

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

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

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

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

            default:
                assert(0);

            } // switch


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

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

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

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

                    if (BM_IS_GAP((this->bv_->blockman_), this->block_, 
                                  this->block_idx_))
                    {
                        this->block_type_ = 1;
                        if (search_in_gapblock())
                        {
                            return;
                        }
                    }
                    else
                    {
                        this->block_type_ = 0;
                        if (search_in_bitblock())
                        {
                            return;
                        }
                    }

            
                } // for j

            } // for i


            this->invalidate();
        }


    private:
        bool search_in_bitblock()
        {
            assert(this->block_type_ == 0);

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

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

            do
            {
                register bm::word_t w = *this->bdescr_.bit_.ptr;

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

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

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

            return false;
        }

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

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

            ++this->bdescr_.gap_.ptr;

            do
            {
                register unsigned val = *this->bdescr_.gap_.ptr;

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

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

                bitval ^= 1;
                ++this->bdescr_.gap_.ptr;

            } while (1);

            return false;
        }

    };
    
    /*!
        @brief Constant input 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 bvector
    */
    class counted_enumerator : public enumerator
    {
    public:
#ifndef BM_NO_STL
        typedef std::input_iterator_tag  iterator_category;
#endif
        counted_enumerator() : bit_count_(0){}
        
        counted_enumerator(const enumerator& en)
        : enumerator(en)
        {
            if (this->valid())
                bit_count_ = 1;
        }
        
        counted_enumerator& operator=(const enumerator& en)
        {
            enumerator* me = this;
            *me = en;
            if (this->valid())
                bit_count_ = 1;
            return *this;
        }
        
        counted_enumerator& operator++()
        {
            this->go_up();
            if (this->valid())
                ++bit_count_;
            return *this;
        }

        counted_enumerator operator++(int)
        {
            counted_enumerator tmp(*this);
            this->go_up();
            if (this->valid())
                ++bit_count_;
            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 
        */
        bm::id_t count() const { return bit_count_; }
        
    private:
        bm::id_t   bit_count_;
    };

    friend class iterator_base;
    friend class enumerator;

public:

#ifdef BMCOUNTOPT
    bvector(strategy strat = BM_BIT, 
            const gap_word_t* glevel_len=bm::gap_len_table<true>::_len,
            bm::id_t max_bits = 0) 
    : count_(0),
      count_is_valid_(true),
      blockman_(glevel_len, max_bits),
      new_blocks_strat_(strat)
    {}

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

#else
    /*!
        \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. 
                            (Put bm::gap_len_table_min<true>::_len for GAP memory saving mode)
        \param max_bits - maximum number of bits addressable by bvector, 0 means "no limits" (recommended)
        \sa bm::gap_len_table bm::gap_len_table_min
    */
    bvector(strategy strat = BM_BIT,
            const gap_word_t* glevel_len=bm::gap_len_table<true>::_len,
            bm::id_t max_bits = 0) 
    : blockman_(glevel_len, max_bits),
      new_blocks_strat_(strat)   
    {}

    bvector(const bvector<A, MS>& bvect)
        :  blockman_(bvect.blockman_),
           new_blocks_strat_(bvect.new_blocks_strat_)
    {}

#endif

    bvector& operator = (const bvector<A, MS>& bvect)
    {
        if (bvect.blockman_.top_block_size() != blockman_.top_block_size())
        {
            blockman_.set_top_block_size(bvect.blockman_.top_block_size());
        }
        else
        {
            clear(false);
        }
        bit_or(bvect);
        return *this;
    }

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


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

    void operator &= (const bvector<A, MS>& bvect)
    {
        bit_and(bvect);
    }

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

    void operator |= (const bvector<A, MS>& bvect)