fast_list/
walker.rs

1use crate::linked_list::{LinkedList, LinkedListIndex, LinkedListItem};
2
3/// Shamelessly stolen/inspired by https://docs.rs/petgraph/0.4.13/src/petgraph/visit/traversal.rs.html#355-370
4
5/// A walker is a traversal state, but where part of the traversal
6/// information is supplied manually to each next call.
7///
8/// This for example allows graph traversals that don't hold a borrow of the
9/// graph they are traversing.
10pub trait Walker<Context> {
11    type Item;
12    /// Advance to the next item
13    fn walk_next(&mut self, context: Context) -> Option<Self::Item>;
14
15    /// Create an iterator out of the walker and given `context`.
16    fn iter(self, context: Context) -> WalkerIter<Self, Context>
17    where
18        Self: Sized,
19        Context: Clone,
20    {
21        WalkerIter {
22            walker: self,
23            context,
24        }
25    }
26}
27
28/// A walker and its context wrapped into an iterator.
29#[derive(Clone, Debug)]
30pub struct WalkerIter<W, C> {
31    walker: W,
32    context: C,
33}
34
35impl<W, C> WalkerIter<W, C>
36where
37    W: Walker<C>,
38    C: Clone,
39{
40    pub fn context(&self) -> C {
41        self.context.clone()
42    }
43
44    pub fn inner_ref(&self) -> &W {
45        &self.walker
46    }
47
48    pub fn inner_mut(&mut self) -> &mut W {
49        &mut self.walker
50    }
51}
52
53impl<W, C> Iterator for WalkerIter<W, C>
54where
55    W: Walker<C>,
56    C: Clone,
57{
58    type Item = W::Item;
59    fn next(&mut self) -> Option<Self::Item> {
60        self.walker.walk_next(self.context.clone())
61    }
62}
63
64impl<'a, C, W: ?Sized> Walker<C> for &'a mut W
65where
66    W: Walker<C>,
67{
68    type Item = W::Item;
69    fn walk_next(&mut self, context: C) -> Option<Self::Item> {
70        (**self).walk_next(context)
71    }
72}
73
74pub struct LinkedListWalker {
75    /// The current index in the list
76    current: Option<LinkedListIndex>,
77    /// If true walk in reverse order (from tail to head)
78    reverse: bool,
79}
80
81impl LinkedListWalker {
82    pub fn new<T>(list: &LinkedList<T>, start: LinkedListIndex, reverse: bool) -> Self {
83        Self {
84            current: Some(start),
85            reverse: reverse,
86        }
87    }
88}
89
90impl<T> Walker<&LinkedList<T>> for LinkedListWalker {
91    type Item = LinkedListIndex;
92
93    /// Advance to the next item, returns the indices of the items in the list and
94    /// does not hold a borrow of the list, allowing for mutation while traversing.
95    ///
96    /// ## Excludes the starting index
97    fn walk_next(&mut self, context: &LinkedList<T>) -> Option<Self::Item> {
98        if let Some(current) = self.current {
99            return if self.reverse {
100                context.get(current).and_then(|item| {
101                    self.current = item.prev_index;
102                    item.prev_index
103                })
104            } else {
105                context.get(current).and_then(|item| {
106                    self.current = item.next_index;
107                    item.next_index
108                })
109            };
110        }
111        None
112    }
113}
114
115// impl<G> Walker<G> for Dfs<G::NodeId, G::Map>
116//     where G: IntoNeighbors + Visitable
117// {
118//     type Item = G::NodeId;
119//     fn walk_next(&mut self, context: G) -> Option<Self::Item> {
120//         self.next(context)
121//     }
122// }
123
124// impl<G> Walker<G> for DfsPostOrder<G::NodeId, G::Map>
125//     where G: IntoNeighbors + Visitable
126// {
127//     type Item = G::NodeId;
128//     fn walk_next(&mut self, context: G) -> Option<Self::Item> {
129//         self.next(context)
130//     }
131// }
132
133#[cfg(test)]
134mod tests {
135    use super::*;
136
137    #[test]
138    pub fn test_list_walker() {
139        let mut list = LinkedList::new();
140        list.extend(0..=100);
141        let mut count = 0;
142        let mut walker = LinkedListWalker::new(&list, list.tail.unwrap(), true);
143
144        assert_eq!(list.get(list.head.unwrap()).unwrap().value, 0);
145        assert_eq!(list.get(list.tail.unwrap()).unwrap().value, 100);
146
147        list.tail_mut().unwrap().value = 0;
148        while let Some(index) = walker.walk_next(&list) {
149            count += 1;
150            list.get_mut(index).unwrap().value = count;
151            // let value = list.get(index).unwrap().value;
152            // println!("{:?} - {:?} - {:?}", value, index, count);
153        }
154
155        assert_eq!(count, 100);
156        assert_eq!(list.get(list.head.unwrap()).unwrap().value, 100);
157        assert_eq!(list.get(list.tail.unwrap()).unwrap().value, 0);
158    }
159}
fast_list/walker.rs

fast_list/
walker.rs
