moonbitlang / core / 1459

92%

push

github

refactor(sorted_set, sorted_map): Add continuation-based iterators for mutable collections

Apply the same continuation-based iterator pattern to the mutable sorted_set
and sorted_map packages for consistency with their immutable counterparts.

Key improvements:
- Memory efficiency: Continuation tree replaces array allocation in to_array()
- Better performance: Eq comparison can short-circuit on first mismatch
- Functional design: Closure-based iterators for better composability
- Consistency: Same pattern across all four packages (immut/sorted_set,
  immut/sorted_map, sorted_set, sorted_map)

Implementation details:
- Iterator[V] / Iterator[K, V]: Wraps a stateful closure
- Tree continuation structure encodes traversal state:
  - Leaf: No more elements
  - More(left, right, value/key, value): Process left, yield, then right
- Handles mutable Node structure (Node[V]? instead of SortedSet[V])
- Uses for-loop with pattern matching for in-order traversal

Changes to Eq implementations:
- sorted_set: Changed from to_array() comparison to iterator-based
- sorted_map: Changed from to_array() comparison to iterator-based
- Both now support early exit on size mismatch
- Both short-circuit on first element mismatch

Performance benefits:
- to_array() allocates O(n) memory and always traverses entire tree
- Iterator-based comparison:
  - No allocation needed
  - Short-circuits on first difference
  - Best case O(1), average case O(n) but with early exit

Testing:
- Enhanced tests verify all elements in sequence
- Added exhaustion checks
- All 5636 tests pass for both packages

Files added:
- sorted_set/external_iterator.mbt
- sorted_map/external_iterator.mbt

Files modified:
- sorted_set/set.mbt (Eq implementation)
- sorted_map/map.mbt (Eq implementation)

No API changes - this is an internal implementation improvement.

26 of 26 new or added lines in 4 files covered. (100.0%)

9285 of 10407 relevant lines covered (89.22%)

193438.81 hits per line