miden_objects/account/delta/
lexicographic_word.rs

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

miden_objects/account/delta/
lexicographic_word.rs
