| 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 |
} |