FST  openfst-1.8.2
OpenFst Library
arc.h
Go to the documentation of this file.
1 // Copyright 2005-2020 Google LLC
2 //
3 // Licensed under the Apache License, Version 2.0 (the 'License');
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an 'AS IS' BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // See www.openfst.org for extensive documentation on this weighted
16 // finite-state transducer library.
17 //
18 // Commonly used FST arc types.
19 
20 #ifndef FST_ARC_H_
21 #define FST_ARC_H_
22 
23 #include <climits>
24 #include <cstdint>
25 #include <string>
26 #include <type_traits>
27 #include <utility>
28 
29 
30 #include <fst/error-weight.h>
31 #include <fst/expectation-weight.h>
32 #include <fst/float-weight.h>
34 #include <fst/power-weight.h>
35 #include <fst/product-weight.h>
36 #include <fst/signed-log-weight.h>
38 #include <fst/string-weight.h>
39 
40 
41 namespace fst {
42 
43 template <class W>
44 struct ArcTpl {
45  public:
46  using Weight = W;
47  using Label = int;
48  using StateId = int;
49 
54 
55  ArcTpl() noexcept(std::is_nothrow_default_constructible_v<Weight>) {}
56 
57  template <class T>
58  ArcTpl(Label ilabel, Label olabel, T &&weight, StateId nextstate)
59  : ilabel(ilabel),
60  olabel(olabel),
61  weight(std::forward<T>(weight)),
62  nextstate(nextstate) {}
63 
64  // Arc with weight One.
65  ArcTpl(Label ilabel, Label olabel, StateId nextstate)
66  : ArcTpl(ilabel, olabel, Weight::One(), nextstate) {}
67 
68  static const std::string &Type() {
69  static const auto *const type = new std::string(
70  Weight::Type() == "tropical" ? "standard" : Weight::Type());
71  return *type;
72  }
73 };
74 
84 
85 // Arc with integer labels and state IDs and string weights.
86 template <StringType S = STRING_LEFT>
87 struct StringArc {
88  public:
89  using Label = int;
91  using StateId = int;
92 
97 
98  StringArc() = default;
99 
100  template <class T>
101  StringArc(Label ilabel, Label olabel, T &&weight, StateId nextstate)
102  : ilabel(ilabel),
103  olabel(olabel),
104  weight(std::forward<T>(weight)),
105  nextstate(nextstate) {}
106 
107  // Arc with weight One.
108  StringArc(Label ilabel, Label olabel, StateId nextstate)
109  : StringArc(ilabel, olabel, Weight::One(), nextstate) {}
110 
111  static const std::string &Type() {
112  static const auto *const type = new std::string(
113  S == STRING_LEFT ? "left_standard_string"
114  : (S == STRING_RIGHT ? "right_standard_string"
115  : "restricted_standard_string"));
116  return *type;
117  }
118 };
119 
120 // Arc with label and state Id type the same as template arg and with
121 // weights over the Gallic semiring w.r.t the output labels and weights of A.
122 template <class A, GallicType G = GALLIC_LEFT>
123 struct GallicArc {
124  using Arc = A;
125  using Label = typename Arc::Label;
126  using StateId = typename Arc::StateId;
128 
133 
134  GallicArc() = default;
135 
136  template <class T>
137  GallicArc(Label ilabel, Label olabel, T &&weight, StateId nextstate)
138  : ilabel(ilabel),
139  olabel(olabel),
140  weight(std::forward<T>(weight)),
141  nextstate(nextstate) {}
142 
143  // Arc with weight One.
144  GallicArc(Label ilabel, Label olabel, StateId nextstate)
145  : GallicArc(ilabel, olabel, Weight::One(), nextstate) {}
146 
147  explicit GallicArc(const Arc &arc)
148  : ilabel(arc.ilabel),
149  olabel(arc.ilabel),
150  weight(arc.olabel, arc.weight),
151  nextstate(arc.nextstate) {}
152 
153  static const std::string &Type() {
154  static const auto *const type = new std::string(
155  (G == GALLIC_LEFT
156  ? "left_gallic_"
157  : (G == GALLIC_RIGHT
158  ? "right_gallic_"
159  : (G == GALLIC_RESTRICT
160  ? "restricted_gallic_"
161  : (G == GALLIC_MIN ? "min_gallic_" : "gallic_")))) +
162  Arc::Type());
163  return *type;
164  }
165 };
166 
167 // Arc with the reverse of the weight found in its template arg.
168 template <class A>
169 struct ReverseArc {
170  using Arc = A;
171  using Label = typename Arc::Label;
172  using StateId = typename Arc::StateId;
173  using Weight = typename Arc::Weight::ReverseWeight;
174 
179 
180  ReverseArc() = default;
181 
182  template <class T>
183  ReverseArc(Label ilabel, Label olabel, T &&weight, StateId nextstate)
184  : ilabel(ilabel),
185  olabel(olabel),
186  weight(std::forward<T>(weight)),
187  nextstate(nextstate) {}
188 
189  // Arc with weight One.
190  ReverseArc(Label ilabel, Label olabel, StateId nextstate)
191  : ReverseArc(ilabel, olabel, Weight::One(), nextstate) {}
192 
193  static const std::string &Type() {
194  static const auto *const type = new std::string("reverse_" + Arc::Type());
195  return *type;
196  }
197 };
198 
199 // Arc with integer labels and state IDs and lexicographic weights.
200 template <class Weight1, class Weight2>
202 
203 // Arc with integer labels and state IDs and product weights.
204 template <class Weight1, class Weight2>
206 
207 // Arc with label and state ID type the same as first template argument and with
208 // weights over the n-th Cartesian power of the weight type of the template
209 // argument.
210 template <class A, size_t n>
211 struct PowerArc {
212  using Arc = A;
213  using Label = typename Arc::Label;
214  using StateId = typename Arc::StateId;
216 
221 
222  PowerArc() = default;
223 
224  template <class T>
225  PowerArc(Label ilabel, Label olabel, T &&weight, StateId nextstate)
226  : ilabel(ilabel),
227  olabel(olabel),
228  weight(std::forward<T>(weight)),
229  nextstate(nextstate) {}
230 
231  // Arc with weight One.
232  PowerArc(Label ilabel, Label olabel, StateId nextstate)
233  : PowerArc(ilabel, olabel, Weight::One(), nextstate) {}
234 
235  static const std::string &Type() {
236  static const auto *const type =
237  new std::string(Arc::Type() + "_^" + std::to_string(n));
238  return *type;
239  }
240 };
241 
242 // Arc with label and state ID type the same as first template argument and with
243 // weights over the arbitrary Cartesian power of the weight type.
244 template <class A, class K = int>
246  using Arc = A;
247  using Label = typename Arc::Label;
248  using StateId = typename Arc::Label;
250 
255 
256  SparsePowerArc() = default;
257 
258  template <class T>
259  SparsePowerArc(Label ilabel, Label olabel, T &&weight, StateId nextstate)
260  : ilabel(ilabel),
261  olabel(olabel),
262  weight(std::forward<T>(weight)),
263  nextstate(nextstate) {}
264 
265  // Arc with weight One.
266  SparsePowerArc(Label ilabel, Label olabel, StateId nextstate)
267  : SparsePowerArc(ilabel, olabel, Weight::One(), nextstate) {}
268 
269  static const std::string &Type() {
270  static const std::string *const type = [] {
271  std::string type = Arc::Type() + "_^n";
272  if (sizeof(K) != sizeof(uint32_t)) {
273  type += "_" + std::to_string(CHAR_BIT * sizeof(K));
274  }
275  return new std::string(type);
276  }();
277  return *type;
278  }
279 };
280 
281 // Arc with label and state ID type the same as first template argument and with
282 // expectation weight over the first template argument's weight type and the
283 // second template argument.
284 template <class A, class X2>
286  using Arc = A;
287  using Label = typename Arc::Label;
288  using StateId = typename Arc::StateId;
289  using X1 = typename Arc::Weight;
291 
296 
297  ExpectationArc() = default;
298 
299  template <class T>
300  ExpectationArc(Label ilabel, Label olabel, T &&weight, StateId nextstate)
301  : ilabel(ilabel),
302  olabel(olabel),
303  weight(std::forward<T>(weight)),
304  nextstate(nextstate) {}
305 
306  // Arc with weight One.
307  ExpectationArc(Label ilabel, Label olabel, StateId nextstate)
308  : ExpectationArc(ilabel, olabel, Weight::One(), nextstate) {}
309 
310  static const std::string &Type() {
311  static const auto *const type =
312  new std::string("expectation_" + Arc::Type() + "_" + X2::Type());
313  return *type;
314  }
315 };
316 
317 } // namespace fst
318 
319 #endif // FST_ARC_H_
Label olabel
Definition: arc.h:176
typename Arc::Weight X1
Definition: arc.h:289
typename Arc::StateId StateId
Definition: arc.h:126
Label ilabel
Definition: arc.h:93
PowerArc(Label ilabel, Label olabel, T &&weight, StateId nextstate)
Definition: arc.h:225
W Weight
Definition: arc.h:46
Label ilabel
Definition: arc.h:251
Label ilabel
Definition: arc.h:129
int Label
Definition: arc.h:47
SparsePowerArc(Label ilabel, Label olabel, StateId nextstate)
Definition: arc.h:266
static const std::string & Type()
Definition: arc.h:310
ExpectationArc(Label ilabel, Label olabel, T &&weight, StateId nextstate)
Definition: arc.h:300
GallicArc(Label ilabel, Label olabel, T &&weight, StateId nextstate)
Definition: arc.h:137
Label ilabel
Definition: arc.h:217
typename Arc::StateId StateId
Definition: arc.h:214
int StateId
Definition: arc.h:91
typename Arc::Label Label
Definition: arc.h:171
static const std::string & Type()
Definition: arc.h:68
ReverseArc(Label ilabel, Label olabel, StateId nextstate)
Definition: arc.h:190
Label olabel
Definition: arc.h:130
typename Arc::Label Label
Definition: arc.h:125
Weight weight
Definition: arc.h:95
StateId nextstate
Definition: arc.h:295
static const std::string & Type()
Definition: arc.h:269
ArcTpl() noexcept(std::is_nothrow_default_constructible_v< Weight >)
Definition: arc.h:55
Weight weight
Definition: arc.h:253
typename Arc::Label Label
Definition: arc.h:287
Label olabel
Definition: arc.h:51
typename Arc::StateId StateId
Definition: arc.h:172
typename Arc::Label Label
Definition: arc.h:247
typename Arc::Weight::ReverseWeight Weight
Definition: arc.h:173
Label olabel
Definition: arc.h:218
int StateId
Definition: arc.h:48
static const std::string & Type()
Definition: arc.h:111
Weight weight
Definition: arc.h:219
int Label
Definition: arc.h:89
Label olabel
Definition: arc.h:293
StateId nextstate
Definition: arc.h:96
typename Arc::StateId StateId
Definition: arc.h:288
static const std::string & Type()
Definition: arc.h:235
Label ilabel
Definition: arc.h:292
StateId nextstate
Definition: arc.h:254
ArcTpl(Label ilabel, Label olabel, T &&weight, StateId nextstate)
Definition: arc.h:58
Weight weight
Definition: arc.h:177
Label olabel
Definition: arc.h:94
SparsePowerArc(Label ilabel, Label olabel, T &&weight, StateId nextstate)
Definition: arc.h:259
typename Arc::Label Label
Definition: arc.h:213
Label ilabel
Definition: arc.h:175
Label ilabel
Definition: arc.h:50
static const std::string & Type()
Definition: arc.h:153
StringArc(Label ilabel, Label olabel, StateId nextstate)
Definition: arc.h:108
StateId nextstate
Definition: arc.h:53
static const std::string & Type()
Definition: arc.h:193
Weight weight
Definition: arc.h:52
Weight weight
Definition: arc.h:294
ReverseArc(Label ilabel, Label olabel, T &&weight, StateId nextstate)
Definition: arc.h:183
GallicArc(const Arc &arc)
Definition: arc.h:147
StateId nextstate
Definition: arc.h:132
Label olabel
Definition: arc.h:252
Weight weight
Definition: arc.h:131
StateId nextstate
Definition: arc.h:178
ArcTpl(Label ilabel, Label olabel, StateId nextstate)
Definition: arc.h:65
typename Arc::Label StateId
Definition: arc.h:248
StateId nextstate
Definition: arc.h:220
PowerArc(Label ilabel, Label olabel, StateId nextstate)
Definition: arc.h:232
StringArc(Label ilabel, Label olabel, T &&weight, StateId nextstate)
Definition: arc.h:101
GallicArc(Label ilabel, Label olabel, StateId nextstate)
Definition: arc.h:144
ExpectationArc(Label ilabel, Label olabel, StateId nextstate)
Definition: arc.h:307