simple_digraph/
lib.rs

1use std::sync::Arc;
2
3#[derive(Clone)]
4pub struct DigraphNode<T> {
5    pub next: DigraphNodeRef<T>, // I made it `pub` to be able `item.next.next()` to remove an item from the middle.
6    data: T,
7}
8
9impl<T> DigraphNode<T> {
10    fn new(next: DigraphNodeRef<T>, data: T) -> Self {
11        Self { next, data }
12    }
13}
14
15pub struct DigraphNodeRef<T> {
16    rc: Option<Arc<DigraphNode<T>>>,
17}
18
19impl<T> DigraphNodeRef<T> {
20    pub fn new() -> Self {
21        Self {
22            rc: None
23        }
24    }
25    pub fn from_node(value: DigraphNode<T>) -> Self {
26        Self::from(Some(Arc::new(value)))
27    }
28    pub fn from(rc: Option<Arc<DigraphNode<T>>>) -> Self {
29        Self {
30            rc
31        }
32    }
33    pub fn as_rc(&self) -> &Option<Arc<DigraphNode<T>>> {
34        &self.rc
35    }
36    pub fn as_rc_mut(&mut self) -> &mut Option<Arc<DigraphNode<T>>> {
37        &mut self.rc
38    }
39    pub fn is_none(&self) -> bool {
40        self.rc.is_none()
41    }
42    pub fn remove(&mut self) -> bool {
43        if let Some(rc) = self.rc.clone() {
44            self.rc = rc.next.rc.clone();
45            true
46        } else {
47            false
48        }
49    }
50    pub fn prepend(&mut self, value: T) -> Self {
51        let new_node = DigraphNode::new(self.clone(), value);
52        let new_node_ref = DigraphNodeRef::from_node(new_node);
53        *self = new_node_ref.clone();
54        new_node_ref
55    }
56    pub fn node(&self) -> Option<DigraphNode<T>>
57        where T: Clone
58    {
59        self.rc.clone().map(|node| (*node).clone())
60    }
61    /// TODO: Should return a reference.
62    pub fn data(&self) -> Option<T>
63        where T: Clone
64    {
65        self.rc.clone().map(|node| (*node).data.clone())
66    }
67    pub fn values(self) -> DigraphNodeValuesIterator<T> {
68        DigraphNodeValuesIterator {
69            underlying: self.clone()
70        }
71    }
72}
73
74impl<T> Clone for DigraphNodeRef<T> {
75    fn clone(&self) -> Self {
76        Self { rc: self.rc.clone() }
77    }
78}
79
80impl<T> Iterator for DigraphNodeRef<T> {
81    type Item = Arc<DigraphNode<T>>;
82
83    fn next(&mut self) -> Option<Self::Item> {
84        if let Some(rc) = self.rc.clone() {
85            self.rc = rc.next.rc.clone();
86            Some(rc.clone())
87        } else {
88            None
89        }
90    }
91}
92
93pub struct DigraphNodeValuesIterator<T> {
94    underlying: DigraphNodeRef<T>,
95}
96
97impl<T: Clone> Iterator for DigraphNodeValuesIterator<T> {
98    type Item = T;
99
100    fn next(&mut self) -> Option<Self::Item> {
101        self.underlying.next().map(|node| node.data.clone())
102    }
103}
104
105#[cfg(test)]
106mod tests {
107    use crate::DigraphNodeRef;
108
109    #[test]
110    fn insert() {
111        let mut list = DigraphNodeRef::new();
112        for i in 0..10 {
113            list.prepend(i);
114        }
115        assert_eq!(list.values().collect::<Vec<i32>>(), (0..10).rev().collect::<Vec<i32>>());
116    }
117
118    #[test]
119    fn pass_two_times() {
120        let mut list = DigraphNodeRef::new();
121        for i in 0..10 {
122            list.prepend(i);
123        }
124        let iter = list.clone();
125        assert_eq!(iter.values().collect::<Vec<i32>>(), (0..10).rev().collect::<Vec<i32>>());
126        let iter = list.clone();
127        assert_eq!(iter.values().collect::<Vec<i32>>(), (0..10).rev().collect::<Vec<i32>>());
128    }
129
130    #[test]
131    fn remove() {
132        let mut list = DigraphNodeRef::new();
133        for i in 0..10 {
134            list.prepend(i);
135        }
136        for _ in 0..5 {
137            list.remove();
138        }
139        assert_eq!(list.values().collect::<Vec<i32>>(), (0..5).rev().collect::<Vec<i32>>());
140    }
141}
simple_digraph/lib.rs

simple_digraph/
lib.rs
