add head/tail methods to linked list mutable cursor

2 files changed, 154 insertions, 0 deletions

diff --git a/library/alloc/src/collections/linked_list.rs b/library/alloc/src/collections/linked_list.rs
index 1a58ad51f78..a21eedf02f1 100644
--- a/library/alloc/src/collections/linked_list.rs
+++ b/library/alloc/src/collections/linked_list.rs
@@ -1506,6 +1506,128 @@ impl<'a, T> CursorMut<'a, T> {
         self.index = 0;
         unsafe { self.list.split_off_before_node(self.current, split_off_idx) }
     }
+
+    /// Appends an element to the front of the cursor's parent list. The node
+    /// that the cursor points to is unchanged, even if it is the "ghost" node.
+    ///
+    /// This operation should compute in O(1) time.
+    // `push_front` continues to point to "ghost" when it addes a node to mimic
+    // the behavior of `insert_before` on an empty list.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn push_front(&mut self, elt: T) {
+        // Safety: We know that `push_front` does not change the position in
+        // memory of other nodes. This ensures that `self.current` remains
+        // valid.
+        self.list.push_front(elt);
+        self.index += 1;
+    }
+
+    /// Appends an element to the back of the cursor's parent list. The node
+    /// that the cursor points to is unchanged, even if it is the "ghost" node.
+    ///
+    /// This operation should compute in O(1) time.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn push_back(&mut self, elt: T) {
+        // Safety: We know that `push_back` does not change the position in
+        // memory of other nodes. This ensures that `self.current` remains
+        // valid.
+        self.list.push_back(elt);
+    }
+
+    /// Removes the first element from the cursor's parent list and returns it,
+    /// or None if the list is empty. The element the cursor points to remains
+    /// unchanged, unless it was pointing to the front element. In that case, it
+    /// points to the new front element.
+    ///
+    /// This operation should compute in O(1) time.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn pop_front(&mut self) -> Option<T> {
+        // We can't check if current is empty, we must check the list directly.
+        // It is possible for `self.current == None` and the list to be
+        // non-empty.
+        if self.list.is_empty() {
+            None
+        } else {
+            // We can't point to the node that we pop. Copying the behavior of
+            // `remove_current`, we move on the the next node in the sequence.
+            // If the list is of length 1 then we end pointing to the "ghost"
+            // node, which is expected.
+            if self.list.head == self.current {
+                self.move_next();
+            }
+            // We always need to change the index since `head` comes before any
+            // other element.
+            self.index.checked_sub(1).unwrap_or(0);
+            self.list.pop_front()
+        }
+    }
+
+    /// Removes the last element from the cursor's parent list and returns it,
+    /// or None if the list is empty. The element the cursor points to remains
+    /// unchanged, unless it was pointing to the back element. In that case, it
+    /// points to the new back element.
+    ///
+    /// This operation should compute in O(1) time.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn pop_back(&mut self) -> Option<T> {
+        if self.list.is_empty() {
+            None
+        } else {
+            if self.list.tail == self.current {
+                self.move_prev()
+            }
+            // We don't need to change the index since `current` points to a
+            // node before `tail`.
+            self.list.pop_back()
+        }
+    }
+
+    /// Provides a reference to the front element of the cursor's parent list,
+    /// or None if the list is empty.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn front(&self) -> Option<&T> {
+        self.list.front()
+    }
+
+    /// Provides a mutable reference to the front element of the cursor's
+    /// parent list, or None if the list is empty.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn front_mut(&mut self) -> Option<&mut T> {
+        self.list.front_mut()
+    }
+
+    /// Provides a reference to the back element of the cursor's parent list,
+    /// or None if the list is empty.
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn back(&self) -> Option<&T> {
+        self.list.back()
+    }
+
+    /// Provides a mutable reference to back element of the cursor's parent
+    /// list, or `None` if the list is empty.
+    ///
+    /// # Examples
+    /// Building and mutating a list with a cursor, then getting the back element:
+    /// ```
+    /// #![feature(linked_list_cursors)]
+    /// use std::collections::LinkedList;
+    /// let mut dl = LinkedList::new();
+    /// dl.push_front(3);
+    /// dl.push_front(2);
+    /// dl.push_front(1);
+    /// let mut cursor = dl.cursor_front_mut();
+    /// *cursor.current().unwrap() = 99;
+    /// *cursor.back_mut().unwrap() = 0;
+    /// let mut contents = dl.into_iter();
+    /// assert_eq!(contents.next(), Some(99));
+    /// assert_eq!(contents.next(), Some(2));
+    /// assert_eq!(contents.next(), Some(0));
+    /// assert_eq!(contents.next(), None);
+    /// ```
+    #[unstable(feature = "linked_list_cursors", issue = "58533")]
+    pub fn back_mut(&mut self) -> Option<&mut T> {
+        self.list.back_mut()
+    }
 }
 
 /// An iterator produced by calling `drain_filter` on LinkedList.
diff --git a/library/alloc/src/collections/linked_list/tests.rs b/library/alloc/src/collections/linked_list/tests.rs
index ad643a7bdf1..429685260fd 100644
--- a/library/alloc/src/collections/linked_list/tests.rs
+++ b/library/alloc/src/collections/linked_list/tests.rs
@@ -428,3 +428,35 @@ fn test_cursor_mut_insert() {
     check_links(&m);
     assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[200, 201, 202, 203, 1, 100, 101]);
 }
+
+#[test]
+fn test_cursor_push_front_back() {
+    let mut ll: LinkedList<u32> = LinkedList::new();
+    ll.extend(&[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
+    let mut c = ll.cursor_front_mut();
+    assert_eq!(c.current(), Some(&mut 1));
+    assert_eq!(c.index(), Some(0));
+    c.push_front(0);
+    assert_eq!(c.current(), Some(&mut 1));
+    assert_eq!(c.peek_prev(), Some(&mut 0));
+    assert_eq!(c.index(), Some(1));
+    c.push_back(11);
+    drop(c);
+    assert_eq!(ll, (0..12).collect());
+    check_links(&ll);
+}
+
+#[test]
+fn test_cursor_pop_front_back() {
+    let mut ll: LinkedList<u32> = LinkedList::new();
+    ll.extend(&[1, 2, 3, 4, 5, 6]);
+    let mut c = ll.cursor_back_mut();
+    assert_eq!(c.pop_front(), Some(1));
+    c.move_prev();
+    c.move_prev();
+    c.move_prev();
+    assert_eq!(c.pop_back(), Some(6));
+    drop(c);
+    assert_eq!(ll, (2..6).collect());
+    check_links(&ll);
+}