rust_ds/linked_lists/double/
mod.rs

1use super::ExtNode as Node;
2use super::{Error, Result};
3use std::cell::RefCell;
4use std::clone::Clone;
5use std::fmt::Debug;
6use std::rc::Rc;
7
8/// `Double` is a double linked list referencing the head, the tail node node and the length of the list.
9#[derive(Debug)]
10pub struct Double<T> {
11    head: Option<Rc<RefCell<Node<T>>>>,
12    tail: Option<Rc<RefCell<Node<T>>>>,
13    len: usize,
14}
15
16impl<T> Default for Double<T>
17where
18    T: Debug + PartialEq + Clone,
19{
20    fn default() -> Self {
21        Self::new()
22    }
23}
24
25impl<T> Double<T>
26where
27    T: Debug + PartialEq + Clone,
28{
29    /// Create a new instance of the `Double` linked list.
30    pub fn new() -> Self {
31        Double {
32            head: None,
33            tail: None,
34            len: 0,
35        }
36    }
37    /// Append a new value to the end of the list.
38    pub fn append(&mut self, value: T) {
39        let new_node = Rc::new(RefCell::new(Node::new(value)));
40
41        match self.head.as_mut() {
42            None => {
43                self.tail = Some(new_node.clone());
44                self.head = Some(new_node);
45            }
46            Some(current) => {
47                let mut current = current.clone();
48                while current.borrow().get_next().is_some() {
49                    current = unsafe {
50                        current
51                            .as_ptr()
52                            .as_ref()
53                            .unwrap()
54                            .get_next()
55                            .clone()
56                            .unwrap()
57                    };
58                }
59                new_node
60                    .borrow_mut()
61                    .set_previous(Some(Rc::downgrade(&current)));
62                self.tail = Some(new_node.clone());
63                current.borrow_mut().set_next(Some(new_node));
64            }
65        }
66        self.len += 1;
67    }
68    /// Remove a node from the list.
69    /// Returns true if the value is found and removed.
70    /// If the value is not found, it returns an error.
71    pub fn remove(&mut self, value: T) -> Result<bool> {
72        if self.is_empty() {
73            return Err(Error::EmptyList);
74        }
75
76        match self.head.as_mut() {
77            None => return Err(Error::EmptyList),
78            Some(current) => {
79                let mut current = current.clone();
80                if *current.borrow().get_value() == value {
81                    let next = current.borrow_mut().get_next_mut().take();
82                    self.head = std::mem::replace(&mut self.head, next);
83                    if let Some(next) = self.head.as_mut() {
84                        next.borrow_mut().set_previous(None);
85                    }
86                    self.len -= 1;
87                    return Ok(true);
88                }
89
90                while current.borrow().get_next().is_some() {
91                    if let Some(next) = current.borrow_mut().get_next_mut().take() {
92                        if *next.borrow().get_value() == value {
93                            if let Some(next_next) = next.borrow().get_next() {
94                                next_next
95                                    .borrow_mut()
96                                    .set_previous(Some(Rc::downgrade(&current)));
97                                unsafe {
98                                    current
99                                        .as_ptr()
100                                        .as_mut()
101                                        .unwrap()
102                                        .get_next_mut()
103                                        .replace(next_next.clone());
104                                }
105                            }
106                            self.len -= 1;
107                            return Ok(true);
108                        }
109                    }
110                    current = unsafe {
111                        current
112                            .as_ptr()
113                            .as_ref()
114                            .unwrap()
115                            .get_next()
116                            .clone()
117                            .unwrap()
118                    };
119                }
120                if current.borrow().get_next().is_none() && *current.borrow().get_value() == value {
121                    let previous = current
122                        .borrow()
123                        .get_previous()
124                        .clone()
125                        .unwrap()
126                        .upgrade()
127                        .unwrap();
128                    previous.borrow_mut().set_next(None);
129                    self.tail = Some(previous);
130                    self.len -= 1;
131                    return Ok(true);
132                }
133            }
134        }
135        Err(Error::ValueNotFound)
136    }
137    /// Search for a value in the list, returns true if the value is found.
138    /// If the value is not found, it returns an error.
139    pub fn search(&self, value: T) -> Result<bool> {
140        match self.head.as_ref() {
141            None => return Err(Error::EmptyList),
142            Some(current) => {
143                let mut current = current;
144                if current.borrow().get_next().is_none() {
145                    return Ok(*current.borrow().get_value() == value);
146                }
147                while current.borrow().get_next().is_some() {
148                    if *current.borrow().get_value() == value {
149                        return Ok(true);
150                    }
151                    current = unsafe {
152                        current
153                            .as_ptr()
154                            .as_ref()
155                            .unwrap()
156                            .get_next()
157                            .as_ref()
158                            .unwrap()
159                    };
160                }
161                if current.borrow().get_next().is_none() {
162                    return Ok(*current.borrow().get_value() == value);
163                }
164            }
165        }
166        Err(Error::ValueNotFound)
167    }
168    /// Update a value in the list, returns true if the value is found and updated.
169    /// If the value is not found, it returns an error.
170    pub fn update(&mut self, old_value: T, new_value: T) -> Result<bool> {
171        match self.head.as_ref() {
172            None => return Err(Error::EmptyList),
173            Some(current) => {
174                let mut current = current;
175                if current.borrow().get_next().is_none() {
176                    return Ok(*current.borrow().get_value() == old_value);
177                }
178                while current.borrow().get_next().is_some() {
179                    if *current.borrow().get_value() == old_value {
180                        current.borrow_mut().set_value(new_value);
181                        return Ok(true);
182                    }
183                    current = unsafe {
184                        current
185                            .as_ptr()
186                            .as_ref()
187                            .unwrap()
188                            .get_next()
189                            .as_ref()
190                            .unwrap()
191                    };
192                }
193                if current.borrow().get_next().is_none() {
194                    current.borrow_mut().set_value(new_value);
195                    return Ok(true);
196                }
197            }
198        }
199        Err(Error::ValueNotFound)
200    }
201    /// Create a new instance of the double linked list from a vector.
202    pub fn from_vec(values: Vec<T>) -> Self {
203        let mut list = Self::new();
204        for value in values {
205            list.append(value);
206        }
207        list
208    }
209    /// Remove the last node from the list.
210    /// Returns the value of the removed node.
211    /// If the list is empty, it returns an error.
212    pub fn pop(&mut self) -> Result<Option<T>> {
213        if self.is_empty() {
214            return Err(Error::EmptyList);
215        }
216
217        match self.tail.as_ref() {
218            None => Err(Error::EmptyList),
219            Some(tail) => {
220                let tail = tail.clone();
221                let previous = tail
222                    .borrow_mut()
223                    .get_previous_mut()
224                    .clone()
225                    .unwrap()
226                    .upgrade()
227                    .unwrap();
228                previous.borrow_mut().set_next(None);
229                self.tail = Some(previous);
230                self.len -= 1;
231                return Ok(Some(tail.borrow().get_value().clone()));
232            }
233        }
234    }
235
236    pub fn print(&self) {
237        if self.is_empty() {
238            println!("{}", Error::EmptyList);
239        }
240
241        let mut index = 0;
242        while index < self.len {
243            let _ = self.get(index).map(|value| {
244                println!("{:?}", value.unwrap());
245                index += 1;
246            });
247        }
248    }
249    /// Check if the list is empty.
250    pub fn is_empty(&self) -> bool {
251        self.head.is_none()
252    }
253    /// Get an element from the list by index.
254    /// Returns an error if the list is empty or the index is out of bounds.
255    /// If the index is valid, it returns the value of the node.
256    pub fn get(&self, index: usize) -> Result<Option<T>> {
257        if self.is_empty() {
258            return Err(Error::EmptyList);
259        }
260        let mut current = &self.head;
261        let mut current_index = 0;
262
263        while current_index <= index {
264            let current_ref = current.as_ref().unwrap();
265            if current_index == index {
266                return Ok(Some(current_ref.borrow().get_value().clone()));
267            }
268            current = unsafe { current_ref.as_ptr().as_ref().unwrap().get_next() };
269            current_index += 1;
270        }
271
272        Err(Error::IndexOutOfBounds)
273    }
274}
275
276// region:    --- Tests
277
278#[cfg(test)]
279mod test {
280    use super::*;
281
282    #[test]
283    fn test_double_linked_list_ops() {
284        let mut list = Double::new();
285        list.append(1);
286        list.append(2);
287        assert!(!list.is_empty());
288        let value = list.pop().unwrap().unwrap();
289        assert_eq!(value, 2);
290        assert_eq!(list.len, 1);
291        let mut list2 = Double::from_vec(vec!["hello", "world", "rust"]);
292        assert_eq!(list2.get(1).unwrap().unwrap(), "world");
293        assert!(!list2.is_empty());
294        assert!(list2.search("rust").unwrap());
295        assert!(list2.update("world", "earth").unwrap());
296        assert_eq!(list2.get(1).unwrap().unwrap(), "earth");
297        assert!(list2.remove("earth").unwrap());
298        list2.print();
299    }
300
301    #[test]
302    fn test_double_linked_list_errors() {
303        let mut list: Double<i32> = Double::new();
304        assert!(list.is_empty());
305        assert!(list.search(6).is_err());
306        assert!(list.update(6, 7).is_err());
307        assert!(list.pop().is_err());
308        assert!(list.remove(6).is_err());
309    }
310}
311
312// endregion: --- Tests
rust_ds/linked_lists/double/mod.rs

rust_ds/linked_lists/double/
mod.rs
