From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- third_party/rust/itertools/src/k_smallest.rs | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) create mode 100644 third_party/rust/itertools/src/k_smallest.rs (limited to 'third_party/rust/itertools/src/k_smallest.rs') diff --git a/third_party/rust/itertools/src/k_smallest.rs b/third_party/rust/itertools/src/k_smallest.rs new file mode 100644 index 0000000000..acaea5941c --- /dev/null +++ b/third_party/rust/itertools/src/k_smallest.rs @@ -0,0 +1,20 @@ +use alloc::collections::BinaryHeap; +use core::cmp::Ord; + +pub(crate) fn k_smallest>(mut iter: I, k: usize) -> BinaryHeap { + if k == 0 { return BinaryHeap::new(); } + + let mut heap = iter.by_ref().take(k).collect::>(); + + iter.for_each(|i| { + debug_assert_eq!(heap.len(), k); + // Equivalent to heap.push(min(i, heap.pop())) but more efficient. + // This should be done with a single `.peek_mut().unwrap()` but + // `PeekMut` sifts-down unconditionally on Rust 1.46.0 and prior. + if *heap.peek().unwrap() > i { + *heap.peek_mut().unwrap() = i; + } + }); + + heap +} -- cgit v1.2.3