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

commonware_utils/
ordered.rs
