delta_struct/
bag.rs

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

delta_struct/
bag.rs
