substrate_median/
lexicographic.rs

1use core::cmp::Ord;
2
3use scale::FullCodec;
4
5/// A trait to obtain an encoding whose lexicographic order corresponds to the value's.
6pub trait LexicographicEncoding: Ord + FullCodec {
7  /// The representation of the encoding.
8  ///
9  /// This SHOULD be `[u8; N]` or similar.
10  type Encoding: AsMut<[u8]> + Ord + FullCodec;
11  /// Encode such that `cmp(e(A), e(B)) == cmp(A, B)`.
12  fn lexicographic_encode(&self) -> Self::Encoding;
13  /// Decode such that `d(e(A)) == A`.
14  fn lexicographic_decode(encoding: Self::Encoding) -> Self;
15}
16
17macro_rules! impl_prim_uint {
18  ($type: ident) => {
19    impl LexicographicEncoding for $type {
20      type Encoding = [u8; core::mem::size_of::<Self>()];
21      fn lexicographic_encode(&self) -> Self::Encoding {
22        self.to_be_bytes()
23      }
24      fn lexicographic_decode(encoding: Self::Encoding) -> Self {
25        Self::from_be_bytes(encoding)
26      }
27    }
28  };
29}
30impl_prim_uint!(u8);
31impl_prim_uint!(u16);
32impl_prim_uint!(u32);
33impl_prim_uint!(u64);
34impl_prim_uint!(u128);
35
36/// A wrapper such that
37/// `a.cmp(&b).reverse() == e(LexicographicReverse(a)).cmp(&e(LexicographicReverse(b)))`.
38///
39/// This allows systems which only allow iterating forwards to iterate backwards by inverting the
40/// direction of values via this derivative encoding.
41pub struct LexicographicReverse<V: LexicographicEncoding>(V::Encoding);
42
43impl<V: LexicographicEncoding> scale::Decode for LexicographicReverse<V> {
44  fn decode<I: scale::Input>(input: &mut I) -> Result<Self, scale::Error> {
45    V::Encoding::decode(input).map(Self)
46  }
47}
48
49impl<V: LexicographicEncoding> scale::Encode for LexicographicReverse<V> {
50  fn size_hint(&self) -> usize {
51    self.0.size_hint()
52  }
53  fn encode_to<T: scale::Output + ?Sized>(&self, dest: &mut T) {
54    self.0.encode_to(dest)
55  }
56  fn encode(&self) -> Vec<u8> {
57    self.0.encode()
58  }
59  fn using_encoded<R, F: FnOnce(&[u8]) -> R>(&self, f: F) -> R {
60    self.0.using_encoded(f)
61  }
62  fn encoded_size(&self) -> usize {
63    self.0.encoded_size()
64  }
65}
66
67impl<V: LexicographicEncoding> scale::EncodeLike for LexicographicReverse<V> {}
68
69/// This is a bijective mapping such that `reverse(reverse(encoding)) == encoding`.
70fn reverse<E: AsMut<[u8]>>(mut encoding: E) -> E {
71  for byte in encoding.as_mut().iter_mut() {
72    *byte = !*byte;
73  }
74  encoding
75}
76
77impl<V: LexicographicEncoding> LexicographicReverse<V> {
78  pub(super) fn from_encoding(encoding: V::Encoding) -> Self {
79    Self(reverse(encoding))
80  }
81  pub(super) fn from(value: &V) -> Self {
82    Self::from_encoding(value.lexicographic_encode())
83  }
84  pub(super) fn into(self) -> V {
85    V::lexicographic_decode(reverse(self.0))
86  }
87}
88
89#[test]
90fn lexicographic_uint() {
91  use rand_core::{RngCore, OsRng};
92
93  // Basic sanity checks
94  {
95    assert_eq!(0u64.lexicographic_encode(), 0u64.lexicographic_encode());
96    assert!(0u64.lexicographic_encode() < 1u64.lexicographic_encode());
97    assert!(0u64.lexicographic_encode() <= 1u64.lexicographic_encode());
98    assert!(1u64.lexicographic_encode() > 0u64.lexicographic_encode());
99    assert!(1u64.lexicographic_encode() >= 0u64.lexicographic_encode());
100  }
101
102  // `lexicographic_decode`
103  for _ in 0 .. 100 {
104    let value = OsRng.next_u64();
105    assert_eq!(u64::lexicographic_decode(value.lexicographic_encode()), value);
106  }
107
108  // Fuzz test the ordinality
109  for _ in 0 .. 100 {
110    let a = OsRng.next_u64();
111    let b = OsRng.next_u64();
112    assert_eq!(a.cmp(&b), a.lexicographic_encode().cmp(&b.lexicographic_encode()));
113  }
114}
115
116#[test]
117fn lexicographic_reverse() {
118  use rand_core::{RngCore, OsRng};
119
120  for _ in 0 .. 100 {
121    let a = OsRng.next_u64();
122    let b = loop {
123      let b = OsRng.next_u64();
124      if a != b {
125        break b;
126      }
127    };
128    let mut a_enc = a.lexicographic_encode();
129    let mut b_enc = b.lexicographic_encode();
130    assert_eq!(a_enc, a_enc);
131    assert_eq!(a.cmp(&b), a_enc.cmp(&b_enc));
132
133    assert_eq!(a.cmp(&b).reverse(), reverse(a_enc).cmp(&reverse(b_enc)));
134
135    // This should be a bijective encoding
136    assert_eq!(reverse(reverse(a_enc)), a_enc);
137    assert_eq!(reverse(reverse(b_enc)), b_enc);
138    assert_eq!(LexicographicReverse::<u64>::from_encoding(a.lexicographic_encode()).into(), a);
139    assert_eq!(LexicographicReverse::<u64>::from_encoding(b.lexicographic_encode()).into(), b);
140    assert_eq!(LexicographicReverse::from(&a).into(), a);
141    assert_eq!(LexicographicReverse::from(&b).into(), b);
142  }
143}
substrate_median/lexicographic.rs

substrate_median/
lexicographic.rs
