bm.h

ncbi源码

    {
        bit_or(bvect);
    }

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

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

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

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

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

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

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

    bvector<A, MS> operator~() const
    {
        return bvector<A, MS>(*this).invert();
    }


    /*!
        \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<A, MS>& set(bm::id_t n, bool val = true)
    {
        // calculate logical block number
        unsigned nblock = unsigned(n >>  bm::set_block_shift); 

        int block_type;

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

        if (!blk) return *this;

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

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

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

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

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

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

    /*!
       \brief Sets every bit in this bitset to 1.
       \return *this
    */
    bvector<A, MS>& set()
    {
        blockman_.set_all_one();
        set(bm::id_max, false);
        BMCOUNT_SET(id_max);
        return *this;
    }


    /*!
        \brief Sets all bits in the specified closed interval [left,right]
        
        \param left  - interval start
        \param right - interval end (closed interval)
        \param value - value to set interval in
        
        \return *this
    */
    bvector<A, MS>& set_range(bm::id_t left,
                              bm::id_t right,
                              bool     value = true)
    {
        if (right < left)
        {
            return set_range(right, left, value);
        }

        BMCOUNT_VALID(false)
        BM_SET_MMX_GUARD

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

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

        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);

        // Set bits in the starting block

        bm::gap_word_t tmp_gap_blk[5] = {0,};
        gap_init_range_block(tmp_gap_blk, 
                             nbit_left, r, value, bm::bits_in_block);

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

        if (nblock_left == nblock_right)  // in one block
            return *this;

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

                bool is_gap = BM_IS_GAP(blockman_, block, nb);

                if (is_gap)
                    A::free_gap_block(BMGAP_PTR(block),blockman_.glen());
                else
                    A::free_bit_block(block);

                blockman_.set_block(nb, FULL_BLOCK_ADDR);
                blockman_.set_block_bit(nb);
                
            } // for
        }
        else // value == 0
        {
            for (unsigned nb = nblock_left+1; nb < nb_to; ++nb)
            {
                block = blockman_.get_block(nb);
                if (block == 0)  // nothing to do
                    continue;

                bool is_gap = BM_IS_GAP(blockman_, block, nb);

                if (is_gap)
                    A::free_gap_block(BMGAP_PTR(block),blockman_.glen());
                else
                    A::free_bit_block(block);

                blockman_.set_block(nb, 0);
                blockman_.set_block_bit(nb);

            } // for
        } // if value else 

        if (nb_to > nblock_right)
            return *this;

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

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

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

        return *this;
    }


    /*!
       \brief Sets bit n.
       \param n - index of the bit to be set. 
    */
    void set_bit(bm::id_t n)
    {
        set(n, true);
    }
    
    /*! Function erturns insert iterator for this bitvector */
    insert_iterator inserter()
    {
        return insert_iterator(*this);
    }


    /*!
       \brief Clears bit n.
       \param n - bit's index to be cleaned.
    */
    void clear_bit(bm::id_t n)
    {
        set(n, false);
    }


    /*!
       \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 = false)
    {
        blockman_.set_all_zero(free_mem);
        BMCOUNT_SET(0);
    }

    /*!
       \brief Clears every bit in the bitvector.
       \return *this;
    */
    bvector<A, MS>& reset()
    {
        clear();
        return *this;
    }


    /*!
       \brief Returns count of bits which are 1.
       \return Total number of bits ON. 
    */
    bm::id_t count() const
    {
    #ifdef BMCOUNTOPT
        if (count_is_valid_) return count_;
    #endif
        bm::word_t*** blk_root = blockman_.get_rootblock();
        typename blocks_manager::block_count_func func(blockman_);
        for_each_nzblock(blk_root, blockman_.top_block_size(), 
                                   bm::set_array_size, func);

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

    /*! \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.
    */
    unsigned count_blocks(unsigned* arr) const
    {
        bm::word_t*** blk_root = blockman_.get_rootblock();
        typename blocks_manager::block_count_arr_func func(blockman_, &(arr[0]));
        for_each_nzblock(blk_root, blockman_.top_block_size(), 
                                   bm::set_array_size, func);
        return func.last_block();
    }

    /*!
       \brief Returns count of 1 bits in the given diapason.
       \param left - index of first bit start counting from
       \param right - index of last bit 
       \param block_count_arr - optional parameter (bitcount by bvector blocks)
              calculated by count_blocks method. Used to improve performance of
              wide range searches
       \return Total number of bits ON. 
    */
    bm::id_t count_range(bm::id_t left, 
                         bm::id_t right, 
                         unsigned* block_count_arr=0) const
    {
        assert(left <= right);

        unsigned count = 0;

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

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

        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::block_count_func func(blockman_);

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

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

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

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

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

        return count;
    }


    bm::id_t recalc_count()
    {
        BMCOUNT_VALID(false)
        return count();
    }
    
    /*!
        Disables count cache. Next call to count() or recalc_count()
        restores count caching.
        
        @note Works only if BMCOUNTOPT enabled(defined). 
        Othewise does nothing.
    */
    void forget_count()
    {
        BMCOUNT_VALID(false)    
    }