Write your own adapters, with an extension trait

An iterator adapter is a type that wraps another iterator and changes what comes out of it. map, filter and take are adapters from the standard library. In this exercise you write two adapters of your own and make them callable as methods on any iterator, the same way map is.

pub struct DedupAdjacent<I: Iterator> { /* .. */ }
pub struct Pairwise<I: Iterator>      { /* .. */ }

pub trait IterExt: Iterator + Sized {
    fn dedup_adjacent(self) -> DedupAdjacent<Self> { /* .. */ }
    fn pairwise(self) -> Pairwise<Self> { /* .. */ }
}
impl<I: Iterator> IterExt for I {}

pub fn dedup_and_pair(nums: Vec<i64>) -> (Vec<i64>, Vec<(i64, i64)>)

The contract

• dedup_adjacent skips an item when it is equal (by PartialEq) to the item emitted immediately before it. The first item is always emitted. [1, 1, 2, 2, 2, 3] becomes 1, 2, 3. [1, 2, 1] stays 1, 2, 1, because only neighbouring repeats are removed; this is not a global "remove all duplicates".
• pairwise yields every pair of neighbouring items, in order: [1, 2, 3] becomes (1, 2), (2, 3). Each item except the first and last appears in two pairs. An input of n items yields n - 1 pairs, and an input with fewer than two items yields no pairs. This is similar to slice::windows(2), except that it works on any iterator (not only a slice) and yields owned tuples instead of borrowed sub-slices.
• dedup_and_pair(nums) returns two things: the result of dedup_adjacent on nums, and the result of pairwise on that deduplicated list (not on the original nums). The starter already contains this function.

Inputs are any i64 values, in any order, including an empty list and negative numbers. Order is preserved everywhere. Nothing is summed, so there is no arithmetic overflow to handle in the items themselves.

For example, [-1, -1, 0, 0, -1] deduplicates to [-1, 0, -1], whose pairs are (-1, 0), (0, -1). [5, 5, 5, 5] deduplicates to [5], which has no pairs.

size_hint is graded too

Iterator::size_hint returns (lower, upper): a promise that the iterator will yield at least lower and at most upper more items, where an upper of None means "no known limit". The default implementation returns (0, None), which is always true but tells callers nothing. Before running the cases, the harness calls your adapters directly on nums.iter().copied() (a source whose hint is exact) and checks:

• DedupAdjacent: lower <= actual count <= upper, and upper must be Some and no larger than nums.len(). The default (0, None) fails.
• Pairwise: the hint must be exactly (actual, Some(actual)).

Adapters are plain structs

The standard library's adapters are ordinary generic structs that hold the iterator below them. A chain such as v.iter().filter(..).map(..) has a type like this (closure types have no names you can write; the compiler prints each one as {closure@...} with its source location, shortened here to {closure}):

Map<Filter<Iter<'_, i32>, {closure}>, {closure}>

Each layer's next calls the next of the layer it holds. Because the types are all known at compile time, these calls are statically dispatched (no trait objects or virtual calls are involved), and the optimizer can usually inline the layers into a single loop. That is typical, not guaranteed: it depends on the optimization level and the inliner's decisions. DedupAdjacent and Pairwise follow the same pattern.

The extension trait, and the two bounds it needs

You cannot add methods to Iterator itself, because it is defined in the standard library. The usual workaround is an extension trait: a new trait whose methods have default bodies, plus a blanket implementation, which implements the trait for every type that meets a bound:

pub trait IterExt: Iterator + Sized { /* methods with default bodies */ }
impl<I: Iterator> IterExt for I {}

The impl block is empty because every method already has a body in the trait. After this, any iterator in a crate that can see IterExt (bring it into scope with use) can call .dedup_adjacent() and .pairwise(). The itertools crate's Itertools trait is built the same way.

The : Iterator + Sized after the trait name are supertraits: they require every implementing type to also implement Iterator and Sized, so the default bodies may rely on both. The starter leaves them out, and compiling it reports a series of E0277 errors (several per method, at the self parameter, the return type and the struct literal), all of these two kinds:

error[E0277]: `Self` is not an iterator
error[E0277]: the size for values of type `Self` cannot be known at compilation time

• Iterator is needed because the method return types DedupAdjacent<Self> and Pairwise<Self> require their parameter to be an iterator. Without the supertrait, Self could be any type.
• Sized is needed because, inside a trait, Self is not assumed to have a size known at compile time (it could be str or dyn Trait). A default body that takes self by value needs that size, and so does the return type: a generic parameter such as the I in DedupAdjacent<I> is required to be Sized unless it is declared ?Sized. Putting Sized on the trait is the simplest fix. Alternatively, you can write where Self: Sized on each such method, which keeps the trait usable for unsized types through its other methods.

Where the Clone and PartialEq bounds go

Pairwise uses each item twice: as the right half of one pair and the left half of the next. It must keep a copy, so it needs Item: Clone. DedupAdjacent returns an item and also remembers it for the next comparison, so it needs Item: PartialEq + Clone.

There are two places those bounds could be written:

// On the struct: every use of the type must prove the bound,
// including code that only stores or names it.
pub struct Pairwise<I: Iterator> where I::Item: Clone { .. }

// On the impl: the bound is required only where iteration is needed.
impl<I> Iterator for Pairwise<I> where I: Iterator, I::Item: Clone { .. }

A bound on a struct must be repeated by every generic function and impl that mentions the type. A bound on an impl applies only to that impl. The standard library's adapters generally use the second form. The structs here still carry I: Iterator, because the field type Option<I::Item> names an associated type of Iterator and cannot be written without it.

Writing the hints

• DedupAdjacent: (0, inner_upper) is a correct hint. The upper bound is the source's upper bound, since you never emit more items than the source has left. A lower bound of 0 is safe because, once an item has been emitted, every remaining item could equal it. (Before the first item you could report 1 when the source is known to be non-empty, but the tests do not require that.)
• Pairwise: let r be the number of items the source has left. If you are holding a previous item, each remaining source item completes one pair, so r pairs remain. If you are not, the next source item only becomes a left half, so r - 1 pairs remain, floored at zero. Apply this to both lower and upper (when upper is Some).

Two arithmetic traps live here, both on usize:

• r - 1 when r is 0 underflows. With default build settings, that panics in a debug build and silently wraps to usize::MAX in a release build. Use saturating_sub(1).
• Computing r + 1 - 1 instead of handling the two cases separately can overflow. An infinite source such as 0u64.. reports a lower bound of usize::MAX, and adding one to it panics in a debug build. The tests feed only finite vectors, but a general-purpose adapter should not panic in size_hint.

The type_complexity lint

Clippy's type_complexity lint is on by default and warns when a type written in a signature exceeds a complexity threshold, which deeply nested adapter types can do. Two common fixes: a type alias, or returning impl Iterator<Item = T> from a function that builds the chain, which hides the concrete type and lets you change the chain without changing callers.

Generator blocks

Rust has an experimental gen block syntax that would let you write these adapters as ordinary loops with yield. In Rust 1.98, gen is a reserved keyword in edition 2024 but gen blocks are unstable, so stable Rust rejects them. Writing a struct with a next method, as here, is the stable way to build a custom adapter.

Grading: the code must compile, pass the test cases (including the size_hint checks above), and pass cargo clippy -- -D warnings.