delta_struct/
index.rs

1//! Fallible lookup, the operation the `unordered` field types diff through.
2//!
3//! [`std::ops::Index`] cannot express a diff: it panics when the element is
4//! absent, and "is this element on the other side?" is the only question a
5//! membership diff asks. [`TryIndex`] is that trait with the answer made
6//! fallible, which is what lets [`bag`](crate::bag) and [`map`](crate::map)
7//! push the lookup down into the collection instead of scanning it.
8//!
9//! The consequence is that a field's cost is the cost of the collection you
10//! picked: a diff over a [`HashSet`] or [`HashMap`] is O(n), and over a
11//! [`BTreeSet`] or [`BTreeMap`] it is O(n log n).
12
13use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
14use std::hash::{BuildHasher, Hash};
15
16/// A collection that can look an element up by key without panicking when it
17/// is not there.
18///
19/// This is [`std::ops::Index`] with the failure made visible, plus the owning
20/// counterpart that the index operator has no equivalent of.
21pub trait TryIndex<Idx: ?Sized> {
22    /// What is stored under a key: the value for a map, and the element
23    /// itself for a set.
24    type Output;
25
26    /// Borrows the element stored under `index`, or [`None`] if there is none.
27    fn try_index(&self, index: &Idx) -> Option<&Self::Output>;
28
29    /// Removes the element stored under `index` and returns it, or [`None`] if
30    /// there was none.
31    fn try_remove(&mut self, index: &Idx) -> Option<Self::Output>;
32}
33
34/// A [`TryIndex`] whose elements can also be modified in place.
35pub trait TryIndexMut<Idx: ?Sized>: TryIndex<Idx> {
36    /// Mutably borrows the element stored under `index`, or [`None`] if there
37    /// is none.
38    fn try_index_mut(&mut self, index: &Idx) -> Option<&mut Self::Output>;
39}
40
41impl<K, V, S> TryIndex<K> for HashMap<K, V, S>
42where
43    K: Hash + Eq,
44    S: BuildHasher,
45{
46    type Output = V;
47
48    fn try_index(&self, index: &K) -> Option<&V> {
49        self.get(index)
50    }
51
52    fn try_remove(&mut self, index: &K) -> Option<V> {
53        self.remove(index)
54    }
55}
56
57impl<K, V, S> TryIndexMut<K> for HashMap<K, V, S>
58where
59    K: Hash + Eq,
60    S: BuildHasher,
61{
62    fn try_index_mut(&mut self, index: &K) -> Option<&mut V> {
63        self.get_mut(index)
64    }
65}
66
67impl<K, V> TryIndex<K> for BTreeMap<K, V>
68where
69    K: Ord,
70{
71    type Output = V;
72
73    fn try_index(&self, index: &K) -> Option<&V> {
74        self.get(index)
75    }
76
77    fn try_remove(&mut self, index: &K) -> Option<V> {
78        self.remove(index)
79    }
80}
81
82impl<K, V> TryIndexMut<K> for BTreeMap<K, V>
83where
84    K: Ord,
85{
86    fn try_index_mut(&mut self, index: &K) -> Option<&mut V> {
87        self.get_mut(index)
88    }
89}
90
91impl<T, S> TryIndex<T> for HashSet<T, S>
92where
93    T: Hash + Eq,
94    S: BuildHasher,
95{
96    type Output = T;
97
98    fn try_index(&self, index: &T) -> Option<&T> {
99        self.get(index)
100    }
101
102    fn try_remove(&mut self, index: &T) -> Option<T> {
103        self.take(index)
104    }
105}
106
107impl<T> TryIndex<T> for BTreeSet<T>
108where
109    T: Ord,
110{
111    type Output = T;
112
113    fn try_index(&self, index: &T) -> Option<&T> {
114        self.get(index)
115    }
116
117    fn try_remove(&mut self, index: &T) -> Option<T> {
118        self.take(index)
119    }
120}
delta_struct/index.rs

delta_struct/
index.rs
