1use std::cell::RefCell;
2use std::rc::Rc;
3
4pub trait List<T: PartialOrd + Clone> {
5 fn new() -> Self;
6 fn push_front(&mut self, data: T);
7 fn push_back(&mut self, data: T);
8 fn pop_front(&mut self) -> Result<T, &'static str>;
9 fn pop_back(&mut self) -> Result<T, &'static str>;
10 fn is_empty(&self) -> bool;
11 fn is_sorted(&self) -> bool;
12 fn get(&mut self, index: usize) -> Option<T>;
13 fn len(&self) -> usize;
14}
15
16
17#[derive(Debug)]
18struct Node<T> {
19 value: T,
20 next: Option<Box<Node<T>>>,
21}
22
23impl<T> Node<T> {
24 fn create(data: T) -> Self {
25 Self {
26 value: data,
27 next: None,
28 }
29 }
30
31 fn create_and_link(data: T, next: Option<Box<Self>>) -> Self {
32 Self {
33 value: data,
34 next,
35 }
36 }
37}
38
39#[derive(Debug)]
40pub struct SinglyLinkedList<T> {
41 head: Option<Box<Node<T>>>,
42 size: usize,
43}
44
45impl<T: PartialOrd + Copy> List<T> for SinglyLinkedList<T> {
46 fn new() -> Self {
47 Self {
48 head: None,
49 size: 0,
50 }
51 }
52
53 fn push_front(&mut self, data: T) {
54 let old_head = self.head.take();
55 let new_head = Box::new(Node::create_and_link(data, old_head));
56
57 self.head = Some(new_head);
58 self.size += 1;
59 }
60
61 fn push_back(&mut self, data: T) {
62 if self.is_empty() {
63 self.head = Some(Box::new(Node::create(data)));
64 } else {
65 let mut current: &mut Option<Box<Node<T>>> = &mut self.head;
66 while current.is_some() && current.as_ref().unwrap().next.is_some() {
67 current = &mut current.as_mut().unwrap().next;
68 }
69 current.as_mut().unwrap().next = Some(Box::new(Node::create(data)));
70 }
71
72 self.size += 1;
73 }
74
75 fn pop_front(&mut self) -> Result<T, &'static str> {
76 if self.is_empty() {
77 return Err("Can't pop an element from an empty ds-list");
78 }
79
80 let old_head = self.head.take().unwrap();
81
82 self.head = old_head.next;
83 self.size -= 1;
84
85 Ok(old_head.value)
86 }
87
88 fn pop_back(&mut self) -> Result<T, &'static str> {
89 if self.is_empty() {
90 return Err("Can't pop an element from an empty ds-list");
91 }
92
93 if self.len() == 1 {
94 let removed_value = self.head.take().unwrap().value;
95 self.head = None;
96 self.size = 0;
97 return Ok(removed_value);
98 }
99
100 let mut current: &mut Option<Box<Node<T>>> = &mut self.head;
101
102 while current.as_ref().unwrap().next.is_some() && current.as_ref().unwrap().next.as_ref().unwrap().next.is_some() {
103 current = &mut current.as_mut().unwrap().next;
104 }
105
106 let removed_value = current.as_mut().unwrap().next.take().unwrap().value;
107 current.as_mut().unwrap().next = None;
108 self.size -= 1;
109 Ok(removed_value)
110 }
111
112 fn is_empty(&self) -> bool {
113 self.head.is_none()
114 }
115
116 fn is_sorted(&self) -> bool {
117 let mut current: Option<&Box<Node<T>>> = self.head.as_ref();
118
119 while current.is_some() && current.as_ref().unwrap().next.is_some() {
120 if current.unwrap().value > current.as_ref().unwrap().next.as_ref().unwrap().value {
121 return false;
122 }
123 current = current.unwrap().next.as_ref();
124 }
125
126 true
127 }
128
129 fn get(&mut self, index: usize) -> Option<T> {
130 if index >= self.len() {
131 return None;
132 }
133
134 let mut current: &mut Option<Box<Node<T>>> = &mut self.head;
135
136 for _ in 0..index {
137 current = &mut current.as_mut().unwrap().next;
138 }
139
140 Some(current.as_ref().unwrap().value)
141 }
142
143 fn len(&self) -> usize {
144 self.size
145 }
146}
147
148struct DoublyLinkedNode<T> {
149 value: T,
150 next: Option<Rc<RefCell<Box<DoublyLinkedNode<T>>>>>,
151 prev: Option<Rc<RefCell<Box<DoublyLinkedNode<T>>>>>,
152}
153
154
155impl<T> DoublyLinkedNode<T>
156 where T: Default {
157 fn create(data: T) -> Self {
158 Self {
159 value: data,
160 next: None,
161 prev: None,
162 }
163 }
164
165 fn create_sentinel() -> Rc<RefCell<Box<Self>>> {
166 let sentinel = Rc::new(RefCell::new(Box::new(Self {
167 value: Default::default(),
168 next: None,
169 prev: None,
170 })));
171
172 sentinel.borrow_mut().next = Some(Rc::clone(&sentinel));
173 sentinel.borrow_mut().prev = Some(Rc::clone(&sentinel));
174
175 sentinel
176 }
177}
178
179pub struct DoublyLinkedList<T> {
180 sentinel: Rc<RefCell<Box<DoublyLinkedNode<T>>>>,
181 size: usize,
182}
183
184impl<T> List<T> for DoublyLinkedList<T>
185 where T: Default + Clone + PartialOrd {
186 fn new() -> Self {
187 Self {
188 sentinel: DoublyLinkedNode::create_sentinel(),
189 size: 0,
190 }
191 }
192
193 fn push_front(&mut self, data: T) {
194 let new_node = Rc::new(RefCell::new(Box::new(DoublyLinkedNode::create(data))));
195 let mut sentinel = self.sentinel.borrow_mut();
196
197 new_node.borrow_mut().next = Some(Rc::clone(&sentinel.next.as_ref().unwrap()));
198 match self.len() {
199 0 => sentinel.prev = Some(Rc::clone(&new_node)),
200 _ => sentinel.next.as_ref().unwrap().borrow_mut().prev = Some(Rc::clone(&new_node)),
201 }
202 sentinel.next = Some(Rc::clone(&new_node));
203 new_node.borrow_mut().prev = Some(Rc::clone(&self.sentinel));
204
205 self.size += 1
206 }
207
208 fn push_back(&mut self, data: T) {
209 let new_node = Rc::new(RefCell::new(Box::new(DoublyLinkedNode::create(data))));
210 let mut sentinel = self.sentinel.borrow_mut();
211
212 new_node.borrow_mut().prev = Some(Rc::clone(&sentinel.prev.as_ref().unwrap()));
213 match self.len() {
214 0 => sentinel.next = Some(Rc::clone(&new_node)),
215 _ => sentinel.prev.as_ref().unwrap().borrow_mut().next = Some(Rc::clone(&new_node)),
216 }
217 sentinel.prev = Some(Rc::clone(&new_node));
218 new_node.borrow_mut().next = Some(Rc::clone(&self.sentinel));
219 self.size += 1
220 }
221
222 fn pop_front(&mut self) -> Result<T, &'static str> {
223 todo!()
224 }
225
226 fn pop_back(&mut self) -> Result<T, &'static str> {
227 todo!()
228 }
229
230 fn is_empty(&self) -> bool {
231 self.size == 0
232 }
233
234 fn is_sorted(&self) -> bool {
235 todo!()
236 }
237
238 fn get(&mut self, index: usize) -> Option<T> {
239 fn get_r<T: Clone>(node: &Rc<RefCell<Box<DoublyLinkedNode<T>>>>, current_index: usize, index: usize) -> Option<T> {
240 if current_index == index {
241 return Some(node.as_ref().borrow().value.clone());
242 }
243 get_r(node.borrow().next.as_ref().unwrap(), current_index + 1, index)
244 }
245
246 if index >= self.len() || self.len() == 0 {
247 return None;
248 }
249 let sentinel_ref = &self.sentinel;
250 get_r(sentinel_ref, 0, index + 1)
251 }
252
253 fn len(&self) -> usize {
254 self.size
255 }
256}