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

commonware_utils/
ordered.rs
