diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-06-19 09:26:03 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-06-19 09:26:03 +0000 |
commit | 9918693037dce8aa4bb6f08741b6812923486c18 (patch) | |
tree | 21d2b40bec7e6a7ea664acee056eb3d08e15a1cf /vendor/itertools-0.11.0/src/k_smallest.rs | |
parent | Releasing progress-linux version 1.75.0+dfsg1-5~progress7.99u1. (diff) | |
download | rustc-9918693037dce8aa4bb6f08741b6812923486c18.tar.xz rustc-9918693037dce8aa4bb6f08741b6812923486c18.zip |
Merging upstream version 1.76.0+dfsg1.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'vendor/itertools-0.11.0/src/k_smallest.rs')
-rw-r--r-- | vendor/itertools-0.11.0/src/k_smallest.rs | 20 |
1 files changed, 20 insertions, 0 deletions
diff --git a/vendor/itertools-0.11.0/src/k_smallest.rs b/vendor/itertools-0.11.0/src/k_smallest.rs new file mode 100644 index 000000000..acaea5941 --- /dev/null +++ b/vendor/itertools-0.11.0/src/k_smallest.rs @@ -0,0 +1,20 @@ +use alloc::collections::BinaryHeap; +use core::cmp::Ord; + +pub(crate) fn k_smallest<T: Ord, I: Iterator<Item = T>>(mut iter: I, k: usize) -> BinaryHeap<T> { + if k == 0 { return BinaryHeap::new(); } + + let mut heap = iter.by_ref().take(k).collect::<BinaryHeap<_>>(); + + 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 +} |