Minimizer.java

package org.eu.autogex.algorithms;

import java.util.*;
import java.util.ArrayDeque;
import org.eu.autogex.core.State;
import org.eu.autogex.models.DFA;

/** Utility class for DFA minimization. Implements Moore's partition refinement algorithm. */
public class Minimizer {

    private Minimizer() {
        throw new UnsupportedOperationException("Utility class cannot be instantiated");
    }

    /**
     * Minimizes a DFA, returning a new equivalent DFA with the minimum number of states.
     *
     * @param dfa The source DFA to minimize.
     * @return The minimal DFA.
     */
    public static DFA minimize(DFA dfa) {
        // 1. Remove unreachable states
        Set<State> reachableStates = getReachableStates(dfa);
        Set<Character> alphabet = getAlphabet(dfa);

        // 2. Initial partition (Finals vs Non-Finals)
        Set<Set<State>> partitions = createInitialPartitions(dfa, reachableStates);

        Map<State, Integer> stateToPartitionId = new HashMap<>();
        updateStateToPartitionMap(partitions, stateToPartitionId);

        // 3. Iterative partition refinement (until Fixed Point is reached)
        boolean changed = true;
        while (changed) {
            changed = false;
            Set<Set<State>> newPartitions = new HashSet<>();

            for (Set<State> group : partitions) {
                // Split the group based on behavior (transition destinations)
                Map<Map<Character, Integer>, Set<State>> subGroups =
                        splitGroup(dfa, group, alphabet, stateToPartitionId);

                newPartitions.addAll(subGroups.values());

                // If a group was split into 2 or more subgroups, the partition has changed
                if (subGroups.size() > 1) {
                    changed = true;
                }
            }
            partitions = newPartitions;

            if (changed) {
                updateStateToPartitionMap(partitions, stateToPartitionId);
            }
        }

        // 4. Rebuild the Minimized DFA
        return buildMinimalDfa(dfa, partitions, alphabet, stateToPartitionId);
    }

    private static void updateStateToPartitionMap(
            Set<Set<State>> partitions, Map<State, Integer> stateToPartitionId) {
        stateToPartitionId.clear();
        int partitionId = 0;
        for (Set<State> partition : partitions) {
            for (State state : partition) {
                stateToPartitionId.put(state, partitionId);
            }
            partitionId++;
        }
    }

    // --- Helper Methods ---

    private static Set<Set<State>> createInitialPartitions(DFA dfa, Set<State> reachableStates) {
        Set<State> finalGroup = new HashSet<>();
        Set<State> nonFinalGroup = new HashSet<>();

        for (State s : reachableStates) {
            if (dfa.getFinalStates().contains(s)) {
                finalGroup.add(s);
            } else {
                nonFinalGroup.add(s);
            }
        }

        Set<Set<State>> partitions = new HashSet<>();
        if (!finalGroup.isEmpty()) partitions.add(finalGroup);
        if (!nonFinalGroup.isEmpty()) partitions.add(nonFinalGroup);

        return partitions;
    }

    private static Map<Map<Character, Integer>, Set<State>> splitGroup(
            DFA dfa,
            Set<State> group,
            Set<Character> alphabet,
            Map<State, Integer> stateToPartitionId) {

        // Maps the behavioral "signature" of a state to the subgroup of states sharing it
        Map<Map<Character, Integer>, Set<State>> subGroups = new HashMap<>();

        for (State s : group) {
            // The signature is: "For each character, which partition do I end up in?"
            Map<Character, Integer> behaviorSignature = new HashMap<>();

            for (char symbol : alphabet) {
                State destination = getDestination(dfa, s, symbol);
                Integer targetPartitionId = stateToPartitionId.get(destination);
                behaviorSignature.put(symbol, targetPartitionId != null ? targetPartitionId : -1);
            }

            subGroups.computeIfAbsent(behaviorSignature, k -> new HashSet<>()).add(s);
        }

        return subGroups;
    }

    private static DFA buildMinimalDfa(
            DFA originalDfa,
            Set<Set<State>> partitions,
            Set<Character> alphabet,
            Map<State, Integer> stateToPartitionId) {
        DFA.Builder builder = new DFA.Builder();
        Map<Integer, String> partitionIdToName = new HashMap<>();

        // Register new states
        for (Set<State> partition : partitions) {
            State representative = partition.iterator().next();
            int partId = stateToPartitionId.get(representative);
            String name = "M" + partId;
            partitionIdToName.put(partId, name);

            // The partition is final if it contains at least one original final state.
            boolean isFinal = !Collections.disjoint(partition, originalDfa.getFinalStates());
            builder.addState(name, isFinal);

            // The partition is initial if it contains the original initial state
            if (partition.contains(originalDfa.getInitialState())) {
                builder.setInitialState(name);
            }
        }

        // Create transitions (taking a "representative" element for each partition is sufficient)
        for (Set<State> partition : partitions) {
            State representative = partition.iterator().next();
            int partId = stateToPartitionId.get(representative);
            String currentName = partitionIdToName.get(partId);

            for (char symbol : alphabet) {
                State dest = getDestination(originalDfa, representative, symbol);
                Integer targetPartitionId = stateToPartitionId.get(dest);

                // Link the transition if valid
                if (targetPartitionId != null) {
                    builder.addTransition(
                            currentName, symbol, partitionIdToName.get(targetPartitionId));
                }
            }
        }

        return builder.build();
    }

    private static Set<State> getReachableStates(DFA dfa) {
        Set<State> reachable = new HashSet<>();
        // ArrayDeque is preferred over LinkedList for queues in hot paths.
        // It provides better cache locality and avoids O(n) node allocation overhead.
        Queue<State> queue = new ArrayDeque<>();

        reachable.add(dfa.getInitialState());
        queue.add(dfa.getInitialState());

        while (!queue.isEmpty()) {
            State current = queue.poll();
            Map<Character, State> transitions = dfa.getTransitionTable().get(current);

            if (transitions != null) {
                for (State nextState : transitions.values()) {
                    if (reachable.add(nextState)) {
                        queue.add(nextState);
                    }
                }
            }
        }
        return reachable;
    }

    private static State getDestination(DFA dfa, State source, char symbol) {
        Map<Character, State> transitions = dfa.getTransitionTable().get(source);
        return transitions != null ? transitions.get(symbol) : null;
    }

    private static Set<Character> getAlphabet(DFA dfa) {
        Set<Character> alphabet = new HashSet<>();
        for (Map<Character, State> transitions : dfa.getTransitionTable().values()) {
            alphabet.addAll(transitions.keySet());
        }
        return alphabet;
    }
}