Function assign_items_weighted_with_scale_fn

Source

pub fn assign_items_weighted_with_scale_fn<C, I, S>(
    containers: &BTreeMap<C, NonZeroUsize>,
    items: &[I],
    salt: S,
    capacity_scale_factor_fn: impl Fn(&BTreeMap<C, NonZeroUsize>, &[I]) -> Option<ScaleFactor>,
) -> BTreeMap<C, Vec<I>>where
    C: Ord + Hash + Eq + Clone + Debug,
    I: Hash + Eq + Copy + Clone + Debug,
    S: Hash + Copy,

Expand description

Assign items to weighted containers with optional capacity scaling and deterministic tie-breaking.

Distributes a slice of items (&[I]) across a set of containers (BTreeMap<C, NonZeroUsize>) using a three-phase algorithm:

§Type Parameters

C: Container identifier. Must implement Ord + Hash + Eq + Clone + Debug.
I: Item type. Must implement Hash + Eq + Copy + Debug.
S: Salt type for tie-breaking. Must implement Hash + Copy.

§Parameters

containers: Map of containers to their non-zero weights (BTreeMap<C, NonZeroUsize>).
items: Slice of items (&[I]) to distribute.
salt: A salt value to vary deterministic tie-breaks between equal remainders.
capacity_scale_factor_fn: Callback (containers, items) -> Option<ScaleFactor>:
- Some(f): Scale each container’s base quota by f (ceiled, but never below base).
- None: Remove upper bound (capacity = usize::MAX).

§Returns

A BTreeMap<C, Vec<I>> mapping each container to the list of assigned items.

If either containers or items is empty, return an empty map.

§Panics

If the sum of all container weights is zero.
If, during weighted rendezvous, no eligible container remains (invariant violation).

§Complexity

Runs in O(N · M) time, where N = containers.len() and M = items.len(). Each item is compared against all containers via a weighted rendezvous hash.

§Example


let mut caps = BTreeMap::new();
caps.insert("fast", NonZeroUsize::new(3).unwrap());
caps.insert("slow", NonZeroUsize::new(1).unwrap());

let tasks = vec!["task1", "task2", "task3", "task4"];
let result = assign_items_weighted_with_scale_fn(&caps, &tasks, 0u8, weighted_scale);

// `fast` should receive roughly 3 tasks, `slow` roughly 1
assert_eq!(result.values().map(Vec::len).sum::<usize>(), tasks.len());

§Algorithm

Quota Calculation
- Compute total_weight = sum(w_i) as u128.
- For each container i with weight w_i:
```
ideal_i     = M * w_i
base_quota_i = floor(ideal_i / total_weight)
rem_i        = ideal_i % total_weight
```
- Let rem_count = M - sum(base_quota_i) and sort containers by rem_i (desc), breaking ties by stable_hash((container, salt)).
- Give +1 slot to the first rem_count containers.
Capacity Scaling
- If Some(f): For each container, quota_i = max(base_quota_i, ceil(base_quota_i as f64 * f)).
- If None: Set quota_i = usize::MAX.
Weighted Rendezvous Assignment
- For each item x, compute for each container i:
```
h = stable_hash((x, i, salt))
r = (h + 1) / (MAX_HASH + 2)       // 0 < r ≤ 1
key_i = -ln(r) / weight_i
```
- Assign x to the container with the smallest key_i.

Function assign_items_weighted_with_scale_fnCopy item path