total_maps/
lib.rs

1//! Maps where every possible key has an associated value.
2//!
3//! Only entries with *uncommon* values are actually stored in the map; all other keys are presumed
4//! to be associated with a *common* value. The definition of "common" and "uncommon" is determined
5//! by the map's optional [Commonality] type parameter; if unspecified, the map will use
6//! [DefaultCommonality], which uses the standard [Default] trait to provide the common value.
7//!
8//! [TotalHashMap] and [TotalBTreeMap] are the main data structures provided by this crate.
9
10use std::{
11    fmt::{self, Debug, Formatter},
12    marker::PhantomData,
13};
14
15#[cfg(feature = "num-traits")]
16pub use self::nonzero::{NonZeroBTreeMap, NonZeroHashMap, ZeroCommonality};
17pub use self::{btree_map::TotalBTreeMap, empty::EmptyCommonality, hash_map::TotalHashMap};
18
19pub mod btree_map;
20pub mod empty;
21pub mod hash_map;
22#[cfg(feature = "num-traits")]
23pub mod nonzero;
24#[cfg(feature = "serde")]
25mod serde;
26
27// --------------------------------------------------------------------------
28
29/// Defines a notion of "common" vs. "uncommon" values for the type `V`, used to determine which
30/// entries are stored in a [TotalHashMap] or [TotalBTreeMap].
31///
32/// There could be multiple definitions of commonality for the same type:
33///
34/// - The basic implementation, [DefaultCommonality], is based on the [Default] trait.
35/// - [EmptyCommonality] is specialized for collection types.
36#[cfg_attr(
37    feature = "num-traits",
38    doc = "- [ZeroCommonality] is based on the [num_traits::Zero] trait."
39)]
40pub trait Commonality<V> {
41    /// The common value of type `V`.
42    ///
43    /// *Important:* The implementations of [PartialEq], [Eq], [PartialOrd], [Ord], and
44    /// [Hash](std::hash::Hash) for [TotalHashMap] and [TotalBTreeMap] treat all common values as
45    /// though they were equal to each other,, even if they aren't really. For example, if you
46    /// defined a `Commonality<f64>` implementation where `common()` returned [f64::NAN], maps based
47    /// on this commonality could still be equal to each other, despite the fact that [f64::NAN] is
48    /// not equal to itself.
49    fn common() -> V;
50
51    /// Returns true if `value` is the common value of type `V`. `Self::is_common(Self::common())`
52    /// must be true.
53    fn is_common(value: &V) -> bool;
54}
55
56/// A [commonality](Commonality) based on the [Default] and [PartialEq] traits.
57///
58/// *Important:* This type's implementation of [Commonality] is valid only if `T::default() ==
59/// T::default()`. Any type with a valid [Eq] implementation satisfies this requirement, but many
60/// types like `f64` and `Vec<f64>` also satisfy this requirement, despite not implementing [Eq].
61///
62/// A [TotalHashMap] or [TotalBTreeMap] using this commonality only stores entries with non-default
63/// values.
64pub struct DefaultCommonality(());
65impl<T: PartialEq + Default> Commonality<T> for DefaultCommonality {
66    // The bound on T is PartialEq (instead of Eq) to allow non-Eq types like f64 and Vec<f64>. The
67    // unchecked reflexivity requirement specified in the docs is gross, but unlikely to be violated
68    // in normal usage.
69    //
70    // A more principled way to handle this requirement would be to define a marker trait
71    // `DefaultEq: PartialEq + Default` and specify the requirement as a "law" of the trait, and
72    // then insist that users implement this trait only when the law holds (similar to how Eq itself
73    // is a marker trait with its own reflexivity law). But implementing this marker trait would be
74    // an annoyance in the best case, and impossible (due to the orphan rule) in the worst case.
75
76    fn common() -> T {
77        T::default()
78    }
79    fn is_common(value: &T) -> bool {
80        value == &T::default()
81    }
82}
83
84struct PhantomPtr<T>(PhantomData<*const T>);
85impl<T> Default for PhantomPtr<T> {
86    fn default() -> Self {
87        Self(PhantomData)
88    }
89}
90impl<T> Debug for PhantomPtr<T> {
91    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
92        f.debug_tuple("PhantomPtr").field(&self.0).finish()
93    }
94}
95unsafe impl<T> Send for PhantomPtr<T> {}
96unsafe impl<T> Sync for PhantomPtr<T> {}
total_maps/lib.rs

total_maps/
lib.rs
