code: package morfologik.fsa.builders;
  
  import java.nio.ByteBuffer;
  import java.util.*;
  
  import morfologik.fsa.FSA;
  import morfologik.fsa.StateVisitor;
  import static com.carrotsearch.randomizedtesting.RandomizedTest.*;
  import static org.junit.Assert.*;
  
  public class FSATestUtils {
    /*
     * Generate a sorted list of random sequences.
     */
    public static byte[][] generateRandom(int count, MinMax length, MinMax alphabet) {
      final byte[][] input = new byte[count][];
      final Random rnd = new Random(randomLong());
      for (int i = 0; i < count; i++) {
        input[i] = randomByteSequence(rnd, length, alphabet);
      }
      Arrays.sort(input, FSABuilder.LEXICAL_ORDERING);
      return input;
    }
  
    /**
     * Generate a random string.
     */
    private static byte[] randomByteSequence(Random rnd, MinMax length, MinMax alphabet) {
      byte[] bytes = new byte[length.min + rnd.nextInt(length.range())];
      for (int i = 0; i < bytes.length; i++) {
        bytes[i] = (byte) (alphabet.min + rnd.nextInt(alphabet.range()));
      }
      return bytes;
    }
  
    /*
     * Check if the DFSA is correct with respect to the given input.
     */
    public static void checkCorrect(byte[][] input, FSA fsa) {
      // (1) All input sequences are in the right language.
      HashSet<ByteBuffer> rl = new HashSet<ByteBuffer>();
      for (ByteBuffer bb : fsa) {
        rl.add(ByteBuffer.wrap(Arrays.copyOf(bb.array(), bb.remaining())));
      }
  
      HashSet<ByteBuffer> uniqueInput = new HashSet<ByteBuffer>();
      for (byte[] sequence : input) {
        uniqueInput.add(ByteBuffer.wrap(sequence));
      }
  
      for (ByteBuffer sequence : uniqueInput) {
        if (!rl.remove(sequence)) {
          fail("Not present in the right language: " + SerializerTestBase.toString(sequence));
        }
      }
  
      // (2) No other sequence _other_ than the input is in the right language.
      assertEquals(0, rl.size());
    }
  
    /*
     * Check if the DFSA reachable from a given state is minimal. This means no
     * two states have the same right language.
     */
    public static void checkMinimal(final FSA fsa) {
      final HashMap<String, Integer> stateLanguages = new HashMap<String, Integer>();
  
      fsa.visitInPostOrder(new StateVisitor() {
        private StringBuilder b = new StringBuilder();
  
        public boolean accept(int state) {
          List<byte[]> rightLanguage = allSequences(fsa, state);
          Collections.sort(rightLanguage, FSABuilder.LEXICAL_ORDERING);
  
          b.setLength(0);
          for (byte[] seq : rightLanguage) {
            b.append(Arrays.toString(seq));
            b.append(',');
          }
  
          String full = b.toString();
          assertFalse("State exists: " + state + " " + full + " " + stateLanguages.get(full),
              stateLanguages.containsKey(full));
          stateLanguages.put(full, state);
  
          return true;
        }
      });
    }
  
    static List<byte[]> allSequences(FSA fsa, int state) {
      ArrayList<byte[]> seq = new ArrayList<byte[]>();
      for (ByteBuffer bb : fsa.getSequences(state)) {
        seq.add(Arrays.copyOf(bb.array(), bb.remaining()));
      }
      return seq;
    }
  
    /*
     * Check if two FSAs are identical.
     */
    public static void checkIdentical(FSA fsa1, FSA fsa2) {
      ArrayDeque<String> fromRoot = new ArrayDeque<String>();
      checkIdentical(fromRoot, fsa1, fsa1.getRootNode(), new BitSet(), fsa2, fsa2.getRootNode(), new BitSet());
    }
  
    /*
     * 
     */
    static void checkIdentical(ArrayDeque<String> fromRoot, FSA fsa1, int node1, BitSet visited1, FSA fsa2, int node2,
        BitSet visited2) {
      int arc1 = fsa1.getFirstArc(node1);
      int arc2 = fsa2.getFirstArc(node2);
  
      if (visited1.get(node1) != visited2.get(node2)) {
        throw new RuntimeException("Two nodes should either be visited or not visited: "
            + Arrays.toString(fromRoot.toArray()) + " " + " node1: " + node1 + " " + " node2: " + node2);
      }
      visited1.set(node1);
      visited2.set(node2);
  
      TreeSet<Character> labels1 = new TreeSet<Character>();
      TreeSet<Character> labels2 = new TreeSet<Character>();
      while (true) {
        labels1.add((char) fsa1.getArcLabel(arc1));
        labels2.add((char) fsa2.getArcLabel(arc2));
  
        arc1 = fsa1.getNextArc(arc1);
        arc2 = fsa2.getNextArc(arc2);
  
        if (arc1 == 0 || arc2 == 0) {
          if (arc1 != arc2) {
            throw new RuntimeException("Different number of labels at path: " + Arrays.toString(fromRoot.toArray()));
          }
          break;
        }
      }
  
      if (!labels1.equals(labels2)) {
        throw new RuntimeException("Different sets of labels at path: " + Arrays.toString(fromRoot.toArray()) + ":\n"
            + labels1 + "\n" + labels2);
      }
  
      // recurse.
      for (char chr : labels1) {
        byte label = (byte) chr;
        fromRoot.push(Character.isLetterOrDigit(chr) ? Character.toString(chr) : Integer.toString(chr));
  
        arc1 = fsa1.getArc(node1, label);
        arc2 = fsa2.getArc(node2, label);
  
        if (fsa1.isArcFinal(arc1) != fsa2.isArcFinal(arc2)) {
          throw new RuntimeException("Different final flag on arcs at: " + Arrays.toString(fromRoot.toArray())
              + ", label: " + label);
        }
  
        if (fsa1.isArcTerminal(arc1) != fsa2.isArcTerminal(arc2)) {
          throw new RuntimeException("Different terminal flag on arcs at: " + Arrays.toString(fromRoot.toArray())
              + ", label: " + label);
        }
  
        if (!fsa1.isArcTerminal(arc1)) {
          checkIdentical(fromRoot, fsa1, fsa1.getEndNode(arc1), visited1, fsa2, fsa2.getEndNode(arc2), visited2);
        }
  
        fromRoot.pop();
      }
    }
  }
  