]>
Commit | Line | Data |
---|---|---|
a7813a04 XL |
1 | // Copyright 2013-2016 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | use clone::Clone; | |
12 | use cmp::PartialOrd; | |
13 | use mem; | |
a7813a04 XL |
14 | use ops::{self, Add, Sub}; |
15 | use option::Option::{self, Some, None}; | |
16 | use marker::Sized; | |
17 | use usize; | |
18 | ||
19 | use super::{DoubleEndedIterator, ExactSizeIterator, Iterator}; | |
20 | ||
21 | /// Objects that can be stepped over in both directions. | |
22 | /// | |
23 | /// The `steps_between` function provides a way to efficiently compare | |
24 | /// two `Step` objects. | |
25 | #[unstable(feature = "step_trait", | |
26 | reason = "likely to be replaced by finer-grained traits", | |
27 | issue = "27741")] | |
28 | pub trait Step: PartialOrd + Sized { | |
29 | /// Steps `self` if possible. | |
30 | fn step(&self, by: &Self) -> Option<Self>; | |
31 | ||
32 | /// Returns the number of steps between two step objects. The count is | |
33 | /// inclusive of `start` and exclusive of `end`. | |
34 | /// | |
35 | /// Returns `None` if it is not possible to calculate `steps_between` | |
36 | /// without overflow. | |
37 | fn steps_between(start: &Self, end: &Self, by: &Self) -> Option<usize>; | |
3157f602 XL |
38 | |
39 | /// Same as `steps_between`, but with a `by` of 1 | |
40 | fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize>; | |
41 | ||
42 | /// Tests whether this step is negative or not (going backwards) | |
43 | fn is_negative(&self) -> bool; | |
44 | ||
45 | /// Replaces this step with `1`, returning itself | |
46 | fn replace_one(&mut self) -> Self; | |
47 | ||
48 | /// Replaces this step with `0`, returning itself | |
49 | fn replace_zero(&mut self) -> Self; | |
50 | ||
51 | /// Adds one to this step, returning the result | |
52 | fn add_one(&self) -> Self; | |
53 | ||
54 | /// Subtracts one to this step, returning the result | |
55 | fn sub_one(&self) -> Self; | |
a7813a04 XL |
56 | } |
57 | ||
58 | macro_rules! step_impl_unsigned { | |
59 | ($($t:ty)*) => ($( | |
60 | #[unstable(feature = "step_trait", | |
61 | reason = "likely to be replaced by finer-grained traits", | |
62 | issue = "27741")] | |
63 | impl Step for $t { | |
64 | #[inline] | |
65 | fn step(&self, by: &$t) -> Option<$t> { | |
66 | (*self).checked_add(*by) | |
67 | } | |
68 | #[inline] | |
69 | #[allow(trivial_numeric_casts)] | |
70 | fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> { | |
71 | if *by == 0 { return None; } | |
72 | if *start < *end { | |
73 | // Note: We assume $t <= usize here | |
74 | let diff = (*end - *start) as usize; | |
75 | let by = *by as usize; | |
76 | if diff % by > 0 { | |
77 | Some(diff / by + 1) | |
78 | } else { | |
79 | Some(diff / by) | |
80 | } | |
81 | } else { | |
82 | Some(0) | |
83 | } | |
84 | } | |
3157f602 XL |
85 | |
86 | #[inline] | |
87 | fn is_negative(&self) -> bool { | |
88 | false | |
89 | } | |
90 | ||
91 | #[inline] | |
92 | fn replace_one(&mut self) -> Self { | |
93 | mem::replace(self, 0) | |
94 | } | |
95 | ||
96 | #[inline] | |
97 | fn replace_zero(&mut self) -> Self { | |
98 | mem::replace(self, 1) | |
99 | } | |
100 | ||
101 | #[inline] | |
102 | fn add_one(&self) -> Self { | |
103 | *self + 1 | |
104 | } | |
105 | ||
106 | #[inline] | |
107 | fn sub_one(&self) -> Self { | |
108 | *self - 1 | |
109 | } | |
110 | ||
111 | #[inline] | |
112 | fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> { | |
113 | Self::steps_between(start, end, &1) | |
114 | } | |
a7813a04 XL |
115 | } |
116 | )*) | |
117 | } | |
118 | macro_rules! step_impl_signed { | |
119 | ($($t:ty)*) => ($( | |
120 | #[unstable(feature = "step_trait", | |
121 | reason = "likely to be replaced by finer-grained traits", | |
122 | issue = "27741")] | |
123 | impl Step for $t { | |
124 | #[inline] | |
125 | fn step(&self, by: &$t) -> Option<$t> { | |
126 | (*self).checked_add(*by) | |
127 | } | |
128 | #[inline] | |
129 | #[allow(trivial_numeric_casts)] | |
130 | fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> { | |
131 | if *by == 0 { return None; } | |
132 | let diff: usize; | |
133 | let by_u: usize; | |
134 | if *by > 0 { | |
135 | if *start >= *end { | |
136 | return Some(0); | |
137 | } | |
138 | // Note: We assume $t <= isize here | |
139 | // Use .wrapping_sub and cast to usize to compute the | |
140 | // difference that may not fit inside the range of isize. | |
141 | diff = (*end as isize).wrapping_sub(*start as isize) as usize; | |
142 | by_u = *by as usize; | |
143 | } else { | |
144 | if *start <= *end { | |
145 | return Some(0); | |
146 | } | |
147 | diff = (*start as isize).wrapping_sub(*end as isize) as usize; | |
148 | by_u = (*by as isize).wrapping_mul(-1) as usize; | |
149 | } | |
150 | if diff % by_u > 0 { | |
151 | Some(diff / by_u + 1) | |
152 | } else { | |
153 | Some(diff / by_u) | |
154 | } | |
155 | } | |
3157f602 XL |
156 | |
157 | #[inline] | |
158 | fn is_negative(&self) -> bool { | |
159 | *self < 0 | |
160 | } | |
161 | ||
162 | #[inline] | |
163 | fn replace_one(&mut self) -> Self { | |
164 | mem::replace(self, 0) | |
165 | } | |
166 | ||
167 | #[inline] | |
168 | fn replace_zero(&mut self) -> Self { | |
169 | mem::replace(self, 1) | |
170 | } | |
171 | ||
172 | #[inline] | |
173 | fn add_one(&self) -> Self { | |
174 | *self + 1 | |
175 | } | |
176 | ||
177 | #[inline] | |
178 | fn sub_one(&self) -> Self { | |
179 | *self - 1 | |
180 | } | |
181 | ||
182 | #[inline] | |
183 | fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> { | |
184 | Self::steps_between(start, end, &1) | |
185 | } | |
a7813a04 XL |
186 | } |
187 | )*) | |
188 | } | |
189 | ||
190 | macro_rules! step_impl_no_between { | |
191 | ($($t:ty)*) => ($( | |
192 | #[unstable(feature = "step_trait", | |
193 | reason = "likely to be replaced by finer-grained traits", | |
194 | issue = "27741")] | |
195 | impl Step for $t { | |
196 | #[inline] | |
197 | fn step(&self, by: &$t) -> Option<$t> { | |
198 | (*self).checked_add(*by) | |
199 | } | |
200 | #[inline] | |
201 | fn steps_between(_a: &$t, _b: &$t, _by: &$t) -> Option<usize> { | |
202 | None | |
203 | } | |
3157f602 XL |
204 | |
205 | #[inline] | |
206 | #[allow(unused_comparisons)] | |
207 | fn is_negative(&self) -> bool { | |
208 | *self < 0 | |
209 | } | |
210 | ||
211 | #[inline] | |
212 | fn replace_one(&mut self) -> Self { | |
213 | mem::replace(self, 0) | |
214 | } | |
215 | ||
216 | #[inline] | |
217 | fn replace_zero(&mut self) -> Self { | |
218 | mem::replace(self, 1) | |
219 | } | |
220 | ||
221 | #[inline] | |
222 | fn add_one(&self) -> Self { | |
223 | *self + 1 | |
224 | } | |
225 | ||
226 | #[inline] | |
227 | fn sub_one(&self) -> Self { | |
228 | *self - 1 | |
229 | } | |
230 | ||
231 | #[inline] | |
232 | fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> { | |
233 | Self::steps_between(start, end, &1) | |
234 | } | |
a7813a04 XL |
235 | } |
236 | )*) | |
237 | } | |
238 | ||
239 | step_impl_unsigned!(usize u8 u16 u32); | |
240 | step_impl_signed!(isize i8 i16 i32); | |
241 | #[cfg(target_pointer_width = "64")] | |
242 | step_impl_unsigned!(u64); | |
243 | #[cfg(target_pointer_width = "64")] | |
244 | step_impl_signed!(i64); | |
245 | // If the target pointer width is not 64-bits, we | |
246 | // assume here that it is less than 64-bits. | |
247 | #[cfg(not(target_pointer_width = "64"))] | |
248 | step_impl_no_between!(u64 i64); | |
249 | ||
250 | /// An adapter for stepping range iterators by a custom amount. | |
251 | /// | |
252 | /// The resulting iterator handles overflow by stopping. The `A` | |
253 | /// parameter is the type being iterated over, while `R` is the range | |
254 | /// type (usually one of `std::ops::{Range, RangeFrom, RangeInclusive}`. | |
255 | #[derive(Clone, Debug)] | |
256 | #[unstable(feature = "step_by", reason = "recent addition", | |
257 | issue = "27741")] | |
258 | pub struct StepBy<A, R> { | |
259 | step_by: A, | |
260 | range: R, | |
261 | } | |
262 | ||
263 | impl<A: Step> ops::RangeFrom<A> { | |
264 | /// Creates an iterator starting at the same point, but stepping by | |
265 | /// the given amount at each iteration. | |
266 | /// | |
267 | /// # Examples | |
268 | /// | |
269 | /// ``` | |
270 | /// # #![feature(step_by)] | |
271 | /// | |
272 | /// for i in (0u8..).step_by(2).take(10) { | |
273 | /// println!("{}", i); | |
274 | /// } | |
275 | /// ``` | |
276 | /// | |
277 | /// This prints the first ten even natural integers (0 to 18). | |
278 | #[unstable(feature = "step_by", reason = "recent addition", | |
279 | issue = "27741")] | |
280 | pub fn step_by(self, by: A) -> StepBy<A, Self> { | |
281 | StepBy { | |
282 | step_by: by, | |
283 | range: self | |
284 | } | |
285 | } | |
286 | } | |
287 | ||
288 | impl<A: Step> ops::Range<A> { | |
289 | /// Creates an iterator with the same range, but stepping by the | |
290 | /// given amount at each iteration. | |
291 | /// | |
292 | /// The resulting iterator handles overflow by stopping. | |
293 | /// | |
294 | /// # Examples | |
295 | /// | |
296 | /// ``` | |
297 | /// #![feature(step_by)] | |
298 | /// | |
299 | /// for i in (0..10).step_by(2) { | |
300 | /// println!("{}", i); | |
301 | /// } | |
302 | /// ``` | |
303 | /// | |
304 | /// This prints: | |
305 | /// | |
306 | /// ```text | |
307 | /// 0 | |
308 | /// 2 | |
309 | /// 4 | |
310 | /// 6 | |
311 | /// 8 | |
312 | /// ``` | |
313 | #[unstable(feature = "step_by", reason = "recent addition", | |
314 | issue = "27741")] | |
315 | pub fn step_by(self, by: A) -> StepBy<A, Self> { | |
316 | StepBy { | |
317 | step_by: by, | |
318 | range: self | |
319 | } | |
320 | } | |
321 | } | |
322 | ||
323 | impl<A: Step> ops::RangeInclusive<A> { | |
324 | /// Creates an iterator with the same range, but stepping by the | |
325 | /// given amount at each iteration. | |
326 | /// | |
327 | /// The resulting iterator handles overflow by stopping. | |
328 | /// | |
329 | /// # Examples | |
330 | /// | |
331 | /// ``` | |
332 | /// #![feature(step_by, inclusive_range_syntax)] | |
333 | /// | |
334 | /// for i in (0...10).step_by(2) { | |
335 | /// println!("{}", i); | |
336 | /// } | |
337 | /// ``` | |
338 | /// | |
339 | /// This prints: | |
340 | /// | |
341 | /// ```text | |
342 | /// 0 | |
343 | /// 2 | |
344 | /// 4 | |
345 | /// 6 | |
346 | /// 8 | |
347 | /// 10 | |
348 | /// ``` | |
349 | #[unstable(feature = "step_by", reason = "recent addition", | |
350 | issue = "27741")] | |
351 | pub fn step_by(self, by: A) -> StepBy<A, Self> { | |
352 | StepBy { | |
353 | step_by: by, | |
354 | range: self | |
355 | } | |
356 | } | |
357 | } | |
358 | ||
359 | #[stable(feature = "rust1", since = "1.0.0")] | |
360 | impl<A> Iterator for StepBy<A, ops::RangeFrom<A>> where | |
361 | A: Clone, | |
362 | for<'a> &'a A: Add<&'a A, Output = A> | |
363 | { | |
364 | type Item = A; | |
365 | ||
366 | #[inline] | |
367 | fn next(&mut self) -> Option<A> { | |
368 | let mut n = &self.range.start + &self.step_by; | |
369 | mem::swap(&mut n, &mut self.range.start); | |
370 | Some(n) | |
371 | } | |
372 | ||
373 | #[inline] | |
374 | fn size_hint(&self) -> (usize, Option<usize>) { | |
375 | (usize::MAX, None) // Too bad we can't specify an infinite lower bound | |
376 | } | |
377 | } | |
378 | ||
379 | #[stable(feature = "rust1", since = "1.0.0")] | |
3157f602 | 380 | impl<A: Step + Clone> Iterator for StepBy<A, ops::Range<A>> { |
a7813a04 XL |
381 | type Item = A; |
382 | ||
383 | #[inline] | |
384 | fn next(&mut self) -> Option<A> { | |
3157f602 | 385 | let rev = self.step_by.is_negative(); |
a7813a04 XL |
386 | if (rev && self.range.start > self.range.end) || |
387 | (!rev && self.range.start < self.range.end) | |
388 | { | |
389 | match self.range.start.step(&self.step_by) { | |
390 | Some(mut n) => { | |
391 | mem::swap(&mut self.range.start, &mut n); | |
392 | Some(n) | |
393 | }, | |
394 | None => { | |
395 | let mut n = self.range.end.clone(); | |
396 | mem::swap(&mut self.range.start, &mut n); | |
397 | Some(n) | |
398 | } | |
399 | } | |
400 | } else { | |
401 | None | |
402 | } | |
403 | } | |
404 | ||
405 | #[inline] | |
406 | fn size_hint(&self) -> (usize, Option<usize>) { | |
407 | match Step::steps_between(&self.range.start, | |
408 | &self.range.end, | |
409 | &self.step_by) { | |
410 | Some(hint) => (hint, Some(hint)), | |
411 | None => (0, None) | |
412 | } | |
413 | } | |
414 | } | |
415 | ||
416 | #[unstable(feature = "inclusive_range", | |
417 | reason = "recently added, follows RFC", | |
418 | issue = "28237")] | |
3157f602 | 419 | impl<A: Step + Clone> Iterator for StepBy<A, ops::RangeInclusive<A>> { |
a7813a04 XL |
420 | type Item = A; |
421 | ||
422 | #[inline] | |
423 | fn next(&mut self) -> Option<A> { | |
424 | use ops::RangeInclusive::*; | |
425 | ||
426 | // this function has a sort of odd structure due to borrowck issues | |
427 | // we may need to replace self.range, so borrows of start and end need to end early | |
428 | ||
429 | let (finishing, n) = match self.range { | |
430 | Empty { .. } => return None, // empty iterators yield no values | |
431 | ||
432 | NonEmpty { ref mut start, ref mut end } => { | |
3157f602 | 433 | let rev = self.step_by.is_negative(); |
a7813a04 XL |
434 | |
435 | // march start towards (maybe past!) end and yield the old value | |
436 | if (rev && start >= end) || | |
437 | (!rev && start <= end) | |
438 | { | |
439 | match start.step(&self.step_by) { | |
440 | Some(mut n) => { | |
441 | mem::swap(start, &mut n); | |
442 | (None, Some(n)) // yield old value, remain non-empty | |
443 | }, | |
444 | None => { | |
445 | let mut n = end.clone(); | |
446 | mem::swap(start, &mut n); | |
447 | (None, Some(n)) // yield old value, remain non-empty | |
448 | } | |
449 | } | |
450 | } else { | |
451 | // found range in inconsistent state (start at or past end), so become empty | |
3157f602 | 452 | (Some(end.replace_zero()), None) |
a7813a04 XL |
453 | } |
454 | } | |
455 | }; | |
456 | ||
457 | // turn into an empty iterator if we've reached the end | |
458 | if let Some(end) = finishing { | |
459 | self.range = Empty { at: end }; | |
460 | } | |
461 | ||
462 | n | |
463 | } | |
464 | ||
465 | #[inline] | |
466 | fn size_hint(&self) -> (usize, Option<usize>) { | |
467 | use ops::RangeInclusive::*; | |
468 | ||
469 | match self.range { | |
470 | Empty { .. } => (0, Some(0)), | |
471 | ||
472 | NonEmpty { ref start, ref end } => | |
473 | match Step::steps_between(start, | |
474 | end, | |
475 | &self.step_by) { | |
476 | Some(hint) => (hint.saturating_add(1), hint.checked_add(1)), | |
477 | None => (0, None) | |
478 | } | |
479 | } | |
480 | } | |
481 | } | |
482 | ||
483 | macro_rules! range_exact_iter_impl { | |
484 | ($($t:ty)*) => ($( | |
485 | #[stable(feature = "rust1", since = "1.0.0")] | |
486 | impl ExactSizeIterator for ops::Range<$t> { } | |
487 | ||
488 | #[unstable(feature = "inclusive_range", | |
489 | reason = "recently added, follows RFC", | |
490 | issue = "28237")] | |
491 | impl ExactSizeIterator for ops::RangeInclusive<$t> { } | |
492 | )*) | |
493 | } | |
494 | ||
495 | #[stable(feature = "rust1", since = "1.0.0")] | |
3157f602 | 496 | impl<A: Step> Iterator for ops::Range<A> where |
a7813a04 XL |
497 | for<'a> &'a A: Add<&'a A, Output = A> |
498 | { | |
499 | type Item = A; | |
500 | ||
501 | #[inline] | |
502 | fn next(&mut self) -> Option<A> { | |
503 | if self.start < self.end { | |
3157f602 | 504 | let mut n = self.start.add_one(); |
a7813a04 XL |
505 | mem::swap(&mut n, &mut self.start); |
506 | Some(n) | |
507 | } else { | |
508 | None | |
509 | } | |
510 | } | |
511 | ||
512 | #[inline] | |
513 | fn size_hint(&self) -> (usize, Option<usize>) { | |
3157f602 | 514 | match Step::steps_between_by_one(&self.start, &self.end) { |
a7813a04 XL |
515 | Some(hint) => (hint, Some(hint)), |
516 | None => (0, None) | |
517 | } | |
518 | } | |
519 | } | |
520 | ||
521 | // Ranges of u64 and i64 are excluded because they cannot guarantee having | |
522 | // a length <= usize::MAX, which is required by ExactSizeIterator. | |
523 | range_exact_iter_impl!(usize u8 u16 u32 isize i8 i16 i32); | |
524 | ||
525 | #[stable(feature = "rust1", since = "1.0.0")] | |
3157f602 | 526 | impl<A: Step + Clone> DoubleEndedIterator for ops::Range<A> where |
a7813a04 XL |
527 | for<'a> &'a A: Add<&'a A, Output = A>, |
528 | for<'a> &'a A: Sub<&'a A, Output = A> | |
529 | { | |
530 | #[inline] | |
531 | fn next_back(&mut self) -> Option<A> { | |
532 | if self.start < self.end { | |
3157f602 | 533 | self.end = self.end.sub_one(); |
a7813a04 XL |
534 | Some(self.end.clone()) |
535 | } else { | |
536 | None | |
537 | } | |
538 | } | |
539 | } | |
540 | ||
541 | #[stable(feature = "rust1", since = "1.0.0")] | |
3157f602 | 542 | impl<A: Step> Iterator for ops::RangeFrom<A> where |
a7813a04 XL |
543 | for<'a> &'a A: Add<&'a A, Output = A> |
544 | { | |
545 | type Item = A; | |
546 | ||
547 | #[inline] | |
548 | fn next(&mut self) -> Option<A> { | |
3157f602 | 549 | let mut n = self.start.add_one(); |
a7813a04 XL |
550 | mem::swap(&mut n, &mut self.start); |
551 | Some(n) | |
552 | } | |
553 | } | |
554 | ||
555 | #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")] | |
3157f602 | 556 | impl<A: Step> Iterator for ops::RangeInclusive<A> where |
a7813a04 XL |
557 | for<'a> &'a A: Add<&'a A, Output = A> |
558 | { | |
559 | type Item = A; | |
560 | ||
561 | #[inline] | |
562 | fn next(&mut self) -> Option<A> { | |
563 | use ops::RangeInclusive::*; | |
564 | ||
565 | // this function has a sort of odd structure due to borrowck issues | |
566 | // we may need to replace self, so borrows of self.start and self.end need to end early | |
567 | ||
568 | let (finishing, n) = match *self { | |
569 | Empty { .. } => (None, None), // empty iterators yield no values | |
570 | ||
571 | NonEmpty { ref mut start, ref mut end } => { | |
572 | if start == end { | |
3157f602 | 573 | (Some(end.replace_one()), Some(start.replace_one())) |
a7813a04 | 574 | } else if start < end { |
3157f602 | 575 | let mut n = start.add_one(); |
a7813a04 XL |
576 | mem::swap(&mut n, start); |
577 | ||
3157f602 XL |
578 | // if the iterator is done iterating, it will change from |
579 | // NonEmpty to Empty to avoid unnecessary drops or clones, | |
580 | // we'll reuse either start or end (they are equal now, so | |
581 | // it doesn't matter which) to pull out end, we need to swap | |
582 | // something back in | |
a7813a04 | 583 | |
3157f602 | 584 | (if n == *end { Some(end.replace_one()) } else { None }, |
a7813a04 XL |
585 | // ^ are we done yet? |
586 | Some(n)) // < the value to output | |
587 | } else { | |
3157f602 | 588 | (Some(start.replace_one()), None) |
a7813a04 XL |
589 | } |
590 | } | |
591 | }; | |
592 | ||
593 | // turn into an empty iterator if this is the last value | |
594 | if let Some(end) = finishing { | |
595 | *self = Empty { at: end }; | |
596 | } | |
597 | ||
598 | n | |
599 | } | |
600 | ||
601 | #[inline] | |
602 | fn size_hint(&self) -> (usize, Option<usize>) { | |
603 | use ops::RangeInclusive::*; | |
604 | ||
605 | match *self { | |
606 | Empty { .. } => (0, Some(0)), | |
607 | ||
608 | NonEmpty { ref start, ref end } => | |
3157f602 | 609 | match Step::steps_between_by_one(start, end) { |
a7813a04 XL |
610 | Some(hint) => (hint.saturating_add(1), hint.checked_add(1)), |
611 | None => (0, None), | |
612 | } | |
613 | } | |
614 | } | |
615 | } | |
616 | ||
617 | #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")] | |
3157f602 | 618 | impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> where |
a7813a04 XL |
619 | for<'a> &'a A: Add<&'a A, Output = A>, |
620 | for<'a> &'a A: Sub<&'a A, Output = A> | |
621 | { | |
622 | #[inline] | |
623 | fn next_back(&mut self) -> Option<A> { | |
624 | use ops::RangeInclusive::*; | |
625 | ||
626 | // see Iterator::next for comments | |
627 | ||
628 | let (finishing, n) = match *self { | |
629 | Empty { .. } => return None, | |
630 | ||
631 | NonEmpty { ref mut start, ref mut end } => { | |
632 | if start == end { | |
3157f602 | 633 | (Some(start.replace_one()), Some(end.replace_one())) |
a7813a04 | 634 | } else if start < end { |
3157f602 | 635 | let mut n = end.sub_one(); |
a7813a04 XL |
636 | mem::swap(&mut n, end); |
637 | ||
3157f602 | 638 | (if n == *start { Some(start.replace_one()) } else { None }, |
a7813a04 XL |
639 | Some(n)) |
640 | } else { | |
3157f602 | 641 | (Some(end.replace_one()), None) |
a7813a04 XL |
642 | } |
643 | } | |
644 | }; | |
645 | ||
646 | if let Some(start) = finishing { | |
647 | *self = Empty { at: start }; | |
648 | } | |
649 | ||
650 | n | |
651 | } | |
652 | } | |
653 |