Debian Codegraph @

morfologik-fsa-builders/src/main/java/morfologik/fsa/builders/FSAInfo.java

raw
1 package morfologik.fsa.builders;
2
3 import java.util.BitSet;
4
5 import morfologik.fsa.FSA;
6 import morfologik.fsa.FSA5;
7
8 import com.carrotsearch.hppc.IntIntHashMap;
9
10 /**
11 * Compute additional information about an FSA: number of arcs, nodes, etc.
12 */
13 public final class FSAInfo {
14 /**
15 * Computes the exact number of states and nodes by recursively traversing the FSA.
16 */
17 private static class NodeVisitor {
18 final BitSet visitedArcs = new BitSet();
19 final BitSet visitedNodes = new BitSet();
20
21 int nodes;
22 int arcs;
23 int totalArcs;
24
25 private final FSA fsa;
26
27 NodeVisitor(FSA fsa) {
28 this.fsa = fsa;
29 }
30
31 public void visitNode(final int node) {
32 if (visitedNodes.get(node)) {
33 return;
34 }
35 visitedNodes.set(node);
36
37 nodes++;
38 for (int arc = fsa.getFirstArc(node); arc != 0; arc = fsa.getNextArc(arc)) {
39 if (!visitedArcs.get(arc)) {
40 arcs++;
41 }
42 totalArcs++;
43 visitedArcs.set(arc);
44
45 if (!fsa.isArcTerminal(arc)) {
46 visitNode(fsa.getEndNode(arc));
47 }
48 }
49 }
50 }
51
52 /**
53 * Computes the exact number of final states.
54 */
55 private static class FinalStateVisitor {
56 final IntIntHashMap visitedNodes = new IntIntHashMap();
57
58 private final FSA fsa;
59
60 FinalStateVisitor(FSA fsa) {
61 this.fsa = fsa;
62 }
63
64 public int visitNode(int node) {
65 int index = visitedNodes.indexOf(node);
66 if (index >= 0) {
67 return visitedNodes.indexGet(index);
68 }
69
70 int fromHere = 0;
71 for (int arc = fsa.getFirstArc(node); arc != 0; arc = fsa.getNextArc(arc)) {
72 if (fsa.isArcFinal(arc))
73 fromHere++;
74
75 if (!fsa.isArcTerminal(arc)) {
76 fromHere += visitNode(fsa.getEndNode(arc));
77 }
78 }
79 visitedNodes.put(node, fromHere);
80 return fromHere;
81 }
82 }
83
84 /**
85 * Number of nodes in the automaton.
86 */
87 public final int nodeCount;
88
89 /**
90 * Number of arcs in the automaton, excluding an arcs from the zero node (initial) and an arc from the start node to
91 * the root node.
92 */
93 public final int arcsCount;
94
95 /**
96 * Total number of arcs, counting arcs that physically overlap due to merging.
97 */
98 public final int arcsCountTotal;
99
100 /**
101 * Number of final states (number of input sequences stored in the automaton).
102 */
103 public final int finalStatesCount;
104
105 /**
106 * Arcs size (in serialized form).
107 */
108 public final int size;
109
110 /*
111 *
112 */
113 public FSAInfo(FSA fsa) {
114 final NodeVisitor w = new NodeVisitor(fsa);
115 int root = fsa.getRootNode();
116 if (root > 0) {
117 w.visitNode(root);
118 }
119
120 this.nodeCount = 1 + w.nodes;
121 this.arcsCount = 1 + w.arcs;
122 this.arcsCountTotal = 1 + w.totalArcs;
123
124 final FinalStateVisitor fsv = new FinalStateVisitor(fsa);
125 this.finalStatesCount = fsv.visitNode(fsa.getRootNode());
126
127 if (fsa instanceof FSA5) {
128 this.size = ((FSA5) fsa).arcs.length;
129 } else {
130 this.size = 0;
131 }
132 }
133
134 /*
135 *
136 */
137 public FSAInfo(int nodeCount, int arcsCount, int arcsCountTotal, int finalStatesCount) {
138 this.nodeCount = nodeCount;
139 this.arcsCount = arcsCount;
140 this.arcsCountTotal = arcsCountTotal;
141 this.finalStatesCount = finalStatesCount;
142 this.size = 0;
143 }
144
145 /*
146 *
147 */
148 @Override
149 public String toString() {
150 return "Nodes: " + nodeCount + ", arcs visited: " + arcsCount + ", arcs total: " + arcsCountTotal
151 + ", final states: " + finalStatesCount + ", size: " + size;
152 }
153 }