cs431_homework/linked_list.rs
1use std::cmp::Ordering;
2use std::marker::PhantomData;
3use std::{fmt, mem, ptr};
4
5/// A doubly-linked list with owned nodes.
6///
7/// The `LinkedList` allows pushing and popping elements at either end
8/// in constant time.
9pub struct LinkedList<T> {
10 head: *mut Node<T>,
11 tail: *mut Node<T>,
12 len: usize,
13 marker: PhantomData<Box<Node<T>>>,
14}
15
16struct Node<T> {
17 next: *mut Node<T>,
18 prev: *mut Node<T>,
19 element: T,
20}
21
22/// An iterator over the elements of a `LinkedList`.
23///
24/// This `struct` is created by the [`iter`] method on [`LinkedList`]. See its
25/// documentation for more.
26///
27/// [`iter`]: struct.LinkedList.html#method.iter
28/// [`LinkedList`]: struct.LinkedList.html
29pub struct Iter<'a, T> {
30 head: *mut Node<T>,
31 tail: *mut Node<T>,
32 len: usize,
33 marker: PhantomData<&'a Node<T>>,
34}
35
36impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
37 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
38 f.debug_tuple("Iter").field(&self.len).finish()
39 }
40}
41
42impl<T> Clone for Iter<'_, T> {
43 fn clone(&self) -> Self {
44 Iter { ..*self }
45 }
46}
47
48/// A mutable iterator over the elements of a `LinkedList`.
49///
50/// This `struct` is created by the [`iter_mut`] method on [`LinkedList`]. See its
51/// documentation for more.
52///
53/// [`iter_mut`]: struct.LinkedList.html#method.iter_mut
54/// [`LinkedList`]: struct.LinkedList.html
55pub struct IterMut<'a, T> {
56 // We do *not* exclusively own the entire list here, references to node's `element`
57 // have been handed out by the iterator! So be careful when using this; the methods
58 // called must be aware that there can be aliasing pointers to `element`.
59 list: &'a mut LinkedList<T>,
60 head: *mut Node<T>,
61 tail: *mut Node<T>,
62 len: usize,
63}
64
65impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> {
66 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
67 f.debug_tuple("IterMut")
68 .field(&self.list)
69 .field(&self.len)
70 .finish()
71 }
72}
73
74/// An owning iterator over the elements of a `LinkedList`.
75///
76/// This `struct` is created by the [`into_iter`] method on [`LinkedList`]
77/// (provided by the `IntoIterator` trait). See its documentation for more.
78///
79/// [`into_iter`]: struct.LinkedList.html#method.into_iter
80/// [`LinkedList`]: struct.LinkedList.html
81#[derive(Clone)]
82pub struct IntoIter<T> {
83 list: LinkedList<T>,
84}
85
86impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
87 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
88 f.debug_tuple("IntoIter").field(&self.list).finish()
89 }
90}
91
92impl<T> Node<T> {
93 fn new(element: T) -> Self {
94 Node {
95 next: ptr::null_mut(),
96 prev: ptr::null_mut(),
97 element,
98 }
99 }
100
101 fn into_element(self) -> T {
102 self.element
103 }
104}
105
106impl<T> LinkedList<T> {
107 /// Adds the given node to the front of the list.
108 #[inline]
109 fn push_front_node(&mut self, mut node: Node<T>) {
110 node.next = self.head;
111 node.prev = ptr::null_mut();
112 let node = Box::into_raw(Box::new(node));
113
114 if self.head.is_null() {
115 self.tail = node;
116 } else {
117 unsafe { (*self.head).prev = node };
118 }
119
120 self.head = node;
121 self.len += 1;
122 }
123
124 /// Removes and returns the node at the front of the list.
125 #[inline]
126 fn pop_front_node(&mut self) -> Option<Node<T>> {
127 if self.head.is_null() {
128 return None;
129 }
130
131 let node = unsafe { Box::from_raw(self.head) };
132 self.head = node.next;
133
134 if self.head.is_null() {
135 self.tail = ptr::null_mut();
136 } else {
137 unsafe { (*self.head).prev = ptr::null_mut() };
138 }
139
140 self.len -= 1;
141 Some(*node)
142 }
143
144 /// Adds the given node to the back of the list.
145 #[inline]
146 fn push_back_node(&mut self, mut node: Node<T>) {
147 todo!()
148 }
149
150 /// Removes and returns the node at the back of the list.
151 #[inline]
152 fn pop_back_node(&mut self) -> Option<Node<T>> {
153 todo!()
154 }
155}
156
157impl<T> Default for LinkedList<T> {
158 /// Creates an empty `LinkedList<T>`.
159 #[inline]
160 fn default() -> Self {
161 Self::new()
162 }
163}
164
165impl<T> LinkedList<T> {
166 /// Creates an empty `LinkedList`.
167 ///
168 /// # Examples
169 ///
170 /// ```
171 /// use cs431_homework::LinkedList;
172 ///
173 /// let list: LinkedList<u32> = LinkedList::new();
174 /// ```
175 #[inline]
176 pub const fn new() -> Self {
177 LinkedList {
178 head: ptr::null_mut(),
179 tail: ptr::null_mut(),
180 len: 0,
181 marker: PhantomData,
182 }
183 }
184
185 /// Moves all elements from `other` to the end of the list.
186 ///
187 /// This reuses all the nodes from `other` and moves them into `self`. After
188 /// this operation, `other` becomes empty.
189 ///
190 /// This operation should compute in `O(1)` time and `O(1)` memory.
191 ///
192 /// # Examples
193 ///
194 /// ```
195 /// use cs431_homework::LinkedList;
196 ///
197 /// let mut list1 = LinkedList::new();
198 /// list1.push_back('a');
199 ///
200 /// let mut list2 = LinkedList::new();
201 /// list2.push_back('b');
202 /// list2.push_back('c');
203 ///
204 /// list1.append(&mut list2);
205 ///
206 /// let mut iter = list1.iter();
207 /// assert_eq!(iter.next(), Some(&'a'));
208 /// assert_eq!(iter.next(), Some(&'b'));
209 /// assert_eq!(iter.next(), Some(&'c'));
210 /// assert!(iter.next().is_none());
211 ///
212 /// assert!(list2.is_empty());
213 /// ```
214 pub fn append(&mut self, other: &mut Self) {
215 if self.tail.is_null() {
216 mem::swap(self, other);
217 } else {
218 let other_head = mem::replace(&mut other.head, ptr::null_mut());
219 if !other_head.is_null() {
220 unsafe {
221 (*self.tail).next = other_head;
222 (*other_head).prev = self.tail;
223 }
224 self.tail = mem::replace(&mut other.tail, ptr::null_mut());
225 self.len += mem::replace(&mut other.len, 0);
226 }
227 }
228 }
229
230 /// Moves all elements from `other` to the beginning of the list.
231 ///
232 /// This reuses all the nodes from `other` and moves them into `self`. After
233 /// this operation, `other` becomes empty.
234 ///
235 /// This operation should compute in `O(1)` time and `O(1)` memory.
236 ///
237 /// # Examples
238 ///
239 /// ```
240 /// use cs431_homework::LinkedList;
241 ///
242 /// let mut list1 = LinkedList::new();
243 /// list1.push_back('a');
244 /// list1.push_back('b');
245 ///
246 /// let mut list2 = LinkedList::new();
247 /// list2.push_back('c');
248 ///
249 /// list2.prepend(&mut list1);
250 ///
251 /// let mut iter = list2.iter();
252 /// assert_eq!(iter.next(), Some(&'a'));
253 /// assert_eq!(iter.next(), Some(&'b'));
254 /// assert_eq!(iter.next(), Some(&'c'));
255 /// assert!(iter.next().is_none());
256 ///
257 /// assert!(list1.is_empty());
258 /// ```
259 pub fn prepend(&mut self, other: &mut Self) {
260 todo!()
261 }
262
263 /// Provides a forward iterator.
264 ///
265 /// # Examples
266 ///
267 /// ```
268 /// use cs431_homework::LinkedList;
269 ///
270 /// let mut list: LinkedList<u32> = LinkedList::new();
271 ///
272 /// list.push_back(0);
273 /// list.push_back(1);
274 /// list.push_back(2);
275 ///
276 /// let mut iter = list.iter();
277 /// assert_eq!(iter.next(), Some(&0));
278 /// assert_eq!(iter.next(), Some(&1));
279 /// assert_eq!(iter.next(), Some(&2));
280 /// assert_eq!(iter.next(), None);
281 /// ```
282 #[inline]
283 pub fn iter(&self) -> Iter<'_, T> {
284 Iter {
285 head: self.head,
286 tail: self.tail,
287 len: self.len,
288 marker: PhantomData,
289 }
290 }
291
292 /// Provides a forward iterator with mutable references.
293 ///
294 /// # Examples
295 ///
296 /// ```
297 /// use cs431_homework::LinkedList;
298 ///
299 /// let mut list: LinkedList<u32> = LinkedList::new();
300 ///
301 /// list.push_back(0);
302 /// list.push_back(1);
303 /// list.push_back(2);
304 ///
305 /// for element in list.iter_mut() {
306 /// *element += 10;
307 /// }
308 ///
309 /// let mut iter = list.iter();
310 /// assert_eq!(iter.next(), Some(&10));
311 /// assert_eq!(iter.next(), Some(&11));
312 /// assert_eq!(iter.next(), Some(&12));
313 /// assert_eq!(iter.next(), None);
314 /// ```
315 #[inline]
316 pub fn iter_mut(&mut self) -> IterMut<'_, T> {
317 IterMut {
318 head: self.head,
319 tail: self.tail,
320 len: self.len,
321 list: self,
322 }
323 }
324
325 /// Returns `true` if the `LinkedList` is empty.
326 ///
327 /// This operation should compute in `O(1)` time.
328 ///
329 /// # Examples
330 ///
331 /// ```
332 /// use cs431_homework::LinkedList;
333 ///
334 /// let mut dl = LinkedList::new();
335 /// assert!(dl.is_empty());
336 ///
337 /// dl.push_front("foo");
338 /// assert!(!dl.is_empty());
339 /// ```
340 #[inline]
341 pub fn is_empty(&self) -> bool {
342 self.head.is_null()
343 }
344
345 /// Returns the length of the `LinkedList`.
346 ///
347 /// This operation should compute in `O(1)` time.
348 ///
349 /// # Examples
350 ///
351 /// ```
352 /// use cs431_homework::LinkedList;
353 ///
354 /// let mut dl = LinkedList::new();
355 ///
356 /// dl.push_front(2);
357 /// assert_eq!(dl.len(), 1);
358 ///
359 /// dl.push_front(1);
360 /// assert_eq!(dl.len(), 2);
361 ///
362 /// dl.push_back(3);
363 /// assert_eq!(dl.len(), 3);
364 /// ```
365 #[inline]
366 pub fn len(&self) -> usize {
367 self.len
368 }
369
370 /// Removes all elements from the `LinkedList`.
371 ///
372 /// This operation should compute in `O(n)` time.
373 ///
374 /// # Examples
375 ///
376 /// ```
377 /// use cs431_homework::LinkedList;
378 ///
379 /// let mut dl = LinkedList::new();
380 ///
381 /// dl.push_front(2);
382 /// dl.push_front(1);
383 /// assert_eq!(dl.len(), 2);
384 /// assert_eq!(dl.front(), Some(&1));
385 ///
386 /// dl.clear();
387 /// assert_eq!(dl.len(), 0);
388 /// assert_eq!(dl.front(), None);
389 /// ```
390 #[inline]
391 pub fn clear(&mut self) {
392 *self = Self::new();
393 }
394
395 /// Returns `true` if the `LinkedList` contains an element equal to the
396 /// given value.
397 ///
398 /// # Examples
399 ///
400 /// ```
401 /// use cs431_homework::LinkedList;
402 ///
403 /// let mut list: LinkedList<u32> = LinkedList::new();
404 ///
405 /// list.push_back(0);
406 /// list.push_back(1);
407 /// list.push_back(2);
408 ///
409 /// assert_eq!(list.contains(&0), true);
410 /// assert_eq!(list.contains(&10), false);
411 /// ```
412 pub fn contains(&self, x: &T) -> bool
413 where
414 T: PartialEq<T>,
415 {
416 self.iter().any(|e| e == x)
417 }
418
419 /// Provides a reference to the front element, or `None` if the list is
420 /// empty.
421 ///
422 /// # Examples
423 ///
424 /// ```
425 /// use cs431_homework::LinkedList;
426 ///
427 /// let mut dl = LinkedList::new();
428 /// assert_eq!(dl.front(), None);
429 ///
430 /// dl.push_front(1);
431 /// assert_eq!(dl.front(), Some(&1));
432 /// ```
433 #[inline]
434 pub fn front(&self) -> Option<&T> {
435 unsafe { self.head.as_ref() }.map(|node| &node.element)
436 }
437
438 /// Provides a mutable reference to the front element, or `None` if the list
439 /// is empty.
440 ///
441 /// # Examples
442 ///
443 /// ```
444 /// use cs431_homework::LinkedList;
445 ///
446 /// let mut dl = LinkedList::new();
447 /// assert_eq!(dl.front(), None);
448 ///
449 /// dl.push_front(1);
450 /// assert_eq!(dl.front(), Some(&1));
451 ///
452 /// match dl.front_mut() {
453 /// None => {},
454 /// Some(x) => *x = 5,
455 /// }
456 /// assert_eq!(dl.front(), Some(&5));
457 /// ```
458 #[inline]
459 pub fn front_mut(&mut self) -> Option<&mut T> {
460 unsafe { self.head.as_mut() }.map(|node| &mut node.element)
461 }
462
463 /// Provides a reference to the back element, or `None` if the list is
464 /// empty.
465 ///
466 /// # Examples
467 ///
468 /// ```
469 /// use cs431_homework::LinkedList;
470 ///
471 /// let mut dl = LinkedList::new();
472 /// assert_eq!(dl.back(), None);
473 ///
474 /// dl.push_back(1);
475 /// assert_eq!(dl.back(), Some(&1));
476 /// ```
477 #[inline]
478 pub fn back(&self) -> Option<&T> {
479 todo!()
480 }
481
482 /// Provides a mutable reference to the back element, or `None` if the list
483 /// is empty.
484 ///
485 /// # Examples
486 ///
487 /// ```
488 /// use cs431_homework::LinkedList;
489 ///
490 /// let mut dl = LinkedList::new();
491 /// assert_eq!(dl.back(), None);
492 ///
493 /// dl.push_back(1);
494 /// assert_eq!(dl.back(), Some(&1));
495 ///
496 /// match dl.back_mut() {
497 /// None => {},
498 /// Some(x) => *x = 5,
499 /// }
500 /// assert_eq!(dl.back(), Some(&5));
501 /// ```
502 #[inline]
503 pub fn back_mut(&mut self) -> Option<&mut T> {
504 unsafe { self.tail.as_mut() }.map(|node| &mut node.element)
505 }
506
507 /// Adds an element first in the list.
508 ///
509 /// This operation should compute in `O(1)` time.
510 ///
511 /// # Examples
512 ///
513 /// ```
514 /// use cs431_homework::LinkedList;
515 ///
516 /// let mut dl = LinkedList::new();
517 ///
518 /// dl.push_front(2);
519 /// assert_eq!(dl.front().unwrap(), &2);
520 ///
521 /// dl.push_front(1);
522 /// assert_eq!(dl.front().unwrap(), &1);
523 /// ```
524 pub fn push_front(&mut self, elt: T) {
525 todo!()
526 }
527
528 /// Removes the first element and returns it, or `None` if the list is
529 /// empty.
530 ///
531 /// This operation should compute in `O(1)` time.
532 ///
533 /// # Examples
534 ///
535 /// ```
536 /// use cs431_homework::LinkedList;
537 ///
538 /// let mut d = LinkedList::new();
539 /// assert_eq!(d.pop_front(), None);
540 ///
541 /// d.push_front(1);
542 /// d.push_front(3);
543 /// assert_eq!(d.pop_front(), Some(3));
544 /// assert_eq!(d.pop_front(), Some(1));
545 /// assert_eq!(d.pop_front(), None);
546 /// ```
547 pub fn pop_front(&mut self) -> Option<T> {
548 self.pop_front_node().map(Node::into_element)
549 }
550
551 /// Appends an element to the back of a list.
552 ///
553 /// This operation should compute in `O(1)` time.
554 ///
555 /// # Examples
556 ///
557 /// ```
558 /// use cs431_homework::LinkedList;
559 ///
560 /// let mut d = LinkedList::new();
561 /// d.push_back(1);
562 /// d.push_back(3);
563 /// assert_eq!(3, *d.back().unwrap());
564 /// ```
565 pub fn push_back(&mut self, elt: T) {
566 self.push_back_node(Node::new(elt));
567 }
568
569 /// Removes the last element from a list and returns it, or `None` if
570 /// it is empty.
571 ///
572 /// This operation should compute in `O(1)` time.
573 ///
574 /// # Examples
575 ///
576 /// ```
577 /// use cs431_homework::LinkedList;
578 ///
579 /// let mut d = LinkedList::new();
580 /// assert_eq!(d.pop_back(), None);
581 /// d.push_back(1);
582 /// d.push_back(3);
583 /// assert_eq!(d.pop_back(), Some(3));
584 /// ```
585 pub fn pop_back(&mut self) -> Option<T> {
586 self.pop_back_node().map(Node::into_element)
587 }
588}
589
590impl<T> Drop for LinkedList<T> {
591 fn drop(&mut self) {
592 while self.pop_front_node().is_some() {}
593 }
594}
595
596impl<'a, T> Iterator for Iter<'a, T> {
597 type Item = &'a T;
598
599 #[inline]
600 fn next(&mut self) -> Option<&'a T> {
601 if self.len == 0 {
602 None
603 } else {
604 unsafe { self.head.as_ref() }.map(|node| {
605 self.len -= 1;
606 self.head = node.next;
607 &node.element
608 })
609 }
610 }
611}
612
613impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
614 #[inline]
615 fn next_back(&mut self) -> Option<&'a T> {
616 if self.len == 0 {
617 None
618 } else {
619 unsafe { self.tail.as_ref() }.map(|node| {
620 self.len -= 1;
621 self.tail = node.prev;
622 &node.element
623 })
624 }
625 }
626}
627
628impl<'a, T> Iterator for IterMut<'a, T> {
629 type Item = &'a mut T;
630
631 #[inline]
632 fn next(&mut self) -> Option<&'a mut T> {
633 todo!()
634 }
635}
636
637impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
638 #[inline]
639 fn next_back(&mut self) -> Option<&'a mut T> {
640 todo!()
641 }
642}
643
644impl<T> IterMut<'_, T> {
645 /// Inserts the given element just after the element most recently returned by `.next()`.
646 /// The inserted element does not appear in the iteration.
647 ///
648 /// # Examples
649 ///
650 /// ```
651 /// use cs431_homework::LinkedList;
652 ///
653 /// let mut list: LinkedList<_> = vec![1, 4].into_iter().collect();
654 ///
655 /// {
656 /// let mut it = list.iter_mut();
657 /// assert_eq!(it.next().unwrap(), &1);
658 /// // insert `2` and `3` after `1`
659 /// it.insert_next(2);
660 /// it.insert_next(3);
661 /// }
662 /// {
663 /// let vec: Vec<_> = list.into_iter().collect();
664 /// assert_eq!(vec, [1, 2, 3, 4]);
665 /// }
666 /// ```
667 #[inline]
668 pub fn insert_next(&mut self, element: T) {
669 todo!()
670 }
671
672 /// Provides a reference to the next element, without changing the iterator.
673 ///
674 /// # Examples
675 ///
676 /// ```
677 /// use cs431_homework::LinkedList;
678 ///
679 /// let mut list: LinkedList<_> = vec![1, 2, 3].into_iter().collect();
680 ///
681 /// let mut it = list.iter_mut();
682 /// assert_eq!(it.next().unwrap(), &1);
683 /// assert_eq!(it.peek_next().unwrap(), &2);
684 /// // We just peeked at 2, so it was not consumed from the iterator.
685 /// assert_eq!(it.next().unwrap(), &2);
686 /// ```
687 #[inline]
688 pub fn peek_next(&mut self) -> Option<&mut T> {
689 todo!()
690 }
691}
692
693impl<T> Iterator for IntoIter<T> {
694 type Item = T;
695
696 #[inline]
697 fn next(&mut self) -> Option<T> {
698 self.list.pop_front()
699 }
700}
701
702impl<T> DoubleEndedIterator for IntoIter<T> {
703 #[inline]
704 fn next_back(&mut self) -> Option<T> {
705 self.list.pop_back()
706 }
707}
708
709impl<T> FromIterator<T> for LinkedList<T> {
710 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
711 let mut list = Self::new();
712 iter.into_iter().for_each(|elt| list.push_back(elt));
713 list
714 }
715}
716
717impl<T> IntoIterator for LinkedList<T> {
718 type Item = T;
719 type IntoIter = IntoIter<T>;
720
721 /// Consumes the list into an iterator yielding elements by value.
722 #[inline]
723 fn into_iter(self) -> IntoIter<T> {
724 IntoIter { list: self }
725 }
726}
727
728impl<'a, T> IntoIterator for &'a LinkedList<T> {
729 type Item = &'a T;
730 type IntoIter = Iter<'a, T>;
731
732 fn into_iter(self) -> Iter<'a, T> {
733 self.iter()
734 }
735}
736
737impl<'a, T> IntoIterator for &'a mut LinkedList<T> {
738 type Item = &'a mut T;
739 type IntoIter = IterMut<'a, T>;
740
741 fn into_iter(self) -> IterMut<'a, T> {
742 self.iter_mut()
743 }
744}
745
746impl<T: PartialEq> PartialEq for LinkedList<T> {
747 fn eq(&self, other: &Self) -> bool {
748 self.len() == other.len() && self.iter().eq(other)
749 }
750}
751
752impl<T: Eq> Eq for LinkedList<T> {}
753
754impl<T: PartialOrd> PartialOrd for LinkedList<T> {
755 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
756 self.iter().partial_cmp(other)
757 }
758}
759
760impl<T: Ord> Ord for LinkedList<T> {
761 #[inline]
762 fn cmp(&self, other: &Self) -> Ordering {
763 self.iter().cmp(other)
764 }
765}
766
767impl<T: Clone> Clone for LinkedList<T> {
768 fn clone(&self) -> Self {
769 self.iter().cloned().collect()
770 }
771}
772
773impl<T: fmt::Debug> fmt::Debug for LinkedList<T> {
774 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
775 f.debug_list().entries(self).finish()
776 }
777}
778
779unsafe impl<T: Send> Send for LinkedList<T> {}
780
781unsafe impl<T: Sync> Sync for LinkedList<T> {}
782
783unsafe impl<T: Sync> Send for Iter<'_, T> {}
784
785unsafe impl<T: Sync> Sync for Iter<'_, T> {}
786
787unsafe impl<T: Send> Send for IterMut<'_, T> {}
788
789unsafe impl<T: Sync> Sync for IterMut<'_, T> {}