miden_crypto/word/
lexicographic.rs

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

miden_crypto/word/
lexicographic.rs
