fact: Fixpoint extra_alloc_at_bottom (extra_points_remaining : N) (min max : Z) (sparse_points dense_points : list (Z * Z)) (cur_n : nat) (fuel : nat) : list (Z * Z) := if ((extra_points_remaining =? 0)%N || (max <? min)) then dense_points ++ sparse_points else let '(removed_points, sparse_points) := List.partition (fun '(n, m) => (n =? cur_n)) sparse_points in let extra_points_remaining := (extra_points_remaining + List.length removed_points)%N in let new_points := allocate_points_for extra_points_remaining min max cur_n in let extra_points_remaining := (extra_points_remaining - List.length new_points)%N in let dense_points := dense_points ++ new_points in match fuel with | O => dense_points ++ sparse_points | S fuel => extra_alloc_at_bottom extra_points_remaining min max sparse_points dense_points (S cur_n) fuel end.
imports: Coq.micromega.Lia Coq.ZArith.ZArith Coq.QArith.QArith Coq.Classes.Morphisms Coq.Setoids.Setoid Coq.Lists.List PerformanceExperiments.Harness