Re: [Boost-users] bitsets in ITL

Subject: Re: [Boost-users] bitsets in ITL
From: Amir Gonnen (amirgonnen_at_[hidden])
Date: 2010-07-01 08:36:50

About the semantics of "size()":
On dynamic_bitset size is a member of the bitset object. i.e. "0000"
is has different size than "00000".
On interval_bitset there is some calculation based on cardinality and
bit counting.
In some use cases this can make a difference, not to mention
performance. I would definitely prefer the dynamic_bitset semantics.
Are there other semantic differences between interval_bitset and dynamic_bitset?

There are other functions missing. Here is my implementation for
bitset compatability functions, just as an example:

        //[large_bitset_compatability_functions	
        large_bitset(element_type size=0) : _size(size){}
        element_type size() const {return _size;}
        bool empty() const {return size()==0;}
        void clear()	 {_map.clear(); _size=0;}
        large_bitset& set(element_type i, bool val = true)
                {if (val) *this += i; else *this -= i; return *this;}	
        large_bitset& reset(element_type i){*this -= i; return *this;}		
        large_bitset& set(){*this += interval_type::rightopen(0,_size); return *this;}	
        large_bitset& reset(){*this -= interval_type::rightopen(0,_size);
return *this;}
        
        bool test(element_type i) const
        {
                interval_bitmap_type::const_iterator it = _map.find(i>>shift);
                if (it == _map.end()) return false;
                const bitset_type &bits = it->second;
                return bits.contains(i & mask);
        }

        bool any() const
        {
                for(typename interval_bitmap_type::const_iterator it_ = _map.begin();
                        it_ != _map.end(); ++it_)
                {			
                        bitset_type     bits = it_->second;
                        if (bits.any()) return true;
                }
                return false;
        }

        bool none() const {return !any();}

        void resize(element_type num_bits, bool v = false)
        {
                element_type old_size = _size;
                _size = num_bits;

                if (old_size > _size)		
                        _map.erase(interval_type::rightopen( (_size>>shift) + 1, _map.last() + 1));
                else if (old_size < _size)
                {
                        if (v)
                                *this += interval_type::rightopen(old_size, _size);
                        else
                                *this -= interval_type::rightopen(old_size, _size);
                }
        }
        //]

Amir

On Wed, Jun 30, 2010 at 11:49 PM, Joachim Faulhaber
<afojgo_at_[hidden]> wrote:
> Hi Amir,
>
> thank you for evaluating the Interval Template Library
>
> 2010/6/30 Amir Gonnen <amirgonnen_at_[hidden]>:
>> I'm evaluating ITL (Interval Template Library which was recently accepted to
>> boost) in order to represent sparse bitsets.
>> In the current implementation the large_bitset class is given as an example
>> with minimal functionality. Are there any plans to develop it into a fully
>> featured bitset and make it a part of boost?
>
> A more elaborated version of large_bitset can be found here.
>
> #include <boost/itl_xt/interval_bitset.hpp>
>
> itl_xt is the extended part of the itl, which contains code not yet
> intended for inclusion into boost.
> I think <boost/itl_xt/interval_bitset.hpp> is pretty well tested and
> should be suitable for production code. You have to download the
> extended itl-version itl_plus_3_2_0.zip or itl_plus_3_2_1.zip form the
> vault or from sourceforge, if you don't have the itl_xt part already:
>
> http://sourceforge.net/projects/itl/
>
>
>> It would be nice if it implemented the interface of dynamic_bitset, to ease
>> the migration between dynamic_bitset and large_bitset.
>
> During the review we have discussed a set of namespace global
> functions for all kinds of set implementations, that can be
> implemented for interval_bitsets or plain bitsets. The naming of those
> function refers to geometry standards:
>
> E.g.
> http://msdn.microsoft.com/en-us/library/bb933960.aspx
> http://postgis.refractions.net/documentation/manual-1.5/reference.html#Spatial_Relationships_Measurements
>
> Which gives the set implementation a broader context. There will be no
> bitset style implementation for interval_bitset, but you could write a
> wrapper yourself using private inheritence and the using-statement on
> member functions.
>
> Best regards,
> Joachim
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>