miden_crypto/word/
lexicographic.rs

1use core::cmp::Ordering;
2
3use p3_field::PrimeField64;
4
5use super::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable};
6use crate::{Felt, WORD_SIZE, Word};
7
8// LEXICOGRAPHIC WORD
9// ================================================================================================
10
11/// A [`Word`] wrapper with lexicographic ordering.
12///
13/// This is a wrapper around any [`Word`] convertible type that overrides the equality and ordering
14/// implementations with a lexigographic one based on the wrapped type's [`Word`] representation.
15#[derive(Debug, Clone, Copy)]
16pub struct LexicographicWord<T: Into<Word> = Word>(T);
17
18impl<T: Into<Word>> LexicographicWord<T> {
19    /// Wraps the provided value into a new [`LexicographicWord`].
20    pub fn new(inner: T) -> Self {
21        Self(inner)
22    }
23
24    /// Returns a reference to the inner value.
25    pub fn inner(&self) -> &T {
26        &self.0
27    }
28
29    /// Consumes self and returns the inner value.
30    pub fn into_inner(self) -> T {
31        self.0
32    }
33}
34
35impl From<[Felt; WORD_SIZE]> for LexicographicWord {
36    fn from(value: [Felt; WORD_SIZE]) -> Self {
37        Self(value.into())
38    }
39}
40
41impl From<Word> for LexicographicWord {
42    fn from(word: Word) -> Self {
43        Self(word)
44    }
45}
46
47impl<T: Into<Word>> From<LexicographicWord<T>> for Word {
48    fn from(key: LexicographicWord<T>) -> Self {
49        key.0.into()
50    }
51}
52
53impl<T: Into<Word> + Copy> PartialEq for LexicographicWord<T> {
54    fn eq(&self, other: &Self) -> bool {
55        let self_word: Word = self.0.into();
56        let other_word: Word = other.0.into();
57        self_word == other_word
58    }
59}
60
61impl<T: Into<Word> + Copy> Eq for LexicographicWord<T> {}
62
63impl<T: Into<Word> + Copy> PartialOrd for LexicographicWord<T> {
64    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
65        Some(self.cmp(other))
66    }
67}
68
69impl<T: Into<Word> + Copy> Ord for LexicographicWord<T> {
70    fn cmp(&self, other: &Self) -> Ordering {
71        let self_word: Word = self.0.into();
72        let other_word: Word = other.0.into();
73
74        for (felt0, felt1) in self_word
75            .iter()
76            .rev()
77            .map(Felt::as_canonical_u64)
78            .zip(other_word.iter().rev().map(Felt::as_canonical_u64))
79        {
80            let ordering = felt0.cmp(&felt1);
81            if let Ordering::Less | Ordering::Greater = ordering {
82                return ordering;
83            }
84        }
85
86        Ordering::Equal
87    }
88}
89
90// SERIALIZATION
91// ================================================================================================
92
93impl<T: Into<Word> + Copy> Serializable for LexicographicWord<T> {
94    fn write_into<W: ByteWriter>(&self, target: &mut W) {
95        self.0.into().write_into(target);
96    }
97
98    fn get_size_hint(&self) -> usize {
99        self.0.into().get_size_hint()
100    }
101}
102
103impl<T: Into<Word> + From<Word>> Deserializable for LexicographicWord<T> {
104    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
105        let word = Word::read_from(source)?;
106
107        Ok(Self::new(T::from(word)))
108    }
109}
110
111// TESTS
112// ================================================================================================
113
114#[cfg(test)]
115mod tests {
116    use p3_field::PrimeCharacteristicRing;
117
118    use super::*;
119
120    #[derive(Debug, Clone, Copy)]
121    struct NoteId(Word);
122
123    impl From<Word> for NoteId {
124        fn from(value: Word) -> Self {
125            Self(value)
126        }
127    }
128
129    impl From<NoteId> for Word {
130        fn from(value: NoteId) -> Self {
131            value.0
132        }
133    }
134
135    #[test]
136    fn lexicographic_word_ordering() {
137        for (expected, key0, key1) in [
138            (Ordering::Equal, [0, 0, 0, 0u32], [0, 0, 0, 0u32]),
139            (Ordering::Greater, [1, 0, 0, 0u32], [0, 0, 0, 0u32]),
140            (Ordering::Greater, [0, 1, 0, 0u32], [0, 0, 0, 0u32]),
141            (Ordering::Greater, [0, 0, 1, 0u32], [0, 0, 0, 0u32]),
142            (Ordering::Greater, [0, 0, 0, 1u32], [0, 0, 0, 0u32]),
143            (Ordering::Less, [0, 0, 0, 0u32], [1, 0, 0, 0u32]),
144            (Ordering::Less, [0, 0, 0, 0u32], [0, 1, 0, 0u32]),
145            (Ordering::Less, [0, 0, 0, 0u32], [0, 0, 1, 0u32]),
146            (Ordering::Less, [0, 0, 0, 0u32], [0, 0, 0, 1u32]),
147            (Ordering::Greater, [0, 0, 0, 1u32], [1, 1, 1, 0u32]),
148            (Ordering::Greater, [0, 0, 1, 0u32], [1, 1, 0, 0u32]),
149            (Ordering::Less, [1, 1, 1, 0u32], [0, 0, 0, 1u32]),
150            (Ordering::Less, [1, 1, 0, 0u32], [0, 0, 1, 0u32]),
151        ] {
152            assert_eq!(
153                LexicographicWord::from(key0.map(Felt::from_u32))
154                    .cmp(&LexicographicWord::from(key1.map(Felt::from_u32))),
155                expected
156            );
157        }
158    }
159
160    #[test]
161    fn lexicographic_serialization() {
162        let word = Word::from([1u64, 2, 3, 4].map(Felt::new));
163        let key = LexicographicWord::new(word);
164        let bytes = key.to_bytes();
165        let deserialized_key = LexicographicWord::<Word>::read_from_bytes(&bytes).unwrap();
166        assert_eq!(key, deserialized_key);
167
168        let note_id = NoteId::from(word);
169        let key = LexicographicWord::new(note_id);
170        let bytes = key.to_bytes();
171        let deserialized_key = LexicographicWord::<NoteId>::read_from_bytes(&bytes).unwrap();
172        assert_eq!(key, deserialized_key);
173    }
174}
miden_crypto/word/lexicographic.rs

miden_crypto/word/
lexicographic.rs
