Implementing a Generic Filter Function in Rust

This challenge focuses on creating a flexible and reusable filter function in Rust. You'll leverage Rust's powerful type system and traits to build a function that can filter elements from any collection based on a user-defined condition. This is a fundamental operation in many data processing tasks, making it a valuable skill to master.

Problem Description

Your task is to implement a generic function named filter that takes two arguments:

A slice of elements of any type T.
A closure (or function pointer) that takes a reference to an element of type T and returns a boolean.

The filter function should return a new Vec<T> containing only the elements from the input slice for which the provided closure returned true.

Key Requirements:

The function must be generic over the type T of the elements in the slice.
The function must accept a closure as the filtering predicate. This closure should take a reference to an element (&T) and return bool.
The function should return a new Vec<T> containing the filtered elements. The original slice should not be modified.
The elements in the returned Vec should maintain their original order.

Expected Behavior:

Given an input slice and a predicate closure, the filter function will iterate through each element of the slice. For each element, it will call the predicate with a reference to that element. If the predicate returns true, the element will be added to the new Vec. If it returns false, the element will be skipped.

Edge Cases to Consider:

Empty Input Slice: The function should correctly handle an empty input slice, returning an empty Vec.
Predicate Always Returns True: All elements should be included in the output Vec.
Predicate Always Returns False: An empty Vec should be returned.

Examples

Example 1: Filtering even numbers from a vector of integers.

Input:
slice = [1, 2, 3, 4, 5, 6]
predicate = |&x: &i32| x % 2 == 0

Output:
[2, 4, 6]

Explanation: The predicate checks if a number is even. 2, 4, and 6 satisfy this condition and are included in the output.

Example 2: Filtering strings longer than a certain length.

Input:
slice = ["apple", "banana", "kiwi", "grapefruit"]
predicate = |s: &&str| s.len() > 5

Output:
["banana", "grapefruit"]

Explanation: The predicate checks if the length of the string is greater than 5. "banana" and "grapefruit" meet this criterion. Note that the closure receives `&&str` because we are iterating over a slice of `&str`.

Example 3: Filtering a vector of structs.

#[derive(Debug, PartialEq, Clone)]
struct User {
    name: String,
    age: u8,
}

let users = vec![
    User { name: "Alice".to_string(), age: 30 },
    User { name: "Bob".to_string(), age: 17 },
    User { name: "Charlie".to_string(), age: 25 },
];

Input:
slice = &users
predicate = |user: &User| user.age >= 18

Output:
[
    User { name: "Alice".to_string(), age: 30 },
    User { name: "Charlie".to_string(), age: 25 },
]

Explanation: The predicate filters for users aged 18 or older. Alice and Charlie meet this condition.

Constraints

The input slice can contain any type T for which T implements the Clone trait. This is necessary because we need to create owned copies of the elements to put into the new Vec.
The input slice can be of any length, from zero to a very large number.
The closure signature should be F where F: Fn(&T) -> bool.
The function should aim for reasonable performance; a linear time complexity (O(n)) where n is the number of elements in the input slice is expected.

Notes

Consider how you will handle ownership when moving elements from the input slice to the new Vec.
The Clone trait bound is crucial here. If you needed to filter without cloning (e.g., into a Vec<&T>), the requirements would be different.
Think about the generic type parameters and trait bounds necessary for your filter function.
You might find it helpful to look at the standard library's Iterator::filter and Iterator::collect methods for inspiration, but remember the goal is to implement your own version.