MRMesh/MRBitSet.h

Go to the documentation of this file.

#pragma once
 
#include "MRMeshFwd.h"
#include "MRId.h"
#include "MRphmap.h"
#include "MRVector.h"
#define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS
#pragma warning(push)
#pragma warning(disable: 4643) //Forward declaring in namespace std is not permitted by the C++ Standard.
#include <boost/dynamic_bitset.hpp>
#pragma warning(pop)
#include <iterator>
#include <functional>
 
namespace MR
{
 
class BitSet : public boost::dynamic_bitset<std::uint64_t>
{
public:
    using base = boost::dynamic_bitset<std::uint64_t>;
    using base::base;
    using IndexType = size_t;
 
    explicit BitSet( size_t numBits, bool fillValue ) { resize( numBits, fillValue ); }
 
    // all bits after size() we silently consider as not-set
    [[nodiscard]] bool test( IndexType n ) const { return n < size() && base::test( n ); }
    [[nodiscard]] bool test_set( IndexType n, bool val = true ) { return ( val || n < size() ) ? base::test_set( n, val ) : false; }
    BitSet & set( IndexType n, size_type len, bool val ) { base::set( n, len, val ); return * this; }
    BitSet & set( IndexType n, bool val = true ) { base::set( n, val ); return * this; }
    BitSet & set() { base::set(); return * this; }
    BitSet & reset( IndexType n, size_type len ) { if ( n < size() ) base::reset( n, len ); return * this; }
    BitSet & reset( IndexType n ) { if ( n < size() ) base::reset( n ); return * this; }
    BitSet & reset() { base::reset(); return * this; }
    BitSet & flip( IndexType n, size_type len ) { base::flip( n, len ); return * this; }
    BitSet & flip( IndexType n ) { base::flip( n ); return * this; }
    BitSet & flip() { base::flip(); return * this; }
 
    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 IndexType find_last() const;
    [[nodiscard]] MRMESH_API size_t nthSetBit( size_t n ) 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() }; }
 
    // Normally those are inherited from `boost::dynamic_bitset`, but MRBind currently chokes on it, so we provide those manually.
    #if defined(MR_PARSING_FOR_PB11_BINDINGS) || defined(MR_COMPILING_PB11_BINDINGS)
    std::size_t size() const { return dynamic_bitset::size(); }
    std::size_t count() const { return dynamic_bitset::count(); }
    void resize( std::size_t num_bits, bool value = false ) { dynamic_bitset::resize( num_bits, value ); }
    void clear() { dynamic_bitset::clear(); }
    void push_back( bool bit ) { dynamic_bitset::push_back( bit ); }
    void pop_back() { dynamic_bitset::pop_back(); }
    #endif
};
 
template <typename T>
class TaggedBitSet : public BitSet
{
    using base = BitSet;
public:
    using base::base;
    using IndexType = Id<T>;
 
    TaggedBitSet & set( IndexType n, size_type len, bool val ) { base::set( n, len, val ); return * this; }
    TaggedBitSet & set( IndexType n, bool val = true ) { base::set( n, val ); return * this; }
    TaggedBitSet & set() { base::set(); return * this; }
    TaggedBitSet & reset( IndexType n, size_type len ) { base::reset( n, len ); return * this; }
    TaggedBitSet & reset( IndexType n ) { base::reset( n ); return * this; }
    TaggedBitSet & reset() { base::reset(); return * this; }
    TaggedBitSet & flip( IndexType n, size_type len ) { base::flip( n, len ); return * this; }
    TaggedBitSet & flip( IndexType n ) { base::flip( n ); return * this; }
    TaggedBitSet & 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 ); }
 
    #ifndef MR_PARSING_FOR_PB11_BINDINGS // Disable for python bindings, because MRBind chokes on `boost::dynamic_bitset::reference`.
    [[nodiscard]] reference operator[]( IndexType pos ) { return base::operator[]( pos ); }
    #endif
    [[nodiscard]] bool operator[]( IndexType pos ) const { return base::operator[]( pos ); }
 
    [[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 nthSetBit( size_t n ) const { return IndexType( base::nthSetBit( n ) ); }
 
    TaggedBitSet & operator &= ( const TaggedBitSet & b ) { base::operator &= ( b ); return * this; }
    TaggedBitSet & operator |= ( const TaggedBitSet & b ) { base::operator |= ( b ); return * this; }
    TaggedBitSet & operator ^= ( const TaggedBitSet & b ) { base::operator ^= ( b ); return * this; }
    TaggedBitSet & operator -= ( const TaggedBitSet & b ) { base::operator -= ( b ); return * this; }
    TaggedBitSet & subtract( const TaggedBitSet & b, int bShiftInBlocks ) { base::subtract( b, bShiftInBlocks ); return * this; }
 
    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]] TaggedBitSet getMapping( const M & map ) const;
    [[nodiscard]] TaggedBitSet getMapping( const Vector<IndexType, IndexType> & map ) const
        { return getMapping( [&map]( IndexType i ) { return map[i]; } ); }
    [[nodiscard]] TaggedBitSet getMapping( const BMap<IndexType, IndexType> & map ) const
        { return getMapping( [&map]( IndexType i ) { return map.b[i]; }, map.tsize ); }
    [[nodiscard]] TaggedBitSet getMapping( const HashMap<IndexType, IndexType> & map ) const
        { return getMapping( [&map]( IndexType i ) { return getAt( map, i ); } ); }
    template <typename M>
    [[nodiscard]] TaggedBitSet getMapping( const M & map, size_t resSize ) const;
    [[nodiscard]] TaggedBitSet getMapping( const Vector<IndexType, IndexType> & map, size_t resSize ) const
        { return getMapping( [&map]( IndexType i ) { return map[i]; }, resSize ); }
    [[nodiscard]] TaggedBitSet 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]] MRMESH_API bool operator == ( const BitSet & a, const BitSet & b );
template <typename T>
[[nodiscard]] inline bool operator == ( const TaggedBitSet<T> & a, const TaggedBitSet<T> & b )
    { return static_cast<const BitSet &>( a ) == static_cast<const BitSet &>( b ); }
template <typename T, typename U>
void operator == ( const TaggedBitSet<T> & a, const TaggedBitSet<U> & b ) = delete;
 
template <typename T>
[[nodiscard]] inline std::function<bool( Id<T> )> makePredicate( const TaggedBitSet<T> * bitset )
{
    std::function<bool( Id<T> )> res;
    if ( bitset )
        res = [bitset]( Id<T> id ) { return bitset->test( id ); };
    return res;
}
 
template <typename T>
[[nodiscard]] inline std::function<bool( Id<T> )> makePredicate( const TaggedBitSet<T> & bitset )
    { return makePredicate( &bitset ); }
 
template <typename T>
[[nodiscard]] inline bool contains( const TaggedBitSet<T> * bitset, Id<T> id )
{
    return id.valid() && ( !bitset || bitset->test( id ) );
}
 
template <typename T>
[[nodiscard]] inline bool contains( const TaggedBitSet<T> & bitset, Id<T> id )
{
    return id.valid() && bitset.test( id );
}
 
template <typename T>
class 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         = const 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_; }
 
private:
    const T * bitset_ = nullptr;
    IndexType index_ = IndexType( ~size_t( 0 ) );
};
 
template <typename T>
[[nodiscard]] inline bool operator ==( const SetBitIteratorT<T> & a, const SetBitIteratorT<T> & b )
    { return *a == *b; }
 
template <typename T>
[[nodiscard]] inline bool operator !=( const SetBitIteratorT<T> & a, const SetBitIteratorT<T> & b )
    { return *a != *b; }
 
 
[[nodiscard]] inline auto begin( const BitSet & a )
    { return SetBitIteratorT<BitSet>(a); }
[[nodiscard]] inline auto end( const BitSet & )
    { return SetBitIteratorT<BitSet>(); }
 
template <typename T>
[[nodiscard]] inline auto begin( const TaggedBitSet<T> & a )
    { return SetBitIteratorT<TaggedBitSet<T>>(a); }
template <typename T>
[[nodiscard]] inline auto end( const TaggedBitSet<T> & )
    { return SetBitIteratorT<TaggedBitSet<T>>(); }
 
template <typename T>
[[nodiscard]] Vector<int, Id<T>> makeVectorWithSeqNums( const TaggedBitSet<T> & bs )
{
    Vector<int, Id<T>> res( bs.size(), -1 );
    int n = 0;
    for ( auto v : bs )
        res[v] = n++;
    return res;
}
 
template <typename T>
[[nodiscard]] HashMap<Id<T>, int> makeHashMapWithSeqNums( const TaggedBitSet<T> & bs )
{
    HashMap<Id<T>, int> res;
    int n = 0;
    for ( auto v : bs )
        res[v] = n++;
    return res;
}
 
template <typename T>
template <typename M>
[[nodiscard]] TaggedBitSet<T> TaggedBitSet<T>::getMapping( const M & map ) const
{
    TaggedBitSet<T> res;
    for ( auto b : *this )
        if ( auto mapped = map( b ) )
            res.autoResizeSet( mapped );
    return res;
}
 
template <typename T>
template <typename M>
[[nodiscard]] TaggedBitSet<T> TaggedBitSet<T>::getMapping( const M & map, size_t resSize ) const
{
    TaggedBitSet<T> 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; }
 
template <typename T> [[nodiscard]] inline TaggedBitSet<T> operator & ( const TaggedBitSet<T> & a, const TaggedBitSet<T> & b ) { auto res{ a }; res &= b; return res; }
template <typename T> [[nodiscard]] inline TaggedBitSet<T> operator | ( const TaggedBitSet<T> & a, const TaggedBitSet<T> & b ) { auto res{ a }; res |= b; return res; }
template <typename T> [[nodiscard]] inline TaggedBitSet<T> operator ^ ( const TaggedBitSet<T> & a, const TaggedBitSet<T> & b ) { auto res{ a }; res ^= b; return res; }
template <typename T> [[nodiscard]] inline TaggedBitSet<T> operator - ( const TaggedBitSet<T> & a, const TaggedBitSet<T> & b ) { auto res{ a }; res -= b; return res; }
 
 
} // namespace MR