1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
use crate::ops::{ControlFlow, Try};

/// 一个能够从两端产生元素的迭代器。
///
/// 实现 `DoubleEndedIterator` 的东西比实现 [`Iterator`] 的东西具有一项额外的功能: 既可以从后面也可以从前面获得 `item` 的功能。
///
///
/// 重要的是要注意,来回运动都在相同的范围内,并且不会交叉: 当它们在中间相遇时,迭代就结束了。
///
/// 以与 [`Iterator`] 协议类似的方式,一旦 `DoubleEndedIterator` 从 [`next_back()`] 返回 [`None`],再次调用它可能会也可能不会再返回 [`Some`]。
/// [`next()`] [`next_back()`] 和 [`next_back()`] 可以互换使用。
///
/// [`next_back()`]: DoubleEndedIterator::next_back
/// [`next()`]: Iterator::next
///
/// # Examples
///
/// 基本用法:
///
/// ```
/// let numbers = vec![1, 2, 3, 4, 5, 6];
///
/// let mut iter = numbers.iter();
///
/// assert_eq!(Some(&1), iter.next());
/// assert_eq!(Some(&6), iter.next_back());
/// assert_eq!(Some(&5), iter.next_back());
/// assert_eq!(Some(&2), iter.next());
/// assert_eq!(Some(&3), iter.next());
/// assert_eq!(Some(&4), iter.next());
/// assert_eq!(None, iter.next());
/// assert_eq!(None, iter.next_back());
/// ```
///
///
///
///
#[stable(feature = "rust1", since = "1.0.0")]
#[cfg_attr(not(test), rustc_diagnostic_item = "DoubleEndedIterator")]
pub trait DoubleEndedIterator: Iterator {
    /// 从迭代器的末尾删除并返回一个元素。
    ///
    /// 没有更多元素时返回 `None`。
    ///
    /// [trait-level] 文档包含更多详细信息。
    ///
    /// [trait-level]: DoubleEndedIterator
    ///
    /// # Examples
    ///
    /// 基本用法:
    ///
    /// ```
    /// let numbers = vec![1, 2, 3, 4, 5, 6];
    ///
    /// let mut iter = numbers.iter();
    ///
    /// assert_eq!(Some(&1), iter.next());
    /// assert_eq!(Some(&6), iter.next_back());
    /// assert_eq!(Some(&5), iter.next_back());
    /// assert_eq!(Some(&2), iter.next());
    /// assert_eq!(Some(&3), iter.next());
    /// assert_eq!(Some(&4), iter.next());
    /// assert_eq!(None, iter.next());
    /// assert_eq!(None, iter.next_back());
    /// ```
    ///
    /// # Remarks
    ///
    /// DoubleEndedIterator 方法产生的元素可能与 [Iterator`] 方法产生的元素不同:
    ///
    ///
    /// ```
    /// let vec = vec![(1, 'a'), (1, 'b'), (1, 'c'), (2, 'a'), (2, 'b')];
    /// let uniq_by_fst_comp = || {
    ///     let mut seen = std::collections::HashSet::new();
    ///     vec.iter().copied().filter(move |x| seen.insert(x.0))
    /// };
    ///
    /// assert_eq!(uniq_by_fst_comp().last(), Some((2, 'a')));
    /// assert_eq!(uniq_by_fst_comp().next_back(), Some((2, 'b')));
    ///
    /// assert_eq!(
    ///     uniq_by_fst_comp().fold(vec![], |mut v, x| {v.push(x); v}),
    ///     vec![(1, 'a'), (2, 'a')]
    /// );
    /// assert_eq!(
    ///     uniq_by_fst_comp().rfold(vec![], |mut v, x| {v.push(x); v}),
    ///     vec![(2, 'b'), (1, 'c')]
    /// );
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    fn next_back(&mut self) -> Option<Self::Item>;

    /// 通过 `n` 元素从后向前推进迭代器。
    ///
    /// `advance_back_by` 是 [`advance_by`] 的反向版本。该方法将急切地从后面开始跳过 `n` 元素,方法是调用 [`next_back`] 最多 `n` 次,直到遇到 [`None`]。
    ///
    /// `advance_back_by(n)` 如果迭代器成功地将 `n` 元素推进,则返回 [`Ok(())`]; 如果遇到 [`None`],则返回 [`Err(k)`],其中 `k` 是迭代器在元素用尽之前被推进的元素数 (即
    /// 迭代器的长度)。
    /// 请注意,`k` 始终小于 `n`。
    ///
    /// 调用 `advance_back_by(0)` 不会消耗任何元素,并且始终返回 [`Ok(())`]。
    ///
    /// [`advance_by`]: Iterator::advance_by
    /// [`next_back`]: DoubleEndedIterator::next_back
    ///
    /// # Examples
    ///
    /// 基本用法:
    ///
    /// ```
    /// #![feature(iter_advance_by)]
    ///
    /// let a = [3, 4, 5, 6];
    /// let mut iter = a.iter();
    ///
    /// assert_eq!(iter.advance_back_by(2), Ok(()));
    /// assert_eq!(iter.next_back(), Some(&4));
    /// assert_eq!(iter.advance_back_by(0), Ok(()));
    /// assert_eq!(iter.advance_back_by(100), Err(1)); // 仅跳过 `&3`
    /// ```
    ///
    /// [`Ok(())`]: Ok
    /// [`Err(k)`]: Err
    ///
    ///
    ///
    #[inline]
    #[unstable(feature = "iter_advance_by", reason = "recently added", issue = "77404")]
    fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
        for i in 0..n {
            self.next_back().ok_or(i)?;
        }
        Ok(())
    }

    /// 从迭代器的末尾返回第 n 个元素。
    ///
    /// 这实际上是 [`Iterator::nth()`] 的反向版本。
    /// 尽管像大多数索引操作一样,计数从零开始,所以 `nth_back(0)` 从末尾返回第一个值,`nth_back(1)` 从第二个开始返回,依此类推。
    ///
    ///
    /// 请注意,将使用 end 和返回元素之间的所有元素,包括返回元素。
    /// 这也意味着在同一迭代器上多次调用 `nth_back(0)` 将返回不同的元素。
    ///
    /// `nth_back()` 如果 `n` 大于或等于迭代器的长度,则将返回 [`None`]。
    ///
    /// # Examples
    ///
    /// 基本用法:
    ///
    /// ```
    /// let a = [1, 2, 3];
    /// assert_eq!(a.iter().nth_back(2), Some(&1));
    /// ```
    ///
    /// 多次调用 `nth_back()` 不会回退迭代器:
    ///
    /// ```
    /// let a = [1, 2, 3];
    ///
    /// let mut iter = a.iter();
    ///
    /// assert_eq!(iter.nth_back(1), Some(&2));
    /// assert_eq!(iter.nth_back(1), None);
    /// ```
    ///
    /// 如果少于 `n + 1` 个元素,则返回 `None`:
    ///
    /// ```
    /// let a = [1, 2, 3];
    /// assert_eq!(a.iter().nth_back(10), None);
    /// ```
    ///
    ///
    ///
    ///
    #[inline]
    #[stable(feature = "iter_nth_back", since = "1.37.0")]
    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
        self.advance_back_by(n).ok()?;
        self.next_back()
    }

    /// 这是 [`Iterator::try_fold()`] 的反向版本: 它从迭代器的后面开始接收元素。
    ///
    ///
    /// # Examples
    ///
    /// 基本用法:
    ///
    /// ```
    /// let a = ["1", "2", "3"];
    /// let sum = a.iter()
    ///     .map(|&s| s.parse::<i32>())
    ///     .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
    /// assert_eq!(sum, Ok(6));
    /// ```
    ///
    /// Short-circuiting:
    ///
    /// ```
    /// let a = ["1", "rust", "3"];
    /// let mut it = a.iter();
    /// let sum = it
    ///     .by_ref()
    ///     .map(|&s| s.parse::<i32>())
    ///     .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
    /// assert!(sum.is_err());
    ///
    /// // 由于发生短路,因此其余元素仍可通过迭代器使用。
    /////
    /// assert_eq!(it.next_back(), Some(&"1"));
    /// ```
    #[inline]
    #[stable(feature = "iterator_try_fold", since = "1.27.0")]
    fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
    where
        Self: Sized,
        F: FnMut(B, Self::Item) -> R,
        R: Try<Output = B>,
    {
        let mut accum = init;
        while let Some(x) = self.next_back() {
            accum = f(accum, x)?;
        }
        try { accum }
    }

    /// 一种迭代器方法,从后面开始,将迭代器的元素减少为单个最终值。
    ///
    /// 这是 [`Iterator::fold()`] 的反向版本: 它从迭代器的后面开始接收元素。
    ///
    /// `rfold()` 接受两个参数: 一个初始值和一个带有两个参数的闭包: 一个 'accumulator' 和一个元素。
    /// 闭包返回累加器在下一次迭代中应具有的值。
    ///
    /// 初始值是累加器在第一次调用时将具有的值。
    ///
    /// 在将此闭包应用于迭代器的每个元素之后,`rfold()` 返回累加器。
    ///
    /// 该操作有时称为 'reduce' 或 'inject'。
    ///
    /// 当您拥有某个集合,并且希望从中产生单个值时,`fold` 非常有用。
    ///
    /// Note: `rfold()` 以*右关联*方式组合元素。
    /// 对于像 `+` 这样的关联性,元素组合的顺序并不重要,但对于像 `-` 这样的非关联性,顺序会影响最终结果。
    ///
    /// 对于 `rfold()` 的*左关联*版本,请参见 [`Iterator::fold()`]。
    ///
    /// # Examples
    ///
    /// 基本用法:
    ///
    /// ```
    /// let a = [1, 2, 3];
    ///
    /// // a 的所有元素的总和
    /// let sum = a.iter()
    ///            .rfold(0, |acc, &x| acc + x);
    ///
    /// assert_eq!(sum, 6);
    /// ```
    ///
    /// 这个例子演示了 `rfold()` 的右结合性质:
    /// 它构建一个字符串,从一个初始值开始,从后面到前面的每个元素继续:
    ///
    /// ```
    /// let numbers = [1, 2, 3, 4, 5];
    ///
    /// let zero = "0".to_string();
    ///
    /// let result = numbers.iter().rfold(zero, |acc, &x| {
    ///     format!("({} + {})", x, acc)
    /// });
    ///
    /// assert_eq!(result, "(1 + (2 + (3 + (4 + (5 + 0)))))");
    /// ```
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    #[doc(alias = "foldr")]
    #[inline]
    #[stable(feature = "iter_rfold", since = "1.27.0")]
    fn rfold<B, F>(mut self, init: B, mut f: F) -> B
    where
        Self: Sized,
        F: FnMut(B, Self::Item) -> B,
    {
        let mut accum = init;
        while let Some(x) = self.next_back() {
            accum = f(accum, x);
        }
        accum
    }

    /// 从后面搜索满足谓词的迭代器的元素。
    ///
    /// `rfind()` 接受一个返回 `true` 或 `false` 的闭包。
    /// 它将这个闭包应用到迭代器的每个元素 (从末尾开始),如果其中任何一个返回 `true`,则 `rfind()` 返回 [`Some(element)`]。
    /// 如果它们都返回 `false`,则返回 [`None`]。
    ///
    /// `rfind()` 短路; 换句话说,一旦闭包返回 `true`,它将立即停止处理。
    ///
    /// 由于 `rfind()` 接受 quot,并且许多迭代器迭代 quot,因此导致参数为双 quot 的情况可能令人困惑。
    ///
    /// 在 `&&x` 的以下示例中,您可以看到这种效果。
    ///
    /// [`Some(element)`]: Some
    ///
    /// # Examples
    ///
    /// 基本用法:
    ///
    /// ```
    /// let a = [1, 2, 3];
    ///
    /// assert_eq!(a.iter().rfind(|&&x| x == 2), Some(&2));
    ///
    /// assert_eq!(a.iter().rfind(|&&x| x == 5), None);
    /// ```
    ///
    /// 在第一个 `true` 处停止:
    ///
    /// ```
    /// let a = [1, 2, 3];
    ///
    /// let mut iter = a.iter();
    ///
    /// assert_eq!(iter.rfind(|&&x| x == 2), Some(&2));
    ///
    /// // 我们仍然可以使用 `iter`,因为还有更多元素。
    /// assert_eq!(iter.next_back(), Some(&1));
    /// ```
    ///
    ///
    ///
    #[inline]
    #[stable(feature = "iter_rfind", since = "1.27.0")]
    fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
    where
        Self: Sized,
        P: FnMut(&Self::Item) -> bool,
    {
        #[inline]
        fn check<T>(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut((), T) -> ControlFlow<T> {
            move |(), x| {
                if predicate(&x) { ControlFlow::Break(x) } else { ControlFlow::CONTINUE }
            }
        }

        self.try_rfold((), check(predicate)).break_value()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, I: DoubleEndedIterator + ?Sized> DoubleEndedIterator for &'a mut I {
    fn next_back(&mut self) -> Option<I::Item> {
        (**self).next_back()
    }
    fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
        (**self).advance_back_by(n)
    }
    fn nth_back(&mut self, n: usize) -> Option<I::Item> {
        (**self).nth_back(n)
    }
}