Skip to main content

tuwunel_core/utils/
budget.rs

1//! Size budgets over ordered items.
2//!
3//! A budget keeps each item that still fits within a limit together with the
4//! items kept before it, without reordering anything, so the same items always
5//! yield the same selection.
6
7/// Marks each item, in order, `Ok` while its size fits within `limit` together
8/// with the items kept before it, and `Err` otherwise.
9///
10/// An item that does not fit is skipped rather than ending the walk, so a later
11/// smaller item may still be kept. The selection depends only on the sizes and
12/// their order.
13pub fn budget<Item, Iter, Size>(
14	items: Iter,
15	limit: usize,
16	size: Size,
17) -> impl Iterator<Item = Result<Item, Item>>
18where
19	Iter: IntoIterator<Item = Item>,
20	Size: Fn(&Item) -> usize,
21{
22	items
23		.into_iter()
24		.scan(0_usize, move |total, item| {
25			let next = total.saturating_add(size(&item));
26			let fits = next <= limit;
27
28			if fits {
29				*total = next;
30			}
31
32			Some(if fits { Ok(item) } else { Err(item) })
33		})
34}