moonbitlang / core / 7874

88%

push

github

fix(immut): use Data.Map's (3, 2) weight-balance parameters

The immutable sorted_map and sorted_set used (delta, gamma) = (5, ~1), which is
not a valid weight-balance pair: one remove could leave a node with subtree
sizes (0, 2), and sequential builds reached height 33 for 50 000 elements.
Switch both to the size-based (3, 2) form Haskell's Data.Map/Data.Set use:
rotate when one side's size > 3 x the other's, and single-rotate iff the
inner grandchild's size < 2 x the outer's. Height for 50 000 ascending adds
drops to 21.

Part of #4612 (P2-31)

Codex verdict: "No blocking correctness, API-policy, or documentation issues found."

Signed-off-by: Codex CLI <codex@openai.com>

12 of 12 new or added lines in 2 files covered. (100.0%)

25126 of 28414 relevant lines covered (88.43%)

418586.84 hits per line