Debian Codegraph @

morfologik-fsa-builders/src/test/java/morfologik/fsa/builders/FSATestUtils.java

raw
1 package morfologik.fsa.builders;
2
3 import java.nio.ByteBuffer;
4 import java.util.*;
5
6 import morfologik.fsa.FSA;
7 import morfologik.fsa.StateVisitor;
8 import static com.carrotsearch.randomizedtesting.RandomizedTest.*;
9 import static org.junit.Assert.*;
10
11 public class FSATestUtils {
12 /*
13 * Generate a sorted list of random sequences.
14 */
15 public static byte[][] generateRandom(int count, MinMax length, MinMax alphabet) {
16 final byte[][] input = new byte[count][];
17 final Random rnd = new Random(randomLong());
18 for (int i = 0; i < count; i++) {
19 input[i] = randomByteSequence(rnd, length, alphabet);
20 }
21 Arrays.sort(input, FSABuilder.LEXICAL_ORDERING);
22 return input;
23 }
24
25 /**
26 * Generate a random string.
27 */
28 private static byte[] randomByteSequence(Random rnd, MinMax length, MinMax alphabet) {
29 byte[] bytes = new byte[length.min + rnd.nextInt(length.range())];
30 for (int i = 0; i < bytes.length; i++) {
31 bytes[i] = (byte) (alphabet.min + rnd.nextInt(alphabet.range()));
32 }
33 return bytes;
34 }
35
36 /*
37 * Check if the DFSA is correct with respect to the given input.
38 */
39 public static void checkCorrect(byte[][] input, FSA fsa) {
40 // (1) All input sequences are in the right language.
41 HashSet<ByteBuffer> rl = new HashSet<ByteBuffer>();
42 for (ByteBuffer bb : fsa) {
43 rl.add(ByteBuffer.wrap(Arrays.copyOf(bb.array(), bb.remaining())));
44 }
45
46 HashSet<ByteBuffer> uniqueInput = new HashSet<ByteBuffer>();
47 for (byte[] sequence : input) {
48 uniqueInput.add(ByteBuffer.wrap(sequence));
49 }
50
51 for (ByteBuffer sequence : uniqueInput) {
52 if (!rl.remove(sequence)) {
53 fail("Not present in the right language: " + SerializerTestBase.toString(sequence));
54 }
55 }
56
57 // (2) No other sequence _other_ than the input is in the right language.
58 assertEquals(0, rl.size());
59 }
60
61 /*
62 * Check if the DFSA reachable from a given state is minimal. This means no
63 * two states have the same right language.
64 */
65 public static void checkMinimal(final FSA fsa) {
66 final HashMap<String, Integer> stateLanguages = new HashMap<String, Integer>();
67
68 fsa.visitInPostOrder(new StateVisitor() {
69 private StringBuilder b = new StringBuilder();
70
71 public boolean accept(int state) {
72 List<byte[]> rightLanguage = allSequences(fsa, state);
73 Collections.sort(rightLanguage, FSABuilder.LEXICAL_ORDERING);
74
75 b.setLength(0);
76 for (byte[] seq : rightLanguage) {
77 b.append(Arrays.toString(seq));
78 b.append(',');
79 }
80
81 String full = b.toString();
82 assertFalse("State exists: " + state + " " + full + " " + stateLanguages.get(full),
83 stateLanguages.containsKey(full));
84 stateLanguages.put(full, state);
85
86 return true;
87 }
88 });
89 }
90
91 static List<byte[]> allSequences(FSA fsa, int state) {
92 ArrayList<byte[]> seq = new ArrayList<byte[]>();
93 for (ByteBuffer bb : fsa.getSequences(state)) {
94 seq.add(Arrays.copyOf(bb.array(), bb.remaining()));
95 }
96 return seq;
97 }
98
99 /*
100 * Check if two FSAs are identical.
101 */
102 public static void checkIdentical(FSA fsa1, FSA fsa2) {
103 ArrayDeque<String> fromRoot = new ArrayDeque<String>();
104 checkIdentical(fromRoot, fsa1, fsa1.getRootNode(), new BitSet(), fsa2, fsa2.getRootNode(), new BitSet());
105 }
106
107 /*
108 *
109 */
110 static void checkIdentical(ArrayDeque<String> fromRoot, FSA fsa1, int node1, BitSet visited1, FSA fsa2, int node2,
111 BitSet visited2) {
112 int arc1 = fsa1.getFirstArc(node1);
113 int arc2 = fsa2.getFirstArc(node2);
114
115 if (visited1.get(node1) != visited2.get(node2)) {
116 throw new RuntimeException("Two nodes should either be visited or not visited: "
117 + Arrays.toString(fromRoot.toArray()) + " " + " node1: " + node1 + " " + " node2: " + node2);
118 }
119 visited1.set(node1);
120 visited2.set(node2);
121
122 TreeSet<Character> labels1 = new TreeSet<Character>();
123 TreeSet<Character> labels2 = new TreeSet<Character>();
124 while (true) {
125 labels1.add((char) fsa1.getArcLabel(arc1));
126 labels2.add((char) fsa2.getArcLabel(arc2));
127
128 arc1 = fsa1.getNextArc(arc1);
129 arc2 = fsa2.getNextArc(arc2);
130
131 if (arc1 == 0 || arc2 == 0) {
132 if (arc1 != arc2) {
133 throw new RuntimeException("Different number of labels at path: " + Arrays.toString(fromRoot.toArray()));
134 }
135 break;
136 }
137 }
138
139 if (!labels1.equals(labels2)) {
140 throw new RuntimeException("Different sets of labels at path: " + Arrays.toString(fromRoot.toArray()) + ":\n"
141 + labels1 + "\n" + labels2);
142 }
143
144 // recurse.
145 for (char chr : labels1) {
146 byte label = (byte) chr;
147 fromRoot.push(Character.isLetterOrDigit(chr) ? Character.toString(chr) : Integer.toString(chr));
148
149 arc1 = fsa1.getArc(node1, label);
150 arc2 = fsa2.getArc(node2, label);
151
152 if (fsa1.isArcFinal(arc1) != fsa2.isArcFinal(arc2)) {
153 throw new RuntimeException("Different final flag on arcs at: " + Arrays.toString(fromRoot.toArray())
154 + ", label: " + label);
155 }
156
157 if (fsa1.isArcTerminal(arc1) != fsa2.isArcTerminal(arc2)) {
158 throw new RuntimeException("Different terminal flag on arcs at: " + Arrays.toString(fromRoot.toArray())
159 + ", label: " + label);
160 }
161
162 if (!fsa1.isArcTerminal(arc1)) {
163 checkIdentical(fromRoot, fsa1, fsa1.getEndNode(arc1), visited1, fsa2, fsa2.getEndNode(arc2), visited2);
164 }
165
166 fromRoot.pop();
167 }
168 }
169 }