morphix/impls/collections/
btree_set.rs

1//! Observer implementation for [`BTreeSet<T>`].
2
3use std::borrow::Borrow;
4use std::collections::BTreeSet;
5use std::fmt::Debug;
6use std::marker::PhantomData;
7use std::ops::{Deref, DerefMut};
8
9use serde::Serialize;
10
11use crate::general::Snapshot;
12use crate::helper::macros::default_impl_ref_observe;
13use crate::helper::{AsDeref, AsDerefMut, ObserverState, Pointer, QuasiObserver, Succ, Unsigned, Zero};
14use crate::observe::{DefaultSpec, Observer, SerializeObserver};
15use crate::{Mutations, Observe};
16
17struct BTreeSetObserverState<T> {
18    /// The last element (inclusive) of the common prefix between the old and current set.
19    /// `None` means the prefix is empty (either the set was initially empty, or all original
20    /// elements have been moved to the tail).
21    boundary: Option<T>,
22    /// Number of elements in the *original* set (at last flush/observe) that are strictly
23    /// after `boundary`. This becomes `truncate_len` on flush.
24    truncate_len: usize,
25}
26
27impl<T> Default for BTreeSetObserverState<T> {
28    fn default() -> Self {
29        Self {
30            boundary: None,
31            truncate_len: 0,
32        }
33    }
34}
35
36impl<T: Clone + Ord> BTreeSetObserverState<T> {
37    /// Move all original elements in `[v, boundary]` from the prefix into the tail,
38    /// then shrink `boundary` to the predecessor of `v`.
39    fn shrink_boundary(&mut self, v: &T, set: &BTreeSet<T>) {
40        let boundary = self.boundary.as_ref().unwrap();
41        self.truncate_len += set.range(v..=boundary).count();
42        self.boundary = set.range(..v).next_back().cloned();
43    }
44}
45
46impl<T: Clone + Ord> ObserverState for BTreeSetObserverState<T> {
47    type Target = BTreeSet<T>;
48
49    fn invalidate(this: &mut Self, set: &BTreeSet<T>) {
50        if let Some(boundary) = this.boundary.take() {
51            this.truncate_len += set.range(..=boundary).count();
52        }
53    }
54}
55
56/// Observer implementation for [`BTreeSet<T>`].
57///
58/// Tracks granular mutations by maintaining a prefix boundary. Elements up to and including
59/// the boundary are unchanged from the last flush; elements beyond the boundary form the
60/// "tail" region that will be emitted as [`Truncate`](crate::MutationKind::Truncate) /
61/// [`Append`](crate::MutationKind::Append) mutations.
62///
63/// ## Limitations
64///
65/// Most methods require `T: Clone` because the observer stores the boundary element.
66pub struct BTreeSetObserver<'ob, T, S: ?Sized, D = Zero> {
67    ptr: Pointer<S>,
68    state: BTreeSetObserverState<T>,
69    phantom: PhantomData<&'ob mut D>,
70}
71
72impl<'ob, T, S: ?Sized, D> Deref for BTreeSetObserver<'ob, T, S, D> {
73    type Target = Pointer<S>;
74
75    fn deref(&self) -> &Self::Target {
76        &self.ptr
77    }
78}
79
80impl<'ob, T, S: ?Sized, D> DerefMut for BTreeSetObserver<'ob, T, S, D> {
81    fn deref_mut(&mut self) -> &mut Self::Target {
82        std::ptr::from_mut(self).expose_provenance();
83        Pointer::invalidate(&mut self.ptr);
84        &mut self.ptr
85    }
86}
87
88impl<'ob, T, S: ?Sized, D> QuasiObserver for BTreeSetObserver<'ob, T, S, D>
89where
90    T: Clone + Ord,
91    D: Unsigned,
92    S: AsDeref<D, Target = BTreeSet<T>>,
93{
94    type Head = S;
95    type OuterDepth = Succ<Zero>;
96    type InnerDepth = D;
97
98    fn invalidate(this: &mut Self) {
99        ObserverState::invalidate(&mut this.state, (*this.ptr).as_deref());
100    }
101}
102
103impl<'ob, T, S: ?Sized, D> Observer for BTreeSetObserver<'ob, T, S, D>
104where
105    T: Clone + Ord,
106    D: Unsigned,
107    S: AsDerefMut<D, Target = BTreeSet<T>>,
108{
109    fn observe(head: &mut Self::Head) -> Self {
110        let this = Self {
111            state: BTreeSetObserverState {
112                boundary: head.as_deref_mut().last().cloned(),
113                truncate_len: 0,
114            },
115            ptr: Pointer::new(head),
116            phantom: PhantomData,
117        };
118        Pointer::register_state::<_, D>(&this.ptr, &this.state);
119        this
120    }
121
122    unsafe fn relocate(this: &mut Self, head: &mut Self::Head) {
123        Pointer::set(this, head);
124    }
125}
126
127impl<'ob, T, S: ?Sized, D> SerializeObserver for BTreeSetObserver<'ob, T, S, D>
128where
129    T: Serialize + Clone + Ord + 'static,
130    D: Unsigned,
131    S: AsDeref<D, Target = BTreeSet<T>>,
132{
133    unsafe fn flush(this: &mut Self) -> Mutations {
134        let set = (*this.ptr).as_deref();
135        let truncate_len = std::mem::replace(&mut this.state.truncate_len, 0);
136        let boundary = std::mem::replace(&mut this.state.boundary, set.last().cloned());
137
138        let prefix_len = match &boundary {
139            Some(b) => set.range(..=b).count(),
140            None => 0,
141        };
142        if prefix_len == 0 && truncate_len > 0 {
143            return Mutations::replace(set);
144        }
145
146        let mut mutations = Mutations::new();
147
148        #[cfg(feature = "truncate")]
149        if truncate_len > 0 {
150            mutations.extend(crate::MutationKind::Truncate(truncate_len));
151        }
152
153        #[cfg(feature = "append")]
154        {
155            // BTreeSet has no contiguous slice representation, so we collect the appended
156            // elements into an owned Vec and box it as the Append value.
157            let appended: Vec<T> = set.iter().skip(prefix_len).cloned().collect();
158            if !appended.is_empty() {
159                mutations.extend(crate::MutationKind::Append(
160                    Box::new(appended) as Box<dyn erased_serde::Serialize>
161                ));
162            }
163        }
164
165        mutations
166    }
167}
168
169impl<'ob, T, S: ?Sized, D> BTreeSetObserver<'ob, T, S, D>
170where
171    T: Clone + Ord,
172    D: Unsigned,
173    S: AsDerefMut<D, Target = BTreeSet<T>>,
174{
175    /// See [`BTreeSet::clear`].
176    pub fn clear(&mut self) {
177        if (*self).untracked_ref().is_empty() {
178            self.untracked_mut().clear()
179        } else {
180            self.tracked_mut().clear()
181        }
182    }
183
184    /// See [`BTreeSet::insert`].
185    pub fn insert(&mut self, value: T) -> bool {
186        if let Some(boundary) = &self.state.boundary
187            && value <= *boundary
188        {
189            let set = (*self.ptr).as_deref();
190            self.state.shrink_boundary(&value, set);
191        }
192        (*self.ptr).as_deref_mut().insert(value)
193    }
194
195    /// See [`BTreeSet::replace`].
196    pub fn replace(&mut self, value: T) -> Option<T> {
197        if let Some(boundary) = &self.state.boundary
198            && value <= *boundary
199        {
200            let set = (*self.ptr).as_deref();
201            self.state.shrink_boundary(&value, set);
202        }
203        (*self.ptr).as_deref_mut().replace(value)
204    }
205
206    /// See [`BTreeSet::remove`].
207    pub fn remove<Q>(&mut self, value: &Q) -> bool
208    where
209        T: Borrow<Q>,
210        Q: Ord + ?Sized,
211    {
212        if let Some(boundary) = &self.state.boundary
213            && let Some(found) = (*self.ptr).as_deref().get(value)
214            && found <= boundary
215        {
216            self.state.shrink_boundary(found, (*self.ptr).as_deref());
217        }
218        (*self.ptr).as_deref_mut().remove(value)
219    }
220
221    /// See [`BTreeSet::take`].
222    pub fn take<Q>(&mut self, value: &Q) -> Option<T>
223    where
224        T: Borrow<Q>,
225        Q: Ord + ?Sized,
226    {
227        if let Some(boundary) = &self.state.boundary
228            && let Some(found) = (*self.ptr).as_deref().get(value)
229            && found <= boundary
230        {
231            self.state.shrink_boundary(found, (*self.ptr).as_deref());
232        }
233        (*self.ptr).as_deref_mut().take(value)
234    }
235
236    /// See [`BTreeSet::pop_first`].
237    pub fn pop_first(&mut self) -> Option<T> {
238        let set = (*self.ptr).as_deref();
239        if let Some(first) = set.first()
240            && let Some(boundary) = &self.state.boundary
241            && first <= boundary
242        {
243            self.state.shrink_boundary(first, set);
244        }
245        (*self.ptr).as_deref_mut().pop_first()
246    }
247
248    /// See [`BTreeSet::pop_last`].
249    pub fn pop_last(&mut self) -> Option<T> {
250        let set = (*self.ptr).as_deref();
251        if let Some(last) = set.last()
252            && let Some(boundary) = &self.state.boundary
253            && last <= boundary
254        {
255            self.state.shrink_boundary(last, set);
256        }
257        (*self.ptr).as_deref_mut().pop_last()
258    }
259
260    /// See [`BTreeSet::retain`].
261    pub fn retain<F>(&mut self, f: F)
262    where
263        F: FnMut(&T) -> bool,
264    {
265        if (*self).untracked_ref().is_empty() {
266            self.untracked_mut().retain(f);
267        } else {
268            self.tracked_mut().retain(f);
269        }
270    }
271
272    /// See [`BTreeSet::append`].
273    pub fn append(&mut self, other: &mut BTreeSet<T>) {
274        for value in std::mem::take(other) {
275            self.insert(value);
276        }
277    }
278
279    /// See [`BTreeSet::split_off`].
280    pub fn split_off(&mut self, value: &T) -> BTreeSet<T> {
281        if let Some(boundary) = &self.state.boundary
282            && let Some(first_split) = (*self.ptr).as_deref().range(value..).next()
283            && first_split <= boundary
284        {
285            self.state.shrink_boundary(first_split, (*self.ptr).as_deref());
286        }
287        (*self.ptr).as_deref_mut().split_off(value)
288    }
289
290    /// See [`BTreeSet::extract_if`].
291    pub fn extract_if<F, R>(&mut self, range: R, pred: F) -> std::collections::btree_set::ExtractIf<'_, T, R, F>
292    where
293        R: std::ops::RangeBounds<T>,
294        F: FnMut(&T) -> bool,
295    {
296        ObserverState::invalidate(&mut self.state, (*self.ptr).as_deref());
297        (*self.ptr).as_deref_mut().extract_if(range, pred)
298    }
299}
300
301impl<'ob, T, S: ?Sized, D> Debug for BTreeSetObserver<'ob, T, S, D>
302where
303    T: Clone + Ord,
304    D: Unsigned,
305    S: AsDeref<D, Target = BTreeSet<T>>,
306    BTreeSet<T>: Debug,
307{
308    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
309        f.debug_tuple("BTreeSetObserver").field(&self.untracked_ref()).finish()
310    }
311}
312
313impl<'ob, T, S: ?Sized, D> PartialEq<BTreeSet<T>> for BTreeSetObserver<'ob, T, S, D>
314where
315    T: Clone + Ord,
316    D: Unsigned,
317    S: AsDeref<D, Target = BTreeSet<T>>,
318    BTreeSet<T>: PartialEq,
319{
320    fn eq(&self, other: &BTreeSet<T>) -> bool {
321        self.untracked_ref().eq(other)
322    }
323}
324
325impl<'ob, T1, T2, S1: ?Sized, S2: ?Sized, D1, D2> PartialEq<BTreeSetObserver<'ob, T2, S2, D2>>
326    for BTreeSetObserver<'ob, T1, S1, D1>
327where
328    T1: Clone + Ord,
329    T2: Clone + Ord,
330    D1: Unsigned,
331    D2: Unsigned,
332    S1: AsDeref<D1, Target = BTreeSet<T1>>,
333    S2: AsDeref<D2, Target = BTreeSet<T2>>,
334    BTreeSet<T1>: PartialEq<BTreeSet<T2>>,
335{
336    fn eq(&self, other: &BTreeSetObserver<'ob, T2, S2, D2>) -> bool {
337        self.untracked_ref().eq(other.untracked_ref())
338    }
339}
340
341impl<'ob, T, S, D> Eq for BTreeSetObserver<'ob, T, S, D>
342where
343    T: Clone + Ord,
344    D: Unsigned,
345    S: AsDeref<D, Target = BTreeSet<T>>,
346    BTreeSet<T>: Eq,
347{
348}
349
350impl<'ob, T, S: ?Sized, D> PartialOrd<BTreeSet<T>> for BTreeSetObserver<'ob, T, S, D>
351where
352    T: Clone + Ord,
353    D: Unsigned,
354    S: AsDeref<D, Target = BTreeSet<T>>,
355    BTreeSet<T>: PartialOrd,
356{
357    fn partial_cmp(&self, other: &BTreeSet<T>) -> Option<std::cmp::Ordering> {
358        self.untracked_ref().partial_cmp(other)
359    }
360}
361
362impl<'ob, T1, T2, S1: ?Sized, S2: ?Sized, D1, D2> PartialOrd<BTreeSetObserver<'ob, T2, S2, D2>>
363    for BTreeSetObserver<'ob, T1, S1, D1>
364where
365    T1: Clone + Ord,
366    T2: Clone + Ord,
367    D1: Unsigned,
368    D2: Unsigned,
369    S1: AsDeref<D1, Target = BTreeSet<T1>>,
370    S2: AsDeref<D2, Target = BTreeSet<T2>>,
371    BTreeSet<T1>: PartialOrd<BTreeSet<T2>>,
372{
373    fn partial_cmp(&self, other: &BTreeSetObserver<'ob, T2, S2, D2>) -> Option<std::cmp::Ordering> {
374        self.untracked_ref().partial_cmp(other.untracked_ref())
375    }
376}
377
378impl<'ob, T, S, D> Ord for BTreeSetObserver<'ob, T, S, D>
379where
380    T: Clone + Ord,
381    D: Unsigned,
382    S: AsDeref<D, Target = BTreeSet<T>>,
383    BTreeSet<T>: Ord,
384{
385    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
386        self.untracked_ref().cmp(other.untracked_ref())
387    }
388}
389
390impl<'ob, T, S: ?Sized, D, U> Extend<U> for BTreeSetObserver<'ob, T, S, D>
391where
392    T: Clone + Ord,
393    D: Unsigned,
394    S: AsDerefMut<D, Target = BTreeSet<T>>,
395    BTreeSet<T>: Extend<U>,
396{
397    fn extend<I: IntoIterator<Item = U>>(&mut self, iter: I) {
398        self.tracked_mut().extend(iter);
399    }
400}
401
402impl<T: Clone + Ord> Observe for BTreeSet<T> {
403    type Observer<'ob, S, D>
404        = BTreeSetObserver<'ob, T, S, D>
405    where
406        Self: 'ob,
407        D: Unsigned,
408        S: AsDerefMut<D, Target = Self> + ?Sized + 'ob;
409
410    type Spec = DefaultSpec;
411}
412
413default_impl_ref_observe! {
414    impl [T] RefObserve for BTreeSet<T>;
415}
416
417impl<T> Snapshot for BTreeSet<T>
418where
419    T: Snapshot,
420    T::Snapshot: Ord,
421{
422    type Snapshot = BTreeSet<T::Snapshot>;
423
424    fn to_snapshot(&self) -> Self::Snapshot {
425        self.iter().map(|item| item.to_snapshot()).collect()
426    }
427
428    fn eq_snapshot(&self, snapshot: &Self::Snapshot) -> bool {
429        self.len() == snapshot.len() && self.iter().zip(snapshot.iter()).all(|(a, b)| a.eq_snapshot(b))
430    }
431}
432
433#[cfg(test)]
434mod tests {
435    use std::collections::BTreeSet;
436
437    use morphix_test_utils::*;
438    use serde_json::json;
439
440    use crate::adapter::Json;
441    use crate::observe::{ObserveExt, SerializeObserverExt};
442
443    #[test]
444    fn no_change() {
445        let mut set = BTreeSet::from([1, 2, 3]);
446        let mut ob = set.__observe();
447        let Json(mutation) = ob.flush().unwrap();
448        assert_eq!(mutation, None);
449    }
450
451    #[test]
452    fn insert_append() {
453        let mut set = BTreeSet::from([1, 2, 3]);
454        let mut ob = set.__observe();
455        ob.insert(4);
456        ob.insert(5);
457        let Json(mutation) = ob.flush().unwrap();
458        assert_eq!(mutation, Some(append!(_, json!([4, 5]))));
459    }
460
461    #[test]
462    fn remove_last_as_truncate() {
463        let mut set = BTreeSet::from([1, 2, 3]);
464        let mut ob = set.__observe();
465        ob.remove(&3);
466        let Json(mutation) = ob.flush().unwrap();
467        assert_eq!(mutation, Some(truncate!(_, 1)));
468    }
469
470    #[test]
471    fn remove_middle() {
472        let mut set = BTreeSet::from([1, 2, 3, 4, 5]);
473        let mut ob = set.__observe();
474        ob.remove(&3);
475        let Json(mutation) = ob.flush().unwrap();
476        assert_eq!(mutation, Some(batch!(_, truncate!(_, 3), append!(_, json!([4, 5])))));
477    }
478
479    #[test]
480    fn insert_middle_then_append() {
481        let mut set = BTreeSet::from([1, 3, 5]);
482        let mut ob = set.__observe();
483        ob.insert(2);
484        ob.insert(6);
485        let Json(mutation) = ob.flush().unwrap();
486        assert_eq!(
487            mutation,
488            Some(batch!(_, truncate!(_, 2), append!(_, json!([2, 3, 5, 6]))))
489        );
490    }
491
492    #[test]
493    fn clear_non_empty() {
494        let mut set = BTreeSet::from([1, 2, 3]);
495        let mut ob = set.__observe();
496        ob.clear();
497        let Json(mutation) = ob.flush().unwrap();
498        assert_eq!(mutation, Some(replace!(_, json!([]))));
499    }
500
501    #[test]
502    fn clear_empty() {
503        let mut set: BTreeSet<i32> = BTreeSet::new();
504        let mut ob = set.__observe();
505        ob.clear();
506        let Json(mutation) = ob.flush().unwrap();
507        assert_eq!(mutation, None);
508    }
509
510    #[test]
511    fn deref_mut_triggers_replace() {
512        let mut set = BTreeSet::from([1, 2, 3]);
513        let mut ob = set.__observe();
514        **ob = BTreeSet::from([4, 5]);
515        let Json(mutation) = ob.flush().unwrap();
516        assert_eq!(mutation, Some(replace!(_, json!([4, 5]))));
517    }
518
519    #[test]
520    fn double_flush() {
521        let mut set = BTreeSet::from([1, 2, 3]);
522        let mut ob = set.__observe();
523        ob.insert(4);
524        let Json(mutation) = ob.flush().unwrap();
525        assert!(mutation.is_some());
526        let Json(mutation) = ob.flush().unwrap();
527        assert_eq!(mutation, None);
528    }
529
530    #[test]
531    fn pop_first() {
532        let mut set = BTreeSet::from([1, 2, 3]);
533        let mut ob = set.__observe();
534        assert_eq!(ob.pop_first(), Some(1));
535        let Json(mutation) = ob.flush().unwrap();
536        assert_eq!(mutation, Some(replace!(_, json!([2, 3]))));
537    }
538
539    #[test]
540    fn pop_last_as_truncate() {
541        let mut set = BTreeSet::from([1, 2, 3]);
542        let mut ob = set.__observe();
543        assert_eq!(ob.pop_last(), Some(3));
544        let Json(mutation) = ob.flush().unwrap();
545        assert_eq!(mutation, Some(truncate!(_, 1)));
546    }
547}
morphix/impls/collections/btree_set.rs

morphix/impls/collections/
btree_set.rs
