moonbitlang / core / 1457

92%

Build Type

push

github

Committed by bobzhang

Commit Message

refactor(immut/sorted_map): Replace array-based iterator with continuation-based design

Apply the same continuation-based iterator pattern used in SortedSet to
SortedMap for consistency and improved design.

Key improvements:
- Memory efficiency: Continuation tree replaces mutable array stack
- Functional design: Iterator wraps a closure (() -> (K, V)?) for composability
- Cleaner implementation: Eliminates explicit stack management methods
- Same performance: Both are O(n) traversal with O(log n) space in average case

Implementation details:
- Iterator[K, V]: Wraps a stateful closure that yields the next (key, value) pair
- Tree[K, V]: Continuation structure encoding remaining traversal state
  - Leaf: No more elements to process
  - More(left, right, key, value): Process left, yield (key, value), then right
- into_iterator(): Creates closure with mutable state (next, cont) captured
- Uses for-loop with pattern matching for elegant in-order traversal

Changes to traits_impl.mbt:
- Updated Eq implementation to use into_iterator() with while-loop pattern
- Updated Compare implementation to use into_iterator() with while-loop pattern
- Both now use modern pattern matching style (guard...else, break)
- Maintains size-first comparison optimization

Testing:
- Enhanced test to verify all elements in sequence
- Added check for proper iterator exhaustion
- All 5634 tests pass successfully

File changes:
- Renamed: inorder_iterator.mbt -> external_iterator.mbt
- Updated: traits_impl.mbt to use new iterator API

No API changes - this is an internal implementation refactoring only.

Run Details

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

2 existing lines in 1 file now uncovered.

9261 of 10383 relevant lines covered (89.19%)

193885.79 hits per line