Re: [boost] [dynamic_bitset] intersects

Subject: Re: [boost] [dynamic_bitset] intersects
From: vicente.botet (vicente.botet_at_[hidden])
Date: 2009-03-08 15:02:33

----- Original Message ----- 
From: "Joachim Faulhaber" <afojgo_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Sunday, March 08, 2009 7:18 PM
Subject: Re: [boost] [dynamic_bitset] intersects

> 
> 2009/3/7 vicente.botet <vicente.botet_at_[hidden]>:
>> ----- Original Message -----
>> From: "Steven Watanabe" <watanabesj_at_[hidden]>
>>> 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