Vec surgery: retain, dedup and extract_if

Split a vector of integers into two vectors: the elements at or above a threshold, and the elements below it. Then collapse runs of adjacent equal values in the first vector. The point of the exercise is to do this with Vec's own removal methods instead of removing elements while iterating.

pub fn compact(items: Vec<i64>, drop_below: i64) -> (Vec<i64>, Vec<i64>)

The contract

Return the tuple (kept, dropped).

• dropped holds every element < drop_below, in the order they appeared in items. Duplicates in dropped are not collapsed.
• kept starts as every element >= drop_below (the threshold is inclusive), in their original order. Then each run of adjacent equal values in kept is reduced to one copy. "Adjacent" means adjacent in kept after the split, not in the original input.
• Values and the threshold can be any i64, including negative numbers and the extremes. Only comparisons are needed, so nothing can overflow.
• items may be empty; then both results are empty.

Example: items = [5, 1, 7, 1, 9], drop_below = 5 gives kept = [5, 7, 9] and dropped = [1, 1]. The two 1s both stay in dropped because only kept is deduplicated.

The test harness reads the input and prints your result as a JSON object with a kept array and a dropped array; you only write compact.

Why the starter does not compile

The starter walks the vector and, when an element is too small, records it and removes it. Rust rejects it with an error that begins:

error[E0502]: cannot borrow `items` as mutable because it is also borrowed as immutable

items.iter() creates an iterator that holds a shared borrow of the vector (a &Vec<i64>, which lets you read but not change it). That borrow lasts for the whole for loop, because the loop keeps using the iterator. items.remove(i) needs a mutable borrow (&mut Vec<i64>) of the same vector while the shared one is still alive, and Rust does not allow a mutable borrow to overlap a shared one.

The rule protects you from a real bug. remove(i) shifts every later element one place to the left, so an iterator that keeps advancing would skip the element that moved into position i. In C++, the equivalent loop with std::vector::erase compiles, but continuing to use an iterator that erase has invalidated is undefined behavior.

The diagram below shows the same conflict in a smaller program: r1 is a shared borrow of s, m is a mutable borrow taken while r1 is still going to be used, and the later use of r1 is what makes the compiler report E0502.

Patching the loop with indices or a clone is possible, but Vec already has methods that do the whole removal for you.

The Vec methods for removing elements

• retain(|x| ...) keeps the elements for which the closure returns true and removes the rest, in one pass, keeping the survivors in order. The removed elements are dropped; you do not get them back.
• extract_if(range, |x| ...) removes the elements in range for which the closure returns true and returns an iterator that yields them in order. The elements it does not remove stay in the vector, in order. The first argument limits which indices are examined; pass .. for the whole vector. Removal happens as the iterator is consumed: if you drop the iterator before it finishes, the elements it has not reached stay in the vector. Collecting it into a Vec consumes it fully. Vec::extract_if has been stable since Rust 1.87.
• dedup() reduces each run of adjacent equal elements (compared with ==) to its first element. It does not sort, so it does not remove duplicates that are not next to each other.
• drain(range) removes a range of positions and yields those elements. split_off(i) moves the elements from index i onward into a new Vec. swap_remove(i) removes one element in constant time by moving the last element into its place, which changes the order. remove(i) keeps the order but shifts every later element, so it takes time proportional to the number of elements after i.

extract_if fits this problem because it produces both halves from one pass: the iterator yields dropped, and the vector is left holding kept.

A common alternative is to rebuild with filter and collect, for example items = items.into_iter().filter(..).collect(). That is correct, but it only produces one half. Getting dropped as well takes extra work, such as a second filter over a copy or Iterator::partition, which builds two new vectors. Clippy's manual_retain lint suggests retain for some rebuild spellings, such as v = v.into_iter().filter(..).collect(), but not for others, such as *v = v.iter().filter(..).copied().collect(), so passing Clippy does not mean every rebuild has been replaced.

Two cases that look alike but are not

• [1, 2, 1] with drop_below = 0 keeps everything and stays [1, 2, 1]. The two 1s are never next to each other, so dedup leaves both.
• [3, 3, 3, 1, 3, 3] with drop_below = 2 gives kept = [3] and dropped = [1]. Removing the 1 makes the two runs of 3 adjacent, and then dedup collapses them into one. This is why deduplication must happen after the split; deduplicating first would leave [3, 3].

Your submission is graded on three things: it must compile, pass the tests, and produce no warnings under cargo clippy -- -D warnings.