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> {}
cs431_homework/linked_list.rs

cs431_homework/
linked_list.rs
