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@googlemail.com> wrote:
Hi Amir,
thank you for evaluating the Interval Template Library
2010/6/30 Amir Gonnen <amirgonnen@gmail.com>:
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#Spati...
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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users