aw080/main/ooxml/source/framework/SchemaParser/src/org/apache/openoffice/ooxml/schema/automaton/HopcroftMinimizer.java

/**************************************************************
*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*
*************************************************************/

package org.apache.openoffice.ooxml.schema.automaton;

import java.io.PrintStream;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Vector;

import org.apache.openoffice.ooxml.schema.model.attribute.Attribute;
import org.apache.openoffice.ooxml.schema.model.base.Location;
import org.apache.openoffice.ooxml.schema.model.base.QualifiedName;

/** Minimize an DFA with respect to its number of states.
 *  This is most important for the use of the 'all' element in the OOXML 
 *  specification which leads to a lot of additional states and transitions.
 */
public class HopcroftMinimizer
{
    /** Create a DFA that is equivalent to a given DFA but has the minimal
     *  number of states.
     */
    public static FiniteAutomaton MinimizeDFA (
        final StateContainer aNewStateContainer,
        final StateContext aOriginalStates,
        final Vector<Attribute> aAttributes,
        final Location aLocation,
        final PrintStream aLog)
    {
        if (aLog != null)
        {
            aLog.printf("minimizing %d states and %d transitions\n",
                aOriginalStates.GetStateCount(),
                aOriginalStates.GetTransitionCount());
            DisplayStates(aOriginalStates, aLog);
        }
        
        TreeSet<StateSet> aT = new TreeSet<>();
        TreeSet<StateSet> aP = new TreeSet<>();
        Map<State,StateSet> aTMap = new HashMap<>();
        Map<State,StateSet> aPMap = new HashMap<>();
        InitializeMap(aT, aTMap, aOriginalStates.GetStates());

        // Split partitions until there is nothing else to do.
        while ( ! AreSetsOfStateSetsEqual(aP, aT))
        {
            if (aLog != null)
                aLog.printf("T has %d members\n", aT.size());

            aP = aT;
            aPMap = aTMap;
            aT = new TreeSet<>();
            aTMap = new HashMap<>();
            
            for (final StateSet aSet : aP)
            {
                final Iterable<StateSet> aParts = Split(aSet, aP, aPMap);
                if (aParts == null)
                {
                    // No split necessary.
                    assert( ! aSet.IsEmpty());
                    aT.add(aSet);
                    for (final State aState : aSet.GetStates())
                        aTMap.put(aState, aSet);
                }
                else
                {
                    for (final StateSet aPart : aParts)
                    {
                        assert( ! aPart.IsEmpty());
                        aT.add(aPart);
                    
                        for (final State aState : aPart.GetStates())
                            aTMap.put(aState, aPart);
                    }
                }
            }
        }
        
        // Create new states.
        final StateContext aMinimizedStates = CreateNewStates(
            aP,
            aPMap,
            aNewStateContainer,
            aOriginalStates);

        if (aLog != null)
        {
            aLog.printf("to %d states and %d transitions\n",
                aMinimizedStates.GetStateCount(),
                aMinimizedStates.GetTransitionCount());
            DisplayStates(aMinimizedStates, aLog);
            for (final StateSet aSet : aT)
                aLog.printf("    %s\n", aSet.toString());
        }

        // Create and return the new minimized automaton.
        return new FiniteAutomaton(
            aMinimizedStates,
            aAttributes,
            aLocation);
    }


    

    /** We start with two sets.  One contains all start states (in our case
    *   just one), the other contains all other states.
    */
    private static void InitializeMap (
        final Set<StateSet> aSet,
        final Map<State,StateSet> aMap,
        final Iterable<State> aStates)
    {
        final StateSet aAcceptingStates = new StateSet();
        final StateSet aNonAcceptingStates = new StateSet();
        for (final State aState : aStates)
        {
            if (aState.IsAccepting())
            {
                aAcceptingStates.AddState(aState);
                aMap.put(aState, aAcceptingStates);
            }
            else
            {
                aNonAcceptingStates.AddState(aState);
                aMap.put(aState, aNonAcceptingStates);
            }
        }
        if (aAcceptingStates.IsEmpty())
            throw new RuntimeException("there should be at least one accepting state");
        aSet.add(aAcceptingStates);
        if ( ! aNonAcceptingStates.IsEmpty())
            aSet.add(aNonAcceptingStates);
    }
    
    
    
    
    private static Iterable<StateSet> Split (
        final StateSet aSet,
        final Set<StateSet> aT,
        final Map<State,StateSet> aTMap)
    {
        if (aSet.GetStateCount() == 1)
            return null;

        final Set<QualifiedName> aElements = CollectElementNames(aSet);
        for (final QualifiedName aElementName : aElements)
        {
            final Collection<StateSet> aPartitions = Split(aSet, aT, aTMap, aElementName);
            if (aPartitions == null)
                continue;
            if (aPartitions.size() > 1)
                return aPartitions;
        }
        return null;
    }
    
    
    

    /** Create a partition of the given set of states according to their
     *  transitions.
     *  All states whose transitions point to the same state set go in the same
     *  partition.
     */
    private static Collection<StateSet> Split (
        final StateSet aSet,
        final Set<StateSet> aT,
        final Map<State,StateSet> aTMap,
        final QualifiedName aElementName)
    {
        // Set up a forward map that does two steps:
        // from s via transition regarding aElementName to s'
        // from s' to a state set under aTMap(s).
        final Map<State,StateSet> aForwardMap = new HashMap<>();
        for (final State aState : aSet.GetStates())
        {
            final Transition aTransition = GetTransition(aState, aElementName);
            if (aTransition == null)
                aForwardMap.put(aState, null);
            else
                aForwardMap.put(aState, aTMap.get(aTransition.GetEndState()));
        }
        
        // Create the partion of aSet according to aForwardMap.  All states that map
        // to the same element go into the same state set.
        if (aForwardMap.size() == 1)
        {
            // No split necessary.
            return null;
        }
        else
        {
            // Set up a reverse map that maps that maps the values in aForwardMap to
            // new state sets whose contents are the keys in aForwardMap.
            final Map<StateSet,StateSet> aReverseMap = new HashMap<>();
            for (final Entry<State,StateSet> aEntry : aForwardMap.entrySet())
            {
                StateSet aPartitionSet = aReverseMap.get(aEntry.getValue());
                if (aPartitionSet == null)
                {
                    aPartitionSet = new StateSet();
                    aReverseMap.put(aEntry.getValue(), aPartitionSet);
                }
                aPartitionSet.AddState(aEntry.getKey());
            }
            return aReverseMap.values();
        }
    }
    
    
    
    
    private static Transition GetTransition (
        final State aState,
        final QualifiedName aElementName)
    {
        Transition aTransition = null;
        for (final Transition aCandidate : aState.GetTransitions())
            if (aCandidate.GetElementName().compareTo(aElementName) == 0)
            {
                assert(aTransition==null);
                aTransition = aCandidate;
                // break;
            }
        return aTransition;
    }
    
    
    
    
    private static Set<QualifiedName> CollectElementNames (final StateSet aSet)
    {
        final Set<QualifiedName> aNames = new TreeSet<>();
        for (final State aState : aSet.GetStates())
            for (final Transition aTransition : aState.GetTransitions())
                aNames.add(aTransition.GetElementName());
        
        return aNames;
    }
    
    
    
    
    private static boolean AreSetsOfStateSetsEqual (
        final TreeSet<StateSet> aSetOfSetsA,
        final TreeSet<StateSet> aSetOfSetsB)
    {
        if (aSetOfSetsA.size() != aSetOfSetsB.size())
            return false;
        else
        {
            final Iterator<StateSet> aSetIteratorA = aSetOfSetsA.iterator();
            final Iterator<StateSet> aSetIteratorB = aSetOfSetsB.iterator();
            while (aSetIteratorA.hasNext() && aSetIteratorB.hasNext())
            {
                if (aSetIteratorA.next().compareTo(aSetIteratorB.next()) != 0)
                    return false;
            }
            return true;
        }
    }

    
    

    private static StateContext CreateNewStates (
        final TreeSet<StateSet> aP,
        final Map<State,StateSet> aPMap,
        final StateContainer aNewStateContainer,
        final StateContext aOriginalStates)
    {
        final StateContext aMinimizedStates = new StateContext(
            aNewStateContainer,
            aOriginalStates.GetStartState().GetFullname());
        
        // Create the new states.
        final Map<State,State> aOldStateToNewStateMap = new TreeMap<>();
        for (final StateSet aSet : aP)
        {
            State aNewState = null;
            for (final State aOldState : aSet.GetStates())
            {
                if (aNewState == null)
                    aNewState = aOldState.Clone(aMinimizedStates);
                aOldStateToNewStateMap.put(aOldState, aNewState);
            }
        }
        
        // Create the new transitions.
        for (final StateSet aSet : aP)
        {
            final State aOldStartState = aSet.GetStates().iterator().next();
            final State aNewStartState = aOldStateToNewStateMap.get(aOldStartState);
            
            for (final Transition aTransition : aOldStartState.GetTransitions())
            {
                final State aOldEndState = aTransition.GetEndState();
                final State aNewEndState = aOldStateToNewStateMap.get(aOldEndState);

                // Check if the transition already exists.
                if (HasTransition(aNewStartState, aTransition.GetElementName()))
                    continue;
                        
                aNewStartState.AddTransition(
                    new Transition(
                        aNewStartState,
                        aNewEndState,
                        aTransition.GetElementName(),
                        aTransition.GetElementTypeName()));               
            }
        }
        
        // Transfer skip data and accepting flags.
        for (final State aOldState : aOriginalStates.GetStates())
        {
            final State aNewState = aOldStateToNewStateMap.get(aOldState);
            aNewState.CopyFrom(aOldState);
        }
        return aMinimizedStates;
    }

    
    

    private static boolean HasTransition (
        final State aState,
        final QualifiedName aElementName)
    {
        for (final Transition aTransition : aState.GetTransitions())
            if (aTransition.GetElementName().compareTo(aElementName) == 0)
                return true;
        return false;
    }
    
    
    
    
    private static void DisplayStates (
        final StateContext aStates,
        final PrintStream aLog)
    {
        for (final State aState : aStates.GetStates())
        {
            aLog.printf("  %s %s\n", aState.GetFullname(),
                aState.IsAccepting() ? "is accepting" : ""); 
            for (final Transition aTransition : aState.GetTransitions())
                aLog.printf("    -> %s via %s\n", 
                    aTransition.GetEndState().GetFullname(),
                    aTransition.GetElementName().GetStateName());
        }
    }
}