Function assign_items_weighted_with_scale_fn

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,

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

1. 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.

2. 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.

3. 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.