Quantcast

[dynamic_bitset] Comparison operators without assertions

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
26 messages Options
12
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
Hi all.

Looking through boost::dynamic_bitset code, I found a interesting
inconsistency between its operator== and operator<. Namely, the first
works well with bitsets of different size, while the second triggers
an assertion:

    boost::dynamic_bitset<> a(std::string("111")),
                            b(std::string("1110"));
    a == b; // false
    a < b;  // Assertion `a.size() == b.size()' failed.

This means that we cannot reliably use dynamic bitset within ordered
containers like std::set or std::map.

Since the standard library has distinct concepts of equality and
equivalence (see [1]), it's fine to have different comparison
behaviors in dynamic_bitset. However, as far as I can judge,
equivalence is a metaphysically broader concept than equality, we
shouldn't restrict it to bitsets of the same size only.

So, the questions:

1. May I remove that assertion?
   (It won't be a breaking change, after all).

2. How about doing the same thing to bitwise operators, too? Instead
   of throwing an assertion if sizes don't match, it may be worth to
   generalize the operators definitions. I can see several possible
   schemes, but not all of them are consistent enough.

3. Shouldn't BOOST_ASSERT be used instead of the one from assert.h?

——— Pavel K.

[1]: http://en.cppreference.com/w/cpp/concept/EqualityComparable

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
On 4/27/2017 1:02 PM, Pavel Kretov via Boost wrote:

> Hi all.
>
> Looking through boost::dynamic_bitset code, I found a interesting
> inconsistency between its operator== and operator<. Namely, the first
> works well with bitsets of different size, while the second triggers
> an assertion:
>
>      boost::dynamic_bitset<> a(std::string("111")),
>                              b(std::string("1110"));
>      a == b; // false
>      a < b;  // Assertion `a.size() == b.size()' failed.
>
> This means that we cannot reliably use dynamic bitset within ordered
> containers like std::set or std::map.
>
> Since the standard library has distinct concepts of equality and
> equivalence (see [1]), it's fine to have different comparison
> behaviors in dynamic_bitset. However, as far as I can judge,
> equivalence is a metaphysically broader concept than equality, we
> shouldn't restrict it to bitsets of the same size only.
>
> So, the questions:
>
> 1. May I remove that assertion?
>     (It won't be a breaking change, after all).
>
> 2. How about doing the same thing to bitwise operators, too? Instead
>     of throwing an assertion if sizes don't match, it may be worth to
>     generalize the operators definitions. I can see several possible
>     schemes, but not all of them are consistent enough.

Are you suggesting that the <,>,<=, and >= operators always return  
'false' if the sizes do not match, rather than assert ?

>
> 3. Shouldn't BOOST_ASSERT be used instead of the one from assert.h?

Possibly. I think the intention was always to assert, whereas  
BOOST_ASSERT lets the assertion be overridden. I do agree with you that  
the current way dynamic_bitset works with the assertion should have been  
documented.

>
> ——— Pavel K.
>
> [1]: http://en.cppreference.com/w/cpp/concept/EqualityComparable


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Apr 27, 2017 13:36, "Pavel Kretov via Boost" <[hidden email]>
wrote:

Hi all.

Looking through boost::dynamic_bitset code, I found a interesting
inconsistency between its operator== and operator<. Namely, the first
works well with bitsets of different size, while the second triggers
an assertion:

    boost::dynamic_bitset<> a(std::string("111")),
                            b(std::string("1110"));
    a == b; // false
    a < b;  // Assertion `a.size() == b.size()' failed.

This means that we cannot reliably use dynamic bitset within ordered
containers like std::set or std::map.

Since the standard library has distinct concepts of equality and
equivalence (see [1]), it's fine to have different comparison
behaviors in dynamic_bitset. However, as far as I can judge,
equivalence is a metaphysically broader concept than equality, we
shouldn't restrict it to bitsets of the same size only.

So, the questions:

1. May I remove that assertion?
   (It won't be a breaking change, after all).


I agree that such comparisons should be valid. We should represent a total
order, just like standard containers do (assuming their elements do, of
course). I'm actually rather surprised that this isn't already supported.

On Apr 27, 2017 13:36, "Pavel Kretov via Boost"

2. How about doing the same thing to bitwise operators, too? Instead
   of throwing an assertion if sizes don't match, it may be worth to
   generalize the operators definitions. I can see several possible
   schemes, but not all of them are consistent enough.


I'm not sure, though I agree that it's definitely worth investigating with
further discussion on the list and some example use-cases. I intuitively
suspect it's a reasonable generalization to act as though implicit 0s were
present for the shorter operand, based on an interpretation as a binary
value. The side on which to pad should be consistent with the
lexicographical ordering. Even this generalization is somewhat debatable
though, since extraneous 0s contribute to value in a dynamic bitset.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Hi Edward and Matt!
Thank you for your replies. Let me comment them both in one (maybe,
overly long) message.

Edward Diener wrote:
> Are you suggesting that the <,>,<=, and >= operators always return
> 'false' if the sizes do not match, rather than assert ?

Definitely, no. I'm suggesting to discuss the rules of meaningful and
useful comparison for dynamic bitsets of different lengths. Returning
'false' each time sizes are different would make 'operator <' not only
inappropriate for std::set or std::map, but will force many STL
algorithms to treat these objects as equivalent, since equivalence is
defined is the standard library as:

   equiv(a, b) = !(a<b) && !(b<a)

We need a more elaborate solution.

> > Shouldn't BOOST_ASSERT be used instead of the one from assert.h?
>
> Possibly. I think the intention was always to assert, whereas
> BOOST_ASSERT lets the assertion be overridden. I do agree with you
> that the current way dynamic_bitset works with the assertion should
> have been documented.

I think, these assertions should be eliminated, not documented. We can
get rid of them without breaking even a bit of backward-compatibility.
Would you feel happy if an innocent-looking code like

    std::string("c++") < "boost"

call std::terminate just because the class authors don't want to
handle all possible inputs for some reason? Less-comparison must
either be completely and safely defined, or not defined at all. That's
how the math works.

If we cannot reliably define total ordering, we can, probably, return
std::optional<bool> or even boost::tribool from 'operator <', or, at
the very bad, put an exception to the throw()-list. Terminating the
whole application immediately is *the worst possible* option, since it
is not the expected behavior for the comparison operator.

Matt Calabrese wrote:
> I agree that such comparisons should be valid. We should represent a
> total order, just like standard containers do (assuming their
> elements do, of course). I'm actually rather surprised that this
> isn't already supported.

At the time, I can see two completely different, mutually exclusive
total-order generalizations:

1. Mimic lexicographic string comparison: compare a[0] with b[0], if
   they're equal, compare a[1] with b[1], etc. This is also the
   way how std::vector<T> works if T is less-comparable (including
   the special case for std::vector<bool>).

2. Mimic little-endian (or big-endian) numeric comparison.

   -bit-: (9)      (0)
       a:  0000001101
       b:     0001101
       c:    00010000
     a<b:       false
     b<a:       false
     equiv(a,b): true
     a<c:        true
     b<c:        true

I strongly prefer the former approach, since the latter makes
equivalence (!(a<b) && !(b<a)) so badly different from equality
(a==b). Equality already works in the lexicographic way, there is
little reason to introduce incompatible ordering scheme
to 'operator <', unless we're going to generalize bitwise operators
to mimic numbers, too.

It must also be noted that std::bitset avoids defining 'operator <'
for some reason. I think, they did it in order not to give users false
expectations about the ordering. The very name 'bitset' is the source
of confusion. I think, if we could rename boost::dynamic_bitset to
simply boost::bitstring, anyone would have no second idea about how
the class does its comparisons.

> I'm not sure, though I agree that it's definitely worth
> investigating with further discussion on the list and some example
> use-cases. I intuitively suspect it's a reasonable generalization to
> act as though implicit 0s were present for the shorter operand,
> based on an interpretation as a binary value. The side on which to
> pad should be consistent with the lexicographical ordering. Even
> this generalization is somewhat debatable though, since extraneous
> 0s contribute to value in a dynamic bitset.

If we continue thinking about dynamic_bitset as a bitstring (or, more
generally, bitlist), it would be consistent to define bitwise
operators in terms of 'zip' function, commonly found in a number of
functional programming languages (some pseudo-Haskell code follows):

   (&) :: [Bit] -> [Bit] -> [Bit]
   a & b = zipWith (&) a b

Usually, 'zip' combines lists until one of them is over (see [1]
and [2], though). Hence, applying 'operator &' to bitsets of
different size should create a new bitset with the length of the
shorter. The great feature of this definition is that it naturally
obeys the De Morghan's laws:

  (~a & ~b) == ~(a | b)
  (~b | ~b) == ~(a & b)

I also tried different padding schemes and had no luck keeping them
consistent to De Morghan laws. It anyone interested, I can post my
generalization attempts on the list.

With best wishes and hope that my suboptimal language
skills won't totally ruin my arguments,
——— Pavel K.

[1]: https://softwareengineering.stackexchange.com/q/274983
     (Why does 'zip' ignore the dangling tail of the collection?)
[2]: http://stackoverflow.com/a/8513803
     (TLDR: Boost's zip_iterator doesn't behave like Haskell's zip).

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
On 5/2/2017 1:47 PM, Pavel Kretov via Boost wrote:

> Hi Edward and Matt!
> Thank you for your replies. Let me comment them both in one (maybe,
> overly long) message.
>
> Edward Diener wrote:
>> Are you suggesting that the <,>,<=, and >= operators always return
>> 'false' if the sizes do not match, rather than assert ?
>
> Definitely, no. I'm suggesting to discuss the rules of meaningful and
> useful comparison for dynamic bitsets of different lengths. Returning
> 'false' each time sizes are different would make 'operator <' not only
> inappropriate for std::set or std::map, but will force many STL
> algorithms to treat these objects as equivalent, since equivalence is
> defined is the standard library as:
>
>     equiv(a, b) = !(a<b) && !(b<a)
>
> We need a more elaborate solution.
>
>>> Shouldn't BOOST_ASSERT be used instead of the one from assert.h?
>>
>> Possibly. I think the intention was always to assert, whereas
>> BOOST_ASSERT lets the assertion be overridden. I do agree with you
>> that the current way dynamic_bitset works with the assertion should
>> have been documented.
>
> I think, these assertions should be eliminated, not documented. We can
> get rid of them without breaking even a bit of backward-compatibility.
> Would you feel happy if an innocent-looking code like
>
>      std::string("c++") < "boost"
>
> call std::terminate just because the class authors don't want to
> handle all possible inputs for some reason? Less-comparison must
> either be completely and safely defined, or not defined at all. That's
> how the math works.
>
> If we cannot reliably define total ordering, we can, probably, return
> std::optional<bool> or even boost::tribool from 'operator <', or, at
> the very bad, put an exception to the throw()-list. Terminating the
> whole application immediately is *the worst possible* option, since it
> is not the expected behavior for the comparison operator.

I do not see the point of having <.<=,>, or >= for dynamic bitsets. I  
was not involved in the original discussion about what this was supposed  
to mean for dynamic_bitset but I would rather that they had not been  
implemented at all. Given that they were implemented, and I have no idea  
when that functionality would ever be used, I have no great stake in how  
they should work when the bitsets are of different sizes. I do agree  
with your point that using an assert when the bitsets are of different  
sizes is a very poor solution.

>
> Matt Calabrese wrote:
>> I agree that such comparisons should be valid. We should represent a
>> total order, just like standard containers do (assuming their
>> elements do, of course). I'm actually rather surprised that this
>> isn't already supported.
>
> At the time, I can see two completely different, mutually exclusive
> total-order generalizations:
>
> 1. Mimic lexicographic string comparison: compare a[0] with b[0], if
>     they're equal, compare a[1] with b[1], etc. This is also the
>     way how std::vector<T> works if T is less-comparable (including
>     the special case for std::vector<bool>).

This seems the most logical method.

>
> 2. Mimic little-endian (or big-endian) numeric comparison.
>
>     -bit-: (9)      (0)
>         a:  0000001101
>         b:     0001101
>         c:    00010000
>       a<b:       false
>       b<a:       false
>       equiv(a,b): true
>       a<c:        true
>       b<c:        true
>
> I strongly prefer the former approach, since the latter makes
> equivalence (!(a<b) && !(b<a)) so badly different from equality
> (a==b). Equality already works in the lexicographic way, there is
> little reason to introduce incompatible ordering scheme
> to 'operator <', unless we're going to generalize bitwise operators
> to mimic numbers, too.
>
> It must also be noted that std::bitset avoids defining 'operator <'
> for some reason. I think, they did it in order not to give users false
> expectations about the ordering. The very name 'bitset' is the source
> of confusion. I think, if we could rename boost::dynamic_bitset to
> simply boost::bitstring, anyone would have no second idea about how
> the class does its comparisons.

I do not think that bitsets are bitstrings in any way.

I admit that I am baffled by the fact that, other than wanting to know  
if two bitsets are equal or unequal, any sort of lesser or greater type  
comparison makes any sense at all. But given that it is already  
implemented in dynamic_bitset I am certainly not against a change which  
would work with bitsets of different sizes.

>
>> I'm not sure, though I agree that it's definitely worth
>> investigating with further discussion on the list and some example
>> use-cases. I intuitively suspect it's a reasonable generalization to
>> act as though implicit 0s were present for the shorter operand,
>> based on an interpretation as a binary value. The side on which to
>> pad should be consistent with the lexicographical ordering. Even
>> this generalization is somewhat debatable though, since extraneous
>> 0s contribute to value in a dynamic bitset.
>
> If we continue thinking about dynamic_bitset as a bitstring (or, more
> generally, bitlist), it would be consistent to define bitwise
> operators in terms of 'zip' function, commonly found in a number of
> functional programming languages (some pseudo-Haskell code follows):
>
>     (&) :: [Bit] -> [Bit] -> [Bit]
>     a & b = zipWith (&) a b

Would you please explain this in C++ rather than in Haskell ?

>
> Usually, 'zip' combines lists until one of them is over (see [1]
> and [2], though). Hence, applying 'operator &' to bitsets of
> different size should create a new bitset with the length of the
> shorter. The great feature of this definition is that it naturally
> obeys the De Morghan's laws:
>
>    (~a & ~b) == ~(a | b)
>    (~b | ~b) == ~(a & b)
>
> I also tried different padding schemes and had no luck keeping them
> consistent to De Morghan laws. It anyone interested, I can post my
> generalization attempts on the list.
>
> With best wishes and hope that my suboptimal language
> skills won't totally ruin my arguments,

Your English language skills are fine. If you create a PR I will look at it.

> ——— Pavel K.
>
> [1]: https://softwareengineering.stackexchange.com/q/274983
>       (Why does 'zip' ignore the dangling tail of the collection?)
> [2]: http://stackoverflow.com/a/8513803
>       (TLDR: Boost's zip_iterator doesn't behave like Haskell's zip).


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
On Wed, May 3, 2017 at 4:47 PM, Edward Diener via Boost <
[hidden email]> wrote:
>
> I do not see the point of having <.<=,>, or >= for dynamic bitsets. I was
> not involved in the original discussion about what this was supposed to
> mean for dynamic_bitset but I would rather that they had not been
> implemented at all. Given that they were implemented, and I have no idea
> when that functionality would ever be used, I have no great stake in how
> they should work when the bitsets are of different sizes. I do agree with
> your point that using an assert when the bitsets are of different sizes is
> a very poor solution.


There are at least some advocates for defining these all of the time to
represent a default order. If you don't fall into that camp, there is the
existing precedent being that standard containers provide such operations,
although they are technically only considered "optional requirements" for
the standard container concept, even though that's a bit of an oxymoron.

On Wed, May 3, 2017 at 4:47 PM, Edward Diener via Boost <
[hidden email]> wrote:

> I admit that I am baffled by the fact that, other than wanting to know if
> two bitsets are equal or unequal, any sort of lesser or greater type
> comparison makes any sense at all. But given that it is already implemented
> in dynamic_bitset I am certainly not against a change which would work with
> bitsets of different sizes.


Having an ordering is a common requirement for generic
algorithms/datastructures. Stepanov defines Regular types as including a
default order. Since we don't (yet) have a standard way to specify some
kind of default order that is different from the relational operators, that
usually means overloading <, >, <=, and >=. I personally tend to feel that
because a given type has multiple valid orderings, unless it's a monostate
type, it's a questionable requirement. An ordering can always be specified
at a call-site. Still, existing practice is to simply define the relational
operators and I don't think it hurts.

--
-Matt Calabrese

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
On 5/9/2017 2:41 PM, Matt Calabrese via Boost wrote:

> On Wed, May 3, 2017 at 4:47 PM, Edward Diener via Boost <
> [hidden email]> wrote:
>>
>> I do not see the point of having <.<=,>, or >= for dynamic bitsets. I was
>> not involved in the original discussion about what this was supposed to
>> mean for dynamic_bitset but I would rather that they had not been
>> implemented at all. Given that they were implemented, and I have no idea
>> when that functionality would ever be used, I have no great stake in how
>> they should work when the bitsets are of different sizes. I do agree with
>> your point that using an assert when the bitsets are of different sizes is
>> a very poor solution.
>
>
> There are at least some advocates for defining these all of the time to
> represent a default order. If you don't fall into that camp, there is the
> existing precedent being that standard containers provide such operations,
> although they are technically only considered "optional requirements" for
> the standard container concept, even though that's a bit of an oxymoron.
>
> On Wed, May 3, 2017 at 4:47 PM, Edward Diener via Boost <
> [hidden email]> wrote:
>
>> I admit that I am baffled by the fact that, other than wanting to know if
>> two bitsets are equal or unequal, any sort of lesser or greater type
>> comparison makes any sense at all. But given that it is already implemented
>> in dynamic_bitset I am certainly not against a change which would work with
>> bitsets of different sizes.
>
>
> Having an ordering is a common requirement for generic
> algorithms/datastructures. Stepanov defines Regular types as including a
> default order. Since we don't (yet) have a standard way to specify some
> kind of default order that is different from the relational operators, that
> usually means overloading <, >, <=, and >=. I personally tend to feel that
> because a given type has multiple valid orderings, unless it's a monostate
> type, it's a questionable requirement. An ordering can always be specified
> at a call-site. Still, existing practice is to simply define the relational
> operators and I don't think it hurts.

I am more pragmatic in this case. Ordering is great when it means
something. i just don't see that ordering dynamic_bitsets mean anything
as far as the uses of a bitset are defined.

Given that there is an ordering I agree with the OP that an assertion,
when bitsets are a different size and an ordering operator is used, is
not the right way that dynamic_bitset should have been designed. But
what should be done I do not know and am perfectly willing to defer to
others on this, as I am just a maintainer and not the original developer.

>



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
Edward wrote:

>Given that there is an ordering I agree with the OP that an assertion, when
bitsets are a different size and an ordering operator is used, is not the
right way that >dynamic_bitset should have been designed. But what should be
done I do not know and am perfectly willing to defer to others on this, as I
am just a maintainer >and not the original developer.

I don't think there is an truly natural ordering because you'd want, say,
'00' not to be equal to be '0' but under any natural ordering they'd map to
the same integer, 0.

So you have two options:
        - consider length first and if they are equal consider the bit
pattern using the ordering you have now.
        - consider common bits first (i.e. given lengths M,N consider
the last min(N,M) bits of each). If they are equal consider the length
(longer is greater).

Either of these would be compatible with the equal-size ordering that is
currently present.
I would imagine the latter is better because it implies '00' < '1' which is
less surprising than the former  ('00' > '1')


 




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
On 5/10/2017 8:28 PM, Peter Bartlett via Boost wrote:

> Edward wrote:
>
>> Given that there is an ordering I agree with the OP that an assertion, when
> bitsets are a different size and an ordering operator is used, is not the
> right way that >dynamic_bitset should have been designed. But what should be
> done I do not know and am perfectly willing to defer to others on this, as I
> am just a maintainer >and not the original developer.
>
> I don't think there is an truly natural ordering because you'd want, say,
> '00' not to be equal to be '0' but under any natural ordering they'd map to
> the same integer, 0.
>
> So you have two options:
> - consider length first and if they are equal consider the bit
> pattern using the ordering you have now.
> - consider common bits first (i.e. given lengths M,N consider
> the last min(N,M) bits of each). If they are equal consider the length
> (longer is greater).

I do not understand the difference above. Currently when the sizes are
equal the algorithm compares the bits from right to left, else asserts.
Your second choice above would do the same when the sizes are equal, but
always specify the longer length as greater rather than assert if the
same length bits are equal. I agree with how you suggest to change it,
but between the first and second above, when the sizes are equal I see
no difference. Or do you mean to suggest that your second choice would
compare the last min(N,M) bits from left to right to determine ordering
rather than the current right to left ?

>
> Either of these would be compatible with the equal-size ordering that is
> currently present.
> I would imagine the latter is better because it implies '00' < '1' which is
> less surprising than the former  ('00' > '1')


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
On 11 May 2017 at 04:15, Edward Diener via Boost <[hidden email]>
wrote:

> On 5/10/2017 8:28 PM, Peter Bartlett via Boost wrote:
> Or do you mean to suggest that your second choice would compare the last
> min(N,M) bits from left to right to determine ordering rather than the
> current right to left ?
>

Seems to me that comparing bitsets of different sizes makes little 'sense',
but, having said that, having an order (any) in bitsets of different size
is the right thing to have, as it allows for putting those bitsets in
std::(multi_)map/std::(multi_)set. The choice of Left/Right or Right/Left
should I think be guided by what is the cheapest way to compare them, as
the 'most significant (to the user) bits' might be on the left, on the
right, in the middle or even on both ends. I would go for memcmp().

degski
--
"*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend,
Schmerzen aus Schwäche stillend.*" - Novalis 1798

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
On 5/11/2017 12:24 AM, degski via Boost wrote:

> On 11 May 2017 at 04:15, Edward Diener via Boost <[hidden email]>
> wrote:
>
>> On 5/10/2017 8:28 PM, Peter Bartlett via Boost wrote:
>> Or do you mean to suggest that your second choice would compare the last
>> min(N,M) bits from left to right to determine ordering rather than the
>> current right to left ?
>>
>
> Seems to me that comparing bitsets of different sizes makes little 'sense',
> but, having said that, having an order (any) in bitsets of different size
> is the right thing to have, as it allows for putting those bitsets in
> std::(multi_)map/std::(multi_)set. The choice of Left/Right or Right/Left
> should I think be guided by what is the cheapest way to compare them, as
> the 'most significant (to the user) bits' might be on the left, on the
> right, in the middle or even on both ends. I would go for memcmp().

There is no reason to change the right-to-left order as the most
significant bit is on the right. Furthermore it would be foolish to
break backward compatibility on a whim. I will probably keep the same
order but just add that the longer size, the rest being equal, will
always be considered greater than the shorter size. This will eliminate
the assert and, hopefully, will not break any backward compatibility as
the assert itself should never have been expected in normal code. The
only other possibility that I can imagine, if the assert is eliminated,
is to throw some exception if the sizes are not equal, which at least
has the possibility of keeping the program running if the exception is
caught.

>
> degski
>



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
On 11 May 2017 at 08:11, Edward Diener via Boost <[hidden email]>
wrote:

> There is no reason to change the right-to-left order as the most
> significant bit is on the right.


A bitset is not a number, 'most signifcant' depends on usage and is in the
eye of the beholder.


> Furthermore it would be foolish to break backward compatibility on a whim.


 Yes.

I will probably keep the same order but just add that the longer size, the
> rest being equal, will always be considered greater than the shorter size.


One could introduce a comparison-policy, the default preserving the
'current' behaviour.


> The only other possibility that I can imagine, if the assert is
> eliminated, is to throw some exception if the sizes are not equal, which at
> least has the possibility of keeping the program running if the exception
> is caught.
>

An exception seems completely wrong to me, as there is a valid use case for
comparing bitsets of differing lengths. Exceptions should be used for
exceptional situations, i.e. not here.

degski
--
"*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend,
Schmerzen aus Schwäche stillend.*" - Novalis 1798

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
On 5/11/2017 1:34 AM, degski via Boost wrote:

> On 11 May 2017 at 08:11, Edward Diener via Boost <[hidden email]>
> wrote:
>
>> There is no reason to change the right-to-left order as the most
>> significant bit is on the right.
>
>
> A bitset is not a number, 'most signifcant' depends on usage and is in the
> eye of the beholder.
>
>
>> Furthermore it would be foolish to break backward compatibility on a whim.
>
>
>   Yes.
>
> I will probably keep the same order but just add that the longer size, the
>> rest being equal, will always be considered greater than the shorter size.
>
>
> One could introduce a comparison-policy, the default preserving the
> 'current' behaviour.
>
>
>> The only other possibility that I can imagine, if the assert is
>> eliminated, is to throw some exception if the sizes are not equal, which at
>> least has the possibility of keeping the program running if the exception
>> is caught.
>>
>
> An exception seems completely wrong to me, as there is a valid use case for
> comparing bitsets of differing lengths. Exceptions should be used for
> exceptional situations, i.e. not here.

What I have ended up doing is to keep the exact same behavior as before
when the bitsets are of equal size. When the bitsets are of unequal
size, if either size is 0 that bitset is less than the other one. If
neither size is 0 I convert both bitsets to an unsigned long using the
already provided member function to_ulong() and use those values for the
comparison.

I have tested this out adding some tests for different sized bitsets. I
have not pushed this to 'develop' yet. I wanted to post here my solution
and then others could chime in if they wished.

I found that it was completely wrong to do bit-by-bit comparisons when
the bitsets were not the same size. No matter how I decided to do it the
result was never correct. If anyone doubts this they can try it for
themselves.

>
> degski
>



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
On 15 May 2017 at 23:50, Edward Diener via Boost <[hidden email]>
wrote:

> What I have ended up doing is to keep the exact same behavior as before
> when the bitsets are of equal size. When the bitsets are of unequal size,
> if either size is 0 that bitset is less than the other one. If neither size
> is 0 I convert both bitsets to an unsigned long using the already provided
> member function to_ulong() and use those values for the comparison.
>

 A throwing function returning a ulong seem wrong and restrictive (32 bits
on windows). If my bitset was only 32 bits long, I wouldn't use a
dynamic_bitset<> in the first place.

I found that it was completely wrong to do bit-by-bit comparisons when the
> bitsets were not the same size.


Size/length could be the deciding factor in this case.

degski
--
"*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend,
Schmerzen aus Schwäche stillend.*" - Novalis 1798

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
On 5/16/2017 2:49 AM, degski via Boost wrote:

> On 15 May 2017 at 23:50, Edward Diener via Boost <[hidden email]>
> wrote:
>
>> What I have ended up doing is to keep the exact same behavior as before
>> when the bitsets are of equal size. When the bitsets are of unequal size,
>> if either size is 0 that bitset is less than the other one. If neither size
>> is 0 I convert both bitsets to an unsigned long using the already provided
>> member function to_ulong() and use those values for the comparison.
>>
>
>   A throwing function returning a ulong seem wrong and restrictive (32 bits
> on windows). If my bitset was only 32 bits long, I wouldn't use a
> dynamic_bitset<> in the first place.

There is no other way to do it. BTW ulong is 64-bits on any 64-bit OS.

>
> I found that it was completely wrong to do bit-by-bit comparisons when the
>> bitsets were not the same size.
>
>
> Size/length could be the deciding factor in this case.

Feel free to suggest an algorithm which works doing bit-by-bit
comparisons when the number of bits are different.

>
> degski
>



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
On 17/05/2017 05:01, Edward Diener wrote:
> There is no other way to do it. BTW ulong is 64-bits on any 64-bit OS.

"unsigned long" is 32-bits on Windows, even in 64 bit.

> Feel free to suggest an algorithm which works doing bit-by-bit
> comparisons when the number of bits are different.

What's wrong with comparing bit-by-bit up to the common length, then if
still equal, whichever is longer is greater?

Sure, that doesn't necessarily produce the same answer as an integral
comparison, but that's not a useful comparison for a bitset anyway.



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
On 5/16/2017 7:33 PM, Gavin Lambert via Boost wrote:

> On 17/05/2017 05:01, Edward Diener wrote:
>> There is no other way to do it. BTW ulong is 64-bits on any 64-bit OS.
>
> "unsigned long" is 32-bits on Windows, even in 64 bit.
>
>> Feel free to suggest an algorithm which works doing bit-by-bit
>> comparisons when the number of bits are different.
>
> What's wrong with comparing bit-by-bit up to the common length, then if
> still equal, whichever is longer is greater?

It depends on what you consider the bits comprising the common length ?
I am assuming you are considering the bits comprising the common length
as the lower order bits comprising the common length. So that with

1010001 and 111

the bits comprising the common length are 001 and 111. Because if you
mean the high order bits comprising the common length, so that the bits
comprising the common length are 101 and 111, that makes absolutely no
sense to me, since by that 1010001 < 111. However even if you mean the
low order bits comprising the common length then by your suggestion
1010001 is still < 111, which again makes no sense. I think whatever the
algorithm the greater value has to be greater than the lesser value

An alternative algorithm I have been considering is when the bit sizes
are unequal is:

a) The bits comprising the common length are the low order bits.
b) If the bitset with the larger bit size has any 1 bit outside the bits
comprising the common length, the smaller bit size is always < the
larger bit size.
c) Else do a bit-by-bit comparison for the bits comprising the common
length going from the higher order bit to the lower order bit of just
those bits.

This algorithm would guarantee that the greater value is always > the
lesser value without the to_ulong limitation of the number of bits in an
unsigned long.

>
> Sure, that doesn't necessarily produce the same answer as an integral
> comparison, but that's not a useful comparison for a bitset anyway.

I disagree. As far as ordering I think it is the only always reliable
comparison.


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
Edward Diener wrote:

> An alternative algorithm I have been considering is when the bit sizes are
> unequal is:
>
> a) The bits comprising the common length are the low order bits.
> b) If the bitset with the larger bit size has any 1 bit outside the bits
> comprising the common length, the smaller bit size is always < the larger
> bit size.
> c) Else do a bit-by-bit comparison for the bits comprising the common
> length going from the higher order bit to the lower order bit of just
> those bits.

Could also add

d) if still equal, the larger bit size > the smaller bit size.

This makes 000111 > 111 instead of equal, so that equality (which I presume
checks sizes) and equivalence match.


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 17/05/2017 12:39, Edward Diener wrote:

> On 5/16/2017 7:33 PM, Gavin Lambert wrote:
>> What's wrong with comparing bit-by-bit up to the common length, then
>> if still equal, whichever is longer is greater?
>
> It depends on what you consider the bits comprising the common length ?
> I am assuming you are considering the bits comprising the common length
> as the lower order bits comprising the common length. So that with
>
> 1010001 and 111
>
> the bits comprising the common length are 001 and 111.

I'm not thinking of it as a bitstring at all.  Whichever bit is bit [0]
is compared first.  It doesn't matter whether this is rendered first or
last as a bitstring.

(Although yes, I would expect it to be rendered last, because I've been
biased by little-bit-endian numbering; note that isn't universal,
however; albeit nearly so, even on big-endian-integer architectures, due
to base numbering.)

> However even if you mean the low order bits comprising the common
> length then by your suggestion 1010001 is still < 111, which again
> makes no sense.

Why does that make no sense?  This is not a number and it is not a
bitstring, it is an arbitrary set of bits.  As long as the ordering is
consistent (which this is, in all cases) it doesn't have to match how it
would be ordered as a bitstring or integer.


Some alternate completely different possible orderings:

   1. Render it as a bitstring first and then use string comparison.
This seems needlessly perf-hungry (unless internal storage were already
as a bitstring, but that seems needlessly storage-hungry).  This also
biases the comparison to the non-[0] end, which might be good or bad
depending on usage.

   2. Compare each 32-bit (or whatever window size is convenient) group
of bits as an unsigned integer (zero-padding if smaller than the window
size), starting at whichever one holds [0] and continuing as long as
both sets contributed at least one "real" bit to the window; if any
comparison returns unequal, that's the result; if all comparisons return
equal, then finally compare the actual sizes of both sets for the final
result.  Advantage: fast.  Disadvantage: the ordering might change if
the window size changes (eg. for different platforms, or future Boost
versions).



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [dynamic_bitset] Comparison operators without assertions

Boost - Dev mailing list
Mere moments ago, quoth I:
>   1. Render it as a bitstring first and then use string comparison. This
> seems needlessly perf-hungry (unless internal storage were already as a
> bitstring, but that seems needlessly storage-hungry).  This also biases
> the comparison to the non-[0] end, which might be good or bad depending
> on usage.

Variations include zero-padding whichever one is smaller, or not.

>   2. Compare each 32-bit (or whatever window size is convenient) group
> of bits as an unsigned integer (zero-padding if smaller than the window
> size), starting at whichever one holds [0] and continuing as long as
> both sets contributed at least one "real" bit to the window; if any
> comparison returns unequal, that's the result; if all comparisons return
> equal, then finally compare the actual sizes of both sets for the final
> result.  Advantage: fast.  Disadvantage: the ordering might change if
> the window size changes (eg. for different platforms, or future Boost
> versions).

Another variation is to start from the non-[0] end.  This would probably
get you a more "natural" bitstring-like ordering and should be less
dependent on the window size.  Might still result in different ordering
on big-endian vs. little-endian platforms, though that depends on how
internal storage is structured vs. indexing.

Comparing the actual sizes at the end if everything else is equal seems
like an important step, though.  0000 > 00.



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
12
Loading...