src/include/fst/arc.h

   1 // See www.openfst.org for extensive documentation on this weighted
   2 // finite-state transducer library.
   3 //
   4 // Commonly used FST arc types.
   5
   6 #ifndef FST_LIB_ARC_H_
   7 #define FST_LIB_ARC_H_
   8
   9 #include <climits>
  10 #include <string>
  11 #include <utility>
  12
  13
  14 #include <fst/expectation-weight.h>
  15 #include <fst/float-weight.h>
  16 #include <fst/lexicographic-weight.h>
  17 #include <fst/power-weight.h>
  18 #include <fst/product-weight.h>
  19 #include <fst/signed-log-weight.h>
  20 #include <fst/sparse-power-weight.h>
  21 #include <fst/string-weight.h>
  22
  23
  24 namespace fst {
  25
  26 template <class W>
  27 struct ArcTpl {
  28  public:
  29   using Weight = W;
  30   using Label = int;
  31   using StateId = int;
  32
  33   Label ilabel;
  34   Label olabel;
  35   Weight weight;
  36   StateId nextstate;
  37
  38   ArcTpl() {}
  39
  40   ArcTpl(Label ilabel, Label olabel, Weight weight, StateId nextstate)
  41       : ilabel(ilabel),
  42         olabel(olabel),
  43         weight(std::move(weight)),
  44         nextstate(nextstate) {}
  45
  46   static const string &Type() {
  47     static const string *const type =
  48         new string(Weight::Type() == "tropical" ? "standard" : Weight::Type());
  49     return *type;
  50   }
  51 };
  52
  53 using StdArc = ArcTpl<TropicalWeight>;
  54 using LogArc = ArcTpl<LogWeight>;
  55 using Log64Arc = ArcTpl<Log64Weight>;
  56 using SignedLogArc = ArcTpl<SignedLogWeight>;
  57 using SignedLog64Arc = ArcTpl<SignedLog64Weight>;
  58 using MinMaxArc = ArcTpl<MinMaxWeight>;
  59
  60 // Arc with integer labels and state IDs and string weights.
  61 template <StringType S = STRING_LEFT>
  62 struct StringArc {
  63  public:
  64   using Label = int;
  65   using Weight = StringWeight<int, S>;
  66   using StateId = int;
  67
  68   Label ilabel;
  69   Label olabel;
  70   Weight weight;
  71   StateId nextstate;
  72
  73   StringArc() = default;
  74
  75   StringArc(Label ilabel, Label olabel, Weight weight, StateId nextstate)
  76       : ilabel(ilabel),
  77         olabel(olabel),
  78         weight(std::move(weight)),
  79         nextstate(nextstate) {}
  80
  81   static const string &Type() {
  82     static const string *const type =
  83         new string(S == STRING_LEFT
  84                        ? "left_standard_string"
  85                        : (S == STRING_RIGHT ? "right_standard_string"
  86                                             : "restricted_standard_string"));
  87     return *type;
  88   }
  89 };
  90
  91 // Arc with label and state Id type the same as template arg and with
  92 // weights over the Gallic semiring w.r.t the output labels and weights of A.
  93 template <class A, GallicType G = GALLIC_LEFT>
  94 struct GallicArc {
  95   using Arc = A;
  96   using Label = typename Arc::Label;
  97   using StateId = typename Arc::StateId;
  98   using Weight = GallicWeight<Label, typename Arc::Weight, G>;
  99
 100   Label ilabel;
 101   Label olabel;
 102   Weight weight;
 103   StateId nextstate;
 104
 105   GallicArc() = default;
 106
 107   GallicArc(Label ilabel, Label olabel, Weight weight, StateId nextstate)
 108       : ilabel(ilabel),
 109         olabel(olabel),
 110         weight(std::move(weight)),
 111         nextstate(nextstate) {}
 112
 113   explicit GallicArc(const Arc &arc)
 114       : ilabel(arc.ilabel), olabel(arc.ilabel), weight(arc.olabel, arc.weight),
 115         nextstate(arc.nextstate) {}
 116
 117   static const string &Type() {
 118     static const string *const type =
 119         new string(
 120             (G == GALLIC_LEFT
 121                  ? "left_gallic_"
 122                  : (G == GALLIC_RIGHT
 123                         ? "right_gallic_"
 124                         : (G == GALLIC_RESTRICT
 125                                ? "restricted_gallic_"
 126                                : (G == GALLIC_MIN
 127                                       ? "min_gallic_" : "gallic_")))) +
 128             Arc::Type());
 129     return *type;
 130   }
 131 };
 132
 133 // Arc with the reverse of the weight found in its template arg.
 134 template <class A>
 135 struct ReverseArc {
 136   using Arc = A;
 137   using Label = typename Arc::Label;
 138   using StateId = typename Arc::StateId;
 139   using AWeight = typename Arc::Weight;
 140   using Weight = typename AWeight::ReverseWeight;
 141
 142   Label ilabel;
 143   Label olabel;
 144   Weight weight;
 145   StateId nextstate;
 146
 147   ReverseArc() = default;
 148
 149   ReverseArc(Label ilabel, Label olabel, Weight weight, StateId nextstate)
 150       : ilabel(ilabel),
 151         olabel(olabel),
 152         weight(std::move(weight)),
 153         nextstate(nextstate) {}
 154
 155   static const string &Type() {
 156     static const string *const type = new string("reverse_" + Arc::Type());
 157     return *type;
 158   }
 159 };
 160
 161 // Arc with integer labels and state IDs and lexicographic weights.
 162 template <class Weight1, class Weight2>
 163 struct LexicographicArc {
 164   using Label = int;
 165   using StateId = int;
 166   using Weight = LexicographicWeight<Weight1, Weight2>;
 167
 168   Label ilabel;
 169   Label olabel;
 170   Weight weight;
 171   StateId nextstate;
 172
 173   LexicographicArc() = default;
 174
 175   LexicographicArc(Label ilabel, Label olabel, Weight weight, StateId nextstate)
 176       : ilabel(ilabel),
 177         olabel(olabel),
 178         weight(std::move(weight)),
 179         nextstate(nextstate) {}
 180
 181   static const string &Type() {
 182     static const string *const type = new string(Weight::Type());
 183     return *type;
 184   }
 185 };
 186
 187 // Arc with integer labels and state IDs and product weights.
 188 template <class Weight1, class Weight2>
 189 struct ProductArc {
 190   using Label = int;
 191   using StateId = int;
 192   using Weight = ProductWeight<Weight1, Weight2>;
 193
 194   Label ilabel;
 195   Label olabel;
 196   Weight weight;
 197   StateId nextstate;
 198
 199   ProductArc() = default;
 200
 201   ProductArc(Label ilabel, Label olabel, Weight weight, StateId nextstate)
 202       : ilabel(ilabel),
 203         olabel(olabel),
 204         weight(std::move(weight)),
 205         nextstate(nextstate) {}
 206
 207   static const string &Type() {
 208     static const string *const type = new string(Weight::Type());
 209     return *type;
 210   }
 211 };
 212
 213 // Arc with label and state ID type the same as first template argument and with
 214 // weights over the n-th Cartesian power of the weight type of the template
 215 // argument.
 216 template <class A, unsigned int N>
 217 struct PowerArc {
 218   using Arc = A;
 219   using Label = typename Arc::Label;
 220   using StateId = typename Arc::StateId;
 221   using Weight = PowerWeight<typename Arc::Weight, N>;
 222
 223   Label ilabel;
 224   Label olabel;
 225   Weight weight;
 226   StateId nextstate;
 227
 228   PowerArc() = default;
 229
 230   PowerArc(Label ilabel, Label olabel, Weight weight, StateId nextstate)
 231       : ilabel(ilabel),
 232         olabel(olabel),
 233         weight(std::move(weight)),
 234         nextstate(nextstate) {}
 235
 236   static const string &Type() {
 237     static const string *const type =
 238         new string(Arc::Type() + "_^" + std::to_string(N));
 239     return *type;
 240   }
 241 };
 242
 243 // Arc with label and state ID type the same as first template argument and with
 244 // weights over the arbitrary Cartesian power of the weight type.
 245 template <class A, class K = int>
 246 struct SparsePowerArc {
 247   using Arc = A;
 248   using Label = typename Arc::Label;
 249   using StateId = typename Arc::Label;
 250   using Weight = SparsePowerWeight<typename Arc::Weight, K>;
 251
 252   Label ilabel;
 253   Label olabel;
 254   Weight weight;
 255   StateId nextstate;
 256
 257   SparsePowerArc() = default;
 258
 259   SparsePowerArc(Label ilabel, Label olabel, Weight weight, StateId nextstate)
 260       : ilabel(ilabel),
 261         olabel(olabel),
 262         weight(std::move(weight)),
 263         nextstate(nextstate) {}
 264
 265   static const string &Type() {
 266     static const string *const type = [] {
 267       string type = Arc::Type() + "_^n";
 268       if (sizeof(K) != sizeof(uint32)) {
 269         type += "_" + std::to_string(CHAR_BIT * sizeof(K));
 270       }
 271       return new string(type);
 272     }();
 273     return *type;
 274   }
 275 };
 276
 277 // Arc with label and state ID type the same as first template argument and with
 278 // expectation weight over the first template argument's weight type and the
 279 // second template argument.
 280 template <class A, class X2>
 281 struct ExpectationArc {
 282   using Arc = A;
 283   using Label = typename Arc::Label;
 284   using StateId = typename Arc::StateId;
 285   using X1 = typename Arc::Weight;
 286   using Weight = ExpectationWeight<X1, X2>;
 287
 288   Label ilabel;
 289   Label olabel;
 290   Weight weight;
 291   StateId nextstate;
 292
 293   ExpectationArc() = default;
 294
 295   ExpectationArc(Label ilabel, Label olabel, Weight weight, StateId nextstate)
 296       : ilabel(ilabel),
 297         olabel(olabel),
 298         weight(std::move(weight)),
 299         nextstate(nextstate) {}
 300
 301   static const string &Type() {
 302     static const string *const type =
 303         new string("expectation_" + Arc::Type() + "_" + X2::Type());
 304     return *type;
 305   }
 306 };
 307
 308 }  // namespace fst
 309
 310 #endif  // FST_LIB_ARC_H_