// 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;

/*
 * Copyright 2015 Matthew Timmermans
 * 
 * Licensed 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 com.nobigsoftware.dfalex;



/**
 * Builds deterministic finite automata (google phrase) or DFAs that find patterns in strings
 * <P>
 * Given a set of patterns and the desired result of matching each pattern, you can produce a
 * DFA that will simultaneously match a sequence of characters against all of those patterns.
 * <P>
 * You can also build DFAs for multiple sets of patterns simultaneously. The resulting DFAs will
 * be optimized to share states wherever possible.
 * <P>
 * When you build a DFA to match a set of patterns, you get a "start state" (a {@link DfaState}) for
 * that pattern set. Each character of a string can be passed in turn to {@link DfaState#getNextState(char)},
 * which will return a new {@link DfaState}.
 * <P>
 * {@link DfaState#getMatch()} can be called at any time to get the MATCHRESULT (if any) for
 * the patterns that match the characters processed so far.
 * <P>
 * A {@link DfaState} can be used with a {@link StringMatcher} to find instances of patterns in strings,
 * or with other pattern-matching classes.
 * <P>
 * NOTE that building a Dfa is a complex procedure.  You should typically do it only once for each
 * pattern set you want to use.  Usually you would do this in a static initializer.
 * <P>
 * You can provide a cache that can remember and recall built DFAs, which allows you to build DFAs
 * during your build process in various ways, instead of building them at runtime.  Or you can use
 * the cache to store built DFAs on the first run of your program so they don't need to be built
 * the next time...  But this is usually unnecessary, since building DFAs is more than fast enough to
 * do during runtime initialization.
 * 
 * @param MATCHRESULT The type of result to produce by matching a pattern.  This must be serializable
 *      to support caching of built DFAs
 */
public class DfaBuilder<MATCHRESULT extends Serializable>
{
    //dfa types for cache keys
    private static final int DFATYPE_MATCHER = 0;
    private static final int DFATYPE_REVERSEFINDER = 1;
    

// 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;

/*
 * Copyright 2015 Matthew Timmermans
 * 
 * Licensed 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 com.nobigsoftware.dfalex;



/**
 * Builds deterministic finite automata (google phrase) or DFAs that find patterns in strings
 * <P>
 * Given a set of patterns and the desired result of matching each pattern, you can produce a
 * DFA that will simultaneously match a sequence of characters against all of those patterns.
 * <P>
 * You can also build DFAs for multiple sets of patterns simultaneously. The resulting DFAs will
 * be optimized to share states wherever possible.
 * <P>
 * When you build a DFA to match a set of patterns, you get a "start state" (a {@link DfaState}) for
 * that pattern set. Each character of a string can be passed in turn to {@link DfaState#getNextState(char)},
 * which will return a new {@link DfaState}.
 * <P>
 * {@link DfaState#getMatch()} can be called at any time to get the MATCHRESULT (if any) for
 * the patterns that match the characters processed so far.
 * <P>
 * A {@link DfaState} can be used with a {@link StringMatcher} to find instances of patterns in strings,
 * or with other pattern-matching classes.
 * <P>
 * NOTE that building a Dfa is a complex procedure.  You should typically do it only once for each
 * pattern set you want to use.  Usually you would do this in a static initializer.
 * <P>
 * You can provide a cache that can remember and recall built DFAs, which allows you to build DFAs
 * during your build process in various ways, instead of building them at runtime.  Or you can use
 * the cache to store built DFAs on the first run of your program so they don't need to be built
 * the next time...  But this is usually unnecessary, since building DFAs is more than fast enough to
 * do during runtime initialization.
 * 
 * @param MATCHRESULT The type of result to produce by matching a pattern.  This must be serializable
 *      to support caching of built DFAs
 */
public class DfaBuilder<MATCHRESULT extends Serializable>
{
    //dfa types for cache keys
    private static final int DFATYPE_MATCHER = 0;
    private static final int DFATYPE_REVERSEFINDER = 1;
    

    private final BuilderCache m_cache;
