Auto merge of #44682 - bluss:iter-rfold, r=dtolnay

Add iterator method .rfold(init, function); the reverse of fold

rfold is the reverse version of fold.

Fold allows iterators to implement a different (non-resumable) internal
iteration when it is more efficient than the external iteration implemented
through the next method. (Common examples are VecDeque and .chain()).

Introduce rfold() so that the same customization is available for reverse
iteration. This is achieved by both adding the method, and by having the
Rev\<I> adaptor connect Rev::rfold → I::fold and Rev::fold → I::rfold.

On the surface, rfold(..) is just .rev().fold(..), but the special case
implementations allow a data structure specific fold to be used through for
example .iter().rev(); we thus have gains even for users never calling exactly
rfold themselves.

2 files changed, 17 insertions, 0 deletions

diff --git a/src/liballoc/lib.rs b/src/liballoc/lib.rs
index 2845d349ae1..d51aaa23c6a 100644
--- a/src/liballoc/lib.rs
+++ b/src/liballoc/lib.rs
@@ -98,6 +98,7 @@
 #![feature(generic_param_attrs)]
 #![feature(i128_type)]
 #![feature(inclusive_range)]
+#![feature(iter_rfold)]
 #![feature(lang_items)]
 #![feature(needs_allocator)]
 #![feature(nonzero)]
diff --git a/src/liballoc/vec_deque.rs b/src/liballoc/vec_deque.rs
index 00def2a1eac..6836fbb7c4d 100644
--- a/src/liballoc/vec_deque.rs
+++ b/src/liballoc/vec_deque.rs
@@ -1973,6 +1973,14 @@ impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
         self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len());
         unsafe { Some(self.ring.get_unchecked(self.head)) }
     }
+
+    fn rfold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc
+        where F: FnMut(Acc, Self::Item) -> Acc
+    {
+        let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
+        accum = back.iter().rfold(accum, &mut f);
+        front.iter().rfold(accum, &mut f)
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -2058,6 +2066,14 @@ impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
             Some(&mut *(elem as *mut _))
         }
     }
+
+    fn rfold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc
+        where F: FnMut(Acc, Self::Item) -> Acc
+    {
+        let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
+        accum = back.iter_mut().rfold(accum, &mut f);
+        front.iter_mut().rfold(accum, &mut f)
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]