MRBitSet.h

Go to the documentation of this file.

#pragma once
 
#include "MRMeshFwd.h"
#include "MRId.h"
#include "MRphmap.h"
#include "MRVector.h"
#include "MRPch/MRBindingMacros.h"
#include <functional>
#include <iosfwd>
#include <iterator>
 
namespace MR
{


template <typename T>
class MR_BIND_IGNORE_PY SetBitIteratorT
{
public:
    using IndexType = typename T::IndexType;
 
    using iterator_category = std::forward_iterator_tag;
    using value_type        = IndexType;
    using difference_type   = std::ptrdiff_t;
    using reference         = IndexType; 
    using pointer           = const IndexType *;

    SetBitIteratorT() = default;

    SetBitIteratorT( const T & bitset )
        : bitset_( &bitset ), index_( bitset.find_first() )
    {
    }
 
    SetBitIteratorT & operator++()
    {
        index_ = bitset_->find_next( index_ );
        return * this;
    }
 
    [[nodiscard]] SetBitIteratorT operator++( int )
    {
        SetBitIteratorT ret = *this;
        operator++();
        return ret;
    }
 
    [[nodiscard]] const T * bitset() const { return bitset_; }
    [[nodiscard]] reference operator *() const { return index_; }
 
    [[nodiscard]] friend bool operator ==( const SetBitIteratorT<T> & a, const SetBitIteratorT<T> & b ) { return *a == *b; }
 
private:
    const T * bitset_ = nullptr;
    IndexType index_ = IndexType( ~size_t( 0 ) );
};

class BitSet
{
public:
    using block_type = Uint64;
    inline static constexpr size_t bits_per_block = sizeof( block_type ) * 8;
    inline static constexpr size_t npos = (size_t)-1;
 
    using size_type = size_t;
    using IndexType = size_t;

    BitSet() noexcept = default;

    explicit BitSet( size_t numBits, bool fillValue = false ) { resize( numBits, fillValue ); }

    static BitSet fromBlocks( std::vector<block_type> && blocks )
    {
        BitSet res;
        res.blocks_ = std::move( blocks );
        res.numBits_ = res.blocks_.size() * bits_per_block;
        return res;
    }
 
    void reserve( size_type numBits ) { blocks_.reserve( calcNumBlocks_( numBits ) ); }
    MRMESH_API void resize( size_type numBits, bool fillValue = false );
    void clear() { numBits_ = 0; blocks_.clear(); }
    void shrink_to_fit() { blocks_.shrink_to_fit(); }
 
    [[nodiscard]] bool empty() const noexcept { return numBits_ == 0; }
    [[nodiscard]] size_type size() const noexcept { return numBits_; }
    [[nodiscard]] size_type num_blocks() const noexcept { return blocks_.size(); }
    [[nodiscard]] size_type capacity() const noexcept { return blocks_.capacity() * bits_per_block; }
 
    [[nodiscard]] bool uncheckedTest( IndexType n ) const { assert( n < size() ); return blocks_[blockIndex_( n )] & bitMask_( n ); }
    [[nodiscard]] bool uncheckedTestSet( IndexType n, bool val = true ) { assert( n < size() ); bool b = uncheckedTest( n ); if ( b != val ) set( n, val ); return b; }

    [[nodiscard]] bool test( IndexType n ) const { return n < size() ? uncheckedTest( n ) : false; } 
    [[nodiscard]] bool test_set( IndexType n, bool val = true ) { return ( val || n < size() ) ? uncheckedTestSet( n, val ) : false; }
 
    MRMESH_API BitSet & set( IndexType n, size_type len, bool val );
    BitSet & set( IndexType n, bool val ) { return val ? set( n ) : reset( n ); } 
    BitSet & set( IndexType n ) { assert( n < size() ); blocks_[blockIndex_( n )] |= bitMask_( n ); return * this; }
    MRMESH_API BitSet & set();
 
    MRMESH_API BitSet & reset( IndexType n, size_type len );
    BitSet & reset( IndexType n ) { if ( n < size() ) blocks_[blockIndex_( n )] &= ~bitMask_( n ); return * this; }
    MRMESH_API BitSet & reset();
 
    MRMESH_API BitSet & flip( IndexType n, size_type len );
    BitSet & flip( IndexType n ) { assert( n < size() ); blocks_[blockIndex_( n )] ^= bitMask_( n ); return * this; }
    MRMESH_API BitSet & flip();

    MRMESH_API void reverse();

    void push_back( bool val ) { auto n = numBits_++; if ( bitIndex_( n ) == 0 ) blocks_.push_back( block_type{} ); set( n, val ); }

    void pop_back() { assert( numBits_ > 0 ); { if ( bitIndex_( numBits_ ) == 1 ) blocks_.pop_back(); else reset( numBits_ - 1 ); } --numBits_; }

    [[nodiscard]] const auto & bits() const { return blocks_; }
 
    MRMESH_API BitSet & operator &= ( const BitSet & b );
    MRMESH_API BitSet & operator |= ( const BitSet & b );
    MRMESH_API BitSet & operator ^= ( const BitSet & b );
 
    MRMESH_API BitSet & operator -= ( const BitSet & b );
    MRMESH_API BitSet & subtract( const BitSet & b, int bShiftInBlocks );

    [[nodiscard]] MRMESH_API bool all() const;

    [[nodiscard]] MRMESH_API bool any() const;

    [[nodiscard]] bool none() const { return !any(); }

    [[nodiscard]] MRMESH_API size_type count() const noexcept;

    [[nodiscard]] IndexType find_first() const { return findSetBitAfter_( 0 ); }

    [[nodiscard]] IndexType find_next( IndexType n ) const { return findSetBitAfter_( n + 1 ); }

    [[nodiscard]] MRMESH_API IndexType find_last() const;

    [[nodiscard]] IndexType find_first_not_set() const { return findNonSetBitAfter_( 0 ); }

    [[nodiscard]] IndexType find_next_not_set( IndexType n ) const { return findNonSetBitAfter_( n + 1 ); }

    [[nodiscard]] MRMESH_API IndexType find_last_not_set() const;

    [[nodiscard]] MRMESH_API size_t nthSetBit( size_t n ) const;

    [[nodiscard]] MRMESH_API bool is_subset_of( const BitSet& a ) const;

    [[nodiscard]] MRMESH_API bool intersects( const BitSet & a ) const;

    void resizeWithReserve( size_t newSize )
    {
        auto reserved = capacity();
        if ( reserved > 0 && newSize > reserved )
        {
            while ( newSize > reserved )
                reserved <<= 1;
            reserve( reserved );
        }
        resize( newSize );
    }

    void autoResizeSet( size_t pos, size_type len, bool val = true )
    {
        if ( pos + len > size() )
            resizeWithReserve( pos + len );
        set( pos, len, val );
    }
    void autoResizeSet( size_t pos, bool val = true ) { autoResizeSet( pos, 1, val ); }

    [[nodiscard]] bool autoResizeTestSet( size_t pos, bool val = true )
    {
        bool const b = test( pos );
        if ( b != val )
            autoResizeSet( pos, val );
        return b;
    }

    [[nodiscard]] size_t heapBytes() const { return capacity() / 8; }

    [[nodiscard]] IndexType backId() const { assert( !empty() ); return IndexType{ size() - 1 }; }

    [[nodiscard]] static IndexType beginId() { return IndexType{ 0 }; }
    [[nodiscard]] IndexType endId() const { return IndexType{ size() }; }
 
private:
    [[nodiscard]] static size_type calcNumBlocks_( size_type numBits ) noexcept { return ( numBits + bits_per_block - 1 ) / bits_per_block; }

    [[nodiscard]] static size_type blockIndex_( IndexType n ) noexcept { return n / bits_per_block; }

    [[nodiscard]] static size_type bitIndex_( IndexType n ) noexcept { return n % bits_per_block; }

    [[nodiscard]] static block_type bitMask_( IndexType n ) noexcept { return block_type( 1 ) << bitIndex_( n ); }

    [[nodiscard]] static block_type bitMask_( IndexType firstBit, IndexType lastBit ) noexcept
    {
        return ( ( block_type( 1 ) << firstBit ) - 1 ) 
            ^ 
            ( lastBit == bits_per_block ? ~block_type{} : ( ( block_type( 1 ) << lastBit ) - 1 ) ); 
    }

    MRMESH_API void setUnusedBits_();

    MRMESH_API void resetUnusedBits_();

    template<class FullBlock, class PartialBlock>
    BitSet & rangeOp_( IndexType n, size_type len, FullBlock&&, PartialBlock&& );

    MRMESH_API IndexType findSetBitAfter_( IndexType n ) const;

    MRMESH_API IndexType findNonSetBitAfter_( IndexType n ) const;
 
    MRMESH_API friend std::ostream& operator<<( std::ostream& s, const BitSet & bs );
    MRMESH_API friend std::istream& operator>>( std::istream& s, BitSet & bs );
 
    [[nodiscard]] MR_BIND_IGNORE_PY friend auto begin( const BitSet & a ) { return SetBitIteratorT<BitSet>(a); }
    [[nodiscard]] MR_BIND_IGNORE_PY friend auto end( const BitSet & ) { return SetBitIteratorT<BitSet>(); }
 
private:
    std::vector<block_type> blocks_;
    size_type numBits_ = 0;
};

template <typename I>
class TypedBitSet : public BitSet
{
    using base = BitSet;
public:
    using base::base;
    using IndexType = I;

    explicit TypedBitSet( const BitSet & src ) : BitSet( src ) {}

    explicit TypedBitSet( BitSet && src ) : BitSet( std::move( src ) ) {}
 
    TypedBitSet & set( IndexType n, size_type len, bool val ) { base::set( n, len, val ); return * this; }
    TypedBitSet & set( IndexType n, bool val ) { base::set( n, val ); return * this; } 
    TypedBitSet & set( IndexType n ) { base::set( n ); return * this; }
    TypedBitSet & set() { base::set(); return * this; }
    TypedBitSet & reset( IndexType n, size_type len ) { base::reset( n, len ); return * this; }
    TypedBitSet & reset( IndexType n ) { base::reset( n ); return * this; }
    TypedBitSet & reset() { base::reset(); return * this; }
    TypedBitSet & flip( IndexType n, size_type len ) { base::flip( n, len ); return * this; }
    TypedBitSet & flip( IndexType n ) { base::flip( n ); return * this; }
    TypedBitSet & flip() { base::flip(); return * this; }
    [[nodiscard]] bool test( IndexType n ) const { return base::test( n ); }
    [[nodiscard]] bool test_set( IndexType n, bool val = true ) { return base::test_set( n, val ); }
 
    [[nodiscard]] IndexType find_first() const { return IndexType( base::find_first() ); }
    [[nodiscard]] IndexType find_next( IndexType pos ) const { return IndexType( base::find_next( pos ) ); }
    [[nodiscard]] IndexType find_last() const { return IndexType( base::find_last() ); }
    [[nodiscard]] IndexType find_first_not_set() const { return IndexType( base::find_first_not_set() ); }
    [[nodiscard]] IndexType find_next_not_set( IndexType pos ) const { return IndexType( base::find_next_not_set( pos ) ); }
    [[nodiscard]] IndexType find_last_not_set() const { return IndexType( base::find_last_not_set() ); }
    [[nodiscard]] IndexType nthSetBit( size_t n ) const { return IndexType( base::nthSetBit( n ) ); }
 
    TypedBitSet & operator &= ( const TypedBitSet & b ) { base::operator &= ( b ); return * this; }
    TypedBitSet & operator |= ( const TypedBitSet & b ) { base::operator |= ( b ); return * this; }
    TypedBitSet & operator ^= ( const TypedBitSet & b ) { base::operator ^= ( b ); return * this; }
    TypedBitSet & operator -= ( const TypedBitSet & b ) { base::operator -= ( b ); return * this; }
 
    [[nodiscard]] friend TypedBitSet operator & ( const TypedBitSet & a, const TypedBitSet & b ) { auto res{ a }; res &= b; return res; }
    [[nodiscard]] friend TypedBitSet operator | ( const TypedBitSet & a, const TypedBitSet & b ) { auto res{ a }; res |= b; return res; }
    [[nodiscard]] friend TypedBitSet operator ^ ( const TypedBitSet & a, const TypedBitSet & b ) { auto res{ a }; res ^= b; return res; }
    [[nodiscard]] friend TypedBitSet operator - ( const TypedBitSet & a, const TypedBitSet & b ) { auto res{ a }; res -= b; return res; }

    TypedBitSet & subtract( const TypedBitSet & b, int bShiftInBlocks ) { base::subtract( b, bShiftInBlocks ); return * this; }

    [[nodiscard]] bool is_subset_of( const TypedBitSet& a ) const { return base::is_subset_of( a ); }

    [[nodiscard]] bool intersects( const TypedBitSet & a ) const { return base::intersects( a ); }
 
    void autoResizeSet( IndexType pos, size_type len, bool val = true ) { base::autoResizeSet( pos, len, val ); }
    void autoResizeSet( IndexType pos, bool val = true ) { base::autoResizeSet( pos, val ); }
    [[nodiscard]] bool autoResizeTestSet( IndexType pos, bool val = true ) { return base::autoResizeTestSet( pos, val ); }

    template <typename M>
    [[nodiscard]] TypedBitSet getMapping( const M & map ) const;
    [[nodiscard]] TypedBitSet getMapping( const Vector<IndexType, IndexType> & map ) const
        { return getMapping( [&map]( IndexType i ) { return map[i]; } ); }
    [[nodiscard]] TypedBitSet getMapping( const BMap<IndexType, IndexType> & map ) const
        { return getMapping( [&map]( IndexType i ) { return map.b[i]; }, map.tsize ); }
    [[nodiscard]] TypedBitSet getMapping( const HashMap<IndexType, IndexType> & map ) const
        { return getMapping( [&map]( IndexType i ) { return getAt( map, i ); } ); }

    template <typename M>
    [[nodiscard]] TypedBitSet getMapping( const M & map, size_t resSize ) const;
    [[nodiscard]] TypedBitSet getMapping( const Vector<IndexType, IndexType> & map, size_t resSize ) const
        { return getMapping( [&map]( IndexType i ) { return map[i]; }, resSize ); }
    [[nodiscard]] TypedBitSet getMapping( const HashMap<IndexType, IndexType> & map, size_t resSize ) const
        { return getMapping( [&map]( IndexType i ) { return getAt( map, i ); }, resSize ); }

    [[nodiscard]] IndexType backId() const { assert( !empty() ); return IndexType{ size() - 1 }; }

    [[nodiscard]] static IndexType beginId() { return IndexType{ size_t( 0 ) }; }
    [[nodiscard]] IndexType endId() const { return IndexType{ size() }; }
 
    [[nodiscard]] MR_BIND_IGNORE_PY friend auto begin( const TypedBitSet & a ) { return SetBitIteratorT<TypedBitSet>(a); }
    [[nodiscard]] MR_BIND_IGNORE_PY friend auto end( const TypedBitSet & ) { return SetBitIteratorT<TypedBitSet>(); }
};
 

[[nodiscard]] inline size_t heapBytes( const BitSet& bs )
{
    return bs.heapBytes();
}

[[nodiscard]] MRMESH_API bool operator == ( const BitSet & a, const BitSet & b );
template <typename I>
[[nodiscard]] inline bool operator == ( const TypedBitSet<I> & a, const TypedBitSet<I> & b )
    { return static_cast<const BitSet &>( a ) == static_cast<const BitSet &>( b ); }

template <typename T, typename U>
void operator == ( const TypedBitSet<T> & a, const TypedBitSet<U> & b ) = delete;
 
template <typename I>
[[nodiscard]] inline std::function<bool( I )> makePredicate( const TypedBitSet<I> * bitset )
{
    std::function<bool( I )> res;
    if ( bitset )
        res = [bitset]( I id ) { return bitset->test( id ); };
    return res;
}
 
template <typename I>
[[nodiscard]] inline std::function<bool( I )> makePredicate( const TypedBitSet<I> & bitset )
    { return makePredicate( &bitset ); }
 
template <typename I>
[[nodiscard]] inline bool contains( const TypedBitSet<I> * bitset, I id )
{
    return id.valid() && ( !bitset || bitset->test( id ) );
}
 
template <typename I>
[[nodiscard]] inline bool contains( const TypedBitSet<I> & bitset, I id )
{
    return id.valid() && bitset.test( id );
}
 

template <typename I>
void fillVectorWithSeqNums( const TypedBitSet<I> & bs, Vector<int, I> & vec )
{
    int n = 0;
    for ( auto v : bs )
        vec[v] = n++;
}

template <typename I>
[[nodiscard]] Vector<int, I> makeVectorWithSeqNums( const TypedBitSet<I> & bs )
{
    Vector<int, I> res( bs.size(), -1 );
    fillVectorWithSeqNums( bs, res );
    return res;
}

template <typename I>
[[nodiscard]] HashMap<I, int> makeHashMapWithSeqNums( const TypedBitSet<I> & bs )
{
    HashMap<I, int> res;
    int n = 0;
    for ( auto v : bs )
        res[v] = n++;
    return res;
}
 
template <typename I>
template <typename M>
[[nodiscard]] TypedBitSet<I> TypedBitSet<I>::getMapping( const M & map ) const
{
    TypedBitSet<I> res;
    for ( auto b : *this )
        if ( auto mapped = map( b ) )
            res.autoResizeSet( mapped );
    return res;
}
 
template <typename I>
template <typename M>
[[nodiscard]] TypedBitSet<I> TypedBitSet<I>::getMapping( const M & map, size_t resSize ) const
{
    TypedBitSet<I> res;
    if ( !any() )
        return res;
    res.resize( resSize );
    for ( auto b : *this )
        if ( auto mapped = map( b ) )
            res.set( mapped );
    return res;
}
 
[[nodiscard]] inline BitSet operator & ( const BitSet & a, const BitSet & b ) { BitSet res{ a }; res &= b; return res; }
[[nodiscard]] inline BitSet operator | ( const BitSet & a, const BitSet & b ) { BitSet res{ a }; res |= b; return res; }
[[nodiscard]] inline BitSet operator ^ ( const BitSet & a, const BitSet & b ) { BitSet res{ a }; res ^= b; return res; }
[[nodiscard]] inline BitSet operator - ( const BitSet & a, const BitSet & b ) { BitSet res{ a }; res -= b; return res; }

 
}