ftml_solver/
utils.rs

1// e.g. CancelToken
2#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, Default)]
3pub struct RefList<'r, T> {
4    elem: T,
5    parent: Option<&'r Self>,
6}
7impl<'r, T> RefList<'r, T> {
8    #[inline]
9    pub const fn parent(&self) -> Option<&'r Self> {
10        self.parent
11    }
12    #[inline]
13    pub const fn derive(&self, new: T) -> RefList<'_, T> {
14        RefList {
15            elem: new,
16            parent: Some(self),
17        }
18    }
19
20    pub fn derive_default(&self) -> RefList<'_, T>
21    where
22        T: Default,
23    {
24        RefList {
25            elem: T::default(),
26            parent: Some(self),
27        }
28    }
29
30    pub fn find<R>(&self, mut f: impl FnMut(&T) -> Option<R>) -> Option<R> {
31        let mut curr = self;
32        loop {
33            if let Some(r) = f(&curr.elem) {
34                return Some(r);
35            }
36            if let Some(p) = curr.parent {
37                curr = p;
38            } else {
39                return None;
40            }
41        }
42    }
43    #[inline]
44    pub fn for_each(&self, mut f: impl FnMut(&T)) {
45        self.find::<()>(move |e| {
46            f(e);
47            None
48        });
49    }
50
51    #[allow(clippy::len_without_is_empty)]
52    pub const fn len(&self) -> usize {
53        let mut curr = self;
54        let mut ret = 1;
55        loop {
56            if let Some(p) = curr.parent {
57                curr = p;
58                ret += 1;
59            } else {
60                return ret;
61            }
62        }
63    }
64}
65impl<T> std::ops::Deref for RefList<'_, T> {
66    type Target = T;
67    fn deref(&self) -> &Self::Target {
68        &self.elem
69    }
70}
71impl<T> From<T> for RefList<'_, T> {
72    fn from(value: T) -> Self {
73        Self {
74            elem: value,
75            parent: None,
76        }
77    }
78}
79
80pub trait Merge {
81    fn merge(&mut self, other: Self);
82}
83
84#[derive(Debug)]
85pub struct MutableRefList<'i, T> {
86    element: &'i mut T,
87    parent: Option<Ancestor<'i, T>>,
88}
89impl<T> std::ops::Deref for MutableRefList<'_, T> {
90    type Target = T;
91    #[inline]
92    fn deref(&self) -> &Self::Target {
93        &*self.element
94    }
95}
96impl<T> std::ops::DerefMut for MutableRefList<'_, T> {
97    fn deref_mut(&mut self) -> &mut Self::Target {
98        self.element
99    }
100}
101impl<'i, T> MutableRefList<'i, T> {
102    pub const fn new(inner: &'i mut T) -> Self {
103        Self {
104            element: inner,
105            parent: None,
106        }
107    }
108    pub const fn new_with_parent(inner: &'i mut T, ancestor: &'i Self) -> Self {
109        Self {
110            element: inner,
111            parent: Some(Ancestor {
112                p: ancestor.element,
113                gp: ancestor.parent.as_ref(),
114            }),
115        }
116    }
117    #[must_use]
118    pub const fn depth(&self) -> usize {
119        let mut curr = self.parent;
120        let mut ret = 0;
121        while let Some(c) = curr {
122            ret += 1;
123            curr = c.gp.copied();
124        }
125        ret
126    }
127    pub fn find<'s, R>(&'s self, mut f: impl FnMut(&'s T) -> Option<R>) -> Option<R> {
128        let mut curr = &*self.element;
129        let mut currp = self.parent;
130        loop {
131            if let Some(r) = f(curr) {
132                return Some(r);
133            }
134            if let Some(a) = currp {
135                curr = a.p;
136                currp = a.gp.copied();
137            } else {
138                return None;
139            }
140        }
141    }
142
143    #[inline]
144    pub fn split_def<R>(
145        &mut self,
146        f: impl FnOnce(MutableRefList<T>) -> R,
147        then: impl FnOnce(&mut Self, &mut R, T),
148    ) -> R
149    where
150        T: Default,
151    {
152        self.split(T::default(), f, then)
153    }
154
155    #[inline]
156    pub fn split_merge<R>(&mut self, f: impl FnOnce(MutableRefList<T>) -> Option<R>) -> Option<R>
157    where
158        T: Default + Merge,
159    {
160        self.split_def(f, |slf, r, t| {
161            if r.is_some() {
162                slf.element.merge(t);
163            }
164        })
165    }
166
167    pub fn split<R>(
168        &mut self,
169        mut new: T,
170        f: impl FnOnce(MutableRefList<T>) -> R,
171        then: impl FnOnce(&mut Self, &mut R, T),
172    ) -> R {
173        let inner = MutableRefList {
174            element: &mut new,
175            parent: Some(Ancestor {
176                p: &*self.element,
177                gp: self.parent.as_ref(),
178            }),
179        };
180        let mut r = f(inner);
181        then(self, &mut r, new);
182        r
183    }
184    pub fn iter(&'i self) -> impl Iterator<Item = &'i T> {
185        self.into_iter()
186    }
187}
188
189#[derive(Debug)]
190struct Ancestor<'i, T> {
191    p: &'i T,
192    gp: Option<&'i Self>,
193}
194impl<T> Clone for Ancestor<'_, T> {
195    #[inline]
196    fn clone(&self) -> Self {
197        *self
198    }
199}
200impl<T> Copy for Ancestor<'_, T> {}
201
202impl<'i, T> IntoIterator for &'i MutableRefList<'i, T> {
203    type IntoIter = RefListIter<'i, T>;
204    type Item = &'i T;
205    fn into_iter(self) -> Self::IntoIter {
206        RefListIter(Some(self.element), self.parent)
207    }
208}
209
210pub struct RefListIter<'i, T>(Option<&'i T>, Option<Ancestor<'i, T>>);
211impl<'i, T> Iterator for RefListIter<'i, T> {
212    type Item = &'i T;
213    fn next(&mut self) -> Option<Self::Item> {
214        let next = self.0.take()?;
215        if let Some(Ancestor { p, gp }) = self.1.take() {
216            self.0 = Some(p);
217            self.1 = gp.copied();
218        }
219        Some(next)
220    }
221}
ftml_solver/utils.rs

ftml_solver/
utils.rs
