[LUCENE-9125] Improve Automaton.step() with binary search and introduce Automaton.next()

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 8.5
• Lucene Fields: New
• Assignee: Bruno Roustant
• Reporter: Bruno Roustant
• Created: 10/Jan/20 14:21
• Updated: 28/Aug/22 15:55
• Resolved: 13/Jan/20 10:39

Description

Implement the existing todo in Automaton.step() (lookup a transition from a source state depending on a given label) to use binary search since the transitions are sorted.

Introduce new method Automaton.next() to optimize iteration & lookup over all the transitions of a state. This will be used in RunAutomaton constructor and in MinimizationOperations.minimize().

Issue Links

• links to: GitHub Pull Request #1160