libtree/cursor.rs
1use crate::tree::{
2 ChildIterator, ChildIteratorMut, ChildLink, LazyTreeIterator, LazyTreeIteratorMut, Node,
3 _iter_rec, _iter_rec_mut,
4};
5use std::{collections::LinkedList, marker::PhantomData, ptr::NonNull};
6
7/// Equivalent of immutable reference for [crate::Tree]
8///
9/// This structure owns a raw pointer, 'current', as in Tree, and can be used to navigate and peek
10/// into the tree (same methods as in [crate::Tree]).
11/// The main contribution of [Cursor] is that you can have multiple cursors together, meaning you
12/// can make concurrent explorations of the tree.
13///
14/// Cursors are created by taking a reference to the tree, meaning that the borrow checker can
15/// ensure it's normal behaviour as you would for normal references. As long as cursors are alive,
16/// the tree cannot be mutated.
17///
18/// # Examples
19/// ```
20/// # use libtree::Tree;
21/// let mut tree = Tree::from_element(10);
22/// tree.push_iter(vec![1, 2, 3]);
23/// tree.navigate_to(1);
24///
25/// // Multiples references we can move all along the tree
26/// let cursor1 = tree.cursor();
27/// let mut cursor2 = tree.cursor_root();
28/// assert_eq!(cursor1.peek(), &2);
29/// assert_eq!(cursor2.peek(), &10);
30/// cursor2.navigate_to(2);
31/// assert_eq!(cursor2.peek(), &3);
32/// ```
33pub struct Cursor<'a, T> {
34 pub(crate) current: ChildLink<T>,
35 pub(crate) _boo: PhantomData<&'a T>,
36}
37
38/// Equivalent of mutable reference for [crate::Tree]
39///
40/// This structure is the same as [Cursor], implements every methods that [Cursor] implements and
41/// only implements a few more methods such as [CursorMut::peek_mut].
42///
43/// CursorMut are created by taking a mutable reference to the tree, meaning that they can be only
44/// one CursorMut alive at the same time, and that creating a CursorMut invalidates every other
45/// Cursor or CursorMut.
46///
47/// That behaviour makes CursorMut a bit useless, as it is the same as navigating 'current' in tree.
48/// The most useful behaviour is when you need a mutable exploration of the tree without navigating
49/// 'current', and so instead of navigating 'current' back to it's original location after you
50/// exploration (which can be sometimes a bit complex), you can create a CursorMut, explores the
51/// tree with it, and then throw it away as soon as you finished the exploration.
52///
53/// # Examples
54/// ```
55/// # use libtree::Tree;
56/// let mut tree = Tree::from_element(10);
57/// tree.push_iter(vec![1, 2, 3]);
58/// // Firstly, node that we need a mut on the cursor definition.
59/// // This is because the signature of peek_mut(&mut self) -> &mut T
60/// // Doing so enforce rust ownership system, but it makes cursor immutable while the reference is
61/// // alive.
62/// let mut cursor = tree.cursor_mut();
63/// let ref_el = cursor.peek_mut();
64/// assert_eq!(ref_el, &mut 10);
65/// *ref_el = 15;
66/// cursor.navigate_to(0);
67/// // but now we can't use ref_el, because navigate_to needs to mutate cursor, and so invalidates
68/// // all mutable refences taken from cursor.
69/// // Not very pratical if we, for exemple, want to build an iterator on the whole tree from a
70/// // CursorMut.
71/// ```
72pub struct CursorMut<'a, T> {
73 pub(crate) current: ChildLink<T>,
74 pub(crate) _boo: PhantomData<&'a T>,
75}
76
77impl<'a, T> Cursor<'a, T> {
78 /// Peek at 'current', returning a reference to the element stored in 'current'.
79 ///
80 /// # Examples
81 /// ```
82 /// # use libtree::Tree;
83 /// let tree = Tree::from_element(10);
84 /// let cursor = tree.cursor();
85 /// assert_eq!(cursor.peek(), &10);
86 /// ```
87 pub fn peek(&self) -> &'a T {
88 unsafe { &(*self.current.as_ptr()).elem }
89 }
90
91 /// Peek at 'current'.childs\[index\], returning a reference to the element stored.
92 ///
93 /// # Examples
94 /// ```
95 /// # use libtree::Tree;
96 /// let mut tree = Tree::from_element(10);
97 /// tree.push(5);
98 /// let cursor = tree.cursor();
99 /// assert_eq!(cursor.peek_child(0), &5);
100 /// ```
101 pub fn peek_child(&self, index: usize) -> &'a T {
102 if index >= self.childs_len() {
103 panic!(
104 "Tried to peek child on child {} but current has only {} childs",
105 index,
106 self.childs_len()
107 );
108 }
109
110 unsafe { &(*(*self.current.as_ptr()).childs[index].as_ptr()).elem }
111 }
112
113 /// Set 'current' to 'current'.childs\[index\], therefore navigating to this child
114 ///
115 /// # Examples
116 /// ```
117 /// # use libtree::Tree;
118 /// let mut tree = Tree::from_element(0);
119 /// tree.push(1);
120 /// let mut cursor = tree.cursor();
121 /// cursor.navigate_to(0);
122 /// assert_eq!(cursor.peek(), &1);
123 /// ```
124 ///
125 /// # Panics
126 /// This method will panic if index >= self.childs_len
127 pub fn navigate_to(&mut self, index: usize) {
128 if index >= self.childs_len() {
129 panic!(
130 "Tried to navigate to child {} but current has only {} childs",
131 index,
132 self.childs_len()
133 );
134 }
135
136 unsafe {
137 self.current = (*self.current.as_ptr()).childs[index];
138 }
139 }
140
141 /// Set 'current' to 'current'.father, therefore navigating up.
142 ///
143 /// # Examples
144 /// ```
145 /// # use libtree::Tree;
146 /// let mut tree = Tree::from_element(0);
147 /// tree.push(1);
148 /// tree.navigate_to(0);
149 /// let mut cursor = tree.cursor();
150 /// cursor.ascend();
151 /// assert_eq!(cursor.peek(), &0);
152 /// ```
153 ///
154 /// # Panics
155 /// This method will panic if 'current' has no father i.e. if 'current'.father.is_none()
156 pub fn ascend(&mut self) {
157 if !self.has_father() {
158 panic!("Tried to call ascend but current has no father");
159 }
160
161 unsafe {
162 self.current = (*self.current.as_ptr()).father.unwrap();
163 }
164 }
165
166 /// Return true if 'current' has a father.
167 ///
168 /// # Examples
169 /// ```
170 /// # use libtree::Tree;
171 /// let mut tree = Tree::from_element(0);
172 /// tree.push(1);
173 /// tree.navigate_to(0);
174 /// let mut cursor = tree.cursor();
175 /// assert!(cursor.has_father());
176 /// cursor.ascend();
177 /// assert!(!cursor.has_father());
178 /// ```
179 pub fn has_father(&self) -> bool {
180 unsafe { (*self.current.as_ptr()).father.is_some() }
181 }
182
183 /// Return the number of childrens of current.
184 ///
185 /// # Examples
186 /// ```
187 /// # use libtree::Tree;
188 /// let mut tree = Tree::from_element(0);
189 /// tree.push_iter(vec![1, 1, 1, 1, 1]);
190 /// let cursor = tree.cursor();
191 /// assert_eq!(cursor.childs_len(), 5);
192 /// ```
193 pub fn childs_len(&self) -> usize {
194 unsafe { (*self.current.as_ptr()).childs.len() }
195 }
196
197 /// Return an Iterator over the elements stored in 'current'.childs
198 ///
199 /// # Examples
200 /// ```
201 /// # use libtree::Tree;
202 /// let mut tree = Tree::from_element(0);
203 /// tree.push_iter(vec![1, 2, 3]);
204 /// let cursor = tree.cursor();
205 /// assert_eq!(cursor.iter_childs().collect::<Vec<&i32>>(), vec![&1, &2, &3]);
206 /// ```
207 pub fn iter_childs(&self) -> ChildIterator<'a, T> {
208 ChildIterator {
209 current: self.current,
210 i: 0,
211 len: self.childs_len(),
212 _boo: PhantomData,
213 }
214 }
215
216 /// Iterate over references of element stored in the subtree rooted at 'current' in a
217 /// depth-first way. This is done
218 /// by creating a Vec and pushing every references into this Vec and then returning an iterator
219 /// over this Vec. As it may not be very memory efficient, you might check [Cursor::lazyiter].
220 ///
221 /// # Examples
222 /// ```
223 /// # use libtree::Tree;
224 /// let mut tree = Tree::from_element(0);
225 /// tree.push_iter(vec![1, 2, 3]);
226 /// tree.navigate_to(1);
227 /// tree.push(4);
228 /// assert_eq!(tree.cursor().iter().collect::<Vec<&i32>>(), vec![&2, &4]);
229 pub fn iter(&self) -> impl Iterator<Item = &'a T> {
230 let mut container = Vec::new();
231 _iter_rec(self.current, &mut container);
232 container.into_iter()
233 }
234
235 /// Iterate over the subtree rooted at 'current' in a lazy depth-first way, returning
236 /// references to the elements stored in the subtree. Although it is lazy iteration, meaning it is
237 /// less stressfull for memory, it is slower than [Cursor::iter], because the cursor that is used
238 /// to move around the tree has to keep tracks of which branches it has already explored.
239 ///
240 /// # Examples
241 /// ```
242 /// # use libtree::Tree;
243 /// let mut tree = Tree::from_element(0);
244 /// tree.push_iter(vec![1, 2, 3]);
245 /// tree.navigate_to(1);
246 /// tree.push_iter(vec![9, 8]);
247 /// tree.ascend();
248 /// tree.navigate_to(0);
249 /// tree.push_iter(vec![9, 10]);
250 /// tree.navigate_to(0);
251 /// tree.push(15);
252 /// tree.go_to_root();
253 /// assert_eq!(
254 /// tree.lazyiter().collect::<Vec<&i32>>(),
255 /// vec![&0, &1, &9, &15, &10, &2, &9, &8, &3]
256 /// );
257 /// tree.navigate_to(1);
258 /// assert_eq!(tree.lazyiter().collect::<Vec<&i32>>(), vec![&2, &9, &8]);
259 /// ```
260 pub fn lazyiter(&self) -> LazyTreeIterator<'a, T> {
261 let mut idx_list = LinkedList::new();
262 idx_list.push_back(0);
263 LazyTreeIterator {
264 cursor: Cursor {
265 current: self.current,
266 _boo: PhantomData,
267 },
268 idx_list,
269 _boo: PhantomData,
270 }
271 }
272}
273
274impl<'a, T> CursorMut<'a, T> {
275 /// Peek at 'current', returning a reference to the element stored in 'current'.
276 ///
277 /// # Examples
278 /// ```
279 /// # use libtree::Tree;
280 /// let mut tree = Tree::from_element(10);
281 /// let cursor = tree.cursor_mut();
282 /// assert_eq!(cursor.peek(), &10);
283 /// ```
284 pub fn peek(&self) -> &'a T {
285 unsafe { &(*self.current.as_ptr()).elem }
286 }
287
288 /// Peek at 'current', returning a mutable reference to the element stored in 'current'.
289 ///
290 /// # Examples
291 /// ```
292 /// # use libtree::Tree;
293 /// let mut tree = Tree::from_element(10);
294 /// let mut cursor = tree.cursor_mut();
295 /// assert_eq!(cursor.peek_mut(), &mut 10);
296 /// ```
297 pub fn peek_mut(&mut self) -> &mut T {
298 unsafe { &mut (*self.current.as_ptr()).elem }
299 }
300
301 /// Peek at 'current'.childs\[index\], returning a reference to the element stored.
302 ///
303 /// # Examples
304 /// ```
305 /// # use libtree::Tree;
306 /// let mut tree = Tree::from_element(10);
307 /// tree.push(5);
308 /// let cursor = tree.cursor_mut();
309 /// assert_eq!(cursor.peek_child(0), &5);
310 /// ```
311 pub fn peek_child(&self, index: usize) -> &'a T {
312 if index >= self.childs_len() {
313 panic!(
314 "Tried to peek child on child {} but current has only {} childs",
315 index,
316 self.childs_len()
317 );
318 }
319
320 unsafe { &(*(*self.current.as_ptr()).childs[index].as_ptr()).elem }
321 }
322
323 /// Peek at 'current'.childs\[index\], returning a mutable reference to the element stored.
324 ///
325 /// # Examples
326 /// ```
327 /// # use libtree::Tree;
328 /// let mut tree = Tree::from_element(10);
329 /// tree.push(5);
330 /// let mut cursor = tree.cursor_mut();
331 /// assert_eq!(cursor.peek_child_mut(0), &mut 5);
332 /// ```
333 pub fn peek_child_mut(&mut self, index: usize) -> &mut T {
334 if index >= self.childs_len() {
335 panic!(
336 "Tried to peek child on child {} but current has only {} childs",
337 index,
338 self.childs_len()
339 );
340 }
341
342 unsafe { &mut (*(*self.current.as_ptr()).childs[index].as_ptr()).elem }
343 }
344
345 /// Set 'current' to 'current'.childs\[index\], therefore navigating to this child
346 ///
347 /// # Examples
348 /// ```
349 /// # use libtree::Tree;
350 /// let mut tree = Tree::from_element(0);
351 /// tree.push(1);
352 /// let mut cursor = tree.cursor_mut();
353 /// cursor.navigate_to(0);
354 /// assert_eq!(cursor.peek(), &1);
355 /// ```
356 ///
357 /// # Panics
358 /// This method will panic if index >= self.childs_len
359 pub fn navigate_to(&mut self, index: usize) {
360 if index >= self.childs_len() {
361 panic!(
362 "Tried to navigate to child {} but current has only {} childs",
363 index,
364 self.childs_len()
365 );
366 }
367
368 unsafe {
369 self.current = (*self.current.as_ptr()).childs[index];
370 }
371 }
372
373 /// Set 'current' to 'current'.father, therefore navigating up.
374 ///
375 /// # Examples
376 /// ```
377 /// # use libtree::Tree;
378 /// let mut tree = Tree::from_element(0);
379 /// tree.push(1);
380 /// tree.navigate_to(0);
381 /// let mut cursor = tree.cursor_mut();
382 /// cursor.ascend();
383 /// assert_eq!(cursor.peek(), &0);
384 /// ```
385 ///
386 /// # Panics
387 /// This method will panic if 'current' has no father i.e. if 'current'.father.is_none()
388 pub fn ascend(&mut self) {
389 if !self.has_father() {
390 panic!("Tried to call ascend but current has no father");
391 }
392
393 unsafe {
394 self.current = (*self.current.as_ptr()).father.unwrap();
395 }
396 }
397
398 /// Return true if 'current' has a father.
399 ///
400 /// # Examples
401 /// ```
402 /// # use libtree::Tree;
403 /// let mut tree = Tree::from_element(0);
404 /// tree.push(1);
405 /// tree.navigate_to(0);
406 /// let mut cursor = tree.cursor_mut();
407 /// assert!(cursor.has_father());
408 /// cursor.ascend();
409 /// assert!(!cursor.has_father());
410 /// ```
411 pub fn has_father(&self) -> bool {
412 unsafe { (*self.current.as_ptr()).father.is_some() }
413 }
414
415 /// Return the number of childrens of current.
416 ///
417 /// # Examples
418 /// ```
419 /// # use libtree::Tree;
420 /// let mut tree = Tree::from_element(0);
421 /// tree.push_iter(vec![1, 1, 1, 1, 1]);
422 /// let cursor = tree.cursor_mut();
423 /// assert_eq!(cursor.childs_len(), 5);
424 /// ```
425 pub fn childs_len(&self) -> usize {
426 unsafe { (*self.current.as_ptr()).childs.len() }
427 }
428
429 /// Return an Iterator over the elements stored in 'current'.childs
430 ///
431 /// # Examples
432 /// ```
433 /// # use libtree::Tree;
434 /// let mut tree = Tree::from_element(0);
435 /// tree.push_iter(vec![1, 2, 3]);
436 /// let cursor = tree.cursor_mut();
437 /// assert_eq!(cursor.iter_childs().collect::<Vec<&i32>>(), vec![&1, &2, &3]);
438 /// ```
439 pub fn iter_childs(&self) -> ChildIterator<'a, T> {
440 ChildIterator {
441 current: self.current,
442 i: 0,
443 len: self.childs_len(),
444 _boo: PhantomData,
445 }
446 }
447
448 /// Return an Iterator over the elements stored in 'current'.childs
449 ///
450 /// # Examples
451 /// ```
452 /// # use libtree::Tree;
453 /// let mut tree = Tree::from_element(0);
454 /// tree.push_iter(vec![1, 2, 3]);
455 /// let mut cursor = tree.cursor_mut();
456 /// assert_eq!(cursor.iter_childs_mut().collect::<Vec<&mut i32>>(), vec![&mut 1, &mut 2, &mut 3]);
457 /// ```
458 pub fn iter_childs_mut(&self) -> ChildIteratorMut<'a, T> {
459 ChildIteratorMut {
460 current: self.current,
461 i: 0,
462 len: self.childs_len(),
463 _boo: PhantomData,
464 }
465 }
466
467 /// Iterate over references of element stored in the subtree rooted at 'current' in a
468 /// depth-first way. This is done
469 /// by creating a Vec and pushing every references into this Vec and then returning an iterator
470 /// over this Vec. As it may not be very memory efficient, you might check [CursorMut::lazyiter].
471 ///
472 /// # Examples
473 /// ```
474 /// # use libtree::Tree;
475 /// let mut tree = Tree::from_element(0);
476 /// tree.push_iter(vec![1, 2, 3]);
477 /// tree.navigate_to(1);
478 /// tree.push(4);
479 /// assert_eq!(tree.cursor_mut().iter().collect::<Vec<&i32>>(), vec![&2, &4]);
480 /// ```
481 pub fn iter(&self) -> impl Iterator<Item = &'a T> {
482 let mut container = Vec::new();
483 _iter_rec(self.current, &mut container);
484 container.into_iter()
485 }
486
487 /// Same as [CursorMut::iter], but returns mutable reference instead
488 /// # Examples
489 /// ```
490 /// # use libtree::Tree;
491 /// let mut tree = Tree::from_element(0);
492 /// tree.push_iter(vec![1, 2, 3]);
493 /// tree.navigate_to(1);
494 /// tree.push(4);
495 /// assert_eq!(tree.cursor_mut().iter_mut().collect::<Vec<&mut i32>>(), vec![&mut 2, &mut 4]);
496 pub fn iter_mut(&mut self) -> impl Iterator<Item = &'a mut T> {
497 let mut container = Vec::new();
498 _iter_rec_mut(self.current, &mut container);
499 container.into_iter()
500 }
501
502 /// Iterate over the subtree rooted at 'current' in a lazy depth-first way, returning
503 /// references to the elements stored in the subtree. Although it is lazy iteration, meaning it is
504 /// less stressfull for memory, it is slower than [CursorMut::iter], because the cursor that is used
505 /// to move around the tree has to keep tracks of which branches it has already explored.
506 ///
507 /// # Examples
508 /// ```
509 /// # use libtree::Tree;
510 /// let mut tree = Tree::from_element(0);
511 /// tree.push_iter(vec![1, 2, 3]);
512 /// tree.navigate_to(1);
513 /// tree.push_iter(vec![9, 8]);
514 /// tree.ascend();
515 /// tree.navigate_to(0);
516 /// tree.push_iter(vec![9, 10]);
517 /// tree.navigate_to(0);
518 /// tree.push(15);
519 /// tree.go_to_root();
520 /// let mut cursor = tree.cursor_mut();
521 /// assert_eq!(
522 /// cursor.lazyiter().collect::<Vec<&i32>>(),
523 /// vec![&0, &1, &9, &15, &10, &2, &9, &8, &3]
524 /// );
525 /// cursor.navigate_to(1);
526 /// assert_eq!(cursor.lazyiter().collect::<Vec<&i32>>(), vec![&2, &9, &8]);
527 /// ```
528 pub fn lazyiter(&self) -> LazyTreeIterator<'a, T> {
529 let mut idx_list = LinkedList::new();
530 idx_list.push_back(0);
531 LazyTreeIterator {
532 cursor: Cursor {
533 current: self.current,
534 _boo: PhantomData,
535 },
536 idx_list,
537 _boo: PhantomData,
538 }
539 }
540
541 /// Same as [CursorMut::lazyiter] but returns mutable references instead
542 ///
543 /// # Examples
544 /// ```
545 /// # use libtree::Tree;
546 /// let mut tree = Tree::from_element(0);
547 /// tree.push_iter(vec![1, 2, 3]);
548 /// tree.navigate_to(1);
549 /// tree.push_iter(vec![9, 8]);
550 /// tree.ascend();
551 /// tree.navigate_to(0);
552 /// tree.push_iter(vec![9, 10]);
553 /// tree.navigate_to(0);
554 /// tree.push(15);
555 /// tree.go_to_root();
556 /// let mut cursor = tree.cursor_mut();
557 /// assert_eq!(
558 /// cursor.lazyiter_mut().collect::<Vec<&mut i32>>(),
559 /// vec![&mut 0, &mut 1, &mut 9, &mut 15, &mut 10, &mut 2, &mut 9, &mut 8, &mut 3]
560 /// );
561 /// ```
562 pub fn lazyiter_mut(&mut self) -> LazyTreeIteratorMut<'a, T> {
563 let mut idx_list = LinkedList::new();
564 idx_list.push_back(0);
565 LazyTreeIteratorMut {
566 cursor: UnsafeCursor {
567 current: self.current,
568 _boo: PhantomData,
569 },
570 idx_list,
571 _boo: PhantomData,
572 }
573 }
574
575 /// Push el to 'current'.child as a new node in the tree.
576 ///
577 /// # Examples
578 /// ```
579 /// # use libtree::Tree;
580 /// let mut tree = Tree::from_element(1);
581 /// let mut cursor = tree.cursor_mut();
582 /// cursor.push(2);
583 /// cursor.navigate_to(0);
584 /// assert_eq!(cursor.peek(), &2);
585 /// assert_eq!(tree.into_vec(), vec![1, 2]);
586 /// ```
587 pub fn push(&mut self, el: T) {
588 unsafe {
589 let current_node = &mut *(self.current.as_ptr());
590 current_node
591 .childs
592 .push(NonNull::new_unchecked(Box::into_raw(Box::new(Node {
593 elem: el,
594 childs: Vec::new(),
595 father: Some(self.current),
596 }))))
597 }
598 }
599
600 /// Convenient method to push the elements of an iterator into the tree.
601 /// It's litteraly : for el in iter.into_iter() { tree.push(el) }
602 ///
603 /// # Examples
604 /// ```
605 /// # use libtree::Tree;
606 /// let mut tree = Tree::from_element(0);
607 /// let mut cursor = tree.cursor_mut();
608 /// cursor.push_iter(vec![1, 2, 3]);
609 /// cursor.navigate_to(2);
610 /// assert_eq!(cursor.peek(), &3);
611 /// assert_eq!(tree.into_vec(), vec![0, 1, 2, 3]);
612 /// ```
613 pub fn push_iter<I>(&mut self, iter: I)
614 where
615 I: IntoIterator<Item = T>,
616 {
617 for el in iter.into_iter() {
618 self.push(el);
619 }
620 }
621}
622
623/// An unsafe version of [CursorMut]
624///
625/// # Principle
626/// UnsafeCursor exists to overcome the limitation of [CursorMut]. In order to respect the Rust
627/// ownership system, mutable methods in CursorMut takes &mut self as signature. This means that
628/// has long as the as the mutable reference is alive, it is not possible to mutate the cursor, to
629/// navigate it around the tree, and to get a mutable reference to another node of the tree. If you
630/// had to mutate the tree in multiple place in a concurrent way, it would be impossible with
631/// CursorMut.
632///
633/// In order to achieve this, the narrator only sees two options :
634/// - rewrite everything using RefCell and interior mutability (no.).
635/// - implements a shotgun for the foot of the user of this crate (yes).
636///
637/// ## How do we achieve it
638/// We simply change the signature of methods that return a mutable reference by
639/// `fn peek_mut(&self) -> &mut T`.
640/// Doing so disconnect the link that Rust was making between the &mut self and the &mut T
641/// returned (as a immutable reference would never produce a mutable reference). This mean that we
642/// can now navigate the UnsafeCursor while keeping the mutable reference alive, have multiples
643/// mutable reference alive and even multiples UnsafeCursor alive. But as great powers came with
644/// responsability, we also now can create two mutable references point at the same node
645///
646/// ```
647/// # use libtree::Tree;
648/// let mut tree = Tree::from_element(vec![10]);
649/// let cursor1 = tree.unsafe_cursor();
650/// let cursor2 = tree.unsafe_cursor();
651/// let ref1 = unsafe { cursor1.peek_mut() };
652/// let ref2 = unsafe { cursor2.peek_mut() };
653/// // We now have two mutable references toward [10]
654/// ```
655///
656/// # Safety
657/// Using this unsafe cursor, we see that we have completly bypassed the rust ownership system, and
658/// it will be a problem. What you should avoid at all costs is having two mutable references (or
659/// more) that points at the same object.
660///
661/// But how to prevent this ? The first idea is to have only one UnsafeCursor that does a travel
662/// around the tree but never peek_mut twice on the same node (This how [crate::Tree::lazyiter_mut] is implemented).
663/// The second idea is to not keep the references, but the unsafe cursor and call peek_mut every
664/// times you need to mutate the elements stored. Doing so will always deliver a correct mutable
665/// reference, on the top of stack of pointer. This is why every mutable methods are marked as
666/// unsafe.
667///
668/// UnsafeCursor are safe as long as you make sure to not have two mutable reference (or a
669/// immutable reference followed by a mutable reference) on a same node of tree. The unsafe keyword
670/// is more to warn you about the risk of using UnsafeCursor, but it is up to you to verify that
671/// the use is safe.
672///
673/// To avoid shooting yourself in the foot, UnsafeCursor does not implement any iter methods,
674/// except for children but only as immutable reference (to decide to which branch to navigate).
675///
676/// # A safe usage example
677/// ```
678/// # use libtree::Tree;
679/// let mut tree = Tree::from_element(0);
680/// tree.push_iter(vec![1, 2]);
681/// let mut cursor1 = tree.unsafe_cursor();
682/// let mut cursor2 = tree.unsafe_cursor();
683/// cursor1.navigate_to(0);
684/// cursor2.navigate_to(1);
685/// unsafe {
686/// assert_eq!(cursor1.peek_mut(), &mut 1);
687/// assert_eq!(cursor2.peek_mut(), &mut 2);
688/// }
689/// ```
690///
691/// Anyways, if you don't need, don't use it.
692pub struct UnsafeCursor<'a, T> {
693 pub(crate) current: ChildLink<T>,
694 pub(crate) _boo: PhantomData<&'a T>,
695}
696
697impl<'a, T> UnsafeCursor<'a, T> {
698 /// Peek at 'current', returning a reference to the element stored in 'current'.
699 ///
700 /// # Examples
701 /// ```
702 /// # use libtree::Tree;
703 /// let tree = Tree::from_element(10);
704 /// let cursor = tree.unsafe_cursor();
705 /// assert_eq!(cursor.peek(), &10);
706 /// ```
707 pub fn peek(&self) -> &'a T {
708 unsafe { &(*self.current.as_ptr()).elem }
709 }
710
711 /// Peek at 'current', returning a mutable reference to the element stored in 'current'.
712 ///
713 /// # Safety
714 /// Bad usages of `peek_mut` can lead to two mutable references pointing at the same object. Be
715 /// always sure when you use this method that no other mutable references or normal references
716 /// are alive at the moment you use it.
717 ///
718 /// # Examples
719 /// ```
720 /// # use libtree::Tree;
721 /// let tree = Tree::from_element(1);
722 /// let cursor = tree.unsafe_cursor();
723 /// unsafe {assert_eq!(cursor.peek_mut(), &mut 1);}
724 /// ```
725 pub unsafe fn peek_mut(&self) -> &'a mut T {
726 unsafe { &mut (*self.current.as_ptr()).elem }
727 }
728
729 /// Peek at 'current'.childs\[index\], returning a reference to the element stored.
730 ///
731 /// # Examples
732 /// ```
733 /// # use libtree::Tree;
734 /// let mut tree = Tree::from_element(10);
735 /// tree.push(5);
736 /// let cursor = tree.unsafe_cursor();
737 /// assert_eq!(cursor.peek_child(0), &5);
738 /// ```
739 pub fn peek_child(&self, index: usize) -> &'a T {
740 if index >= self.childs_len() {
741 panic!(
742 "Tried to peek child on child {} but current has only {} childs",
743 index,
744 self.childs_len()
745 );
746 }
747
748 unsafe { &(*(*self.current.as_ptr()).childs[index].as_ptr()).elem }
749 }
750
751 /// Peek at 'current'.childs\[index\], returning a mutable reference to the element stored in
752 /// child.
753 ///
754 /// # Safety
755 /// Bad usages of `peek_child_mut` can lead to two mutable references pointing at the same object. Be
756 /// always sure when you use this method that no other mutable references or normal references
757 /// are alive at the moment you use it.
758 ///
759 /// # Examples
760 /// ```
761 /// # use libtree::Tree;
762 /// let mut tree = Tree::from_element(10);
763 /// tree.push(5);
764 /// let cursor = tree.unsafe_cursor();
765 /// unsafe {assert_eq!(cursor.peek_child_mut(0), &5);}
766 /// ```
767 pub unsafe fn peek_child_mut(&self, index: usize) -> &'a mut T {
768 if index >= self.childs_len() {
769 panic!(
770 "Tried to call peek_child_mut on child {} but current has only {} childs",
771 index,
772 self.childs_len()
773 );
774 }
775
776 unsafe { &mut (*(*self.current.as_ptr()).childs[index].as_ptr()).elem }
777 }
778
779 /// Set 'current' to 'current'.childs\[index\], therefore navigating to this child
780 ///
781 /// # Examples
782 /// ```
783 /// # use libtree::Tree;
784 /// let mut tree = Tree::from_element(0);
785 /// tree.push(1);
786 /// let mut cursor = tree.unsafe_cursor();
787 /// cursor.navigate_to(0);
788 /// assert_eq!(cursor.peek(), &1);
789 /// ```
790 ///
791 /// # Panics
792 /// This method will panic if index >= self.childs_len
793 pub fn navigate_to(&mut self, index: usize) {
794 if index >= self.childs_len() {
795 panic!(
796 "Tried to navigate to child {} but current has only {} childs",
797 index,
798 self.childs_len()
799 );
800 }
801
802 unsafe {
803 self.current = (*self.current.as_ptr()).childs[index];
804 }
805 }
806
807 /// Set 'current' to 'current'.father, therefore navigating up.
808 ///
809 /// # Examples
810 /// ```
811 /// # use libtree::Tree;
812 /// let mut tree = Tree::from_element(0);
813 /// tree.push(1);
814 /// tree.navigate_to(0);
815 /// let mut cursor = tree.unsafe_cursor();
816 /// cursor.ascend();
817 /// assert_eq!(cursor.peek(), &0);
818 /// ```
819 ///
820 /// # Panics
821 /// This method will panic if 'current' has no father i.e. if 'current'.father.is_none()
822 pub fn ascend(&mut self) {
823 if !self.has_father() {
824 panic!("Tried to call ascend but current has no father");
825 }
826
827 unsafe {
828 self.current = (*self.current.as_ptr()).father.unwrap();
829 }
830 }
831
832 /// Return true if 'current' has a father.
833 ///
834 /// # Examples
835 /// ```
836 /// # use libtree::Tree;
837 /// let mut tree = Tree::from_element(0);
838 /// tree.push(1);
839 /// tree.navigate_to(0);
840 /// let mut cursor = tree.unsafe_cursor();
841 /// assert!(cursor.has_father());
842 /// cursor.ascend();
843 /// assert!(!cursor.has_father());
844 /// ```
845 pub fn has_father(&self) -> bool {
846 unsafe { (*self.current.as_ptr()).father.is_some() }
847 }
848
849 /// Return the number of childrens of current.
850 ///
851 /// # Examples
852 /// ```
853 /// # use libtree::Tree;
854 /// let mut tree = Tree::from_element(0);
855 /// tree.push_iter(vec![1, 1, 1, 1, 1]);
856 /// let cursor = tree.unsafe_cursor();
857 /// assert_eq!(cursor.childs_len(), 5);
858 /// ```
859 pub fn childs_len(&self) -> usize {
860 unsafe { (*self.current.as_ptr()).childs.len() }
861 }
862
863 /// Return an Iterator over the elements stored in 'current'.childs
864 ///
865 /// # Examples
866 /// ```
867 /// # use libtree::Tree;
868 /// let mut tree = Tree::from_element(0);
869 /// tree.push_iter(vec![1, 2, 3]);
870 /// let cursor = tree.unsafe_cursor();
871 /// assert_eq!(cursor.iter_childs().collect::<Vec<&i32>>(), vec![&1, &2, &3]);
872 /// ```
873 pub fn iter_childs(&self) -> ChildIterator<'a, T> {
874 ChildIterator {
875 current: self.current,
876 i: 0,
877 len: self.childs_len(),
878 _boo: PhantomData,
879 }
880 }
881
882 /// Push el to 'current'.child as a new node in the tree.
883 ///
884 /// # Examples
885 /// ```
886 /// # use libtree::Tree;
887 /// let mut tree = Tree::from_element(1);
888 /// let mut cursor = tree.unsafe_cursor();
889 /// cursor.push(2);
890 /// cursor.navigate_to(0);
891 /// assert_eq!(cursor.peek(), &2);
892 /// assert_eq!(tree.into_vec(), vec![1, 2]);
893 /// ```
894 pub fn push(&mut self, el: T) {
895 unsafe {
896 let current_node = &mut *(self.current.as_ptr());
897 current_node
898 .childs
899 .push(NonNull::new_unchecked(Box::into_raw(Box::new(Node {
900 elem: el,
901 childs: Vec::new(),
902 father: Some(self.current),
903 }))))
904 }
905 }
906
907 /// Convenient method to push the elements of an iterator into the tree.
908 /// It's litteraly : for el in iter.into_iter() { tree.push(el) }
909 ///
910 /// # Examples
911 /// ```
912 /// # use libtree::Tree;
913 /// let mut tree = Tree::from_element(0);
914 /// let mut cursor = tree.unsafe_cursor();
915 /// cursor.push_iter(vec![1, 2, 3]);
916 /// cursor.navigate_to(2);
917 /// assert_eq!(cursor.peek(), &3);
918 /// assert_eq!(tree.into_vec(), vec![0, 1, 2, 3]);
919 /// ```
920 pub fn push_iter<I>(&mut self, iter: I)
921 where
922 I: IntoIterator<Item = T>,
923 {
924 for el in iter.into_iter() {
925 self.push(el);
926 }
927 }
928}
929
930#[cfg(test)]
931mod test {
932 use super::super::Tree;
933
934 #[test]
935 fn unsafe_cursor1() {
936 let mut tree = Tree::from_element(0);
937 tree.push_iter(vec![1, 2, 3]);
938 tree.navigate_to(1);
939 tree.push_iter(vec![9, 8]);
940 tree.ascend();
941 tree.navigate_to(0);
942 tree.push_iter(vec![9, 10]);
943 tree.navigate_to(0);
944 tree.push(15);
945 tree.go_to_root();
946 let mut cursor1 = tree.unsafe_cursor();
947 cursor1.navigate_to(0);
948 let mut cursor2 = tree.unsafe_cursor();
949 cursor2.navigate_to(1);
950 cursor2.navigate_to(1);
951 unsafe { *cursor1.peek_mut() += 1 };
952 unsafe { *cursor2.peek_mut() += 2 };
953 assert_eq!(
954 tree.lazyiter().collect::<Vec<&i32>>(),
955 vec![&0, &2, &9, &15, &10, &2, &9, &10, &3]
956 );
957 unsafe { *cursor1.peek_mut() -= 10 };
958 assert_eq!(
959 tree.lazyiter().collect::<Vec<&i32>>(),
960 vec![&0, &-8, &9, &15, &10, &2, &9, &10, &3]
961 );
962 }
963
964 #[test]
965 fn unsafe_cursor2() {
966 let mut tree = Tree::from_element(vec![1, 2, 3]);
967 tree.push_iter(vec![vec![4], vec![5, 6, 7, 8]]);
968 let mut cursor1 = tree.unsafe_cursor();
969 cursor1.navigate_to(0);
970 let mut cursor2 = tree.unsafe_cursor();
971 cursor2.navigate_to(1);
972 unsafe { cursor2.peek_mut().push(9) };
973 unsafe { cursor1.peek_mut().pop() };
974 assert_eq!(
975 tree.iter().collect::<Vec<&Vec<i32>>>(),
976 vec![&vec![1, 2, 3], &vec![], &vec![5, 6, 7, 8, 9]]
977 );
978 unsafe {
979 let vec = cursor2.peek_mut();
980 while !vec.is_empty() {
981 vec.pop();
982 }
983 }
984
985 assert_eq!(
986 tree.iter().collect::<Vec<&Vec<i32>>>(),
987 vec![&vec![1, 2, 3], &vec![], &vec![]]
988 );
989 cursor2.push(vec![10]);
990 assert_eq!(
991 tree.iter().collect::<Vec<&Vec<i32>>>(),
992 vec![&vec![1, 2, 3], &vec![], &vec![], &vec![10]]
993 )
994 }
995}