standard_lib/collections/linked/cursor/
cursor.rs

1use std::hash::{Hash, Hasher};
2use std::hint;
3use std::marker::PhantomData;
4
5use derive_more::IsVariant;
6
7use super::{State, StateMut};
8use crate::collections::linked::list::{Length, LinkedList, ListContents, ListState, Node, NodePtr};
9use crate::util::error::{CapacityOverflow, IndexOutOfBounds};
10use crate::util::result::ResultExtension;
11
12/// A type for bi-directional traversal and mutation of [`LinkedList`]s. See
13/// [`LinkedList::cursor_front`] and [`LinkedList::cursor_back`] to create one.
14#[derive(Hash)]
15pub struct Cursor<T> {
16    pub(crate) state: CursorState<T>,
17    pub(crate) _phantom: PhantomData<T>,
18}
19
20#[derive(Hash, IsVariant)]
21pub(crate) enum CursorState<T> {
22    Empty,
23    Full(CursorContents<T>),
24}
25
26#[derive(Hash)]
27pub(crate) struct CursorContents<T> {
28    pub list: ListContents<T>,
29    pub pos: CursorPosition<T>,
30}
31
32use CursorState::*;
33
34#[derive(IsVariant)]
35pub(crate) enum CursorPosition<T> {
36    Head,
37    Tail,
38    Ptr { ptr: NodePtr<T>, index: usize },
39}
40
41use CursorPosition::*;
42
43impl<T> Cursor<T> {
44    pub const fn list(self) -> LinkedList<T> {
45        match self.state {
46            Empty => LinkedList {
47                state: ListState::Empty,
48                _phantom: PhantomData,
49            },
50            Full(CursorContents { list, .. }) => LinkedList {
51                state: ListState::Full(list),
52                _phantom: PhantomData,
53            },
54        }
55    }
56
57    pub const fn index(&self) -> Option<usize> {
58        match &self.state {
59            Empty => None,
60            Full(CursorContents { pos, .. }) => match pos {
61                Head | Tail => None,
62                Ptr { index, .. } => Some(*index),
63            },
64        }
65    }
66
67    pub const fn read(&self) -> Option<&T> {
68        match &self.state {
69            Empty => None,
70            Full(CursorContents { pos, .. }) => match pos {
71                Ptr { ptr, .. } => Some(ptr.value()),
72                _ => None,
73            },
74        }
75    }
76
77    pub const fn read_mut(&mut self) -> Option<&mut T> {
78        match &mut self.state {
79            Empty => None,
80            Full(CursorContents { pos, .. }) => match pos {
81                Ptr { ptr, .. } => Some(ptr.value_mut()),
82                _ => None,
83            },
84        }
85    }
86
87    pub const fn read_next(&self) -> Option<&T> {
88        match &self.state {
89            Empty => None,
90            Full(CursorContents { list, pos }) => match pos {
91                Head => Some(list.head.value()),
92                Tail => None,
93                Ptr { ptr, .. } => match ptr.next() {
94                    Some(next_node) => Some(next_node.value()),
95                    None => None,
96                },
97            },
98        }
99    }
100
101    pub const fn read_next_mut(&mut self) -> Option<&mut T> {
102        match &mut self.state {
103            Empty => None,
104            Full(CursorContents { list, pos }) => match pos {
105                Head => Some(list.head.value_mut()),
106                Tail => None,
107                Ptr { ptr, .. } => match ptr.next_mut() {
108                    Some(next_node) => Some(next_node.value_mut()),
109                    None => None,
110                },
111            },
112        }
113    }
114
115    pub const fn read_prev(&self) -> Option<&T> {
116        match &self.state {
117            Empty => None,
118            Full(CursorContents { list, pos }) => match pos {
119                Head => None,
120                Tail => Some(list.tail.value()),
121                Ptr { ptr, .. } => match ptr.prev() {
122                    Some(prev_node) => Some(prev_node.value()),
123                    None => None,
124                },
125            },
126        }
127    }
128
129    pub const fn read_prev_mut(&mut self) -> Option<&mut T> {
130        match &mut self.state {
131            Empty => None,
132            Full(CursorContents { list, pos }) => match pos {
133                Head => None,
134                Tail => Some(list.tail.value_mut()),
135                Ptr { ptr, .. } => match ptr.prev_mut() {
136                    Some(prev_node) => Some(prev_node.value_mut()),
137                    None => None,
138                },
139            },
140        }
141    }
142
143    pub const fn move_next(&mut self) -> &mut Self {
144        match &mut self.state {
145            Empty => (),
146            Full(CursorContents { list, pos }) => match pos {
147                Head => *pos = Ptr {
148                    ptr: list.head,
149                    index: 0,
150                },
151                Tail => (),
152                Ptr { ptr, index } => *pos = match ptr.next() {
153                    Some(next_node) => Ptr {
154                        ptr: *next_node,
155                        index: *index + 1,
156                    },
157                    None => Tail,
158                },
159            },
160        }
161        self
162    }
163
164    pub const fn move_prev(&mut self) -> &mut Self {
165        match &mut self.state {
166            Empty => (),
167            Full(CursorContents { list, pos }) => match pos {
168                Head => (),
169                Tail => *pos = Ptr {
170                    ptr: list.tail,
171                    index: list.last_index(),
172                },
173                Ptr { ptr, index } => *pos = match ptr.prev() {
174                    Some(prev_node) => Ptr {
175                        ptr: *prev_node,
176                        index: *index - 1,
177                    },
178                    None => Head,
179                },
180            },
181        }
182        self
183    }
184
185    pub fn push_next(&mut self, value: T) {
186        match &mut self.state {
187            Empty => self.state = CursorState::single(value, Head),
188            Full(CursorContents { list, pos }) => match pos {
189                Head => list.push_front(value),
190                Tail => list.push_back(value),
191                Ptr { ptr, .. } => {
192                    list.len = list.len.checked_add(1).ok_or(CapacityOverflow).throw();
193
194                    let node = NodePtr::from_node(Node {
195                        value,
196                        prev: Some(*ptr),
197                        next: *ptr.next(),
198                    });
199
200                    match ptr.next_mut() {
201                        Some(second_next) => *second_next.prev_mut() = Some(node),
202                        None => list.tail = node,
203                    }
204                    *ptr.next_mut() = Some(node)
205                },
206            },
207        }
208    }
209
210    pub fn push_prev(&mut self, value: T) {
211        match &mut self.state {
212            Empty => self.state = CursorState::single(value, Tail),
213            Full(CursorContents { list, pos }) => match pos {
214                Head => list.push_front(value),
215                Tail => list.push_back(value),
216                Ptr { ptr, .. } => {
217                    list.len = list.len.checked_add(1).ok_or(CapacityOverflow).throw();
218
219                    let node = NodePtr::from_node(Node {
220                        value,
221                        prev: *ptr.prev(),
222                        next: Some(*ptr),
223                    });
224
225                    match ptr.prev_mut() {
226                        Some(second_prev) => *second_prev.next_mut() = Some(node),
227                        None => list.head = node,
228                    }
229                    *ptr.prev_mut() = Some(node)
230                },
231            },
232        }
233    }
234
235    pub fn pop_next(&mut self) -> Option<T> {
236        match &mut self.state {
237            Empty => None,
238            Full(CursorContents { list, pos }) => {
239                match pos {
240                    Head => {
241                        let node = list.head.take_node();
242                        match node.next {
243                            Some(next_node) => {
244                                *next_node.prev_mut() = None;
245                                list.head = next_node;
246                                // SAFETY: We've removed 1 node from a list we know to have at least
247                                // two: node and next_node.
248                                list.len = unsafe { list.len.checked_sub(1).unwrap_unchecked() };
249                            },
250                            None => self.state = Empty,
251                        }
252                        Some(node.value)
253                    },
254                    Tail => None,
255                    Ptr { ptr, .. } => {
256                        match ptr.next_mut() {
257                            Some(next_ptr) => {
258                                let next_node = next_ptr.take_node();
259                                match next_node.next {
260                                    Some(second_next) => {
261                                        *second_next.prev_mut() = Some(*ptr);
262                                        *ptr.next_mut() = Some(second_next);
263                                    },
264                                    None => {
265                                        list.tail = *ptr;
266                                        *ptr.next_mut() = None;
267                                    },
268                                }
269                                // SAFETY: We've removed 1 node from a list we know to have at least
270                                // two, pointed to by ptr and next_ptr.
271                                list.len = unsafe { list.len.checked_sub(1).unwrap_unchecked() };
272                                Some(next_node.value)
273                            },
274                            // We are on a node without a next value, so we return None, despite not
275                            // being empty.
276                            None => None,
277                        }
278                    },
279                }
280            },
281        }
282    }
283
284    pub fn pop_prev(&mut self) -> Option<T> {
285        match &mut self.state {
286            Empty => None,
287            Full(CursorContents { list, pos }) => {
288                match pos {
289                    Head => None,
290                    Tail => {
291                        let node = list.tail.take_node();
292                        match node.prev {
293                            Some(prev_node) => {
294                                *prev_node.next_mut() = None;
295                                list.head = prev_node;
296                                // SAFETY: We've removed 1 node from a list we know to have at least
297                                // two: node and next_node.
298                                list.len = unsafe { list.len.checked_sub(1).unwrap_unchecked() };
299                            },
300                            None => self.state = Empty,
301                        }
302                        Some(node.value)
303                    },
304                    Ptr { ptr, .. } => {
305                        match ptr.prev_mut() {
306                            Some(prev_ptr) => {
307                                let prev_node = prev_ptr.take_node();
308                                match prev_node.prev {
309                                    Some(second_prev) => {
310                                        *second_prev.next_mut() = Some(*ptr);
311                                        *ptr.prev_mut() = Some(second_prev);
312                                    },
313                                    None => {
314                                        list.head = *ptr;
315                                        *ptr.prev_mut() = None;
316                                    },
317                                }
318                                // SAFETY: We've removed 1 node from a list we know to have at least
319                                // two, pointed to by ptr and prev_ptr.
320                                list.len = unsafe { list.len.checked_sub(1).unwrap_unchecked() };
321                                Some(prev_node.value)
322                            },
323                            // We are on a node without a next value, so we return None, despite not
324                            // being empty.
325                            None => None,
326                        }
327                    },
328                }
329            },
330        }
331    }
332
333    pub const fn state<'a>(&'a self) -> State<'a, T> {
334        match &self.state {
335            Empty => State::Empty,
336            Full(CursorContents { pos, .. }) => match pos {
337                Head => State::Head,
338                Tail => State::Tail,
339                Ptr { ptr, .. } => State::Node(ptr.value()),
340            },
341        }
342    }
343
344    pub const fn state_mut<'a>(&'a mut self) -> StateMut<'a, T> {
345        match &mut self.state {
346            Empty => StateMut::Empty,
347            Full(CursorContents { pos, .. }) => match pos {
348                Head => StateMut::Head,
349                Tail => StateMut::Tail,
350                Ptr { ptr, .. } => StateMut::Node(ptr.value_mut()),
351            },
352        }
353    }
354
355    pub const fn is_head(&self) -> bool {
356        match &self.state {
357            Empty => false,
358            Full(CursorContents { pos, .. }) => pos.is_head(),
359        }
360    }
361
362    pub const fn is_tail(&self) -> bool {
363        match &self.state {
364            Empty => false,
365            Full(CursorContents { pos, .. }) => pos.is_tail(),
366        }
367    }
368
369    pub fn read_offset(&self, offset: isize) -> Option<&T> {
370        match &self.state {
371            Empty => None,
372            Full(CursorContents { list, pos }) => match offset.signum() {
373                0 => match pos {
374                    Ptr { ptr, .. } => Some(ptr.value()),
375                    _ => None,
376                },
377                -1 => {
378                    let (mut ptr, mut steps) = match pos {
379                        Head => return None,
380                        Tail => (list.tail, offset.abs() - 1),
381                        Ptr { ptr, .. } => (*ptr, offset.abs()),
382                    };
383
384                    while steps > 0 {
385                        ptr = (*ptr.prev())?;
386                        steps -= 1;
387                    }
388
389                    Some(ptr.value())
390                },
391                1 => {
392                    let (mut ptr, mut steps) = match pos {
393                        Head => return None,
394                        Tail => (list.head, offset),
395                        Ptr { ptr, .. } => (*ptr, offset),
396                    };
397
398                    while steps > 0 {
399                        ptr = (*ptr.next())?;
400                        steps -= 1;
401                    }
402
403                    Some(ptr.value())
404                },
405                // SAFETY: signum returns only one of the options above.
406                _ => unsafe { hint::unreachable_unchecked() },
407            },
408        }
409    }
410
411    pub fn read_offset_mut(&mut self, offset: isize) -> Option<&mut T> {
412        match &mut self.state {
413            Empty => None,
414            Full(CursorContents { list, pos }) => match offset.signum() {
415                0 => match pos {
416                    Ptr { ptr, .. } => Some(ptr.value_mut()),
417                    _ => None,
418                },
419                -1 => {
420                    let (mut ptr, mut steps) = match pos {
421                        Head => return None,
422                        Tail => (list.tail, offset.abs() - 1),
423                        Ptr { ptr, .. } => (*ptr, offset.abs()),
424                    };
425
426                    while steps > 0 {
427                        ptr = (*ptr.prev())?;
428                        steps -= 1;
429                    }
430
431                    Some(ptr.value_mut())
432                },
433                1 => {
434                    let (mut ptr, mut steps) = match pos {
435                        Head => return None,
436                        Tail => (list.head, offset),
437                        Ptr { ptr, .. } => (*ptr, offset),
438                    };
439
440                    while steps > 0 {
441                        ptr = (*ptr.next())?;
442                        steps -= 1;
443                    }
444
445                    Some(ptr.value_mut())
446                },
447                // SAFETY: signum returns only one of the options above.
448                _ => unsafe { hint::unreachable_unchecked() },
449            },
450        }
451    }
452
453    pub const fn move_offset(&mut self, offset: isize) -> &mut Self {
454        match &mut self.state {
455            Empty => (),
456            Full(CursorContents { list, pos }) => match offset.signum() {
457                0 => (),
458                -1 => {
459                    let (mut ptr, mut steps, mut index) = match pos {
460                        Head => return self,
461                        Tail => (list.tail, offset.unsigned_abs() - 1, list.last_index()),
462                        Ptr { ptr, index } => (*ptr, offset.unsigned_abs(), *index),
463                    };
464                    index -= steps;
465
466                    while steps > 0 {
467                        ptr = match *ptr.prev() {
468                            Some(p) => p,
469                            None => {
470                                *pos = Tail;
471                                return self;
472                            },
473                        };
474                        steps -= 1;
475                    }
476
477                    *pos = Ptr { ptr, index };
478                },
479                1 => {
480                    let (mut ptr, mut steps, mut index) = match pos {
481                        Head => return self,
482                        Tail => (list.head, offset as usize, 0),
483                        Ptr { ptr, index } => (*ptr, offset as usize, *index),
484                    };
485                    index += steps;
486
487                    while steps > 0 {
488                        ptr = match *ptr.next() {
489                            Some(p) => p,
490                            None => {
491                                *pos = Head;
492                                return self;
493                            },
494                        };
495                        steps -= 1;
496                    }
497
498                    *pos = Ptr { ptr, index };
499                },
500                // SAFETY: signum returns only one of the options above.
501                _ => unsafe { hint::unreachable_unchecked() },
502            },
503        }
504        self
505    }
506
507    pub fn move_to(&mut self, index: usize) -> &mut Self {
508        self.try_move_to(index).throw()
509    }
510
511    pub fn try_move_to(&mut self, index: usize) -> Result<&mut Self, IndexOutOfBounds> {
512        let contents = self.checked_contents_for_index_mut(index)?;
513        contents.pos = Ptr {
514            ptr: contents.seek(index),
515            index,
516        };
517        Ok(self)
518    }
519
520    pub const fn split_before(self) -> (LinkedList<T>, LinkedList<T>) {
521        match &self.state {
522            Empty => (LinkedList::new(), LinkedList::new()),
523            Full(CursorContents { list, pos }) => match pos {
524                Head => (LinkedList::new(), self.list()),
525                Tail => (self.list(), LinkedList::new()),
526                Ptr { index, .. } if *index == 0 => (LinkedList::new(), self.list()),
527                Ptr { ptr, index } => (
528                    LinkedList {
529                        state: ListState::Full(ListContents {
530                            // SAFETY: index = 0 matches the previous branch.
531                            len: unsafe { Length::new_unchecked(*index) },
532                            head: list.head,
533                            // SAFETY: index != 0, so prev is Some.
534                            tail: unsafe { ptr.prev().unwrap_unchecked() },
535                        }),
536                        _phantom: PhantomData,
537                    },
538                    LinkedList {
539                        state: ListState::Full(ListContents {
540                            // SAFETY: index is in the range 0..list.len so list.len - index as at
541                            // least 1.
542                            len: unsafe { Length::new_unchecked(list.len.get() - *index) },
543                            head: *ptr,
544                            tail: list.tail,
545                        }),
546                        _phantom: PhantomData,
547                    },
548                ),
549            },
550        }
551    }
552
553    pub const fn split_after(self) -> (LinkedList<T>, LinkedList<T>) {
554        match &self.state {
555            Empty => (LinkedList::new(), LinkedList::new()),
556            Full(CursorContents { list, pos }) => match pos {
557                Head => (LinkedList::new(), self.list()),
558                Tail => (self.list(), LinkedList::new()),
559                Ptr { index, .. } if *index == list.last_index() => {
560                    (LinkedList::new(), self.list())
561                },
562                Ptr { ptr, index } => (
563                    LinkedList {
564                        state: ListState::Full(ListContents {
565                            // SAFETY: value is at least 1.
566                            len: unsafe { Length::new_unchecked(*index + 1) },
567                            head: list.head,
568                            tail: *ptr,
569                        }),
570                        _phantom: PhantomData,
571                    },
572                    LinkedList {
573                        state: ListState::Full(ListContents {
574                            // SAFETY: index = list.last_index() matches the previous branch, so
575                            // list.last_index() - index is > 0.
576                            len: unsafe { Length::new_unchecked(list.last_index() - *index) },
577                            // SAFETY: index = list.last_index() matches the previous branch, so
578                            // next is Some.
579                            head: unsafe { ptr.next().unwrap_unchecked() },
580                            tail: list.tail,
581                        }),
582                        _phantom: PhantomData,
583                    },
584                ),
585            },
586        }
587    }
588}
589
590impl<T> Cursor<T> {
591    pub const fn len(&self) -> usize {
592        match &self.state {
593            Empty => 0,
594            Full(CursorContents { list, .. }) => list.len.get(),
595        }
596    }
597
598    pub const fn is_empty(&self) -> bool {
599        self.state.is_empty()
600    }
601
602    pub const fn front(&self) -> Option<&T> {
603        match &self.state {
604            Empty => None,
605            Full(CursorContents { list, .. }) => Some(list.head.value()),
606        }
607    }
608
609    pub const fn front_mut(&mut self) -> Option<&mut T> {
610        match &mut self.state {
611            Empty => None,
612            Full(CursorContents { list, .. }) => Some(list.head.value_mut()),
613        }
614    }
615
616    pub const fn back(&self) -> Option<&T> {
617        match &self.state {
618            Empty => None,
619            Full(CursorContents { list, .. }) => Some(list.tail.value()),
620        }
621    }
622
623    pub const fn back_mut(&mut self) -> Option<&mut T> {
624        match &mut self.state {
625            Empty => None,
626            Full(CursorContents { list, .. }) => Some(list.tail.value_mut()),
627        }
628    }
629
630    pub fn push_front(&mut self, value: T) {
631        match &mut self.state {
632            Empty => self.state = CursorState::single(value, Head),
633            Full(CursorContents { list, .. }) => list.push_front(value),
634        }
635    }
636
637    pub fn push_back(&mut self, value: T) {
638        match &mut self.state {
639            Empty => self.state = CursorState::single(value, Head),
640            Full(CursorContents { list, .. }) => list.push_back(value),
641        }
642    }
643
644    pub fn pop_front(&mut self) -> Option<T> {
645        match &mut self.state {
646            Empty => None,
647            Full(CursorContents { list, pos }) => {
648                match pos {
649                    // If we're pointing to the node we need to pop, move to head. Might be strange
650                    // but at least its obvious that we've moved.
651                    Ptr { ptr, .. } if *ptr == list.head => *pos = Head,
652                    _ => (),
653                }
654
655                let node = list.head.take_node();
656
657                match list.len.checked_sub(1) {
658                    Some(new_len) => {
659                        // SAFETY: Previous length is greater than 1, so the last element is
660                        // preceded by at least one more.
661                        let new_head = unsafe { node.next.unwrap_unchecked() };
662                        list.head = new_head;
663                        *new_head.prev_mut() = None;
664                        list.len = new_len;
665                    },
666                    None => self.state = Empty,
667                }
668
669                Some(node.value)
670            },
671        }
672    }
673
674    pub fn pop_back(&mut self) -> Option<T> {
675        match &mut self.state {
676            Empty => None,
677            Full(CursorContents { list, pos }) => {
678                match pos {
679                    Ptr { ptr, .. } if *ptr == list.tail => *pos = Tail,
680                    _ => (),
681                }
682
683                let node = list.tail.take_node();
684
685                match list.len.checked_sub(1) {
686                    Some(new_len) => {
687                        // SAFETY: Previous length is greater than 1, so the last element is
688                        // preceded by at least one more.
689                        let new_tail = unsafe { node.prev.unwrap_unchecked() };
690                        list.tail = new_tail;
691                        *new_tail.prev_mut() = None;
692                        list.len = new_len;
693                    },
694                    None => self.state = Empty,
695                }
696
697                Some(node.value)
698            },
699        }
700    }
701
702    pub fn get(&self, index: usize) -> &T {
703        self.checked_seek(index).throw().value()
704    }
705
706    pub fn try_get(&self, index: usize) -> Option<&T> {
707        Some(self.checked_seek(index).ok()?.value())
708    }
709
710    pub fn get_mut(&mut self, index: usize) -> &mut T {
711        self.checked_seek(index).throw().value_mut()
712    }
713
714    pub fn try_get_mut(&mut self, index: usize) -> Option<&mut T> {
715        Some(self.checked_seek(index).ok()?.value_mut())
716    }
717
718    // TODO: more redirection to list functions
719}
720
721impl<T> Cursor<T> {
722    pub(crate) fn checked_seek(&self, index: usize) -> Result<NodePtr<T>, IndexOutOfBounds> {
723        Ok(self.checked_contents_for_index(index)?.seek(index))
724    }
725
726    pub(crate) const fn checked_contents_for_index(
727        &self,
728        index: usize,
729    ) -> Result<&CursorContents<T>, IndexOutOfBounds> {
730        match &self.state {
731            Empty => Err(IndexOutOfBounds { index, len: 0 }),
732            Full(contents) => {
733                let len = contents.list.len.get();
734                if index < len {
735                    Ok(contents)
736                } else {
737                    Err(IndexOutOfBounds { index, len })
738                }
739            },
740        }
741    }
742
743    pub(crate) const fn checked_contents_for_index_mut(
744        &mut self,
745        index: usize,
746    ) -> Result<&mut CursorContents<T>, IndexOutOfBounds> {
747        match &mut self.state {
748            Empty => Err(IndexOutOfBounds { index, len: 0 }),
749            Full(contents) => {
750                let len = contents.list.len.get();
751                if index < len {
752                    Ok(contents)
753                } else {
754                    Err(IndexOutOfBounds { index, len })
755                }
756            },
757        }
758    }
759}
760
761impl<T> CursorState<T> {
762    pub(crate) fn single(value: T, pos: CursorPosition<T>) -> CursorState<T> {
763        Full(CursorContents {
764            list: ListContents::wrap_one(value),
765            pos,
766        })
767    }
768}
769
770impl<T> CursorContents<T> {
771    pub fn seek(&self, target: usize) -> NodePtr<T> {
772        match self.pos {
773            Head | Tail => self.list.seek(target),
774            Ptr { ptr, index } => {
775                let end = if target < self.list.len.get() / 2 {
776                    (self.list.head, 0)
777                } else {
778                    (self.list.tail, self.list.last_index())
779                };
780
781                let offset_ptr = target as i128 - index as i128;
782                let ptr_dist = offset_ptr.unsigned_abs() as usize;
783
784                let offset_end = target as i128 - end.1 as i128;
785                let end_dist = offset_end.unsigned_abs() as usize;
786
787                if ptr_dist < end_dist {
788                    self.seek_n(ptr_dist, ptr, offset_ptr.is_positive())
789                } else {
790                    self.seek_n(end_dist, end.0, offset_end.is_positive())
791                }
792            },
793        }
794    }
795
796    pub fn seek_n(&self, count: usize, start: NodePtr<T>, forward: bool) -> NodePtr<T> {
797        if forward {
798            self.list.seek_fwd(count, start)
799        } else {
800            self.list.seek_bwd(count, start)
801        }
802    }
803}
804
805impl<T> Hash for CursorPosition<T> {
806    fn hash<H: Hasher>(&self, state: &mut H) {
807        match self {
808            Ptr { index, .. } => index.hash(state),
809            other => core::mem::discriminant(other).hash(state),
810        }
811    }
812}
813
814// impl<T: Debug> Debug for Cursor<T> {
815//     fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
816//         f.debug_struct("Cursor")
817//             // .field("list", &self.list)
818//             .field("curr", &self.curr.value())
819//             .finish()
820//     }
821// }
standard_lib/collections/linked/cursor/cursor.rs

standard_lib/collections/linked/cursor/
cursor.rs
