----- Original Message ----- From: "Steven Watanabe" <watanabesj@gmail.com> To: <boost@lists.boost.org> Sent: Saturday, March 07, 2009 4:13 PM Subject: Re: [boost] [dynamic_bitset] intersects

AMDG

vicente.botet wrote:

...

I want to know if two dynamic_bitsets have an element in common. Is there an efficient way to get this?

dynamic_bitset<> bs1, bs2;

intersetcs(bs1, bs2)?

It's a member function. bs1.intersects(bs2);

Thanks for the info. I was unable to find it on the reference. I see this on the section Changes from Boost 1.31.0 "Several member functions (empty(), find_first() , find_next(), get_allocator(), intersects() , max_size() ) have been added. ". I've added a ticket to tract it https://svn.boost.org/trac/boost/ticket/2837 Vicente

----- Original Message ----- From: "Joachim Faulhaber" <afojgo@googlemail.com> To: <boost@lists.boost.org> Sent: Sunday, March 08, 2009 7:18 PM Subject: Re: [boost] [dynamic_bitset] intersects

2009/3/7 vicente.botet <vicente.botet@wanadoo.fr>:

...

----- Original Message ----- From: "Steven Watanabe" <watanabesj@gmail.com>

...

vicente.botet wrote:

...

I want to know if two dynamic_bitsets have an element in common. Is there an efficient way to get this?

dynamic_bitset<> bs1, bs2;

intersetcs(bs1, bs2)?

It's a member function. bs1.intersects(bs2);

I think that the assumption of Vicente ...

dynamic_bitset<> bs1, bs2; // ... expecting ... intersetcs(bs1, bs2)?

is kind of justified, because function intersects could be implemented not only by memberfunctions of dynamic_bitset but even with non member functions, in more than one way,

e.g. bool intersects(const dynamic_bitset<Block, Allocator>& a, const dynamic_bitset<Block, Allocator>& b) // nonmembers & and member empty() { return !(a & b).empty(); }

This is a valid implementation but it is not efficient because it needs to make a new bitset with the intersection.

this would be consistent with the coding standard to keep class interfaces minimal and to implement namespace global functions on the bases of class memberfunctions where ever this is possible.

I agree.

I've stumbled over this, because I took the pleasure to refactor the interfaces of my libraries class interfaces according to that rule recently and made the experience that this can reduce class interfaces rather drastically up to a point that hurts ;)

Yes, separating generic algorithms is always good thing.

Seeing this example in an established boost library raises the question how serious this rule in taken in the boost community or what the special reason might be to implement

intersects

as member function here.

In my libraries I use to apply this, the single problem is in which namespace you put the free function. If you put it inthe boost namespace, this free functions must be able to be partialy specialized, so they can be used for dynamic_bitset std::bitset or other classes. I use the following workarround waiting for C++0x partial specialization on functions: namespace result_of { template <typename A, typename B> struct intersects { typedef bool type; }; } namespace partial_specialization_workaround { template <typename A, typename B> struct intersects { static typename result_of::intersects<A,B>::type apply( const A& a, const B& b ) { return a.intersects(b); } }; } template <typename A, typename B> typename result_of::intersects<A,B>::type intersects(const A& a, const B& b) { return partial_specialization_workaround::intersects<A,B>::apply(act); } The default behavior could call to the member function with the same name and return bool in this case, or default could also do return !(a & b).empty(); If the default is not enoug efficient for dynamic_bitset the dynamic_bitset library could specialize it as namespace partial_specialization_workaround { template <typename A_Block, typename A_Allocator, typename B_Block, typename A_Allocator> struct intersects { static typename result_of::intersects<A,B>::type apply( const boost::dynamic_bitset<A_Block, A_Allocator>& a, const boost::dynamic_bitset<B_Block, B_Allocator>& b ) { return a.intersects(b); } }; } A more efficient generic algorithm would needs a function to iterate on all the blocks (read only of course) const Block* get_block(std::size_t i) const; std::size blocks = std::min(a.num_blocks(), b.num_blocks()); for (std::size_t i = 0; i < blocks; ++i) { if (a.get_block(i) & b.get_block(i)) return true; } return false; Best regards, Vicente

2009/3/8 Steven Watanabe <watanabesj@gmail.com>:

AMDG

Joachim Faulhaber wrote:

...

I think that the assumption of Vicente ...

dynamic_bitset<> bs1, bs2; // ... expecting ... intersetcs(bs1, bs2)?

is kind of justified, because function intersects could be implemented not only by memberfunctions of dynamic_bitset but even with non member functions, in more than one way,

e.g. bool intersects(const dynamic_bitset<Block, Allocator>& a,               const dynamic_bitset<Block, Allocator>& b) // nonmembers & and member empty() { return !(a & b).empty(); }

this would be consistent with the coding standard to keep class interfaces minimal and to implement namespace global functions on the bases of class memberfunctions where ever this is possible.

This would be less efficient because of the temporary.

Thank you both (this also refers to Vicente since he had the same argument). Yes, but this is not the only way to implement the function. I think this implementation is as efficient as the member function: template <typename Block, typename Allocator> bool intersects(const dynamic_bitset<Block, Allocator>& a, const dynamic_bitset<Block, Allocator>& b) { typedef typename dynamic_bitset<Block, Allocator>::size_type size_type; size_type common_blocks = a.num_blocks() < b.num_blocks() ? a.num_blocks() : b.num_blocks(); for(size_type i = 0; i < common_blocks; ++i) { if(a.test(i) & b.test(i)) return true; } return false; } best regards, Joachim