// Path: src/com/nobigsoftware/util/BuilderCache.java
// public interface BuilderCache
// {
//     /**
//      * Get a cached item.
//      * 
//      * @param key  The key used to identify the item.  The key uniquely identifies all
//      *  of the source information that will go into building the item if this call fails
//      *  to retrieve a cached version.  Typically this will be a cryptographic hash of
//      *  the serialized form of that information.
//      * 
//      * @return  the item that was previously cached under the key, or null if no such item
//      *  can be retrieved.
//      */
//     Serializable getCachedItem(String key);
//     
//     /**
//      * This method may be called when an item is built, providing an opportunity to
//      * cache it.
//      * 
//      * @param key   The key that will be used to identify the item in future calls to {@link #getCachedItem(String)}.
//      *      Only letters, digits, and underscores are valid in keys, and key length is limited to 32 characters.
//      *      The behaviour of this method for invalid keys is undefined.
//      *      <P>
//      *      Keys that differ only by case may or may not be considered equal by this class.
//      * @param item  The item to cache, if desired
//      */
//     void maybeCacheItem(String key, Serializable item);
// }
// 
// Path: src/com/nobigsoftware/util/SHAOutputStream.java
// public class SHAOutputStream extends DigestOutputStream
// {
//     private static NullOutputStream NULL_OUTPUT_STREAM = new NullOutputStream();
//     private static char[] DIGITS_36 = "0123456789abcdefghijklmnopqrstuvwxyz".toCharArray(); 
//     
//     public SHAOutputStream()
//     {
//         super(NULL_OUTPUT_STREAM, _initDigest());
//     }
//     
//     /**
//      * @return a base-32 version of the digest, consisting of 32 letters and digits
//      */
//     public String getBase32Digest()
//     {
//         StringBuilder sb = new StringBuilder();
//         int bits = 0, nbits = 0;
//         for (byte b : getMessageDigest().digest())
//         {
//             bits |= (((int)b)&255)<<nbits;
//             nbits+=8;
//             while(nbits >= 5)
//             {
//                 sb.append(DIGITS_36[bits&31]);
//                 bits>>>=5;
//                 nbits-=5;
//             }
//         }
//         return sb.toString();
//     }
// 
//     private static class NullOutputStream extends OutputStream
//     {
//         @Override
//         public void close() throws IOException
//         {
//         }
//         @Override
//         public void flush() throws IOException
//         {
//         }
//         @Override
//         public void write(byte[] arg0, int arg1, int arg2) throws IOException
//         {
//         }
//         @Override
//         public void write(byte[] arg0) throws IOException
//         {
//         }
//         @Override
//         public void write(int arg0) throws IOException
//         {
//         }
//     }
//     private static MessageDigest _initDigest()
//     {
//         try
//         {
//             return MessageDigest.getInstance("SHA-1");
//         }
//         catch(NoSuchAlgorithmException e)
//         {
//             throw new RuntimeException("JRE is broken - it's supposed to support SHA-1, but does not");
//         }
//     }
// }


import java.io.IOException;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import com.nobigsoftware.util.BuilderCache;
import com.nobigsoftware.util.SHAOutputStream;

    }
    
    /**
     * Build DFAs from a provided NFA
     * <P>
     * This method is used when you want to build the NFA yourself instead of letting
     * this class do it.
     * <P>
     * Languages built simultaneously will be globally minimized and will share as many states as possible.
     * 
     * @param nfa           The NFA
     * @param nfaStartStates     The return value will include the DFA states corresponding to these NFA states, in the same order
     * @param ambiguityResolver     When patterns for multiple results match the same string, this is called to
     *                              combine the multiple results into one.  If this is null, then a DfaAmbiguityException
     *                              will be thrown in that case.
     * @param cache If this cache is non-null, it will be checked for a memoized result for this NFA, and will be populated
     *      with a memoized result when the call is complete.
     * @return DFA start states that are equivalent to the given NFA start states.  This will have the same length as nfaStartStates, with
     *         corresponding start states in corresponding positions.
     */
    @SuppressWarnings("unchecked")
    public static <MR> List<DfaState<MR>> buildFromNfa(Nfa<MR> nfa, int[] nfaStartStates, DfaAmbiguityResolver<? super MR> ambiguityResolver, BuilderCache cache )
    {
        String cacheKey = null;
        SerializableDfa<MR> serializableDfa = null;
        if (cache != null)
        {
            try
            {
                //generate the cache key by serializing key info into an SHA hash

// Path: src/com/nobigsoftware/util/BuilderCache.java
// public interface BuilderCache
// {
//     /**
//      * Get a cached item.
//      * 
//      * @param key  The key used to identify the item.  The key uniquely identifies all
//      *  of the source information that will go into building the item if this call fails
//      *  to retrieve a cached version.  Typically this will be a cryptographic hash of
//      *  the serialized form of that information.
//      * 
//      * @return  the item that was previously cached under the key, or null if no such item
//      *  can be retrieved.
//      */
//     Serializable getCachedItem(String key);
//     
//     /**
//      * This method may be called when an item is built, providing an opportunity to
//      * cache it.
//      * 
//      * @param key   The key that will be used to identify the item in future calls to {@link #getCachedItem(String)}.
//      *      Only letters, digits, and underscores are valid in keys, and key length is limited to 32 characters.
//      *      The behaviour of this method for invalid keys is undefined.
//      *      <P>
//      *      Keys that differ only by case may or may not be considered equal by this class.
//      * @param item  The item to cache, if desired
//      */
//     void maybeCacheItem(String key, Serializable item);
// }
// 
// Path: src/com/nobigsoftware/util/SHAOutputStream.java
// public class SHAOutputStream extends DigestOutputStream
// {
//     private static NullOutputStream NULL_OUTPUT_STREAM = new NullOutputStream();
//     private static char[] DIGITS_36 = "0123456789abcdefghijklmnopqrstuvwxyz".toCharArray(); 
//     
//     public SHAOutputStream()
//     {
//         super(NULL_OUTPUT_STREAM, _initDigest());
//     }
//     
//     /**
//      * @return a base-32 version of the digest, consisting of 32 letters and digits
//      */
//     public String getBase32Digest()
//     {
//         StringBuilder sb = new StringBuilder();
//         int bits = 0, nbits = 0;
//         for (byte b : getMessageDigest().digest())
//         {
//             bits |= (((int)b)&255)<<nbits;
//             nbits+=8;
//             while(nbits >= 5)
//             {
//                 sb.append(DIGITS_36[bits&31]);
//                 bits>>>=5;
//                 nbits-=5;
//             }
//         }
//         return sb.toString();
//     }
// 
//     private static class NullOutputStream extends OutputStream
//     {
//         @Override
//         public void close() throws IOException
//         {
//         }
//         @Override
//         public void flush() throws IOException
//         {
//         }
//         @Override
//         public void write(byte[] arg0, int arg1, int arg2) throws IOException
//         {
//         }
//         @Override
//         public void write(byte[] arg0) throws IOException
//         {
//         }
//         @Override
//         public void write(int arg0) throws IOException
//         {
//         }
//     }
//     private static MessageDigest _initDigest()
//     {
//         try
//         {
//             return MessageDigest.getInstance("SHA-1");
//         }
//         catch(NoSuchAlgorithmException e)
//         {
//             throw new RuntimeException("JRE is broken - it's supposed to support SHA-1, but does not");
//         }
//     }
// }


// Path: src/com/nobigsoftware/dfalex/DfaBuilder.java
import java.io.IOException;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import com.nobigsoftware.util.BuilderCache;
import com.nobigsoftware.util.SHAOutputStream;

    }
    
    /**
     * Build DFAs from a provided NFA
     * <P>
     * This method is used when you want to build the NFA yourself instead of letting
     * this class do it.
     * <P>
     * Languages built simultaneously will be globally minimized and will share as many states as possible.
     * 
     * @param nfa           The NFA
     * @param nfaStartStates     The return value will include the DFA states corresponding to these NFA states, in the same order
     * @param ambiguityResolver     When patterns for multiple results match the same string, this is called to
     *                              combine the multiple results into one.  If this is null, then a DfaAmbiguityException
     *                              will be thrown in that case.
     * @param cache If this cache is non-null, it will be checked for a memoized result for this NFA, and will be populated
     *      with a memoized result when the call is complete.
     * @return DFA start states that are equivalent to the given NFA start states.  This will have the same length as nfaStartStates, with
     *         corresponding start states in corresponding positions.
     */
    @SuppressWarnings("unchecked")
    public static <MR> List<DfaState<MR>> buildFromNfa(Nfa<MR> nfa, int[] nfaStartStates, DfaAmbiguityResolver<? super MR> ambiguityResolver, BuilderCache cache )
    {
        String cacheKey = null;
        SerializableDfa<MR> serializableDfa = null;
        if (cache != null)
        {
            try
            {
                //generate the cache key by serializing key info into an SHA hash

                SHAOutputStream sha = new SHAOutputStream();
