size_hint and DoubleEndedIterator: an iterator with two ends

Implement an inclusive integer span that can be consumed from both ends and that reports how many items remain.

pub struct Span { pub lo: i64, pub hi: i64 }

pub fn span_probe(lo: i64, hi: i64, take_front: usize, take_back: usize)
    -> (Vec<i64>, usize, usize)

Span { lo, hi } represents the integers lo..=hi, both ends included. It is empty when lo > hi. The starter already implements Iterator::next, which yields from the low end. Add:

• a size_hint that reports the exact number of remaining items;
• DoubleEndedIterator, whose next_back yields from the high end;
• ExactSizeIterator.

The exercise contract

Every test uses lo and hi between -1_000_000_000 and 1_000_000_000 inclusive, so the remaining count always fits in usize and stepping past either end cannot overflow i64. take_front and take_back can be any non-negative value, including zero and values larger than the span.

The starter also contains a complete span_probe; you do not need to change it. In this order, it:

1. records span.len(), which comes from ExactSizeIterator;
2. records span.size_hint().0, the lower bound of the hint;
3. repeats rounds until both budgets are zero. In each round it first takes one element with next if take_front budget remains, then one with next_back if take_back budget remains. Each taken element is pushed onto the output vector. The loop stops early the first time either call returns None.

Both counts are recorded before anything is consumed, so they describe the whole span. The function returns (taken, len, hint_lower), and the grader reports it as JSON with the keys taken, len and hint.

span_probe(1, 5, 2, 1)    ->  ([1, 5, 2],    5, 5)
span_probe(1, 4, 10, 10)  ->  ([1, 4, 2, 3], 4, 4)
span_probe(5, 1, 2, 2)    ->  ([],           0, 0)
span_probe(0, 0, 0, 0)    ->  ([],           1, 1)

In the first example, round one takes 1 from the front and 5 from the back. Round two takes 2 from the front; the back budget is already spent. In the second, the budgets are larger than the span, so each of the four values appears once and the next call returns None. The third span is empty. The fourth span contains only 0, but zero budgets mean nothing is taken.

What size_hint reports

fn size_hint(&self) -> (usize, Option<usize>)

The first value is a lower bound on how many items remain. The second is an upper bound, or None when the iterator cannot give one. The default implementation returns (0, None). That is always a valid answer because it promises nothing, but callers cannot use it to plan ahead.

The standard library treats the hint mainly as an optimization input. For example, Vec and String collection and extend code currently use the lower bound to reserve space before inserting items. This is an implementation detail, not a documented guarantee about the number of allocations. With (0, None), a vector starts small and grows as needed.

Adapters combine the hints of the iterators they wrap. On Rust 1.98.1, with v a 20-element vector and chunks a Vec<Vec<u32>>:

map produces one output per input, so it passes the hint through. chain adds the two hints. filter may reject every item, so its lower bound is 0, but it can never produce more than its input. A fresh flatten or flat_map over vectors cannot know the inner lengths before reaching them, so it reports no upper bound. str::split does not compute a count in advance and also reports (0, None).

Some fixed-size cases, such as flattening arrays, can report more precise hints. The table shows only the expressions listed.

Why a correct hint matters

Rust's documentation says that an incorrect size_hint must not cause memory unsafety, and unsafe code must not rely on it for that reason. It is still a bug for an iterator to yield fewer items than its lower bound or more than its upper bound.

A wrong hint can also produce wrong results, not just extra work. Some standard methods and adapters use the length reported by ExactSizeIterator. For example, iterating enumerate().rev() computes each index from that length. When the hint is wrong, the indices are wrong. This exercise returns the reported length and lower bound so the tests can check them directly.

The standard library has an unstable unsafe marker trait, TrustedLen, for iterators whose hint is guaranteed exact. It lets internal Vec code fill a preallocated buffer with fewer checks. Stable code cannot implement it for its own iterators, so Span cannot opt into that optimization. A correct hint still lets ordinary collection code reserve the right capacity.

ExactSizeIterator relies on the hint

ExactSizeIterator promises that size_hint is exact. Its provided len method is equivalent to:

fn len(&self) -> usize {
    let (lower, upper) = self.size_hint();
    assert_eq!(upper, Some(lower));
    lower
}

If the two bounds disagree, len panics in both debug and release builds. With a hint of (3, Some(4)), the message includes:

assertion `left == right` failed
  left: Some(4)
 right: Some(3)

The assertion cannot detect a hint whose bounds agree but are both wrong. A hint of (3, Some(3)) for four remaining items returns 3 without a panic. That is why the tests compare len with the true count.

Once size_hint is exact, impl ExactSizeIterator for Span {} needs no method bodies.

Some standard ranges do not implement ExactSizeIterator at all, because their length may not fit in usize on every target. For example, (0i64..5).len() and (0i32..=5).len() are rejected with E0599, while (0i32..5).len() compiles. The input bounds above avoid that problem for Span.

DoubleEndedIterator: both ends share one sequence

fn next_back(&mut self) -> Option<Self::Item>

next_back removes an item from the other end of the same sequence. The standard documentation describes the two ends as working on the same range and not crossing. Methods such as rev, rfind, rfold and nth_back use this trait. rposition also requires ExactSizeIterator.

For Span, next moves lo up and next_back moves hi down. When lo > hi, no items remain. An off-by-one error can make both ends return the middle element. With span_probe(10, 12, 3, 3), the correct output is [10, 12, 11]; the next call returns None, so 11 must not appear twice.

last is an Iterator method. Its default implementation consumes items from the front until the end, even if the iterator also implements DoubleEndedIterator. Some iterators override it. Clippy 1.98 enables the double_ended_iterator_last lint by default and suggests next_back when calling last would needlessly walk the whole iterator.

FusedIterator

An ordinary iterator may return Some again after returning None. FusedIterator is a marker trait promising that, after the first None, every later call to next also returns None. The standard library uses it to make Iterator::fuse cheaper. Any iterator can be wrapped with .fuse() to get that behavior.

Within this exercise's input bounds, Span behaves this way: once lo > hi, neither method changes the fields again. You do not need to implement FusedIterator for these tests.

Passing requires compilation, the expected outputs and Clippy with warnings treated as errors.