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

commonware_utils/
ordered.rs
