commonware_utils/
ordered.rs

1//! Ordered collections that guarantee sorted, deduplicated items.
2
3#[cfg(not(feature = "std"))]
4use alloc::vec::Vec;
5use bytes::{Buf, BufMut};
6use commonware_codec::{EncodeSize, RangeCfg, Read, Write};
7use core::{
8    fmt,
9    hash::Hash,
10    ops::{Deref, Index, Range},
11};
12use hashbrown::HashSet;
13use thiserror::Error;
14
15type Hasher = ahash::RandomState;
16
17#[cfg(not(feature = "std"))]
18type VecIntoIter<T> = alloc::vec::IntoIter<T>;
19#[cfg(feature = "std")]
20type VecIntoIter<T> = std::vec::IntoIter<T>;
21
22/// Errors that can occur when interacting with ordered collections.
23#[derive(Error, Debug, PartialEq, Eq)]
24pub enum Error {
25    /// A key was duplicated.
26    #[error("duplicate key")]
27    DuplicateKey,
28
29    /// A value was duplicated.
30    #[error("duplicate value")]
31    DuplicateValue,
32}
33
34use crate::{Faults, Participant, TryFromIterator};
35
36/// An ordered, deduplicated collection of items.
37#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
38pub struct Set<T>(Vec<T>);
39
40impl<T: fmt::Debug> fmt::Debug for Set<T> {
41    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
42        f.debug_tuple("Set").field(&self.0).finish()
43    }
44}
45
46impl<T> Default for Set<T> {
47    fn default() -> Self {
48        Self(Vec::new())
49    }
50}
51
52impl<T: Ord> Set<T> {
53    /// Creates a new [`Set`] from an iterator, removing duplicates.
54    ///
55    /// Unlike [`FromIterator`] and [`From`], this method tolerates duplicate
56    /// items by silently discarding them.
57    pub fn from_iter_dedup<I: IntoIterator<Item = T>>(iter: I) -> Self {
58        let mut items: Vec<T> = iter.into_iter().collect();
59        items.sort();
60        items.dedup();
61        Self(items)
62    }
63}
64
65impl<T> Set<T> {
66    /// Returns the size of the ordered collection.
67    pub const fn len(&self) -> usize {
68        self.0.len()
69    }
70
71    /// Returns `true` if the collection is empty.
72    pub const fn is_empty(&self) -> bool {
73        self.0.is_empty()
74    }
75
76    /// Returns an item by index, if it exists.
77    pub fn get(&self, index: usize) -> Option<&T> {
78        self.0.get(index)
79    }
80
81    /// Returns the position of a given item in the collection, if it exists.
82    pub fn position(&self, item: &T) -> Option<usize>
83    where
84        T: Ord,
85    {
86        self.0.binary_search(item).ok()
87    }
88
89    /// Returns an iterator over the items in the collection.
90    pub fn iter(&self) -> core::slice::Iter<'_, T> {
91        self.into_iter()
92    }
93}
94
95impl<T: Write> Write for Set<T> {
96    fn write(&self, buf: &mut impl BufMut) {
97        self.0.write(buf);
98    }
99}
100
101impl<T: EncodeSize> EncodeSize for Set<T> {
102    fn encode_size(&self) -> usize {
103        self.0.encode_size()
104    }
105}
106
107impl<T: Read + Ord> Read for Set<T> {
108    type Cfg = (RangeCfg<usize>, T::Cfg);
109
110    fn read_cfg(buf: &mut impl Buf, cfg: &Self::Cfg) -> Result<Self, commonware_codec::Error> {
111        let items = Vec::<T>::read_cfg(buf, cfg)?;
112        for i in 1..items.len() {
113            if items[i - 1] >= items[i] {
114                return Err(commonware_codec::Error::Invalid(
115                    "Set",
116                    "items must be sorted and unique",
117                ));
118            }
119        }
120        Ok(Self(items))
121    }
122}
123
124impl<T: Ord> TryFromIterator<T> for Set<T> {
125    type Error = Error;
126
127    /// Attempts to create a [`Set`] from an iterator.
128    ///
129    /// Returns an error if there are duplicate items.
130    fn try_from_iter<I: IntoIterator<Item = T>>(iter: I) -> Result<Self, Self::Error> {
131        let mut items: Vec<T> = iter.into_iter().collect();
132        items.sort();
133        let len = items.len();
134        items.dedup();
135        if items.len() != len {
136            return Err(Error::DuplicateKey);
137        }
138        Ok(Self(items))
139    }
140}
141
142impl<T: Ord> TryFrom<Vec<T>> for Set<T> {
143    type Error = Error;
144
145    fn try_from(items: Vec<T>) -> Result<Self, Self::Error> {
146        Self::try_from_iter(items)
147    }
148}
149
150impl<T: Ord + Clone> TryFrom<&[T]> for Set<T> {
151    type Error = Error;
152
153    fn try_from(items: &[T]) -> Result<Self, Self::Error> {
154        Self::try_from_iter(items.iter().cloned())
155    }
156}
157
158impl<T: Ord, const N: usize> TryFrom<[T; N]> for Set<T> {
159    type Error = Error;
160
161    fn try_from(items: [T; N]) -> Result<Self, Self::Error> {
162        Self::try_from_iter(items)
163    }
164}
165
166impl<T: Ord + Clone, const N: usize> TryFrom<&[T; N]> for Set<T> {
167    type Error = Error;
168
169    fn try_from(items: &[T; N]) -> Result<Self, Self::Error> {
170        Self::try_from(items.as_slice())
171    }
172}
173
174impl<T> IntoIterator for Set<T> {
175    type Item = T;
176    type IntoIter = VecIntoIter<T>;
177
178    fn into_iter(self) -> Self::IntoIter {
179        self.0.into_iter()
180    }
181}
182
183impl<'a, T> IntoIterator for &'a Set<T> {
184    type Item = &'a T;
185    type IntoIter = core::slice::Iter<'a, T>;
186
187    fn into_iter(self) -> Self::IntoIter {
188        self.0.iter()
189    }
190}
191
192impl<T> Index<usize> for Set<T> {
193    type Output = T;
194
195    fn index(&self, index: usize) -> &Self::Output {
196        &self.0[index]
197    }
198}
199
200impl<T> Index<Range<usize>> for Set<T> {
201    type Output = [T];
202
203    fn index(&self, index: Range<usize>) -> &Self::Output {
204        &self.0[index]
205    }
206}
207
208impl<T> AsRef<[T]> for Set<T> {
209    fn as_ref(&self) -> &[T] {
210        &self.0
211    }
212}
213
214impl<T: fmt::Display> fmt::Display for Set<T> {
215    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
216        write!(f, "[")?;
217        for (i, item) in self.0.iter().enumerate() {
218            if i > 0 {
219                write!(f, ", ")?;
220            }
221            write!(f, "{item}")?;
222        }
223        write!(f, "]")
224    }
225}
226
227impl<T> From<Set<T>> for Vec<T> {
228    fn from(set: Set<T>) -> Self {
229        set.0
230    }
231}
232
233#[cfg(feature = "arbitrary")]
234impl<T> arbitrary::Arbitrary<'_> for Set<T>
235where
236    T: for<'a> arbitrary::Arbitrary<'a> + Ord,
237{
238    fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result<Self> {
239        let vec = Vec::<T>::arbitrary(u)?;
240        Ok(Self::from_iter_dedup(vec))
241    }
242}
243
244/// Extension trait for [`Set`] participant sets providing quorum and index utilities.
245pub trait Quorum {
246    /// The type of items in this set.
247    type Item: Ord;
248
249    /// Returns the quorum value for this participant set using the given fault model.
250    ///
251    /// ## Panics
252    ///
253    /// Panics if the number of participants exceeds `u32::MAX`.
254    fn quorum<M: Faults>(&self) -> u32;
255
256    /// Returns the maximum number of faults tolerated by this participant set.
257    ///
258    /// ## Panics
259    ///
260    /// Panics if the number of participants exceeds `u32::MAX`.
261    fn max_faults<M: Faults>(&self) -> u32;
262
263    /// Returns the participant key at the given index.
264    fn key(&self, index: Participant) -> Option<&Self::Item>;
265
266    /// Returns the index for the given participant key, if present.
267    ///
268    /// ## Panics
269    ///
270    /// Panics if the participant index exceeds `u32::MAX`.
271    fn index(&self, key: &Self::Item) -> Option<Participant>;
272}
273
274impl<T: Ord> Quorum for Set<T> {
275    type Item = T;
276
277    fn quorum<M: Faults>(&self) -> u32 {
278        M::quorum(u32::try_from(self.len()).expect("too many participants"))
279    }
280
281    fn max_faults<M: Faults>(&self) -> u32 {
282        M::max_faults(self.len())
283    }
284
285    fn key(&self, index: Participant) -> Option<&Self::Item> {
286        self.get(index.into())
287    }
288
289    fn index(&self, key: &Self::Item) -> Option<Participant> {
290        self.position(key).map(Participant::from_usize)
291    }
292}
293
294/// An ordered, deduplicated collection of key-value pairs.
295#[derive(Clone, PartialEq, Eq, Hash)]
296pub struct Map<K, V> {
297    keys: Set<K>,
298    values: Vec<V>,
299}
300
301impl<K: Ord, V> Map<K, V> {
302    /// Creates a new [`Map`] from an iterator, removing duplicate keys.
303    ///
304    /// Unlike [`FromIterator`] and [`From`], this method tolerates duplicate
305    /// keys by silently discarding them (keeping the first occurrence).
306    pub fn from_iter_dedup<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
307        let mut items: Vec<(K, V)> = iter.into_iter().collect();
308        items.sort_by(|(lk, _), (rk, _)| lk.cmp(rk));
309        items.dedup_by(|l, r| l.0 == r.0);
310
311        let mut keys = Vec::with_capacity(items.len());
312        let mut values = Vec::with_capacity(items.len());
313        for (key, value) in items {
314            keys.push(key);
315            values.push(value);
316        }
317
318        Self {
319            keys: Set(keys),
320            values,
321        }
322    }
323}
324
325impl<K, V> Default for Map<K, V> {
326    fn default() -> Self {
327        Self {
328            keys: Set::default(),
329            values: Vec::new(),
330        }
331    }
332}
333
334impl<K, V> Map<K, V> {
335    /// Returns the number of entries in the map.
336    pub const fn len(&self) -> usize {
337        self.keys.len()
338    }
339
340    /// Returns `true` if the map is empty.
341    pub const fn is_empty(&self) -> bool {
342        self.keys.is_empty()
343    }
344
345    /// Returns a key by index, if it exists.
346    pub fn get(&self, index: usize) -> Option<&K> {
347        self.keys.get(index)
348    }
349
350    /// Returns the position of the provided key, if it exists.
351    pub fn position(&self, key: &K) -> Option<usize>
352    where
353        K: Ord,
354    {
355        self.keys.position(key)
356    }
357
358    /// Returns the ordered keys as a [`Set`] reference.
359    pub const fn keys(&self) -> &Set<K> {
360        &self.keys
361    }
362
363    /// Consumes the map and returns the ordered keys.
364    pub fn into_keys(self) -> Set<K> {
365        self.keys
366    }
367
368    /// Returns the associated value at `index`, if it exists.
369    pub fn value(&self, index: usize) -> Option<&V> {
370        self.values.get(index)
371    }
372
373    /// Returns the associated value for `key`, if it exists.
374    pub fn get_value(&self, key: &K) -> Option<&V>
375    where
376        K: Ord,
377    {
378        self.position(key).and_then(|index| self.values.get(index))
379    }
380
381    /// Returns a mutable reference to the associated value for `key`, if it exists.
382    pub fn get_value_mut(&mut self, key: &K) -> Option<&mut V>
383    where
384        K: Ord,
385    {
386        self.position(key)
387            .and_then(|index| self.values.get_mut(index))
388    }
389
390    /// Returns the associated values.
391    pub fn values(&self) -> &[V] {
392        &self.values
393    }
394
395    /// Returns a mutable reference to the associated values
396    pub fn values_mut(&mut self) -> &mut [V] {
397        &mut self.values
398    }
399
400    /// Truncates the map to at most `len` entries.
401    pub fn truncate(&mut self, len: usize) {
402        self.keys.0.truncate(len);
403        self.values.truncate(len);
404    }
405
406    /// Returns a zipped iterator over keys and values.
407    pub fn iter_pairs(&self) -> impl Iterator<Item = (&K, &V)> {
408        self.keys.iter().zip(self.values.iter())
409    }
410
411    /// Returns a zipped iterator over keys and mutable references to values.
412    ///
413    /// This is provided because the borrow checker does not let you combine
414    /// the other functions yourself.
415    pub fn iter_pairs_mut(&mut self) -> impl Iterator<Item = (&K, &mut V)> {
416        self.keys.iter().zip(self.values.iter_mut())
417    }
418
419    /// Returns an iterator over the ordered keys.
420    pub fn iter(&self) -> core::slice::Iter<'_, K> {
421        self.keys.iter()
422    }
423}
424
425impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Map<K, V> {
426    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
427        f.debug_tuple("Map")
428            .field(&self.iter_pairs().collect::<Vec<_>>())
429            .finish()
430    }
431}
432
433impl<K: fmt::Display, V: fmt::Display> fmt::Display for Map<K, V> {
434    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
435        write!(f, "[")?;
436        for (i, (key, value)) in self.iter_pairs().enumerate() {
437            if i > 0 {
438                write!(f, ", ")?;
439            }
440            write!(f, "({key}, {value})")?;
441        }
442        write!(f, "]")
443    }
444}
445
446impl<K, V> AsRef<[K]> for Map<K, V> {
447    fn as_ref(&self) -> &[K] {
448        self.keys.as_ref()
449    }
450}
451
452impl<K, V> AsRef<Set<K>> for Map<K, V> {
453    fn as_ref(&self) -> &Set<K> {
454        &self.keys
455    }
456}
457
458impl<K, V> Deref for Map<K, V> {
459    type Target = Set<K>;
460
461    fn deref(&self) -> &Self::Target {
462        &self.keys
463    }
464}
465
466impl<K: Ord, V> TryFromIterator<(K, V)> for Map<K, V> {
467    type Error = Error;
468
469    /// Attempts to create a [`Map`] from an iterator.
470    ///
471    /// Returns an error if there are duplicate keys.
472    fn try_from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Result<Self, Self::Error> {
473        let mut items: Vec<(K, V)> = iter.into_iter().collect();
474        items.sort_by(|(lk, _), (rk, _)| lk.cmp(rk));
475        let len = items.len();
476        items.dedup_by(|l, r| l.0 == r.0);
477        if items.len() != len {
478            return Err(Error::DuplicateKey);
479        }
480
481        let mut keys = Vec::with_capacity(items.len());
482        let mut values = Vec::with_capacity(items.len());
483        for (key, value) in items {
484            keys.push(key);
485            values.push(value);
486        }
487
488        Ok(Self {
489            keys: Set(keys),
490            values,
491        })
492    }
493}
494
495impl<K: Ord, V> TryFrom<Vec<(K, V)>> for Map<K, V> {
496    type Error = Error;
497
498    fn try_from(items: Vec<(K, V)>) -> Result<Self, Self::Error> {
499        Self::try_from_iter(items)
500    }
501}
502
503impl<K: Ord + Clone, V: Clone> TryFrom<&[(K, V)]> for Map<K, V> {
504    type Error = Error;
505
506    fn try_from(items: &[(K, V)]) -> Result<Self, Self::Error> {
507        Self::try_from_iter(items.iter().cloned())
508    }
509}
510
511impl<K: Ord, V, const N: usize> TryFrom<[(K, V); N]> for Map<K, V> {
512    type Error = Error;
513
514    fn try_from(items: [(K, V); N]) -> Result<Self, Self::Error> {
515        Self::try_from_iter(items)
516    }
517}
518
519impl<K: Ord + Clone, V: Clone, const N: usize> TryFrom<&[(K, V); N]> for Map<K, V> {
520    type Error = Error;
521
522    fn try_from(items: &[(K, V); N]) -> Result<Self, Self::Error> {
523        Self::try_from(items.as_slice())
524    }
525}
526
527impl<K, V> From<Map<K, V>> for Vec<(K, V)> {
528    fn from(wrapped: Map<K, V>) -> Self {
529        wrapped.into_iter().collect()
530    }
531}
532
533impl<K: Write, V: Write> Write for Map<K, V> {
534    fn write(&self, buf: &mut impl BufMut) {
535        self.keys.write(buf);
536        self.values.write(buf);
537    }
538}
539
540impl<K: EncodeSize, V: EncodeSize> EncodeSize for Map<K, V> {
541    fn encode_size(&self) -> usize {
542        self.keys.encode_size() + self.values.encode_size()
543    }
544}
545
546impl<K: Read + Ord, V: Read> Read for Map<K, V> {
547    type Cfg = (RangeCfg<usize>, K::Cfg, V::Cfg);
548
549    fn read_cfg(buf: &mut impl Buf, cfg: &Self::Cfg) -> Result<Self, commonware_codec::Error> {
550        let (range_cfg, key_cfg, value_cfg) = cfg;
551        let keys = Set::<K>::read_cfg(buf, &(*range_cfg, key_cfg.clone()))?;
552        let values = Vec::<V>::read_cfg(buf, &(RangeCfg::exact(keys.len()), value_cfg.clone()))?;
553        Ok(Self { keys, values })
554    }
555}
556
557impl<K, V> IntoIterator for Map<K, V> {
558    type Item = (K, V);
559    type IntoIter = MapIntoIter<K, V>;
560
561    fn into_iter(self) -> Self::IntoIter {
562        MapIntoIter {
563            keys: self.keys.into_iter(),
564            values: self.values.into_iter(),
565        }
566    }
567}
568
569impl<'a, K, V> IntoIterator for &'a Map<K, V> {
570    type Item = (&'a K, &'a V);
571    type IntoIter = core::iter::Zip<core::slice::Iter<'a, K>, core::slice::Iter<'a, V>>;
572
573    fn into_iter(self) -> Self::IntoIter {
574        self.keys.iter().zip(self.values.iter())
575    }
576}
577
578/// An iterator over owned key-value pairs.
579pub struct MapIntoIter<K, V> {
580    keys: VecIntoIter<K>,
581    values: VecIntoIter<V>,
582}
583
584impl<K, V> Iterator for MapIntoIter<K, V> {
585    type Item = (K, V);
586
587    fn next(&mut self) -> Option<Self::Item> {
588        let key = self.keys.next()?;
589        let value = self.values.next()?;
590        Some((key, value))
591    }
592
593    fn size_hint(&self) -> (usize, Option<usize>) {
594        self.keys.size_hint()
595    }
596}
597
598impl<K, V> ExactSizeIterator for MapIntoIter<K, V> {}
599
600impl<K, V> DoubleEndedIterator for MapIntoIter<K, V> {
601    fn next_back(&mut self) -> Option<Self::Item> {
602        let key = self.keys.next_back()?;
603        let value = self.values.next_back()?;
604        Some((key, value))
605    }
606}
607
608#[cfg(feature = "arbitrary")]
609impl<K, V> arbitrary::Arbitrary<'_> for Map<K, V>
610where
611    K: for<'a> arbitrary::Arbitrary<'a> + Ord,
612    V: for<'a> arbitrary::Arbitrary<'a>,
613{
614    fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result<Self> {
615        let vec = Vec::<(K, V)>::arbitrary(u)?;
616        Ok(Self::from_iter_dedup(vec))
617    }
618}
619
620/// An ordered, deduplicated collection of key-value pairs with unique values.
621#[derive(Clone, PartialEq, Eq, Hash)]
622pub struct BiMap<K, V> {
623    inner: Map<K, V>,
624}
625
626impl<K, V> Default for BiMap<K, V> {
627    fn default() -> Self {
628        Self {
629            inner: Map::default(),
630        }
631    }
632}
633
634impl<K, V> BiMap<K, V> {
635    /// Returns the number of entries in the map.
636    pub const fn len(&self) -> usize {
637        self.inner.len()
638    }
639
640    /// Returns `true` if the map is empty.
641    pub const fn is_empty(&self) -> bool {
642        self.inner.is_empty()
643    }
644
645    /// Returns a key by index, if it exists.
646    pub fn get(&self, index: usize) -> Option<&K> {
647        self.inner.get(index)
648    }
649
650    /// Returns the position of the provided key, if it exists.
651    pub fn position(&self, key: &K) -> Option<usize>
652    where
653        K: Ord,
654    {
655        self.inner.position(key)
656    }
657
658    /// Returns the ordered keys as a [`Set`] reference.
659    pub const fn keys(&self) -> &Set<K> {
660        self.inner.keys()
661    }
662
663    /// Consumes the map and returns the ordered keys.
664    pub fn into_keys(self) -> Set<K> {
665        self.inner.into_keys()
666    }
667
668    /// Returns the associated value at `index`, if it exists.
669    pub fn value(&self, index: usize) -> Option<&V> {
670        self.inner.value(index)
671    }
672
673    /// Returns the associated value for `key`, if it exists.
674    pub fn get_value(&self, key: &K) -> Option<&V>
675    where
676        K: Ord,
677    {
678        self.inner.get_value(key)
679    }
680
681    /// Returns the associated key for `value`, if it exists.
682    pub fn get_key(&self, value: &V) -> Option<&K>
683    where
684        V: PartialEq,
685    {
686        self.inner
687            .values()
688            .iter()
689            .position(|v| v == value)
690            .map(|idx| &self.inner.keys()[idx])
691    }
692
693    /// Returns the associated values.
694    pub fn values(&self) -> &[V] {
695        self.inner.values()
696    }
697
698    /// Returns a zipped iterator over keys and values.
699    pub fn iter_pairs(&self) -> impl Iterator<Item = (&K, &V)> {
700        self.inner.iter_pairs()
701    }
702
703    /// Returns an iterator over the ordered keys.
704    pub fn iter(&self) -> core::slice::Iter<'_, K> {
705        self.inner.iter()
706    }
707}
708
709impl<K: Ord, V: Eq + Hash> TryFromIterator<(K, V)> for BiMap<K, V> {
710    type Error = Error;
711
712    /// Attempts to create a [`BiMap`] from an iterator of key-value pairs.
713    ///
714    /// Returns an error if any key or value is duplicated.
715    fn try_from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Result<Self, Self::Error> {
716        let map = <Map<K, V> as TryFromIterator<(K, V)>>::try_from_iter(iter)?;
717        Self::try_from(map)
718    }
719}
720
721impl<K, V: Eq + Hash> TryFrom<Map<K, V>> for BiMap<K, V> {
722    type Error = Error;
723
724    fn try_from(map: Map<K, V>) -> Result<Self, Self::Error> {
725        {
726            let mut seen = HashSet::with_capacity_and_hasher(map.values.len(), Hasher::default());
727            for value in map.values.iter() {
728                if !seen.insert(value) {
729                    return Err(Error::DuplicateValue);
730                }
731            }
732        }
733        Ok(Self { inner: map })
734    }
735}
736
737impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for BiMap<K, V> {
738    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
739        f.debug_tuple("BiMap")
740            .field(&self.inner.iter_pairs().collect::<Vec<_>>())
741            .finish()
742    }
743}
744
745impl<K: fmt::Display, V: fmt::Display> fmt::Display for BiMap<K, V> {
746    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
747        write!(f, "[")?;
748        for (i, (key, value)) in self.iter_pairs().enumerate() {
749            if i > 0 {
750                write!(f, ", ")?;
751            }
752            write!(f, "({key}, {value})")?;
753        }
754        write!(f, "]")
755    }
756}
757
758impl<K, V> AsRef<[K]> for BiMap<K, V> {
759    fn as_ref(&self) -> &[K] {
760        self.inner.as_ref()
761    }
762}
763
764impl<K, V> AsRef<Set<K>> for BiMap<K, V> {
765    fn as_ref(&self) -> &Set<K> {
766        self.inner.as_ref()
767    }
768}
769
770impl<K, V> Deref for BiMap<K, V> {
771    type Target = Set<K>;
772
773    fn deref(&self) -> &Self::Target {
774        &self.inner
775    }
776}
777
778impl<K: Ord + Clone, V: Clone + Eq + Hash> TryFrom<&[(K, V)]> for BiMap<K, V> {
779    type Error = Error;
780
781    fn try_from(items: &[(K, V)]) -> Result<Self, Self::Error> {
782        Self::try_from_iter(items.iter().cloned())
783    }
784}
785
786impl<K: Ord, V: Eq + Hash> TryFrom<Vec<(K, V)>> for BiMap<K, V> {
787    type Error = Error;
788
789    fn try_from(items: Vec<(K, V)>) -> Result<Self, Self::Error> {
790        Self::try_from_iter(items)
791    }
792}
793
794impl<K: Ord, V: Eq + Hash, const N: usize> TryFrom<[(K, V); N]> for BiMap<K, V> {
795    type Error = Error;
796
797    fn try_from(items: [(K, V); N]) -> Result<Self, Self::Error> {
798        Self::try_from_iter(items)
799    }
800}
801
802impl<K: Ord + Clone, V: Clone + Eq + Hash, const N: usize> TryFrom<&[(K, V); N]> for BiMap<K, V> {
803    type Error = Error;
804
805    fn try_from(items: &[(K, V); N]) -> Result<Self, Self::Error> {
806        Self::try_from(items.as_slice())
807    }
808}
809
810impl<K, V> From<BiMap<K, V>> for Vec<(K, V)> {
811    fn from(wrapped: BiMap<K, V>) -> Self {
812        wrapped.inner.into()
813    }
814}
815
816impl<K: Write, V: Write> Write for BiMap<K, V> {
817    fn write(&self, buf: &mut impl BufMut) {
818        self.inner.write(buf);
819    }
820}
821
822impl<K: EncodeSize, V: EncodeSize> EncodeSize for BiMap<K, V> {
823    fn encode_size(&self) -> usize {
824        self.inner.encode_size()
825    }
826}
827
828impl<K: Read + Ord, V: Eq + Hash + Read> Read for BiMap<K, V> {
829    type Cfg = (RangeCfg<usize>, K::Cfg, V::Cfg);
830
831    fn read_cfg(buf: &mut impl Buf, cfg: &Self::Cfg) -> Result<Self, commonware_codec::Error> {
832        let inner = Map::<K, V>::read_cfg(buf, cfg)?;
833        Self::try_from(inner).map_err(|_| {
834            commonware_codec::Error::Invalid(
835                "BiMap",
836                "duplicate value detected during deserialization",
837            )
838        })
839    }
840}
841
842impl<K, V> IntoIterator for BiMap<K, V> {
843    type Item = (K, V);
844    type IntoIter = MapIntoIter<K, V>;
845
846    fn into_iter(self) -> Self::IntoIter {
847        self.inner.into_iter()
848    }
849}
850
851impl<'a, K, V> IntoIterator for &'a BiMap<K, V> {
852    type Item = (&'a K, &'a V);
853    type IntoIter = core::iter::Zip<core::slice::Iter<'a, K>, core::slice::Iter<'a, V>>;
854
855    fn into_iter(self) -> Self::IntoIter {
856        self.inner.iter().zip(self.inner.values().iter())
857    }
858}
859
860#[cfg(feature = "arbitrary")]
861impl<K, V> arbitrary::Arbitrary<'_> for BiMap<K, V>
862where
863    K: for<'a> arbitrary::Arbitrary<'a> + Ord,
864    V: for<'a> arbitrary::Arbitrary<'a> + Ord + Eq + Hash,
865{
866    fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result<Self> {
867        let mut vec = Vec::<(K, V)>::arbitrary(u)?;
868        vec.sort_by(|(lk, _), (rk, _)| lk.cmp(rk));
869        vec.dedup_by(|l, r| l.0 == r.0);
870        vec.sort_by(|(_, lv), (_, rv)| lv.cmp(rv));
871        vec.dedup_by(|l, r| l.1 == r.1);
872        Self::try_from_iter(vec).map_err(|_| arbitrary::Error::IncorrectFormat)
873    }
874}
875
876#[cfg(test)]
877mod test {
878    use super::*;
879
880    #[test]
881    fn test_sorted_unique_construct_unseal() {
882        const CASE: [u8; 12] = [1, 3, 2, 5, 4, 3, 1, 7, 9, 6, 8, 4];
883        const EXPECTED: [u8; 9] = [1, 2, 3, 4, 5, 6, 7, 8, 9];
884
885        let sorted = Set::from_iter_dedup(CASE);
886        assert_eq!(sorted.iter().copied().collect::<Vec<_>>(), EXPECTED);
887
888        let unsealed: Vec<_> = sorted.into();
889        assert_eq!(unsealed, EXPECTED);
890    }
891
892    #[test]
893    fn test_sorted_unique_codec_roundtrip() {
894        const CASE: [u8; 9] = [1, 2, 3, 4, 5, 6, 7, 8, 9];
895        let sorted: Set<_> = CASE.try_into().unwrap();
896
897        let mut buf = Vec::with_capacity(sorted.encode_size());
898        sorted.write(&mut buf);
899        let decoded =
900            Set::<u8>::read_cfg(&mut buf.as_slice(), &(RangeCfg::from(0..=9), ())).unwrap();
901
902        assert_eq!(sorted, decoded);
903    }
904
905    #[test]
906    fn test_sorted_unique_display() {
907        const CASE: [u8; 9] = [1, 2, 3, 4, 5, 6, 7, 8, 9];
908
909        #[derive(Ord, PartialOrd, Eq, PartialEq)]
910        struct Example(u8);
911        impl fmt::Display for Example {
912            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
913                write!(f, "ex({})", self.0)
914            }
915        }
916        let sorted: Set<_> = Set::try_from_iter(CASE.into_iter().map(Example)).unwrap();
917        assert_eq!(
918            sorted.to_string(),
919            "[ex(1), ex(2), ex(3), ex(4), ex(5), ex(6), ex(7), ex(8), ex(9)]"
920        );
921    }
922
923    #[test]
924    fn test_set_from_iter_dedup() {
925        let items = [3u8, 1u8, 2u8, 2u8];
926        let set = Set::from_iter_dedup(items);
927        assert_eq!(set.iter().copied().collect::<Vec<_>>(), vec![1, 2, 3]);
928    }
929
930    #[test]
931    fn test_set_try_from_duplicate() {
932        let result: Result<Set<u8>, _> = vec![3u8, 1u8, 2u8, 2u8].try_into();
933        assert_eq!(result, Err(Error::DuplicateKey));
934    }
935
936    #[test]
937    fn test_set_try_from_iter_duplicate() {
938        let items = vec![3u8, 1u8, 2u8, 2u8];
939        let result = Set::try_from_iter(items);
940        assert_eq!(result, Err(Error::DuplicateKey));
941    }
942
943    #[test]
944    fn test_map_from_iter_dedup() {
945        let items = vec![(3u8, "c"), (1u8, "a"), (2u8, "b"), (1u8, "duplicate")];
946        let map = Map::from_iter_dedup(items);
947
948        assert_eq!(map.len(), 3);
949        assert_eq!(map.iter().copied().collect::<Vec<_>>(), vec![1, 2, 3]);
950        assert_eq!(map.get_value(&1), Some(&"a"));
951        assert_eq!(map.get_value(&4), None);
952        assert_eq!(map.value(1), Some(&"b"));
953    }
954
955    #[test]
956    fn test_map_try_from() {
957        let pairs = vec![(3u8, "c"), (1u8, "a"), (2u8, "b")];
958        let wrapped: Map<_, _> = pairs.try_into().unwrap();
959
960        assert_eq!(wrapped.iter().copied().collect::<Vec<_>>(), vec![1, 2, 3]);
961        assert_eq!(wrapped.get_value(&2), Some(&"b"));
962    }
963
964    #[test]
965    fn test_map_try_from_duplicate() {
966        let result: Result<Map<u8, &str>, _> =
967            vec![(3u8, "c"), (1u8, "a"), (2u8, "b"), (1u8, "duplicate")].try_into();
968        assert_eq!(result, Err(Error::DuplicateKey));
969    }
970
971    #[test]
972    fn test_map_try_from_iter_duplicate() {
973        let pairs = vec![(3u8, "c"), (1u8, "a"), (2u8, "b"), (1u8, "duplicate")];
974        let result = Map::try_from_iter(pairs);
975        assert_eq!(result, Err(Error::DuplicateKey));
976    }
977
978    #[test]
979    fn test_map_deref_to_set() {
980        fn sum(set: &Set<u8>) -> u32 {
981            set.iter().map(|v| *v as u32).sum()
982        }
983
984        let map: Map<_, _> = vec![(2u8, "b"), (1u8, "a")].try_into().unwrap();
985        assert_eq!(sum(&map), 3);
986    }
987
988    #[test]
989    fn test_map_from_set() {
990        let set: Set<_> = vec![(3u8, 'a'), (1u8, 'b'), (2u8, 'c')].try_into().unwrap();
991        let wrapped: Map<_, _> = Map::try_from_iter(set.clone()).unwrap();
992
993        assert_eq!(
994            set.iter().map(|(k, _)| *k).collect::<Vec<_>>(),
995            wrapped.keys().iter().copied().collect::<Vec<_>>(),
996        );
997    }
998
999    #[test]
1000    fn test_map_into_keys() {
1001        let map: Map<_, _> = vec![(3u8, "c"), (1u8, "a"), (2u8, "b")].try_into().unwrap();
1002        let keys = map.into_keys();
1003        assert_eq!(keys.iter().copied().collect::<Vec<_>>(), vec![1, 2, 3]);
1004    }
1005
1006    #[test]
1007    fn test_values_mut() {
1008        let mut map: Map<u8, u8> = vec![(1u8, 10u8), (2, 20)].try_into().unwrap();
1009        for value in map.values_mut() {
1010            *value += 1;
1011        }
1012        assert_eq!(map.values(), &[11, 21]);
1013    }
1014
1015    #[test]
1016    fn test_map_allows_duplicate_values() {
1017        let items = vec![(1u8, "a"), (2u8, "b"), (3u8, "a")];
1018        let map: Map<_, _> = items.try_into().unwrap();
1019        assert_eq!(map.len(), 3);
1020        assert_eq!(map.get_value(&1), Some(&"a"));
1021        assert_eq!(map.get_value(&3), Some(&"a"));
1022    }
1023
1024    #[test]
1025    fn test_bimap_duplicate_value_error() {
1026        let items = vec![(1u8, "a"), (2u8, "b"), (3u8, "a")];
1027        let result = BiMap::try_from_iter(items);
1028        assert_eq!(result, Err(Error::DuplicateValue));
1029    }
1030
1031    #[test]
1032    fn test_bimap_no_duplicate_values() {
1033        let items = vec![(1u8, "a"), (2u8, "b"), (3u8, "c")];
1034        let result = BiMap::try_from_iter(items);
1035        assert!(result.is_ok());
1036        let map = result.unwrap();
1037        assert_eq!(map.len(), 3);
1038        assert_eq!(map.get_value(&1), Some(&"a"));
1039        assert_eq!(map.get_value(&2), Some(&"b"));
1040        assert_eq!(map.get_value(&3), Some(&"c"));
1041    }
1042
1043    #[test]
1044    fn test_bimap_try_from_map() {
1045        let items = vec![(1u8, "a"), (2u8, "b"), (3u8, "c")];
1046        let map: Map<_, _> = items.try_into().unwrap();
1047        let bimap = BiMap::try_from(map).unwrap();
1048        assert_eq!(bimap.len(), 3);
1049        assert_eq!(bimap.get_value(&1), Some(&"a"));
1050    }
1051
1052    #[test]
1053    fn test_bimap_get_key() {
1054        let items = vec![(1u8, "a"), (2u8, "b"), (3u8, "c")];
1055        let bimap: BiMap<_, _> = items.try_into().unwrap();
1056        assert_eq!(bimap.get_key(&"a"), Some(&1));
1057        assert_eq!(bimap.get_key(&"b"), Some(&2));
1058        assert_eq!(bimap.get_key(&"c"), Some(&3));
1059        assert_eq!(bimap.get_key(&"d"), None);
1060    }
1061
1062    #[test]
1063    fn test_bimap_try_from_map_duplicate() {
1064        let items = vec![(1u8, "a"), (2u8, "b"), (3u8, "a")];
1065        let map: Map<_, _> = items.try_into().unwrap();
1066        let result = BiMap::try_from(map);
1067        assert_eq!(result, Err(Error::DuplicateValue));
1068    }
1069
1070    #[test]
1071    fn test_bimap_decode_rejects_duplicate_values() {
1072        let items = vec![(1u8, 10u8), (2, 20), (3, 10)];
1073        let map: Map<_, _> = items.try_into().unwrap();
1074
1075        let mut buf = Vec::with_capacity(map.encode_size());
1076        map.write(&mut buf);
1077
1078        let cfg = (RangeCfg::from(0..=10), (), ());
1079        let result = BiMap::<u8, u8>::read_cfg(&mut buf.as_slice(), &cfg);
1080        assert!(result.is_err());
1081    }
1082
1083    #[test]
1084    fn test_set_decode_rejects_duplicates() {
1085        let items: Vec<u8> = vec![1, 2, 2, 3];
1086        let mut buf = Vec::new();
1087        items.write(&mut buf);
1088
1089        let cfg = (RangeCfg::from(0..=10), ());
1090        let result = Set::<u8>::read_cfg(&mut buf.as_slice(), &cfg);
1091        assert!(result.is_err());
1092    }
1093
1094    #[test]
1095    fn test_set_decode_rejects_unsorted() {
1096        let items: Vec<u8> = vec![1, 3, 2, 4];
1097        let mut buf = Vec::new();
1098        items.write(&mut buf);
1099
1100        let cfg = (RangeCfg::from(0..=10), ());
1101        let result = Set::<u8>::read_cfg(&mut buf.as_slice(), &cfg);
1102        assert!(result.is_err());
1103    }
1104
1105    #[test]
1106    fn test_set_decode_accepts_valid() {
1107        let items: Vec<u8> = vec![1, 2, 3, 4];
1108        let mut buf = Vec::new();
1109        items.write(&mut buf);
1110
1111        let cfg = (RangeCfg::from(0..=10), ());
1112        let result = Set::<u8>::read_cfg(&mut buf.as_slice(), &cfg);
1113        assert!(result.is_ok());
1114        assert_eq!(result.unwrap().iter().copied().collect::<Vec<_>>(), items);
1115    }
1116
1117    #[test]
1118    fn test_map_decode_rejects_duplicate_keys() {
1119        let keys: Vec<u8> = vec![1, 2, 2, 3];
1120        let values: Vec<u8> = vec![10, 20, 30, 40];
1121        let mut buf = Vec::new();
1122        keys.write(&mut buf);
1123        values.write(&mut buf);
1124
1125        let cfg = (RangeCfg::from(0..=10), (), ());
1126        let result = Map::<u8, u8>::read_cfg(&mut buf.as_slice(), &cfg);
1127        assert!(result.is_err());
1128    }
1129
1130    #[test]
1131    fn test_map_decode_rejects_unsorted_keys() {
1132        let keys: Vec<u8> = vec![1, 3, 2, 4];
1133        let values: Vec<u8> = vec![10, 20, 30, 40];
1134        let mut buf = Vec::new();
1135        keys.write(&mut buf);
1136        values.write(&mut buf);
1137
1138        let cfg = (RangeCfg::from(0..=10), (), ());
1139        let result = Map::<u8, u8>::read_cfg(&mut buf.as_slice(), &cfg);
1140        assert!(result.is_err());
1141    }
1142
1143    #[test]
1144    fn test_map_decode_accepts_valid() {
1145        let keys: Vec<u8> = vec![1, 2, 3, 4];
1146        let values: Vec<u8> = vec![10, 20, 30, 40];
1147        let mut buf = Vec::new();
1148        keys.write(&mut buf);
1149        values.write(&mut buf);
1150
1151        let cfg = (RangeCfg::from(0..=10), (), ());
1152        let result = Map::<u8, u8>::read_cfg(&mut buf.as_slice(), &cfg);
1153        assert!(result.is_ok());
1154        let map = result.unwrap();
1155        assert_eq!(map.keys().iter().copied().collect::<Vec<_>>(), keys);
1156        assert_eq!(map.values(), values.as_slice());
1157    }
1158
1159    #[cfg(feature = "arbitrary")]
1160    mod conformance {
1161        use super::*;
1162        use commonware_codec::conformance::CodecConformance;
1163
1164        commonware_conformance::conformance_tests! {
1165            CodecConformance<Set<u32>>,
1166            CodecConformance<Map<u32, u32>>,
1167            CodecConformance<BiMap<u32, u32>>,
1168        }
1169    }
1170}
commonware_utils/ordered.rs

commonware_utils/
ordered.rs
