LinkedListAlex/
lib.rs

1#![allow(dead_code)]
2#![allow(unused_variables)]
3
4use std::rc::Weak;
5use std::{fmt::Display, rc::Rc, cell::RefCell};
6use std::fmt::Debug;
7use std::cmp::PartialEq;
8
9// Node
10#[derive(Debug)]
11struct Node<T>
12  where T: Display + Debug + Copy + PartialEq
13{
14  pub prev: Option<Weak<RefCell<Node<T>>>>,
15  pub next: Option<Rc<RefCell<Node<T>>>>,
16  pub data: T
17}
18
19impl<T> Node<T>
20  where T: Display + Debug + Copy + PartialEq
21{
22  pub fn new(data: T) -> Rc<RefCell<Self>> {
23    Rc::new(RefCell::new(Node {
24      prev: None,
25      next: None,
26      data
27    }))
28  }
29}
30
31// Linked List
32#[derive(Debug)]
33pub struct LinkedList<T>
34  where T: Display + Debug + Copy + PartialEq
35{
36  head: Option<Rc<RefCell<Node<T>>>>,
37  tail: Option<Rc<RefCell<Node<T>>>>,
38  pub len: usize,
39  index: usize
40}
41
42impl<T> LinkedList<T>
43  where T: Display + Debug + Copy + PartialEq
44{
45
46  pub fn new() -> LinkedList<T> {
47    LinkedList {
48      head: None,
49      tail: None,
50      len: 0,
51      index: 0
52    }
53  }
54
55  pub fn push_front(&mut self, elem: T) {
56    self.len += 1;
57    let new_head = Node::new(elem);
58    match self.head.take() {
59        Some(old_head) => {
60            old_head.borrow_mut().prev = Some(Rc::downgrade(&new_head.clone()));
61            new_head.borrow_mut().next = Some(old_head.to_owned());
62            self.head = Some(new_head);
63        }
64        None => {
65            self.tail = Some(new_head.clone());
66            self.head = Some(new_head);
67        }
68    }
69  }
70
71  pub fn push_back(&mut self, elem: T) {
72    self.len += 1;
73    let new_tail = Node::new(elem);
74    match self.tail.take() {
75      Some(old_tail) => {
76        old_tail.borrow_mut().next = Some(new_tail.to_owned());
77        new_tail.borrow_mut().prev = Some(Rc::downgrade(&old_tail.clone()));
78        self.tail = Some(new_tail);
79      }
80      None => {
81        self.head = Some(new_tail.clone());
82        self.tail = Some(new_tail);
83      }
84    }
85  }
86
87  pub fn delete_by_index(&mut self, index: usize) {
88    let node: Option<Rc<RefCell<Node<T>>>>;
89    if index == 0 {
90      node = self.head.clone();
91    } else if index == self.len - 1 {
92      node = self.tail.clone();
93    } else if index <= self.len / 2 {
94      let index = index + 1;
95      node = self.get_by_index_from_head(self.head.clone(), index, 0);
96    } else {
97      let index = index + 1;
98      node = self.get_by_index_from_tail(self.tail.clone(), index, self.len + 1);
99    }
100    
101    let unwraped = node.unwrap();
102
103    let prev = unwraped.borrow().prev.clone();
104    let prev = if prev.is_none() {
105      unwraped.clone()
106    } else {
107      prev.unwrap().upgrade().unwrap()
108    };
109    let mut prev_mut = prev.borrow_mut();
110
111    let next = unwraped.borrow().next.clone();
112    let next = if next.is_none() {
113      unwraped.clone()
114    } else {
115      next.unwrap()
116    };
117    let mut next_mut = next.borrow_mut();
118    
119    prev_mut.next = Some(next.to_owned());
120    next_mut.prev = Some(Rc::downgrade(&prev.to_owned()));
121    
122    self.len -= 1;
123  }
124
125  pub fn get_by_index(&self, index: usize) -> Option<T> {
126    let node: Option<Rc<RefCell<Node<T>>>>;
127    if index == 0 {
128      node = self.head.clone();
129    } else if index == self.len-1 {
130      node = self.tail.clone();
131    } else if index <= self.len / 2 {
132      let index = index + 1;
133      node = self.get_by_index_from_head(self.head.clone(), index, 0);
134    } else {
135      let index = index + 1;
136      node = self.get_by_index_from_tail(self.tail.clone(), index, self.len + 1);
137    }
138
139    let result = match node {
140      Some(data) => Some(data.borrow().data.clone()),
141      None => None
142    };
143
144    result.to_owned()
145  }
146
147  pub fn get_by_value(&self, value: &T) -> Option<T> {
148    let node = self.get_by_value_from_head(self.head.clone(), value);
149    let result = match node {
150      Some(data) => Some(data.borrow().data.clone()),
151      None => None
152    };
153    result.to_owned()
154  }
155
156  pub fn delete_by_value(&mut self, value: &T) {
157    let node = self.get_by_value_from_head(self.head.clone(), value);
158    
159    if node.is_some() {
160      let unwraped = node.unwrap();
161
162      let prev = unwraped.borrow().prev.clone();
163      let prev = if prev.is_none() {
164        unwraped.clone()
165      } else {
166        prev.unwrap().upgrade().unwrap()
167      };
168      let mut prev_mut = prev.borrow_mut();
169
170      let next = unwraped.borrow().next.clone();
171      let next = if next.is_none() {
172        unwraped.clone()
173      } else {
174        next.unwrap()
175      };
176      let mut next_mut = next.borrow_mut();
177      
178      prev_mut.next = Some(next.to_owned());
179      next_mut.prev = Some(Rc::downgrade(&prev.to_owned()));
180      
181      self.len -= 1;
182    }
183    
184  }
185
186  /// Executes a closure to every node
187  pub fn excecute_to_all(&self, f: fn(&mut T)) {
188    self.recursive(self.head.to_owned(), f);
189  }
190
191  /// Private functions 
192  fn recursive(&self, node: Option<Rc<RefCell<Node<T>>>>, f: fn(&mut T)) -> bool {
193    let result = match node {
194      Some(node) => {
195        let mut bnode = node.borrow_mut();
196        let data = &mut bnode.data;
197        f(data);
198        self.recursive(bnode.next.to_owned(), f)
199      },
200      None => false
201    };
202    result
203  }
204
205  fn get_by_index_local(&self, index: usize) -> Option<T> {
206    let node: Option<Rc<RefCell<Node<T>>>>;
207
208    if index == 0 {
209      node = self.head.clone();
210    } else if index == self.len {
211      node = self.tail.clone();
212    } else if index <= self.len / 2 {
213      node = self.get_by_index_from_head(self.head.clone(), index, 0);
214    } else {
215      node = self.get_by_index_from_tail(self.tail.clone(), index, self.len + 1);
216    }
217
218    let result = match node {
219      Some(data) => Some(data.borrow().data.clone()),
220      None => None
221    };
222
223    result
224  }
225
226  fn get_by_index_from_head(&self, node: Option<Rc<RefCell<Node<T>>>>, index: usize, global_index: usize) -> Option<Rc<RefCell<Node<T>>>> {
227    let n = node.clone();
228    let global_index = global_index + 1;
229    if node.is_some() {
230      if index == global_index {
231        n
232      } else {
233        let next = n.unwrap().borrow().next.clone();
234        self.get_by_index_from_head(next, index, global_index)
235      }
236    } else {
237      None
238    }
239  }
240
241  fn get_by_index_from_tail(&self, node: Option<Rc<RefCell<Node<T>>>>, index: usize, global_index: usize) -> Option<Rc<RefCell<Node<T>>>> {
242    let n = node.clone();
243    let global_index = global_index - 1;
244    if node.is_some() {
245      if index == global_index {
246        n
247      } else {
248        let prev = n.unwrap().borrow().prev.clone();
249        if prev.is_some() {
250          let prev = prev.unwrap().upgrade();
251          self.get_by_index_from_tail(prev, index, global_index)
252        } else {
253          None
254        }
255      }
256    } else {
257      None
258    }
259  }
260
261  fn get_by_value_from_head(&self, node: Option<Rc<RefCell<Node<T>>>>, value: &T) -> Option<Rc<RefCell<Node<T>>>> {
262    let n = node.clone();
263    if node.is_some() {
264      let val = node.unwrap().borrow().data;
265      if val == *value {
266        n
267      } else {
268        let next = n.unwrap().borrow().next.clone();
269        self.get_by_value_from_head(next, value)
270      }
271    } else {
272      None
273    }
274  }
275
276  fn get_by_value_from_tail(&self, node: Option<Rc<RefCell<Node<T>>>>, value: &T) -> Option<Rc<RefCell<Node<T>>>> {
277    let n = node.clone();
278    if node.is_some() {
279      let val = node.unwrap().borrow().data;
280      if val == *value {
281        n
282      } else {
283        let prev = n.unwrap().borrow().prev.clone();
284        if prev.is_some() {
285          let prev = prev.unwrap().upgrade();
286          self.get_by_value_from_tail(prev, value)
287        } else {
288          None
289        }
290      }
291    } else {
292      None
293    }
294  }
295}
296
297// Iterator
298impl<T> Iterator for LinkedList<T>
299  where T: Display + Debug + Copy + PartialEq
300{
301  type Item = T;
302
303  fn next(&mut self) -> Option<Self::Item> {
304    if self.index >= self.len {
305      return None
306    }
307    self.index += 1;
308    self.get_by_index_local(self.index)
309  }
310
311}
312
313#[cfg(test)]
314mod tests {
315  use crate::LinkedList;
316
317  #[test]
318  fn push_back_works() {
319    let mut list = LinkedList::new();
320    list.push_back(0);
321    list.push_back(1);
322    list.push_back(2);
323    list.push_back(3);
324    list.push_back(4);
325    list.push_back(5);
326    list.push_back(6);
327    list.push_back(7);
328
329    assert_eq!(list.len, 8);
330  }
331
332  #[test]
333  fn push_front_works() {
334    let mut list = LinkedList::new();
335    list.push_front(0);
336    list.push_front(1);
337    list.push_front(2);
338    list.push_front(3);
339    list.push_front(4);
340    list.push_front(5);
341    list.push_front(6);
342    list.push_front(7);
343
344    assert_eq!(list.len, 8);
345  }
346
347  #[test]
348  fn delete_by_index_works() {
349    let mut list = LinkedList::new();
350    list.push_back(0);
351    list.push_back(1);
352    list.push_back(2);
353    list.push_back(3);
354    list.push_back(4);
355    list.push_back(5);
356    list.push_back(6);
357    list.push_back(7);
358
359    list.delete_by_index(3);
360    assert_eq!(list.len, 7);
361
362    let data = list.get_by_index(3);
363    assert_eq!(data.is_some(), true);
364    let unwraped = data.unwrap();
365    assert_eq!(unwraped, 4);
366  }
367
368  #[test]
369  fn get_by_index_works() {
370    let mut list = LinkedList::new();
371    list.push_back(0);
372    list.push_back(1);
373    list.push_back(2);
374    list.push_back(3);
375    list.push_back(4);
376    list.push_back(5);
377    list.push_back(6);
378    list.push_back(7);
379
380    let data = list.get_by_index(4);
381    assert_eq!(data.is_some(), true);
382    let unwraped = data.unwrap();
383    assert_eq!(unwraped, 4);
384
385    let data = list.get_by_index(9);
386    assert_eq!(data.is_none(), true);
387  }
388
389  #[test]
390  fn iterator_works() {
391    let mut list = LinkedList::new();
392    list.push_back(0);
393    list.push_back(1);
394    list.push_back(2);
395    list.push_back(3);
396    list.push_back(4);
397    list.push_back(5);
398    list.push_back(6);
399    list.push_back(7);
400
401    let mut index = 0;
402    for item in list {
403      assert_eq!(item, index);
404      index += 1;
405    }
406  }
407
408  #[test]
409  fn recursive_works() {
410    let mut list = LinkedList::new();
411    list.push_back(0);
412    list.push_back(1);
413    list.push_back(2);
414    list.push_back(3);
415    list.push_back(4);
416    list.push_back(5);
417    list.push_back(6);
418    list.push_back(7);
419
420    list.excecute_to_all(|data| {
421      *data = *data * 2;
422    });
423
424    let item0 = list.get_by_index(0).unwrap();
425    let item1 = list.get_by_index(1).unwrap();
426    let item2 = list.get_by_index(2).unwrap();
427    let item3 = list.get_by_index(3).unwrap();
428    let item4 = list.get_by_index(4).unwrap();
429    let item5 = list.get_by_index(5).unwrap();
430    let item6 = list.get_by_index(6).unwrap();
431    let item7 = list.get_by_index(7).unwrap();
432
433    assert_eq!(item0, 0);
434    assert_eq!(item1, 2);
435    assert_eq!(item2, 4);
436    assert_eq!(item3, 6);
437    assert_eq!(item4, 8);
438    assert_eq!(item5, 10);
439    assert_eq!(item6, 12);
440    assert_eq!(item7, 14);
441
442  }
443
444  #[test]
445  fn get_by_value_works() {
446    let mut list = LinkedList::new();
447    list.push_back(0);
448    list.push_back(1);
449    list.push_back(2);
450    list.push_back(3);
451    list.push_back(4);
452    list.push_back(5);
453    list.push_back(6);
454    list.push_back(7);
455
456    list.excecute_to_all(|data| {
457      *data = *data * 2;
458    });
459
460    let val = list.get_by_value(&10);
461
462    assert!(val.is_some());
463
464    assert_eq!(val.unwrap(), 10);
465  }
466
467  #[test]
468  fn delete_by_value_works() {
469    let mut list = LinkedList::new();
470    list.push_back(0);
471    list.push_back(1);
472    list.push_back(2);
473    list.push_back(3);
474    list.push_back(4);
475    list.push_back(5);
476    list.push_back(6);
477    list.push_back(7);
478
479    list.excecute_to_all(|data| {
480      *data = *data * 2;
481    });
482
483    list.delete_by_value(&10);
484
485    assert_eq!(list.len, 7);
486  }
487
488}
LinkedListAlex/lib.rs

LinkedListAlex/
lib.rs
