rust-bitcoin / rust-bech32

Bech32 format encoding and decoding
MIT License
93 stars 49 forks source link

Add Ord trait to Fe32 (derived) #186

Closed optout21 closed 1 month ago

optout21 commented 1 month ago

See #187 . Add derived Ord trait to Fe32, and tests. Implementation is trivial (derived), but this can be useful.

apoelstra commented 1 month ago

We have a crate ordered with a trait ArbitraryOrd for things like this where it would be "useful" to have an ordering, but there isn't any (or there are multiple) sensible orderings for the type.

I'd prefer you add an optional dependency on that, which implements the ArbitraryOrd trait.

Though cc @clarkmoody to see what he thinks.

In any case, I do not think that Fe32 should implement the Ord trait because it is not an ordered field.

optout21 commented 1 month ago

Indeed, ordering may be confusing, as the char order is different than the numerical. The ordered crate workaround looks useful. Closing.

optout21 commented 1 month ago

A note just for completeness:

In version 0.9.1 the type u5 (the predecessor of Fe32 before the rewrite) did support Ord, in the default way, based on the underlying byte value.

#[derive(PartialEq, Eq, Debug, Copy, Clone, Default, PartialOrd, Ord, Hash)]
pub struct u5(u8);
apoelstra commented 1 month ago

Yes, but u5 was intended to be analagous to u8, u16, etc., which pretend to be integers even though they are actually integers mod 2^n. We never took a principled approach to its API but if we did it would have implemented arithmetic ops in the "ordinary" way where they behaved like integers except in cases of overflow and underflow. We manually simulated field arithmetic using this type by using bit operations.

Fe32 directly represents a field element in an unordered field, where there is no "overflow" or "underflow", and where no matter how you defined an ordering, x + 1 > x could be true at most half the time, etc.