Skip to main content

group_aware_fill

Function group_aware_fill 

Source
pub fn group_aware_fill<R>(
    items: impl Iterator<Item = R>,
    quotas: &BTreeMap<BucketKey, usize>,
    seed: u64,
    bucket_key_fn: impl Fn(&R) -> BucketKey,
    group_key_fn: impl Fn(&R) -> GroupKey,
) -> GroupAwareFillResult<R>
Expand description

Group-aware bounded-heap quota fill: streams items once, assigns each a bucket via bucket_key_fn, and – among items whose bucket has a quota in quotas – fills that bucket’s quota preferring group diversity (group_key_fn) over first-come-first-served.

Algorithm: a pre-tally of (bucket, group) -> how many already seen gives each item a rank (its group’s Nth occurrence in that bucket, 0-indexed); the item is then pushed onto that bucket’s bounded top-quota heap keyed on (rank, seeded_hash(seed, group)). Lower rank always wins, so every group’s first occurrence in a bucket outranks every group’s second occurrence, across all groups – one group can never consume a whole bucket’s quota while a second group present in it is starved out. The hash only breaks ties within one rank value.