nb_tree/tree/
position.rs

1use replace_with::replace_with_or_abort;
2
3use crate::path::Path;
4
5/// Descripion of a position in a tree
6///
7/// Tthe position can either be attached (targetting a node)
8/// or detached (outside of the tree).
9/// Positions are described by an absolute Path
10/// that cannot move above the tree root.
11#[derive(Debug, Clone)]
12pub enum Position<B, I> {
13    /// The position is targetting a node
14    Attached(AttachedPosition<B, I>),
15    /// The position is leaving the tree
16    Detached(DetachedPosition<B, I>),
17}
18
19impl<B, I> Position<B, I> {
20    pub fn new_detached() -> Self {
21        Self::Detached(DetachedPosition::new())
22    }
23
24    pub fn new_attached(root: I) -> Self {
25        let mut ph = Path::new();
26        ph.push_last(root);
27        Self::Attached(AttachedPosition::from(Path::new(), ph))
28    }
29
30    pub fn from(path: Path<B>, idxs: Path<I>) -> Self {
31        if !idxs.is_empty() && path.len() == idxs.len() - 1 {
32            Self::Attached(AttachedPosition::from(path, idxs))
33        } else {
34            Self::Detached(DetachedPosition::from(path, idxs))
35        }
36    }
37
38    pub fn move_up(&mut self, up: usize) -> Option<usize> {
39        let mut overflow = None;
40        replace_with_or_abort(self, |s| match s {
41            Position::Attached(mut attached) => {
42                attached.move_up(up).map(|e| {
43                    overflow = Some(e);
44                    e
45                });
46                attached.into()
47            }
48            Position::Detached(detached) => {
49                let (p, e) = detached.move_up(up);
50                overflow = e;
51                p
52            }
53        });
54        overflow
55    }
56
57    //TODO: move_down? And use it
58
59    pub fn parent(&self) -> Option<(Option<&B>, Option<&I>)> {
60        match self {
61            Position::Attached(attached) => attached.parent().map(|(b, i)| (b, Some(i))),
62            Position::Detached(detached) => detached.parent(),
63        }
64    }
65
66    pub fn is_attached(&self) -> bool {
67        match self {
68            Position::Attached(_) => true,
69            Position::Detached(_) => false,
70        }
71    }
72
73    pub fn attached_mut(&mut self) -> Option<&mut AttachedPosition<B, I>> {
74        match self {
75            Position::Attached(position) => Some(position),
76            Position::Detached(_) => None,
77        }
78    }
79
80    pub fn detached_mut(&mut self) -> Option<&mut DetachedPosition<B, I>> {
81        match self {
82            Position::Attached(_) => None,
83            Position::Detached(position) => Some(position),
84        }
85    }
86
87    pub fn attached(&self) -> Option<&AttachedPosition<B, I>> {
88        match self {
89            Position::Attached(position) => Some(position),
90            Position::Detached(_) => None,
91        }
92    }
93
94    pub fn detached(&self) -> Option<&DetachedPosition<B, I>> {
95        match self {
96            Position::Attached(_) => None,
97            Position::Detached(position) => Some(position),
98        }
99    }
100
101    pub fn unwrap_detached(self) -> DetachedPosition<B, I> {
102        match self {
103            Position::Attached(_) => panic!("Unwrapping an Attached Position as DetachedPosition"),
104            Position::Detached(position) => position,
105        }
106    }
107
108    pub fn unwrap_attached(self) -> AttachedPosition<B, I> {
109        match self {
110            Position::Attached(position) => position,
111            Position::Detached(_) => panic!("Unwrapping a Detached Position as AttachedPosition"),
112        }
113    }
114
115    pub fn at(&self) -> Option<&I> {
116        match self {
117            Position::Attached(position) => Some(position.at()),
118            Position::Detached(_) => None,
119        }
120    }
121
122    pub fn path(&self) -> &Path<B> {
123        match self {
124            Position::Attached(position) => position.path(),
125            Position::Detached(position) => position.path(),
126        }
127    }
128
129    pub fn idxs(&self) -> &Path<I> {
130        match self {
131            Position::Attached(position) => position.idxs(),
132            Position::Detached(position) => position.idxs(),
133        }
134    }
135
136    pub fn at_branch(&self) -> Option<&B> {
137        match self {
138            Position::Attached(position) => position.at_branch(),
139            Position::Detached(position) => position.at_branch(),
140        }
141    }
142}
143
144impl<B, I> From<AttachedPosition<B, I>> for Position<B, I> {
145    fn from(value: AttachedPosition<B, I>) -> Self {
146        Self::Attached(value)
147    }
148}
149
150impl<B, I> From<DetachedPosition<B, I>> for Position<B, I> {
151    fn from(value: DetachedPosition<B, I>) -> Self {
152        Self::Detached(value)
153    }
154}
155
156#[derive(Debug, Clone)]
157pub struct AttachedPosition<B, I> {
158    path: Path<B>,
159    idxs: Path<I>,
160}
161
162#[derive(Debug, Clone)]
163pub struct DetachedPosition<B, I> {
164    path: Path<B>,
165    idxs: Path<I>,
166}
167
168/*
169impl<B, I> Deref for AttachedPosition<B, I> {
170    type Target = I;
171
172    fn deref(&self) -> &Self::Target {
173        self.at()
174    }
175}*/
176
177impl<B, I> AttachedPosition<B, I> {
178    /// # Panics
179    /// Panics if the built position is not attached
180    pub fn from(path: Path<B>, idxs: Path<I>) -> Self {
181        assert!(path.len() + 1 == idxs.len(), "Position is not attached");
182        Self { path, idxs }
183    }
184
185    pub fn at(&self) -> &I {
186        self.idxs.last().unwrap()
187    }
188
189    pub fn move_up(&mut self, up: usize) -> Option<usize> {
190        let len = self.path.len();
191        if up > len {
192            self.path.clear();
193            // Keep the root
194            self.idxs.truncate_end(self.idxs.len() - 1);
195            Some(up - len)
196        } else {
197            self.path.truncate_end(up);
198            self.idxs.truncate_end(up);
199            None
200        }
201    }
202    /// Returns None upon trying to move down to an indexed position while detached
203    pub fn move_down(&mut self, branch: B, idx: I) {
204        self.path.push_last(branch);
205        self.idxs.push_last(idx);
206    }
207
208    /// Returns None upon trying to move down to an indexed position while detached
209    pub fn move_down_detach(mut self, branch: B) -> DetachedPosition<B, I> {
210        self.path.push_last(branch);
211        self.into_detached()
212    }
213
214    /// Returns the branch and index of the parent node or None if the current node is the root.
215    /// The branch is None if the parent node is the tree root.
216    pub fn parent(&self) -> Option<(Option<&B>, &I)> {
217        // If there is at least two nodes in the path (idx -(branch)-> idx)
218        if self.path.last().is_some() {
219            Some((
220                // If there is more than two nodes in the path
221                if self.path.len() > 1 {
222                    // Retrieve the parent's branch
223                    Some(&self.path[self.path.len() - 2])
224                } else {
225                    None
226                },
227                &self.idxs[self.path.len() - 1],
228            ))
229        } else {
230            None
231        }
232    }
233
234    pub fn remove_node(mut self) -> DetachedPosition<B, I> {
235        self.idxs.pop_last();
236        self.into_detached()
237    }
238
239    pub fn into_detached(self) -> DetachedPosition<B, I> {
240        DetachedPosition {
241            path: self.path,
242            idxs: self.idxs,
243        }
244    }
245    pub fn at_branch(&self) -> Option<&B> {
246        self.path.last()
247    }
248
249    pub fn path(&self) -> &Path<B> {
250        &self.path
251    }
252
253    pub fn idxs(&self) -> &Path<I> {
254        &self.idxs
255    }
256}
257
258impl<B, I> DetachedPosition<B, I> {
259    pub fn new() -> Self {
260        Self {
261            path: Path::new(),
262            idxs: Path::new(),
263        }
264    }
265
266    /// # Panics
267    /// Panics if the built position is not detached
268    pub fn from(path: Path<B>, idxs: Path<I>) -> Self {
269        assert!(path.len() >= idxs.len(), "Position is not detached");
270        Self { path, idxs }
271    }
272
273    pub fn into_attached(self) -> AttachedPosition<B, I> {
274        assert!(self.is_attached());
275        AttachedPosition {
276            path: self.path,
277            idxs: self.idxs,
278        }
279    }
280
281    pub fn detached_at(&self) -> Option<&I> {
282        self.idxs.last()
283    }
284
285    pub fn move_up(mut self, up: usize) -> (Position<B, I>, Option<usize>) {
286        let len = self.path.len();
287        if up > len {
288            self.path.clear();
289            // Keep the root if any
290            if !self.idxs.is_empty() {
291                self.idxs.truncate_end(self.idxs.len() - 1);
292                (self.into_attached().into(), Some(up - len))
293            } else {
294                (self.into(), Some(up - len))
295            }
296        } else {
297            self.path.truncate_end(up);
298            (
299                if self.path.len() < self.idxs.len() {
300                    self.idxs
301                        .truncate_end(self.idxs.len() - self.path.len() - 1);
302                    self.into_attached().into()
303                } else {
304                    self.into()
305                },
306                None,
307            )
308        }
309    }
310
311    pub fn move_to_attached(mut self) -> Result<AttachedPosition<B, I>, Self> {
312        if !self.idxs.is_empty() && self.idxs.len() <= self.path.len() {
313            self.path
314                .truncate_end(self.path.len() - self.idxs.len() + 1);
315            debug_assert!(
316                self.is_attached(),
317                "Position is still not attached after moving to attached position"
318            );
319            Ok(self.into_attached())
320        } else {
321            Err(self)
322        }
323    }
324
325    pub fn move_down(&mut self, branch: B) {
326        self.path.push_last(branch);
327    }
328
329    /// Returns the branch and index of the parent node or None if the current node is the root.
330    /// The branch is None if the parent node is the tree root and the index is None if it is unknown.
331    pub fn parent(&self) -> Option<(Option<&B>, Option<&I>)> {
332        // If there is at least two nodes in the path (idx -(branch)-> idx)
333        if self.path.last().is_some() {
334            let l = self.path.len();
335            Some((
336                // If there is more than two nodes in the path
337                if l > 1 {
338                    // Retrieve the parent's branch
339                    Some(&self.path[l - 2])
340                } else {
341                    None
342                },
343                // If the index of the parent is known
344                if self.idxs.len() == l {
345                    self.idxs.last()
346                } else {
347                    None
348                },
349            ))
350        } else {
351            None
352        }
353    }
354
355    pub fn attach(mut self, idx: I) -> Position<B, I> {
356        self.idxs.push_last(idx);
357        if self.is_attached() {
358            self.into_attached().into()
359        } else {
360            self.into()
361        }
362    }
363
364    pub fn attach_all(mut self, mut idxs: Vec<I>) -> Position<B, I> {
365        idxs.truncate(self.path.len() - self.idxs.len() + 1);
366        self.idxs.append(idxs.into());
367        if self.is_attached() {
368            self.into_attached().into()
369        } else {
370            self.into()
371        }
372    }
373
374    fn is_attached(&self) -> bool {
375        self.is_rooted() && self.path.len() == self.idxs.len() - 1 // Root idx
376    }
377
378    pub fn path(&self) -> &Path<B> {
379        &self.path
380    }
381
382    pub fn idxs(&self) -> &Path<I> {
383        &self.idxs
384    }
385
386    pub fn iter_detached_path(&self) -> std::collections::vec_deque::Iter<'_, B> {
387        if self.is_rooted() {
388            self.path.range((self.idxs.len() - 1)..)
389        } else {
390            self.path.range(..)
391        }
392    }
393
394    pub fn offshoot_len(&self) -> usize {
395        self.path.len() + 1 - self.idxs.len()
396    }
397
398    pub fn is_rooted(&self) -> bool {
399        !self.idxs.is_empty()
400    }
401
402    pub fn is_empty(&self) -> bool {
403        self.path.is_empty()
404    }
405
406    pub fn at_branch(&self) -> Option<&B> {
407        self.path.last()
408    }
409}
410
411impl<B, I> DetachedPosition<B, I>
412where
413    B: Clone,
414{
415    pub fn detached_at_branch(&self) -> Option<&B> {
416        if !self.idxs.is_empty() {
417            Some(&self.path[self.idxs.len()])
418        } else {
419            None
420        }
421    }
422}
nb_tree/tree/position.rs

nb_tree/tree/
position.rs
