| // Copyright 2023 Google LLC |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // https://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| /// Placeholder implementation of Vec::drain_filter. |
| /// The feature drain_filter is currently unstable. |
| pub fn drain_filter<T, F>(input: &mut Vec<T>, predicate: F) -> Vec<T> |
| where |
| F: Fn(&T) -> bool, |
| { |
| // Pass 1: compute the total number of removed elements. |
| let mut total_left_count = 0; |
| for element in input.iter() { |
| total_left_count += !predicate(element) as usize; |
| } |
| // Pass 2: compute the final position of each element in the input |
| // array in order to position left elements first and drained elements |
| // last, preserving the order. |
| let mut rank = Vec::with_capacity(input.len()); |
| let mut left_count = 0; |
| let mut removed_count = 0; |
| for element in input.iter() { |
| if predicate(element) { |
| rank.push(total_left_count + removed_count); |
| removed_count += 1; |
| } else { |
| rank.push(left_count); |
| left_count += 1; |
| } |
| } |
| // Pass 3: swap the elements to their final position. |
| let mut n = 0; |
| while n < input.len() { |
| let rank_n = rank[n]; |
| if n != rank_n { |
| input.swap(n, rank_n); |
| rank.swap(n, rank_n); |
| } else { |
| n += 1; |
| } |
| } |
| // Finally: split off the removed elements off the input vector. |
| input.split_off(total_left_count) |
| } |
| |
| #[cfg(test)] |
| mod test { |
| use crate::utils::drain_filter; |
| |
| #[test] |
| fn test_drain_filter() { |
| let mut input = vec![1, 4, 2, 5, 3, 6, 7]; |
| let drained = drain_filter(&mut input, |element| *element > 3); |
| assert_eq!(input, vec![1, 2, 3]); |
| assert_eq!(drained, vec![4, 5, 6, 7]); |
| } |
| } |