delta_struct/
bag.rs

1//! Membership diffing, behind the `unordered` field type.
2//!
3//! A field marked `#[delta_struct(field_type = "unordered")]` is treated as a
4//! bag of elements whose order carries no meaning, and represented as a
5//! [`BagDelta`] — which elements came and which went, and nothing about where
6//! they sit.
7//!
8//! The derive emits calls to [`diff`] and [`apply`]; you only need this module
9//! directly to inspect or construct a delta by hand.
10
11use crate::TryIndex;
12
13/// A membership diff between two collections: what arrived and what left.
14///
15/// Nothing here records position — see [`SeqDelta`](crate::SeqDelta) for that.
16#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
17#[derive(Clone, Debug, PartialEq, Eq)]
18pub struct BagDelta<T> {
19    /// Elements in the new collection that the old one did not have.
20    pub add: Vec<T>,
21    /// Elements in the old collection that the new one does not have.
22    pub remove: Vec<T>,
23}
24
25impl<T> BagDelta<T> {
26    /// Whether the two collections held the same elements, and so nothing
27    /// needs sending.
28    pub fn is_empty(&self) -> bool {
29        self.add.is_empty() && self.remove.is_empty()
30    }
31}
32
33impl<T> Default for BagDelta<T> {
34    fn default() -> Self {
35        BagDelta {
36            add: Vec::new(),
37            remove: Vec::new(),
38        }
39    }
40}
41
42/// Computes which elements `new` gained and which `old` lost.
43///
44/// Returns an empty [`BagDelta`] when the two hold the same elements. Each
45/// element of `old` is looked up in `new` exactly once, through the
46/// collection's own [`TryIndex`] implementation, so the cost is that of n
47/// lookups: O(n) for a [`HashSet`](std::collections::HashSet), O(n log n) for
48/// a [`BTreeSet`](std::collections::BTreeSet).
49///
50/// ```
51/// use delta_struct::bag::diff;
52/// use std::collections::BTreeSet;
53///
54/// let old: BTreeSet<i32> = vec![1, 2, 3].into_iter().collect();
55/// let new: BTreeSet<i32> = vec![3, 4, 5].into_iter().collect();
56///
57/// let delta = diff(old, new);
58/// assert_eq!(delta.add, vec![4, 5]);
59/// assert_eq!(delta.remove, vec![1, 2]);
60/// ```
61pub fn diff<C, T>(old: C, mut new: C) -> BagDelta<T>
62where
63    C: IntoIterator<Item = T> + TryIndex<T, Output = T>,
64{
65    // Take each of `old`'s elements out of `new` as it is matched, so whatever
66    // is still standing at the end is exactly what was added, and no second
67    // pass is needed to work that out.
68    let remove = old
69        .into_iter()
70        .filter(|element| new.try_remove(element).is_none())
71        .collect();
72    BagDelta {
73        add: new.into_iter().collect(),
74        remove,
75    }
76}
77
78/// Applies a membership diff to `target` in place.
79///
80/// Each removal is a single lookup rather than a scan, so this costs the same
81/// as [`diff`] does. Membership is preserved but position is not — additions
82/// land wherever the collection decides to put them. Use `ordered` where that
83/// matters.
84///
85/// A removal that `target` does not have is ignored, which makes applying the
86/// same delta twice harmless.
87///
88/// ```
89/// use delta_struct::bag::{apply, diff};
90/// use std::collections::BTreeSet;
91///
92/// let set = |items: Vec<i32>| items.into_iter().collect::<BTreeSet<i32>>();
93///
94/// let delta = diff(set(vec![1, 2, 3]), set(vec![2, 3, 4]));
95/// let mut target = set(vec![1, 2, 3]);
96/// apply(&mut target, delta);
97/// assert_eq!(target, set(vec![2, 3, 4]));
98/// ```
99pub fn apply<C, T>(target: &mut C, delta: BagDelta<T>)
100where
101    C: IntoIterator<Item = T> + Extend<T> + TryIndex<T, Output = T>,
102{
103    for element in delta.remove {
104        target.try_remove(&element);
105    }
106    target.extend(delta.add);
107}
delta_struct/bag.rs

delta_struct/
bag.rs
