moonbitlang / core / 6912

89%

push

github

feat(sorted_map): add ordered navigation and reverse iteration (#4333)

* feat(sorted_map): add ordered navigation and @cmp.Bound

Add the ordered-map operations that callers otherwise rebuild by hand:

- first/last and pop_first/pop_last
- nearest-key queries first_ge/first_gt/last_le/last_lt
- range_bounds/rev_range_bounds with @cmp.Bound ends (Included,
  Excluded, Unbounded), so bound kinds can be chosen at runtime
- reverse iteration: rev_iter, rev_keys, rev_values, rev_range

All additions are lazy or O(log n) and leave existing APIs unchanged.
Tests compare every operation against a sorted-array model over all
bound combinations, check AVL invariants after pops, and add quickcheck
properties. The README documents the new API and how to get custom or
runtime-chosen key order with a key type that carries its ordering.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

* fix(sorted_map): check range bounds with Compare::compare

Bound checks used the relational operators, which disagree with
Compare::compare for NaN in Double keys. range_bounds and rev_range
could then return different entries than range for the same bounds.
Use compare, the ordering range, get and the nearest-key queries use,
and add a regression test comparing both with range for NaN bounds.

Found by Codex CLI review.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

* refactor(sorted_map): separate bounded ranges from navigation

* docs(sorted_map): keep navigation examples separate from ranges

* feat(sorted_map): add rev_iter2 and clarify key ordering

---------

Co-authored-by: Claude Opus 5.5 <noreply@anthropic.com>

59 of 59 new or added lines in 1 file covered. (100.0%)

16757 of 18728 relevant lines covered (89.48%)

335385.24 hits per line