fact: Fixpoint piecewise_uniform_alloc_helper {T} {HDA : has_double_avg T} (size : T -> Q) (allocation_per_subdivision : Q) (min_point_count : N) (max_point_count_per_subdivision : N) (surplus_allocation : Q) (extra_unallocated_points : N) (st : @surplus_state T) (subdivisions : list (T * T)) : list ((T * T ) * N) := match subdivisions, st with | [], _ => [] | (min, max) :: rest, surplus | (min, _):: rest, deficit max => let max_sz := size max in let cur_allocation := allocation_per_subdivision + surplus_allocation in let cur_unallocated_points := (max_point_count_per_subdivision + extra_unallocated_points)%N in let '(cur_alloc, st, surplus_allocation, extra_unallocated_points) := if Qle_bool cur_allocation (min_point_count * max_sz) then ([], deficit max, cur_allocation, cur_unallocated_points) else let n_points := N.min cur_unallocated_points (Z.to_N (Qfloor (cur_allocation / max_sz))) in ([((min, max), n_points)], surplus, cur_allocation - n_points * max_sz, (extra_unallocated_points - n_points)%N) in cur_alloc ++ (piecewise_uniform_alloc_helper size allocation_per_subdivision min_point_count max_point_count_per_subdivision surplus_allocation extra_unallocated_points st rest) end.
imports: Coq.Strings.String Coq.Structures.Orders Coq.micromega.Lia Coq.Bool.Bool Coq.Sorting.Mergesort Coq.QArith.QArith Coq.QArith.Qround Coq.QArith.Qabs Coq.QArith.Qminmax Coq.NArith.NArith Coq.ZArith.ZArith Coq.Arith.Arith Coq.Lists.List PerformanceExperiments.LetIn