tree_cursor/
cursor.rs

1use prelude::*;
2use std::marker::PhantomData;
3
4/// A cursor that holds a shared reference to its tree.
5#[derive(Clone, Debug, Eq, Hash, PartialEq)]
6pub struct TreeCursor<'n: 'f, 'f, N: 'n> {
7    root: PhantomData<&'n N>,
8    frozen: PhantomData<&'f ()>,
9    stack: Vec<(*const N, usize)>,
10}
11
12impl<'n, N: 'n> TreeCursor<'n, 'n, N> {
13    /// Creates a new `TreeCursor` starting at `root`.
14    pub fn new(root: &'n N) -> Self {
15        Self {
16            root: PhantomData,
17            frozen: PhantomData,
18            stack: vec![(root as *const N, 0)],
19        }
20    }
21}
22
23impl<'n: 'f, 'f, N: 'n> TreeCursor<'n, 'f, N> {
24    fn top(&self) -> &(*const N, usize) {
25        self.stack.last().unwrap()
26    }
27
28    fn top_mut(&mut self) -> &mut (*const N, usize) {
29        self.stack.last_mut().unwrap()
30    }
31
32    fn down_map_ptr<F>(&mut self, f: F) -> Option<*const N>
33    where
34        F: Fn(&'n N, usize) -> Option<&'n N>,
35    {
36        let idx = self.top().1;
37        let here_ptr = self.get() as *const N;
38        let new_ptr =
39            f(unsafe { here_ptr.as_ref().unwrap() }, idx)? as *const N;
40        self.top_mut().1 += 1;
41        Some(new_ptr)
42    }
43
44    /// Passes `f` the active node and the current value of the "next child"
45    /// counter. If `f` returns a node, it's set as the active node, the old
46    /// active node's "next child" counter is incremented, and this method
47    /// returns true. Otherwise, this method returns false.
48    pub fn down_map<F>(&mut self, f: F) -> bool
49    where
50        F: Fn(&'n N, usize) -> Option<&'n N>,
51    {
52        let maybe_new_ptr = self.down_map_ptr(f);
53        if let &Some(new_ptr) = &maybe_new_ptr {
54            self.stack.push((new_ptr, 0));
55        }
56        maybe_new_ptr.is_some()
57    }
58
59    /// Like [`down_new`], except that it takes a closure like [`down_map`].
60    ///
61    /// [`down_new`]: TreeCursor::down_new
62    /// [`down_map`]: TreeCursor::down_map
63    pub fn down_map_new<'s, F>(&'s mut self, f: F)
64        -> Option<TreeCursor<'n, 's, N>>
65    where
66        F: Fn(&'n N, usize) -> Option<&'n N>,
67    {
68        let new_ptr = self.down_map_ptr(f)?;
69        Some(Self {
70            root: PhantomData,
71            frozen: PhantomData,
72            stack: vec![(new_ptr, 0)],
73        })
74    }
75
76    /// Resets the active node's "next child" counter to 0.
77    pub fn zero(&mut self) {
78        self.top_mut().1 = 0;
79    }
80
81    /// Moves the cursor up one node. Returns true if there was a node to move
82    /// to, and false otherwise. In both cases, the old active node's "next
83    /// child" counter is reset, as if [`zero`] had been called.
84    ///
85    /// [`zero`]: TreeCursor::zero
86    pub fn up(&mut self) -> bool {
87        if self.stack.len() == 1 {
88            self.stack[0].1 = 0;
89            false
90        } else {
91            self.stack.pop().unwrap();
92            true
93        }
94    }
95
96    /// Takes the active node from this `TreeCursor` and returns a new
97    /// `TreeCursor` at that position. `self` is frozen until the new cursor
98    /// goes out of scope.
99    pub fn take<'s>(&'s mut self) -> Option<TreeCursor<'n, 's, N>> {
100        if self.stack.len() == 1 {
101            None
102        } else {
103            let (old_ptr, old_idx) = self.stack.pop().unwrap();
104            let old = unsafe { old_ptr.as_ref().unwrap() };
105            Some(Self {
106                root: PhantomData,
107                frozen: PhantomData,
108                stack: vec![(old, old_idx)],
109            })
110        }
111    }
112
113    /// Returns a shared reference to the active node.
114    pub fn get(&self) -> &N {
115        let here: *const N = self.top().0;
116        unsafe { here.as_ref().unwrap() }
117    }
118}
119
120impl<'n: 'f, 'f, N: 'n + Down> TreeCursor<'n, 'f, N> {
121    fn down_ptr(&mut self) -> Option<*const N> {
122        let idx = self.top().1;
123        let new_ptr = self.get().down(idx)? as *const N;
124        self.top_mut().1 += 1;
125        Some(new_ptr)
126    }
127
128    /// Moves the cursor down one node. The node to move to is determined by
129    /// calling [`Down::down`] on the active node and passing it the "next
130    /// child" counter. Returns true and increments the old active node's
131    /// "next child" counter if there was a node to move to, and returns false
132    /// otherwise.
133    pub fn down(&mut self) -> bool {
134        let maybe_new_ptr = self.down_ptr();
135        if let &Some(new_ptr) = &maybe_new_ptr {
136            self.stack.push((new_ptr, 0));
137        }
138        maybe_new_ptr.is_some()
139    }
140
141    /// Like [`down`], except instead of moving the position of `self`, it
142    /// returns a new `TreeCursor` whose root is the new position. `self` is
143    /// frozen until the new cursor goes out of scope.
144    ///
145    /// [`down`]: TreeCursor::down
146    pub fn down_new<'s>(&'s mut self) -> Option<TreeCursor<'n, 's, N>> {
147        let new_ptr = self.down_ptr()?;
148        Some(Self {
149            root: PhantomData,
150            frozen: PhantomData,
151            stack: vec![(new_ptr, 0)],
152        })
153    }
154}
155
156impl<'n: 'f, 'f, N: 'n> From<TreeCursorMut<'n, 'f, N>>
157    for TreeCursor<'n, 'f, N>
158{
159    fn from(mut cm: TreeCursorMut<'n, 'f, N>) -> Self {
160        TreeCursor {
161            root: PhantomData,
162            frozen: PhantomData,
163            stack: cm.stack.drain(..).map(|(p, n)| (p as *const N, n))
164                .collect(), // TODO: speed this up
165        }
166    }
167}
168
169/// A cursor that holds a mutable reference to its tree.
170#[derive(Debug, Eq, Hash, PartialEq)]
171pub struct TreeCursorMut<'n: 'f, 'f, N: 'n> {
172    root: PhantomData<&'n mut N>,
173    frozen: PhantomData<&'f ()>,
174    stack: Vec<(*mut N, usize)>,
175}
176
177impl<'n, N: 'n> TreeCursorMut<'n, 'n, N> {
178    /// Creates a new `TreeCursorMut` starting at `root`.
179    pub fn new(root: &'n mut N) -> Self {
180        Self {
181            root: PhantomData,
182            frozen: PhantomData,
183            stack: vec![(root as *mut N, 0)],
184        }
185    }
186}
187
188impl<'n: 'f, 'f, N: 'n> TreeCursorMut<'n, 'f, N> {
189    fn top(&self) -> &(*mut N, usize) {
190        self.stack.last().unwrap()
191    }
192
193    fn top_mut(&mut self) -> &mut (*mut N, usize) {
194        self.stack.last_mut().unwrap()
195    }
196
197    fn down_map_ptr<F>(&mut self, f: F) -> Option<*mut N>
198    where
199        F: Fn(&'n mut N, usize) -> Option<&'n mut N>,
200    {
201        let idx = self.top().1;
202        let here_ptr = self.get_mut() as *mut N;
203        let new_ptr = f(unsafe { here_ptr.as_mut().unwrap() }, idx)? as *mut N;
204        self.top_mut().1 += 1;
205        Some(new_ptr)
206    }
207
208    /// Passes `f` the active node and the current value of the "next child"
209    /// counter. If `f` returns a node, it's set as the active node, the old
210    /// active node's "next child" counter is incremented, and this method
211    /// returns true. Otherwise, this method returns false.
212    pub fn down_map<F>(&mut self, f: F) -> bool
213    where
214        F: Fn(&'n mut N, usize) -> Option<&'n mut N>,
215    {
216        let maybe_new_ptr = self.down_map_ptr(f);
217        if let &Some(new_ptr) = &maybe_new_ptr {
218            self.stack.push((new_ptr, 0));
219        }
220        maybe_new_ptr.is_some()
221    }
222
223    /// Like [`down_new`], except that it takes a closure like [`down_map`].
224    ///
225    /// [`down_new`]: TreeCursorMut::down_new
226    /// [`down_map`]: TreeCursorMut::down_map
227    pub fn down_map_new<'s, F>(&'s mut self, f: F)
228        -> Option<TreeCursorMut<'n, 's, N>>
229    where
230        F: Fn(&'n mut N, usize) -> Option<&'n mut N>,
231    {
232        let new_ptr = self.down_map_ptr(f)?;
233        Some(Self {
234            root: PhantomData,
235            frozen: PhantomData,
236            stack: vec![(new_ptr, 0)],
237        })
238    }
239
240    /// Resets the active node's "next child" counter to 0.
241    pub fn zero(&mut self) {
242        self.top_mut().1 = 0;
243    }
244
245    /// Moves the cursor up one node. Returns true if there was a node to move
246    /// to, and false otherwise. In both cases, the old active node's "next
247    /// child" counter is reset, as if [`zero`] had been called.
248    ///
249    /// [`zero`]: TreeCursorMut::zero
250    pub fn up(&mut self) -> bool {
251        if self.stack.len() == 1 {
252            self.stack[0].1 = 0;
253            false
254        } else {
255            self.stack.pop().unwrap();
256            true
257        }
258    }
259
260    /// Takes the active node from this `TreeCursorMut` and returns a new
261    /// `TreeCursorMut` at that position. `self` is frozen until the new cursor
262    /// goes out of scope.
263    pub fn take<'s>(&'s mut self) -> Option<TreeCursorMut<'n, 's, N>> {
264        if self.stack.len() == 1 {
265            None
266        } else {
267            let (old_ptr, old_idx) = self.stack.pop().unwrap();
268            let old = unsafe { old_ptr.as_mut().unwrap() };
269            Some(Self {
270                root: PhantomData,
271                frozen: PhantomData,
272                stack: vec![(old, old_idx)],
273            })
274        }
275    }
276
277    /// Returns a shared reference to the active node.
278    pub fn get(&self) -> &N {
279        let here: *const N = self.top().0;
280        (unsafe { here.as_ref() }).unwrap()
281    }
282
283    /// Returns a mutable reference to the active node.
284    pub fn get_mut(&mut self) -> &mut N {
285        let here = self.top().0;
286        (unsafe { here.as_mut() }).unwrap()
287    }
288
289    pub fn as_cursor<'s>(&'s self) -> TreeCursor<'n, 's, N> {
290        TreeCursor {
291            root: PhantomData,
292            frozen: PhantomData,
293            stack: self.stack.iter()
294                .map(|&(p, n)| (p as *const N, n)).collect(),
295        }
296    }
297}
298
299/// Stores a cursor's position at an earlier point in time.
300pub struct TreeCursorPos(Vec<usize>);
301
302impl<'n: 'f, 'f, N: 'n + DownMut> TreeCursorMut<'n, 'f, N> {
303    /// Returns an opaque object that stores the current position of the cursor.
304    /// Pass it to [`set_pos`] to restore that position.
305    ///
306    /// [`set_pos`]: TreeCursorMut::set_pos
307    pub fn pos(&self) -> TreeCursorPos {
308        TreeCursorPos(self.stack.iter().map(|&(_, idx)| idx).collect())
309    }
310
311    /// Moves the cursor to the given position, as long as tree mutation hasn't
312    /// invalidated the position since it was retrieved.
313    ///
314    /// # Panics
315    ///
316    /// If the tree has changed such that the position is no longer valid, this
317    /// method panics. However, since the position is stored using "next child"
318    /// indices (not pointers), it remains valid as long as the tree has a node
319    /// in that position, even if the node's value changes or it's replaced with
320    /// another node. If this is a problem, you should track the position's
321    /// validity yourself.
322    ///
323    /// [`pos`]: TreeCursorMut::pos
324    pub fn set_pos(&mut self, pos: &TreeCursorPos) {
325        self.stack.truncate(1);
326        for &idx in pos.0.iter().rev().skip(1).rev() { // TODO: ugly
327            self.top_mut().1 = idx - 1;
328            if !self.down() {
329                panic!("missing node in TreeCursorPos");
330            }
331        }
332        let &idx = pos.0.last().unwrap();
333        self.top_mut().1 = idx;
334    }
335
336    fn down_ptr(&mut self) -> Option<*mut N> {
337        let idx = self.stack.last().unwrap().1;
338        let new_ptr = self.get_mut().down_mut(idx)? as *mut N;
339        self.stack.last_mut().unwrap().1 += 1;
340        Some(new_ptr)
341    }
342
343    /// Moves the cursor down one node. The node to move to is determined by
344    /// calling [`DownMut::down_mut`] on the active node and passing it the
345    /// "next child" counter. Returns true and increments the old active node's
346    /// "next child" counter if there was a node to move to, and returns false
347    /// otherwise.
348    pub fn down(&mut self) -> bool {
349        let maybe_new_ptr = self.down_ptr();
350        if let &Some(new_ptr) = &maybe_new_ptr {
351            self.stack.push((new_ptr, 0));
352        }
353        maybe_new_ptr.is_some()
354    }
355
356    /// Like [`down`], except instead of moving the position of `self`, it
357    /// returns a new `TreeCursorMut` whose root is the new position. `self` is
358    /// frozen until the new cursor goes out of scope.
359    ///
360    /// [`down`]: TreeCursorMut::down
361    pub fn down_new<'s>(&'s mut self) -> Option<TreeCursorMut<'n, 's, N>> {
362        let new_ptr = self.down_ptr()?;
363        Some(Self {
364            root: PhantomData,
365            frozen: PhantomData,
366            stack: vec![(new_ptr, 0)],
367        })
368    }
369}
tree_cursor/cursor.rs

tree_cursor/
cursor.rs
