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